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. :::definition[NAND Connective] Let $p$ and $q$ be statements. The connective 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. ::: :::theorem[NAND of a Statement with Itself] Let $p$ be a statement. Then $$\begin{equation*} p\uparrow p\Leftrightarrow\neg p. \end{equation*}$$ ::: :::proof 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$ ::: :::theorem[Basic Connectives Using NAND] Let $p$ and $q$ be statements. Then negation, conjunction, disjunction, implication, and biconditional can be represented using only NAND. ::: :::proof 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$ ::: :::definition[NOR Connective] Let $p$ and $q$ be statements. The connective 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. :::calculator[NAND and NOR Truth Checker] ::: :::theorem[NOR of a Statement with Itself] Let $p$ be a statement. Then $$\begin{equation*} p\downarrow p\Leftrightarrow\neg p. \end{equation*}$$ ::: :::proof 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$ ::: :::theorem[Basic Connectives Using NOR] Let $p$ and $q$ be statements. Then negation, conjunction, disjunction, implication, and biconditional can be represented using only NOR. ::: :::proof 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$ ::: :::theorem[Negation Relations Between NAND and NOR] 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*}$$ ::: :::proof 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$ ::: :::solved-problem Represent $\neg p$, $p\lor q$, $p\land q$, and $p\to q$ using only NAND. ::: :::solution 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*}$$ ::: :::solved-problem Represent $\neg p$, $p\lor q$, $p\land q$, and $p\to q$ using only NOR. ::: :::solution 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*}$$ ::: :::exercise 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$. ::: :::answer (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)$. ::: :::faq[Frequently Asked Questions] Q: What does NAND mean? A: NAND means not both; $p\uparrow q$ is equivalent to $\neg(p\land q)$. Q: What does NOR mean? A: NOR means neither; $p\downarrow q$ is equivalent to $\neg(p\lor q)$. Q: Why are NAND and NOR important? A: Each can represent all basic logical connectives, so each is functionally complete. ::: :::call-to-action[Consolidate Logical Equivalence] subtitle: Review equivalent forms, laws of logic, simplification, switching networks, NAND, and NOR before continuing to the next section. button: Review Section | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/equivalent-forms-of-compound-statements button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/logical-equivalence-and-the-laws-of-logic/switching-networks-and-logical-equivalence :::