Lògica proposicional
|
Per a altres significats vegeu «Lògica (desambiguació)». |
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.
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 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
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
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
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
- 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.