Chapter 2 · Computational Thinking & Algorithms

2.7Propositional Satisfiability

Can a logical statement ever be true? Learn the test for satisfiable and unsatisfiable expressions.

Written and checked by Muhammad Raheel(opens in a new tab)

Full Stack Developer · AI Engineer · Reviewed 21 Oct 2026 · 2 min read

On this page

Some rules can be followed. Some rules can never be followed, because they fight each other. Satisfiability is the logic word for this idea. It asks one question about an expression: is there any way to make it true?

Computer scientists use this idea a lot. The book says it helps us test logical statements and make decisions. It is also important for designing algorithms and checking that programs work correctly.

The book's pizza example

The book gives two everyday instructions:

"Bring pizza OR (burger AND do NOT bring soda)." You can follow this one. Bring pizza and no soda, and the instruction is met. So it is satisfiable: a solution exists.
"You must bring pizza AND you must NOT bring pizza." Nobody can do both. No solution exists, so it is unsatisfiable.

We checked all eight cases of the first instruction (pizza, burger and soda each brought or not). It is true in five of them. You only need one.

Conditions for a Proposition to be Satisfiable

Here is the rule, in the book's words:

What decides the answer? The structure of the expression and the connectives inside it: AND, OR and NOT. To test an expression, list all possible cases in a truth table. Look at the result column. One "true" is enough for satisfiable. All "false" means unsatisfiable.

The test: check all cases with a truth table; if there is at least one true outcome the proposition is satisfiable, if all are false it is unsatisfiable

Examples of Satisfiable and Unsatisfiable Expressions

The book uses three short examples. We worked out their truth tables:

Expression	Rows that are true	Verdict
P OR Q	3 of 4	satisfiable
P AND Q	1 of 4 (both true)	satisfiable
P AND NOT P	0 of 2	unsatisfiable

"P AND NOT P" can never be true, because P cannot be true and false at the same time.

The book ends with a class activity: your instructor gives you several expressions, and you sort them into satisfiable and unsatisfiable.

Practice this topic

All MCQs of this chapter with answers

Short questions

1.What is propositional satisfiability?2 marks
Answer
From the book: "Propositional satisfiability is a concept in logic that checks whether a statement can be true. It helps us know if a logical expression has at least one situation where it is true."
2.When is a proposition satisfiable and when is it unsatisfiable?2 marks
Answer
From the book: "A proposition is satisfiable if there is at least one combination of truth values that makes it true. If all possible combinations make it false, it is unsatisfiable."
3.What does satisfiability depend on?2 marks
Answer
From the book: "Satisfiability depends on the structure of the expression and the logical connectives used. Logical connectives like AND, OR, and NOT determine whether a statement can be true."
4.How can we test whether a proposition is satisfiable?2 marks
Answer
From the book: "Checking all possible cases using a truth table is one way to test satisfiability. A proposition with at least one "true" outcome is satisfiable."
5.Give two examples of satisfiable expressions from the book.2 marks
Answer
From the book: "An example of a satisfiable expression is "P OR Q." This is true if either P or Q is true. Another example is "P AND Q," which is true when both P and Q are true."
6.Why is "P AND NOT P" an unsatisfiable expression?2 marks
Answer
From the book: "An unsatisfiable expression is "P AND NOT P." This is never true because P cannot be both true and false."
7.Is "Bring pizza OR (burger AND do NOT bring soda)." satisfiable? Give a reason.3 marks
Answer
Yes. From the book: "Result: Bring pizza, no soda = satisfiable expression. Solution exists." Bringing pizza and no soda is one way to make the statement true, and at least one way is enough.
8.Why is satisfiability important in computer science?3 marks
Answer
From the book: "This concept is widely used in computer science, especially in problem solving and programming. Satisfiability helps us test logical statements and make decisions. It is important for designing algorithms and verifying programs."

Long questions

1.What is propositional satisfiability? Explain satisfiable and unsatisfiable propositions with examples.8 marks
Answer
Cover all parts, using the book's text:
1. Meaning (verbatim): "Propositional satisfiability is a concept in logic that checks whether a statement can be true. It helps us know if a logical expression has at least one situation where it is true." DO YOU KNOW?: "A logical expression is satisfiable if there is at least one way to make it true."
2. Uses: "widely used in computer science, especially in problem solving and programming"; "It is important for designing algorithms and verifying programs."
3. Satisfiable vs unsatisfiable (verbatim): "A proposition is satisfiable if there is at least one combination of truth values that makes it true. If all possible combinations make it false, it is unsatisfiable." "Satisfiable expressions have at least one true outcome, while unsatisfiable expressions have none."
4. Examples of satisfiable expressions: "P OR Q" ("true if either P or Q is true") and "P AND Q" ("true when both P and Q are true"). Everyday example: "Bring pizza OR (burger AND do NOT bring soda)." "Result: Bring pizza, no soda = satisfiable expression. Solution exists."
5. Examples of unsatisfiable expressions: "P AND NOT P", "never true because P cannot be both true and false". Everyday example: "You must bring pizza AND you must NOT bring pizza." "Result: No solution exists = unsatisfiable expression."
Aim for 250-350 words.
2.Explain the conditions for a proposition to be satisfiable. Show with a truth table how "P AND Q" is satisfiable and "P AND NOT P" is unsatisfiable.6 marks
Answer
1. Conditions (verbatim): "A proposition is satisfiable if there is at least one combination of truth values that makes it true. If all possible combinations make it false, it is unsatisfiable. Satisfiability depends on the structure of the expression and the logical connectives used. Logical connectives like AND, OR, and NOT determine whether a statement can be true. Checking all possible cases using a truth table is one way to test satisfiability. A proposition with at least one "true" outcome is satisfiable."
2. Truth table for P AND Q (4 rows): FF gives F, FT gives F, TF gives F, TT gives T. One "true" outcome, so it is satisfiable. Book: "P AND Q," "is true when both P and Q are true."
3. Truth table for P AND NOT P (2 rows): P = F gives F AND T = F; P = T gives T AND F = F. No "true" outcome, so it is unsatisfiable. Book: "This is never true because P cannot be both true and false."
4. Close: "This condition helps in reasoning and decision-making."
Aim for two truth tables plus 120-180 words.

Share on WhatsApp

In this chapter