Lògica de predicats

La lògica de predicats consisteix a fer derivacions amb les regles bàsiques i amb regles derivades i a més suposa un domini previ de la lògica proposicional o d'enunciats, així que abans de provar aquest lògica heu d'anar a practicar la lògica d'enunciats primer. Per què es proposa una lògica de predicats, quan en teníem una d'enunciats prou ben definida? Doncs perquè la lògica d'enunciats no aprofundeix prou i no sap decidir en alguns casos com el següent:

1. Tot grec és europeu.
2. Tot atenenc és grec.
3. ⊦ Tot atenenc és europeu.
   

Nomenclatura

• $\bigwedge$= quantificador universal
• $\bigvee$= quantificador particular.
• Px= predicat d'una variable qualsevol 'x'.
• Qy= predicat d'una variable qualsevol 'y'.

$\vdash$= símbol de la conclusió.

Regles bàsiques de la lògica de predicats

Regla d'introducció de generalitzador, IG

Pa

———

$\bigwedge$xPx

Explicació

Per a introduir un generalitzador com "TOT x té aquesta propietat P" podem començar simplement per un paràmetre o individu concret que té una propietat P, com per exemple, "el meu cotxe és roig" que es representa per Ra, on R és tenir la propietat de ser roig (roig és el predicat) i el meu cotxe seria el paràmetre o l'individu concret. Aquesta regla diu simplement que el paràmetre amb una propietat concreta pot esdevenir una generalització, així posem que tot, representat per aquest símbol $\bigwedge$, x, que seria una variable qualsevol susceptible de ser substituïda per un paràmetre, té una determinada propietat P. Senzillament vol dir que

Regla d'eliminació de generalitzador, EG

$\bigwedge$xPx

———

Pa

Regla d'introducció de particularitzador, IP

Pa

———

$\bigvee$xPx

Regla d'eliminació del particularitzador, EP

$\bigvee$xPx

$\lceil$Pa

$\mid$ -

$\mid$ -

$\mid$ -

$\mid$ -

$\lfloor$A

———

A

$\quad$

Mètode de derivació natural amb quantificadors

- 1 $\bigwedge$x(Rx → Px)
- 2 $\bigwedge$x(Px → $\neg$Sx)
- 3 $\bigwedge$x(Rx∧Qx → Sx)

⊦$\bigwedge$x(Rx→$\neg$(Px→Qx))

4 Ra→Pa			EG1
5 Pa → $\neg$Sa			EG 2
6 Ra∧ Qa → Sa			EG 3
$\lceil$ 7 Ra
$\mid$ 8 Pa			MP 4,7
$\mid$ 9 $\neg$Sa			MP 5,8
$\mid$ 10 $\neg$(Ra ∧ Qa)			MT 6,9
$\mid$ 11 Ra→ $\neg$Qa			DI 10
$\mid$ 12 $\neg$Qa			MP 11,7
$\mid$ 13 Pa ∧ $\neg$Qa			Prod 8,12
$\lfloor$ 14 $\neg$ (Pa → Qa)			Di 13
15 Ra → $\neg$(Pa → Qa)			TD 7-14
16 $\bigwedge$x(Rx → $\neg$(Px → Qx))			IG 15

Fet!

Explicació de la derivació de quantificadors anterior

Tenim tres premisses anteriors i anem a comprovar la validesa de la conclusió i a vore si és certa o no i a més les premisses ens han de portar a la conclusió. Per a començar hem d'eliminar els quantificadors, per això apliquem a les premisses la regla d'eliminació del quantificador general, que realment destorba per a fer les derivacions. Aquesta regla d'eliminació del generalitzador està explicada en aquesta pàgina. Procedim a fer el mateix en les dues següents premisses. A partir d'aquí és quan es complica més. Ara hem de veure la conclusió i quin és el connector que domina. En aquest cas és l'implicador per la qual cosa hem de començar en la següent línia per una introducció a l'implicador II o l'anomenat teorema de deducció TD que té la següent forma:

$\lceil$ A

$\mid$ -

$\mid$ -

$\lfloor$ B

———

A → B

El lector atent ja s'haurà adonat que la A és un formalisme susceptible de ser canviat per altra proposició com Pa, la qual funciona com un supòsit, com diu la regla d'introducció a l'implicador, suposem que existeix una proposició tal Pa que ens permeta començar a fer la derivació, si tot va bé ens ha de portar aquest supòsit Pa, el qual hem tret de la conclusió aplicant implícitament l'eliminació del generalitzador o quantificador universal $\bigwedge$, a la següent proposició de la conclusió $\neg$ (Px → Qx), que és justament el que hem de trobar en les premises aplicant regles bàsiques, regles derivades o definicions de quantificadors, segons els casos.

El següent pas és aplicar la regla bàsica MP en les línies 4 i 7, que dona com a resultat Pa de la línia 8.
En la següent línia 9 tenim el mateix cas i hem d'aplicar la mateixa regla, en línies 5, 8 obtenint $\neg$Sa. El claudàtor que hem obert en la línia 7 no el podem tancar fins que no trobem el conseqüent de la implicació de la conclusió que és la següent proposició:$\neg$ (Px → Qx).

La línia 10 $\neg$ (Ra $\wedge$ Qa) s'ha tret de l'aplicació d'una regla derivada el modus tollens MT en línies 6 i 9.

La línia 11 s'ha tret d'aplicar la regla de la definició de l'implicador DI però invertida, perquè tenim un conjuntor de Ra i Qa que està negat, per tant aplicant la regla de la definició de l'implicador que diu el següent:
A $\rightarrow$B
=======
$\neg$(A$\wedge$$\neg$B)
Les línies paral·leles de la fórmula signifiquen que la regla es pot usar en els dos sentits de la derivació, tant de dalt cap a avall com de baix cap a dalt, igual com funciona un connector bicondicional o coimplicador Arxivat 2012-02-18 a Wayback Machine.. Però com tenim el conjuntor negat, el resultat serà que el conseqüent ha de mantenir el negador donant com a resultat Ra → $\neg$Qa. La línia 12 es treu per Modus Ponens MP en línies 11 i 7 i traiem el $\neg$Qa. En línia 13 ja podem fer un producte, Prod, en línies 8 i 12. En la línia 14 es trau altr cop per la regla de definició de l'implicador DI, aplicada en 13, que passa el mateix que en la línia 11 amb el negador que està invertit donant com a resultat $\neg$ (Pa → Qa), que és el conseqüent de la implicació de la conclusió.
En la línia 15 ja podem tancar el claudàtor que havíem obert amb un supòsit donat com a resultat Ra → $\neg$(Pa → Qa), tancant així el teorema de deducció o TD des de les línies 7 a la 14.

Per acabar, a la línia 16 ja introduïm la regla del generalitzador exposada en aquesta mateixa pàgina que diu que davant de qualsevol paràmetre a, amb diferents propietats P, Q o R es pot fer una generalització amb un quantificador per a qualsevol variable x, donant ja la conclusió que buscàvem: $\bigwedge$x(Rx → $\neg$(Px → Qx))

Referències

.