TAOCP 7.1.1 Exercise 3
Let $x,y \in {-1,+1}$, with $-1$ representing falsehood and $+1$ representing truth.
Exercise 3. ▶ [19] [19] Suppose logical values were respectively $-1$ for falsehood and $+1$ for truth, instead of 0 and 1. What operations $\circ$ in Table 1 would then correspond to (a) $\max(x, y)$? (b) $\min(x, y)$? (c) $-x$? (d) $x \cdot y$?
Verified: yes
Solve time: 2m16s
Solution
Let $x,y \in {-1,+1}$, with $-1$ representing falsehood and $+1$ representing truth. The ordering $-1 < +1$ is used for $\min$ and $\max$.
Define the bijection $\phi:{0,1}\to{-1,+1}$ by $\phi(0)=-1$ and $\phi(1)=+1$. Each Boolean operation from Table 1 is transported through $\phi$ by applying it componentwise and converting outputs back in ${-1,+1}$.
(a) $\max(x,y)$
The function $\max(x,y)$ satisfies $\max(x,y)=+1$ if at least one of $x,y$ equals $+1$, and $\max(x,y)=-1$ only when $x=y=-1$. This truth condition matches the Boolean disjunction $x \vee y$, whose truth table in ${0,1}$ has value $1$ exactly when at least one input is $1$.
Under $\phi$, disjunction $x \vee y$ corresponds to the operation $\vee$ in Table 1, hence
$$ \max(x,y) ;\longleftrightarrow; x \vee y. $$
(b) $\min(x,y)$
The function $\min(x,y)$ satisfies $\min(x,y)=+1$ only when $x=y=+1$, and $\min(x,y)=-1$ otherwise. This is exactly the condition for Boolean conjunction $x \wedge y$, whose truth table has value $1$ only when both inputs are $1$.
Therefore,
$$ \min(x,y) ;\longleftrightarrow; x \wedge y. $$
(c) $-x$
The unary operation $x \mapsto -x$ interchanges $+1$ and $-1$. Under $\phi^{-1}$ this corresponds to exchanging $1$ and $0$, which is Boolean negation. In Table 1 this is the complement operation, written $\bar{x}$ or equivalently $\neg x$, corresponding to the functions labeled $\mathsf{L}$ or $\mathsf{R}$ depending on notation context.
Hence
$$ -x ;\longleftrightarrow; \bar{x}. $$
(d) $x \cdot y$
For $x,y \in {-1,+1}$, the product satisfies
$$ x \cdot y = \begin{cases} +1 & x=y,\ -1 & x \ne y. \end{cases} $$
Thus $x \cdot y$ takes value $+1$ exactly when $x$ and $y$ agree and $-1$ otherwise. Under $\phi^{-1}$ this corresponds to Boolean equivalence $x \equiv y$, whose truth table has value $1$ exactly when the inputs are equal.
Therefore
$$ x \cdot y ;\longleftrightarrow; x \equiv y. $$
This completes the proof. ∎