CS 201 - 11/18/14
Logic - proof of arguments
Arguments:
Given some starting conditions/statement
(these are assumed to be true)
We need to get to a particular conclusion
We use the logical Rules of Inference to get from
the starting conditions to the conclusion
This information is taken from The Discrete Math
book by Epp, Susanna http://condor.depaul.edu/sepp/DMwA4e.htm
Rule of Transivity
p -> q
q -> r
:. p -> r
The proof for the above relies on the follow:
Given:
p -> q
p
Can we show the q is also exists when both of
the above conditions exist?
p q | p->q p && p->q
-------|--------------------
Line 0 0 0 | 1 0
Line 1 0 1 | 1 0
Line 2 1 0 | 0 0
Line 3 1 1 | 1 1
Do all lines that have a true value for the
statement (p && p->q) also have a true value
for q?
Yes, For the above this is the case. Line 3
is the only line where (p && p->q) is true.
On line 3, q is also true.
Note: q may be true in other instances, but
we don't care about that in this
case. We get to ignore Lines 0-2
since (p && p->q) are false on those
lines.
Now let us look at the Truth Tables for
Given: p->q q->r
Can we imply p->r?
p q r | p->r | p->q q->r (p->q && q->r)
----------|-----------------------------------
0 0 0 | 1 | 1 1 1
0 0 1 | 1 | 1 1 1
0 1 0 | 1 | 1 0 0
0 1 1 | 1 | 1 1 1
1 0 0 | 0 | 0 1 0
1 0 1 | 1 | 0 1 0
1 1 0 | 0 | 1 0 0
1 1 1 | 1 | 1 1 1
For the true lines of the statement (p->q && q->r),
is p->r also true on these lines?
For all line where (p->q && q->r) is true, is
the value of p-r also true?
Since the truth table shows the above questions
to be correct, then the inference is also correct.
Given: p->q q->r
:. p->r
Consider the statements:
p: The team scores more points than its oppenent.
q: The team wins a game.
r: The team is happy.
The above is the Rule of Transitity.
The Rule of Inference of Modus Ponens:
Given: p->q
p
:. q