Forma prenexa

De la Viquipèdia, l'enciclopèdia lliure

Una fórmula de la lògica de predicatsforma prenexa si està escrita com a cadena de quantificadors seguits per una part sense quantificar (anomenada matriu).

Tota fórmula és equivalent a una fórmula en forma prenexa. Per exemple, si , , i són fórmules sense quantificar amb les variables lliures mostrades, llavors

és en forma normal prenexa amb la matriu , mentre que

és lògicament equivalent, però no en forma prenexa.

Conversió a forma prenexa[modifica]

Tota fórmula de primer ordre és lògicament equivalent a alguna fórmula en forma prenexa. Hi ha algunes regles de conversió que es poden aplicar recursivament per tal de convertir una fórmula a forma prenexa. Les regles depenen de quina connectiva lògica (o connectives) i quin quantificador (o quantificadors) apareguin a la fórmula.

Conjunció i disjunció[modifica]

Les regles per a la conjunció i la disjunció diuen que

és equivalent a ,
és equivalent a ;

i

és equivalent a ,
és equivalent a .

Les equivalències són vàlides quan x no apareix com a variable lliure de ψ; si x apareix lliure en ψ, ha de ser substituïda per una altra variable lliure.

Per exemple, en el llenguatge dels anells,

és equivalent a ,

però

no és equivalent a

perquè la fórmula de l'esquerra és certa en qualsevol anell quan la variable lliure x és igual a 0, mentre que la fórmula de la dreta no té variables lliures, i és falsa en qualsevol anell no trivial.

Negació[modifica]

Les regles per a la negació diuen que

és equivalent a

i

és equivalent a .

Implicació[modifica]

Hi ha quatre regles per a la implicació: dues que eliminen els quantificadors de l'antecedent, i dues més que eliminen els quantificadors del conseqüent. Aquestes regles es poden derivar tot reescrivint la implicació com a i aplicant després les regles per a la disjunció. De la mateixa manera que les regles de la disjunció, aquestes regles requereixen que la variable quantificada en una subfórmula no aparegui lliure en altra subfórmula.

Les regles per eliminar els quantificadors de l'antecedent són:

és equivalent a ,
és equivalent a .

Les regles per eliminar els quantificadors del conseqüent són:

és equivalent a ,
és equivalent a .

Exemple[modifica]

Suposem que , i són fórmules sense quantificar, i que no comparteixen cap variable lliure. Considerem la fórmula

.

Si apliquem recursivament les regles començant per les subfórmules internes, hom pot obtenir la següent seqüència de fórmules lògicament equivalents:

.

Aquesta no és l'única forma prenexa equivalent a la fórmula original. Per exemple, si transformem el conseqüent abans que l'antecedent, hom pot obtenir la forma prenexa

amb els següents passos:

.

Lògica intuïcionista[modifica]

Les regles per convertir una fórmula a una altra en forma prenexa fa feixuc el maneig de la lògica clàssica. En lògica intuïcionista no és sempre cert que tota fórmula sigui lògicament equivalent a una altra en forma prenexa. La negació d'una connectiva és un obstacle, però no pas l'únic. La implicació també rep un tractament diferent en lògica intuïcionista que en lògica clàssica; en lògica intuïcionista, no és definible mitjançant la negació i la disjunció.

Ús de la forma prenexa[modifica]

Alguns sistemes lògics només poden tractar amb una teoria que tingui les fórmules escrites en forma normal prenexa.

Aquest concepte és essencial per tal de desenvolupar la jerarquia aritmètica i la jerarquia analítica.

La demostració de Gödel del seu teorema de completesa per a la lògica de primer ordre pressuposa que totes les fórmules estan reescrites en forma normal prenexa.

Vegeu també[modifica]

Bibliografia[modifica]

  • Hinman, Peter G. Fundamentals of mathematical logic. Wellesley, Mass.: A.K. Peters, 2005. ISBN 978-1-56881-262-5.