Proving ◦ is either nand or nor if ◦ is a binary operator that can define negation and all other binary operators by itself.

291 Views Asked by At

I have a outline of the proof in my book but I am not able to understand the second part of it.

Suppose that $\circ$ is a binary operator that can define all the other operators. Negation must be defined by an equivalence of the form: $¬A \equiv A \circ \dots \circ A$ ($n$ times $A$; if $\circ$ is not associative, add parentheses as necessary).

Any binary operator $\text{op}$ must be defined by an equivalence: $A_1 \text{ op } A_2 \equiv B_1 \circ \dots \circ B_n$, where each $B_i$ is either $A_1$ or $A_2$. (If $\circ$ is not associative, add parentheses as necessary.) We will show that these requirements impose restrictions on $\circ$ so that it must be nand or nor.

Now I am able to show by induction that when $v(A_1)= T$ and $v(A_2)=T$ it implies $v(A_1 \circ A_2)=F$ and when $v(A_1)=F$ and $v(A_2)=F$ it implies $v(A_1 \circ A_2)=T$. How do I prove the remaining two valuations of must be both $T$ or both $F$?

1

There are 1 best solutions below

0
On

If the two remaining valuation of $v(A_1 \circ A_2)=F$ are not the same, then $\circ$ will be a unary operation (it will ignore $A_1$ or $A_2$).

If $v(T \circ F)=F$ and $v(F \circ T)=T$, then $v(A_1 \circ A_2)=v(\lnot A_1)$

If $v(T \circ F)=T$ and $v(F \circ T)=F$, then $v(A_1 \circ A_2)=v(\lnot A_2)$

Since these are both unary operations, they cannot define other binary operaters.