Which of the following is the principal conjunctive normal form of [(p ∨ q) ∧ ¬p] → ¬q?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. p ∨ ¬q
Explanation
(p ∨ q) ∧ ¬p ≡ ¬p ∧ q, so the implication is ¬(¬p ∧ q) ∨ ¬q ≡ p ∨ ¬q ∨ ¬q = p ∨ ¬q.
More Discrete Structures and Optimisation questions
- How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
- Match List I with List II. List I: (a) p → q, (b) p ∨ q, (c) p ∧ q, (d) ¬(p → q). List II: (i) ¬(q → ¬p), (ii) p ∧ ¬q, (iii) ¬p → q, (iv) ¬…
- Find the zero-one matrix of the transitive closure of the relation with matrix A = [1 0 1; 0 1 0; 1 1 0].
- For the LPP: maximize Z = 2x₁ − x₂ + 2x₃ subject to 2x₁ + x₂ ≤ 10, x₁ + 2x₂ − 2x₃ ≤ 20, x₁ + 2x₃ ≤ 5, x₁, x₂, x₃ ≥ 0, what is the solution…
- How many different Boolean functions of degree n are there?
- Consider the Euler's phi function given by ϕ(n) = n ∏ (1 − 1 ) p p n where runs over all the primes dividing . What ϕ(45) is the value of ?