Talk:Prenex normal form

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Mid Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
Explanation, motivation and references would help. Geometry guy 22:37, 9 June 2007 (UTC)

Is the first formula correct ?

Yes. Either Q or not Q. If Q, then anything implies Q, so in particular, the LHS is true, and ∃xP(x) implies Q, so LHS=RHS. If not Q, then both sides reduce to "P never holds" (i.e. there is no x such that P(x)), so again they must be equal. greenrd 01:42, 2 May 2006 (UTC)

1 Article Title
2 Question
3 first schemata
4 Expansion of content
5 Rules that do not hold in intuitionistic logic

[edit] Article Title

I am curious as to whether or not the "normal" used in this articles title is misplaced. The form the article details converting terms to doesn't seem to correspond to what would normally be considered a normal form (by the current process formulas can correspond to several prenex "normal" form terms). Is this not just prenex form, with prenex conjuntive/disjunctive normal forms being special cases? --Luke.mccrohon (talk) 14:43, 23 January 2008 (UTC)

[edit] Question

Does someone know where the name comes from?

[edit] first schemata

I don't understand the first schemata given as an example here. Isn't the quantifier on the far left in both forms? Are the parentheses important here? -- Creidieki 15:35, 21 November 2006 (UTC)

No, it isn't "on the far left" in both forms, and yes, parentheses are important here. --greenrd 03:12, 27 November 2006 (UTC)

[edit] Expansion of content

This page has scope for expansion in the following areas:

A proof of the assertion that all formulas are logically equiv to some formula in PNF.
A demonstration of how a formula can be 'converted' into PNF.

reetep 12:32, 1 December 2006 (UTC)

The work here outstrips the time available to do it. Even if you don't think it will be perfect, making a first set of edits yourself will probably draw others here to polish them up. CMummert 13:54, 1 December 2006 (UTC)

What do you mean when you say that the work required outstrips the time available? Wikipedia is a work in progress with no project deadlines. reetep 12:29, 4 December 2006 (UTC)

I mean that other people (like me) have also noticed that this article needs improvement, but such a large number of articles need improvement, relative to the amount of time per week that is spent editing them, that it may be a long time before articles like this get attention. So if you have some experience with this topic, and would like to see the article expanded, you can't do any harm by starting the improvements yourself. CMummert 13:17, 4 December 2006 (UTC)

[edit] Rules that do not hold in intuitionistic logic

Maybe we could add the list of the rules for converting a formula to prenex form that do fail in intuitionistic logic. I think that they are:

(1) $\forall x (\phi \lor \psi)$ implies $(\forall x \phi) \lor \psi$ ,

(2) $\forall x (\phi \lor \psi)$ implies $\phi \lor (\forall x \psi)$ ,

(3) $(\forall x \phi) \rightarrow \psi$ implies $\exists x (\phi \rightarrow \psi)$ ,

(4) $\phi \rightarrow (\exists x \psi)$ implies $\exists x (\phi \rightarrow \psi)$ ,

(5) $\lnot \forall x \phi$ implies $\exists x \lnot \phi$ ,

(x does not appear as a free variable of $\,\psi$ in (1) and (3); x does not appear as a free variable of $\,\phi$ in (2) and (4)). Jayme 10:41, 30 June 2007 (UTC)