3.5. Conjunctive Normal Form (CNF) Introduction

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.

Conjunctive Normal Form (CNF) is a standard way to express logical propositions. A compound proposition is in CNF if it is structured so that it is a conjunction (AND) of one or more clauses, where each clause is a disjunction (OR) of one or more literals. This structure simplifies the process of checking for satisfiability since it allows for systematic testing of truth values assigned to the variables.

Imagine a team of detectives solving a case. If they create a list of must-have evidence (clauses) that needs to be found (connected by AND—like all items in a shopping list), it will be easier to check one item at a time to see if they can solve the case, rather than looking for a vague description of what the evidence could be.

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

The formal definition states that an expression X is in CNF if it comprises one or more clauses joined by the AND operator. Each clause, in turn, is a combination of literals connected by the OR operator. For instance, in the expression (A OR B) AND (C OR D), there are two clauses: one composed of A and B, and the other of C and D.

Think of a recipe that requires you to gather ingredients before you can start cooking. Each clause represents a group of ingredients needed (like spices or vegetables), and you can only start cooking when you've gathered everything on your list. The CNF ensures you know exactly what groups of ingredients you need together.

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.

A clause is formed from literals, which are the most basic building blocks in logic. A literal can be a propositional variable, like P or Q, or a negated variable, like NOT P or NOT Q. The clause is constructed by combining these literals using the OR operator. For example, (P OR NOT Q) is a clause.

Imagine you have a list of items you could potentially use in a project—including both the items (like scissors) and things you won't use (like broken scissors). Each item in the list represents a literal. You can pick any one or more of them to use in your project, which is essentially what a disjunction represents—choosing any combination of literals.

My definition of literal here is a literal is either a propositional variable or the constants true or false. So here T stands for true F stands for false, and these are my constants.

Literals are the simplest elements in logical expressions. They are either variables that can be true or false, or they can be the predefined constants true (T) or false (F). For instance, if we consider the variable P, then both P (true) and NOT P (false) are literals.

Think about a light switch; it can either be ON (true) or OFF (false). These two states are similar to the true or false constants in logic. The position of the switch represents a propositional variable, and whether it is in the on or off position tells you its truth value.

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 determine if an expression is in CNF, we check if it can be broken down into conjunctions of clauses. Each internal segment must be a disjunction of literals. If so, the expression qualifies as CNF. For example, if X is defined as (P OR NOT Q) AND (Q OR NOT R), we find two clauses, each one made of ORs, confirming X is in CNF.

Consider organizing books on a shelf where each shelf (conjunction) has groups of books (clauses), each group containing different genres (disjunctions). If every shelf contains these organized groups, then your arrangement meets the required functionality!

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 and answer is yes.

It is indeed possible to convert any logical expression into CNF. There are algorithms that perform this transformation while maintaining the logical equivalence of the expression. This process typically involves eliminating implications, applying De Morgan’s laws, and using distributive laws to structure the expression appropriately.

Imagine reshaping clay into different forms; just like clay can be molded into various shapes without losing its mass, logical expressions can be reshaped into CNF without changing what they represent, ensuring the core meaning stays intact.

--