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.[1]
Contingut
1 Lògica proposicional
1.1 Llenguatge formal del càlcul de proposicions
1.2 Taules de veritat
1.3 Solvers
2 Referències
3 Bibliografia
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.
p | ¬ p |
|---|---|
| V | F |
| F | V |
- Disjunció (∨)
La sentència serà vertadera quan una o ambdues variables proposicionals siguin vertaderes.
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.
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à q.
p | q | p → q |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
- Bicondicional (↔, si i només si)
És una connectiva definida per:
p ↔ q = ((p → q) ∧ (q → p))
La sentència serà vertadera quan ambdues variables proposicionals siguin iguals.
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:
p | q | p |
|---|---|---|
| V | V | F |
| V | F | V |
| F | V | V |
| F | F | F |
Solvers
Trobar solucions a fórmules de lògica proposicional és NP-complet. Tot i això, s'han trobat mètodes que, en la pràctica (p. e.: algorisme DPLL, 1962; algorisme Chaff, 2001), són molt ràpids en casos pràctics.
Referències
↑ Diccionario de Filosofía (en castellà). 1a. Barcelona: SPES Editorial (edició especial per a RBA Editoriales), 2003, p. 30 (Biblioteca de Consulta Larousse). ISBN 84-8332-398-2.
Bibliografia
 | A Wikimedia Commons hi ha contingut multimèdia relatiu a: Lògica proposicional  |
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. 2ª. Universitext, Springer-Verlag, 1983.
