Propositional Logic Handout PDF

IT1713 Proposition Defined Bases for Propositional Logic (http://www.the-philosopher.co.uk/lawsofthought.htm) · Law of Identity or “Logical Identity” · Law of Excluded Middle · Law of Non-Contradiction What is a Proposition? (http://cglab.snu.ac.kr/lectures/09-1/discrete_math/dm09_slide1...

IT1713 Proposition Defined Bases for Propositional Logic (http://www.the-philosopher.co.uk/lawsofthought.htm) · Law of Identity or “Logical Identity” · Law of Excluded Middle · Law of Non-Contradiction What is a Proposition? (http://cglab.snu.ac.kr/lectures/09-1/discrete_math/dm09_slide1-1.pdf) · It is a declarative sentence that is either false or true (NOT both) p False (F) or 0 True (T) or 1 Propositional Game (http://www.csee.umbc.edu/~artola/slides/Logic.ppt) · Elephants are bigger than mice. · 520 < 111 · y>5 · Today is January 1 and 99 < 5. · Please do not fall asleep. · If elephants were red, they could hide in cherry trees. · x < y if and only if y > x. Logical Connectives Compound Proposition (http://www2.lv.psu.edu/ojj/courses/discrete-math/topics/01logic.html) · It is a new proposition constructed by combining one (1) or more existing propositions · Negation (Ø or!) Venn Diagram: Truth Table: p Øp False (F) or 0 True (T) or 1 True (T) or 1 False (F) or 0 http://cglab.snu.ac.kr/lectures/09- 1/discrete_math/dm09_slide1-1.pdf http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- Connective_6.7.2012.pdf · Logical Conjunction (Ù) Truth Table: Venn Diagram: P q pÙ q False (F) or 0 False (F) or 0 False (F) or 0 False (F) or 0 True (T) or 1 False (F) or 0 True (T) or 1 False (F) or 0 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 http://cglab.snu.ac.kr/lectures/09- http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- 1/discrete_math/dm09_slide1-1.pdf Connective_6.7.2012.pdf 01 Handout 1 *Property of STI Page 1 of 5  IT1713 · Logical Disjunction (Ú) Truth Table: Venn Diagram: p q pÚ q False (F) or 0 False (F) or 0 False (F) or 0 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 True (T) or 1 http://cglab.snu.ac.kr/lectures/09- http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- 1/discrete_math/dm09_slide1-1.pdf Connective_6.7.2012.pdf · Implication (Þ or ®) Truth Table: Venn Diagram: p q p®q False (F) or 0 False (F) or 0 True (T) or 1 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 False (F) or 0 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 http://cglab.snu.ac.kr/lectures/09- http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- 1/discrete_math/dm09_slide1-1.pdf Connective_6.7.2012.pdf o Related Implications That Can Be Formed From p®q (http://www.sfponline.org/uploads/300/Inverse%20Converse%20&%20Contrapositive.doc) § Converse –p®q becomes q®p § Contrapositive – p®q becomes Øq®Øp § Inverse – p®q becomes Øp®Øq · Bi-conditional (Û or «) Truth Table: Venn Diagram: p q p«q False (F) or 0 False (F) or 0 True (T) or 1 False (F) or 0 True (T) or 1 False (F) or 0 True (T) or 1 False (F) or 0 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 http://cglab.snu.ac.kr/lectures/09- http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- 1/discrete_math/dm09_slide1-1.pdf Connective_6.7.2012.pdf · XOR or exclusive OR (Å) Truth Table: Venn Diagram: p q pÅq False (F) or 0 False (F) or 0 False (F) or 0 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 False (F) or 0 True (T) or 1 True (T) or 1 True (T) or 1 False (F) or 0 http://cglab.snu.ac.kr/lectures/09- http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- 1/discrete_math/dm09_slide1-1.pdf Connective_6.7.2012.pdf 01 Handout 1 *Property of STI Page 2 of 5  IT1713 · Practice Exercise o Express each of the proposition in an English sentence as negation of p, conjunction, disjunction, implication and bi-conditional (http://math.jhu.edu/~jpaschke/Extra%20Handouts/Working_with_Logic.pdf) § p: It is raining § q: I am indoors · Precedence of Logical Operators (http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- Connective_6.7.2012.pdf) Precedence level Operator 1 Negation (Ø or!) 2 Logical Conjunction (Ù) 3 Logical Disjunction (Ú) 4 Implication (Þ or ®) 5 Bi-conditional (Û or «) · Precedence of Logical Operators (O'Donnell, J., Hall, C. & Page, R., 2007) o Øp Ù q o Ø Øp o pÚqÙr o pÙqÙrÙs o pÙqÚrÚuÙv o pÙq®pÚq o p®q®r®s Tautology, Contradiction, Contingency, Logical Equivalence · Tautology – It is any statement that is TRUE regardless of the truth values of the constituent parts (http://www.uow.edu.au/~bmaloney/wuct121/LogicTeacher.pdf) Venn Diagram: http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical-Connective_6.7.2012.pdf · Example (http://people.math.gatech.edu/~ecroot/2406_2012/basic_logic.pdf) o Show by the use of the truth table (truth matrix) that the statement p Ú Øp is a tautology · Practice Exercise (Waner, S. & Costenoble, S. (1996)) o Show by the use of the truth table (truth matrix) that the statement (pÚq) Ú [(Øp) Ù ( Øq)] is a tautology · Contradiction – It is any statement that is FALSE regardless of the truth values of the constituent parts (http://www.uow.edu.au/~bmaloney/wuct121/LogicTeacher.pdf) Venn Diagram: http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical-Connective_6.7.2012.pdf 01 Handout 1 *Property of STI Page 3 of 5  IT1713 · Example (http://people.math.gatech.edu/~ecroot/2406_2012/basic_logic.pdf) o Show by the use of the truth table (truth matrix) that the statement p Ù Øp is a contradiction · Practice Exercise (Waner, S. & Costenoble, S. (1996)) o Show by the use of the truth table (truth matrix) that the statement (pÚq) Ù [( Øp)Ù( Øq)] is a contradiction · Contingency – It is any statement that is NEITHER a tautology NOR a contradiction (http://www.uow.edu.au/~bmaloney/wuct121/LogicTeacher.pdf) · Example o Show by the use of the truth table (truth matrix) that the statement p ® Ø p is a contingency (Cabero, J., Lopez, R., Salamat, L. & Sta. Maria, A. (2010)) · Logical Equivalence o These are two (2) different compound propositions that have EXACTLY the SAME/IDENTICAL truth value in every model (Orenstein, A. & Kotatko, P. (2000).) Negation/ Logical Logical Laws Implication/ Conjunction Disjunction Exportation (AND) Form (OR) Form Identity pÙT ≡ p pÚF ≡ p Commutative pÙq ≡ qÙp pÚq ≡ qÚp pÙ(qÙr) ≡ pÚ(qÚr) ≡ Associative (pÙq)Ùr (pÚq)Úr pÙ(qÚr) ≡ pÚ(qÙr) ≡ Distributive (pÙq) Ú (pÚq) Ù (pÙr) (pÚr) Complement/ p Ù Øp ≡ F p Ú Øp ≡ T Negation Idempotency p∧p≡p p∨p≡p Zero (0) and one pÙF ≡ F pÚT ≡ T (1)/Domination Involution p ≡ ØØp /Double Negation Ø (p ∧ q) ≡ Ø (p ∨ q) ≡ De Morgan's Øp ∨ Øq Øp ∧ Øq Absorption or p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) ≡ Redundancy p p p®q≡ Implication Øp∨q Exportation (aka (p ∧ q) ® r ≡ Currying) p ® (q ® r) Table 1 Replacement Rules (http://www.cs.arizona.edu/people/mccann/handouts/equivalences.pdf) 01 Handout 1 *Property of STI Page 4 of 5  IT1713 · Example o Show by the use of the truth table (truth matrix) that the two (2) compound propositions p ≡ Ø Øp are logically equivalent (Cabero, J., Lopez, R., Salamat, L. & Sta. Maria, A. (2010)) o Show by the use of replacement rules that the two (2) compound propositions Ø (p ∨ (Øp ∧ q) ≡ Ø p ∧ Øq are logically equivalent (http://www.fatih.edu.tr/~bkokluce/Abstract%20Mathematics/Logical%20Equivalence.pdf) · Practice Exercise (Cabero, J., Lopez, R., Salamat, L. & Sta. Maria, A. (2010)) o Show by the use of replacement rules that the two (2) compound propositions below are logically equivalent § p®q≡Øq®Øp § (Ø p ∧ q) ∧ (q ® p) ≡ F References: Cabero, J., Lopez, R., Salamat, L. & Sta. Maria, A. (2010). Discrete Mathematics 1. Quad Alpha Centrum Bldg., 125 Pioneer Street, Mandaluyong City: National Book Store. Converse, Inverse, & Contrapositive (n. d.) Retrieved from http://www.sfponline.org/uploads/300/Inverse%20Converse%20&%20Contrapositive.doc CSc 245 — Introduction to Discrete Structures (McCann) The Page O’ Logical Equivalences (“POLE”) (2014) Retrieved from http://www.cs.arizona.edu/people/mccann/handouts/equivalences.pdf Discrete Mathematics 1-1. Logic (2009) Retrieved from http://cglab.snu.ac.kr/lectures/09-1/discrete_math/dm09_slide1-1.pdf Orenstein, A. & Kotatko, P. (2000). Knowledge, Language and Logic: Questions for Quine. Kluwer Academic Publishers. Logic (2003) Retrieved from http://www.csee.umbc.edu/~artola/slides/Logic.ppt Logical Connective (n. d.) Retrieved from http://www.saylor.org/site/wp-content/uploads/2012/06/MA111_Wikipedia_Logical- Connective_6.7.2012.pdf Math 114(2/3) Discrete Mathematics 2. Logical Equivalence (2003) Retrieved from http://www.fatih.edu.tr/~bkokluce/Abstract%20Mathematics/Logical%20Equivalence.pdf O'Donnell, J., Hall, C. & Page, R. (2007), Discrete Mathematics Using a Computer, Springer, p. 120, ISBN 9781846285981. Paschke, J. (2015). Working with Logic Retrieved from http://math.jhu.edu/~jpaschke/Extra%20Handouts/Working_with_Logic.pdf Propositional Equivalences (n. d.) Retrieved from http://people.math.gatech.edu/~ecroot/2406_2012/basic_logic.pdf Propositional Logic (2014) Retrieved from http://www2.lv.psu.edu/ojj/courses/discrete-math/topics/01logic.html The Laws of Thought (n. d.) Retrieved from http://www.the-philosopher.co.uk/lawsofthought.htm Waner, S. & Costenoble, S. (1996), Introduction to Logic (2001) Retrieved from http://www.zweigmedia.com/RealWorld/logic/logic2.html WUCT Discrete Mathematics Logic (n. d.) Retrieved from http://www.uow.edu.au/~bmaloney/wuct121/LogicTeacher.pdf 01 Handout 1 *Property of STI Page 5 of 5