Lecture 5
Propositional Logic Part 1
UGED1111 LOGIC 2023/23 SUMMER TERM
DR. ARTHUR CHIN
1
Is the argument valid?
• That Peter does 100 push-ups and 100 sit-ups everyday
are jointly sufficient for him to be a super-hero, provided
that he drinks Yakult everyday. Peter is not a super-hero
despite drinking Yakult everyday. It follows that he
neither does 100 push-ups nor 100 sit-ups everyday.
2
Propositional Logic
• Formal logic (形式邏輯)
▪ Purpose: Facilitate the identification of argument form, and
through this, the determination of validity
▪ Consist of a set of symbols with precise rules specifying:
1) how to construct grammatical sentences out of them
(syntax);
2) how to interpret the meanings of such sentences
(semantics); and
3) how to construct proofs (natural deduction).
• Propositional logic (PL) (命題邏輯): elementary system
of formal logic
3
Syntax
4
Symbols
1) Propositional letters (命題字母) (“P”, “Q”, “R”, etc.) for
translating simple propositions
• Simple proposition =df A proposition that does not contain any
logical connective
2) Logical Connectives (邏輯連接詞)
(2.1) Negation “~” (2.2) Conjunction “&”
(2.3) Disjunction “v” (2.4) Material Implication/Conditional “→”
(2.5) Biconditional “↔”
3) Brackets (“(“, “)”)
5
Syntax: 1
• Well-formed formula (WFF) (完構式) in PL are
grammatical expressions formed according to the
following rules of syntax:
1) All propositional letters are WFFs.
2) If p is a WFF, then ~p is a WFF.
3) If p and q are WFFs, then (p & q), (p v q), (p → q), (p ↔
q) are also WFFs.
4) Nothing else is a WFF.
6
Syntax: 2
• Scope (範圍) of a connective =df The shortest WFF
containing that connective
• Main connective (主連接詞) =df The connective in a
WFF with the widest scope
▪ “(~ (P & Q) v (R → S))”
▪ Main connective determines the kind of WFF it is:
negation, conjunction, or conditional, etc.
7
5 Kinds of Compound Proposition
Negation ~A / ~ (P →Q)
Conjunction (K & L) / ((P v Q) & ~G)
Disjunction (P v Q) / ((T → U) v ~(Y ↔ Z))
Material Implication (P → Q) / ((A v B) → ~ (C & D))
(Material
conditional)
Biconditional (P ↔ T) / (~(B v D) ↔ (A & C))
Class Exercise Q1 and Q2 (UReply)
8
Propositional Form
Proposition Propositional
Form
Negation ~A / ~ (P →Q) ~p
Conjunction (K & L) / ((P v Q) & ~G) (p & q)
Disjunction (P v Q) / ((T → U) v ~(Y ↔ Z)) (p v q)
Material Implication (P → Q) / ((A v B) → ~ (C & D)) (p → q)
(Material conditional)
Biconditional (P ↔ T) / (~(B v D) ↔ (A & C)) (p ↔ q)
• Propositional variables (命題變量; “p”, “q”, “r”, etc.) stand for
any proposition (simple or compound)
9
Semantics
10
Semantics
• Meaning of a PL WFF is defined by its truth table
• Truth table (真值表) shows how the truth value of a
proposition, or a propositional form, can be calculated
merely by looking at the truth values of its components
11
Truth Table of Negation (否定句): 1
• ~: “it is not the case that” p ~p
T F
F T
12
Truth Table of Negation (否定句): 2
P: All soldiers are brave.
Q: All soldiers are strong.
P ~P
• It is not the case that all T F
soldiers are brave.
F T
• It is not true (both) that all (P & Q) ~ (P & Q)
soldiers are brave and all T F
are strong.
F T
13
Truth Table of Negation (否定句): 3
• Is this formalization correct? Explain your answer in
terms of contradictories.
• Peter: All soldiers are brave. P
• Mary: I disagree: no soldiers are brave. ~P
14
Truth Table of Conjunction (合取句)
• &: “and”
p q (p & q)
T T
T F
F T
F F
15
Truth Table of Disjunction (析取句): 1
• v: “or” p q (p v q)
T T
T F
F T
F F
16
Truth Table of Disjunction (析取句): 2
How to translate “Biden or Trump won the Presidential
Election in 2020”?
Translation scheme
P: Biden won the Presidential Election in 2020.
Q: Trump won the Presidential Election in 2020.
17
Truth Table of Material Conditional (質料條件句)
• →: “If…then…”
p q (p → q)
T T
• “If you get an A in T F
Midterm, then you will get F T
an A in this course.”
F F
P: You get an A in
Midterm.
Q: You will get an A in this • p: antecedent (前項)
course. • q: consequent (後項)
18
Truth Table of Biconditional (雙條件句)
• ↔: “if and only if”
p q ((p → q) & (q → p)) (p ↔ q)
T T
T F
F T
F F
19
Truth Functionality
• PL connectives are truth-functional (真值函項連詞) =df
Truth values of statements formed by using these
connectives are determined entirely by the truth values
of its component statements.
20
T or F?
1) If "(P v Q)" is true, then either "P” is false or "Q" is
false.
2) If "(P & Q)" is false, then "P" is false and "Q" is also
false.
3) Whenever "(P v Q)" is true, "(Q → P)" is also true.
21
Drawing Complex Truth Tables
Step 1: In region 2, write down WFF Region 1 Region 2
Step 2: In region 1, list all Region 3 Region 4
propositional letters
Step 3: In region 3, list all possible
assignments of the truth values (真值
賦予) of propositional letters stated
in region 1
Step 4: In region 4, determine the Draw the complete truth
truth value of the WFF, starting with table of “(~ (P v Q) → R)”.
the shortest component WFF, then
the second shortest…
22
P Q R (~ (P v Q) → R)
Class Exercise Q5.2
Hurley (2018) Ex.6.2 III Q12, 18 and 20 (p.352)
23
Use of Brackets
• Every occurrence of 2-place connective must be accompanied by a pair
of brackets to avoid ambiguity
• “(P & Q → R)” P Q R ((P & Q) → R) (P & (Q → R))
T T T T T
T T F F F
T F T T T
T F F T T
F T T T F
F T F T F
F F T T F
F F F T F
24
Putting Truth Table to Use
25
Truth Table
• Useful for:
1) determining the logical status of a single proposition
(tautology; inconsistent; contingent)
2) determining the logical relationships between
propositions ((in)consistency; contraries;
subcontraries; contradictories; entailment; logical
strength)
3) determining the validity of a deductive argument
26
Single Proposition: Tautology
• Tautological proposition (恆真命題) =df Proposition that is
true regardless of the truth values of its component
propositions
P (P v ~P)
T T
F T
P Q (( ~P → Q) v ~P))
T T T
T F T
F T T
F F T
27
Single Proposition: Inconsistency
• Inconsistent proposition (不一致命題) =df Proposition that is
false regardless of the truth values of its component
propositions
P (P & ~P)
T F
F F
P Q (P & ~(P v Q))
T T F
T F F
F T F
F F F
28
Single Proposition: Contingency
• Contingent proposition (適真命題) =df Proposition with at
least 1 true assignment and at least 1 false assignment.
P P Q (P → Q)
T T T T
F T F F
F T T
F F T
Class Exercise: Q6.1-6.2 (UReply)
Hurley (2018) Ex.I Q1-5 p.361
29
Relation b/w Propositions:
Consistency 1
• Consistent set of propositions =df There exists at least 1
assignment in the truth table where all propositions are
true. Otherwise the set is inconsistent.
• Is the following set consistent: [(P v ~Q), (P & Q)]?
P Q (P v ~Q) (P & Q)
T T T T
T F T F
F T F F
F F T F
30
Relation b/w Propositions:
Consistency 2
• Is the following set consistent: [(P & Q), ~ (P v Q)]?
P Q (P & Q) ~ (P v Q)
T T T F
T F F F
F T F F
F F F T
Do Class Exercise Q8
31
Relation b/w Propositions:
Entailment
• Set [p, q, r] entails s =df There is no assignment in the
truth table where all members of the set [p, q, r] are all
true while s is false at the same time
❑[p, q, r] entails s: “p, q, r ⊧ s”
❑[p, q, r] does not entail s: “p, q, r ⊭ s”
• Use truth table method to determine whether:
❑ (P→Q) ⊧ (~P→~Q)
❑ (P→Q) ⊧ (~Q→~P)
32
• “(P → Q)” ⊧ “(~P → ~Q)”?
P Q (P → Q) (~P → ~Q)
T T T
T F F
F T T
F F T
33
• “(P → Q)” ⊧ “(~Q → ~P)”?
P Q (P → Q) (~Q → ~P)
T T T T
T F F F
F T T T
F F T T
34
Relation b/w Propositions:
Logical Equivalence
• p and q are logically equivalent =df (1) p ⊧ q and (2) q
⊧ p.
▪ (P & Q) (Q & P)
▪ (P v Q) (Q v P)
▪ ~(P & Q) (~P v ~Q) (De Morgan’s Law)
▪ ~(P v Q) (~P & ~Q) (De Morgan’s Law)
▪ (P → Q) (~P v Q) (Material Implication)
▪ (P → Q) (~Q → ~P) (Contraposition)
▪ (P ↔ Q) ((P → Q) & (Q → P))
35
Exercise
• Translate the following into logically equivalent WFFs by
performing the stated operations in sequence. Note
there can be more than one correct answer.
1) *((P v Q) → R) (First, material implication; second, De
Morgan’s Law)
2) (~(P & ~Q) → (Q → ~R)) (First, contraposition; second,
material implication; third, De Morgan’s Law)
3) (~P v (Q v (R → ~S))) (First, material implication;
second, contraposition; third, De Morgan’s Law)
36
Readings
• *Hurley (2018): Chapter 6 “Propositional Logic” pp.316-
350 (answers for selected questions on Blackboard)
• Particularly relevant exercise on logical status of
propositions: Ex. 6.3 I and II pp.361-362
37
