Lògica proposicional

De Viquipèdia
Dreceres ràpides: navegació, cerca
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 sentències lògiques, les seves possibles avaluacions de veritat i, en el cas ideal, el seu nivell absolut de veritat.

Lògica proposicional[modifica | modifica el codi]

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 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 | modifica el codi]

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 | modifica el codi]

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 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 serà vertadera només quan una de les dues variables proposicionals sigui vertadera.

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

Solvers[modifica | modifica el codi]

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 | modifica el codi]

  • 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.