Bài giảng Discrete Mathematics I - Chapter 1: Logics

Logics Tran Vinh Tan Contents Propositional Logic 1.1 Chapter 1 Logics Discrete Mathematics I on 13 March 2012 Tran Vinh Tan Faculty of Computer Science and Engineering University of Technology - VNUHCM Logics Tran Vinh Tan Contents Propositional Logic 1.2 Contents 1 Propositional Logic Logics Tran Vinh Tan Contents Propositional Logic 1.3 Logic Definition (Averroes) The tool for distinguishing between the true and the false. Definition (Penguin Encyclopedia) The formal systematic study of the principles of valid inference and correct reasoning. Definition (Discrete Mathematics - Rosen) Rules of logic are used to distinguish between valid and invalid mathematical arguments. Logics Tran Vinh Tan Contents Propositional Logic 1.4 Applications in Computer Science • Design of computer circuits • Construction of computer programs • Verification of the correctness of programs • Constructing proofs automatically • Artificial intelligence • Many more... Logics Tran Vinh Tan Contents Propositional Logic 1.5 Propositional Logic Definition A proposition is a declarative sentence that is either true or false, but not both. Examples • Hanoi is the capital of Viet Nam. • New York City is the capital of USA. • 1 + 1 = 2 • 2 + 2 = 3 Logics Tran Vinh Tan Contents Propositional Logic 1.6 Examples Examples (Which of these are propositions?) • How easy is logic! • Read this carefully. • H1 building is in Ho Chi Minh City. • 4 > 2 • 2n ≥ 100 • The sun circles the earth. • Today is Thursday. • Proposition only when the time is specified Logics Tran Vinh Tan Contents Propositional Logic 1.7 Notations • Propositions are denoted by p, q, . . . • The truth value (”chân trị”) is true (T) or false (F) Logics Tran Vinh Tan Contents Propositional Logic 1.8 Operators Negation - ”Phủ định”: ¬p Bảng: Truth Table for Negation p ¬p T F F T Logics Tran Vinh Tan Contents Propositional Logic 1.9 Operators Conjunction - ”Hội”: p ∧ q “p and q” p q p ∧ q T T T T F F F T F F F F I’m teaching DM1 and it is raining today. Disjunction - ”Tuyển”: p ∨ q “p or q” p q p ∨ q T T T T F T F T T F F F We need students who have experience in Java or C++. Tomorrow, I will eat Pho or Bun bo. Logics Tran Vinh Tan Contents Propositional Logic 1.10 Operators Exclusive OR - Tuyển loại : p⊕ q “p or q (but not both)” p q p⊕ q T T F T F T F T T F F F Implication - Kéo theo: p→ q “if p, then q” p q p→ q T T T T F F F T T F F T If it rains, the pavement will be wet. Logics Tran Vinh Tan Contents Propositional Logic 1.11 More Expressions for Implication p→ q • if p, then q • p implies q • p is sufficient for q • q if p • p only if q • q unless ¬p • If you get 100% on the final, you will get 10 grade. • If you feel asleep this afternoon, then 2 + 3 = 5. Logics Tran Vinh Tan Contents Propositional Logic 1.12 Conditional Statements From p→ q • q → p (converse - đảo) • ¬q → ¬p (contrapositive - phản đảo) • Prove that only contrapositive have the same truth table with p→ q Logics Tran Vinh Tan Contents Propositional Logic 1.13 Exercise What are the converse and contrapositive of the following conditional statement “If he plays online games too much, his girlfriend leaves him.” • Converse: If his girlfriend leaves him, then he plays online games too much. • Contrapositive: If his girlfriend does not leave him, then he does not play online games too much. Logics Tran Vinh Tan Contents Propositional Logic 1.14 Biconditionals p↔ q “p if and only if q” p q p→ q T T T T F F F T F F F T • “p is necessary and sufficient for q”. • “if p then q, and conversely”. • “p iff q”. Logics Tran Vinh Tan Contents Propositional Logic 1.15 Translating Natural Sentences Exercise I will buy a new phone only if I have enough money to buy iPhone 4 or my phone is not working. • p: I will buy a new phone • q: I have enough money to buy iPhone 4 • r: My phone is working • p→ (q ∨ ¬r) Logics Tran Vinh Tan Contents Propositional Logic 1.16 Translating Natural Sentences Exercise He will not run the red light if he sees the police unless he is too risky. Logics Tran Vinh Tan Contents Propositional Logic 1.17 Construct Truth Table Exercise Construct the truth table of the compound proposition (p ∨ ¬q)→ (p ∧ q). p q ¬q p ∨ ¬q p ∧ q (p ∨ ¬q)→ (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F Logics Tran Vinh Tan Contents Propositional Logic 1.18 Applications • System specifications • “When a user clicked on Help button, a pop-up will be shown up” • Boolean search • type “dai hoc bach khoa” in Google • means “dai AND hoc AND bach AND khoa” Logics Tran Vinh Tan Contents Propositional Logic 1.19 Applications (cont.) • Logic puzzles • There are two kinds of inhabitants on an island, knights, who always tell the truth, and their opposites, knaves, who always lie. You encounter two people A and B. What are A and B if A says “B is a knight” and B says ”The two of us are opposite types”? • Bit operations • 101010011 is a bit string of length nine. Logics Tran Vinh Tan Contents Propositional Logic 1.20 Tautology and Contradiction Definition A compound proposition that is always true (false) is called a tautology (contradiction). • Tautology: hằng đúng • Contradiction: mâu thuẫn Example • p ∨ ¬p (tautology) • p ∧ ¬p (contradiction) Logics Tran Vinh Tan Contents Propositional Logic 1.21 Logical Equivalences Definition The compound compositions p and q are called logically equivalent if p↔ q is a tautology, denoted p ≡ q. Example Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent. Logics Tran Vinh Tan Contents Propositional Logic 1.22 Logical Equivalences p ∧T ≡ p Identity laws p ∨ F ≡ p Luật đồng nhất p ∨T ≡ T Domination laws p ∧ F ≡ F Luật nuốt p ∨ p ≡ p Idempotent laws p ∧ p ≡ p Luật lũy đẳng ¬(¬p) ≡ p Double negation law Luât phủ định kép Logics Tran Vinh Tan Contents Propositional Logic 1.23 Logical Equivalences p ∨ q ≡ q ∨ p Commutative laws p ∧ q ≡ q ∧ p Luật giao hoán (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Luật kết hợp p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Luật phân phối ¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s law ¬(p ∨ q) ≡ ¬p ∧ ¬q Luật De Morgan p ∨ (p ∧ q) ≡ p Absorption laws p ∧ (p ∨ q) ≡ p Luật hút thu Logics Tran Vinh Tan Contents Propositional Logic 1.24 Logical Equivalences Equivalence p ∨ ¬p ≡ T p ∧ ¬p ≡ F (p→ q) ∧ (p→ r) ≡ p→ (q ∧ r) (p→ r) ∧ (q → r) ≡ (p ∨ q)→ r (p→ q) ∨ (p→ r) ≡ p→ (q ∨ r) (p→ r) ∨ (q → r) ≡ (p ∧ q)→ r p↔ q ≡ (p→ q) ∧ (q → p) Logics Tran Vinh Tan Contents Propositional Logic 1.25 Constructing New Logical Equivalences Example Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences. Solution ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) by the second De Morgan law ≡ ¬p ∧ [¬(¬p) ∨ ¬q] by the first De Morgan law ≡ ¬p ∧ (p ∨ ¬q) by the double negation law ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) by the second distributive law ≡ F ∨ (¬p ∧ ¬q) because ¬p ∧ p ≡ F ≡ ¬p ∧ ¬q by the identity law for F Consequently, ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent.