HTSEFP: Prenex normal form

1Equivalent formulas in Prenex normal form¶

Given a formula not in Prenex normal form, find an equivalent formula that is and justify your answer.

1.1General solution¶

Use the rules mentioned in class on Wednesday, November 23.

1.1.1Tips¶

• The existential quantifier distributes over $\lor$.
• Make sure you don't have a clash of variables. To confirm, count the free variables, then count the quantifiers. The original formula and the formula in prenex form should have the same number of each, except if you use the above fact about the existential quantifier.
• Use the distributive laws to move negations inward.
• When "swallowing up" the clause on the other side of the $\land$ or $\lor$, make sure that the correct quantifier is on the outside.

1.2Examples¶

• Assignment 9, question 7
• Fall 2009 final exam, question 8
• Fall 2010 final exam, question 8