Lògica proposicional
La lògica proposicional és una branca de la lògica clàssica que estudia les proposicions o sentencies lògiques, les seves possibles avaluacions de veritat i, en el cas ideal, el seu nivell absolut de veritat.
Taula de continguts |
Lògica proposicional[modifica]
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 functors o funcions de veritat, de les que 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[modifica]
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 ells 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 corxets 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[modifica]
La taula de veritat d'una sentència és una taula en la que 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 en 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 serà vertadera només quan una de les dues variables proposicionals sigui vertadera.
| p | q | p |
|---|---|---|
| V | V | F |
| V | F | V |
| F | V | V |
| F | F | F |
Solvers[modifica]
Trobar solucions a fórmules de lògica proposicional és NP-complete. Tot i això, s'han trobat mètodes que a la pràctica (e.g., algorisme DPLL, 1962; algorisme Chaff, 2001) són molt ràpids en casos pràctics.
Bibliografia[modifica]
- A Mathematical Introduction to Logic. Academic Press, 1972.
- Lógica para matemáticos. Paraningo, 1981.
- Introduction to Mathematical Logic. 4ª. Chapman and May, 1997.
- Lliçons de lógica matemática. P.P.U., 1991.
- Elementos de lógica formal. Ariel, 1998.
- Una introducción algebraica a la lógica matemática. Eunibar, 1978.
- Beginning Model Theory. Oxford University Pres, 1977.
- Lógica matemática. Mir, 1990.
- Gödel, Escher, Bach: un Eterno y Grácil Bucle. Tusquets Editores, 1987.
- Álgebras de Boole y lógica. Publicaciones U.B., 1989.
- Mathematical Logic. Springer-Verlag, 1976.
- El desarrollo de la lógica matemática. Cátedra, 1978.
- Logic and Structure. 2ª. Universitext, Springer-Verlag, 1983.
