# Give the truth table of a single binary connective which is adequate.

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.

• You have the nor table wrong. It only has F in the final row where P,Q are F. And nor is defined by "not or" rather than "not implies". Commented Feb 19, 2014 at 14:34
• yes, I completely meant "not or", but I have only seen NOR as T in the final row and F in the others rather than the way you describe it Commented Feb 19, 2014 at 14:37
• ZZS14 You're right I got things backward. Commented Feb 19, 2014 at 14:44
• $P nor Q$ is equal to $\lnot (P \lor Q)$ . $(P \lnot \lor Q)$ is not even well formed Commented Feb 20, 2014 at 0:27

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$?

A single binary connective may also happen to be equivalent to another expression involving more than one binary/unary connective. For example $p \to q$ is equivalent to $\lnot p \lor q$, but we still say that $\to$ is a "single" binary connective when we use it as $p \to q.$

The same goes for nand and nor. "p nand q" is equivalent to $\lnot(p \land q)$, yet is still a "single" connective, in this case sometimes written as $p | q.$

There's also a commonly used symbol for "p nor q" which I forgot at the moment.

• okay, thanks that is what I thought so I can just use the truth table of nor for the example. Commented Feb 19, 2014 at 14:44

Your truth table is correct. Yes, NOR can be expressed using our usual connectives as NOT OR, but it can also be the first connective you define. You define it by the truth table you have above and it is a single connective. Now you need to show that you can define all the other connectives in terms of NOR. So can you find a way to express $\lnot P$ using only $\overline \vee$ and either $P \vee Q$ or $P \wedge Q$?