7.3.2. Verification of Other Expressions

If you are given a set of logical operators, we say it is functionally complete, if every compound proposition can be converted into a logically equivalent proposition involving only the logical operators in your collection. The first part of question 8 asks you to prove that the set of three operators is functionally complete.

Functional completeness means you can express any logical expression using just a select few operators. For example, if you have a set of operators like conjunction (AND), disjunction (OR), and negation (NOT), you can represent every logical statement or expression using only those operators. To prove this, you would start by showing that if you have a proposition involving implications, you can convert it into a form that does not use implications but instead uses the allowed operators. This shows that these operators can indeed construct any logical statement.

Imagine you have a toolbox that only contains a hammer, a screwdriver, and pliers. If you can build a complete piece of furniture using just those tools, you prove that your toolbox is 'functionally complete' for furniture assembly. Similarly, the logical operators can be thought of as tools that together are capable of creating any logical structure, such as any proposition.

If a compound proposition contains implications (like p → q), we can convert it using the logical identity that p → q is equivalent to ¬p ∨ q. By substituting every occurrence of implication, we can express the entire proposition using just conjunction, disjunction, and negation.

When you encounter an implication in a logical expression, it can be a bit tricky since we might not always think in terms of its equivalent forms. The key conversion here is recognizing that ‘if p then q’ is actually saying ‘either p is not true, or q is true’. This allows you to replace all implications in a complex expression, thereby simplifying it into a format that only utilizes your base logical operators: AND, OR, and NOT.

Consider a simple rule: 'If it rains (p), then the ground gets wet (q)'. We can rephrase the rule: 'Either it does not rain or the ground gets wet'. This rephrasing allows us to represent conditions more flexibly, just like how we can replace complications in logical expressions with simpler forms.

To represent conjunction (AND), we can express p ∧ q as ¬(¬p ∨ ¬q) using De Morgan's Law. This means that ‘p AND q’ can be represented just with the negation and disjunction operators.

Using De Morgan's Law, which states that the negation of a disjunction is the conjunction of the negations, we can transform an expression involving AND into an expression that only uses OR and NOT. This transformation is significant, showing that we do not need direct access to the AND operator; we can derive it logically from the others.

Imagine a rule that says you can attend a party if both you have an invitation (p) and you have time to go (q). If we wanted to express this without using ‘AND’, we could say it's NOT the case that you don't have an invitation OR you don't have time. This reframes our rule into a format that still conveys the same requirements for attending the party.

Just having a negation operator and a disjunction operator means it is enough to represent any compound proposition. This fact can be shown by proving that you can represent conjunction with just those two operators.

This part of the discussion emphasizes that even if you only have the capabilities to negate (flip truth values) and combine (OR), you can still represent every logical operation necessary. By showing you can derive AND from these operators, you strengthen the understanding of their functional completeness.

Think of a poker game where you have two cards. If instead of saying you need both cards to win, you could claim that it’s not the case you don’t have both or you do not win at all. Thus, even without explicitly stating 'both cards', the logic remains clear and allows for strategic expression.

--