7.2.1. Functionally Complete Set of Logical Operators

A set of logical operators is termed functionally complete if every compound proposition can be represented as a logically equivalent proposition using only the operators in that set.

A functionally complete set of logical operators means that any possible logical statement can be constructed using just those operators. For example, if we have operators like conjunction (AND), disjunction (OR), and negation (NOT), we can create any logical expression without using any other operators. The essence of functional completeness lies in its ability to express any logical relationship purely using those included operators.

Think of a functionally complete set of logical operators as a toolset for building models. If you have a complete set of tools, you can construct anything you need. Similarly, with a functionally complete set of logical operators, you can express any logical statement or proposition just like you would build any object with all the necessary tools.

To prove that a set of operators is functionally complete, we can start with a compound proposition that includes implications (→). We can replace an implication using the logical equivalence p → q is logically equivalent to ¬p ∨ q.

In logic, implications can be tricky because they can be rewritten in terms of other logical operations. For example, instead of saying p implies q, we can say that not p or q is true. This transformation allows us to eliminate implications when we're working with a logical expression. By repeatedly applying this substitution for all occurrences of implications, we can rewrite any complex logical statement into one that solely uses conjunction, disjunction, and negation.

Imagine you have a complex recipe, but you realize that one of the ingredients can be substituted with two others. By doing this substitution throughout the recipe, you can simplify your cooking process without losing the essence of the dish. Similarly, substituting implications in logic simplifies expressions while keeping the same truth values.

If a proposition involves a biconditional operator (↔), it can be expressed as the conjunction of two implications. This means p ↔ q can be rewritten as (p → q) ∧ (q → p), which can then be further simplified by replacing the implications.

Just like implications, biconditional statements can also be rewritten in simpler forms. The biconditional means that both statements must be true together or false together. By breaking it down into two separate implications, we can further dive into the logical operations involved and replace each implication, ensuring we stay within our original set of logical operators (conjunction, disjunction, negation).

Think of a two-way street: just like both directions must be open for it to be functional, a biconditional requires both parts to be true or false together. By expressing it as two separate one-way streets (implications), you can manage traffic (truth values) on each road without any confusion.

Even without using both conjunction (∧) and disjunction (∨) operators, it is possible to represent logical propositions using just disjunction and negation by employing De Morgan's laws.

To show that disjunction (OR) and negation (NOT) can suffice, we can take a conjunction like p ∧ q and transform it into an expression involving just disjunction and negation. According to De Morgan's laws, p ∧ q can be expressed as ¬(¬p ∨ ¬q). This means that by intelligently applying negation and disjunction, we can represent conjunction as well.

Imagine trying to say that you have a specific pair of shoes and a jacket. Instead of simply saying you have both, one could also say 'It's not true that I don't have the shoes or I don't have the jacket,' which conveys the same meaning but in a different structure. This demonstrates how we can still reach the same conclusion using different logical constructs.

The argument can also be made that solely using negation (¬) and either conjunction (∧) or disjunction (∨) is still functionally complete.

This means that even if we only have negation and one of the other operators (either conjunction or disjunction), we can represent all logical statements. For example, using just negation and disjunction provides sufficient means to reformulate conjunction. This shows the versatility of logical operators in formulating any logical expression.

Imagine a toolbox that only has a hammer and a pair of pliers. Even if you don't have every tool available, you can still accomplish a number of tasks—driving nails in and gripping odd shapes—using creativity with just those two tools, much like how logical operations can still be versatile despite limited choices.

--