Question

COMP1805AB (Fall 2019)  "Discrete Structures I" Specification for Assignment 1 of 4

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

1. Translate the following English expressions into logical statements. You must explicitly state what the atomic propositions are (e.g., "Let p be proposition ...") and then show their logical relation.

   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. Show all your work and do not skip any steps (i.e., ensure you that you include a new column for every single operation and that you state at the end whether each expression is a tautology, contingency, or contradiction).

   a. ¬(?∧(¬?∨(?→?)))
   b. (? ∨(? ↔(¬?∧ (? ∨?))))

   c. (? ∧¬(? ∧(? ∨(? ↔?))))d. ¬(?∨¬(?→(?∧?)))

3. Determine if the following expressions are tautologies, contradictions, or contingencies by using only the logical equivalences. 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 at the end whether each expression is a tautology, contingency, or contradiction).

   a. (? ∧(? →¬?))b. (¬?→(?∨?))c. (? ↔(?∨ ¬?))d. (¬? ∨(?∧?))

4. Using only the  and the  operators, find a logical expression that is equivalent to (? → (? ∧ p)) → (? ∨ p). For this question, you do not need to specify "how" you found the equivalent expression because you will show both techniques in questions 5 and 6 below.

5. Prove that the expression you found for question 4 above is equivalent to the expression (? → (? ∧ p)) → (? ∨ p) by using only truth tables. Show all your work and do not skip any steps (i.e., ensure that you include a new column for every single operation).

6. Prove that the expression you found for question 4 above is equivalent to the expression (? → (? ∧ p)) → (? ∨ p) by using only the logical equivalences. Show all your work and do not skip any 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 of discourse is all animals.

   1. ∀? (?(?) ∧ ?(?))

   2. ∃? (¬(?(?) ∧ ?(?)) ∨ ¬?(?))

   3. ∀? ((?(?) ∨ ?(?)) → (¬?(?) → ?(?)))

Answer 1