Discrete Structures Chapter 1 Mathematical Logic PDF

AlBaha University Faculty of Computer Science and Information Technology Department of computer science Semester 1/1440-1441 Discrete Structures 41011212 Instructors: Dr. Bedine KERIM, Dr. Mahmoud ABUOGHALY...

AlBaha University Faculty of Computer Science and Information Technology Department of computer science Semester 1/1440-1441 Discrete Structures 41011212 Instructors: Dr. Bedine KERIM, Dr. Mahmoud ABUOGHALY Dr. Najib BEN AOUN  Chapter 1 Mathematical Logic 2  Mathematical Logic Definition: Mathematical Logic is a Methods of reasoning, it provides rules and techniques to determine whether an (argument == statement == proposition) is valid or not Example: If x is an even integer, then x + 1 is an odd integer The statement x + 1 is an odd integer is true under the condition that x is an integer is true 3  Mathematical Logic A statement, or a proposition, is a declarative sentence that is either true or false, but not both Uppercase letters denote propositions – Examples: P: 2 is an even number (true) Q: 7 is an even number (false) R: A is a vowel (true) – The following are not propositions: P: My cat is beautiful § Q: My house is big How beautiful is the rose? What time is it? Take a cup of tea. 𝑥+𝑦 =3 4  Logical Connectives and Truth Tables Each proposition evaluates to either true T or false F. T and F are called proposition truth values In this section we look at how simple propositions can be combined to form more complicated propositions called compound propositions. Logical connectives {negation, and, inclusive or, exclusive or, implication, biconditional} are used to link pairs of propositions, the truth value of any compound proposition is completely determined by (a) the truth values of its component simple propositions, and (b) the particular connective, or connectives, used to link them. 5  Negation or ¬P The negation of P, written ¬P, is the statement obtained by negating statement P Example: P: A is a consonant letter. ¬P :A is not a consonant letter. Q: The circle have a volume ¬P : The circle does not have a volume The negation of the proposition reverse the truth value of the proposition which is shown in the following truth table P ¬P T F F T 6 There are several alternative ways of stating the negation of a proposition. If we consider the proposition ‘All dogs are fierce’, some examples of its negation are: - It is not the case that all dogs are fierce. - Not all dogs are fierce. - Some dogs are not fierce. Note that the proposition ‘No dogs are fierce’ is not the negation of ‘All dogs are fierce’. 7 Conjunction ^ Let P and Q be statements. The conjunction of P and Q, written P ^Q , is the statement formed by joining statements P and Q using the word “and” P ^ Q is true if both p and q are true; otherwise P ^ Q is false The Truth Table for the conjunction is : Example: 𝑝 𝑞 𝑝∧𝑞 p : The sun is shining. 1 1 1 q : Pigs eat turnips. 1 0 0 0 1 0 p ∧ q : The sun is shining and pigs eat turnips. 0 0 0 8 The Inclusive Disjunction: Let P and Q be statements. The Inclusive disjunction of P and Q, written P VQ is true if at least one of the statements P and Q is true; otherwise P VQ is false.. The Truth Table for the inclusive disjunction is shown left below. The Exclusive Disjunction: Let P and Q be statements. The exclusive disjunction of P and Q, written P VQ is true if either P or Q is true but not both. 𝑝 𝑞 𝑝∨𝑞 1 1 1 1 0 1 0 1 1 0 0 0 Inclusive or Exclusive or 9 Examples: Assume the propositions: p: ‘Tomorrow I will go swimming. q: ‘I will play golf’. Then the proposition: ‘Tomorrow I will go swimming or ‘I will play golf’. seems to suggest that I will not do both and therefore points to an exclusive interpretation P VQ But the propositions ‘Applicants for this post must be over 25 or have at least 3 years relevant. experience’ suggests that applicants who satisfy both criteria will also be considered, therefore ‘or’ should be interpreted inclusively P vQ. 10  Implication or condition Let P and Q be statements. The statement if P then Q is called an implication or condition. It is written as P ® Q P is called the hypothesis, Q is called the conclusion 𝑝 𝑞 𝑝→𝑞 Truth Table for Implication: 1 1 1 1 0 0 0 1 1 Notice that ‘if p then q’ is false only when p is true and q is 0 0 1 false, i.e. a true statement cannot imply a false one. If p is false, the compound proposition is true no matter what the truth value of q. 11 Examples: p : I eat breakfast. q : I don’t eat lunch. p → q : If I eat breakfast then I don’t eat lunch Let P : Today is Sunday. Q : I will wash the car. P ® Q : If today is Sunday, then I will wash the car – The contrapositive of this implication is ¬Q ® ¬P If I do not wash the car, then today is not Sunday P ® Q is equivalent to ¬Q ® ¬P 12  Biimplication (Biconditional:) Let P and Q be statements. The statement “P if and only if Q” is called the biimplication or biconditional of P and Q. It is written as P « Q Example: p : I eat breakfast. q : I don’t eat lunch. p ↔ q : I eat breakfast if and only if I don’t eat lunch (or alternatively, ‘If and only if I eat breakfast, then I don’t eat lunch’). The truth table for p ↔ q is given by: 13 Examples 1.1 1. Consider the following propositions: p : Mathematicians are generous. q : Spiders hate algebra. Write the compound propositions symbolized by: Solution (i) Mathematicians are generous or spiders don’t hate algebra (or both). (ii) It is not the case that spiders hate algebra and mathematicians are generous. (iii) If mathematicians are not generous then spiders hate algebra. (iv) Mathematicians are not generous if and only if spiders don’t hate algebra. 14 Example 1.2 2. Let p be the proposition ‘Today is Monday’ and q be ‘I’ll go to London’. Write the following propositions symbolically. (i) If today is Monday then I won’t go to London. (ii) Today is Monday or I’ll go to London, but not both. (iii) I’ll go to London and today is not Monday. (iv) If and only if today is not Monday then I’ll go to London. Solution 15 Example 1.3: Construct the Truth Table for the following compound propositions 16 17 Example 1. : (ii) Homework 18 Example 1.5 Construct the truth table for p∨q→(p∧q) Solution 𝐩 𝐪 𝐩∨𝐪 𝐩∧𝐪 𝐩 ∨ 𝐪 → (𝐩 ∧ 𝐪) 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟎 𝟏 𝟎 𝟎 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟏 19 Example 1.6 Construct the truth table for (p→q)→(q→p) Solution 𝐩 𝐪 𝐩→𝐪 𝐪→𝐩 (𝐩 → 𝐪) → (𝐪 → 𝐩) 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟎 𝟎 𝟏 𝟏 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟎 𝟏 𝟏 𝟏 20  Tautology A tautology is a compound proposition which is true no matter what the truth values of its simple components. In other words A compound proposition 𝑝 ≡ 𝑝 (𝑝! , 𝑝" , … , 𝑝# ) where 𝑝! , 𝑝" , … , 𝑝# are variables is called a tautology if it is true for every truth assignments for 𝑝! , 𝑝" , … , 𝑝#. Example 1.7 21 Example 1.8 Note that The proposition is said to be a substitution instance of the proposition 22  Contradiction A contradiction is a compound proposition which is false no matter what the truth values of its simple components. The proposition 𝑝 ∧ ~𝑝 is a contradiction which is shown in next truth table 𝑝 ~𝑝 𝑝 ∧ ~𝑝 1 0 0 Example 1.9 0 1 0 23 Assignment 1- Question 1: Attempt any two of the following questions 24  Logically Implies A proposition P is said to logically imply a proposition Q if, whenever P is true, then Q is also true. If P logically implies Q, then symbolically we write P → Q. In Other words: A proposition P is said to logically imply proposition Q if the proposition P → Q is a tautology. 25 Example 1.10 26 Example 1.11 27  Logically Equivalent Two propositions are said to be logically equivalent if they have identical truth values for every set of truth values of their components. we write P ≡ Q if P and Q are logically equivalent. In other words a proposition P is said to be logically equivalent to a propositions Q if the statement formula P ↔ Q is a tautology Example 1.12 28 Example 1.13 Show that the following two propositions are logically equivalent 29 compound propositions. 30 Assignment 1- Question 2: Attempt any two of the following questions 31  The Algebra of Propositions The following is a list of some important logical equivalences, all of which can be verified using one of the techniques described previously. These laws hold for any simple propositions p, q and r and also for any substitution instance of them. The duality principle states that, if two propositions are logically equivalent, then so are their duals. 32  Laws of algebra of proposition Primal form Dual Form Idempotent Law 𝑝∨𝑝≡𝑝 𝑝∧𝑝≡𝑝 Dominant Law 𝑝∨𝑇 ≡𝑇 𝑝∧𝐹 ≡𝐹 Complement Law 𝑝 ∨ ~𝑝 ≡ 𝑇 𝑝 ∧ ~𝑝 ≡ 𝐹 Commutative Law 𝑝∨𝑞 ≡𝑞∨𝑝 𝑝∧𝑞 ≡𝑞∧𝑝 Associative Law (𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟) (𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟) Distributive Law 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟) Absorption Law 𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝 𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝 DeMorgan’s Law ~ 𝑝 ∨ 𝑞 ≡ ~𝑝 ∧ ~𝑞 ~ 𝑝 ∧ 𝑞 ≡ ~𝑝 ∨ ~𝑞 33 Example 1.14 Assignment 1- Question 3: Prove the following logical equivalences using the method of the above example 34