Which of the following are tautologies?
(A) (P → (P → Q)) → (P → Q)
(B) ((P → Q) → Q) → (P ∨ Q)
(C) ((P ∨ ¬P) → Q) → ((P ∨ ¬P) → R)
(D) (Q → (P ∧ ¬P)) → (R → (P ∧ ¬P))
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (A) and (B) Only
Explanation
A: P → (P → Q) ≡ P → Q, so it is X → X. B: (P → Q) → Q ≡ P ∨ Q, so again X → X. C reduces to Q → R and D to ¬Q → ¬R, neither of which is a tautology.More Discrete Structures and Optimization questions
- Let P(x) be the statement "x = x²". If the universe of discourse is the integers, which of the following have truth value TRUE? (A) P(0) (B…
- Which of the following statements are true if the universe of discourse is the set of integers? (A) ∀n (n² ≥ 0) (B) ∃n (n² = 2) (C) ∀n (n²…
- Which of the following graphs (on vertices a–f) are trees? (A) edges: ac, bc, cd, cf, ef (B) edges: ac, af, df, ef, be (C) edges: ab, ac, a…
- Match List I with List IIList I List II (A) φ ∩ {φ} (I) φ (B) {φ} ∩ {φ} (II) {φ} (C) {φ, {φ}} − φ (III) {{φ}} (D) φ ∪ {{φ}} (IV) {φ, {φ}}
- Match List I with List II (logically equivalent expressions)List I List II (a) P ∧ (P → Q) (I) P ∨ Q (b) ¬(P ∨ Q) → (P ∧ Q) (II) (P ∧ ¬P) ∨…
- Arrange the following in ascending order: (a) Remainder of 4916 when divided by 17 (b) Remainder of 2446 when divided by 9 (c) Remainder of…