Martynas

chapter 18 - slide 16 onwards
logical algebra
P ∧ Q ⊨ P
(P∧Q)→ P - tautology
⊨(P∧Q)→ P
valid arguments can be turned into tautological conditionals
ent- ⊨
nent- ⊭
a1…an ⊨ γ ≈ ⊨ a1∧…∧an → γ

a1…an ⊨ β → γ
a1…an ∧ β ⊨ γ - deduction theorem

α → β, α ⊨ β
α → β ⊨ α → β
⊨(α→β)→(α→β)

α ≈ β
if and only if
⊨ α ↔ β ≈ α → β ∧ β → α

slide 19 is important

Chapter 20-22 - PL proofs - syntax

syntactic notion of validity - there exists a derivation with premises a1..an and end with γ
we choose Fitch-style natural deduction proof system
⊢ - syntactic validity

Fitch system - 11 rules:

• 8 introduction and elimination rules
• 1 special rules
• 2 rules that makes life easier (not strictly necessary)

1. ∧ Introduction: From P and Q, conclude P ∧ Q.
2. ∧ Elimination: From P ∧ Q, conclude P or Q.
3. ∨ Introduction: From P, conclude P ∨ Q.
4. ∨ Elimination: From P ∨ Q, P → R, and Q → R, conclude R.
5. → Introduction: From assuming P leads to Q, conclude P → Q.
6. → Elimination (Modus Ponens): From P → Q and P, conclude Q.
7. ¬ Introduction: If assuming P leads to ⊥, conclude ¬P.
8. ¬ Elimination: If assuming ¬P leads to ⊥, conclude P.
9. ↔ Introduction: From P → Q and Q → P, conclude P ↔ Q.
10. ↔ Elimination: From P ↔ Q, conclude P → Q and Q → P.
11. ⊥ Introduction/Elimination: From P and ¬P, conclude ⊥; from ⊥, conclude any Q.

up to slide 9