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?
$$(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.