3.8. Verification of CNF

Before that let me introduce what we call as Conjunctive Normal Form or CNF form for a compound proposition. The motivation for studying the Conjunctive Normal form is that if you are compound proposition X is given in its CNF form then it is relatively easier to verify whether X is satisfiable or not.

CNF is a way of organizing logical expressions so that they can be easily checked for satisfiability. When a compound proposition is in CNF, it has a specific structure that allows computers to determine if there is a truth assignment that makes the expression true. This is important because problems in logic often need to be simplified to understand their solvability effectively.

Think of CNF as organizing your closet. When all clothes are neatly arranged in specific sections (like shirts in one section and pants in another), it becomes easier to find what you need. In logic, CNF organizes propositions in a way that makes it easier to check if they can be true under certain conditions.

So now let us formally define what do we mean by a conjunctive normal form? An expression X is said to be in its conjunctive normal form if it is expressed as a conjunction of clauses.

A conjunctive normal form (CNF) consists of multiple clauses connected by the AND operator (conjunction). Each clause is made up of literals connected by the OR operator (disjunction). This means that for an expression to be in CNF, you should see it as a series of 'OR'ed statements (literals) combined with 'AND' between them. This structure allows for straightforward checking of whether the entire expression is true.

Imagine a team project where each member must complete their task for the project to be successful. Each task can be completed (true) or not (false). If every member's task is completed (conjunction), then the project is successful (true). This mirrors how statements are combined in CNF.

Now, the question is, what is the clause? Well, it turns out that the clause is a disjunction of literals. Because informally in each clause, inside each clause you have disjunctions of various variables. Those variables might be either without the negation operator or with negation operator.

In CNF, a 'clause' refers to a set of literals combined using the OR operator. A 'literal' is simply a variable or its negation. So, if you have literals like p (true), ¬q (not q), and so on, you can form clauses by combining them with OR. For example, (p OR ¬q) is a clause. Understanding this helps in determining the structure of CNF.

Imagine voting for a holiday destination. Each option (beach, mountains, city) represents a literal, while saying, 'we can go to the beach OR mountains' forms a clause. You need at least one option (literal) to agree on a destination. In CNF, the overall choice (AND statement) requires agreement across all clauses to reach a final decision.

So let us verify whether this expression X which we have written here is indeed in its conjunction normal form as per this definition that we have given here.

To verify if an expression is in CNF, check if it consists entirely of clauses (disjunctions) combined by conjunctions. Each segment within parentheses should also be a valid disjunction of literals. If all these conditions are met, the expression is valid CNF.

Suppose you have a recipe listing multiple ingredients where you can choose any combination. But for the dish to be complete, you must make sure all sections of the recipe (clauses) are included. Just like checking each ingredient list to ensure they conform to the recipe, you check whether all parts of the expression are valid clauses in CNF.

Now the question is, well if my expression X is not given in its conjunctive normal form can I convert it into another expression which is in conjunctive normal form and which is logically equivalent to my original expression X.

If you have a logical expression not in CNF, it can be transformed into an equivalent CNF expression using a systematic process that involves eliminating bi-implications and implications, applying De Morgan's laws, and distributing disjunctions over conjunctions. The goal is to reach a form that's easier to analyze for satisfiability while preserving the logical meaning.

Think of changing a recipe that requires cooking methods not suitable for grilling. You might need to adjust the method and ingredients (apply logical transformations) until you have a version that can still be grilled but tastes just as good. Similarly, in logic, we manipulate the expression until it's in CNF without changing its essentials.

So let us see that algorithm. So the input here is some expression X which may or may not be in its conjunctive normal form...

The algorithm for converting an arbitrary expression to CNF consists of a series of steps: eliminate bi-implications, remove implications, apply De Morgan's laws, and finally distribute disjunctions over conjunctions. Following these steps systematically ensures that the new expression is logically equivalent to the original and adheres to CNF requirements.

Consider a set of drawers filled with different types of items. To find what you need quickly, you label each drawer (declaring bi-implications), then combine and separate items based on their types (removing implications and applying laws). The end result is a neatly organized system (CNF) where everything is easy to locate.

--