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