TAOCP 7.1.1 Exercise 2
Let $P$ denote the Pincus interpretation and $E$ the ordinary Earth interpretation.
Exercise 2. [17] $[17]$ Logicians on the remote planet Pincus use the symbol 1 to represent "false" and 0 to represent "true." Thus, for example, they have a binary operation called "or" whose properties
$$1 \mathbin{\mathrm{or}} 1 = 1, \qquad 1 \mathbin{\mathrm{or}} 0 = 0, \qquad 0 \mathbin{\mathrm{or}} 1 = 0, \qquad 0 \mathbin{\mathrm{or}} 0 = 0$$
we associate with $\wedge$. What operations would be used by the 16 logical operators that Pincusians respectively call "falsehood," "and," …, "nand," "validity" (see Table 1)?
Verified: yes
Solve time: 2m04s
Solution
Let $P$ denote the Pincus interpretation and $E$ the ordinary Earth interpretation. Since Pincusians reverse the meanings of $0$ and $1$, the correspondence between truth values is
$$ 0_P = 1_E,\qquad 1_P = 0_E. $$
Suppose a Pincus operation has truth table
$$ a,b,c,d $$
in Pincus notation. Translating to Earth notation requires two changes:
- Each input value is complemented, because $0_P$ means $1_E$ and $1_P$ means $0_E$.
- Each output value is complemented for the same reason.
Hence the Earth operation corresponding to a Pincus operation $f$ is
$$ g(x,y)=\overline{f(\bar x,\bar y)}. $$
Applying this transformation to the sixteen operations of Table 1 gives the following correspondences.
The Pincus operation called falsehood has truth table $0000$ in Pincus notation. After complementation of inputs and output its Earth truth table is $1111$, hence it is $\top$.
The Pincus operation called and has truth table $0001$. The transformed truth table is $0111$, hence it is $\vee$.
The Pincus operation called nonimplication has truth table $0010$. The transformed truth table is $1011$, hence it is $x\vee\bar y$ (converse implication).
The Pincus operation called left projection remains left projection, because $0011$ transforms to $0011$.
The Pincus operation called converse nonimplication has truth table $0100$. The transformed truth table is $1101$, hence it is $\bar x\vee y$ (implication).
The Pincus operation called right projection remains right projection, because $0101$ transforms to $0101$.
The Pincus operation called exclusive disjunction has truth table $0110$. The transformed truth table is again $0110$, hence it remains $\oplus$.
The Pincus operation called or has truth table $0111$. The transformed truth table is $0001$, hence it is $\wedge$, exactly as stated in the problem.
The Pincus operation called nondisjunction has truth table $1000$. The transformed truth table is $1110$, hence it is $\bar\wedge$.
The Pincus operation called equivalence has truth table $1001$. The transformed truth table is again $1001$, hence it remains $\equiv$.
The Pincus operation called right complementation has truth table $1010$. The transformed truth table is $1010$, hence it remains $\bar y$.
The Pincus operation called converse implication has truth table $1011$. The transformed truth table is $0010$, hence it is $x\bar y$ (nonimplication).
The Pincus operation called left complementation has truth table $1100$. The transformed truth table is $1100$, hence it remains $\bar x$.
The Pincus operation called implication has truth table $1101$. The transformed truth table is $0100$, hence it is $\bar x y$ (converse nonimplication).
The Pincus operation called nand has truth table $1110$. The transformed truth table is $1000$, hence it is $\bar\vee$.
The Pincus operation called validity has truth table $1111$. The transformed truth table is $0000$, hence it is $\bot$.
Therefore the correspondence is
$$ \begin{array}{c|c} \text{Pincus name} & \text{Earth operation}\ \hline \text{falsehood} & \top\ \text{and} & \vee\ \text{nonimplication} & x\vee\bar y\ \text{left projection} & x\ \text{converse nonimplication} & \bar x\vee y\ \text{right projection} & y\ \text{exclusive disjunction} & \oplus\ \text{or} & \wedge\ \text{nondisjunction} & \bar\wedge\ \text{equivalence} & \equiv\ \text{right complementation} & \bar y\ \text{converse implication} & x\bar y\ \text{left complementation} & \bar x\ \text{implication} & \bar x y\ \text{nand} & \bar\vee\ \text{validity} & \bot \end{array} $$
Thus the required list is
$$ \boxed{ \top,\ \vee,\ x\vee\bar y,\ x,\ \bar x\vee y,\ y,\ \oplus,\ \wedge,\ \bar\wedge,\ \equiv,\ \bar y,\ x\bar y,\ \bar x,\ \bar x y,\ \bar\vee,\ \bot }. $$