Happy birthday to you!
Your professor gives you a strange device as your birthday gift. But your experience tells you, it is a trap.
Just as expected, he smirks, and then says slowly: "This device is my new invention. Only you, my most brilliant student, deserve to have it."
"Thanks, I will keep it up." You reply.
"However," silent for a while, he starts again: "unfortunately, I have lost its original circuit diagram. So I need you to do some researches on it and use a simple logical expression to describe its characteristics. You won't let me down, will you?"
He laughs, pats you on the back, then turns and stalks off, leaves you, the poor guy, with the "gift" on your hands.
You collect yourself, and start looking at the "lovely" thing. It is a black box, with n inputs labeled from the first capital letter (A) to the n-th capital letter, as well as one unique output. All the inputs and the output are one-bit binary numbers (either 0 or 1).
Then you sit down, put the device on the desk, take out the tools, examine all possible combinations of input values and record the output on the paper.
After everything gets ready, now it is just a piece of cake for you to give a correct logical expression for it.
A correct logical expression should be:
1. A not null string only contains '+', '-' and capital letters from the first (A) to the n-th;
2. A single capital letter in range is a legal logical expression, and its output equals to the value of the input labeled by this letter;
3. If E is a legal logical expression, then NOT operation -E is a legal logical expression;
4. If E and F are legal logical expressions, then AND operation EF is a legal logical expression;
5. If E and F are legal logical expressions, then OR operation E+F is a legal logical expression;
6. In a legal logical expression, you should first do NOT operations from the left to the right, then AND operations from the left to the right, and finally the OR operations from the left to the right;
7. A logical expression is correct if and only if with any possible combinations of input values, its output is the same as which the device outputs.
But as a down-to-earth idealist, you are never satisfied with this. You want to give the most beautiful logical expression like this:
1. It is a correct logical expression;
2. It is the shortest one (not null) among all correct logical expressions;
3. If there are still many available logical expressions, choose the lexicographically least one.