Converting From First-order Logic
To convert first-order logic to CNF:
- Convert to negation normal form.
- Eliminate implications: convert to
- Move NOTs inwards by repeatedly applying DeMorgan's Law. Specifically, replace with ; replace with ; and replace with .
- Standardize variables
- For sentences like (∀x P(x)) ∨ (∃x Q(x)) which use the same variable name twice, change the name of one of the variables. This avoids confusion later when we drop the quantifiers. For example, from ∀x ∨ . we obtain: ∀x ∨ .
- Skolemize the statement
- ∃x P(x) into P(A), where A is a new constant (consult linked article for more details)
- Drop universal quantifiers
- Distribute ORs over ANDs.
Read more about this topic: Conjunctive Normal Form
Famous quotes containing the words converting and/or logic:
“A way of certifying experience, taking photographs is also a way of refusing itby limiting experience to a search for the photogenic, by converting experience into an image, a souvenir. Travel becomes a strategy for accumulating photographs.”
—Susan Sontag (b. 1933)
“Neither Aristotelian nor Russellian rules give the exact logic of any expression of ordinary language; for ordinary language has no exact logic.”
—Sir Peter Frederick Strawson (b. 1919)
Related Phrases
Related Words