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.