CS 201 - 11/20/14 Rule of Modus Tollens: Given: p->q (p implies q) ~q (q is not true) :. ~p (p is not true) Assume there is a course in which the student who gets the highest grade on the final exam will get an A in the class p = Student X got the highest grade on the final q = Student X got an A in the class In this class the implication of p->q exists Student X did not get an A: ~q From this we can infer, Student X did not get the highest grade on the final exam: ~p =============================== Note: ~ is the NOT symbol ^ is the AND symbol v is the OR symbol -> is the IMPLIES symbol :. Therefore ======================================= Rule of Modus Ponens Given: p->q (p implies q) p (p is true) :. q (q is true) =========================================== Rule of Modus Tollens: Given: p->q (p implies q) ~q (q is not true) :. ~p (p is not true) =========================================== Rule of Conjuction: Given: p q :. p ^ q (p AND q are true) ==================================== Rule of Generalization Given: p :. p v q Alternatively Given: q :. p V q ================================== Rule of Specification Given: p ^ q :. p Alternatively Given: p ^ q :. q ======================================= Rule of Elimination Given: p V q ~q :. p Alternatively Given: p v q ~p :. q ======================================== Rule of Transitivity Given: p -> q q -> r :. p -> r ======================================= Proof by Division into Cases Given: p v q p -> r q -> r :. r ======================================= Condtradiction Rule Given: ~p -> contradiction (always false) :. p ========================================= p = I go to the movies q = I will finish my homework r = I will do well on the exam Given: p -> ~q ~q -> ~r Infer: p -> ~r by Rule of Transivity