Transcript lecture slides

F22H1
Logic and Proof
Week 6
Reasoning
How can we show that this is a tautology (section 11.2):
The hard way: “logical calculation”
The “easy” way: “reasoning”
That’s what chapter 11 is all about:
Logical Calculation: use well defined rules one by one and you will
slowly get towards the thing that you are trying to prove.
Reasoning: (logical calculation, but with a few hints, tips and
additional rules) is more like common sense.
Of course, we can do a truth table to show that this is always T –
however you can’t do that with, e.g., 100 logical variables. So we
need to learn reasoning.
We start with this.
Why?? Because Lemma 7.3.4. Says this:
So, if our calculation eventually gets to “P => R”, using steps
that are either
or
then we will have proved what we want to prove
This is the next step:
Understand? Next:
Tricky! But straightforward
Next this:
Understand it? Also known as False-elimination.
Next, we can go a long way with rules from chap 7:
Actually this only uses AND-weakening
The remainder is fairly quick and easy:
So from Lemma 7.3.4. We have now proved the tautology we
wanted to prove.
Koyaanasqatsi
A brand new dawn …
Let’s just assume, for the time being, that the whole first bit is true
{Assumption}
(1)
Now let’s make another assumption:
{Assumption}
2) P
{from (1) and (2)}
3) Q
{from (1) and (3)}
4) R
{we assumed P (2) and derived R (4), this means:}
5) P => R
{We assumed (1), and got (5), this means:}
6)
Inference
This is the general rule for inference:
You can be creative about when to make an inference and what
to base it on, but of course it has to be valid.
Some valid inference rules
{Tautology}
(1)
P  P
{Implication and double negation}
(2)
P  P
{Follows from (1) and (2) – called   introduction}
(3) ( P  P )  (P  P )
{Assume}
(1) P  Q
…
{follows from (1) --   eliminatio n
(m) P
{follows from (1) and (m) if there are no assumptions between (1)
and (m) that the derivation of (m) relies on --  introduction
(m+1) P  Q  P
Reasoning by Contradiction
This is an extremely useful inference rule, very often used, often
called reductio ad absurdum
The idea is: assume the negation of what you want to prove –
If reasoning then leads to a contradiction (i.e. leads to False), then
you can infer (i.e. you have proved) the negation of your assumption.
{Assume}
(1) P
… {via valid inferences but no other assumptions we get …}
(m) False
{it follows that the original assumption must be False, so
we can infer the following}
(m+1) P
E.g. Let’s prove that 10 is an even number.
To do this by Contradiction, we first assume that
“10 is even” is False:
{Assumption}
(1) 10 is an odd number
{this follows from (1)
(2) 10 = 2k + 1 for some k in N
{this follows from (2), by simple algebra}
(3) 9 = 2k for some k in N
{simple algebra, follows from (3)}
(4) k = 4.5 and k in N
{This follows from (4), since it is a contradiction}
(5) False
{We have now proved this, via proof by contradiction}
(6) 10 is an even number
Prove that this: ( x  5)  ( y  4)  ( x  6)
Implies:
( x  100)
It stands to reason, when you look at it. Let’s prove it by contradiction
{Assume}
(1) (( x  5)  ( y  4)  ( x  6)  ( x  100))
{ Implication}
(2) ((( x  5)  ( y  4)  ( x  6))  ( x  100))
{De Morgan, double negation, and associativity}
(3) ( x  5)  ( y  4)  ( x  6)  ( x  100)
{follows from (3) by AND-elimination, twice}
(4) ( x  5)  ( x  100)
{we can see that (4) is a contradiction, so we have proved this:
( x  5)  ( y  4)  ( x  6)  ( x  100)
(5)