NAND and NOR Connectives

Switching networks show how logical connectives can model physical circuits. NAND and NOR connectives take this idea further because each of them can express all the usual logical connectives. This property is important in logic design and digital circuits. In this lesson, NAND and NOR connectives will be defined, related to negation, and used to represent the basic logical connectives.

Let

p

and

q

be statements. The connective \textbf{NAND}, denoted by

\uparrow

, is defined by

\begin{equation*} p\uparrow q\Leftrightarrow\neg(p\land q). \end{equation*}

Thus,

p\uparrow q

means that

p

and

q

are not both true.

Let

p

and

q

be statements. The connective \textbf{NAND}, denoted by

\uparrow

, is defined by

\begin{equation*} p\uparrow q\Leftrightarrow\neg(p\land q). \end{equation*}

Thus,

p\uparrow q

means that

p

and

q

are not both true.

Let

p

be a statement. Then

\begin{equation*} p\uparrow p\Leftrightarrow\neg p. \end{equation*}

Given that

p\uparrow p\Leftrightarrow\neg(p\land p)

. To prove that

p\uparrow p\Leftrightarrow\neg p

. Using the idempotent law,

p\land p\Leftrightarrow p

. Therefore,

\neg(p\land p)\Leftrightarrow\neg p

. Hence,

p\uparrow p\Leftrightarrow\neg p

\square

Let

p

and

q

be statements. Then negation, conjunction, disjunction, implication, and biconditional can be represented using only NAND.

Given that

p\uparrow q\Leftrightarrow\neg(p\land q)

. To prove that the basic connectives can be represented using only NAND. First,

\neg p\Leftrightarrow p\uparrow p

. Next,

\begin{align*} p\land q&\Leftrightarrow\neg(p\uparrow q)\\ &\Leftrightarrow(p\uparrow q)\uparrow(p\uparrow q). \end{align*}

For disjunction,

\begin{equation*} p\lor q\Leftrightarrow(p\uparrow p)\uparrow(q\uparrow q). \end{equation*}

For implication,

\begin{equation*} p\to q\Leftrightarrow p\uparrow(q\uparrow q). \end{equation*}

Since

p\leftrightarrow q\Leftrightarrow(p\to q)\land(q\to p)

, the biconditional can also be written using only NAND by substitution. Hence, NAND is functionally complete.

\square

Let

p

and

q

be statements. The connective \textbf{NOR}, denoted by

\downarrow

, is defined by

\begin{equation*} p\downarrow q\Leftrightarrow\neg(p\lor q). \end{equation*}

Thus,

p\downarrow q

means that neither

p

nor

q

is true.

Use the checker to compare NAND and NOR against the basic connectives they negate. NAND means not both, so it is the negation of conjunction. NOR means neither, so it is the negation of disjunction. Testing the same values of

p

and

q

makes the two special connectives easier to remember.

Let

p

be a statement. Then

\begin{equation*} p\downarrow p\Leftrightarrow\neg p. \end{equation*}

Given that

p\downarrow p\Leftrightarrow\neg(p\lor p)

. To prove that

p\downarrow p\Leftrightarrow\neg p

. Using the idempotent law,

p\lor p\Leftrightarrow p

. Therefore,

\neg(p\lor p)\Leftrightarrow\neg p

. Hence,

p\downarrow p\Leftrightarrow\neg p

\square

Let

p

and

q

be statements. Then negation, conjunction, disjunction, implication, and biconditional can be represented using only NOR.

Given that

p\downarrow q\Leftrightarrow\neg(p\lor q)

. To prove that the basic connectives can be represented using only NOR. First,

\neg p\Leftrightarrow p\downarrow p

. Next,

\begin{align*} p\lor q&\Leftrightarrow\neg(p\downarrow q)\\ &\Leftrightarrow(p\downarrow q)\downarrow(p\downarrow q). \end{align*}

For conjunction,

\begin{equation*} p\land q\Leftrightarrow(p\downarrow p)\downarrow(q\downarrow q). \end{equation*}

For implication,

\begin{equation*} p\to q\Leftrightarrow[(p\downarrow p)\downarrow q]\downarrow[(p\downarrow p)\downarrow q]. \end{equation*}

Since

p\leftrightarrow q\Leftrightarrow(p\to q)\land(q\to p)

, the biconditional can also be represented using only NOR by substitution. Hence, NOR is functionally complete.

\square

Let

p

and

q

be statements. Then

\begin{equation*} \neg(p\downarrow q)\Leftrightarrow(\neg p\uparrow\neg q) \end{equation*}

and

\begin{equation*} \neg(p\uparrow q)\Leftrightarrow(\neg p\downarrow\neg q). \end{equation*}

Given that

p

and

q

are statements. For the first equivalence,

\begin{align*} \neg(p\downarrow q)&\Leftrightarrow\neg\neg(p\lor q)\\ &\Leftrightarrow p\lor q. \end{align*}

Also,

\begin{align*} \neg p\uparrow\neg q&\Leftrightarrow\neg(\neg p\land\neg q)\\ &\Leftrightarrow p\lor q. \end{align*}

Therefore,

\neg(p\downarrow q)\Leftrightarrow(\neg p\uparrow\neg q)

. For the second equivalence,

\begin{align*} \neg(p\uparrow q)&\Leftrightarrow p\land q,\\ \neg p\downarrow\neg q&\Leftrightarrow\neg(\neg p\lor\neg q)\Leftrightarrow p\land q. \end{align*}

Hence,

\neg(p\uparrow q)\Leftrightarrow(\neg p\downarrow\neg q)

\square

Represent

\neg p

p\lor q

p\land q

, and

p\to q

using only NAND.

Using

p\uparrow q\Leftrightarrow\neg(p\land q)

\begin{align*} \neg p&\Leftrightarrow p\uparrow p,\\ p\land q&\Leftrightarrow(p\uparrow q)\uparrow(p\uparrow q),\\ p\lor q&\Leftrightarrow(p\uparrow p)\uparrow(q\uparrow q),\\ p\to q&\Leftrightarrow p\uparrow(q\uparrow q). \end{align*}

Represent

\neg p

p\lor q

p\land q

, and

p\to q

using only NOR.

Using

p\downarrow q\Leftrightarrow\neg(p\lor q)

\begin{align*} \neg p&\Leftrightarrow p\downarrow p,\\ p\lor q&\Leftrightarrow(p\downarrow q)\downarrow(p\downarrow q),\\ p\land q&\Leftrightarrow(p\downarrow p)\downarrow(q\downarrow q),\\ p\to q&\Leftrightarrow[(p\downarrow p)\downarrow q]\downarrow[(p\downarrow p)\downarrow q]. \end{align*}

Using only NAND, express: (1)

\neg p

. (2)

p\land q

. (3)

p\lor q

. Using only NOR, express: (4)

\neg p

. (5)

p\lor q

. (6)

p\land q

(1)

p\uparrow p

. (2)

(p\uparrow q)\uparrow(p\uparrow q)

. (3)

(p\uparrow p)\uparrow(q\uparrow q)

. (4)

p\downarrow p

. (5)

(p\downarrow q)\downarrow(p\downarrow q)

. (6)

(p\downarrow p)\downarrow(q\downarrow q)

NAND means not both;

p\uparrow q

is equivalent to

\neg(p\land q)

NOR means neither;

p\downarrow q

is equivalent to

\neg(p\lor q)

Each can represent all basic logical connectives, so each is functionally complete.

BMLabs Mathematics

BMLabs Mathematics

NAND and NOR Connectives

NAND and NOR Connectives

NAND CONNECTIVE

NAND OF A STATEMENT WITH ITSELF

BASIC CONNECTIVES USING NAND

NOR CONNECTIVE

COMPARING NAND AND NOR OUTPUTS

NAND AND NOR TRUTH CHECKER

NOR OF A STATEMENT WITH ITSELF

BASIC CONNECTIVES USING NOR

NEGATION RELATIONS BETWEEN NAND AND NOR

FREQUENTLY ASKED QUESTIONS

CONSOLIDATE LOGICAL EQUIVALENCE

Introduction To Discrete Mathematics

Paths and Circuits