CMPS 211 Homework 1 Solution, Fall 2015

American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 15/16 Please solve the following exercises and submit BEFORE 11:55 p.m. of Friday 18 September. Exercise 1 (10 points) Which of these are propositions? What are the truth values of those that are propositions? a) The north pole is hot. Proposition - False b) When is the closest holiday? Not a proposition c) , for all z Proposition - True d) Do not pass! Just go! Not a proposition e) In CMPS 211, there is no raise Proposition. True if there’s no raise, false otherwise. Exercise 2 (10 points) Let f, e, and h be the propositions  f : You eat healthy food  e : You exercise regularly  h : You are in good health Write these propositions using f, e, and h and logical connectives (including negations). a) If you aren’t in good health, then you either don’t eat healthy food, or you don’t exercise regularly. ¬h →(¬f ∨ ¬e) b) You neither eat healthy food, nor you exercise regularly, and you aren’t in good health ¬f ∧ ¬e ∧ ¬h c) To exercise regularly, it is necessary that you eat healthy food e →f d) Exercising regularly is sufficient for being in good health e →h e) If you aren’t in good health, then you don’t eat healthy food, and if you don’t eat 2 healthy food, then you can’t exercise regularly. (¬h →¬f) ∧ (¬f →¬e) Exercise 3 (10 points) Determine whether these bi-conditionals are true or false. f) if and only if is defined true g) 5*5=25 if and only if 1-1=2. false h) (p∨¬p ) ↔ Bananas are yellow; true Exercise 4 (10 points) Let p and q be the propositions  d: I do my assignments on my own  p: I pass my courses Express each of these propositions as an English sentence. i) p→d if I pass my courses then I’ve done my assignments on my own j) ¬d∧¬p I don’t do my assignments on my own and I don’t pass my courses k) ¬d∨(d∧p) I either don’t do my assignment on my own, or I do my assignments on my own and I pass my courses Exercise 5 (10 points) For each of these sentences, determine whether an inclusive or, or an exclusive or, is intended. Explain your answer. a) To enter the country you need a passport or a voter registration card. inclusive b) You can pick Section 1 or Section 2 exclusive c) You either own a Samsung or an iPhone inclusive 3 d) You either get a full grade or you have some mistake exclusive Exercise 6 (10 points) State the converse, contrapositive, and inverse of each of these conditional statements. a) If you solve it fast, then it’s wrong p: solve fast, q: its wrong converse: if it’s wrong, then you’ll solve it fast contrapositive: if its not wrong, then you won’t solve it fast inverse: if you aren’t solving it fast, then it’s not wrong b) To stay healthy, it’s sufficient to drink milk p: drink milk, q: stay healthy converse: if you are healthy then you drink milk contrapositive: if you aren’t healthy then you don’t drink milk inverse: if you don’t drink milk then you aren’t healthy c) When I wake up late, it is necessary that I have a full day headache p: I wake up late, q: I have a full day headache converse: If I have a full day headache, then I woke up late contrapositive: If I didn’t have a full day headache, then I didn’t wake up late inverse: if I don’t wake up late, I won’t have a full day headache Exercise 7 (10 points) Construct a truth table for each of these compound propositions. a) ¬p→¬q b) p↔(¬p∧ q) c) (¬p∨¬q)→p d) (¬p→¬q)↔( q→p) e) (p↔q) XOR (p↔¬q) p q ¬p ¬q ¬p→¬q ¬p∧ q p↔(¬p∧ q) (¬p∨¬q) (¬p∨¬q)→p ( q→p) (¬p→¬q) ↔( q→p) (p↔q) (p↔¬q) (p↔q) XOR (p↔¬q) 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 Exercise 8 (10 points) What is the value of x after each of these statements is encountered in a computer 4 program, if x = -1 before the statement is reached? a) if x - 3 < 0 then x := (x+1)/2 +1 if -1 - 3 < 0 then x := (-1+1)/2 +1, true  x = 1 b) if (2x +2 =3) OR (3x +1 = 3) then x := x*2 if (2(-1) +2 =3) OR (3(-1) +1 = 3) then x := -1*2, false  x = -1 c) if (x + 3 = 2) AND (3x +4 = -1) then x := x-2 if (-1 + 3 = 2) AND (3(-1) +4 = -1) then x := x-2, false  x = -1 d) if (x > x) XOR (x < x) then x := x+2 if (-1 > -1) XOR (-1 < -1) then x := -1+2, false  x = -1 e) if x < 2 then x := x mod 2 –mod is the modulus function if -1 < 2 then x := -1 mod 2, true  x = 1 Exercise 9 (20 points) Fuzzy logic is used in artificial intelligence. In fuzzy logic, a proposition has a truth value that is a number between 0 and 1, inclusive. A proposition with a truth value of 0 is false and one with a truth value of 1 is true. Truth values that are between 0 and 1 indicate varying degrees of truth. For instance, the truth value 0.3 can be assigned to the statement “Tarek is sick” because Tarek is sick slightly less than half the time, and the truth value 0.9 can be assigned to the statement “Reem is hungry” because Reem is hungry most of the time. Use these truth values to solve the following exercises. a) The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition. What are the truth values of the statements “Tarek is not sick”, and “Reem is not hungry?” Tarek is not sick = 1-0.3 = 0.7 Reem is not hungry = 1-0.9 = 0.1 b) The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions. What are the truth values of the statements “Tarek is sick and Reem is hungry” and “Tarek is not sick but Reem is hungry?” Tarek is sick and Reem is hungry = min(0.3, 0.9) = 0.3 Tarek is not sick but Reem is hungry = min(0.7, 0.9) = 0.7 c) The truth value of the disjunction of two propositions in fuzzy logic is the maximum of the truth values of the two propositions. What are the truth values of the statements “Tarek is sick, or Reem is not hungry” and “Tarek is not sick, or 5 Reem is not hungry?” Tarek is sick, or Reem is not hungry = max(0.3, 0.1) = 0.3 Tarek is not sick, or Reem is not hungry = max(0.7, 0.1) = 0.7