Informally like equals sign for propositions

https://amyglen.wordpress.com

LECTURE 23

Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Mathematics	Lecture 23	1

Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Mathematics	Lecture 23	2

Recall: Logical Equivalence
Definition

Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Mathematics	Lecture 23	3

Since (p æ q) … (¬q æ ¬p), we could prove p æ q is true by showing that its contrapositive ¬q æ ¬p is true, and vice versa.

This method of proving a conditional proposition is called proof by contrapositive.

Chapter 7: Propositional Logic		6

I It appears to be more di�cult to deduce that n is odd by assuming p compared to showing that n2is even by assuming ¬q.

Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Mathematics	Lecture 23	6

Laws of Propositional Logic

For any propositions p, q, and r, the following laws hold. 1 Commutativity		Lecture 23	7




(a) p ‚ F … p (b) p · T … p
Dr Amy Glen (Murdoch University)	MAS162 – Foundations of Discrete Mathematics

Chapter 7: Propositional Logic		9

¬p ‚ ¬(p ‚ q) … ¬p.

[Working on the VOHP]

Chapter 7: Propositional Logic		10

Chapter 7: Propositional Logic		11

(p æ q) · (p æ ¬q) … ¬p. [Working on the VOHP]

We could also verify this logically equivalence by using a truth table to show that (p æ q) · (p æ ¬q) ¡ ¬p is a tautology.