lógica de proposiciones

Tema 1 Lógica de proposiciones y de predicados de primer orden.
Lógica de proposiciones
Sintaxis
El alfabeto de la Lógica de Proposiciones debe proporcionar los símbolos necesarios para representar
proposiciones sobre el mundo. Como el número de proposiciones que pueden manejarse en un mismo
razonamiento no está limitado, debe proveer un número infinito de letras proposicionales.
Consta delos siguientes elementos:
1. Infinitas letras proposicionales: p0, p1, p2, p3 . . .
2. Símbolos lógicos: constantes (^,), conectiva monaria () y conectivas binarias (⋀,⋁,→,↔)
3. Dos símbolos auxiliares de puntuación: paréntesis izquierdo’(’ y derecho ’)’.
En las exposiciones teóricas, el número de letras proposicionales que se consideran simultáneamente es
pequeño (por ejemplo, de p0 a p8).En estos caso se suelen notar informalmente con las últimas letras del
alfabeto latino: {p,q, r, s, t, . . .}.
En la siguiente tabla se adjunta el nombre usual de cada conectiva y su lectura:
^,

Enunciado Falso, Verdadero

Negación



No p

p

Conjunción



pyq

 p  q

Disyunción



poq

 p  q

Condicional



Si p entonces q

 p  q    p  q

Bicondicional



p si y sólo si q

 p  q    p  q    q  p 

Semántica de las conectivas
p
1
1
0
0

q
1
0
1
0

p
0
0
1
1

pq
1
0
0
0

pq
1
1
1
0

pq
1
0
1
1

p«q
1
0
0
1

Tablas de verdad
Si interesa conocer cómo se comporta globalmente la fórmula habrá que estudiarla frente a toda
asignación posible. La tabla de verdad es unaenumeración completa del valor de la fórmula para cada
asignación distinta. A este tipo de tablas se le denomina tabla de verdad de la fórmula.
A una fórmula verdadera para toda interpretación se le denomina tautología.
A una fórmula falsa para toda interpretación se le denomina contradicción.
A las fórmulas que no son ni tautología ni contradicción se las suele denominar contingentes.

1Satisfacibilidad
Una interpretación satisface una o varias fórmulas cuando éstas se evalúan como verdaderas en esa
interpretación o línea.
Sobre la tabla de verdad, cualquier "línea" (interpretación) donde una fórmula se evalúa como 1 satisface
esa fórmula.
Una interpretación satisface a un conjunto de fórmulas si todas ellas presentan valor 1 en esa misma línea.
La satisfacibilidad es laposibilidad de ser satisfecho por alguna interpretación.
Basta que al menos exista una línea donde se satisfaga simultáneamente ese conjunto de fórmulas para
afirmar que es satisfacible.
Si un conjunto o una fórmula no es satisfacible se denominará insatisfacible.
Las fórmulas insatisfacibles también se denominan contradicciones.
En la tabla de verdad 1, la primera fórmula por la izquierdaes insatisfacible, una contradicción. Las dos
restantes son satisfacibles. De estas dos fórmulas satisfacibles, una resulta ser verdadera en toda
interpretación y la otra no.
p
1
1
1
1
0
0
0
0

q
1
1
0
0
1
1
0
0

r (p  q)  ¬ (q  r) (p  q) → (q  r) (p  q) → (q  r)
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
1
0
0
1
1
1
0
1
1
0
0
1
1
Tabla 1:Una fórmula insatisfacible y dos satisfacibles

En la tabla de verdad 2, ese conjunto de tres fórmulas es satisfacible. Existe al menos una línea donde
todas las fórmulas tienen el valor 1.
El conjunto de fórmulas de la tabla 1.8 se satisface simultáneamente en 5 líneas.

 Si se eliminase una de las fórmulas, el conjunto resultante se satisfaría en un número igual o
mayor de líneas.
 Sise añadiese una fórmula cualquiera, el conjunto resultante se satisfaría en un número igual o
menor de líneas.
p
1
1
1
1
0
0
0
0

q
1
1
0
0
1
1
0
0

r p → (q  r) (p  q)  r
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
0
1
0

r → (r  p)
1
1
1
1
1
1
1
1

Tabla 2: El conjunto Г = {p → (q  r), (p  q)  r, r → (r  p)} es satisfacible

2...