Propositional Logic – Comprehensive Study Notes

Propositions

• Declarative sentences that are unequivocally TRUE (T) or FALSE (F) – never both.
  • Examples judged as propositions
  • “Kuala Lumpur is the capital of Malaysia.” → $T$
  • “Superman can fly.” → truth‐value context–dependent; formally treated as a proposition.
  • $1+5=9$ → $F$
  • “Tuesday is the day after Wednesday.” → $F$
  • Non-propositions (commands, open statements, questions, etc.)
  • “Please sit down.” (imperative)
  • “$x+1=2$” (contains free variable)
  • “What time is it?” (question)
• Truth‐value operator
  • Notation $[[p]]$ returns the truth value of proposition $p$.
  • $T$ abbreviates TRUE, $F$ abbreviates FALSE.

Truth Values & Notation

• Long propositions are symbolised by lowercase letters $p,q,r,s,\dots$
  • Example: $p$: “CMA6124 is a compulsory subject for Finance majors at MMU.”
  • $q$: “You are sitting in this class to learn mathematical logic.”
  • We write $[[p]]$, $[[q]]$ for their truth values.

Compound Propositions & Logical Connectives

Compound proposition = combination of ≥2 simple propositions using logical operators.

• Four fundamental connectives + two derived ones
  1. Negation $\lnot$ (“not”)
  2. Conjunction $\land$ (“and”)
  3. Disjunction $\lor$ (“or”, inclusive)
  4. Implication $\rightarrow$ (“if … then”)
  5. Biconditional $\leftrightarrow$ (“iff”, derived)
  6. Exclusive–or $\oplus$ (derived)
• Truth tables precisely describe how truth values propagate through connectives.

Negation (¬)

• Truth table
  • $p$ $\lnot p$
  • $T\;\;\;F$
  • $F\;\;\;T$
• Example
  • $p$: “It is sunny.”
  • $\lnot p$: “It is not sunny.” — true exactly when $p$ is false.

Conjunction (∧)

• Truth table
  
  \begin{array}{|c|c|c|}
  \hline p&q&p\land q\\hline
  T&T&T\ T&F&F\ F&T&F\ F&F&F\\hline
  \end{array}
  
• Example: $p$: “Today is Tuesday”, $q$: “It is raining today”
  • $p\land q$: “Today is Tuesday and it is raining today.” Truth only when both clauses are true.

Disjunction (∨)

• Truth table
  
  \begin{array}{|c|c|c|}\hline
  p&q&p\lor q\\hline
  T&T&T\ T&F&T\ F&T&T\ F&F&F\\hline
  \end{array}
  
• Example: $p$: “Mary likes jogging.” $q$: “Mary likes dancing.”
  • $p\lor q$: “Mary likes jogging or dancing.” False only if Mary likes neither.

Implication (→)

• Truth table
  
  \begin{array}{|c|c|c|}\hline
  p&q&p\rightarrow q\\hline
  T&T&T\ T&F&F\ F&T&T\ F&F&T\\hline
  \end{array}
  
• Linguistic equivalents: “$p$ implies $q$”, “$p$ only if $q$”, “$p$ sufficient for $q$”, “$q$ necessary for $p$”, “$q$ when/whenever $p$”.
• Example: $p$: “It is sunny.”, $q$: “We go to the beach.”
  • Statement false only in the scenario $p=T,q=F$ (sunny but we do not go).

Biconditional (↔) & Exclusive–or (⊕)

• Definitions
  • $p\leftrightarrow q\equiv (p\rightarrow q)\land(q\rightarrow p)$
  • $p\oplus q\equiv \lnot(p\leftrightarrow q)$
• Truth table snippet
  
  \begin{array}{|c|c|c|c|}\hline
  p&q&p\leftrightarrow q&p\oplus q\\hline
  T&T&T&F\ T&F&F&T\ F&T&F&T\ F&F&T&F\\hline
  \end{array}
  
• English for $p\leftrightarrow q$: “$p$ iff $q$”, “$p$ is necessary and sufficient for $q$”.

Translating English ↔ Propositional Logic

• Given example block (rain/sun/clouds):
  • $p$: It is raining; $q$: The sun is shining; $r$: There are clouds.
  • a) “If it is raining, then the sun is not shining and there are clouds.” → $p\rightarrow(\lnot q\land r)$
  • b) “If the sun is shining or there are no clouds, then it is not raining.” → $(q\lor\lnot r)\rightarrow \lnot p$
  • c) “The sun is shining iff it is not raining.” → $q\leftrightarrow \lnot p$
  • d) “If there are no clouds, then it is not raining and the sun is shining.” → $\lnot r\rightarrow(\lnot p\land q)$
• Reverse translation example (Monday / raining / hot):
  • $\lnot p\rightarrow(q\lor r)$ → “If today is not Monday, then it is raining or hot.”
  • $\lnot(p\lor q)\leftrightarrow r$ → “It is not the case that today is Monday or raining iff it is hot.”
  • $p\land(q\lor r)\rightarrow r\lor(q\lor p)$ → “Today is Monday and (raining or hot) implies that it is hot or raining or today is Monday.”

Truth Tables

• Mechanical method to compute full semantics of a compound formula.
• Example truth table for $(p\rightarrow q)\land(r\lor\lnot q)$ shown on slide 14.
• Precedence rules (highest → lowest):
  1. Parentheses $(\ )$
  2. Negation $\lnot$
  3. Conjunction $\land$
  4. Disjunction $\lor$
  5. Implication $\rightarrow$
  6. Biconditional $\leftrightarrow$
  • Exercise: add parentheses to $p\leftrightarrow q\land\lnot r\lor s$ ⇒ $p\leftrightarrow((q\land\lnot r)\lor s)$

Converse, Inverse, Contrapositive

Given $p\rightarrow q$

• Converse: $q\rightarrow p$
• Inverse: $\lnot p\rightarrow \lnot q$
• Contrapositive: $\lnot q\rightarrow \lnot p$
• Truth‐table property: $p\rightarrow q$ is logically equivalent to its contrapositive, but not to its inverse or converse.

Tautology, Contradiction, Contingency

• Tautology: always $T$ (e.g. $p\lor\lnot p$).
• Contradiction: always $F$ (e.g. $p\land\lnot p$).
• Contingency: sometimes $T$, sometimes $F$ (e.g. $p\lor q$).
• Slide 19 provides illustrative truth tables.

Logical Equivalence

• $p$ and $q$ are logically equivalent if $p\leftrightarrow q$ is a tautology.
  • Denoted $p\equiv q$, $p\Leftrightarrow q$, or $p\Longleftrightarrow q$.
• Demonstrations
  • Truth-table method (slide 22): $(p\lor q)\land q \equiv q$.
  • Algebraic method using equivalence laws (slide 23): $\lnot(p\lor q)\lor(\lnot p\land q)\equiv\lnot p$.

Catalogue of Equivalence Laws (slide 24)

• Identity, Domination, Idempotent, Double-negation, Commutative, Associative, Distributive, De Morgan, Implication conversion, Biconditional conversion, Contrapositive, Absorption, Negation.
• Emphasises ability to transform complex statements systematically.

Worked Law-Based Proofs

• Prove $p\rightarrow(q\rightarrow r)\equiv q\rightarrow(p\rightarrow r)$ via chain of replacements (slide 25).
• Show tautology of $p\land(\lnot p\lor q)\leftrightarrow(p\land q)$ (slide 26) – critical for simplifying logical conditions in programming/specification.

Summary of Lecture Concepts

• Definition & examples of propositions.
• Compound propositions and six logical connectives.
• Construction & interpretation of truth tables.
• Translation between natural language and propositional formulas.
• Converse, inverse, contrapositive notions and their equivalence relations.
• Classification into tautology / contradiction / contingency.
• Operator precedence conventions.
• Logical equivalence, truth-table verification, and algebraic proof using equivalence laws.

Supplementary Exercises (selected)

• Syntax check: identify malformed formulas, e.g. “(p → q)(→ r ∨ ¬q)” lacks connective between parenthetical groups.
• Truth-value evaluation given $[[p]]=T, [[q]]=F, [[r]]=T$: compute
  1. $[[p\land(q\lor r)]]$
  2. $[[\lnot(p\oplus q)\rightarrow(p\leftrightarrow q)]]$
  3. $[[\lnot p\land q]]$
• Construct the full truth table for $p\rightarrow q\land r\lor\lnot q$ (be mindful of precedence).
• Translation & manipulation with health/wealth/wise predicates; derive converse/inverse/contrapositive.
• Classify each formula as tautology/contingency/contradiction.
• Fill-in-the-blanks to recall specific laws (conversion, De Morgan, distributive, contrapositive, etc.).
• Prove $[\lnot(\lnot p\rightarrow q)\lor p]\equiv p\lor\lnot q$ by (a) truth table & (b) equivalence laws.

Practical/Real-World Relevance

• Digital circuit design: conjunction ↔ AND-gate, disjunction ↔ OR-gate, negation ↔ NOT-gate.
• Software specification & verification: implications capture pre-/post-conditions; tautologies assure invariant truths.
• Database query optimisation: equivalence laws parallel relational algebra rewrites.
• AI rule systems: contrapositive allows backward chaining; exclusive-or models mutually-exclusive conditions.
• Ethical reasoning: clear separation of truth values prevents equivocation; helps analyse argument validity.

Foundational Connections

• Forms basis for Predicate Logic (next topic) by adding quantifiers $\forall,\exists$.
• Probability & discrete structures: logical events correspond to sets; $\lor$ maps to union, $\land$ to intersection, $\lnot$ to complement.
• Set identities mirror logical equivalences (De Morgan between sets & logic).

Operator Precedence Reference (re-listed)

$( )\;>\;\lnot\;>\;\land\;>\;\lor\;>\;\rightarrow\;>\;\leftrightarrow$

Key Takeaways

• Master truth tables for mechanical certainty.
• Learn key equivalence laws – they dramatically shorten proofs and simplify conditions.
• Remember: implication ≡ contrapositive; biconditional captures equality of truth.
• Evaluate real English statements carefully: OR is inclusive unless explicitly exclusive.
• Practise translating both directions to reinforce comprehension.