3.2.5. Finding Truth Assignments

So what is the satisfiability problem? So first let us first define, what do we mean by a satisfiable proposition? So imagine you are given a compound proposition X. The compound proposition X will be called satisfiable if it is true for at least one truth assignment of the underlying propositional variable.

This chunk defines what the satisfiability problem is. A proposition is satisfied when there is at least one way to assign truth values to its variables that makes the proposition true. For instance, if you have a proposition with variables p, q, and r, and you can assign them the values true (T) or false (F) such that the proposition evaluates to true, then it's satisfiable. If you find at least one combination of truth assignments that holds true, we label that proposition as satisfiable.

Think of satisfiability like a puzzle where you have different pieces (the variables) that need to fit together in a certain way (the truth assignment) to form a complete picture (the proposition). If at least one combination of pieces fits perfectly, then the puzzle is solvable.

An alternate definition here for satisfiability is the following. I will say that my compound proposition X is unsatisfiable if and only if negation of X is the tautology.

This part explains that if a proposition X is unsatisfiable, it means it can never be true regardless of how we assign the truth values to its variables. In logical terms, this is expressed by saying that the negation of X is always true, or in other words, X is a contradiction. This relationship helps us understand the boundary of what can be satisfied versus what cannot be satisfied.

Imagine a group of friends trying to plan a picnic on a day when it always rains. If the day is rainy (the negation of a sunny day) for a picnic proposition, then the picnic can never happen (X is unsatisfiable). However, if there is at least one day it could be sunny (X is satisfiable), then the picnic could proceed.

The question here the definition say that even if you have one true assignment for which X becomes true, my statement X will be called as satisfied. The SAT problem is the following.

The SAT problem is to determine whether a given compound proposition X is satisfiable, meaning you need to verify if there is at least one truth assignment that makes X true. This problem is significant in computer science because finding such truth assignments can be complex and time-consuming, especially for larger and more complex propositions.

Consider a job application process where you need to satisfy specific criteria (truth assignments) to be selected for a job (making proposition true). If you meet at least one crucial requirement, your application can proceed. However, if you do not meet any of the requirements, you cannot get the job (unsatisfiable scenario).

This is one of the widely studied problems in computer science. There are plenty of applications of this SAT problem. We will see one such application in this lecture and it is believed to be a hard problem.

The SAT problem is considered 'hard' because, despite extensive study, no efficient algorithms have been revealed that can quickly determine whether any arbitrary proposition is satisfiable. An efficient algorithm would need to provide answers in a reasonable time regardless of the size or complexity of the proposition.

Think of trying to organize a large festival where various constraints exist, such as venue availability, artist schedule, etc. Finding a combination of arrangements that satisfies all restrictions can be extremely challenging. An efficient method to tackle it has yet to be discovered, exemplifying the hard nature of the SAT problem.

Before that let me introduce what we call as Conjunctive Normal Form or CNF form for a compound proposition.

Conjunctive Normal Form (CNF) expresses a compound proposition in a standardized way that consists of a conjunction of one or more clauses. Each clause is a disjunction of literals (which may be simple variables or their negations). This form is crucial because it simplifies the process of verifying satisfiability; it makes it easier for algorithms to determine if a proposition can be satisfied.

Imagine a recipe where every ingredient must be included (conjunction) and each ingredient could be modified (disjunction). CNF is like a structured way to write the recipe, where we clearly outline what combinations of ingredients can or cannot be used, simplifying the cooking process.

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.

This chunk explains how to verify if a given expression is in CNF. The expression should show a conjunction (AND) of clauses, where each clause must exhibit disjunctions (OR) of literals. This structured verification ensures compliance with the CNF standards and establishes whether the initial expression can indeed be considered as such.

Think of it like checking a test or quiz in school. Each question (clause) must adhere to a specific format (disjunction of ingredients) and all questions must collectively fall into categories (conjunction). Ensuring every aspect of the quiz meets these standards signifies that the test adheres to the intended norms.

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 a proposition isn't in CNF, there's a systematic approach to convert it without changing its fundamental truth. This involves multiple steps: eliminating bi-implications, dealing with implications, applying De Morgan’s laws, and utilizing distributive laws to ensure the expression changes appropriately while adhereing to the CNF structure.

Imagine a disorganized filing system at an office (original expression). By following a systematic sorting method (steps for conversion), you ensure that every document is categorized correctly and adheres to a structured filing system (CNF). In the end, you achieve a more efficient retrieval of documents.

Now let us see some fun application of the SAT problem, of course as I said there are plenty of advanced applications of the SAT problem.

One engaging application of SAT problems is in solving Sudoku puzzles. Each Sudoku challenge can be expressed as a propositional variable that needs satisfiability verification. This shows the direct link between logic programming and practical problem solving, demonstrating how theoretical concepts can be applied to real-world scenarios.

Imagine Sudoku as a giant logic puzzle. Each cell must be filled in such a way that all rules are satisfied: each number must appear once per row, column, and sub-grid. The SAT problem helps determine whether that's even feasible, much like a check to ensure a plan can actually be realized before moving forward with execution.

--