Propositional logic · Definition

NAND

logicpropositional

Before you start you need to know

NAND combines conjunction and negation in a single operation, and by itself is enough to build any other logical connective.

Definition

Given propositions \(P\) and \(Q\), the NAND operation is the negation of their conjunction.

\[P\mathbin{\uparrow}Q=\neg(P\land Q)\]

NAND is false only when \(P\) and \(Q\) are both true, because only then is \(P\land Q\) true and its negation false. So its truth table has three true rows and one false row.

Guiding example: with \(P\) true and \(Q\) false, \(P\land Q\) is false and \(\neg(P\land Q)\) is true. With \(P\) and \(Q\) both true, however, NAND is false.

Common mistake: confusing it with \(\neg P\land\neg Q\), which with \(P\) true and \(Q\) false is false, while NAND is true. Remember that the negation applies to the whole conjunction.

Think about it

In which case does NAND produce false?

When both inputs are true.

Exercises 10

  1. NAND is the negation of...
  2. P NAND Q is false when...
  3. Which formula represents NAND?
  4. An important property of NAND is that...
  5. P NAND P is equivalent to...
  6. P NAND Q is usually written...
  7. NAND is false when...
  8. What function does NAND perform with a single input P?
  9. Select the values for which P NAND Q is false.
  10. NAND is functionally complete because it can build...

References

  • Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.