Description

Logic is a science that studies propositions and their truth values. A proposition is usually represented by a lowercase letter, and the value of any proposition is either true or false. We use T to denote that a proposition is true, and F to denote that a proposition is false.

Operators between propositions are called propositional connectives, or simply connectives. The three most basic connectives in a logic system are NOT, AND, and OR. For simplicity, we use $!$ for NOT, $\&$ for AND, and $|$ for OR.

The NOT connective is a unary connective. For any proposition $p$, the truth value of $!p$ is always the opposite of $p$.

The AND connective, also called conjunction, is a binary connective. For any propositions $p$ and $q$, $p\&q$ is true if and only if both $p$ and $q$ are true; otherwise, $p\&q$ is false.

The OR connective, also called disjunction, is a binary connective. For any propositions $p$ and $q$, $p|q$ is false if and only if both $p$ and $q$ are false; otherwise, $p|q$ is true.

Below is the truth table of the three basic propositional connectives:

A logical expression is composed of propositions, connectives, and parentheses. It is defined as follows:

<Expression> ::=<Conjunction> or <Disjunction> or <Negation> or (<Expression>) or <Atom>

<Conjunction> ::=<Expression>&<Expression>

<Disjunction> ::=<Expression>|<Expression>

<Negation> ::=!<Expression>

<Atom> ::=<Proposition>

Note: here, is a lowercase letter from $a$ to $z$, ::= means “is defined as”, and or means “or”.

The evaluation of an expression is the process of performing propositional operations according to the truth values of propositions in the expression and the truth tables. The operator precedence is $()$, $!$, $\&$, and $|$. $\&$ and $|$ have the same precedence. Operators with the same precedence are evaluated from left to right.

An AND-OR-NOT logical normal form (hereinafter referred to as “normal form”) is a logical expression that matches a specific truth table. For example, in standard logic, the implication operator $\rightarrow$ has the following truth table:

We can use the expression $!p|q$ to represent this implication. The truth table of $!p|q$ is:

Thus, we say that the normal form of $p \to q$ is $!p|q$.

The completeness theorem tells us that for any $n$-ary logical function $A$, given the truth table of $A$, we can always find a normal form of $A$. A normal form contains only propositions, the three basic connectives, and parentheses. For example, the following is the truth table of a ternary function $A(p,q,r)$:

That is, when at least two of $p, q, r$ are true, $A$ is true; otherwise, $A$ is false.

Of course, the normal form is not unique. Suppose one normal form of $A$ is $(p\&q\&r)|(!p\&q\&r)|(p\&!q\&r)|(p\&q\&!r)$. Then the expression $(p\&q)|(q\&r)|(p\&r)$ is also a normal form of $A$, and its length is shorter than the former.

Your task is: given the truth table of an $n$-ary function $A$, find a normal form of $A$, and make the normal form as short as possible.

Constraints

Input Format

The first line of the input file is $n$ ($n \leq 6$), indicating that $A$ is an $n$-ary function. Then there are $2^n$ lines. Each line is a string of length $n+1$, containing only characters T and F. The first $n$ characters in order represent the values of the $n$ propositions, and the last character represents the value of $A$ under this assignment.

Output Format

The output file contains one line: the normal form you provide. The propositions are represented in order by lowercase letters $a, b, c, d, \ldots$.

3
TTTT
TTFT
TFTT
TFFF
FTTT
FTFF
FFTF
FFFF

a&b|(a|b&c)

Hint

Scoring:

• If the normal form you give is incorrect, or you do not produce a solution within the time limit, you get $0$ points for that test.
• If the length of your normal form is less than or equal to the length of the standard answer, you get full points for that test.
• If the length of your normal form is at least twice the length of the standard answer, you get $0$ points for that test.
• If the length of your normal form is greater than the length of the standard answer and less than twice the length of the standard answer, the score is computed as:

Here, $FullScore$ is the full score for that test, $L_{std}$ is the length of the standard answer, and $L$ is the length of your answer.

Thanks to tiger2005 for providing the SPJ.

Translated by ChatGPT 5