GATE 2007
March 20, 2025GATE 2007
March 20, 2025GATE 2007
|
Question 48
|
Which of the following is TRUE about formulae in Conjunctive Normal Form?
|
For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
|
|
|
For any formula, there is a truth assignment for which all the clauses evaluate to true.
|
|
|
There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true.
|
|
|
None of the above.
|
Question 48 Explanation:
For n=2, (means two variables a and b)
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1—–TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2—–TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3—–TRUE=7, FALSE=1 (7/8 ARE TRUE)
(1-2-n) are TRUE.
Looking at options,
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1—–TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2—–TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3—–TRUE=7, FALSE=1 (7/8 ARE TRUE)
(1-2-n) are TRUE.
Looking at options,
Correct Answer: A
Question 48 Explanation:
For n=2, (means two variables a and b)
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1—–TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2—–TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3—–TRUE=7, FALSE=1 (7/8 ARE TRUE)
(1-2-n) are TRUE.
Looking at options,
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1—–TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2—–TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3—–TRUE=7, FALSE=1 (7/8 ARE TRUE)
(1-2-n) are TRUE.
Looking at options,