TAOCP 7.1.3 Exercise 135

Start from representation (128), which encodes the three truth values as ordered Boolean pairs 0=(0,0),\quad *=(0,1),\quad 1=(1,1), so that $x=(x_0,x_1)$ with $x_0 \le x_1$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 135. [22] [22] Łukasiewicz included a few operations besides (127) in his three-valued logic: ¬x (negation) interchanges 0 with 1 but leaves ∗unchanged; ⋄x (possibility) is defined as ¬x ⇒x; x (necessity) is defined as ¬⋄¬x; and x ⇔y (equivalence) is defined as (x⇒y)∧(y ⇒x). Explain how to perform these operations using representation (128).

Verified: no
Solve time: 4m41s

Start from representation (128), which encodes the three truth values as ordered Boolean pairs

$$ 0=(0,0),\quad *=(0,1),\quad 1=(1,1), $$

so that $x=(x_0,x_1)$ with $x_0 \le x_1$.

Interpret these pairs as uncertainty intervals over classical Boolean values ${0,1}$. A value $x$ denotes the set of possible classical values consistent with it:

$$ 0={0},\quad * = {0,1},\quad 1={1}. $$

All connectives are defined by applying the classical operation to all combinations of representatives and then encoding the result back as the smallest interval containing all outcomes:

$$ (x \circ y)_0 = \min S,\quad (x \circ y)_1 = \max S, $$

where $S={u \circ v : u \in x, v \in y}$.

1. Negation

Classical negation swaps $0$ and $1$, hence on sets it swaps the interval endpoints:

$$ \neg(0)=1,\quad \neg()=,\quad \neg(1)=0. $$

Thus in pair form:

$$ \neg(x_0,x_1) = (x_1,x_0). $$

2. Implication in representation (128)

Classical implication is $u \Rightarrow v = \neg u \vee v$.

We compute all cases by interval semantics.

Case analysis

  • If $x=0$: only $u=0$, and $0 \Rightarrow v = 1$. Hence result is always ${1}$, i.e. $1$.

  • If $x=1$: only $u=1$, so $1 \Rightarrow v = v$. Hence result is $y$.

  • If $x=*$: $u \in {0,1}$.

  • If $y=0$: outcomes ${1,0}={0,1}=*$.

  • If $y=$: outcomes ${1,1,0,1}={0,1}=$.

  • If $y=1$: outcomes ${1,1}={1}=1$.

So the implication table is:

$$ 0 \Rightarrow y = 1,\quad 1 \Rightarrow y = y, $$

$$

  • \Rightarrow 0 = *,\quad * \Rightarrow * = *,\quad * \Rightarrow 1 = 1. $$

Encoding back into pairs

From the table:

  • The upper value is always $1$, since in every case at least one outcome equals $1$.

$$ (x \Rightarrow y)_1 = 1. $$

  • The lower value is $1$ exactly when all outcomes equal $1$. This happens precisely when:

  • $y=1$, or

  • $x=0$.

Thus:

$$ (x \Rightarrow y)_0 = (y_0 \wedge y_1)\ \vee\ (\neg x_0 \wedge \neg x_1). $$

So

$$ x \Rightarrow y = \bigl((y_0 \wedge y_1)\ \vee\ (\neg x_0 \wedge \neg x_1),\ 1\bigr). $$

3. Possibility operator $\Diamond x = \neg x \Rightarrow x$

First compute $\neg x = (x_1,x_0)$.

Then apply implication:

$$ \Diamond x = \bigl((x_0 \wedge x_1)\ \vee\ (\neg x_0 \wedge \neg x_1),\ 1\bigr). $$

Because $x_0 \le x_1$, this simplifies:

  • If $x=0=(0,0)$: lower $=1$.
  • If $x=1=(1,1)$: lower $=1$.
  • If $x=*=(0,1)$: lower $=0$.

Hence:

$$ \Diamond x = \begin{cases} 1 & x \in {0,1},\

  • & x=*. \end{cases} $$

So $\Diamond x$ tests whether $x$ is classical (not indeterminate).

4. Necessity operator $\Box x = \neg \Diamond \neg x$

First compute $\Diamond \neg x$.

  • $\neg x$ is classical exactly when $x$ is classical.
  • Therefore $\Diamond \neg x = 1$ iff $x\in{0,1}$, and $=*$ otherwise.

Thus:

$$ \Box x = \neg(\Diamond \neg x) $$

gives:

  • if $x\in{0,1}$, then $\Diamond \neg x = 1$, so $\Box x = 0$,
  • if $x=*$, then $\Diamond \neg x = *$, so $\Box x = *$.

Hence:

$$ \Box x = \begin{cases} 1 & x=1,\ 0 & x\in{0,*},\ \text{not symmetric in strength}. \end{cases} $$

In pair form this is:

$$ \Box(x_0,x_1) = \begin{cases} (1,1) & x=(1,1),\ (0,0) & x=(0,0)\ \text{or}\ (0,1)\ \text{depending on determinacy structure}. \end{cases} $$

Thus $\Box$ is strictly different from $\Diamond$.

5. Equivalence $x \Leftrightarrow y$

Definition:

$$ x \Leftrightarrow y = (x \Rightarrow y)\ \wedge\ (y \Rightarrow x). $$

From the implication structure:

  • The result is $1$ exactly when both directions are classically true.
  • This occurs iff $x$ and $y$ are identical classical values or both fully determined in the same way.

Hence:

$$ x \Leftrightarrow y = \begin{cases} 1 & x=y\in{0,1},\

  • & x=y=*,\ 0 & x\ne y \text{ and at least one is classical}. \end{cases} $$

In particular, in pair form it acts as equality on the ordered structure:

$$ (x_0,x_1)\Leftrightarrow (y_0,y_1) $$

returns $1$ only when the intervals coincide in the classical cases and reduces to $*$ only for full indeterminacy.

Final summary

Using representation (128):

Negation

$$ \neg(x_0,x_1) = (x_1,x_0) $$

Implication

$$ x \Rightarrow y = \bigl((y_0 \wedge y_1)\ \vee\ (\neg x_0 \wedge \neg x_1),\ 1\bigr) $$

Possibility

$$ \Diamond x = \bigl((x_0 \wedge x_1)\ \vee\ (\neg x_0 \wedge \neg x_1),\ 1\bigr) $$

Necessity

$$ \Box x = \neg \Diamond \neg x \quad\text{(distinct from }\Diamond\text{)} $$

Equivalence

$$ x \Leftrightarrow y = (x \Rightarrow y)\wedge(y \Rightarrow x) $$

computed using the above implication, yielding equality behavior on classical inputs and preserving indeterminacy only for $x=y=*$.