3.3. Unsatisfiable Proposition

So first let us 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. 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. Because for this truth assignment this p disjunction ¬q becomes true. The disjunction of q ¬r becomes true, the disjunction of r ¬p also becomes true and conjunction of true, true, true is overall true. So, I have one truth assignment for p, q and r for which the statement X becomes true.

A satisfiable proposition is one that can be true under at least one arrangement of truth values for its variables. In our example, when specific values (true for p, q, and r) are assigned to the variables, the compound proposition is true. Here, each disjunction (like p or ¬q) must evaluate to true for the entire expression X to be true. It's crucial to understand that only needing one scenario where the proposition holds true makes it satisfiable, even if other scenarios evaluate it as false.

Think of a group of friends deciding on a movie to watch. If at least one friend wants to see a particular film, you can consider the choice of that movie as 'satisfied.' Even if most of the friends prefer other films, the proposition of watching that movie is still satisfiable because at least one person supports it.

An alternate definition here for satisfiability is the following. I will say that my compound proposition X is unsatisfiable. I stress unsatisfiable if and only if negation of X is the tautology. And why so? Because if X is unsatisfiable that means it is always false, right? 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.

An unsatisfiable proposition cannot be true under any arrangement of its variables, implying that it is perpetually false. The negation of such a proposition must always be true, thus making it a tautology. Understanding this definition clarifies how unsatisfiability is intrinsically tied to logical contradictions, where the negation flips the circumstances from false to true permanently.

Imagine trying to fulfill a requirement that says 'You must be both here and not here at the same time.' No matter what you do, this requirement is impossible to satisfy, making it a contradiction. Therefore, the condition can never be true, representing an unsatisfiable proposition.

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. You will be given a compound proposition X here and you have to verify whether the proposition X is satisfiable or not.

The SAT problem involves determining whether a given compound proposition can be satisfied by some assignment of truth values. It essentially asks, 'Can we find a combination of true/false values for the variables in proposition X that allows it to hold true?' If such an assignment exists, then the proposition is considered satisfiable.

Consider a multiple-choice quiz where you must choose the correct answers. If there is at least one combination of choices that yields a high score, the quiz is deemed satisfiable. If no selection combination results in a passing score, the quiz is unsatisfiable.

And 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 recognized for its extensive applications across various domains in computer science, particularly in logic, algorithm design, and artificial intelligence. The 'hard problem' status arises from the belief that no efficient algorithm exists for solving all instances of SAT quickly. This complexity highlights the depth of challenges faced while handling various logical propositions in computational settings.

Think of a vast maze with multiple paths. Finding the shortest path from start to finish can be tricky, especially when new paths are added or changed. While some mazes might be easier to solve, others increase in complexity to the point where you need advanced strategies or might never find an efficient way to reach the end.

--