Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Propositional logic and inference

Clear, exam-focused study notes on propositional logic and inference: definitions, laws, CNF conversion, resolution, soundness/completeness, worked exam-style proofs and common errors.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Propositional logic is the basic language for representing yes/no facts and rules in knowledge-based systems and parts of AI such as rule engines, expert systems and some steps in planning. An engineer uses these ideas to check whether a set of rules implies a conclusion, to simplify logical conditions in hardware/firmware, and to implement automated inference like forward/backward chaining and SAT-based checks.

Key ideas

Start with plain language and small building blocks.

  • Proposition: a sentence that is either true or false (for example, "It is raining"). We represent atomic propositions by symbols like P, Q, R.

  • Formula (or well-formed formula): a valid expression built from proposition symbols and connectives (¬, ∧, ∨, ⇒, ⇔) according to grammar rules.

  • Literal: either an atomic proposition P (a positive literal) or its negation ¬P (a negative literal).

  • Clause: a disjunction (OR) of literals. Example clause: (¬P ∨ Q ∨ R). A Horn clause has at most one positive literal; Horn KBs support linear-time forward/backward chaining, and unit resolution is complete for Horn clauses.

  • Conjunctive Normal Form (CNF): a conjunction (AND) of clauses. Every propositional formula can be transformed to a logically equivalent CNF by standard rewriting; alternatively, using definitional CNF (Tseitin transformation) yields an equisatisfiable CNF of linear size, useful for SAT solvers and resolution.

  • Model: an assignment of truth values to all atomic propositions. A model satisfies (makes true) a formula if the formula evaluates to true under that assignment.

  • Satisfiable / Unsatisfiable: a formula is satisfiable if it has at least one model; unsatisfiable if no model makes it true.

  • Tautology: a formula true in every model (e.g., P ∨ ¬P).

  • Entailment (semantic consequence): We write KB |= α to mean: in every model where all formulas in the knowledge base KB are true, α is also true. This is a semantic notion (about models).

  • Inference (syntactic consequence): We write KB ⊢ α to mean: there is a finite sequence of applications of inference rules (a proof) from KB that derives α. Inference is a syntactic proof concept.

  • Soundness: An inference procedure is sound if whenever KB ⊢ α, then KB |= α. (No false conclusions.)

  • Completeness: An inference procedure is complete if whenever KB |= α, then KB ⊢ α. (It can derive every logical consequence.)

  • Modus Ponens (an inference rule): From P and (P ⇒ Q) infer Q. This is a basic sound rule.

  • Resolution rule (for clauses): From (A ∨ l) and (B ∨ ¬l) infer (A ∨ B), where l is a literal and A,B are (possibly empty) disjunctions of literals. Resolution is used in refutation proofs: to show KB |= α, add ¬α to KB, convert to CNF, and derive the empty clause (contradiction).

Exact statements universities expect:

  • Definition (Entailment): KB |= α iff for every model m, if m satisfies KB then m satisfies α.

  • Soundness theorem (general): For any inference system S, S is sound if for all KB and α, KB ⊢_S α implies KB |= α. (Assume standard truth-table semantics.)

  • Completeness theorem for propositional resolution (refutation-completeness): If a set of propositional clauses is unsatisfiable, resolution will derive the empty clause after finite applications of the resolution rule. (Assumption: finite clause set; standard propositional semantics.)

Derivations commonly asked (example: CNF conversion). Step-by-step method to convert any formula to CNF (equivalent without new symbols; equisatisfiable if using Tseitin renaming):

  1. Eliminate biconditionals: replace (A ⇔ B) by ((A ⇒ B) ∧ (B ⇒ A)).
  2. Eliminate implications: replace (A ⇒ B) by (¬A ∨ B).
  3. Move negation inward using De Morgan until it applies only to atoms: ¬(A ∧ B) -> (¬A ∨ ¬B); ¬(A ∨ B) -> (¬A ∧ ¬B); ¬¬A -> A.
  4. Distribute OR over AND to get a conjunction of disjunctions: use distributive laws: (A ∨ (B ∧ C)) -> ((A ∨ B) ∧ (A ∨ C)) and ((A ∧ B) ∨ C) -> ((A ∨ C) ∧ (B ∨ C)). Repeat until in CNF. Optionally, to avoid exponential blow-up, use definitional CNF (Tseitin) by introducing fresh symbols for subformulas; this yields an equisatisfiable CNF.

What to draw for truth-table proofs: draw a table with one column per atomic proposition, additional columns for each subformula used in the derivation, and a final column for the formula being tested. Label the top headers with symbol names (e.g., P, Q, P ⇒ Q, etc.). Fill rows for all 2^n truth assignments.

What to draw for resolution proof: write each clause on its own line, numbered. When you resolve two clauses, write the resolvent and its parent clause numbers in parentheses, until you derive the empty clause (write an empty box or the symbol ⊥ and list parents).

Assumptions to state in answers: classical two-valued semantics (no probabilities), finite propositional vocabulary unless otherwise noted.

Formulas

¬ means logical NOT (negation). ∧ means logical AND (conjunction). ∨ means logical OR (disjunction). ⇒ means implication (material implication). ⇔ means biconditional (equivalence). KB |= α means every model that satisfies KB satisfies α (entailment). KB ⊢ α means α is syntactically derivable from KB using the chosen inference rules. (A ∨ l), (B ∨ ¬l) ⊢_resolve (A ∨ B) resolution rule: from these two clauses infer (A ∨ B). P, (P ⇒ Q) ⊢ Q Modus Ponens rule: from P and (P ⇒ Q) infer Q.

(Each symbol above: no SI units apply — these are logical symbols used in propositional logic. Use where binary truth values true/false apply.)

Worked examples

Example 1 — Basic entailment by truth table. Question (model-answer style): Show that (P ∧ (P ⇒ Q)) |= Q by truth table. Answer steps:

  1. Identify atomic propositions: P, Q. Draw table with 4 rows for (P,Q). Columns headers: P | Q | P ⇒ Q | P ∧ (P ⇒ Q) | Conclusion Q.
  2. Fill rows:
    • Row 1: P=T, Q=T: P⇒Q = T, P∧(P⇒Q)=T, Q=T.
    • Row 2: P=T, Q=F: P⇒Q = F, P∧(P⇒Q)=F, Q=F.
    • Row 3: P=F, Q=T: P⇒Q = T, P∧(P⇒Q)=F, Q=T.
    • Row 4: P=F, Q=F: P⇒Q = T, P∧(P⇒Q)=F, Q=F.
  3. Check every row where P∧(P⇒Q) is true: only row 1, and there Q is true. So every model of the left side makes Q true. Therefore entailment holds. Final statement (bold): (P ∧ (P ⇒ Q)) |= Q.

Example 2 — CNF conversion and resolution refutation. Question: Prove (P ⇒ Q), (Q ⇒ R), P |= R using CNF + resolution. Model answer steps:

  1. Convert premises and negated goal to clauses.
    • P ⇒ Q is ¬P ∨ Q. Clause C1: (¬P ∨ Q).
    • Q ⇒ R is ¬Q ∨ R. Clause C2: (¬Q ∨ R).
    • P is unit clause C3: (P).
    • To use refutation, add ¬R as C4: (¬R).
  2. Write clauses numbered:
    1. (¬P ∨ Q)
    2. (¬Q ∨ R)
    3. (P)
    4. (¬R)
  3. Resolve: from (3) P and (1) (¬P ∨ Q) resolve on P to get (Q). Call it 5: (Q) (parents 3,1).
  4. Resolve (5) (Q) with (2) (¬Q ∨ R) on Q to get (R). Call it 6: (R) (parents 5,2).
  5. Resolve (6) (R) with (4) (¬R) on R to get empty clause ⊥ (contradiction). Call it 7: ⊥ (parents 6,4).
  6. Since we derived contradiction from premises plus ¬R, the original KB entails R. Final statement (bold): (P ⇒ Q), (Q ⇒ R), P |= R (proved by resolution).

Example 3 — Show equivalence using laws (short derivation question). Question: Prove that (P ⇒ Q) is logically equivalent to (¬P ∨ Q). Model answer steps:

  1. Start from definition of implication: A ⇒ B is defined as ¬A ∨ B in propositional calculus (material implication). This is a standard logical equivalence.
  2. To show formally, build truth table with columns P, Q, P ⇒ Q, ¬P ∨ Q and verify all rows match. Final statement: (P ⇒ Q) ⇔ (¬P ∨ Q).

Common mistakes

  • Using resolution directly on formulas instead of first converting to CNF clauses.
  • Confusing satisfiability with validity (tautology): a formula can be satisfiable without being a tautology.
  • Saying KB ⊢ α implies α is true in all models without specifying KB; soundness requires the inference system to be sound.
  • Dropping parentheses or precedence errors: implication has lower precedence than ∨ and ∧ in many conventions—always use parentheses in answers.
  • Forgetting to include ¬α when doing refutation proof for entailment.

For your exam

Typical question types:

  • Definitions (e.g., define clause, CNF, model, entailment). Full marks: correct definition plus a short example.
  • Short notes (e.g., describe resolution). Full marks: definition, rule form, and an example of a resolution step.
  • Derivations/proofs (e.g., convert given formula to CNF). Full marks: show each CNF conversion step (eliminate ⇔, ⇒, push negation, distribute) with intermediate formulas.
  • Proofs of entailment (truth-table, semantic argument, or resolution refutation). Full marks: choose suitable method; for truth table show full table if small, for resolution show clauses, numbered resolvents, and final empty clause.
  • Diagrams: truth-table or resolution proof graph. Full marks: properly labelled table or numbered clauses with parent references.

Always state assumptions (classical 2-valued logic) and whether you use semantic (truth table/models) or syntactic (proof/resolution) method.

Quick check

  1. What is a clause? Give an example.
  2. State Modus Ponens in symbolic form.
  3. Why do we add ¬α when proving KB |= α using resolution? Answers: 1) A clause is a disjunction of literals, e.g. (¬P ∨ Q ∨ R). 2) From P and (P ⇒ Q) infer Q; formally: P, (P ⇒ Q) ⊢ Q. 3) We add ¬α to the KB and attempt to derive contradiction (empty clause); if contradiction follows, α is entailed because KB ∧ ¬α is unsatisfiable.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?