Lògica proposicional

La lògica proposicional és una branca de la lògica clàssica que estudia les proposicions o sentències lògiques, les seves possibles avaluacions de veritat i, en el cas ideal, el seu nivell absolut de veritat. Les seves constants lògiques, anomenades connectives lògiques, representen operacions sobre proposicions, capaces de formar altres proposicions de complexitat superior.

Les lògiques proposicionals manquen de quantificadors o de variables d'individu, però tenen variables proposicionals (és a dir, que es poden interpretar com proposicions amb un valor de veritat definit), és per això que es diuen proposicionals. Els sistemes de lògica proposicional inclouen a més connectives lògiques, i per això dins d'aquest tipus de lògica es pot analitzar la inferència lògica de proposicions a partir de proposicions, però sense tenir en compte l'estructura interna de les proposicions més simples.

Com que les lògiques proposicionals no tenen quantificadors o variables d'individu, qualsevol seqüència de signes que constitueixi una fórmula ben formada admet una valoració sobre si la proposició és verdadera o falsa depenent del valor de veritat assignat a les proposicions que la componen. Això implica que qualsevol fórmula ben formada defineix una funció proposicional. Per tant, qualsevol sistema lògic basat en la lògica proposicional és decidible i en un nombre finit de passos es pot determinar la veritat o falsedat semàntica d'una proposició. Això fa que la lògica proposicional sigui completa i amb una semàntica molt senzilla.

A diferència de la lògica de primer ordre, la lògica proposicional no s'ocupa d'objectes no lògics, predicats sobre ells o quantificadors. Tanmateix, tota la maquinària de la lògica proposicional s'inclou a la lògica de primer ordre i a les lògiques d'ordre superior. En aquest sentit, la lògica proposicional és el fonament de la lògica de primer ordre i de la lògica d'ordre superior.

Història

La lògica és coneguda com una de les ciències més antigues. Tant és així que Aristòtil és considerat el pare fundador d'aquesta disciplina, atès que va ser el primer en tractar amb tot detall la lògica. En un principi, aquesta ciència es va anomenar Analítica, però més tard els escrits d'Aristòtil relatius a la lògica que van ser recopilats pels seus deixebles van rebre el nom d'Òrganon, ja que consideraven que la disciplina en qüestió constituïa un instrument per al coneixement de la veritat.

Aristòtil es va plantejar com és possible comprovar i demostrar que un coneixement és veritable, és a dir, que té una validesa universal. Finalment va trobar el fonament de la demostració en la deducció, procediment que consisteix en derivar un fet particular a partir d'un d'universal.

Malgrat que la lògica proposicional havia estat insinuada per alguns dels filòsofs anteriors, va ser desenvolupada en una lògica formal per Chrysippus durant el segle iii aC i ampliada posteriorment pel seu successor estoics. La lògica proposicional, tal com el seu nom indica, es basava en proposicions, característica que la diferenciava de la lògica sil·logística tradicional, la qual se centrava en els termes. Tot i així, més endavant la lògica proposicional desenvolupada pels estoics no resultava comprensible, i per aquest motiu el sistema va ser reinventat essencialment per Pedro Abelardo al segle xii.

La lògica proposicional va ser finalment refinada mitjançant la lògica simbòlica, el fundador de la qual va ser el matemàtic Gottfried Leibniz (segles XVII - XVIII). Malgrat ser un dels primers en treballar el càlcul, era desconegut per la majoria de la comunitat lògica, fet que va suposar que molts dels avanços que va aconseguir fossin recreats per lògics com ara George Boole i Augustus De Morgan, completament independents a Leibniz.

De la mateixa manera en què la lògica proposicional pot considerar-se una evolució de la lògica sil·logística anterior, la lògica predicada de Gottlob Frege era una evolució de la lògica proposicional. Un autor descriu aquesta lògica com "la combinació dels trets distintius de la lògica sil·logística i la proposicional". Per tant, la lògica predicada va marcar l'inici d'una nova etapa en la història de la lògica. La deducció natural va ser inventada per Gerhard Gentzen i Jan Lukasiewicz, mentre que els arbres de la veritat s'atribueixen a Evert Willem Beth. La invenció de les taules de la veritat, però, és d'atribució controvertida.

Introducció

Els connectius lògics es troben en els llenguatges naturals. En català, per exemple, alguns exemples són "i" (conjunció), "o" (disjunció), "no" (negació) i "sí" (però només quan s'utilitza per indicar condicional material).

Consideri's el següent argument:

1. Demà és dimecres o demà és dijous.
2. Demà no és dijous.
3. Per tant, demà és dimecres.

Es tracta d'un argument vàlid, fet que significa que les premisses (1) i (2) siguin veritables i la conclusió (3) falsa.

Així i tot, malgrat que l'argument sigui vàlid, això no implica que la conclusió sigui necessàriament veritable. En altres paraules: si les premisses són falses, aleshores la conclusió també podria ser-ho. Però si, en canvi, les premisses són veritables, aleshores la conclusió també ho és. La validesa de l'argument no depén, doncs, de les expressions "demà és dimecres" ni "demà és dijous", sinó de l'estructura mateixa de l'argument. Aquestes premisses podrien canviar-se per altres i l'argument seguiria sent vàlid. Per exemple:

1. Avui fa sol o avui plou.
2. Avui no plou.
3. Per tant, avui fa sol.

La validesa dels dos arguments anteriors depèn del significat de les expressions "o" i "no". Si qualsevol d'aquestes expressions es substitueix per una altra, aleshores els arguments podrien deixar de ser vàlids. Per exemple, el següent argument seria invàlid:

1. Ni fa sol ni plou.
2. No plou.
3. Per tant, fa sol.

Aquestes expressions (com ara "o" i "no"), de les quals depèn la validesa dels arguments, s'anomenen connectives lògiques. Pel que fa a expressions com "plou" i "demà és dijous", l'única cosa important de les mateixes és que tinguin un valor de veritat. És per això que se les reemplaça per simples lletres, la intenció de les quals és simbolitzar una expressió amb un valor de veritat qualsevol. A aquestes lletres se les anomena variables proposicionals, i en general s'importen de l'alfabet llatí, començant per la lletra p i seguint amb q, r, s, etc.Així doncs, els dos primers arguments presentats prèviament es podrien reescriure d'aquesta manera:

1. p o q
2. No q
3. Per tant, p

I el tercer argument, tot i no ser vàlid, podria reescriure's així:

1. Ni p ni q
2. No q
3. Per tant, p

Lògica proposicional

Proposicions. Formalment parlant, es defineix una proposició com un enunciat declaratiu que pot ser vertader o fals, però mai ambdues coses alhora. Les proposicions es representen mitjançant variables proposicionals i conjuncions, definides com a functors o funcions de veritat, de les quals s'obtenen fórmules sentencials o sentències.

Aquestes poden ser, segons la seva taula de veritat:

• Tautologia: és la sentència que és necessàriament vertadera.
• Contradicció: és la sentència que és necessàriament falsa.
• Contingència: és la sentència que pot ser vertadera o falsa.

Llenguatge formal del càlcul de proposicions

Sintaxi: el primer pas en l'estudi d'un llenguatge qualsevol és definir els símbols bàsics que el constitueixen (alfabet) i com es combinen entre si per a formar paraules i sentències. En aquest cas, està constituït per:

• Símbols de veracitat: V per a vertader i F per a fals.
• Símbols de variables: p, q, r, s, t...
• Símbols de connectives: ¬, ^;, ∨, v, →, ↔
• Símbols de puntuació: (,), per a evitar ambigüitats.

Regles de formació. Les classes de sentències ben formades es defineixen per regles purament sintàctiques, anomenades regles de formació. Aquestes són:

• Una variable proposicional és una sentència ben formada.
• Una sentència ben formada precedida de la negació és una sentència ben formada.
• Dues sentències ben formades unides per una de les partícules connectives binàries constitueix una sentència ben formada.
• Es poden ometre els parèntesis que tanquen una sentència completa.
• L'estil tipogràfic dels parèntesis es pot variar per fer-los més evidents usant claudàtors i claus.
• A les conjuncions i disjuncions, se'ls pot permetre tenir més de dos arguments.

Les connectives es divideixen per la seva aplicació en:

• Singulars: s'apliquen a una única sentència
• Binàries: s'apliquen a dues sentències.

Per la seva definició, també es poden dividir en:

• Primitives: les variables proposicionals, els parèntesis i les connectives ¬ i ∨.
• Definides: les connectives ∧, →, ↔, i XOR.

Taules de veritat

La taula de veritat d'una sentència és una taula en la qual es presenten totes les possibles interpretacions de les variables proposicionals que constitueixen la sentència i el valor de la veritat de la sentència per a cada interpretació.

Semàntica

• Negació (¬)

Consisteix a canviar el valor de veritat d'una variable proposicional. La seva expressió en el llenguatge natural és equivalent a "no" (per exemple: "No està plovent" = ¬ p).

p	¬ p
V	F
F	V

• Disjunció (∨)

La sentència serà vertadera quan una o ambdues variables proposicionals siguin vertaderes. La seva expressió en el llenguatge natural es correspon amb "o" (per exemple: "Plou o fa sol" = p V q).

p	q	p ∨ q
V	V	V
V	F	V
F	V	V
F	F	F

• Conjunció (^)

És una connectiva que pot definir-se com la composició:

p ^ q = ¬(¬p ∨ ¬q)

La sentència serà vertadera només quan ambdues variables proposicionals siguin vertaderes. En el llenguatge natural s'expressaria com a "i" (per exemple: "Plou i fa sol" = p ^ q).

p	q	p ∧ q
V	V	V
V	F	F
F	V	F
F	F	F

• Condicional (→)

És una connectiva definida per:

p → q = ¬p ∨ q

La sentència serà vertadera quan es compleixi: si és vàlid p, llavors ho serà (per exemple: "Si fa sol, aleshores és de dia" = p → q).

p	q	p → q
V	V	V
V	F	F
F	V	V
F	F	V

• Bicondicional (↔)

És una connectiva definida per:

p ↔ q = ((p → q) ∧ (q → p))

La sentència serà vertadera quan ambdues variables proposicionals siguin iguals (per exemple "Plou si i només si hi ha núvols" = p ↔ q).

p	q	p ↔ q
V	V	V
V	F	F
F	V	F
F	F	V

• Disjunció exclusiva (v)

És una connectiva definida per:

p v q = ¬(p ↔ q)

La sentència només serà vertadera quan només una de les dues variables proposicionals sigui vertadera (per exemple: "O bé plou, o bé fa sol" = p v q):

p	q	p v q
V	V	F
V	F	V
F	V	V
F	F	F

Límits de la lògica proposicional

La lògica proposicional permet formalitzar i teoritzar sobre la validesa d'un gran nombre d'arguments. Malgrat tot, també existeixen alguns arguments que son intuïtivament vàlids, però la validesa dels quals no és possible comprovar mitjançant la lògica proposicional. Per exemple:

1. Tots els homes són mortals,
2. Sòcrates és un home.
3. Per tant, Sòcrates és mortal.

Com que aquest argument no conté cap de les connectives "no", "i", "o", etc., segons la lògica proposicional la seva formalització seria la següent:

1. p
2. q
3. Per tant, r

Però aquesta és una forma d'argument invàlida, i això contradiu la nostra intuïció que l'argument és vàlid. Per tal de teoritzar sobre la validesa d'aquest tipus d'arguments, és necessari dur a terme una investigació sobre l'estructura interna de les variables proposicionals. D'això se n'ocuparà la lògica de primer ordre. Altres sistemes formals permeten teoritzar sobre altres tipus d'arguments; per exemple, la lògica de segon ordre, la lògica modal i la lògica temporal.

Bibliografia

• Enderton. A Mathematical Introduction to Logic. Academic Press, 1972. 
• Hamilton. Lógica para matemáticos. Paraningo, 1981. 
• Mendelson. Introduction to Mathematical Logic. 4ª. Chapman and May, 1997. 
• Pla, J. Lliçons de lógica matemática. P.P.U., 1991. 
• Badesa, C.; Jané, I.; Jansana, R. Elementos de lógica formal. Ariel, 1998. 
• Barnes; Mack. Una introducción algebraica a la lógica matemática. Eunibar, 1978. 
• Bridge, J. Beginning Model Theory. Oxford University Pres, 1977. 
• Ershov, Y.; Paliutin, E. Lógica matemática. Mir, 1990. 
• Hofstadter, D. Gödel, Escher, Bach: un Eterno y Grácil Bucle. Tusquets Editores, 1987. 
• Jané, I. Álgebras de Boole y lógica. Publicaciones U.B., 1989. 
• Monk. Mathematical Logic. Springer-Verlag, 1976. 
• Nidditch. El desarrollo de la lógica matemática. Cátedra, 1978. 
• Van Dalen, D. Logic and Structure. 2a edició. Universitext, Springer-Verlag, 1983.