Related Tags

What is satisfiability in propositional logic?

Naima Ali

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

Mathematical logic is the study of how we reason, which is pivotal in every field of life. Satisfiability is one of the most important elementary concepts in mathematical logic. Before discussing the concept of satisfiability, let’s briefly overview propositional logic.

Propositional logic

Propositional logic deals with propositions and the logical relationships between them. A proposition is a declarative statement that can either be true or false, but not both. Multiple propositions can be combined using logical operations to make a compound proposition.

Satisfiability

A compound proposition is satisfiable if it is true for some assignment of truth values to its variables. It is trivial to note that a tautology is always satisfiable.

Note: A proposition that is always true is a tautology. Contradiction is a proposition that is always false. A proposition that is neither a tautology nor a contradiction is called a contingency.

A compound proposition is unsatisfiable when there is no assignment of truth values for which it is true.

Note: A compound proposition is unsatisfiable if and only if its negation is a tautology.

When we find a specific assignment of truth values that makes the compound proposition true, that is proof of its satisfiability. Such an assignment is called a solution or satisfying assignment.

On the other hand, we need to demonstrate that no satisfying assignment exists to establish a compound proposition to be unsatisfiable.

We can use clever arguments to show that a compound proposition is satisfiable, or we can check all the possible assignments using a truth table.

Example

Let’s find out whether the following compound proposition is satisfiable or not:

• $(p\lor \neg q)\land (q\lor \neg r) \land (r \lor \neg p)$

First, we determine the satisfiability by reasoning about the truth values instead of using a truth table. We see that the above proposition is true when $p$, $q$, and $r$ have the same truth value. Hence, it is satisfiable, as we have found at least one satisfying assignment.

The truth table for the example above is as follows, which verifies the argument already presented:

$p$ $q$ $r$ $(p\lor \neg q)$ $(q\lor \neg r)$ $(r\lor \neg p)$ $(p\lor \neg q)\land (q\lor \neg r) \land (r \lor \neg p)$
T T T T T T T
T T F T T F F
T F T T F T F
T F F T T F F
F T T F T T F
F T F F T T F
F F T T F T F
F F F T T T T

It is important to note that when the number of variables grows, the number of rows in a truth table grows exponentially.

Note: Since each variable has only two possible values, that is, true or false, a truth table will have $2^n$ rows, where $n$ is the number of variables.

In the example above, we have $3$ variables, so we have $8$ rows. Similarly, if we have $1000$ variables, the number of rows of the truth table will mount to $2^{1000}$. It doesn’t practically seem possible to generate such large truth tables to prove the satisfiability of a given compound proposition. Hence, truth tables are often not considered an efficient option.

NP-completeness

In general, finding the satisfying assignment for some arbitrary compound proposition is NP-complete. Steven Cook proved it in 1971.

Note: A problem is called a member of class NP if its solution can be verified in polynomial time. Problem $A$ is called polynomial time reducible to problem $B$ if we can convert any instance of problem $A$ to an instance of problem $B$ in polynomial time.

A problem is called NP-complete if it is a member of class NP and all the members of class NP are polynomial time reducible to that problem.

We can use the satisfiability problem, also known as SAT, to prove that some problem $P$ is a member of class NP and SAT is polynomial time reducible to $P$. In the theory of computers, SAT is of central importance. There are many problems that are NP-complete. The travelling salesman problem, subsets sum problem, Hamiltonian cycle problem, and vertex-cover problem are a few examples from a long list of known NP-complete problems.

RELATED TAGS

CONTRIBUTOR

Naima Ali