7.2. Question 8

In question 8 we are defining a functionally complete set of logical operators. A set is functionally complete if every compound proposition can be converted into a logically equivalent proposition using only the operators in this set.

A set of logical operators is said to be functionally complete if any logical expression can be created using just those operators. This means all logical propositions can be expressed through combinations of these operators without needing any others. For instance, if we start with a simple logical proposition, we can use available operators to derive all possible outcomes.

Think of this concept as having a limited set of building blocks (logical operators) with which you can create anything—your house (logical propositions), a car, or even sculptures. With the right blocks, you can build any structure you need.

The first part of question 8 asks you to prove that the set of these three operators is functionally complete. This means that any compound proposition can be represented using just these three operators: conjunction, disjunction, and negation.

To prove that a set of logical operators is functionally complete, we start with any compound proposition that includes logical implications. By using substitution rules, we can replace implications by using the disjunction and negation operators. For example, an implication such as p → q can be replaced with ¬p ∨ q, allowing us to express the original proposition entirely in terms of conjunction, disjunction, and negation.

Imagine you have a toolbox with various tools, say only a hammer, a screwdriver, and a wrench. You are tasked with assembling furniture (the compound proposition). Even though you only have these three tools, with creativity, you can dismantle and rebuild any piece of furniture using just those tools.

If my expression has a bi-implication (↔) symbol, I can represent it in terms of the conjunction of two implications, which I can then substitute with the known equivalences.

When faced with a bi-implication like p ↔ q, it's useful to recall that it can be expressed as (p → q) ∧ (q → p). Now, since we know how to translate both implications into disjunction and negation, we can express the entire bi-implication only with conjunction, disjunction, and negation, maintaining functional completeness.

Think of it like a two-way street sign: if a car can go in either direction, you can view it as two separate one-way arrows in opposite directions. Each arrow can easily direct traffic, just like converting implications does not change the essence of the original operations.

The second part of the question shows that we do not need both conjunction and disjunction; we can represent every statement with just a disjunction and negation.

This means that if we only use negation (¬) and disjunction (∨), we can still construct all logical propositions. For instance, you can express an 'and' operation (p ∧ q) in terms of these two operators as well. By applying De Morgan's laws, we can convert conjunctions into only disjunctions and negations.

Imagine making recipes with only two ingredients. Even if you lack some key components (like an egg or milk), you can still whip up various dishes by creatively mixing these two available ingredients to reproduce any desired flavor.

To represent a conjunction like p ∧ q, it can be equivalently expressed as ¬(¬p ∨ ¬q) by using De Morgan's law.

This step shows how conjunctions can be constructed using only disjunctions and negations. We interpret the conjunction of p and q as the negation of the disjunction of their negations, ensuring we can still express 'p and q' without using conjunction directly.

Think of cleaning your room. Instead of saying, 'I will clean my room if I am not too tired or distracted,' you can rephrase it: 'I will not be tired or distracted while I clean my room.' Using the rules of language allows you to maintain the meaning no matter how it’s structured.

--