Session 2: Propositional Logic

Overview

Propositional logic from syntax to semantics: what a formula is, what it means, and how to move between the two.

Lecturer

Kevin Abou Rousse

Session Information

• Date and Time: Thursday 24 September 2026 — 17:30-19:30
• Place: (to be announced)
• Online Meeting Link
• Session Recording

Core Concepts

• Connectives (¬, ∧, ∨, →, ↔), precedence, and parenthesization
• Syntax vs semantics: formulas as objects, valuations as meaning, and the ⊨ relation
• Truth tables; tautology, contradiction, satisfiability, and validity
• Logical equivalences: De Morgan, distribution, contraposition, and p → q ≡ ¬p ∨ q
• Overview of common truth tables
• Normal forms (CNF/DNF); SAT stated as a problem

Slides

Session 2 Slides: Download PDF

Readings

• Logic in Computer Science (Huth & Ryan), Ch. 1.1, 1.3
• The Open Logic Project, Ch. 7

Exercises & Extra Steps

• Practice (not collected): prove (p → q) → ((q → r) → (p → r)) is a tautology, first by truth table and then by equivalences
• Practice (not collected): convert ¬((p ∧ q) → (r ∨ ¬s)) to CNF

Navigation

• ← Previous: S1: Why Our Code Breaks (and What a Proof Is)
• Back to Course Overview
• Next: S3: Rules of Inference & Natural Deduction →

Questions? Reach out on the course WhatsApp!