Boolean Logic

Boolean Logic

In Boolean Logic, we can only use two valuses; TRUE and FALSE. This mathematical system is the foundation of digital electronics and computer design. Often we represent TRUE by 1 and FALSE by 0, but this is just representation, technically, \(TRUE \neq 1\).

Boolean values are manipulated with the Boolean operations as follows:

• Exclusive or, XOR: \(\oplus\)
The exclusive or is 1 if either but not both of its two values is 1.
(e.g. \(1 \oplus 1 = 0, \quad 1 \oplus 0 = 1, \quad 0 \oplus 0 = 0\))
• Equality: \(\leftrightarrow\)
The equality is 1 if both of its operands have the same value.
(e.g. \(1 \leftrightarrow 1 = 1, \quad 1 \leftrightarrow 0 = 0, \quad 0 \leftrightarrow 0 = 1\))
This is equivalent to XNOR, which is the logical complement of the XOR.
• Implication: \(\rightarrow\)
The implication is 0 if its first operand is 1 and its second operand is 0. Otherwise, it's 1.
(e.g. \(1 \rightarrow 1 = 1, \quad 1 \rightarrow 0 = 0, \quad 0 \rightarrow 0 = 1\))

Negation of Conjunction & Disjunction

• NAND: \(\uparrow\)
NAND is negation of conjunction: \[ P \uparrow Q = \neg (P \wedge Q) \] So, it is TRUE unless both \(P\) and \(Q\) are TRUE. (e.g. \(1 \uparrow 0 = 1, \quad 1 \uparrow 1 = 0, \quad 0 \uparrow 0 = 1\))
• NOR: \(\downarrow\)
NOR is negation of disjunction: \[ P \downarrow Q = \neg (P \vee Q) \] So, it is TRUE if both \(P\) and \(Q\) are FALSE. (e.g. \(1 \downarrow 0 = 0, \quad 1 \downarrow 1 = 0, \quad 0 \downarrow 0 = 1\))

• Equality
\[ \begin{align*} P \leftrightarrow Q &= (P \wedge Q) \vee (\neg P \wedge \neg Q) \\\\ &= (P \uparrow Q) \uparrow ((P \uparrow Q) \uparrow (Q \uparrow Q)) \end{align*} \]
• Implication
\[ \begin{align*} P \rightarrow Q &= \neg P \vee Q \\\\ &= P \uparrow (Q \uparrow Q) \end{align*} \]

Circuits

When we study Boolean logic as a purely mathematical system, the focus is on abstract algebraic properties. However, when these Boolean functions 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.

However, circuits are not only used for physical hardware but also for theoretical models in computer science. When Boolean functions are used to construct a computational model rather than a physical device, we refer to them as Boolean circuits. These circuits serve as a fundamental concept in computational complexity theory, where they help analyze the efficiency and limitations of different computational processes. Here, we only introduce the definition of Boolean circuits. We will revisit this topic after learning complexity theory in the future.