3.2. Application of SAT Problem

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. So this is an example of 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. So in this case, this is my expression X and it turns out that if I make p to be true and r to the true and q to be true then the overall expression X becomes true.

The SAT problem, or satisfiability problem, seeks to determine if a given compound proposition (a statement made up of variables and logical operations) can be made true by evaluating it with the right truth values assigned to its variables. A compound proposition is a combination of simpler propositions. In this context, a proposition is called satisfiable if there is at least one way to assign truth values (true or false) to its variables such that the entire expression evaluates to true. In the example given, the assignment p = true, q = true, and r = true makes the expression true, so it's considered satisfiable.

Imagine a restaurant scenario where you have several menu items (the variables) that either can or cannot be included in a meal (the proposition). The SAT problem is like figuring out if you can create a meal that satisfies certain dietary restrictions (making the meal 'true'). If you find a combination that works, then the meal is satisfiable.

Because satisfiable means at least one truth assignment is there for which X will be true, but unsatisfiable it means it is always false or in other words it is a contradiction and if it is contradiction then you take the negation of that it will be always true.

In formal logic, when discussing satisfiability, we encounter two terms: satisfiable and unsatisfiable. A proposition is satisfiable if there is at least one truth assignment that makes it true. Conversely, a proposition is unsatisfiable if there is no possible truth assignment that can make it true, indicating that the proposition is inherently contradictory. The negation of an unsatisfiable proposition (which denotes that it cannot ever be true) would therefore always be true – this is known as a tautology.

Think of a light switch that is broken. If the light switch is always in the 'off' position (the unsatisfiable case), it can never be turned on, no matter how you try to flip it. Conversely, if the switch can be flipped to 'on' at least once (the satisfiable case), it is similar to having an option that works sometimes.

The SAT problem is the following. You will be given a compound proposition X here and you have to verify whether the proposition X is satisfiable or not. That means you have to give me a yes or no answer.

The SAT problem involves determining whether a given compound proposition X has a solution that's true (satisfiable) or not (unsatisfiable). This is a fundamental question in computer science because a wide range of problems can be reduced to SAT. The challenge lies in the fact that while we can often reason about small cases easily, the problems typically grow exponentially in complexity as the propositions become larger and more complex, leading to the term 'hard problem' in computing.

Consider trying to solve a complex jigsaw puzzle. You can only tell if you've succeeded (the puzzle is complete) or not (there are missing pieces) until you've attempted various combinations of pieces. This mirrors the SAT problem, where you seek the correct arrangement to achieve a truthful statement.

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 way of structuring a logical expression such that it is written as a combination of conjunctions (ANDs) of disjunctions (ORs). Each disjunction contains literals, which are basic propositions or their negations. CNF is utilized because it simplifies the process of checking whether a proposition is satisfiable. If a logical formula is in CNF, various algorithms can quickly determine satisfiability compared to other forms.

Imagine sorting a recipe list where each ingredient must meet certain conditions (like 'must be fresh' AND 'must be in stock'). If you list them separately but grouped by the type of dish (like using tomatoes OR cucumbers), this is similar to CNF – a convenient structure that makes it easier to verify if you have everything needed.

So what I am going to do here is I am going to represent an instance of Sudoku Puzzle using a compound proposition...

The SAT problem can be applied to real-world puzzles like Sudoku, where you need to fill in a grid with numbers subject to certain constraints (like each number 1-9 must appear exactly once per row, column, and block). This can be structured as a series of compound propositions representing the constraints of Sudoku. By converting a Sudoku puzzle into a SAT problem, one can apply solving techniques from SAT to find a solution for the puzzle.

Think of Sudoku as a complex arrangement of books on a shelf. Each book (number from 1-9) must go on a designated spot (grid position) ensuring no duplicates in rows or columns (like genres only appearing once on a shelf). Solving the puzzle with SAT is like using a methodical approach to ensure every book is in its correct place according to the rules.

--