I'm preparing for an undergraduate Discrete Mathematics Term test. It seems the exam format includes multiple choice questions(MCQ) and open ended proofs and some of the MCQ surprisingly take up a lot of time. I want to optimise my time for the tougher, rigorous proof questions.

This is an example of a question. Note that $\sim$ means the negation of.

Which of the following are tautologies?

$(I) \sim (p \lor q) \lor [(\sim p) \land q] \lor p$

$(II) [(p \to q) \land (r \to s) \land (p \lor r)] \to (q \lor s) $

$(III) (p \to r) \land (q \to r) \to [(p \lor q) \to r] $

A. None of (I), (II) or (III).

B. (I) and (II) only.

C. (I) and (III) only.

D. (II) and (III) only.

E. All of (I), (II) and (III). (Answer)

I solved it by converting them (on either side of the compound eqn) some form of equations I know of, if not I try to apply some laws/truth table. The second alternative definitely feels super time consuming and may cause me to get careless under time pressure. A good friend of mine said these things come a lot from intuition, but I don't believe I have it. He also used things like

$(p \land r) \to (p \land q)$ is logically equivalent to $(p \land r) \to q$

and $(p \lor q) \to r$ is logically equivalent to $(p \to r) \land (q \to r)$

and $(p \lor q) \to \sim r$ is logically equivalent to $(p \lor r) \to \sim q$

and we can apply $d \land$ on both sides of the compound proposition $(a \lor b) \to c)$ to get $d \land (a \lor b) \to d \land c$

all of which are not obvious to me at first sight until after he gave me an analogy.

Some other questions will be "Which of the following are logical equivalent", haven't found a good question to show here yet. Does anyone have advice on what to do regarding such problems? Should I keep a library of commonly use proposition logic and their equivalence, negations and what tricks can be applied. If so, where and how can I get them?

  • $\begingroup$ Basically only two ways : either truth table (quite fast with only 2 or 3 prop variables) or reduce them to simpler form by way of rules of equiv. $\endgroup$ Sep 27 '18 at 14:32
  • $\begingroup$ Do u mind showing how u would do up a Truth table quickly? For things like (II) I think I would require around 10 columns? $\endgroup$ Sep 27 '18 at 14:34
  • $\begingroup$ For the first one, for example, $p \vee \neg p \wedge q$ simplifies to $p \vee q$. Therefore $I$ is clearly a tautology of the form $A \vee \neg A$. $\endgroup$ Sep 27 '18 at 14:55
  • $\begingroup$ For the second, if $p \vee r$ is true, then either $q$ or $s$ must be true because of the two implications inside the square brackets. Another tautology. $\endgroup$ Sep 27 '18 at 14:58
  • $\begingroup$ for (II) $q$ TRUE than $(q \lor s)$ is TRUE than formula is TRUE. Thus, consider the case $q$ FALSE. $\endgroup$ Sep 27 '18 at 15:00

I am afraid there is no shortcut.

A systematic way is by filling truth tables, but alas for more than four variables this becomes impractical.

  • $\begingroup$ Do you mind doing up the truth table for (II)? $\endgroup$ Sep 27 '18 at 15:32
  • 1
    $\begingroup$ I'd rather say that there is no known shortcut that will work in general. While tautology is coNP-complete, there are many tautologies with short resolution proofs. $\endgroup$ Sep 27 '18 at 15:35
  • $\begingroup$ @FabioSomenzi could you get into a room with me for discussion? Though it's a first time using it. $\endgroup$ Sep 27 '18 at 15:41
  • $\begingroup$ @PrashinJeevaganth: yes, I do, sorry. $\endgroup$
    – user65203
    Sep 27 '18 at 16:08

$$(I) \sim (p \lor q) \lor [(\sim p) \land q] \lor p$$

If $p$ is true the third component is true.

If $ p $ is false and $q$ is true the second component is true.

If both $p$ and $q$ are false then the first component is true.

$$(II) [(p \to q) \land (r \to s) \land (p \lor r)] \to (q \lor s)$$

From $(p\lor q) $, one of $p$ or $r$ is true.

Thus from $(p \to q) \land (r \to s)$ we deduct that one of $q$ or $s$ is true, therefore $(q \lor s)$ is true.

$$(III) (p \to r) \land (q \to r) \to [(p \lor q) \to r]$$

If either $p$ or $q$ is true then from $(p \to r) \land (q \to r)$ we deduct that $r$ is true.

  • $\begingroup$ I don't understand the line "Thus from ..." and u have a typo error on the "from $(p \lor q)$ line" $\endgroup$ Sep 27 '18 at 15:06
  • $\begingroup$ $p$ implies $q$ and $r$ implies $s$ therefore if one of $p$ or $r$ is true, then one of $q$ or $s$ must be true. $\endgroup$ Sep 27 '18 at 15:10
  • $\begingroup$ When you meant one of q or s, do u mean the XOR or do u mean inclusive OR? Also, are q and s meant to be booleans to be set? When doing the full truth table we would have to set it, but this case I observe that you always assume true, why is that so? $\endgroup$ Sep 27 '18 at 15:14
  • $\begingroup$ The or is inclusive. I did not understand your second question. $\endgroup$ Sep 27 '18 at 15:24
  • $\begingroup$ I only learnt truth tables to be used to test whether 2 statements are logically equivalent. Say prove A \lor B \to C is logically equivalent to D \lor E \to F, then I would need a truth table for 6 columns of A to F at minimum and shown that there isn't any critical row. However, from what I see now you are making a claim of "If one of p or r is true", how are you so sure that q or s must be true? Don't u set these possibilities and assumptions in the truth table as I have mentioned? $\endgroup$ Sep 27 '18 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.