Definition
"If it is raining, the ground is wet. The ground is not wet. So…?" You conclude it is not raining, without looking at the sky. Can a computer reason like that, with certainty?
Propositional logic is a formal language for statements that are either true or false, called propositions, combined with connectives: NOT (¬), AND (∧), OR (∨), IMPLIES (→) and IF AND ONLY IF (↔). A knowledge base is a set of such sentences, and inference derives new sentences that must be true whenever the knowledge base is true, using truth tables or rules such as modus ponens.
In simple words
Think of switches that are on or off. "Raining" is one switch; "ground wet" is another. Rules connect them, such as "if raining is on, ground wet must be on". Logic works out which switches must be on or off, given the rules and what you know.
Overview
- Propositional logic reasons with statements that are either true or false, called propositions.
- Connectives combine them: NOT (¬), AND (∧), OR (∨), IMPLIES (→) and IF AND ONLY IF (↔).
- A truth table lists the value of a formula for every combination of truth values.
- A knowledge base entails a sentence if the sentence is true in every world where the knowledge base is true.
- Inference rules such as modus ponens derive new facts mechanically.
- SAT solvers decide whether huge propositional formulas can be satisfied and are used in chip verification and scheduling.
Why it matters
Logic was the foundation of early AI and remains essential wherever conclusions must be guaranteed: verifying chip designs and software, configuring products, checking rules and building systems that must explain their reasoning exactly.
Key terms
- Proposition
- A statement that is either true or false, such as "it is raining".
- Connective
- An operator combining propositions: ¬, ∧, ∨, → and ↔.
- Truth table
- A table listing a sentence's truth value for every combination of its propositions.
- Entailment
- KB ⊨ α: α is true in every world where the knowledge base is true.
- Modus ponens
- From P → Q and P, conclude Q.
- Satisfiability (SAT)
- Whether some assignment of true/false values makes a sentence true.
Types
Propositional logic has several types of connective and of sentence, and several inference methods. These are the essentials.
1. Logical connectives
The operators NOT, AND, OR, IMPLIES and IFF that build compound sentences.
- How it works: P ∧ Q is true only when both are true; P ∨ Q when at least one is; P → Q is false only when P is true and Q false; P ↔ Q when both match.
- Example: "If it rains (R), the match is cancelled (C)": R → C.
- When to use it: Use them to write rules precisely; the implication's truth table is the one beginners most often get wrong.
2. Tautologies, contradictions and contingent sentences
Tautologies are always true, contradictions always false, and contingent sentences depend on the facts.
- How it works: A truth table shows which: a tautology has T in every row, a contradiction F in every row.
- Example: P ∨ ¬P is a tautology; P ∧ ¬P is a contradiction; P ∧ Q is contingent.
- When to use it: Use them to check whether rules are always valid or whether a knowledge base contains a contradiction.
3. Inference rules
Patterns that derive a true conclusion from true premises: modus ponens, modus tollens, and-elimination and resolution.
- How it works: Modus ponens: from P → Q and P, conclude Q; modus tollens: from P → Q and ¬Q, conclude ¬P.
- Example: "If the alarm rings, there is smoke" and "the alarm rings" give "there is smoke".
- When to use it: Use them to build chains of reasoning in rule-based systems.
4. Normal forms (CNF and DNF)
Standard shapes for formulas: conjunctive normal form is an AND of ORs; disjunctive normal form is an OR of ANDs.
- How it works: Any formula can be rewritten into CNF using equivalences such as De Morgan's laws and distribution.
- Example: P → Q becomes ¬P ∨ Q; (A ∨ B) ∧ (¬B ∨ C) is already in CNF.
- When to use it: Use CNF as the input format for resolution and SAT solvers.
5. Proof methods: model checking, resolution and chaining
Ways to decide entailment: checking every model, deriving a contradiction by resolution, or forward and backward chaining.
- How it works: Model checking enumerates truth assignments (2ⁿ of them); resolution proves KB ⊨ α by showing KB ∧ ¬α is unsatisfiable; chaining works on Horn clauses in linear time.
- Example: Forward chaining in a medical rule base from symptoms to possible diagnoses.
- When to use it: Use chaining for rule-based expert systems and SAT solvers for large combinatorial problems.
Explained in detail
The connectives
| P | Q | ¬P | P ∧ Q | P ∨ Q | P → Q |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
The implication P → Q surprises people: it is false only when P is true and Q is false. "If it rains, the match is cancelled" is not broken on a dry day, whatever happens to the match. OR is inclusive in logic: P ∨ Q is true when both are true. These precise meanings are what allow mechanical reasoning, and the rules were set out by George Boole in his 1854 book The Laws of Thought, the origin of the Boolean logic inside every computer.
Inference
A knowledge base entails a sentence if the sentence is true in every possible world where the knowledge base is true. The simplest way to check is model checking: list every combination of truth values, which a truth table does, and confirm. With n propositions there are 2ⁿ rows, which grows quickly. Inference rules are faster: modus ponens says from "P → Q" and "P", conclude "Q"; modus tollens says from "P → Q" and "¬Q", conclude "¬P", exactly the rain argument at the top of this page. Resolution, a single rule that combines clauses, is complete for propositional logic and underlies automated theorem provers.
SAT solvers
- Satisfiability asks whether any assignment makes a sentence true. It was the first problem proved NP-complete, by Stephen Cook in 1971, so no known algorithm solves every case quickly.
- Yet modern SAT solvers routinely handle problems with millions of variables, using clever search and learning from conflicts.
- They verify that microprocessor designs are correct, find bugs in software, plan schedules and even solve hard mathematical questions.
- Many CSPs can be translated into SAT and solved this way.
Limits
Propositional logic cannot talk about objects in general. To say "every student who passes all subjects is promoted" you would need a separate proposition for every student. It also cannot express degrees of belief: a statement is fully true or fully false. The next page introduces first-order logic, which adds objects and quantifiers, and later pages handle uncertainty with probability and vagueness with fuzzy logic.
How it works
- Choose propositions for the basic facts.
- Write the rules as sentences with connectives.
- Add the facts you observe.
- Infer conclusions with truth tables for small cases or rules such as modus ponens.
- For large problems, hand the sentences to a SAT solver.
In code
from itertools import product
implies = lambda p, q: (not p) or q
# Knowledge base: Rain -> Wet, Sprinkler -> Wet, and we observe: not Wet
def kb(rain, sprinkler, wet):
return implies(rain, wet) and implies(sprinkler, wet) and (not wet)
def entails(query):
worlds = [w for w in product([True, False], repeat=3) if kb(*w)]
return all(query(*w) for w in worlds), worlds
print("Rain | Sprinkler | Wet | KB true?")
for rain, sprinkler, wet in product([True, False], repeat=3):
print(f"{rain!s:>5} | {sprinkler!s:>9} | {wet!s:>4} | {kb(rain, sprinkler, wet)}")
ok, worlds = entails(lambda rain, sprinkler, wet: not rain)
print("KB entails 'not Rain'?", ok, " (worlds where KB holds:", worlds, ")")Output
Rain | Sprinkler | Wet | KB true? True | True | True | False True | True | False | False True | False | True | False True | False | False | False False | True | True | False False | True | False | False False | False | True | False False | False | False | True KB entails 'not Rain'? True (worlds where KB holds: [(False, False, False)] )
Try it yourself
The dry ground
A rule-based garden assistant knows: "If it rains, the soil is wet" and "If the sprinkler ran, the soil is wet".
Match the connective to its meaning
What does each say?
- ¬P
- P ∧ Q
- P ∨ Q
- P → Q
Common mistakes
- Reversing an implication: concluding P from P → Q and Q.
- Treating OR as exclusive.
- Using propositional logic where facts are uncertain.
Check yourself
Summary
- Propositional logic combines true/false statements with connectives.
- Entailment means true in every world where the knowledge base holds; truth tables and rules such as modus ponens check it.
- SAT solvers scale logic to huge problems, but propositional logic cannot express general rules about objects.
Read it. Now try it yourself.
Open the interactive activityFinished reading?
Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · Stanford Encyclopedia of Philosophy: Classical Logic