Module 1: Propositional Logic & Basic Reasoning¶

Table of Contents¶

Overview
Source File Mapping
Core Concepts
1.1 Language & Semantics
1.2 Truth Tables
1.3 Validity & Proof Methods
Practice Problem Analysis
Summary & Connection to Next Module

Overview¶

This module develops three key skills: - Understanding the syntax and semantics of propositional logic. - Mastering construction and analysis of truth tables for formulas. - Applying basic proof methods, including semantic and syntactic approaches.

Prerequisites: None
Recommended for: Beginners or those reviewing fundamentals.

Source File Mapping¶

Content Area	Key Topics	Handout	Transcript	Practice
Language & Semantics	Syntax, semantics, definitions	Part_1_Introduction_handout.pdf (pp. 1–4)	COMP304_521-Lecture-1_Zi-Mu-_English-United-Kingdom.txt (L1–60)	1_Propositional_Logic_Exercises.pdf (Q1–Q3)
Truth Tables	Evaluation, procedure	Part_2_Prop_logic_syntax_semantics_handout.pdf (pp. 1–3)	COMP304_521-Lecture-2_Zi-Mu-_English-United-Kingdom.txt (L1–40)	1_Propositional_Logic_Exercises_with_solutions.pdf (all)
Validity & Proof	Validity, proof strategies	Part_3_Prop_logic_proof_validty_and_proofs_handout.pdf (pp. 1–6)	COMP304_521-Lecture-2_Zi-Mu-_English-United-Kingdom.txt (L41–80)	1_Propositional_Logic_Exercises.pdf (Q4–Q7)

⚠️ Transcripts offer additional clarifications and real-world examples. Any discrepancies between handout and transcript are flagged below with ⚠️ notation.

Core Concepts¶

1.1 Language & Semantics¶

Formal Definition¶

From slides (pp. 1–2):

A proposition is a declarative statement that is either true or false (never both).

Syntax: Formulas of propositional logic are constructed inductively from:
Atomic propositions (propositional variables): \(p, q, r, \ldots\)
Logical connectives:
- Negation (\(\lnot\)): unary operator
- Conjunction (\(\land\)): binary operator (AND)
- Disjunction (\(\lor\)): binary operator (OR)
- Implication (\(\rightarrow\)): binary operator (IF...THEN)
- Biconditional (\(\leftrightarrow\)): binary operator (IF AND ONLY IF)
Parentheses for grouping
Semantics: An interpretation \(I\) assigns each atomic proposition a truth value in \(\{\text{True}, \text{False}\}\). The truth value of a compound formula is determined recursively by the truth values of its parts and the semantic rules of the connectives.

Lecture Insight¶

From transcript (L5–25):

The instructor emphasizes: - Only statements with a definite truth value qualify as propositions—not questions, commands, or open expressions. - Atomic propositions represent minimal facts, concerned purely with truth or falsity, not linguistic meaning. - Compound formulas can be parsed structurally, which is crucial for formal reasoning and avoiding ambiguity. - The structure of a formula (its syntax) is distinct from what it means (its semantics).

⚠️ Common Confusion¶

Transcript Q&A (L35–45):

⚠️ Mistake: Treating non-declarative statements (questions like "What time is it?", commands like "Close the door!") as propositions.
Correction: Only sentences that can be true or false are propositions. Questions and commands lack truth values, so they are not propositions.

Example: - "Today is Monday." — Proposition (can be True or False) - "Is it raining?" — NOT a proposition (question, no definite truth value) - "Please sit down." — NOT a proposition (command, no truth value)

Key Takeaways¶

Propositions are truth-valued declaratives only.
Syntax defines the structure of formulas; semantics assigns truth values to that structure.
Atomic propositions are the basic building blocks; compounds are recursive combinations.

1.2 Truth Tables¶

Step-by-Step Procedure¶

From handout (pp. 1–3):

Identify all atomic propositions in the formula (e.g., \(p\), \(q\), \(r\)).
Generate all possible truth assignments:
For \(n\) distinct variables, there are \(2^n\) rows.
Example: For \(p, q\), create \(2^2 = 4\) rows (all combinations: TT, TF, FT, FF).
Calculate subformulas column by column, row by row, using these semantic rules:
\(\lnot p\) is True iff \(p\) is False.
\(p \land q\) is True iff both \(p\) and \(q\) are True.
\(p \lor q\) is True iff at least one of \(p, q\) is True.
\(p \rightarrow q\) is False only when \(p\) is True and \(q\) is False (otherwise True).
\(p \leftrightarrow q\) is True iff \(p\) and \(q\) have the same truth value.

In-Class Example¶

Transcript (L15–30):

Formula: \((p \rightarrow q) \land (\lnot p \lor q)\)

Truth Table:

\(p\)	\(q\)	\(p \rightarrow q\)	\(\lnot p\)	\(\lnot p \lor q\)	\((p \rightarrow q) \land (\lnot p \lor q)\)
T	T	T	F	T	T
T	F	F	F	F	F
F	T	T	T	T	T
F	F	T	T	T	T

Analysis: The formula is false only in the second row (when \(p = \text{True}\) and \(q = \text{False}\)).

Tips & Pitfalls¶

Transcript (L28–38):

Use separate columns for each subformula to avoid errors.
Implication (\(p \rightarrow q\)) is only false if true implies false; many students wrongly assume it means "if and only if."
Biconditional (\(p \leftrightarrow q\)) is stricter than implication; both sides must have the same truth value.
Always verify row count: \(n\) variables require exactly \(2^n\) rows.
Parentheses matter: \(p \lor q \land r\) ≠ \((p \lor q) \land r\); follow standard operator precedence or use explicit parentheses.

Key Takeaways¶

Create a separate column for each subformula to maintain clarity.
Implication is only false when the antecedent is true and consequent is false.
Truth tables exhaustively check validity and equivalence.
Always verify row counts and operator precedence.

1.3 Validity & Proof Methods¶

Criteria for Validity¶

From handout (pp. 3–5):

A formula \(\varphi\) is valid (also called a tautology) if and only if it is true under every possible interpretation—equivalently, every row of its truth table shows True in the final column.

Formal definition:
\(\models \varphi\) (read: "entails \(\varphi\)") iff for all interpretations \(I\), \(I(\varphi) = \text{True}\).

Related concepts: - Satisfiable: A formula is satisfiable if it is true in at least one interpretation. - Contingent: A formula is contingent if it is true in some interpretations but false in others. - Unsatisfiable (contradiction): A formula is unsatisfiable if it is false in every interpretation.

Method Comparison¶

From transcript (L42–65):

Method	Approach	Strengths	Limitations
Truth Tables	Enumerate all \(2^n\) cases	Complete, exhaustive, visual	Exponential growth; impractical for many variables
Proof Systems	Apply formal inference rules	Systematic, scalable	Requires training; depends on system choice
Semantic Analysis	Reason about structure directly	Insightful; may reveal redundancy	Prone to human error

Transcript insight (L50–65): "Truth tables are fundamental for understanding logic but impractical beyond 4–5 variables. Proof systems (introduced in Module 2) offer scalable alternatives."

Representative Cases¶

From handout examples (pp. 4–5) and transcript (L23–40):

Case 1: Valid formula
\(\varphi = (p \lor q) \rightarrow (q \lor p)\)

Truth table (abbreviated):

\(p\)	\(q\)	Result
T	T	T
T	F	T
F	T	T
F	F	T

Conclusion: All rows are True, so \(\varphi\) is valid.

Case 2: Invalid (contingent) formula
\(\psi = p \rightarrow q\)

Truth table (abbreviated):

\(p\)	\(q\)	Result
T	T	T
T	F	F
F	T	T
F	F	T

Conclusion: Not all rows are True (row 2 is False), so \(\psi\) is not valid (but is satisfiable—true in rows 1, 3, 4).

⚠️ Common Errors¶

Transcript Q&A (L68–75):

⚠️ Error 1: Confusing tautology with satisfiability. A tautology is true in all cases; a satisfiable formula need only be true in at least one case.

⚠️ Error 2: Miscounting rows or misapplying truth rules for connectives. Always double-check: - Implication: only false when \(\text{True} \rightarrow \text{False}\). - Disjunction: true if either side is true.

⚠️ Error 3: Neglecting parentheses, leading to mis-parsed formulas and incorrect validity judgments.

Key Takeaways¶

Valid formulas are true in every interpretation; check by examining all truth-table rows.
Truth tables provide an exhaustive (if computationally expensive) method for validity checking.
Distinguish: validity (all True), satisfiability (at least one True), unsatisfiability (all False).
Proof systems, introduced in Module 2, provide an alternative, often more efficient, approach.

Practice Problem Analysis¶

Annotated problems with difficulty ratings and lecture cross-references:

Difficulty Key¶

⭐ Fundamental: Tests basic comprehension of syntax, simple truth tables, or core definitions.
⭐⭐ Intermediate: Requires careful truth-table construction, handling multiple variables, or proof intuition.
⭐⭐⭐ Advanced: Multi-step reasoning, complex formulas, or deeper conceptual grasp.

Annotated Problems¶

From 1_Propositional_Logic_Exercises.pdf:

Q1.1 ⭐ (Fundamental; cf. [§1.1])
"Which of the following are well-formed formulas (WFFs)?"
Tests understanding of syntax rules.
Lecture support: Transcript L5–15.
Q1.2 ⭐ (Fundamental; cf. [§1.2])
"Make a truth table for the XOR connective."
Introduces truth-table methodology.
Solution approach: Follow the step-by-step procedure in [§1.2].
Q1.3 ⭐⭐ (Intermediate; cf. [§1.2])
"Make truth tables for: (a) \((p \rightarrow q) \leftrightarrow p\), (b) \((p \land \lnot p) \rightarrow p\), etc."
Applies multiple connectives; tests careful row construction.
Common pitfall: Confusing implication and biconditional (Transcript L35–40).
Q1.5 ⭐⭐ (Intermediate; cf. [§1.3])
"Use truth tables to show which formulas are valid: (a) \(p \rightarrow (q \rightarrow p)\), (b) \(p \rightarrow (p \rightarrow q)\), etc."
Directly applies validity criterion from [§1.3].
Key skill: Identifying whether all rows are True (valid) or not (invalid).
Q1.6 ⭐⭐ (Intermediate; cf. [§1.3])
"Show which entailment relations hold, e.g., \(\{\lnot q, p \rightarrow q\} \models \lnot p\)."
Tests semantic entailment (requires truth-table reasoning).
Method: Show the conclusion is true whenever all premises are true.

Error Pattern Summary¶

Common Mistakes (from Transcript and Exercise Solutions):

Forgetting row counts:
Failing to generate all \(2^n\) rows for \(n\) variables, leading to incomplete validity checks.
Implication confusion:
Treating \(p \rightarrow q\) as equivalent to \(p \leftrightarrow q\) or misapplying the "false only when \(\text{True} \rightarrow \text{False}\)" rule.
Parenthesis neglect:
Misinterpreting \(p \lor q \land r\) as \((p \lor q) \land r\) instead of the correct \(p \lor (q \land r)\) (standard precedence: \(\lnot > \land > \lor > \rightarrow > \leftrightarrow\)).
Confusing satisfiability with validity:
Declaring a formula "valid" when it is merely satisfiable (true in some, not all, rows).
Calculation errors in complex formulas:
Rushing through subformula columns and introducing arithmetic/logical mistakes.

Summary & Connection to Next Module¶

Summary¶

This module establishes the rigorous foundation for formal logic study by: - Defining the language of propositional logic with precise syntax and semantics. - Mastering truth tables, the fundamental tool for evaluating formulas and checking validity. - Understanding validity as the central concept for logical consequence.

These skills are not merely academic; they train rigorous, systematic thinking essential for all subsequent logical systems (modal logic, description logic, epistemic logic).

Connection to Next Module: Proof Systems¶

While truth tables provide a complete method for checking validity, they are computationally expensive for formulas with many variables. Module 2: Proof Systems & Modal Logic introduces: - Natural deduction and Hilbert systems, which offer syntactic (rule-based) alternatives to semantic (truth-table) approaches. - System K, the foundational proof system for modal logic, which extends propositional reasoning to handle necessity and possibility. - The key insight: Soundness and completeness theorems that guarantee proof systems yield exactly the valid formulas.

Bridge concept: Where Module 1 asks "Is \(\varphi\) true in all interpretations?", Module 2 asks "Can we derive \(\varphi\) from the axioms using inference rules?"—and demonstrates these questions have the same answer.

Appendix: Symbol Quick Reference¶

Symbol	Name	Meaning	Example
\(\lnot\)	Negation	NOT	\(\lnot p\) = not p
\(\land\)	Conjunction	AND	\(p \land q\) = p and q
\(\lor\)	Disjunction	OR	\(p \lor q\) = p or q
\(\rightarrow\)	Implication	IF...THEN	\(p \rightarrow q\) = if p then q
\(\leftrightarrow\)	Biconditional	IF AND ONLY IF	\(p \leftrightarrow q\) = p iff q
\(\models\)	Entails	"implies" (semantic)	\(\Phi \models \varphi\)
\(\vdash\)	Proves	"derives" (syntactic)	\(\Phi \vdash \varphi\)
\(\top\)	True	Tautology	Always true
\(\bot\)	False	Contradiction	Always false

References¶

Lecture Slides: Part_1, Part_2, Part_3 (Propositional Logic Handouts)
Lecture Transcripts: COMP304_521-Lecture-1, Lecture-2 (full English transcripts)
Exercise Sets: 1_Propositional_Logic_Exercises.pdf, 1_Propositional_Logic_Exercises_with_solutions.pdf
Next Module: Part_10, Part_11, Part_12 (Modal Logic & Proof Systems Handouts)

Last Updated: 2025-11-24
Module Status: Ready for Review & Publication
Next Step: Proceed to Module 2: Proof Systems & Modal Logic Introduction