Apply equivalence laws step by step:
Final simplification: ¬(p ∧ ¬q) ∧ (p ∨ q) ≡ q.
Marking guide (15 pts, 3 pts per correct step over 5 steps).
¬(p ∧ ¬q).¬(¬q).q.¬p ∧ p ≡ c.q.Accept equivalent orderings. Equivalent if students use NOT, ~, or ∼ instead of ¬.
Build the truth table column by column. Four rows for two variables p, q:
| p | q | p → q | p ∧ (p → q) | (p ∧ (p → q)) → q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
The final column is T in every row, so the expression evaluates to true for every assignment of truth values to p and q.
(p ∧ (p → q)) → q ≡ T. The expression is a tautology.Marking guide (25 pts).
p → q and p ∧ (p → q)).T.If the table is missing entirely: 0 pts.
The tautology (p ∧ (p → q)) → q says: if both p and p → q are true, then q is true. That is exactly Modus Ponens.
Marking guide (5 pts).
p and p → q, conclusion q).Accept equivalent notations for the conclusion (∴ q, ⊢ q, "therefore q"). 0 pts if the rule name is wrong (any other rule).
If Sara passes Discrete Math, then she will register for Data Structures and she will take Algorithms.
Let p = "Sara passes Discrete Math", q = "Sara registers for Data Structures", r = "Sara takes Algorithms". The original statement is p → (q ∧ r).
Important. The negation is not a conditional (no "if…then"). It is a conjunction: the hypothesis holds and the conclusion fails.
Marking guide (20 pts, 5 pts per variation).
Must apply De Morgan to ¬(q ∧ r) when writing the contrapositive, inverse, and negation. Deduct 2 pts if missing. Accept ¬q ∨ ¬r or equivalently ¬r ∨ ¬q. The negation must not be a conditional.
D = {2, 3, 5, 6, 8}:
E(x): "x is even"P(x): "x is prime"D is even. [5 pts]D that is both even and prime. [5 pts]Rewrite the following formal statement as a complete English sentence, then determine its truth value with justification: [10 pts]
(i) Every element in D is even.
Formal: ∀x ∈ D, E(x).
Truth value: False. Counterexample: x = 3 is in D but is not even. (Also 5 works.)
(ii) There exists an element in D that is both even and prime.
Formal: ∃x ∈ D, (E(x) ∧ P(x)).
Truth value: True. Witness: x = 2 is both even (2 = 2·1) and prime.
Rewrite: ∀x ∈ D, (E(x) → P(x))
English: "For every element x in D, if x is even then x is prime."
Truth value: False. Counterexample: x = 6 is even (6 = 2·3) but is not prime (6 = 2·3). The hypothesis holds and the conclusion fails. (x = 8 is another counterexample.)
Marking guide (20 pts).
Part (i) · 5 pts:
∀x ∈ D, E(x).Part (ii) · 5 pts:
∃x ∈ D, (E(x) ∧ P(x)).x = 2).Rewrite · 10 pts:
x = 6 or x = 8).p → q.p → q is logically equivalent to its Converse?p ↔ q, write it as a conjunction of two conditional statements.p and q).D = {1, 2, 3, 4} and let P(x) be "x is a factor of 8." Write the truth set of P(x).1) Negation of p → q:
Reading: "p is true and q is false." The negation of a conditional is not itself a conditional.
2) The variation equivalent to the converse (q → p) is the Inverse:
The converse and inverse are contrapositives of each other, so they are logically equivalent.
3) The biconditional as a conjunction of two conditionals:
(p implies q) and (q implies p) read together as "p if and only if q".
4) Formal argument form of Modus Tollens:
Reading: "If p then q. Not q. Therefore not p."
5) Truth set of P(x) on D = {1, 2, 3, 4}:
Check each element. The factors of 8 are 1, 2, 4, 8. Of these, the ones in D are:
Note: 8 is a factor of 8, but 8 ∉ D, so 8 is excluded.
Marking guide (15 pts, 3 pts each).
p ∧ ¬q. Accept ¬(p → q) directly but only 1 pt if no simplification.¬p → ¬q is given without naming it.(p → q) ∧ (q → p). Accept equivalent ordering. 0 pts if disjunction or wrong connective.p → q, ¬q), 1 pt for conclusion ∴ ¬p. All three must be present for full marks.{1, 2, 4}. Deduct 1 pt if 8 is included (forgetting the domain restriction). Deduct 1 pt per wrong or missing element.