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