Week 3,4 Logic Discrete Mathematics 2023-2024 (EGYPTIAN E-LEARNING UNIVERSITY)

2023-2024 Fall Semester Discrete Mathematics. 1  MA 112 : Discrete Structures Week 3,4 2 2  MA 112 : Discrete Structures  Instructor: E-mail: My Offic...

2023-2024 Fall Semester Discrete Mathematics. 1  MA 112 : Discrete Structures Week 3,4 2 2  MA 112 : Discrete Structures  Instructor: E-mail: My Office : Lecture : 3 Computer Science Department 3  Text Book : “Discrete Mathematics and its Application “, by K.Rosen , 8th Edition , Course URL: Use lecture notes as a study guide. 4 4  Assessment method Activity % assignments Quizzes Tutorial and Lab Attendance Performance and Interaction (electronic and physical) Mid -Term Exam 20 Final Exam 50 Total 100 5 Topics Covered This course will cover the following topics: Sets And Sets Operations Functions Relations Mathematical Induction Propositional Logic Proof Technical. Graphs. Trees 6 Computer Science Department 6 7 Propositional Logic  Introduction to Logic 8 Computer Science Department 8 Lecture Overview Statement Logical Connectives Conjunction Disjunction Propositions Conditional Bio-conditional Converse Inverse Contrapositive Laws of Logic 9 Computer Science Department 9 Introduction: Logic? We will study Propositional Logic (PL) Logic is the study of the logic relationships between objects and forms the basis of all mathematical reasoning and all automated reasoning ( ‫)التفكير االلى‬ 10  Introduction: Propositional Logic (PL)? The basic building block of logic is Proposition Definition: A proposition (or statement) is a declarative sentence that is either true or false, but not both or somewhere “in between!”. EXAMPLE 1: All the following declarative sentences are propositions. 1. Cairo is the capital of Egypt. 2.1+1=2. 3.2+2=3. Propositions 1 and 2 are true, whereas 3 are false 11  Introduction: Propositional Logic (PL)? EXAMPLE 2: all the following sentences are not propositions. 1. What time is it? 2. Read this carefully. 3.x+1=2. 4.x+y=Z Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false The area of logic that deals with propositions is called propositional logic. We usually denote a proposition by a letter: p, q, r, s, … 12  Introduction: Propositional Logic (PL)? Definition: The value of a proposition is called its truth value; denoted by T or 1 if it is true or F or 0 if it is false Truth table Truth tables: a table that gives the truth values of a proposition. p T F 13  Propositions: Examples 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 Opinion Q: My house is big Opinion C++ is the best language Opinion When is the pretest? Interrogative Do your homework Imperative 14 © Discrete Mathematical Structures: Theory and Applications 14  Logical Connectives and Compound Statement 15 Computer Science Department 15 Compound Proposition Compound Propositions are formed from existing propositions using logical connectives (operators). 16 Logical Connective: Negation (Not) ¬ Definition: Let p be a proposition. The negation of p, denoted by ¬𝑝, is the statement “It is not the case that p.” The proposition ¬𝑝 is read as “not p.” The truth value of the negation of p, ¬𝑝, is the opposite of the truth value of p. Truth table The Truth Table for the Negation of a Proposition. p ¬p T F F T 17  Logical Connective: Negation (Not) ¬ Examples Find the negation of the following propositions: 1- p: Today is Friday. 2- q: Cairo is the capital of Egypt Solution: 1- ¬𝑝: Today is not Friday. or ¬𝑝: It is not Friday today. 2- ¬𝑞: It is not the case that Cairo is the capital of Egypt Or ¬𝑞: Cairo is not the capital of Egypt 18 18  Logical Connective: conjunction And Λ DEFINITION Let p and q be propositions. The conjunction of p and q, denoted by p Λ q, is the proposition “p and q”. The conjunction p Λ q is true when both p and q are true and is false otherwise. Examples Truth table a- p: It is raining The Truth Table for q: it is warm the Conjunction of p Λ q: It is raining and it is warm. Two Propositions. p q pΛq b- p: 2+3=5 T T T q: 1 10 Disjunction of Two Propositions. P  Q is True iff x is outside 0 to 10 Examples p q pνq It is raining or it is the second lecture T T T (2+2=5)  (1