Elementos de lógica proposicional

1. La estructura lógica del método.
2. Noción y necesidad de la lógica.
3. La axiomatización de la lógica.
3.4. Elementos constitutivos de la lógica proposicional.
3.5. El análisis de las proposiciones mediante valores de verdad.
3.6. Las funciones de verdad.

3.5. Análisis de las proposiciones mediante valores de verdad
Sabemos que, por definición, toda letra proposicional puede tomar uno de dos valores de verdad que son verdadero (1) y falso (0). Del mismo modo, dada una fórmula con una determinada conectiva, su valor de verdad (verdadero o falso) queda determinado por los valores de verdad de las letras proposicionales que la integran. Los valores de verdad de las fórmulas elementales consideradas se pueden escribir del modo siguiente

V(¬φ)=0 sii V(φ)=1.
V(φ⊥ψ)=1 sii V(φ)=1 y V(ψ)=1.
V(φ⊦ψ)=1 sii V(φ)=1 ó V(ψ)=1.
V(φ→ψ)=0 sii V(φ)=1 y V(ψ)=0.
V(φ↔ψ)=1 sii V(φ)=V(ψ).
Visto ya como se valúan las proposiciones, podemos calcular la valuación V de cualquier fórmula φ empleando el árbol constructivo de φ. Por ejemplo, si queremos valuar la fórmula ¬(¬p→q), y sabemos que V(p)=1 y V(q)=0, tenemos que valuar: V(¬p)=0, V(¬p→q)=1 y, luego, V(¬(¬p→q))=0.
Dado que también puede darse que V(p)=0 y V(q)=1, V(p)=0 y V(q)=0, V(p)=1 y V(q)=1, la fórmula dada puede tomar otros valores. Es así que, se pueden calcular todos los valores de verdad que puede tomar la fórmula para todas las posibles distribuciones de valores de verdad de las letras proposicionales que aparecen en ella. Estos valores se suelen escribir en una tabla de verdad compuesta. A continuación, construimos una para la fórmula anterior:1 2 3 4 5
p q ¬p ¬p→q ¬(¬p→q)

V1 1 1 0 1 0
V2 1 0 0 1 0
V3 0 1 1 1 0
V4 0 0 1 0 1

En una tabla de verdad compuesta, el número de filas, para contener todas las combinaciones posibles de valores de verdad, depende sólo de la cantidad de letras proposicionales, y es 2n. Es 2n el número de distribuciones diferentes de los dos valores de verdad entre n proposiciones.

3.5.1. Fórmulas lógicamente equivalentes

Agregamos ahora dos nuevas columnas (6 y 7) a la tabla anterior, con las expresiones ¬q y ¬p⊥¬q:

1 2 3 4 5 6 7
p q ¬p ¬p→q ¬(¬p→q) ¬q ¬p⊥¬q

V1 1 1 0 1 0 0 0
V2 1 0 0 1 0 1 0
V3 0 1 1 1 0 0 0
V4 0 0 1 0 1 1 1

Vemos que los valores de verdad de las columnas 5 y 7 son los mismos. Es decir, para cada valuación Vi: Vi(¬(¬p→q)) = Vi(¬p⊥¬q). Por lo cual se dice que las fórmulas ¬(¬p→q) y ¬p⊥¬q son lógicamente equivalentes.

3.5.1.1. Demostración de la equivalencia de fórmulas.

En general, dadas dos fórmulas, φ y ψ, se dice que son lógicamente equivalentes siempre que, para cada evaluación, Vi: Vi(φ) = Vi(ψ).
Para demostrar que dos fórmulas son equivalentes, se establece la tabla de verdad en que se muestra que la columna de valores de verdad de la primera es igual a la columna de valores de verdad de la segunda. Lo puedes ver en el siguiente ejemplo:

φ ψ χ φ⊦ψ (φ⊦ψ)⊦χ ψ⊦χ φ⊦(ψ⊦χ)

V1 1 1 1 1 1 1 1
V2 1 1 0 1 1 1 1
V3 1 0 1 1 1 1 1
V4 1 0 0 1 1 0 1

V5 0 1 1 1 1 1 1
V6 0 1 0 1 1 1 1
V7 0 0 1 0 1 1 1
V8 0 0 0 0 0 0 0

Esta equivalencia es conocida como la asociatividad de la disyunción.Observa, en esta tabla de verdad, que la cantidad de filas es 23=8 (porque hay 3 letras proposicionales distintas). Nota también que para la primer letra proposicional (φ) se escribe la primera mitad de valores con 1, y la segunda mitad con 0; para la segunda letra (ψ), los valores van de a dos; y para la tercera (χ), los valores van de a uno.

3.5.1.2. Fórmulas equivalentes más comunes.

Del mismo modo se puede probar, mediante tablas de verdad, la equivalencia entre las fórmulas de cada una de las siguientes parejas (muy conocidas):

a) φ, ¬¬φ (ley de la doble negación)

b) φ⊥ψ, ψ⊥φ (conmutatividad de ⊥)

c) φ⊦ψ, ψ⊦φ (conmutatividad de ⊦)

d) φ↔ψ, ψ↔φ (conmutatividad de ↔)

e) (φ⊥ψ)⊥χ, φ⊥(ψ⊥χ) (asociatividad de ⊥)

f) (φ↔ψ)↔χ, φ↔(ψ↔χ) (asociatividad de ↔)

g) φ⊥(ψ⊦χ), (φ⊥ψ)⊦(φ⊥χ) (ley distributiva)

h) φ⊦(ψ⊥χ), (φ⊦ψ)⊥(φ⊦χ) (ley distributiva)

i) ¬(φ⊦ψ), ¬φ⊥¬ψ (ley de De Morgan)

j) ¬(φ⊥ψ), ¬φ⊦¬ψ (ley de De Morgan)

k) φ→ψ, ¬ψ→¬φ (ley de contraposición)

l) φ↔ψ, (φ→ψ)⊥(ψ→φ) (Definición de ↔)

m) φ↔ψ, (φ⊥ψ)⊦(¬φ⊥¬ψ) (Definición de ↔)

n) φ→ψ, ¬φ⊦ψ (Definición de →)

o) (φ⊥ψ)→χ, φ→(ψ→χ) (Ley de exportación)

p) φ, φ⊥φ (Idempotencia)

q) φ, φ⊦φ (Idempotencia)

r) φ→ψ, φ→( φ→ψ) (Absorción)

3.5.1.3. Regla del reemplazo

Se puede decir que dos fórmulas lógicamente equivalentes tienen el mismo significado lógico. Por ello, el significado lógico de una fórmula se conserva si se reemplaza una subfórmula por otra que tiene el mismo significado lógico. Esto se puede ver en el ejemplo: la fórmula (φ→ψ)⊥χ conserva su significado lógico cuando se transforma en esta otra: (¬φ⊦ψ)⊥χ. Se puede ver que esta última no es más que el resultado dereemplazar en la primera la subfórmula φ→ψ por ¬φ⊦ψ, siendo que estas dos expresiones tiene el mismo significado lógico.

3.5.1.4. Teorema de la equivalencia

(T1) Las fórmulas φ y ψ son lógicamente equivalentes si y sólo si para toda valuación V, V(φ↔ψ) = 1.

No haremos una prueba del teorema, pero lo ejemplificaremos con una doble negación (p ↔ ¬¬p)

p ¬p ¬¬p p ↔ ¬¬p
V1 1 0 1 1
V2 0 1 0 1

Vemos en esta tabla que el valor de verdad resultante de la fórmula p ↔ ¬¬p es siempre 1. Las fórmulas que tienen esta propiedad son denominadas tautologías. Si la fórmula φ es una tautología se expresa como aŠšφ.

Si una fórmula no es una tautología entonces existe al menos una valuación de V tal que V(φ) = 0. Cada una de estas valuaciones (que dan cero) es un contraejemplo de la tautologicidad de φ. Una fórmula que no es una tautología se expresa como aŠ­φ (phi no es una tautología). Tomaremos la fórmula (p → q) ↔ (¬p → ¬q) (Si hay humo entonces hay fuego, es equivalente a que si no hay humo entonces no hay fuego), como ejemplo de expresión no tautológica, a la que aplicaremos todas las valoraciones.

p q ¬p ¬q p → q ¬p → ¬q (p→q) ↔ (¬p→¬q

V1 1 1 0 0 1 1 1
V2 1 0 0 1 0 1 0
V3 0 1 1 0 1 0 0
V4 0 0 1 1 1 1 1

Se puede ver en la tabla que no se obtiene una tautología, y que por lo tanto la equivalencia dada es un contraejemplo.

3.5.1.5. Teoremas de la contradicción

(T2) Si φ es una tautología, entonces ¬φ es una contradicción.
Las contradicciones jamás son verdaderas; para toda valuación V debe cumplirse que V(¬φ)=0. Así se constata en la más conocida y elemental de las expresiones contradictorias: p⊥¬p

p¬p p⊥¬p
V1 1 0 0
V2 0 1 0

(T3) Si φ es una contradicción, entonces ¬φ es una tautología.

3.5.1.6. Teorema de la contingencia

Las fórmulas que no son ni tautologías ni contradicciones se denominan contingencias. Es decir, hay fórmulas φ tales que tienen al menos una valuación Vi1(φ)=1 y al menos una valuación Vi2(φ)=0.

(T4) φ es una contingencia si y sólo si ¬φ es una contingencia.

También en este caso nos limitaremos a proporcionar un caso en que se constata el teorema. Sea la tabla de (¬p→¬q) → (¬p⊦¬q)

p q ¬p ¬q ¬p→¬q ¬p⊦¬q (¬p→¬q)→(¬p⊦¬q) V1 1 1 0 0 1 0 0
V2 1 0 0 1 1 1 1
V3 0 1 1 0 0 1 1
V4 0 0 1 1 1 1 1

Como hay al menos una fila con valor de verdad 1, y al menos una con valor 0, la tabla nos muestra que (¬p→¬q) → (¬p⊦¬q) es una contingencia.

3.6. Las funciones de verdad

Una función es una correspondencia unívoca o en una sola dirección entre los elementos de un conjunto dado (que contiene los argumentos) y los de otro conjunto (que contiene los valores de la función). Comúnmente, una función consta de dos variables unidas entre sí por una determinada ley de dependencia. La lógica es un campo especial de aplicación del concepto de función.
Hasta aquí hemos visto las conectivas como términos sincategoremáticos, esto es, cuyo significado depende de su vinculación con los términos que poseen un significado autónomo. Por ej., en la fórmula p⊥q el significado de ⊥ depende de las interpretaciones dadas a φ y ψ. Sin embargo, se puede interpretar la conectiva ⊥, y las otras vistas, en forma directa, como funciones de verdad.

Cada conectiva binaria es una función de verdad. Se distingue de lasotras por la serie de valores que toma, dentro de las combinaciones posibles de valores de verdad. El significado de cada conectiva utilizada lo vemos a continuación en una tabla con todas las posibles funciones de verdad para las conectivas binarias. En nuestra lógica sólo empleamos cuatro, que resaltamos en la tabla: la disyunción, la implicación material, la equivalencia material y la conjunción.

φ ψ f⊦
1 1 1 0 0
0 1 0 1 0

Entonces, la negación, que es una conectiva unaria, posee la función dada por:
f¬(1)=0, f¬(0)=1.

Un sistema desarrollado con las conectivas ⊥ ⊦ y ¬ es funcionalmente completo y puede expresar todas las funciones de verdad. Si a este sistema se le agregan las conectivas → y ↔, será suficiente para expresar todas las posibles conectivas veritativo-funcionales (el valor de verdad de la función depende sólo del valor de verdad de las dos partes que la componen).

Veamos en un ejemplo, como se puede expresar una fórmula con otra equivalente, pero que contenga sólo ⊥ ⊦ y ¬. Sea la fórmula

p→(q↔r)

• q↔r se puede escribir como: (q⊥r)⊦(¬q⊥¬r), aplicando una equivalencia vista anteriormente, llamada Definición de ↔. Con ello, la fórmula dada se transforma en la siguiente:

p→((q⊥r)⊦(¬q⊥¬r))

• Una implicación material φ→ψ se puede escribir de la forma ¬φ⊦ψ. Aplicándolo a la fórmula anterior, se transforma en otra equivalente:
¬p⊦((q⊥r)⊦(¬q⊥¬r))

En fin, es preciso notar que, las fórmulas que al ser tratadas con su tabla de verdad producen siempre el valor 1 se denominan leyes lógicas. Es decir, las fórmulas tautológicas se dicen leyeslógicas.

aŽ¢aŽ¢aŽ¢

Respuestas a los ejercicios:
Ejercicio 1: a
Ejercicio 2: b
Ejercicio 3: b

aŽ¢aŽ¢aŽ¢
----- ----- -------------
Ejercicio de autoevaluación 1 (elige la respuesta correcta):
Determinar si la expresión φ: p → q es lógicamente equivalente a ψ: p → (p → q).

1 2 3 4
p q p → q p → (p → q)
V1 1 1
V2 1 0
V3 0 1
V4 0 0
Completar los valores de verdad que faltan en la tabla de verdad compuesta, y constatar si los valores de las columnas que
corresponden a las expresiones dadas son iguales.
sSon lógicamente equivalentes p→q y p→( p→q)? Sí
No
No se puede establecer.
Respuesta

Ejercicio de autoevaluación 2 (elige la respuesta correcta):
Determinar si la expresión φ: (p→q)↔(p→(p⊦q)) es una tautología, una contradicción o una contingencia.

p q p→q p⊦q p→(p⊦q) (p→q)↔(p→(p⊦q))
V1 1 1 1 1 1 1
V2 1 0 0 1 1
V3 0 1 1 1 1
V4 0 0 1 0 1 1
Completar los valores de verdad que faltan en la tabla de verdad compuesta, y constatar si en la columna resultante son todos ceros, todos unos, o si hay valores ceros y unos.
La expresión (p→q)↔(p→(p⊦q)) es tautológica, contingente o contradictoria?
Es una tautología.
Es una contradicción.
Es una contingencia.
Respuesta

Ejercicio de autoevaluación 3 (elige la respuesta correcta):
Traducir la expresión φ = (p↔q) → ¬(q⊥p) a otra equivalente, pero que contenga sólo ⊥ ⊦ y ¬.
sCuál de las siguientes expresiones es equivalente a φ?:
(p⊥q) ⊥ ¬(p⊦q)
¬(p⊥q) ⊥ (p⊦q)
¬(p⊥q) ⊥ ¬(p⊦q)
Respuesta