Lógica proposicional

Diagrama de matematicas discretas: grafo con nodos conectados, puertas logicas y diagramas de Venn. — Temas centrales de matematicas discretas: logica, conjuntos, grafos y conteo.

Mapa conceptual

La idea que gobierna todo Una proposición es una frase que puede ser verdadera (V) o falsa (F), sin término medio. «Llueve» es una proposición; «¡Cierra la ventana!» y «x + 1» no lo son. La lógica estudia cómo el valor de las partes determina el valor del todo.

Los conectivos combinan proposiciones. Dados p y q: la negación ¬p invierte el valor; la conjunción p ∧ q es verdadera solo si ambas lo son; la disyunción p ∨ q es verdadera si al menos una lo es; el condicional p → q sólo es falso cuando p es V y q es F; y el bicondicional p ↔ q es verdadero cuando ambas tienen el mismo valor.

La disyunción es INCLUSIVA: «p o q» es verdadera también cuando ambas lo son, al revés que el «o» exclusivo del habla cotidiana.
Conectivo	Símbolo	Es V cuando…
Negación	¬p	p es F
Conjunción (y)	p ∧ q	ambas son V
Disyunción (o)	p ∨ q	al menos una es V
Condicional (si…then)	p → q	no ocurre que p sea V y q sea F
Bicondicional	p ↔ q	p y q coinciden en valor

Tabla de verdad del condicional

La fila que sorprende: si p es FALSA, el condicional es VERDADERO independientemente de q («de lo falso se sigue cualquier cosa»).
p	q	p → q
V	V	V
V	F	F
F	V	V
F	F	V

Entender el condicional El condicional «si apruebas entonces celebro» solo se rompe si apruebas y NO celebras. Si suspends, la promesa no dice nada: no se rompió. Por eso p Falso hace el condicional verdadero, aunque resulte anti-intuitivo.

Tautología, contradicción y equivalencia

Tautología: verdadera para toda asignación, como p ∨ ¬p.
Contradicción: siempre falsa, como p ∧ ¬p.
Equivalencia lógica: dos fórmulas con la misma tabla, p. ej. p → q ≡ ¬p ∨ q (¡definición del condicional!) y la ley de De Morgan ¬(p ∧ q) ≡ ¬p ∨ ¬q.

Dos proposiciones equivalentes pueden usarse indistintamente. Simplificar una fórmula lógica es reemplazarla por otra equivalente más simple, habilidad que está detrás de optimizar una consulta SQL o un circuito.

¿Cuál es la tabla de verdad correcta de p ∧ q?

La negación de «p ∧ q» es «¬p ∧ ¬q».

Une cada fórmula con su equivalente lógica.

Errores frecuentes

Confundir el condicional p → q con su recíproca q → p: no son equivalentes; la equivalente es la contrarrecíproca ¬q → ¬p.
Leer «o» como exclusivo: en lógica ∨ es inclusivo salvo que se diga «o bien… o bien» (xor).
Olvidar que p → q es V cuando p es F: muchas discusiones se enquistan en un antecedente falso.

Ejemplo resuelto

Decidir si ((p → q) ∧ p) → q es tautología.
Supón el antecedente (p → q) ∧ p verdadero.
Entonces p es V y p → q es V, lo que obliga a q = V.
Con q = V, la conclusión q es V, así que todo el condicional es V.
Si el antecedente es F, el condicional global es V por definición. En todos los casos: V → tautología (es el modus ponens).

En datos, la lógica proposicional gobierna los filtros: una consulta con WHERE activo AND (region = Norte OR region = Sur) evalúa exactamente una fórmula booleana sobre cada fila. Dominar las tablas de verdad es dominar el porqué de cada fila que entra o sale.

Lo esencial de la lógica

proposición

frase V o F

∧

y, ambos V

∨

o, al menos uno V

→

solo F si V lleva a F

¬(p∧q)

¬p∨¬q

p→q ≡

¬p∨q

tautología

siempre V

contrarrecíproca

¬q→¬p, equivale a p→q

Lógica de proposiciones (repaso formal)
Conectivos, tablas de verdad y equivalencias con ejercicios.

Formaliza con proposiciones y conectivos el enunciado: «Si estudio y descanso, aprobaré; pero no descansé». Determina si se sigue lógicamente que no aprobaste, construyendo la tabla o razonando fila a fila.

MIT OCW 6.042J
Matematicas para Ciencias de la Computacion (MIT OpenCourseWare).