Desde la antigüedad, la humanidad ha buscado herramientas para razonar correctamente. Aristóteles fue uno de los primeros en formalizar este esfuerzo mediante un conjunto de reglas para el razonamiento deductivo, cuya intención era establecer una base sólida para todas las ciencias. Mucho más tarde, durante el siglo XVII, Gottfried Leibniz propuso una idea revolucionaria: usar símbolos para representar el razonamiento, del mismo modo en que la notación algebraica había transformado el manejo de los números (Lenzen 2025). Esta visión simbólica tomó forma en el siglo XIX gracias a George Boole y Augustus De Morgan, quienes establecieron las bases de la lógica moderna o lógica simbólica.

Figura 1

Retratos de Gottfried Leibniz, Augustus De Morgan y George Boole

Hoy en día, la lógica proposicional es indispensable en múltiples campos de la computación, como el diseño de circuitos digitales, las bases de datos relacionales, la teoría de autómatas o la inteligencia artificial. Pero también tiene un valor universal: nos permite razonar con precisión, sin ambigüedad, evaluando no el contenido de las afirmaciones, sino su estructura lógica. Por ejemplo, si aceptamos como verdaderas las premisas «Todos los matemáticos usan sandalias» y «Cualquiera que use sandalias es un algebrista», entonces, sin importar lo extraño que suene, la conclusión lógica «Todos los matemáticos son algebristas» debe aceptarse como verdadera dentro de ese sistema de razonamiento.

La lógica proposicional también es fundamental para asegurar la corrección de programas y sistemas. Consideremos el desarrollo de un algoritmo que calcule rutas óptimas entre ciudades. Para pocos datos, podemos verificar los resultados manualmente; pero cuando el número de entradas crece, ya no es viable comprobar todo a mano. ¿Cómo podemos entonces confiar en que el programa funciona siempre? La respuesta es: necesitamos un argumento lógico que demuestre su validez.

Incluso en contextos cotidianos, entender la lógica puede evitar confusiones. Pensemos en este decreto de la ciudad de Naperville: «Será ilegal que una persona tenga más de tres perros y tres gatos en su propiedad» (Johnsonbaugh 2018). ¿Qué sucede si alguien tiene cinco perros y ningún gato? Este tipo de afirmación ambigua se puede analizar y desambiguar mediante la lógica proposicional, revelando cómo una interpretación clara puede cambiar completamente la aplicación de una norma.

Antes de hablar sobre lógica matemática, necesitamos responder una pregunta fundamental: ¿todas las oraciones que usamos al hablar o escribir son útiles para hacer lógica? La respuesta es no. No toda oración es útil en lógica, y para entender por qué, tenemos que fijarnos en qué función cumple esa oración.

En general, cuando alguien dice algo, lo hace con una intención: informar, expresar emociones o pedir algo. Esto se llama función del lenguaje. Mira estos tres ejemplos:

• Informar: «La Tierra gira alrededor del Sol». Aquí, quien habla está dando un dato, algo que puede ser verdadero o falso.
• Expresar: «¡Qué emoción este concierto!». Aquí, la persona está mostrando cómo se siente.
• Pedir o dirigir: «Pásame la sal, por favor». Aquí, se espera que el otro haga algo.

De estos tres tipos, solo nos interesa uno en lógica: el primero. Solo nos sirven las oraciones que informan algo que puede ser verdadero o falso. Entonces, ¿cómo se llama una oración de ese tipo en lógica? Se llama proposición. De esta manera, una proposición es una oración que afirma algo y puede ser verdadera o falsa, pero no ambas al mismo tiempo.

Por ejemplo, observa estas oraciones:

• El ECU 911 es el sistema nacional de emergencias del Ecuador.
• El presidente del Ecuador en 2020 fue Gustavo Petro.
• Todo sistema conectado a Internet puede ser vulnerable a un ciberataque.
• El volcán Cotopaxi hará erupción este año.
• Configura un firewall en todos los servidores antes del viernes.

Solo las oraciones a), b), c) y d) son proposiciones, porque todas afirman algo que puede ser verdadero o falso, aunque en el caso de la d) no sepamos actualmente cuál es su valor de verdad. En cambio, la oración e) no es una proposición, ya que no afirma nada que pueda ser evaluado como verdadero o falso: es una orden. En lógica, solo trabajamos con oraciones declarativas que tienen un valor de verdad bien definido.

Para trabajar con proposiciones de manera más clara, vamos a representarlas con letras, igual que en álgebra usamos letras para representar números. Así, en lugar de escribir frases largas una y otra vez, usamos símbolos como p, q, r, etc.

¿Por qué hacemos esto? Porque en lógica no nos interesa el contenido de las frases, sino cómo se relacionan entre ellas. Esto es fundamental para analizar argumentos.

Veamos como ejemplo este argumento tomado del texto de Epp (2020):

Si la sintaxis del programa es defectuosa o si los resultados de la ejecución del programa dan como resultado una división entre cero, entonces la computadora va a generar un mensaje de error. Por tanto, si la computadora no genera un mensaje de error, entonces la sintaxis del programa es correcta y la ejecución del programa no da como resultado una división entre cero.

Aquí hay muchas palabras, pero si lo analizamos, todo se puede reducir a proposiciones. Para manejarlo mejor, vamos a dar un nombre a cada una:

• p: La sintaxis del programa es defectuosa.
• q: La ejecución del programa da como resultado una división entre cero.
• r: La computadora genera un mensaje de error.

Ahora que tenemos identificadas las proposiciones individuales, queremos escribirlas de forma que conserven la estructura del argumento original. En el texto, notamos palabras como «o», «entonces», «no», «y», que conectan las distintas partes del razonamiento.

Esas palabras son claves porque nos indican cómo se relacionan las proposiciones entre sí. En lógica, usamos símbolos especiales para representar esas conexiones, y a esos símbolos los llamamos conectores lógicos.

Los principales conectores lógicos que utilizaremos en este curso son:

Con estos conectores, podemos tomar proposiciones simples como p, q y r, y combinarlas para formar proposiciones más complejas que reflejen argumentos reales. Por ejemplo, el argumento anterior puede ser representado así:

\[ \big((p \lor q) \rightarrow r\big) \rightarrow \big(\neg r \rightarrow (\neg p \land \neg q)\big) \]

Hasta ahora hemos hablado de proposiciones y cómo se conectan entre sí usando conectores lógicos. Pero si queremos trabajar de forma rigurosa, necesitamos definir con precisión qué se considera una expresión válida en lógica proposicional.

En otras palabras: ¿cómo sabemos si una fórmula está bien escrita? Para eso, vamos a introducir una noción fundamental: la forma proposicional.

Definición 1: Forma Proposicional

Una forma proposicional es una cadena de caracteres que se genera mediante las siguientes reglas:

• Las letras minúsculas del alfabeto (como p, q, r, etc.) son formas proposicionales. A estas se les llama letras proposicionales.
• Si P y Q son formas proposicionales, entonces también lo son las siguientes:

\[ \neg P, \quad P \land Q, \quad P \lor Q, \quad P \rightarrow Q, \quad P \leftrightarrow Q \]

• Nada más es una forma proposicional salvo lo que se construye usando las reglas anteriores.

A las formas proposicionales las llamaremos directamente proposición. Esta definición nos da un marco claro para construir fórmulas lógicas: empezamos con letras (como p, q) y las combinamos usando conectores para formar proposiciones más complejas. La lógica, en este sentido, funciona como un lenguaje formal con reglas de formación bien definidas.

En la próxima clase veremos cómo evaluar si una de estas proposiciones es verdadera o falsa: eso nos llevará al concepto de tablas de verdad.

Para entender mejor cómo funciona la sintaxis de las fórmulas, veamos algunos ejemplos concretos. Algunas expresiones están bien formadas y siguen las reglas que definimos para las formas proposicionales. Otras, en cambio, parecen razonables a simple vista, pero no cumplen con las reglas formales del lenguaje lógico. En la siguiente tabla comparamos ambas situaciones e indicamos qué errores aparecen en los casos incorrectos:

Ahora que ya conoces los elementos fundamentales de la lógica proposicional —las proposiciones, los conectores lógicos y la forma correcta de escribir fórmulas— es momento de ponerlos en práctica. En esta sección trabajaremos la siguiente tarea: Traducción del lenguaje natural al lenguaje lógico, lo que significa identificar las proposiciones simples y expresar oraciones más complejas usando conectores lógicos.

Para realizar una traducción correcta, seguimos estos pasos:

1. Identificar las proposiciones simples: Detecta las partes básicas del enunciado que afirman algo y asocia una letra a cada proposición.
2. Reconocer los conectores: Determina si en el enunciado hay palabras como «y», «o», «no», «si..., entonces...», «si y solo si», y tradúcelas a símbolos lógicos.
3. Escribir la expresión lógica: Usa las letras proposicionales y los conectores para construir la fórmula correspondiente, respetando el uso de paréntesis si es necesario.

Ejemplo 1.

Queremos traducir la siguiente frase del lenguaje ordinario al lenguaje lógico formal:

«Si estudio lógica o resuelvo ejercicios, entonces aprobaré el curso.»

1. Paso 1. Identificamos las proposiciones simples que componen el enunciado:
   • p: Estudio lógica.
   • q: Resuelvo ejercicios.
   • r: Aprobaré el curso.
2. Paso 2. Reconocemos los conectores del lenguaje natural:
   • «o» se traduce como disyunción: ∨
   • «si..., entonces...» se traduce como implicación: →
3. Paso 3. Escribimos la fórmula compuesta respetando la estructura lógica:

\[ (p \lor q) \rightarrow r \]

Este primer ejemplo muestra cómo los paréntesis son cruciales para agrupar la condición completa («estudio lógica o resuelvo ejercicios») y distinguirla del resultado.

Ejemplo 2.

Queremos traducir la siguiente frase del lenguaje ordinario al lenguaje lógico formal:

«No es cierto que si llueve, entonces no saldremos a caminar.»

1. Paso 1. Identificamos las proposiciones simples que componen el enunciado:
   • p: Llueve.
   • q: Saldremos a caminar.
2. Paso 2. Reconocemos los conectores del lenguaje natural:
   • «no es cierto que» se traduce como negación: ¬
   • «si..., entonces...» se traduce como implicación: →
   • «no» (antes de «saldremos») se traduce como negación: ¬
3. Paso 3. Escribimos la fórmula compuesta respetando la estructura lógica:

\[ \neg (p \rightarrow \neg q) \]

En este caso, se introducen dos negaciones. Es importante notar que la primera negación afecta a toda la implicación, mientras que la segunda solo afecta a la proposición q, lo que se refleja en el uso de los paréntesis.

Ejemplo 3.

Queremos traducir la siguiente frase del lenguaje ordinario al lenguaje lógico formal:

«Si se detecta una intrusión, entonces el acceso no se autoriza y se activa una alerta.»

1. Paso 1. Identificamos las proposiciones simples que componen el enunciado:
   • p: Se detecta una intrusión.
   • q: El acceso se autoriza.
   • r: Se activa una alerta.
2. Paso 2. Reconocemos los conectores del lenguaje natural:
   • «no» se traduce como negación: ¬
   • «y» se traduce como conjunción: ∧
   • «si..., entonces...» se traduce como implicación: →
3. Paso 3. Escribimos la fórmula compuesta respetando la estructura lógica:

\[ p \rightarrow (\neg q \land r) \]

Aquí vemos una implicación donde el resultado es una conjunción. La coma después de «se autoriza» nos indica que ambas condiciones siguientes («el acceso no se autoriza» y «se activa una alerta») son consecuencias de la intrusión, lo que se representa correctamente con la conjunción entre paréntesis.

Ejemplo 4

Queremos traducir la siguiente frase del lenguaje ordinario al lenguaje lógico formal:

«Si estudio matemáticas y no pierdo clases, o si realizo todas las tareas, entonces aprobaré el examen.»

1. Paso 1. Identificamos las proposiciones simples que componen el enunciado:
   • p: Estudio matemáticas.
   • q: Pierdo clases.
   • r: Realizo todas las tareas.
   • s: Aprobaré el examen.
2. Paso 2. Reconocemos los conectores del lenguaje natural:
   • «y» se traduce como conjunción: ∧
   • «no» se traduce como negación: ¬
   • «o» se traduce como disyunción: ∨
   • «si..., entonces...» se traduce como implicación: →
3. Paso 3. Escribimos la fórmula compuesta respetando la estructura lógica:

\[ \big[(p \land \neg q) \lor r\big] \rightarrow s \]

Este ejemplo es más complejo y demuestra el uso de paréntesis anidados. El uso de los corchetes grandes no es obligatorio pero ayuda a leer la fórmula, dejando claro que la implicación principal tiene como antecedente todo el conjunto de la disyunción.

1.3.1. Jupyter Notebooks en el curso

Durante este curso, utilizaremos Jupyter Notebooks como herramienta para explorar conceptos de Matemática Discreta mediante programación en Python.

Un Jupyter Notebook es un entorno interactivo que permite escribir texto, insertar ecuaciones, ejecutar código y visualizar resultados en un mismo documento. Esta herramienta combina la claridad de una libreta de apuntes con el poder computacional de Python, facilitando el aprendizaje activo y la experimentación directa.

No necesitas instalar nada en tu computadora para utilizarlo: puedes acceder a todos los notebooks del curso directamente desde tu navegador utilizando Google Colab, una plataforma gratuita que permite ejecutar código Python en la nube.

¿Alguna vez te has preguntado cómo una computadora decide qué datos mostrarte cuando filtras por más de una condición? Por ejemplo, en una hoja de cálculo puedes aplicar un filtro para mostrar únicamente los registros donde el campo «Acceso permitido» sea verdadero y el campo «Intentos fallidos» sea menor a 3. En este caso, estás utilizando una combinación de condiciones que, en el fondo, responde a la lógica proposicional.

Para poder analizar con claridad este tipo de situaciones, introducimos una herramienta fundamental: las tablas de verdad. Estas nos permiten observar qué valor (verdadero o falso) adopta una proposición compuesta según los valores de sus componentes más simples (Epp 2020). A este proceso lo llamamos una asignación de valores de verdad: consiste en suponer que cada proposición simple tiene un valor definido (verdadero o falso) y, a partir de ello, calcular el valor de verdad de la proposición completa. Así, podemos explorar todas las combinaciones posibles y conocer el comportamiento lógico completo de cualquier expresión.

Retomemos el ejemplo de filtrar registros en una base de datos. Supongamos que queremos mostrar únicamente aquellos registros en los que se cumplen las siguientes dos condiciones:

• Que el usuario tenga acceso permitido (p).
• Que el número de intentos fallidos sea menor que 3 (q).

Queremos evaluar si se cumplen ambas condiciones al mismo tiempo, es decir, si se cumple la proposición compuesta p∧q.

Antes de continuar, adoptaremos una convención: en lugar de escribir «verdadero» o «falso» en la tabla, utilizaremos V y F, respectivamente.

Ahora sí, construiremos la tabla de verdad considerando todas las asignaciones posibles de valores de verdad para p y q, y evaluaremos el valor resultante de p∧q en cada caso:

1. Si el valor asignado a p es V (el usuario tiene acceso permitido), y el valor asignado a q también es V (menos de 3 intentos fallidos), entonces ambas condiciones se cumplen, por lo que p∧q también es V.
2. Si el valor asignado a p es V, pero el valor asignado a q es F (3 o más intentos fallidos), no se cumplen ambas condiciones, así que p∧q es F.
3. Si el valor asignado a p es F (el acceso no fue permitido), aunque el valor asignado a q sea V, la condición conjunta no se cumple: p∧q es F.
4. Finalmente, si ambos valores asignados son F, claramente p∧q también es F.

Esto se resume en la siguiente tabla:

Observa que esta es la tabla de verdad de la proposición p∧q, sin importar lo que representen exactamente las proposiciones p y q. Siempre que analicemos una conjunción, este será su comportamiento lógico.

Ahora, supón que queremos hacer otro filtrado de registros, pero esta vez con un criterio más flexible. Imaginemos que deseamos mostrar todos los registros que cumplan al menos una de las siguientes condiciones:

1. p: «El usuario tiene acceso permitido»
2. q: «El número de intentos fallidos es menor que 3»
3. Proposición compuesta: p ∧ q

Esto significa que aceptaremos registros en los que el acceso esté permitido, o bien donde el número de intentos fallidos no supere el límite, o incluso ambos casos a la vez. En términos lógicos, esto se expresa mediante la proposición p∨q.

Te invito a construir la tabla de verdad para p∨q, considerando todas de la misma manera que lo hicimos para p∧q. El resultado debería ser:

Una forma sencilla de trabajar con valores de verdad es codificarlos como números binarios: escribiremos 1 para «verdadero» y 0 para «falso». Adoptada esta convención, la tabla de verdad de la conjunción p∧q queda:

Esto nos permite formalizar el significado de una asignación de valores de verdad. Si tenemos dos letras proposicionales, una asignación consiste en elegir un valor de verdad (1 o 0) para cada una. Por ejemplo, la asignación (1,1) indica que el valor asignado a p es 1 (verdadero) y el valor asignado a q también es 1. Bajo esta asignación, el valor de verdad de p∧q es 1.

Definición 1: Asignación de valores de verdad.

Sea n∈N. Una asignación de valores de verdad para n letras proposicionales es un elemento del conjunto {0,1}^n, es decir, una n-tupla de ceros y unos que determina el valor de verdad (0 o 1) de cada proposición elemental.

Con esto, para cada asignación de valores de verdad de p y q se tiene un valor de verdad de p∧q:

De esta manera, podemos ver que, la tabla de verdad no es más que una función

\[ f : \{0,1\}^2 \rightarrow \{0,1\} \]

De manera general, tenemos la siguiente definición:

Definición 2: Función de verdad.

Para n∈N, una función de verdad de n variables es una función de la forma

\[ f : \{0,1\}^n \rightarrow \{0,1\} \]

Es decir, una regla que asigna a cada combinación posible de valores de entrada (ceros y unos) un único valor de salida (0 o 1).

Una vez formalizados estos conceptos, a continuación, se presentan las tablas de verdad de los conectores lógicos estudiados en la clase anterior:

Con esta base, podemos construir tablas de verdad de proposiciones más complejas.

Para construir una tabla de verdad de una proposición lógica compuesta, se procede de la siguiente manera:

1. Se identifica el número n de letras proposicionales distintas que intervienen.
2. Se listan todas las posibles asignaciones de valores de verdad para dichas proposiciones. Como cada letra puede tomar dos valores (0 o 1), el número total de combinaciones posibles es 2^n, es decir, la tabla tendrá 2^n filas.
3. Se organiza la tabla de forma que las columnas correspondientes a las letras proposicionales reflejen todas las combinaciones en orden sistemático:
   • A la primera letra se le asignan 2^(n-1) valores verdaderos (la mitad de filas) seguidos de 2^(n-1) valores falsos (la otra mitad de filas).
   • A la segunda, 2^(n-2) verdaderos (la mitad de filas del paso anterior), 2^(n-2) falsos, repitiendo ese patrón.
   • Y así sucesivamente, dividiendo la secuencia por mitades.
4. Finalmente, se completan las columnas adicionales con los valores de verdad de las proposiciones compuestas, hasta obtener el valor de la proposición final.

Ejemplo:

Tabla de verdad de:

\[ (p \lor q) \rightarrow q \]

Vamos a construir la tabla de verdad para la proposición lógica compuesta (p∨q)→q, siguiendo los pasos indicados.

1. Identificación de letras proposicionales: Las letras que aparecen son p y q. Por tanto, n = 2.
2. Número de combinaciones: El número de combinaciones posibles de valores de verdad es 2^n = 2^2 = 4. La tabla tendrá 4 filas.
3. Asignación sistemática de valores de verdad:

Tabla

Valores de p y q

p	q
1	1
1	0
0	1
0	0

p=1, q=1

p: 1
q: 1

p=1, q=0

p: 1
q: 0

p=0, q=1

p: 0
q: 1

p=0, q=0

p: 0
q: 0

Nota. Creación propia.

4. Evaluación de las proposiciones compuestas:
   • Calculemos p ∨ q: la disyunción es verdadera cuando al menos una de las proposiciones lo es.
   • Luego, evaluamos (p ∨ q) → q: una implicación es falsa solo cuando el antecedente es verdadero y el consecuente es falso.

Para proposiciones más complejas, el procedimiento para construir tablas de verdad sigue exactamente el mismo lineamiento. Por ejemplo, en la siguiente tabla se evalúa la expresión compuesta:

\[ (p \lor \neg q) \land r \]

Dado que hay tres letras proposicionales, el número de combinaciones será 2^3=8, es decir, la tabla tendrá 8 filas. Siguiendo la secuencia lógica: primero se calcula ¬q, luego p∨¬q, y finalmente se evalúa la conjunción completa con r.

Generación con Python:

La construcción manual de tablas de verdad es una excelente forma de comprender el proceso lógico. Sin embargo, cuando se trabaja con fórmulas más largas o con más variables, puede resultar útil automatizar este procedimiento. Una forma sencilla de hacerlo es utilizando el lenguaje de programación Python junto con la biblioteca ttg (truth-table-generator 2025).

El siguiente código genera automáticamente la tabla de verdad de la proposición (p∨¬q)∧r, junto con algunas subexpresiones intermedias:

Código 1

Generación de Tabla de Verdad con ttg

                        
from ttg import Truths

# Creamos una tabla de verdad con las variables p, q y r
# y tres fórmulas: ~p, p or ~q, (p or ~q) and r
tabla = Truths(['p', 'q', 'r'], ['~p', 'p or ~q', '(p or ~q) and r'])

# Mostramos la tabla generada
print(tabla)
                        
                    

Este código realiza automáticamente las siguientes acciones:

1. Genera todas las combinaciones posibles de valores de verdad para las letras proposicionales p, q y r (en este caso, 8 combinaciones en total).
2. Evalúa las tres expresiones dadas: la negación ¬p, la disyunción p∨¬q, y finalmente la conjunción completa (p∨¬q)∧r.
3. Presenta la tabla completa con una columna para cada variable, cada subexpresión y el resultado final, facilitando la interpretación paso a paso del razonamiento lógico.

Esta herramienta es especialmente útil para validar tablas de verdad complejas, comprobar equivalencias, o preparar material educativo de forma rápida y confiable.

En la siguiente figura se muestra la salida obtenida, donde puede observarse la evaluación de cada una de las expresiones incluidas:

Figura 1 Salida de la ejecución en Python del generador de tablas de verdad

Figura 1

Salida de la ejecución en Python del generador de tablas de verdad

Al analizar proposiciones compuestas, uno de los objetivos es determinar si su valor de verdad depende de la asignación o si, por el contrario, siempre resulta igual. En este sentido, se distinguen tres casos:

• Una proposición es una tautología si su valor de verdad es siempre 1, sin importar qué valores tomen las letras proposicionales.
• Una proposición es una contradicción si su valor de verdad es siempre 0, sin importar qué valores tomen las letras proposicionales.
• Una proposición es contingente si en algunas asignaciones resulta verdadera y en otras, falsa.

Estos conceptos son importantes porque nos permiten clasificar proposiciones según su comportamiento lógico, sin necesidad de conocer su contenido específico. Por ejemplo, una tautología puede interpretarse como una regla lógica válida, mientras que una contradicción señala un error estructural en el razonamiento.

Ejemplos:

• p∨¬p es una tautología. Para cualquier valor que tome p, la disyunción será siempre verdadera.
• p∧¬p es una contradicción. Nunca puede ser verdadera porque no existe una asignación en la que p y ¬p sean simultáneamente verdaderas.
• p→q es una proposición contingente: su valor depende de la asignación particular de p y q.

A continuación, se muestra una tabla de verdad para la proposición p∨¬p, que permite verificar que su valor de verdad es siempre 1:

Tabla 8

En muchas ocasiones, dos proposiciones pueden parecer distintas a primera vista, pero al analizarlas con una tabla de verdad, descubrimos que se comportan de forma idéntica bajo todas las asignaciones posibles de valores. Cuando esto ocurre, decimos que las proposiciones son regla de tres compuesta lógicamente equivalentes.

Es decir, dos formas proposicionales son equivalentes si tienen la misma función de verdad. En este caso, escribimos P≡Q. Esta noción de equivalencia es especialmente útil en programación, por ejemplo, al simplificar condicionales dentro de un if, donde una forma más corta o clara puede hacer el código más legible y eficiente.

Ejemplo 1 - Leyes de De Morgan:

Las leyes de De Morgan son equivalencias clásicas que permiten transformar negaciones de conjunciones o disyunciones. Estas son:

\[ \neg (p \land q) \equiv \neg p \lor \neg q \quad \text{y} \quad \neg (p \lor q) \equiv \neg p \land \neg q \]

Verifiquemos una de estas equivalencias con su tabla de verdad:

Como se puede observar, las columnas de ¬(p∧q) y ¬p∨¬q coinciden completamente: son equivalentes.

Ejemplo 2 - Reescribir una implicación:

Otra equivalencia fundamental es la siguiente

\[ p \rightarrow q \equiv \neg p \lor q \]

Esta equivalencia es especialmente útil en programación para reescribir condicionales, por ejemplo:

if \( (p) \) then \( q \) es equivalente a if \( (\text{not } p \text{ or } q) \)

2.4.1. Expresiones mínimas

Toda proposición lógica puede escribirse de múltiples formas equivalentes. Algunas de ellas pueden ser más simples que otras, dependiendo de los conectores que se utilicen. En lógica formal, existen métodos para encontrar estas formas equivalentes mínimas o «formas normales».

Por ejemplo, la siguiente proposición:

\[ (p \rightarrow q) \lor (r \land \neg q) \]

es lógicamente equivalente a:

\[ \neg p \lor q \lor r \]

En lógica, no todos los conjuntos de conectores permiten expresar cualquier proposición posible. Por esta razón, se habla de conjuntos adecuados de conectores, es decir, colecciones de conectivos que son suficientes para construir cualquier función de verdad, sin necesidad de recurrir a conectores adicionales.

Un ejemplo clásico de conjunto adecuado es {∧,∨,¬}. Esto significa que cualquier proposición lógica—por más compleja que sea—puede escribirse utilizando únicamente conjunciones, disyunciones y negaciones.

Por ejemplo, los siguientes conectores pueden reescribirse así:

• Implicación:

\[ p \rightarrow q \equiv \neg p \lor q \]

• Bicondicional:

\[ p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q) \]

Este hecho tiene una aplicación directa en programación: basta con conocer y usar adecuadamente los conectores AND, OR y NOT para poder expresar cualquier condición lógica que deba ser evaluada dentro de estructuras como if, while o validaciones booleanas. Por ejemplo, en lugar de escribir una implicación, puede implementarse como una disyunción negada, haciendo el código más compatible con el lenguaje de programación en uso.

Además, en áreas como el diseño de circuitos digitales, la optimización de expresiones booleanas o la verificación de lógica en bases de datos, esta propiedad resulta esencial, ya que permite trabajar siempre con un subconjunto reducido y eficiente de conectores lógicos.