Assignment 1 Discrete Mathematics PDF

Preview

Summary

ASSIGNMENT 1Due date: 28th Nov 2021Group assignment (include profile of each member)Predicate Logic Use predicates and quantifiers with more than one variable to express these statements. i. Every computer science student needs a course in Discrete Structures. ii. There is a student in this class wh...

Description

ASSIGNMENT 1 Due date: 28th Nov 2021 Group assignment (include profile of each member) Predicate Logic 1. Use predicates and quantifiers with more than one variable to express these statements. i. Every computer science student needs a course in Discrete Structures. ii. There is a student in this class who owns a personal computer. iii. Every student in this class has taken at least one computer science course. iv. There is a student in this class who has taken at least one computer science course. v. Every student in this class has been in every building on campus. vi. There is a student in this class who has been in every room of at least one building on campus. vii. Every student in this class has been in at least one room of every building on campus. a. ∀xP(x), where P(x) is “x needs a course in Discrete Structures”and the domain for x consists of all computer science students. B. ∃xP(x), where P(x) is “x owns a personal computer”and the domain for x consists of all students in this class. C. ∀x∃yP(x, y), where P(x, y) is “x has taken y”and the domain for x consists of all students in this class and the domain for y consists of all computer science classes. D. ∃x∃yP(x, y), where P(x, y) is “x has taken y”and the domain for x consists of all students in this class and the domain for y consists of all computer science classes. 12 e. ∀x∀yP(x, y), where P(x, y) is “x has been in y”and the domain for x consists of all students in this class and the domain for y consists of all buildings on campus. F. ∃x∃y∀z(P(z, y) → Q(x, z)), where P(z, y) is “z is in y”and Q(x, z) is “x has been in z”; the domain for x consists of all students in this class, the domain for y consists of all buildings on campus and the domain for z consists of all rooms. G. ∀x∀y∃z(P(z, y) ∧ Q(x, z)), where P(z, y) is “z is in y”and Q(x, z) is “x has been in z”; the domain for x consists of all students in this class, the domain for y consists of all buildings on campus and the domain for z consists of all rooms. 2. Express each of these mathematical statements using predicates, quantifiers, logical connectives, and mathematical operators.

i. ii. iii. iv.

The product of two negatives real numbers is positive. The difference of a real number and itself is zero. Every positive real number has exactly two square roots. A negative real number does not have a square root that is a real number.

Rules of Inference & Methods of Proof 1. For each of these collections of premises, what relevant conclusion or conclusions can be drawn? Explain the rules of inference used to obtain each conclusion from the premises. i.

"If I take the day off. it either rains or snows." "I took Tuesday off or I took Thursday off." "It was sunny on Tuesday." "It did not snow on Thursday."

O(x) = “I took x off” R(x) = “it rains on x” S(x) = “it snows on x” “If I take the day off, it either rains or snows.” ∀x(O(x) → (R(x) ∨ S(x))) “I took Tuesday off or I took Thursday off.” O(Tue) ∨ O(Thu) “It was sunny on Tuesday.” ¬S(Tue) ∧ ¬R(Tue) “It did not snow on Thursday.” ¬S(Thu) Step Reason 1 ∀x(O(x) → (R(x) ∨ Premise 1 S(x))) 2 ¬S(Tue) ∧ ¬R(Tue) Premise 3 Premise 3 3 O(Tue) → (R(Tue) ∨ Universal Instantiation S(Tue)) from (1) using “Tue” 4 ¬(R(Tue) ∨ S(Tue)) De Morgan’s Law from (2) 5 ¬O(Tue) Modus Tollens from (3) “I did not take Tues and (4) off.” 6 O(Tue) ∨ O(Thu) Premise 2

7 O(Thu)

Disjunctive Syllogism from (5) and (6) 8 O(Thu) → (R(Thu) ∨ Universal Instantiation S(Thu)) from (1) using “Thu” 9 R(Thu) ∨ S(Thu) Modus Ponens from (7) and (8) 10 ¬S(Thu) Premise 4 11 R(Thu) Disjunctive syllogism from (9) and (10)

“I took Thu off.”

“Either it rained snowed on Thu.”

or

“It rained Thu.”

ii.

ii. "If I eat spicy foods, then I have strange dreams." "I have strange dreams if there is thunder while I sleep." "I did not have strange dreams." S = “I ate spicy food” D = “I had strange dreams” T = “It thundered while I slept” “If I eat spicy foods, then I have strange dreams.” S → D “I have strange dreams if there is thunder while I sleep.” T → D “I did not have strange dreams.” ¬D Step Reason 1 S → D Premise 1 2 T → D Premise 2 3 ¬D Premise 3 4 ¬T Modus Tollens from (2) and (3) “It did not thunder while I slept.” 5 ¬S Modus Tollens from (1) and (3) “I did not eat spicy food” 6 ¬T ∧ ¬S Conjunction from (4) and (5) “It did not thunder and I did not eat spicy food” Step Reason 1S→D Premise 1 2T→D Premise 2 3 ¬D Premise 3 4 ¬T Modus Tollens from (2) “It did not thunder and (3) while I slept.” 5 ¬S Modus Tollens from (1) “I did not eat spicy and (3) food” 6 ¬T ∧ ¬S Conjunction from (4) “It did not thunder and and (5) I did not eat spicy food”

iii.

"I am either clever or lucky." "I am not lucky." "If I am lucky, then I will win the lottery." A=“I am clever” B=”I am lucky” C=”I will win the lottery” “I am either clever or lucky." "I am not lucky." "If I am lucky, then I will win the lottery."

iv.

AvB B A->C

"Every computer science major has a personal computer." "Ralph does not have a personal computer." "Ann has a personal computer."

2. For each of these arguments, explain which rules of inference are used for each step. i.

"Haikal, a student in this class, knows how to write programs in JAVA. Everyone who knows how to write programs in JAVA can get a high-paying job. Therefore, someone in this class can get a high-paying job."

C(x) = “x is in this class” J(x) = “x knows how to write programs in JAVA” H(x) = “x can get a high paying job” Premise 1 C(Doug) Premise 2 J(Doug) Premise 3 ∀x(J(x) → H(x)) Conclude ∃x(C(x) ∧ H(x)) Step Reason 1 ∀x(J(x) → H(x)) Premise 3 2 J(Doug) → H(Doug) Universal Instantiation from (1) 3 J(Doug) Premise 2 4 H(Doug) Modus Ponens from (2) and (3) 5 C(Doug) Premise 1 6 C(Doug)∧H(Doug) Conjunction from (4) and (5) ∴ ∃x(C(x) ∧ H(x)) Existential generalization from (6) ii. "Somebody in this class enjoys whale watching. Every person who enjoys whale watching cares about ocean pollution. Therefore, there is a person in this class who cares about ocean pollution." iii.

"Each of the 93 students in this class owns a personal computer. Everyone who owns a personal computer can use a word processing program. Therefore, Zaidi, a student in this class, can use a word processing program." C(x) = “x is in this class” P(x) = “x owns a personal computer” W(x) = “x can use a word processing program” Premise 1 ∀x(C(x) → P(x)) Premise 2 ∀x(P(x) → W(x)) Premise 3 C(Zeke) Conclude W(Zeke) Step Reason 1 ∀x(C(x) → P(x)) Premise 1 2 C(Zeke)→ P(Zeke) Universal Instantiation on (1) 3 C(Zeke) Premise 3 4 P(Zeke) Modus Ponens on (2) and (3) 5 ∀x(P(x) → W(x)) Premise 2 6 P(Zeke)→ W(Zeke) Universal Instantiation on (5) ∴ W(Zeke) Modus Ponens on (4) and (6)

iv.

"Everyone in Shah Alam lives within 50 miles of the beach. Someone in Shah Alam has never seen the beach. Therefore, someone who lives within 50 miles of the beach has never seen the beach." J(x) = “x lives in New Jersey” O(x) = “x lives within 50 miles of the ocean” S(x) = “x has seen the ocean” Premise 1 ∀x(J(x) → O(x)) Premise 2 ∃x(J(x) ∧ ¬S(x)) Conclude ∃x(O(x) ∧ ¬S(x)) Step Reason Step Reason 1 ∃x(J(x) ∧ ¬S(x)) Premise 2 2 J(y) ∧ ¬S(y) Existential Instantiation on (1) (y is an element of the domain) 3 J(y) Simplification on (2) 4 ∀x(J(x) → O(x)) Premise 1 5 J(y) → O(y) Universal Instantiation on (4) 6 O(y) Modus Ponens on (3) and (5) 7 ¬S(y) Simplification on (2) 8 O(y) ∧ ¬S(y) Conjunction on (6) and (7) ∴ ∃x(O(x) ∧ ¬S(x)) Existential generalizing on (8) 3. For each of these arguments determine whether the argument is correct or incorrect and explain why. i. All students in this class understand logic. Daniel is a student in this class. Therefore, Daniel understands logic. ii. Every computer science major takes discrete mathematics. Nazreen is taking Discrete Structures. Therefore, Nazreen is a computer science major. iii. All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit. iv. Everyone who eats granola every day is healthy. Aminah is not healthy. Therefore, Aminah does not eat granola every day. 4. Prove that there exists a pair of consecutive integers such that one of these integers is a perfect square and the other is a perfect cube.

5. Suppose that you meet three people Aiman, Borhan, and Camelia. Can you determine what Aiman, Borhan, and Camelia are if Aiman says "All of us are knaves" and Borhan says "Exactly one of us is a knave."? 6. Suppose that on an island there are three types of people, knights, knaves, and normals (also known as spies). Knights always tell the truth, knaves always lie, and normals sometimes lie and sometimes tell the truth. Detectives

questioned three inhabitants of the island, Anis , Belinda, and Christy -as part of the investigation of a crime. The detectives knew that one of the three committed the crime, but not which one. They also knew that the criminal was a knight, and that the other two were not. Additionally, the detectives recorded these statements: Anis: "I am innocent." Belinda: "What Anis says is true." Christy: "Belinda is not a normal." After analyzing their information, the detectives positively identified the guilty party. Who was it?...