To refresh your memory, a truth table shows you the possible interpretations of a sentence. On one side is listed all the possible values for each variable in the sentence. For each interpretation, the value of sentence using those values for the variables, is given.
Each test case has two lines. The first line contains variable names. This line will have no embedded spaces, and will have only correct variable names present. A variable name is a single upper case letter. The second line gives a sentence to be tested using those variables. There will be no more than 5 variables for any given sentence.
A sentence consists of variable names, the `and' operator (&), the `or' operator (|), the negation operator (~), or parentheses. For our purposes, all sentences evaluate left to right (ie, they have equal precedence). Negation is a unary operation. Parentheses are used to "up the precedence" of whatever is inside. No other values will appear. No line of input will be more than 80 characters.
The truth tables for the basic operations are:
| P | Q | P & Q | P | Q | ~P |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
For each sentence, you are to produce a truth table then say if the sentence is valid. The first line of output for a test case should the name of each variable (in the same order as given in the input), separated by exactly one space. After the last variable, print a space, two vertical bars (||), a space, then the sentence. The sentence should appear exactly as given in the input.
Each line after the first will show the values (either T for true, or F for false) for each variable. Each value is separated by a space (ie, the value lines up underneath the variable). After the last value, print a space, followed by two vertical bars (||), a space, then the value of the sentence (either T for true or F for false).
After the truth table, print one sentence saying either:
The order of rows in the truth table is important. Consider a coding for the values of each variable whereby a 0 is false and a 1 is true. Write the values of the variables down in the order they appear in the first line of input. Convert that bit string to decimal number (the rightmost bit is the least significant one. ie, the rightmost bit is 2^0.) The rows in the truth table should be strictly monotonically increasing (ie, row3 > row2 > row1).
If a variable appears in the sentence that wasn't specified on the first line of the test case, then that variable is to be considered a constant true value. It is fine if all the variables specified on the first line of each test case is not used in the sentence itself.
AB A | ~A ACB A & ~(B | C)
A B || A | ~A F F || T F T || T T F || T T T || T Sentence is valid A C B || A & ~(B | C) F F F || F F F T || F F T F || F F T T || F T F F || T T F T || F T T F || F T T T || F Sentence is not valid