7.2.2. Proving Functionality with Three Operators

We define a functionally complete set of logical operators. A set of logical operators is functionally complete if every compound proposition can be converted into a logically equivalent proposition using only those operators in the set.

First, we need to understand what it means for a set of logical operators to be functionally complete. This means that through the operators in the set, one can represent any logical statement or proposition. If we have a specific logical operation that is a combination of several propositions (compound proposition), we should be able to rewrite that operation using just the operators that we have available in our set. Examples of these operators include conjunction (AND), disjunction (OR), and negation (NOT).

Imagine you are building a toy figure. If you were given a complete set of Lego blocks, you would be able to create any shape you want. Similarly, if you have a complete set of logical operators, you can create any logical statement or proposition you need.

To prove the set's functionality, we handle implications. We use the logical identity: p → q is logically equivalent to ¬p ∨ q. By substituting every occurrence of implication, we can express the compound proposition using conjunction, disjunction, and negation only.

When facing a proposition that contains an implication (p → q), we can replace it with its equivalent form using basic logical identities. Specifically, the implication can be rewritten in terms of disjunction and negation. This allows us to systematically eliminate implications from our expressions, leaving us with only conjunctions, disjunctions, and negations.

Think of this substitution as converting a complex recipe into simpler steps. Instead of trying to follow a complicated instruction (the implication), you're breaking it down into more manageable and recognizable tasks (the disjunctions and negations) that are easier to work with.

If the expression contains biconditional symbols (↔), we can replace them as well. A biconditional can be expressed as the conjunction of its constituent implications.

Biconditional statements are statements that express 'if and only if' conditions. To simplify a biconditional (like p ↔ q), we rewrite it as (p → q) ∧ (q → p). Then, by applying the earlier rule for implications, we can replace each of these implications with their disjunctive counterparts, ultimately transforming the entire statement into one that consists only of conjunctions, disjunctions, and negations.

Imagine a contract that states 'You will receive the bonus if and only if you complete the project.' This biconditional can be broken down into two simpler conditions: 'If you complete the project, then you receive the bonus' and 'If you receive the bonus, then you have completed the project.' This simplification helps clarify the terms of the contract.

It suffices to use just disjunction and negation to represent any statement. By converting conjunctions through De Morgan's laws, we show that all propositions are expressible with these two operators alone.

We can express any logical conjunction (p ∧ q) as a negation of a disjunction using De Morgan's laws. Specifically, (p ∧ q) can be rewritten as ¬(¬p ∨ ¬q). This means that with negation and disjunction alone, we can represent conjunctions as well, thus proving that these two operators are functionally complete.

Consider combining ingredients to make a dish. If you only had sugar (negation) and salt (disjunction), you could still create a variety of flavors by combining them (which represents conjunction). Just as with cooking, having fewer basic ingredients doesn't limit your ability to create diverse dishes.

In essence, either (negation with conjunction) or (negation with disjunction) can represent any logical statement.

The critical conclusion drawn from the experiments with the logical operators is that either combination of a negation operator with conjunction or a negation operator with disjunction is sufficient to construct any logical expression. This means we have options for how to work with logical expressions depending on the operators available.

Think of a toolbox that contains both a hammer and a wrench. Regardless of whether you use the hammer with screws (conjunction with negation) or the wrench with bolts (disjunction with negation), you can assemble a car. Similarly, with any set of functional operators, you can achieve the same logical outcomes.

--