Discrete Mathematics Lecture 01 PDF

Discrete Mathematics Lecture 01 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Introduce Myself Dr. Ahmed Hagag Associate Professor, Scientific Computing Department...

Discrete Mathematics Lecture 01 Dr. Ahmed Hagag Faculty of Computers and Artificial Intelligence Benha University Fall 2025  Introduce Myself Dr. Ahmed Hagag Associate Professor, Scientific Computing Department, Vice Dean for Community Service Affairs, Faculty of Computers and Artificial Intelligence, Benha University. Email: [email protected] ©Ahmed Hagag Discrete Mathematics 2  Basic Course Information Course code: BS102 Course name: Discrete Mathematics Level: 1st Year / B.Sc. Course Credit: 3 credits Instructors: Dr. Ahmed Hagag Dr. Hiba Khalil Dr. Doaa Lotfy ©Ahmed Hagag Discrete Mathematics 3  Assessment (1/6) Final Exam Section 50 15 ‫االمتحان النهائي‬ ‫حضور و واجبات‬ ‫ومشاركة في السكاشن‬ Midterm Oral Attend 20 10 5 ‫منتصف الفصل‬ ‫شفوي‬ ‫حضور‬ ©Ahmed Hagag Discrete Mathematics 4  Assessment (2/6) Grade Point Average ©Ahmed Hagag Discrete Mathematics 5  Assessment (3/6) Grade Point Average ©Ahmed Hagag Discrete Mathematics 6  Assessment (4/6) Grade Point Average ©Ahmed Hagag Discrete Mathematics 7  Assessment (5/6) Grade Point Average 2 ‫ × عدد ساعات المادة‬2 ‫ نقاط المادة‬+ 1 ‫ × عدد ساعات المادة‬1 ‫نقاط المادة‬ ©Ahmed Hagag Discrete Mathematics 8  Assessment (6/6) Grade Point Average ©Ahmed Hagag Discrete Mathematics 9  Lectures Reference Textbook 2019 ©Ahmed Hagag Discrete Mathematics 10  Discussion Question Why do we study this course? ©Ahmed Hagag Discrete Mathematics 11  Course Objectives Learn how to think mathematically. Grasp the basic logical and reasoning mechanisms of mathematical thought. Acquire logic and proof as the basics for abstract thinking. Improve problem-solving skills. Grasp the basic elements of induction, recursion, combination and discrete structures. ©Ahmed Hagag Discrete Mathematics 12  DM is a Gateway Course Topics in discrete mathematics will be important in many courses that you will take in the future: Computer Science: Computer Architecture, Data Structures, Algorithms, Programming Languages, Compilers, Computer Security, Databases, Artificial Intelligence, Networking, Graphics, Game Design, Theory of Computation, …… Mathematics: Logic, Set Theory, Probability, Number Theory, Abstract Algebra, Combinatorics, Graph Theory, Game Theory, Network Optimization, … Other Disciplines: You may find concepts learned here useful in courses in philosophy, economics, linguistics, and other departments. ©Ahmed Hagag Discrete Mathematics 13  Course Syllabus Some topics from the following chapters: The Foundations: Logic and Proofs. Basic Structures. Algorithms. Number Theory and Cryptography. Induction and Recursion. Relations. Graphs. ©Ahmed Hagag Discrete Mathematics 14  Chapter 1: Logic and Proofs Some topics from the following sections: Introduction to Propositional Logic. Compound Propositions. Applications of Propositional Logic. Propositional Equivalences. Predicates and Quantifiers. Nested Quantifiers Rules of Inference. Introduction to Proofs. ©Ahmed Hagag Discrete Mathematics 15  Introduction to Propositional Logic (1/4) What is Logic? Logic is the discipline that deals with the methods of reasoning. On an elementary level, logic provides rules and techniques for determining whether a given argument is valid. Logical reasoning is used in mathematics to prove theorems. ©Ahmed Hagag Discrete Mathematics 16  Introduction to Propositional Logic (2/4) The basic building blocks of logic is Proposition A proposition (or statement) is a declarative sentence that is either true or false, but not both. The area of logic that deals with propositions is called propositional logics. ©Ahmed Hagag Discrete Mathematics 17  Introduction to Propositional Logic (3/4) Examples: Propositions Truth value 2+3=5 True 5−2=1 False Today is Friday False 𝑥+3=7, for 𝑥 = 4 True Cairo is the capital of Egypt True Sentences Is a Proposition What time is it? Not propositions Read this carefully. Not propositions 𝑥+3=7 Not propositions ©Ahmed Hagag Discrete Mathematics 18  Introduction to Propositional Logic (4/4) We use letters to denote propositional variables 𝒑, 𝒒, 𝒓, 𝒔, … The truth value of a proposition is true, denoted by T, if it is a true proposition and false, denoted by F, if it is a false proposition. ©Ahmed Hagag Discrete Mathematics 19  Compound Propositions (1/23) Compound Proposition Compound Propositions are formed from existing propositions using logical operators. ©Ahmed Hagag Discrete Mathematics 20  Compound Propositions (2/23) Negation Other notations you might see are ©Ahmed Hagag Discrete Mathematics 21  Compound Propositions (3/23) Example Find the negation of the proposition 𝑝: “Cairo is the capital of Egypt” ©Ahmed Hagag Discrete Mathematics 22  Compound Propositions (4/23) Example: Solution Find the negation of the proposition 𝑝: “Cairo is the capital of Egypt” The negation is ¬𝑝: “It is not the case that Cairo is the capital of Egypt” This negation can be more simply expressed as ¬𝑝: “Cairo is not the capital of Egypt” ©Ahmed Hagag Discrete Mathematics 23  Compound Propositions (5/23) Truth Table Truth Table: is a table that gives the truth values of a compound statement. The Truth Table for the Negation of a Proposition 𝒑 ¬𝒑 Proposition 𝑇 Truth Values 𝐹 ©Ahmed Hagag Discrete Mathematics 24  Compound Propositions (5/23) Truth Table Truth Table: is a table that gives the truth values of a compound statement. The Truth Table for the Negation of a Proposition 𝒑 ¬𝒑 Proposition 𝑇 𝐹 Truth Values 𝐹 𝑇 ©Ahmed Hagag Discrete Mathematics 25  Compound Propositions (6/23) Negation ©Ahmed Hagag Discrete Mathematics 26  Compound Propositions (7/23) Logical Connectives Example 𝑝: Today is Friday. 𝑞: It is raining today. 𝑝 ∧ 𝑞: Today is Friday and it is raining today. ©Ahmed Hagag Discrete Mathematics 27  Compound Propositions (8/23) Logical Connectives Example 𝑝: Today is Friday. 𝑞: It is raining today. 𝑝 ∨ 𝑞: Today is Friday or it is raining today. ©Ahmed Hagag Discrete Mathematics 28  Compound Propositions (9/23) Logical Connectives Example p : They are parents. q : They are children. p  q : They are parents or children but not both. ©Ahmed Hagag Discrete Mathematics 29  Compound Propositions (10/23) Logical Connectives ©Ahmed Hagag Discrete Mathematics 30  Compound Propositions (10/23) Logical Connectives ©Ahmed Hagag Discrete Mathematics 31  Compound Propositions (11/23) Logical Connectives 1 ©Ahmed Hagag Discrete Mathematics 32  Compound Propositions (12/23) Logical Connectives 2 ©Ahmed Hagag Discrete Mathematics 33  Compound Propositions (12/23) Logical Connectives 2 ©Ahmed Hagag Discrete Mathematics 34  Compound Propositions (13/23) Logical Connectives 3 ©Ahmed Hagag Discrete Mathematics 35  Compound Propositions (13/23) Logical Connectives 3 ©Ahmed Hagag Discrete Mathematics 36  Compound Propositions (14/23) Logical Connectives ©Ahmed Hagag Discrete Mathematics 37  Compound Propositions (15/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 38  Compound Propositions (16/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 39  Compound Propositions (16/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 40  Compound Propositions (16/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 41  Compound Propositions (16/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 42  Compound Propositions (16/23) Truth Tables of Compound Propositions 1 ©Ahmed Hagag Discrete Mathematics 43  Compound Propositions (17/23) Precedence of Logical Operators ©Ahmed Hagag Discrete Mathematics 44  Compound Propositions (18/23) Truth Tables of Compound Propositions 2 ©Ahmed Hagag Discrete Mathematics 45  Compound Propositions (19/23) Truth Tables of Compound Propositions 2 𝒑 𝒒 𝒓 ¬𝒒 𝒑 ∧ ¬𝒒 𝒑 ∧ ¬𝒒 → 𝒓 ©Ahmed Hagag Discrete Mathematics 46  Compound Propositions (19/23) Truth Tables of Compound Propositions 2 𝒑 𝒒 𝒓 ¬𝒒 𝒑 ∧ ¬𝒒 𝒑 ∧ ¬𝒒 → 𝒓 𝐓 𝐓 𝐓 𝐓 𝐓 𝐅 𝐓 𝐅 𝐓 𝐓 𝐅 𝐅 𝐅 𝐓 𝐓 𝐅 𝐓 𝐅 𝐅 𝐅 𝐓 𝐅 𝐅 𝐅 ©Ahmed Hagag Discrete Mathematics 47  Compound Propositions (19/23) Truth Tables of Compound Propositions 2 𝒑 𝒒 𝒓 ¬𝒒 𝒑 ∧ ¬𝒒 𝒑 ∧ ¬𝒒 → 𝒓 𝐓 𝐓 𝐓 𝐅 𝐓 𝐓 𝐅 𝐅 𝐓 𝐅 𝐓 𝐓 𝐓 𝐅 𝐅 𝐓 𝐅 𝐓 𝐓 𝐅 𝐅 𝐓 𝐅 𝐅 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐅 𝐓 ©Ahmed Hagag Discrete Mathematics 48  Compound Propositions (19/23) Truth Tables of Compound Propositions 2 𝒑 𝒒 𝒓 ¬𝒒 𝒑 ∧ ¬𝒒 𝒑 ∧ ¬𝒒 → 𝒓 𝐓 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐅 𝐓 𝐅 𝐓 𝐓 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐓 𝐓 𝐅 𝐅 𝐅 𝐓 𝐅 𝐅 𝐅 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐅 𝐅 𝐓 𝐅 ©Ahmed Hagag Discrete Mathematics 49  Compound Propositions (19/23) Truth Tables of Compound Propositions 2 𝒑 𝒒 𝒓 ¬𝒒 𝒑 ∧ ¬𝒒 𝒑 ∧ ¬𝒒 → 𝒓 𝐓 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐓 𝐅 𝐅 𝐅 𝐓 𝐓 𝐅 𝐓 𝐓 𝐓 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐓 𝐅 𝐓 𝐅 𝐅 𝐅 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐓 𝐅 𝐅 𝐅 𝐓 𝐅 𝐓 ©Ahmed Hagag Discrete Mathematics 50  Compound Propositions (20/23) Logic and Bit Operations Computers represent information using bits. A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one). ©Ahmed Hagag Discrete Mathematics 51  Compound Propositions (21/23) Computer Bit Operations We will also use the notation OR, AND, and XOR for the operators ∨, ∧, and ⊕, as is done in various programming languages. ©Ahmed Hagag Discrete Mathematics 52  Compound Propositions (22/23) Bit Strings Information is often represented using bit strings, which are lists of zeros and ones. When this is done, operations on the bit strings can be used to manipulate this information. ©Ahmed Hagag Discrete Mathematics 53  Compound Propositions (23/23) Example Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101 ©Ahmed Hagag Discrete Mathematics 54  Video Lectures All Lectures: https://www.youtube.com/playlist?list=PLxIvc-MGOs6gZlMVYOOEtUHJmfUquCjwz Lecture #1: https://www.youtube.com/watch?v=eFDzhn1Inc4&list=PLxIvc- MGOs6gZlMVYOOEtUHJmfUquCjwz&index=1 https://www.youtube.com/watch?v=dOZ6Bam4Bks&list=PLxIvc- MGOs6gZlMVYOOEtUHJmfUquCjwz&index=2 https://www.youtube.com/watch?v=-BxvBFJaN6E&list=PLxIvc- MGOs6gZlMVYOOEtUHJmfUquCjwz&index=3 ©Ahmed Hagag Discrete Mathematics 55 Thank You Dr. Ahmed Hagag [email protected]