7.3.1. Satisfiability of a Compound Proposition

We say a set of logical operators is functionally complete if every compound proposition can be converted into a logically equivalent proposition using only those operators. For instance, if we have three operators: conjunction, disjunction, and negation, any compound proposition can be represented by these operators.

Functional completeness means that with certain logical operators, we can express any logical statement. In this case, if we have conjunction (AND), disjunction (OR), and negation (NOT), we can create any other logical function starting with any given compound proposition. For example, if a proposition includes 'implies' (→), we can use the logical equivalence that p → q is the same as NOT p OR q. By using these transformations, we can replace any occurrence of 'implies' in a proposition. The process involves repeatedly applying known logical identities until only our base operators are left.

Think of a toolbox for fixing things. The toolbox contains a hammer, a screwdriver, and a wrench. If you have these three tools, you can tackle any kind of basic repair—tightening screws, driving nails, or loosening bolts. Similarly, having conjunction, disjunction, and negation allows us to construct any logical statement or proposition.

If my expression has a bi-implication (↔) symbol, I can use the identity that this bi-implication is equivalent to the conjunction of two implications. Thus, we can rewrite those implications using our base operators.

The equivalence of bi-implication allows us to express it in terms of simpler operators. Specifically, p ↔ q can be expressed as (p → q) AND (q → p). Each of these implications can then be transformed further into conjunctions and disjunctions by substituting with what we know about logical identities. Hence, all logical operators can ultimately be defined using conjunction, disjunction, and negation.

Imagine you are building a house. You have a goal to construct it using beams (AND), bricks (OR), and mortar (NOT). No matter how complex the design or what specific building elements you want (the bi-implications), you can still build it using just these three foundational components.

It is sufficient to have only disjunction and negation to represent every statement, as well as only conjunction and negation.

In logic, we can show that if we only have disjunction (OR) and negation (NOT), we can still express conjunction (AND). For example, the expression 'p AND q' can be transformed using De Morgan's Law into 'NOT (NOT p OR NOT q)'. The key idea is that these two forms of logical expression (using just disjunction and negation or just conjunction and negation) are functionally complete on their own, meaning we do not need all three forms to express any compound proposition.

Consider a cooking recipe. Even if the recipe only calls for flour and sugar, you can still create a variety of baked goods by mixing, kneading, and applying heat. Likewise, just having either sets of logical operators allows you to bake up any logical truth.

To determine whether a long compound proposition is satisfiable, one can analyze its conjunctive normal form and attempt to find a truth assignment that satisfies all clauses involved.

A compound proposition is satisfiable if there exists at least one assignment of truth values to its variables that makes the entire proposition true. When a compound proposition is in conjunctive normal form, it is expressed as a conjunction of several clauses, where each clause is a disjunction of literals. To check satisfiability, you can assume different truth values and test combinations to see if all clauses can be satisfied simultaneously. This often involves some trial and error or strategic assignments of truth values.

Imagine trying to complete a jigsaw puzzle where each piece represents a clause. To finish the puzzle, you need to find which pieces fit together correctly. Some combinations will work, and some won’t, just like in logical expressions where certain truth assignments will satisfy all conditions, and others won't.

--