Skip to content
learn
  1. Learn
  2. Artificial Intelligence
  3. Knowledge, Logic and Planning

AI AI-02.02

Propositional logic

Syntax and semantics, truth tables, entailment, inference rules, resolution, and the SAT solvers that decide huge formulas, with a truth table generator.

Intermediate 14 min Last reviewed

The big idea

Rules written in English are ambiguous. "If the alarm is on and a door opens, call security" seems clear until someone asks whether it applies when the alarm is switched on after the door opens. A program needs a language where every sentence means exactly one thing, and where "does this follow from that?" has a definite answer that can be checked mechanically.

Propositional logicA logic whose sentences are built from true-or-false propositions joined by not, and, or, implies and if-and-only-if. is the simplest such language. Its building blocks are statements that are either true or false, such as "it is raining" or "the alarm is on", combined with five connectives. It cannot talk about objects or say "every", but it is precise, it is fully automatic, and it is the language of the SAT solvers that check computer chips and solve scheduling problems with millions of variables.

The key idea is easiest to see as a detective's reasoning. The detective does not know what happened, but each clue rules out some possible versions of events. When every version still standing agrees that the butler did it, the detective can say "the butler did it" with certainty, without knowing anything else. Logic calls this entailment, and checking it is the main job of a reasoning system.

How it works

Step 1: Syntax

A propositionA statement that is either true or false, written as a symbol such as P or Rain. is a symbol standing for a statement that is true or false: , , or readable names such as and . Sentences are built with five connectives:

ConnectiveWrittenRead asTrue when
negationnot PP is false
conjunctionP and Qboth are true
disjunctionP or Qat least one is true
implicationif P then QP is false, or Q is true
biconditionalP if and only if Qboth have the same value

In the lab and code below these are typed as ~, &, |, -> and <->.

Implication is the one that surprises people. is only a promise about what happens when is true. If is false, the promise is not broken, so the implication is true. "If it rains, the ground is wet" is not contradicted by a dry, sunny day.

Step 2: Semantics, models and truth tables

A modelAn assignment of true or false to every proposition symbol: one possible way the world could be. is one possible world: a choice of true or false for every proposition. With propositions there are models. A truth table lists them all, one per row, and computes the value of a sentence in each.

A sentence is valid (a tautologyA sentence that is true in every model, such as P or not P.) if it is true in every row, satisfiable if it is true in at least one, and unsatisfiable if it is true in none.

Step 3: Entailment

A knowledge base is a set of sentences the system believes. entailsKB entails alpha (written KB |= alpha) when alpha is true in every model in which KB is true. a sentence , written , if is true in every model where is true. In pictures, the models of sit entirely inside the models of :

Entailment as containment of models All eight models of Rain, Sprinkler and Wet are listed. Four of them, where Wet is false, lie outside the region for Wet. Inside the Wet region, a glowing region holds the three models where the knowledge base is true: rain and sprinkler, rain only, and sprinkler only, all with Wet true. The fourth Wet model, no rain and no sprinkler, is in the Wet region but outside the knowledge base region. Because the knowledge base region lies entirely inside the Wet region, the knowledge base entails Wet. all 8 models models of alpha: Wet models of KB ~R ~S ~W R ~S ~W ~R S ~W R S ~W R S W R ~S W ~R S W ~R ~S W Figure 1. The 8 possible worlds for Rain (R), Sprinkler (S) and Wet (W). Every world where the KB is true (green) is also a world where Wet is true, so KB entails Wet. The more the KB says, the smaller its region, and the more it entails.

The simplest way to check entailment is model checking: enumerate the truth table and look at the rows where is true. For example, take

Of the 8 rows for , and , the is true in 3, and is true in all 3. So : we do not know why the ground is wet, but we know it is.

A useful fact connects entailment to validity: exactly when the single sentence is valid. That is how the lab checks arguments.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Each example is written as "premises -> conclusion", so a valid result means the argument is sound in every possible world. Try this:

  1. Modus ponens, : valid. From "if P then Q" and "P", you may always conclude Q.
  2. Affirming the consequent, : only 3 of 4 rows. The false row is the counterexample: false, true. "If it rains the ground is wet; the ground is wet; so it rained" fails when the sprinkler was on.
  3. Type your own, for example rain -> wet or ~(P & Q) <-> (~P | ~Q) (one of De Morgan's laws), and check the verdict.

Going deeper

Inference rules: proofs instead of tables

Truth tables grow as : 20 propositions already mean about a million rows, and 300 would mean more rows than there are atoms in the observable universe. Inference rules derive new sentences directly from old ones, like steps in a proof:

  • Modus ponens: from and , infer .
  • And-elimination: from , infer .
  • Logical equivalences, such as De Morgan's laws, , used to rewrite sentences.

A set of rules is sound if it only derives entailed sentences, and complete if it can derive every entailed sentence. Finding a proof is itself a search problem ( Uninformed search: BFS, DFS, uniform cost ): states are sets of known sentences, actions are rule applications.

Resolution: one rule that is enough

Convert every sentence to conjunctive normal formConjunctive normal form: an AND of clauses, where each clause is an OR of literals (propositions or their negations). (CNF): an AND of clauses, each an OR of literals. Then a single rule, resolution, does all the work. From two clauses where one contains and the other , infer a clause with everything else from both:

Either is true, and then must be, or is false, and then must be. That is the "resolution" example in the lab. To prove , add to the clauses and resolve repeatedly. If you derive the empty clause, a contradiction, then is unsatisfiable, so must follow. This proof by contradiction is complete for propositional logic.

SAT solvers

Turn the question around: is there any model that makes a formula true? That is the SAT problemThe Boolean satisfiability problem: deciding whether some assignment of true and false makes a formula true. It is NP-complete, yet modern solvers handle huge industrial instances.. It was the first problem proved NP-complete, so no known algorithm is fast on every input. Yet modern SAT solvers routinely handle industrial formulas with millions of variables, because real problems have structure. They build on the DPLL algorithm:

dpll.pyruns with python3 (standard library)
# A tiny DPLL SAT solver. A formula in CNF is a list of clauses; each
# clause is a set of literals: "A" means A is true, "-A" means A is false.
def neg(lit):
    return lit[1:] if lit.startswith("-") else "-" + lit

def dpll(clauses, model, log):
    while True:                                  # unit propagation
        units = [next(iter(c)) for c in clauses if len(c) == 1]
        if not units:
            break
        lit = units[0]
        log.append(f"forced {lit}")
        model = model | {lit}
        clauses = [c - {neg(lit)} for c in clauses if lit not in c]
        if any(len(c) == 0 for c in clauses):
            log.append("conflict")
            return None
    if not clauses:
        return model                             # every clause satisfied
    lit = next(iter(sorted(clauses[0])))         # branch on a literal
    for choice in (lit, neg(lit)):
        log.append(f"guess {choice}")
        found = dpll(clauses + [{choice}], model, log)
        if found is not None:
            return found
    return None

PARTY = [
    {"A", "B"},       # invite Alice or Bob (or both)
    {"-A", "C"},      # if Alice comes, Carol comes
    {"-B", "-C"},     # Bob and Carol cannot both come
    {"-D", "B"},      # Dave comes only if Bob comes
    {"D"},            # Dave must come
    {"E", "F"},       # Eve or Frank...
    {"-E", "-F"},     # ...but not both
]
for extra in ([], [{"A"}]):                      # then insist on Alice
    log = []
    model = dpll(PARTY + extra, frozenset(), log)
    print("with Alice required:" if extra else "party rules:")
    print("    steps:", ", ".join(log))
    print("    model:", sorted(model) if model else "none, unsatisfiable")

Output

party rules:
    steps: forced D, forced B, forced -C, forced -A, guess E, forced E, forced -F
    model: ['-A', '-C', '-F', 'B', 'D', 'E']
with Alice required:
    steps: forced D, forced B, forced -C, forced -A, conflict
    model: none, unsatisfiable

DPLL is backtracking search from Constraint satisfaction problems with propagation. Unit propagation is the key: a clause with only one literal left forces that literal. Dave must come, so Bob must come, so Carol cannot, so Alice cannot. Only Eve and Frank need a genuine guess (the guess is added as a one-literal clause, so propagation then applies it). When Alice is also required, propagation alone finds the conflict and proves the rules unsatisfiable without any guessing.

Modern solvers add conflict-driven clause learningConflict-driven clause learning: when a SAT solver hits a conflict, it derives a new clause explaining it, so the same mistake is never repeated, and can jump back several levels at once. (CDCL): every conflict is analysed and summarised as a new clause, so the same combination is never tried again, and the search can jump back many levels at once.

Trade-offs

OptionWins whenLoses when
Truth tables (model checking) A handful of propositions; teaching; checking an argument by hand Doubles with every proposition: hopeless beyond a few dozen
Inference rules / resolution Proofs that explain why something follows; entailment without listing models Finding the right proof is a search; can be slow
SAT solvers (DPLL, CDCL) Large real problems: hardware verification, scheduling, dependency resolution Worst case is still exponential; encoding a problem as CNF takes care
First-order logic Knowledge about many objects and 'for all' statements Harder inference; some questions are undecidable

Common mistakes

  • Reading as "P causes Q", or thinking it is false when is false. It only promises Q when P holds.
  • Affirming the consequent: concluding P from and Q. The truth table shows the counterexample.
  • Confusing "satisfiable" with "valid". A satisfiable sentence can be true; a valid one must be.
  • Treating "not entailed" as "false". If neither nor is entailed, the KB simply does not know.
  • Expecting propositional logic to say "every customer". It has no objects or quantifiers; that is what First-order logic adds.

In the wild

Where you will see this: chip makers use SAT-based tools to check that hardware designs behave as specified before manufacturing. Package managers resolve dependency versions by turning "this needs that version range" into clauses for a SAT-style solver. Scheduling, test generation and parts of software verification are encoded as satisfiability problems, and SAT solvers sit inside SMT solvers, which add arithmetic and data structures and are widely used to find bugs in programs.

Check yourself

  1. When is P -> Q false?

    Show answer

    C. Only when P is true and Q is false An implication only breaks its promise when the condition holds and the conclusion does not.

  2. KB is true in 3 models, and alpha is true in 2 of those 3. Does KB entail alpha?

    Show answer

    B. No, because one model of KB makes alpha false Entailment requires alpha in every model of KB. A single counterexample is enough to break it; models where KB is false do not matter.

  3. From 'P or Q' and 'not P or R', what does resolution infer?

    Show answer

    C. Q or R Resolving on P removes P and not P and keeps everything else: Q or R.

  4. A formula has 30 propositions. Why not just use a truth table?

    Show answer

    B. It would have 2^30, about a billion, rows Each proposition doubles the rows. Proof methods and SAT solvers avoid listing every model.

  5. In DPLL, what does unit propagation do?

    Show answer

    B. Sets the only remaining literal in a one-literal clause, which can force others A clause with one literal left can only be satisfied one way, so that value is forced, often triggering a chain of further forced values.

Recap

  • Propositional logic combines true-or-false propositions with not, and, or, implies and iff.
  • A model assigns every proposition a value; a truth table lists all 2^n models.
  • KB entails alpha when alpha is true in every model of KB; model checking tests this directly.
  • Inference rules and resolution prove entailment without listing models; proof by contradiction derives the empty clause.
  • SAT solvers (DPLL with unit propagation, plus clause learning) decide huge formulas in practice.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy