NAND and NOR Operations

Basic operations

The list of fundamental operations or connectives in propositional logic is summarized in the following table:

Operation	Other Names	Symbol
Conjunction	AND	$\land$
Disjunction	OR	$\lor$
Exclusive Disjunction	XOR	$\oplus$
Negation	NOT	$\neg$
Implication	Conditional	$\Rightarrow$
Bi-implication	Bi-conditional	$\Leftrightarrow$

Now, let’s look at some other logic operations.

NAND

It is a negated AND operation. Take two arbitrary propositions, $q_1$ and $q_2$. The NAND of $q_1$ and $q_2$ is false only when both $q_1$ and $q_2$ are true, otherwise it’s true. This is a commutative operation, which means:

• NAND$\left(q_1, q_2\right) \equiv$ NAND$\left(q_2, q_1\right).$

We can represent this operation using basic operations as follows:

• NAND$\left(q_1, q_2\right) \equiv \neg\left(q_1 \land q_2\right).$

Let’s look at the truth table of this operation:

$q_1$	$q_2$	NAND$\left(q_1, q_2\right)$
T	T	F
T	F	T
F	T	T
F	F	T

In general, NAND operation can be applied as follows:

• NAND$\left(q_1, q_2,\ldots ,q_n\right) \equiv \neg\left(q_1 \land q_2 \land \ldots \land q_n\right).$

NOR

It is negated OR operation. Take two arbitrary propositions, $q_1$ and $q_2$. NOR of $q_1$ and $q_2$ is true only when both $q_1$ and $q_2$ are false. Otherwise, it’s false. This is a commutative operation, which means:

• NOR$\left(q_1, q_2\right) \equiv$ NOR$\left(q_2, q_1\right).$

We can represent this operation using basic operations as follows:

• NOR$\left(q_1, q_2\right) \equiv \neg\left(q_1 \lor q_2\right).$

Let’s look at the truth table of this operation:

$q_1$	$q_2$	NOR$\left(q_1, q_2\right)$
T	T	F
T	F	F
F	T	F
F	F	T

In general, NOR operation can be applied as follows:

• NOR$\left(q_1, q_2,\ldots ,q_n\right) \equiv \neg\left(q_1 \lor q_2 \lor \ldots \lor q_n\right).$

Theorem

We know that the set $\{\land,\lor,\neg\}$ is a complete set. We now establish that $\{$NAND$\}$ is also a complete set.

Statement

The set $\{$NAND$\}$ is a complete set.

Proof

Observe that NAND can be used for negation as follows:

• NAND$\left(q_1,q_1\right)\equiv \neg q_1.$

If we want to take the conjunction of $q_1$ and $q_2$, we can do it using the NAND operation as follows:

• NAND$($NAND$(q_1,q_2),$ NAND$(q_1,q_2)) \equiv q_1\land q_2.$

Similarly, we can take the disjunction of $q_1$ and $q_2$ using the NAND operation as follows:

• NAND$($NAND$(q_1,q_1),$ NAND$(q_2,q_2)) \equiv q_1\lor q_2.$

As we saw, the NAND operation is sufficient to perform negation, conjunction, and disjunction operations, hence, it makes a complete set.

Theorem

We now establish that $\{$NOR$\}$ is also a complete set.

Statement

The set $\{$NOR$\}$ is a complete set.

Proof

Observe that NOR can be used for negation as follows:

• NOR$(q_1,q_1)\equiv \neg q_1.$

If we want to take the conjunction of $q_1$ and $q_2$, we can do it using the NOR operation as follows:

• NOR$($NOR$(q_1,q_1),$ NOR$(q_2,q_2)) \equiv q_1\land q_2.$

Similarly, we can take the disjunction of $q_1$ and $q_2$ using the NOR operation as follows:

• NOR$($NOR$(q_1,q_2),$ NOR$\left(q_1,q_2\right)) \equiv q_1\lor q_2.$

As we saw, the NOR operation is sufficient to perform negation, conjunction, and disjunction operations. Hence, it makes a complete set.