Question

Show that \(\mid\) and \(\downarrow\) are the only binary connectives \(\$$ such that \)\\{\$\\}$ is functionally complete.

Short answer

NAND and NOR are the only functionally complete binary connectives.

Step-by-step solution

Understand Terms and Definitions

A binary connective is an operation that combines exactly two logic values (true or false). A set of connectives is functionally complete if every possible truth function can be expressed using only those connectives.

Review Existing Functionally Complete Connectives

Known functionally complete connectives include AND, OR, and NOT. Additionally, NAND (\( \mid \)) and NOR (\( \downarrow \)) by themselves are functionally complete. Our task is to show that no other single binary connective is functionally complete.

Recognize Properties of NAND and NOR

NAND (\( \mid \)) and NOR (\( \downarrow \)) are indeed functionally complete because they can be used to construct all the other standard logical connectives such as NOT, AND, and OR, from which any logic function can be built.

Determine Limitations of Other Connectives

Any binary connective can be expressed in terms of a truth table. For any proposed connective, verify if it can construct the NOT function. If it cannot create NOT, it cannot be functionally complete. Most binary connectives like AND, OR, and XOR cannot construct NOT alone.

Demonstrate Construction of NOT Using NOR and NAND

For NOR, NOT can be expressed as \( p \downarrow p \). For NAND, NOT can be expressed as \( p \mid p \). Both constructions are straightforward and show the ability of these operations to create the NOT function.

Conclude Aliasing Functionally Complete Connectives

Since the steps above show that only NOR and NAND can express the NOT operation independently, they are the only binary connectives that are functionally complete.

Key concepts

Functional Completeness

Functional completeness is a concept in propositional logic that refers to a set of logical connectives that can be used to express any possible truth function.
In simpler terms, if a set of connectives is functionally complete, you can build any logical statement or function using just those connectives. For example, if we use AND, OR, and NOT together, we can represent any logical expression.
The truly intriguing part about functional completeness in logic is the existence of minimal and surprising sets of connectives that are functionally complete on their own.
Among binary connectives, NAND (denoted as \( \mid \)) and NOR (denoted as \( \downarrow \)) are functionally complete. This means you can express any logical operation using just NAND or just NOR.
Here's a simple illustration: with NAND, the NOT operation can be constructed as \( p \mid p \), and similarly, NOR can also achieve this with \( p \downarrow p \). These abilities to derive NOT imply that we can build all standard logic functions (AND, OR) using combinations of either NAND or NOR.
Thus, functional completeness is a fascinating and powerful property in logic, showing how complex expressions can be simplified into basic operations.

Binary Connectives

Binary connectives are operations in logic that combine exactly two truth values, which are typically true and false.
Common binary connectives include logical operations like AND, OR, and XOR. These operations are fundamental building blocks in logic, acting as the basic operators to create more complex logical statements.
However, not all binary connectives are created equal. While they serve as invaluable tools in propositional logic, their ability to independently create or not create other logical functions varies significantly.
The power of a binary connective is truly tested when we consider its capability to generate all other logical functions, which is captured by the idea of functional completeness. For example, while AND and OR are useful, by themselves they cannot generate the NOT function, which is crucial for developing complex logical operations.
In contrast, binary connectives like NAND and NOR can singularly generate NOT—and thus all other functions, qualifying them as functionally complete.

Logical Operators

Logical operators are the fundamental elements of propositional logic, used to build complex expressions by manipulating truth values.
These operators include basic actions such as AND, OR, and NOT, each serving specific purpose in logic structures:

• **AND** results true only if both operands are true.
• **OR** results true if at least one operand is true.
• **NOT** inverts the truth value of an operand.

Such logical operators are the backbone of constructing logical statements in mathematics, computer science, and philosophy.
However, what makes NAND and NOR unique among logical operators is their ability to perform any logical operation due to their functional completeness.
With them, one can construct AND, OR, and NOT. This gives rise to interesting setups where complex logical systems rely solely on one operator, simplifying hardware design in digital circuits, for instance.
Therefore, while other logical operators play critical roles in logic, the universality of NAND and NOR highlights the importance of understanding functional completeness and the unique capabilities of these operators.