[Math] Give the truth table of a single binary connective which is adequate.

logicnotation

This might be a silly question, but I am confused.
I know there is a theorem saying the only single binary connectives which are adequate are NOR or NAND, so I could use either of them.
And then the truth table for NOR would be;

$$\begin{array}{cc|c}
P & Q & P\bar\lor Q \\ \hline
T & T & F \\
T & F & F \\
F & T & F \\
F & F & T
\end{array}$$

P={T,T,F,F} Q={T,F,T,F} and PNORQ={F,F,T,F}

but isn't NOR denoted by "not or" ¬V which is 2 connectives so it isn't a "single binary connective" or is that the whole point, that "NOR" can be written as those 2 connectives so it is adequate?

Thanks, I hope it kind of makes sense.

Best Answer

isn't NOR denoted by "not or" ¬V which is 2 connectives ....

No. It is a single connective defined directly by its truth-table.

What you then need to show, to prove expressive adequacy, is that e.g. "Not" and "Or" can be defined in terms of "NOR" (because we know that they suffice to express any truth-function).

Hint to get you going ... what is $P$ NOR $P$?

Related Question