Discrete! #10: Discrete Mathematics and Its Applications 1.2 Problem Set B

Interesting Problems in Section 1.2, Part B


As you might guess, there are lots of POSSIBLE logical operators in Discrete, beyond human-friendly ones like AND, OR, and XOR. As it turns out, they’re also quite useful.

First, let’s talk NAND. The statement “p NAND q” is true when one or both of its propsitions is false. Otherwise, p NAND q is false.

Let’s imagine Kelly comes up to me and says “Happy anniversary!” I then look surprised and say “OF COURSE! HAPPY ANNIVERSARY! HA! I GOT YOU… SOMETHING.”

Kelly internally thinks the following:

“p: He remembered our anniversary.

q: He got me a present.”

She then narrows her eyes in anger and thinks:

“p NAND q is true”

By that, she means that I’m either lying about the present, lying about remembering the anniversary, or lying about both.

This is the sense in which NAND is like saying not-AND. If p NAND q is true, the one thing you can be certain of is that p AND q is false.

And bonus, you get a new symbol, thereby further eroding your ability to meaningfully converse with other humans who don’t like math. The symbol for NAND is ↑, also known as the Sheffer Stroke, which is (or at least, should be) a euphemism for masturbation among computer scientists.

An easy way to remember it is that it’s just a conjunction (∧) with a line through it.

Got it?

Okay, moving on to NOR.

NOR is to OR what NAND is to AND.

p NOR q is only true when both p and q are false. That, NOR is the Satan of logical operators. Let’s do an example.

I go up to Kelly and say “It’s my birthday!” She looks awkward and says “OF COURSE IT IS. HA! UH! I GOT YOU STUFF!”

I narrow my eyes and think:

“p: She remembered.

q: She got me stuff.”

When my eyes open out again, she’s run out of the room, shouting “you’ll never catch me!”

I sigh, and think “p NOR q is true.” That is, I think that it’s definitely the case that she’s done neither p nor q. That’s what makes “NOR” easy to remember – we actually use it in normal conversation. NOR is denoted by a down arrow: ↓.

Got it?

The book actually uses | for the up arrow, but having the up and down symbols makes more sense to me, so I’m going with it.

The problem set below shows you what hopefully you’ve had an inkling of by now: p NAND q is logically equivalent to NOT-(p AND q). And, p NOR q is logically equivalent to NOT-(p OR q). This is shown when you work 46, 47, 48, and 49.

But the really cool stuff happens in 50, which I’ve roughly worked out here:

I didn’t work out everything for chunk C because I think it was intuitive where I left it. You should be able to see how the ability to alter the NOT-ness of p and q at the outset allows me to arrive at a simple p AND q at the end, proving that you can get AND, OR, and NOT from just using NOR.

Also, step C is actually a bit simpler if you refer back to 44 and 45 where we proved that ¬ plus AND or OR gives you a functionally complete set.

Note that you can construct any proposition using NOR simply by making big ugly chains of logic. In fact, knowing that it’d be ugly, I condensed a chunk into a symbol, which I normally don’t like to do.

The rest of the problems about NAND and NOR became fairly easy little games once you understand 50.


This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

3 Responses to Discrete! #10: Discrete Mathematics and Its Applications 1.2 Problem Set B

  1. Alexander says:

    You made a typo in:

    “And, p NOR q is logically equivalent to NOT-(p NOR q).”

    That should be “NOT-(p OR q)”, instead.

  2. Olin says:

    Just in case you’re interested, the NOR operator is commonly called a ‘dagger’, or ‘Quine’s dagger’. This way there’s a nice symmetry between the stroke and the dagger.

    I teach intro logic, and getting my students to express our standard logical operators in terms of daggers or strokes is a fun exercise.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>