Computer-Organization
October 5, 2023Computer-Organization
October 5, 2023Engineering-Mathematics
| Question 19 |
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
| ∃x(p(x) → W) ≡ ∀x p(x) → W | |
| ∀x(p(x) → W) ≡ ∀x p(x) → W
| |
| ∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W | |
| ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W |
~p→q ≡ ~p∨q
Demorgan laws:
~(∀x(a(x)) ≡ ∃x~a(x)
~(∃x(a(x)) ≡ ∀x~a(x)
(A) ∃x(p(x)→w) ≡ ∀x p(x)→w
LHS: ∃x(p(x)→w) ≡ ∃x(~p(x)∨w)
≡ ∃x(~p(x))∨w
Demorgan’s law:
~(∀x(a(x)) = ∃x ~ a(x)
≡ ~(∀x P(x)) ∨ w
≡ (∀x) P(x) → w ≡ RHS
It’s valid.
(B) ∀x(P(x) → w) ≡ ∀x(~P(x) ∨ w)
≡ ∀x(~P(x)) ∨ w
≡ ~(∃x P(x)) ∨ w
≡ ∃x P(x) → w
This is not equal to RHS.
(C) ∃x(P(x) ∧ w) ≡ ∃x P(x) ∧ w
‘w’ is not a term which contains x.
So the quantifier does not have any impact on ‘w’.
Thus it can be written as
∃x(P(x)) ∧ w) ≡ ∃x P(x) ∧ w
(D) ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
‘w’ is not a term which contains ‘x’.
So the quantifier does not have an impact on ‘w’.
Thus ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
~p→q ≡ ~p∨q
Demorgan laws:
~(∀x(a(x)) ≡ ∃x~a(x)
~(∃x(a(x)) ≡ ∀x~a(x)
(A) ∃x(p(x)→w) ≡ ∀x p(x)→w
LHS: ∃x(p(x)→w) ≡ ∃x(~p(x)∨w)
≡ ∃x(~p(x))∨w
Demorgan’s law:
~(∀x(a(x)) = ∃x ~ a(x)
≡ ~(∀x P(x)) ∨ w
≡ (∀x) P(x) → w ≡ RHS
It’s valid.
(B) ∀x(P(x) → w) ≡ ∀x(~P(x) ∨ w)
≡ ∀x(~P(x)) ∨ w
≡ ~(∃x P(x)) ∨ w
≡ ∃x P(x) → w
This is not equal to RHS.
(C) ∃x(P(x) ∧ w) ≡ ∃x P(x) ∧ w
‘w’ is not a term which contains x.
So the quantifier does not have any impact on ‘w’.
Thus it can be written as
∃x(P(x)) ∧ w) ≡ ∃x P(x) ∧ w
(D) ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
‘w’ is not a term which contains ‘x’.
So the quantifier does not have an impact on ‘w’.
Thus ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w