06 Logic and Proof slides for Discrete Mathematics.pptx

Discrete Mathematics - Logic and Proof 6

1. Logic and Proof CSE 2213 – Discrete Mathematics Course teacher: Minhajul Bashir 10/9/2023 [email protected]

2. What happens for multiple variables? Remember commutative rule? For all values of and , How to represent this using quantifiers?   10/9/2023 [email protected] 2

3. Nested quantifiers Quantifier used within the scope of another quantifier The example from previous slide: We can put any quantifier within the scope of any quantifier Quantifiers are read left-to-right   10/9/2023 [email protected] 3

4. Another example: Additive inverse For every real number , there is a corresponding real number such that . How do we represent it using quantifiers?   10/9/2023 [email protected] 4

5. Quick exercise Express the following statement using predicates and quantifiers: “If a real number is negative and another real number is positive, then their product is negative.”   10/9/2023 [email protected] 5

6. Order of quantifiers Commutative law: Can we rewrite this as ?? What do they mean? Do they mean the same? Yes    10/9/2023 [email protected] 6

7. Order of quantifiers Some random observation: Can we rewrite this as ?? What do they mean? Do they mean the same?   10/9/2023 [email protected] 7

8. Order of quantifiers Inverse law: Can we write it as ?? What do they mean? Do they mean the same? No    10/9/2023 [email protected] 8

9. Order of quantifiers If only universal or only existential quantifiers are nested, their order can be changed If both quantifiers are nested, their order cannot be changed, otherwise the meaning will be changed 10/9/2023 [email protected] 9

10. Quick exercise Find out the truth values of the following:   10/9/2023 [email protected] 10

11. Quick exercise Find out the truth values of the following:   10/9/2023 [email protected] 11

12. Exercise There is a student at your school who has been a contestant on a television quiz show No student at your school has ever been a contestant on a television quiz show . There is a student at your school who has been a contestant on Jeopardy! and on Wheel of Fortune Every television quiz show has had a student from your school as a contestant. Given predicate: has been a contestant on the game show . Domains: : Set of students in your school : Set of all television quiz shows   10/9/2023 [email protected] 12

13. Exercise At least two students from your school have been contestants on Jeopardy! Given predicate: has been a contestant on the game show . Domains: : Set of students in your school : Set of all television quiz shows   10/9/2023 [email protected] 13

14. Exercise Jerry does not have an internet connection. No one in the class has chatted with Bob. Sanjay has chatted with everyone except Joseph. Not everyone in your class has an internet connection. Everyone in your class with an Internet connection has chatted over the Internet with at least one other student in your class. Given predicate: has an internet connection and have chatted over the internet Domain: Set of all students in this class   10/9/2023 [email protected] 14

15. Exercise Exactly one student in your class has an Internet connection. Someone in your class has an Internet connection but has not chatted with anyone else in your class . There are two students in your class who have not chatted with each other over the Internet . There are at least two students in your class who have not chatted with the same person in your class. Given predicate: has an internet connection and have chatted over the internet Domain: Set of all students in this class   10/9/2023 [email protected] 15

16. Exercise There are two students in the class who between them have chatted with everyone else in the class. Given predicate: has an internet connection and have chatted over the internet Domain: Set of all students in this class   10/9/2023 [email protected] 16