Boolean Logic

Knowledge Map Atlas
Boolean Logic Negation of Conjunction & Disjunction Circuits

Boolean Logic

In Boolean logic, we work with two values: TRUE and FALSE, customarily encoded as \(1\) and \(0\). Throughout this page we identify the Boolean values with the elements of \(\{0, 1\}\). This mathematical system is the foundation of digital electronics and computer design.

Boolean values are combined using the following fundamental operations:

Definition: Fundamental Boolean Operations
  • Negation (NOT): \(\neg\)
    The negation of a Boolean value is its opposite: \(\neg 1 = 0\) and \(\neg 0 = 1\).
  • Conjunction (AND): \(\wedge\)
    The conjunction of two Boolean values is 1 if both operands are 1: \(1 \wedge 0 = 0\), \(1 \wedge 1 = 1\), \(0 \wedge 0 = 0\).
  • Disjunction (OR): \(\vee\)
    The disjunction of two Boolean values is 1 if at least one operand is 1: \(1 \vee 0 = 1\), \(1 \vee 1 = 1\), \(0 \vee 0 = 0\).

We will also use three further Boolean operations:

All of these operations are special cases of a more general object: any function from finitely many Boolean inputs to a single Boolean output.

Definition: Boolean Function

A Boolean function of \(n\) variables (\(n \geq 1\)) is a function \[ f: \{0, 1\}^n \to \{0, 1\}. \] Equivalently, \(f\) is specified by a truth table: a list of the value \(f(a_1, \ldots, a_n) \in \{0, 1\}\) for each of the \(2^n\) input assignments \((a_1, \ldots, a_n) \in \{0, 1\}^n\).

Negation of Conjunction & Disjunction

Definition: NAND and NOR
  • NAND: \(\uparrow\)
    NAND is the negation of conjunction: \[ P \uparrow Q = \neg(P \wedge Q). \] It is TRUE unless both \(P\) and \(Q\) are TRUE: \(1 \uparrow 1 = 0\), \(1 \uparrow 0 = 1\), \(0 \uparrow 1 = 1\), \(0 \uparrow 0 = 1\).
  • NOR: \(\downarrow\)
    NOR is the negation of disjunction: \[ P \downarrow Q = \neg(P \vee Q). \] It is TRUE only when both \(P\) and \(Q\) are FALSE: \(1 \downarrow 1 = 0\), \(1 \downarrow 0 = 0\), \(0 \downarrow 1 = 0\), \(0 \downarrow 0 = 1\).
Definition: Functional Completeness

A set of Boolean operations is functionally complete if every Boolean function can be expressed using only operations from that set.

Theorem: Functional Completeness of \(\{\neg, \wedge, \vee\}\)

The set \(\{\neg, \wedge, \vee\}\) is functionally complete. That is, every Boolean function can be expressed as a formula in the variables using only negation, conjunction, and disjunction.

Proof.

Let \(f: \{0, 1\}^n \to \{0, 1\}\). If \(f\) is identically \(0\), then \(f(x_1, \ldots, x_n) = x_1 \wedge \neg x_1\) suffices. Otherwise, let \(S = \{(a_1, \ldots, a_n) \in \{0, 1\}^n \mid f(a_1, \ldots, a_n) = 1\}\). For each input \(\mathbf{a} = (a_1, \ldots, a_n) \in S\), define the minterm \[ m_{\mathbf{a}}(x_1, \ldots, x_n) = \ell_1 \wedge \ell_2 \wedge \cdots \wedge \ell_n, \quad \text{where } \ell_i = \begin{cases} x_i & \text{if } a_i = 1, \\ \neg x_i & \text{if } a_i = 0. \end{cases} \]

By construction, for \(\mathbf{x} = (x_1, \ldots, x_n) \in \{0, 1\}^n\) we have \(m_{\mathbf{a}}(\mathbf{x}) = 1\) if and only if \(\mathbf{x} = \mathbf{a}\). The disjunctive normal form of \(f\) is then \[ f(x_1, \ldots, x_n) = \bigvee_{\mathbf{a} \in S} m_{\mathbf{a}}(x_1, \ldots, x_n), \] which evaluates to \(1\) at exactly the inputs in \(S\), matching \(f\).

In fact, a single operation already suffices, so every Boolean function can be computed with one type of gate. Hardware design exploits this fact, and NAND gates are a standard building block of digital hardware.

Theorem: Functional Completeness of NAND and NOR

Each of the singleton sets \(\{\uparrow\}\) and \(\{\downarrow\}\) is functionally complete. In other words, every Boolean function can be expressed using only NAND gates, and likewise using only NOR gates.

Proof.

By the functional completeness of \(\{\neg, \wedge, \vee\}\), it suffices to express \(\neg\), \(\wedge\), and \(\vee\) using NAND alone:

  • NOT: \(\quad \neg P = P \uparrow P\)
  • AND: \(\quad P \wedge Q = (P \uparrow Q) \uparrow (P \uparrow Q)\)
  • OR: \(\quad P \vee Q = (P \uparrow P) \uparrow (Q \uparrow Q)\)

Each identity is verified by direct truth-table evaluation. Since AND, OR, and NOT together express any Boolean function, and all three can be built from NAND alone, NAND is functionally complete.

The analogous constructions using NOR are:

  • NOT: \(\quad \neg P = P \downarrow P\)
  • OR: \(\quad P \vee Q = (P \downarrow Q) \downarrow (P \downarrow Q)\)
  • AND: \(\quad P \wedge Q = (P \downarrow P) \downarrow (Q \downarrow Q)\)

By the same argument, NOR is functionally complete.

In particular, implication, XOR, and equality can each be written with NAND alone:

Circuits

When we study Boolean logic as a purely mathematical system, the focus is on abstract algebraic properties. However, when the basic Boolean operations are implemented in hardware, they are called logic gates. Computers are built using electronic components wired together in a design known as a digital circuit. Logic gates are physically implemented using transistors, and each Boolean operation corresponds to a type of gate that controls the flow of electrical signals.

Circuits are used not only for physical hardware but also as theoretical models in computer science. When gates are wired together as a computational model rather than a physical device, we call the result a Boolean circuit. These circuits are a fundamental model in computational complexity theory, where they help analyze the efficiency and limitations of different computational processes. Here we introduce the basic definition. The study of circuit complexity, which classifies problems by asymptotic bounds on circuit size and depth, lies beyond the scope of this page.

Definition: Boolean Circuit

Fix a functionally complete set of Boolean operations as the available gate types (typical choices are \(\{\wedge, \vee, \neg\}\) or \(\{\uparrow\}\)). A Boolean circuit over this gate set is a directed acyclic graph (DAG), with parallel edges allowed, in which each node belongs to one of three categories:

  • Input nodes (sources, in-degree \(0\)): each labeled with a Boolean variable.
  • Gate nodes (internal): each labeled with one of the available gate types of arity \(k \geq 1\), with in-degree exactly \(k\), and computing that operation applied to its \(k\) input wires, taken in a fixed order (several of these wires may come from the same node).
  • Output nodes (sinks, out-degree \(0\)): each of in-degree \(1\), producing as a final Boolean result the value computed at its unique predecessor.

The size of a circuit is its total number of gate nodes, and its depth is the largest number of gate nodes on a directed path from an input node to an output node.

Example: Circuit for XOR

The expression \(P \oplus Q = (P \wedge \neg Q) \vee (\neg P \wedge Q)\) is realized by the following Boolean circuit using the standard gate set \(\{\neg, \wedge, \vee\}\):

Boolean circuit computing XOR with NOT, AND, and OR gates

This circuit consists of:

  • 2 input nodes: \(P\) and \(Q\).
  • 5 gate nodes: 2 NOT gates, 2 AND gates, and 1 OR gate. Thus, the size is 5.
  • 1 output node: the final result \(P \oplus Q\).

The depth of this circuit is 3. For instance, the path \(P \to \text{NOT} \to \text{AND} \to \text{OR}\) to the output node passes through three gates, and no path passes through more.

The DAG structure ensures that computation proceeds in a well-defined order from inputs to output, with no feedback loops.

The operations introduced here appear throughout the curriculum. In the finite fields whose size is a power of \(2\), addition is bitwise XOR once field elements are written as bit vectors. These fields appear both in abstract algebra and in cryptography. Boolean circuits provide a computational model complementary to the Turing machine.