Discrete Structures Overview with Logic Foundations

In this chapter, you will delve into the fundamentals of discrete structures, including propositional logic and logical operators. Explore examples of propositions and popular boolean operators like negation, conjunction, and implication. Gain insights into the foundations of logic, exploring compound propositions and equivalence. Enhance your understanding of unary and binary operators, connecting with the essence of discrete mathematics.

• Discrete Structures
• Propositional Logic
• Logical Operators
• Foundations of Logic
• Unary and Binary Operators

rayniy Follow

Uploaded on Mar 09, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Discrete Structure Chapter 1 Dr. Mustafa Salah Khalefa Chapter 1 1

2. Course Objectives . : Chapter 1 2

3. Course Textbook(s) 1- Rosen, Kenneth. Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science, 2011. 2- \ 1993 \ 2 . 1996 Other Recommended Resource: 1- Todd Feil, Joan Krone, "Essential Discrete Mathematics", Prentice Hall, 2003. Chapter 1 3

4. Course Overview Chapter 1 4

5. Discrete Structures Well Study Chapter 1 5

6. Chapter 1 6

7. Foundations of Logic Chapter 1 7

8. Foundations of Logic: Overview Proposition Logical operators Compound proposition Bit operators Equivalence Chapter 1 8

9. Propositional Logic Propositional . ) ( ) ( False True Propositional variable True False Propositional ) p,q,r . ( 9 Chapter 1

10. Examples of Propositions It is raining. (In a given situation.) Bagdad is the capital of Iraq. 1 + 2 = 3 But, the following are NOT propositions: Who s there? (interrogative, question) La la la la la. (meaningless interjection) Just do it! (imperative, command) Yeah, I sorta dunno, whatever... (vague) 1 + 2 (expression with a non-true/false value) Chapter 1 10

11. Operators / Connectives operator or connective : . Unary operators take 1 operand (e.g., 3); binaryoperators take 2 operands (e.g., 3 4). Chapter 1 11

12. Some Popular Boolean Operators Formal Name Nickname Arity Symbol Negation operator Conjunction operator Disjunction operator Exclusive-OR operator XOR Implication operator Biconditional operator NOT AND OR Unary Binary Binary Binary Binary Binary IMPLIES IFF 12 Chapter 1

13. The Negation Operator E.g. If p = I have brown hair. then p = I do not have brown hair. ( unaryoperator ) NOT: p p T F F T T : True; F : False : means is defined as 13 Chapter 1

14. The Conjunction Operator (AND) binary connective , operator ) conjunction operator Propositional ( ND E.g. If p= I will have chicken for lunch. and q= I will have steak for dinner. , then p q= I will have salad for lunch and I will have steak for dinner. Chapter 1 14

15. Conjunction Truth Table Note that a conjunction p1 p2 pn of n propositions will have 2n rows in its truth table. Operand columns p q F F F T p F F T T q F T F T ( and truth table . ) Chapter 1 15

16. The Disjunction Operator / OR disjunction operator disjunction connective , binary operator ) ( Propositional p= My car has a bad engine. q= My car has a bad carburetor. p q= Either my car has a bad engine, or my car has a bad carburetor. Meaning is like and/or in English. Chapter 1 16

17. Disjunction Truth Table p q . true true q true P true q true p q p F F F F T T T F T T T T q inclusive p AND . Chapter 1 17

18. Nested Propositional Expressions I just saw my old friend, and either he s grown or I ve shrunk. = f (g s) ) ( parentheses (f g) s f g s Chapter 1 18

19. A Simple Exercise Let p= It rained last night , q= The sprinklers came on last night, r= The lawn was wet this morning. Translate each of the following into English: p = r p = r p q = it didn t rain last night. Either the lawn wasn t wet this morning, or it rained last night, or the sprinklers came on last night. It didn t rain last night. The lawn was wet this morning, and Chapter 1 19

20. The Exclusive Or Operator Exclusive Disjunction . p = I will earn an A in this course, q = I will drop this course, p q = I will either earn an A for this course, or I will drop it (but not both!) XOR Exclusive-or , Chapter 1 20

21. Exclusive-Or Truth Table q p q p F F F T T F T T - . F T T F ( ( exclusive or Note difference from OR. . Chapter 1 21

22. Natural Language is Ambiguous q p "or" q p F F F T T F T T F T T ? Noor is a singer or Noor is a writer. - Noor is a man or Noor is a woman. - Chapter 1 22

23. The Implication Operator Conditional Operator .) E.g., let p = You study hard. q = You will get a good grade. p q = If you study hard, then you will get a good grade. (else, it could go either way) q p ( , Chapter 1 23

24. Implication Truth Table p q q . p q p q F F F T T F T T T T F T p The only False case! Chapter 1 24

25. Examples of Implications 1-p = T , q = T , (p q) = T 2-p = F , q = T , (p q) = T 3-p = F , q = F , (p q) = T 4-p = T , q = F , (p q) = F ) = , q = P ( . Chapter 1 25

26. Examples of Implications If this lecture ends, then the sun will rise tomorrow. True or False? If Tuesday is a day of the week, then the humans is a penguin. True or False? If 1+1=6, then 2 is event number. True or False? If the moon is made of green cheese, then I am richer than Bill Gates. True or False? Chapter 1 26

27. English Phrases Meaning p q p implies q if p, then q if p, q when p, q whenever p, q q if p q when p q whenever p p only if q p is sufficient for q q is necessary for p q follows from p q is implied by p Chapter 1 27

28. Converse, Inverse, Contrapositive :p q ) ( conditional implication q p p q Its converse is: Its inverse is: Its contrapositive: q p. Contrapositive ) ( p q , Chapter 1 28

29. How do we know for sure? Proving the equivalence of p q and its contrapositive using truth tables: q T F T F p T T F F p q q p T T F T p F F F T T F T T q T T F T Chapter 1 29

30. The biconditional operator/IFF p q p = You passed the exam. q = you scored 50% or higher. p q = You passed the exam if and only if you scored 50% or higher. p 30 Chapter 1

31. Biconditional Truth Table p q . Biconditional q (p q) p p q p q F F F T T F T T T F F T p q p, q Chapter 1 31

32. Compound Propositions , p q ( p) q ( (p q priorities ( , .) Chapter 1 32

33. Operations Priorities 1. Negation / NOT 2. Conjunction / AND 3. Disjunction/OR , Exclusive-OR / XOR )( , . Chapter 1 33

34. Boolean Operations Summary p q p p q p q p q p qp q F F T F F F T T F T T F F F T T T F T T F T T F T T F T T F F T Chapter 1 34

35. Some Alternative Notations Name: Propositional logic: not and or xor implies ppq + iff == Boolean algebra: C/C++/Java (wordwise): ! && || != C/C++/Java (bitwise): Logic gates: ~ & | ^ 35 Chapter 1

36. Bits and Bit Operators = Bit Binary Digit Bit False = 0 True = 1 1010011 Bit string 36 Chapter 1

37. Represent Operators using Bit p q p q p q p q 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 Chapter 1 37

38. Example Lets x=0110 y=1101 Fined x y , x y , x vy. Bitwise AND vBitwise OR Bitwise XOR Chapter 1 38

39. Tautology & Contradiction True Tautology p ( p) p p Compound Proposition . p ( p) F T T T F T False Contradiction . p p p p p p F T F T F F Chapter 1 39

40. Logical Equivalence Two propositions are said to be logically equivalent if they have identical truth values for every set of truth values of their components. . P Q Chapter 1 40

41. De Morgan's laws . (p q) (p v q) p v p q q Chapter 1 41