MATH0050 Logic
Table of Contents
Section A: Common questions & additional notes
Chapter 1 Language
Chapter 2: Propositional Logic
Chapter 3: First Order Predicate Logic
Chapter 4: Computability
Section B: List of definitions and proofs
Chapter 1 Language
Chapter 2 Propositional Logic
Chapter 3 First Order Predicate Logic
Chapter 4 Computability
Section C: Definitions and proofs
Chapter 1, 2 & 4: Definitions & proofs (handwritten)
Comparison: Chapter 1 vs Chapter 2
Comparison: Chapter 2 (Syntactic vs Semantic)
Comparison: Chapter 2 vs Chapter 3
,Section A: Common questions & additional notes
Chapter 1 Language
1. Calculate degree & weight
Degree Weight
Variable symbol 0 -1
n-ary predicate symbol 0 n-1
¬ Add 1 0
⇒ Add 2 +1
Ɐ Add 1 +1
2. Determine whether if it is a formula / Determine if string is an element of L
Defining properties of
formulae
Check weight 1. If weight ≠ -1 then conclude not formula
2. If weight = -1, need to check with definition of “formula”
Proper initial segment Check cumulative weight and see if we reach a negative weight before
the string ends
3. Covert into a formula in L
αvβ “or” (¬α) ⇒ β If does not have α, we must
have β
α˄β “and” ¬ (α ⇒ (¬β)) Not possible to have α and
not have β
α⇔β “if and only if” (α ⇒ β) ˄ (β ⇒ α)
Ǝxα Exists x such that α is satisfied ¬ Ɐx¬ α Not possible that for all x, α
is not satisfied
, 4. Semantic equivalent vs Semantic tableau vs Truth table
Convert into formula in L Semantic tableaux
Truth table
(semantically equivalent)
αvβ (¬α) ⇒ β
α β αvβ
0 0 0
1 0 1
0 1 1
1 1 1
α˄β ¬ (α ⇒ (¬β))
α β α˄β
0 0 0
1 0 0
0 1 0
1 1 1
α⇔β (α ⇒ β) ˄ (β ⇒ α)
α β α⇔β
0 0 1
1 0 0
0 1 0
1 1 1
Ǝxα ¬ Ɐx¬ α N/A N/A
α⇒β N/A
α β α⇒β
0 0 1
1 0 0
0 1 1
1 1 1
¬¬ α N/A
α ¬α ¬¬ α
0 1 0
1 0 1
,Chapter 2: Propositional Logic
1. Use semantic tableaux method to prove if semantic implication holds / tautology
Question Solution
(note the position of the ⊨ symbol)
Semantic We form a semantic tableau starting from
implication the propositions:
*3 separate propositions
Semantic We form a semantic tableau starting from
implication /
tautology
If there are open branches, must describe every valuation which it fails to hold:
By considering the open branch, we may describe a type of valuation v for which the given proposition fails to
be true. For a valuation v, if v(α)=0/1, v(β)=0/1 and v(γ)=0/1, then v(……) = 0
2. Use truth table to prove tautology
“The column corresponds to π contains only ones”
3. Direct proof for syntactic implication
a. α ⇒ α
b. ¬¬ α ⇒ α (use α ⇒ α as ‘assumed’)
c. α ⇒ ¬¬ α (use ¬¬ α ⇒ α as ‘assumed)
4. Use deduction theorem to prove syntactic implication
“By Deduction theorem, it suffices to give a proof of … “
“A further application of deduction theorem indicates that it suffices to give a proof of…”
5. Some theorems that you can assume
a. ¬¬ α ⇒ α
b. α ⇒ ¬¬ α
c. α ⇒ α
6. Axioms:
a. Axiom 1: want to add something in front of β
b. Axiom 3: change of negations
c. Modus ponens: cancel something in front of β
, Chapter 3: First Order Predicate Logic
1. Describe a theory
Π and Ω Sentences
Graphs Π = {∼}
Ω=φ
Graphs Π = {∼ , =}
(when add equality Ω=φ Add:
symbol) Reflexibity, symmetry,
transistivity
(about the = sign)
Substituvity sentences
(interaction of = and ~ )
Posets Π = { = , ≤}
Ω=φ
About the ≤ sign
Reflexibity,
symmetry,
transistivity
(about the = sign)
Substituvity sentences
(interaction of = and ≤)
Groups Π={=}
Ω={.,E}
About the . and E
Reflexibity, symmetry,
transistivity
(about the = sign)
Substituvity sentences
(interaction of = and . )
