Hoofdstuk 5:
A proof of a (true) statement is a demonstration of its validity which contains sufficient detail to
convince someone that the statement is true. Statements which are provable are called theorems.
Recap:
- syntax describes what terms are well-formed;
- semantics describes the meaning of terms (or in the context of logic, what statements are
true);
We defined the syntax of propositional logic:
- T and F are a propositions;
- an atomic propositional variable, such as P and Q
- if p is a proposition, so is ¬p
- if p and q are propositions, so are p ∧ q, p ∨ q, p ⇒ q, and p ⇔ q
This fixes the language that we consider. We can rule out non-sensical terms such as ∧p(∨¬) – but it
doesn’t tell us what the meaning is of a formula such as p ∨ q ⇒ p.
The semantics of propositional logic is given by truth tables. We defined truth tables for all the
operators, such as ∧ and ⇒, and showed how to use these to write a truth table for any syntactically
valid formula in propositional logic.
Theorem Let A, B, and C be sets. Then A ⊆ C ∧ B ⊆ C ⇒ A ∪ B ⊆ C. If we unfold the definition of
subsets and translate this statement to predicate logic, this gives rise to a sizeable formula:
∀A ∀B ∀C ((∀a (a ∈ A ⇒ a ∈ C))∧(∀b (b ∈ B ⇒ b ∈ C)) ⇒ (∀x (x ∈ A∪B ⇒ x ∈ C)))
How should we go about proving this? We could draw a Venn diagram to convince ourselves that
this is true – but let’s look at what a written proof looks like.
Proof:
- Suppose A ⊆ C and B ⊆ C. We must show A ∪ B ⊆ C. By definition of set inclusion, this
amounts to proving:
- ∀x x ∈ A ∪ B ⇒ x ∈ C
- Let x be some element of A ∪ B. We need to show that x ∈ C.
- From x ∈ A ∪ B, we know that either x ∈ A or x ∈ B:
o if x ∈ A, we know that x ∈ C by our assumption that A ⊆ C
o if x ∈ B, we know that x ∈ C by our assumption that B ⊆ C
Hence, we can conclude that x ∈ C as required.
There are different proof strategies or proof templates that can be used to write such formal proofs.
Typically, there will be two proof strategies for each such logical operator and quantifier:
1. a introduction strategy tells you how to prove a goal of the form “example: p ∧ q”
2. a elimination strategy tells you how to use an assumption of the form
To find a proof, you: 1. write down all you assumptions and apply elimination strategies. 2. write
down the conclusion you wish to prove and use introduction strategies. By repeating these two
steps, the proof goals should get simpler – until the proof is finished.
, In the example prove, we showed that A ⊆ C ∧ B ⊆ C ⇒ A ∪ B ⊆ C in the following fashion:
General templates for prove strategies:
Implication Introduction: When I have to prove an implication which has the
form P => Q. We assume that P holds, and then we give a prove of Q. From
that we can conclude that P => Q. Example: We call a number a even if a = 2 ×
k for some number k. Theorem: The product of two even numbers is also
even. Question:
Make this statement precise and finish this proof. Be explicit about the proof
strategy used. Proof We need to show that if a and b are even, then so is a × b.
Assume a and b are even. By definition, we know a = 2 × n and b = 2 × m. The
product of a and b is (2 × n) × (2 × m). Using simple arithmetic, we can rewrite
this as: 2 × (2 × n × m). Therefore the product of a and b can be written in the
form 2 × k and is also even.
Implication elimination:
As part of the proof done earlier, we showed that if a ∈ A and A ⊆ C, we can
conclude that a ∈ C.
