7.1.2. Tutorial 1: Part II

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 involving only the logical operators given in your collection.

This chunk introduces the concept of a 'functionally complete' set of logical operators. A functionally complete set allows for any logical expression to be expressed using only the operators in that set. For example, a set of operators may be considered functionally complete if it can express all possible truth functions for every possible input combination.

Think of a toolbox that contains all the necessary tools to fix any problem in your house. If you only have a few tools but they can do every required task, such as a hammer, a screwdriver, and a wrench, then this toolbox can be described as functionally complete for home repairs.

We want to prove that the set of these three operators is functionally complete. If the expression has an occurrence of implication, we can use the identity that p → q is logically equivalent to ¬p ∨ q and substitute it. For bi-implication, use the equivalence that ↔ is conjunction of two implications.

To prove functional completeness, we start with the logical operators in question. We demonstrate that if we encounter implication (p → q), it can be rewritten using negation and disjunction. This allows us to simplify compound propositions step-by-step into a form that uses only conjunction, disjunction, and negation. The process will progressively show that we can express any compound statement, establishing the completeness of the operators.

Imagine rewriting a recipe that calls for eggs and milk. Instead of saying 'add eggs and milk,' you might find alternative ingredients or expressions to convey the same meaning. Just as you can express your recipe in different ways, you can express logical statements using different operators while still retaining the same outcome.

It is sufficient to show that we can represent conjunction using disjunction and negation. A conjunction of p and q, denoted as p ∧ q, can be expressed as ¬(¬p ∨ ¬q) by applying De Morgan's law.

This chunk shows that we don't need both conjunction and disjunction to achieve functional completeness. We can represent conjunction using just disjunction and negation. By applying De Morgan's laws, we can express 'and' operations in terms of 'or' operations combined with negations. This further illustrates the flexibility of the logical operators.

Consider a situation where you have a set of rules for a game. Instead of saying 'Player A must be present and Player B must be present to start the game,' you can say, 'If Player A is not present or Player B is not present, the game cannot start.' Both statements convey the same rule but in different forms.

Similarly, we show that if only negation and conjunction are present, we can represent disjunction too. By stating p ∨ q as ¬(¬p ∧ ¬q), we demonstrate that our initial set can still express all necessary logical propositions.

Here we establish that even with only negation and conjunction, we can express disjunction. By again employing De Morgan's laws, we derive that any 'or' operation can be reformulated using our remaining operators. This step solidifies the assertion of functional completeness with different combinations of basic operators.

Picture a vending machine that offers snacks. If it only dispenses salty and sweet options, you can tell someone, 'If you don't want something salty or sweet, you shouldn't use the vending machine.' While this may sound limited, it still describes the available choices creatively through combinations and exclusions.

Question 9 asks whether a long compound proposition is satisfiable. The expression needs to be in conjunctive normal form, and I must find a truth assignment that satisfies all clauses.

This chunk introduces the concept of satisfiability in propositional logic, where we check if there exists an assignment of truth values to variables such that the entire proposition holds true. Using a systematic approach, one can test various truth assignments to see if all clauses can be satisfied simultaneously.

Think of solving a puzzle. Each piece represents a different variable, and to finish the puzzle, you must place all the pieces in a way that they fit together correctly. If you can fit all the pieces, the puzzle is 'satisfiable.' If not, it's like understanding that certain combinations will not work together, showing the importance of finding the right truth assignments.

Question 9a involves designing an algorithm to check if an input proposition is a tautology. The claim is that if X is a tautology, then its negation is unsatisfiable.

This section explains how to create an algorithm that utilizes an existing one to check for tautologies. It utilizes the relationship between a tautology and the satisfiability of its negation, providing a systematic way to determine if a given logical statement is always true.

Imagine you're checking if a light switch always makes a bulb light up. If every time you flip the switch and the bulb lights up, you can conclude that flipping the switch means the bulb is on without fail (a tautology). Conversely, if there was a scenario where flipping the switch didn't turn on the bulb, you would know the bulb does not always light up, akin to showing that the negation is satisfiable.

--