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,