In: Statistics and Probability
Find a prenex normal form for the following wff. ∃x p(x) ∧ ∃x q(x) → ∃x (p(x) ∨ q(x))
Solution :
Algorithm for prenex normal form :
Any expression can be converted into prenex normal form. To do this,the following steps are needed:
1.Eliminate all occurrences of and from the formula in question.
2.Move all negations inward such that ,in the end,negations only appear as part of literals.
3.Standardize the variables apart(when necessary).
4.The prenex normal form can now be obtained by moving all quantifiers to the front of the formula.
Given that :
Given formula,
1. According to step-1,we must eliminate,which yields :
The formula does not contain '',so the modified formula is,
2. According to step-2, we move negation inwards,which yields;
3.Next,all variables are standardized apart :
4. We can now move all quantifiers in front, which yields :