2

Without using truth tables, show that the statements

  • ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and
  • ‘If you did all assignments but did not get an A in Discrete Math, then you either did not do all problems in the book or did not attend all lectures’

are logically equivalent.

Hint: first translate the given sentences to compound propositions.

My solution

Let A be the proposition ‘you did all problems in the book,’ B be the proposition ‘you attended all lectures,’ C be the proposition ‘you completed all assignments’ and D be the proposition ‘you got an A in Discrete Maths.’

Therefore, ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ translates to (A AND B AND C) IMPLIES D and ‘If you did all assignments but did not get an A in Discrete Math, then you either did not do all problems in the book or did not attend all lectures’ translates to [A AND (NOT D)] IMPLIES [(NOT)B OR (NOT)C].

(A AND B AND C) IMPLIES D = [NOT (A AND B AND C)] OR D = [ (NOT A) OR (NOT B) OR (NOT C)] OR D = [(NOT A) OR D] OR [(NOT B) OR (NOT C)] = [NOT (A AND (NOT D))] OR [(NOT B) OR (NOT C)] = [A AND (NOT D)] IMPLIES [(NOT)B OR (NOT)C]

Do you think my answer is correct?

hullahmullah
  • 21

1 Answers1

1

There's a small mistake there, “If you did all assignments but did not get an A in Discrete Math, then you either did not do all problems in the book or did not attend all lectures” translates to “$\small\rm (C\land \lnot\, D)\Rightarrow(\lnot\, A\lor\lnot\, B)$” rather than “$\small\rm (A\land \lnot\, D)\Rightarrow(\lnot\, C\lor\lnot\, B)$”, but this wont have any consequence on the result since interchanging $\small\rm A,B,$ and $\small\rm C$ will yield basically the same thing. In any case, I changed your proof so that it yields the requested result:

$$\small\begin{align} \mathrm{(A \land B \land C) \Rightarrow D} & \equiv \mathrm{ \big(\lnot\, (A \land B \land C)\big) \lor D} \\ & \equiv \mathrm{ \big( (\lnot\, A) \lor (\lnot\, B) \lor (\lnot\, C)\big) \lor D} \\ & \rm \equiv \big((\lnot\, C) \lor D\big) \lor \big((\lnot\, A) \lor (\lnot\, B)\big) \\ & \equiv \mathrm{\big(\lnot\, (C \land (\lnot\, D))\big) \lor \big((\lnot\, A) \lor (\lnot\, B)\big)} \\ & \equiv\mathrm{ \big(C \land \lnot\, D\big)\Rightarrow \big(\lnot\, A \lor \lnot\, B\big)}.\tag*{$\square$} \end{align}$$

Workaholic
  • 6,763