Section Progress:

19.5 Nor: ↓ and Nand: |

In this section we learn two more binary connectives, called nor and nand.

Nor is symbolized with a down arrow: ↓. Its truth function is the negation of "or". So P↓Q is FFFT.

Nand is symbolized with a vertical bar: |. Its truth function is the negation of "and". P|Q is FTTT.

P↓Q means "Neither P nor Q," and P|Q means "Not P and Q".

We are not going to add these connectives to PROP. Instead, we'll see that each of these connective has an important feature on its own: each one alone is truth-functionally complete.

Before we show that, though, it should be obvious to you that the Boolean connectives can express these truth functions.

Let's practice writing complex sentences with nand.

Next, we'll practice computing truth functions with nand and nor.

If you had trouble understanding that problem, we'll walk you through it here.

After you compute the inner truth functions, your diagram should look like this:

When then use those values to compute the main connective. For example, how do we compute what goes in the red "?"? The two inputs on that row are F. So just look at the definition of nand again: when the two inputs are F (row 4), then the output is T.

In order to compute the rest of the rows, we just have to remember that when both inputs are T, then the nand output is F.

Let's practice some more.

As you can see from these examples, both nand and nor can express conjunction, and they can also express negation.

But you already know that the set { &, ~} is truth-functionally complete. What that means is that nand alone is TFC, and also that nor alone is TFC.

For example, to show that nand is TFC, all we need to do is add some steps to the TFC algorithm. We start with an arbitrary truth function, and the TFC algorithm eventually gives us a sentence that expresses it, using just conjunction and negation.

Next, we add a step that says, for every negation, such as ~P, we replace it with P|P.

Then we add a final step that says, for every conjunction, such as Q&R, we replace it with (Q|R)|(Q|R).

Let's see if you can do it.

What this all shows is that we could just get by with one truth functional connective, as long as it was nand or nor, instead of the five connectives we have in PROP.

That's an important result of metalogic. But it's not something we'd want to do.

After all, compare it to binary: we don't need all ten numerals of the base-ten system. We could just get by with 1s and 0s. But that would be a real pain.

Similarly, you saw how messy it was just to write A&~B with one connective. Imagine writing ~((~PvQ)&(Rv~T))!

Additionally, the reason why we have the five connectives that we do is so that our system will be a helpful model for analyzing reasoning that we do in our everyday lives. Much of that reasoning is with connectives like IF..., THEN and ... OR ... . That is why the proof rules for our connectives hopefully make sense and seem natural to you.

If we only had nand, by contrast, we couldn't so nicely model everyday reasoning.

Now you can see, though, that from a logical point of view it is a decision we make to include certain connectives in our system, so that it can easily model everyday reasoning.

Like we said in Chapter 1, logical systems are models we create for certain purposes. And for our purposes, BOOL and PROP are quite useful.

20.5 Nor and Nand