Boolean algebra - Derived Boolean Operators

Secondary Operations Introduction In addition to the three primary logical operators (AND, OR, and NOT), we can define several other useful logical operations by combining the primary operators. These secondary operations are derived from the primary ones, but they're so commonly used that they deserve their own symbols and names. Understanding how to define and work with these operations is essential for logic, computer science, and digital design. Exclusive-Or (XOR) Exclusive-or, often written as $x \oplus y$ or "XOR," is a logical operation that outputs true when exactly one of its inputs is true, but not both. The key word here is "exclusive"—we're saying "one or the other, but not both." This is different from regular disjunction (OR), which outputs true even if both inputs are true. We can define XOR using the primary operators as: $$x \oplus y = (x \lor y) \land \lnot(x \land y)$$ What this definition says: "Either $x$ or $y$ is true (or both), AND it's not the case that both are true." The result is that exactly one must be true. Example: When deciding between two routes to work, "I'll take Route A XOR Route B" means you'll take exactly one route, not both. Logical Implication Logical implication, written as $x \rightarrow y$ (read as "$x$ implies $y$"), is a conditional statement. It expresses a relationship where if the first statement (the antecedent) is true, then the second statement (the consequent) must also be true. Here's an important insight: implication can be defined as: $$x \rightarrow y = \lnot x \lor y$$ This definition might seem odd at first, so let's think through it. The implication $x \rightarrow y$ is false only when $x$ is true but $y$ is false. In all other cases—when $x$ is false, or when both $x$ and $y$ are true—the implication is true. The definition $\lnot x \lor y$ captures exactly this: it's true whenever $x$ is false (making $\lnot x$ true) or whenever $y$ is true (or both). Example: "If it rains, then the ground is wet." This implication is false only when it rains but the ground is not wet. If it doesn't rain, the implication is true regardless of whether the ground is wet. Logical Equivalence Logical equivalence, written as $x \leftrightarrow y$ (read as "$x$ if and only if $y$"), is true when both inputs have the same truth value—either both are true or both are false. We can define logical equivalence as: $$x \leftrightarrow y = \lnot(x \oplus y)$$ Since XOR is true when exactly one input is true, the negation of XOR is true when the inputs are the same. This is exactly equivalence. Example: "I'll attend the party if and only if you attend" means either we both go or we both don't go. If one of us goes and the other doesn't, the equivalence is false. NAND (Not-And) NAND, short for "not-and," is simply the negation of conjunction: $$\text{NAND}(x, y) = \lnot(x \land y)$$ NAND outputs true except when both inputs are true. It's false only when both $x$ and $y$ are true; in all other cases it's true. Why does NAND matter? NAND is fundamentally important in digital circuits because any logical operation can be constructed using only NAND gates. This makes NAND a universal operator in digital design. NOR (Not-Or) NOR, short for "not-or," is the negation of disjunction: $$\text{NOR}(x, y) = \lnot(x \lor y)$$ NOR outputs true only when both inputs are false. It's false whenever at least one input is true. Why does NOR matter? Like NAND, NOR is a universal operator—any logical operation can be built using only NOR gates. This makes NOR another critical building block in digital systems. Summary All five secondary operations can be expressed in terms of the primary operators (AND, OR, NOT): XOR: $(x \lor y) \land \lnot(x \land y)$ — true when exactly one input is true Implication: $\lnot x \lor y$ — false only when antecedent is true and consequent is false Equivalence: $\lnot(x \oplus y)$ — true when inputs have the same truth value NAND: $\lnot(x \land y)$ — false only when both inputs are true NOR: $\lnot(x \lor y)$ — true only when both inputs are false Understanding these definitions and how they relate to the primary operators is essential for working with logic and digital systems.