COMP1805AB (Fall 2019) ? "Discrete Structures I" Specificationfor Assignment 1 of 4

Please ensure that you include your name and student number onyour submission. Your submission must be created using MicrosoftWord, Google Docs, or LaTeX.

1. Translate the following English expressions into logicalstatements. You must explicitly state what the atomic propositionsare (e.g., "Let p be proposition ...") and then show their logicalrelation.

   1. If it is red then it is not blue and it is not green.

   2. It is white but it is also red and green and blue.

   3. It is black if and only if it is not red, green, or blue.

2. Determine if the following expressions are tautologies,contradictions, or contingencies by using only truth tables. Showall your work and do not skip any steps (i.e., ensure you that youinclude a new column for every single operation and that you stateat the end whether each expression is a tautology, contingency, orcontradiction).

   a. ¬(??(¬??(???)))
   b. (? ?(? ?(¬?? (? ??))))

   c. (? ?¬(? ?(? ?(? ??))))d. ¬(??¬(??(???)))

3. Determine if the following expressions are tautologies,contradictions, or contingencies by using only the logicalequivalences. Show all your work and do not skip any steps (i.e.,ensure you that you include the name of each equivalence used(excluding commutativity and associativity) and that you state atthe end whether each expression is a tautology, contingency, orcontradiction).

   a. (? ?(? ?¬?))b. (¬??(???))c. (? ?(?? ¬?))d. (¬? ?(???))

4. Using only the ? and the ? operators, find a logical expressionthat is equivalent to (? ? ?(? ? ?p)) ? (?? ? p). For thisquestion, you do not need to specify "how" you found the equivalentexpression because you will show both techniques in questions 5 and6 below.

5. Prove that the expression you found for question 4 above isequivalent to the expression (? ? ?(? ? ?p)) ? (?? ? p) by usingonly truth tables. Show all your work and do not skip any steps(i.e., ensure that you include a new column for every singleoperation).

6. Prove that the expression you found for question 4 above isequivalent to the expression (? ? ?(? ? ?p)) ? (?? ? p) by usingonly the logical equivalences. Show all your work and do not skipany steps.

7. Let L(x) be the predicate "x is a lion", G(x) be the predicate"x is a giraffe", and M(x) be the predicate "x eats meat".Translate the following expressions into English. The universe ofdiscourse is all animals.

   1. ?? (?(?) ? ?(?))

   2. ?? (¬(?(?) ? ?(?)) ? ¬?(?))

   3. ?? ((?(?) ? ?(?)) ? (¬?(?) ? ?(?)))