Matemáticas discretas - Lógica proposicional
Las reglas de la lógica matemática especifican métodos de razonamiento de enunciados matemáticos. El filósofo griego Aristóteles fue el pionero del razonamiento lógico. El razonamiento lógico proporciona la base teórica para muchas áreas de las matemáticas y, en consecuencia, de la informática. Tiene muchas aplicaciones prácticas en informática como diseño de máquinas informáticas, inteligencia artificial, definición de estructuras de datos para lenguajes de programación, etc.
Propositional Logicse ocupa de enunciados a los que se pueden asignar valores de verdad, "verdadero" y "falso". El propósito es analizar estas declaraciones, ya sea de forma individual o compuesta.
Lógica preposicional - Definición
Una proposición es una colección de enunciados declarativos que tiene un valor de verdad "verdadero" o un valor de verdad "falso". Una proposicional consiste en variables proposicionales y conectivos. Denotamos las variables proposicionales con letras mayúsculas (A, B, etc.). Los conectivos conectan las variables proposicionales.
A continuación se dan algunos ejemplos de propuestas:
- "El hombre es mortal", devuelve el valor de verdad "VERDADERO"
- "12 + 9 = 3 - 2", devuelve el valor verdadero "FALSO"
Lo siguiente no es una propuesta:
"A es menor que 2". Se debe a que, a menos que demos un valor específico de A, no podemos decir si el enunciado es verdadero o falso.
Conectivos
En lógica proposicional generalmente usamos cinco conectivos que son:
O ($ \ lor $)
Y ($ \ tierra $)
Negación / NO ($ \ lnot $)
Implicación / si-entonces ($ \ rightarrow $)
Si y solo si ($ \ Leftrightarrow $).
OR ($\lor$) - La operación OR de dos proposiciones A y B (escritas como $ A \ lor B $) es verdadera si al menos alguna de las variables proposicionales A o B es verdadera.
La tabla de verdad es la siguiente:
| UNA | segundo | A ∨ B |
|---|---|---|
| Cierto | Cierto | Cierto |
| Cierto | Falso | Cierto |
| Falso | Cierto | Cierto |
| Falso | Falso | Falso |
AND ($\land$) - La operación AND de dos proposiciones A y B (escritas como $ A \ land B $) es verdadera si ambas variables proposicionales A y B son verdaderas.
La tabla de verdad es la siguiente:
| UNA | segundo | A ∧ B |
|---|---|---|
| Cierto | Cierto | Cierto |
| Cierto | Falso | Falso |
| Falso | Cierto | Falso |
| Falso | Falso | Falso |
Negation ($\lnot$) - La negación de una proposición A (escrita como $ \ lno A $) es falsa cuando A es verdadera y es verdadera cuando A es falsa.
La tabla de verdad es la siguiente:
| UNA | ¬ A |
|---|---|
| Cierto | Falso |
| Falso | Cierto |
Implication / if-then ($\rightarrow$)- Una implicación $ A \ rightarrow B $ es la proposición “si A, entonces B”. Es falso si A es verdadero y B es falso. Los demás casos son ciertos.
La tabla de verdad es la siguiente:
| UNA | segundo | A → B |
|---|---|---|
| Cierto | Cierto | Cierto |
| Cierto | Falso | Falso |
| Falso | Cierto | Cierto |
| Falso | Falso | Cierto |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ es un conectivo lógico bi-condicional que es verdadero cuando pyq son iguales, es decir, ambos son falsos o ambos son verdaderos.
La tabla de verdad es la siguiente:
| UNA | segundo | A ⇔ B |
|---|---|---|
| Cierto | Cierto | Cierto |
| Cierto | Falso | Falso |
| Falso | Cierto | Falso |
| Falso | Falso | Cierto |
Tautologías
Una tautología es una fórmula que siempre es cierta para cada valor de sus variables proposicionales.
Example - Demuestre que $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ es una tautología
La tabla de verdad es la siguiente:
| UNA | segundo | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Cierto | Cierto | Cierto | Cierto | Cierto |
| Cierto | Falso | Falso | Falso | Cierto |
| Falso | Cierto | Cierto | Falso | Cierto |
| Falso | Falso | Cierto | Falso | Cierto |
Como podemos ver, cada valor de $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ es "Verdadero", es una tautología.
Contradicciones
Una contradicción es una fórmula que siempre es falsa para cada valor de sus variables proposicionales.
Example - Demuestra que $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ es una contradicción
La tabla de verdad es la siguiente:
| UNA | segundo | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Cierto | Cierto | Cierto | Falso | Falso | Falso | Falso |
| Cierto | Falso | Cierto | Falso | Cierto | Falso | Falso |
| Falso | Cierto | Cierto | Cierto | Falso | Falso | Falso |
| Falso | Falso | Falso | Cierto | Cierto | Cierto | Falso |
Como podemos ver, cada valor de $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ es “Falso”, es una contradicción.
Contingencia
Una contingencia es una fórmula que tiene valores verdaderos y falsos para cada valor de sus variables proposicionales.
Example - Demuestre que $ (A \ lor B) \ land (\ lnot A) $ una contingencia
La tabla de verdad es la siguiente:
| UNA | segundo | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Cierto | Cierto | Cierto | Falso | Falso |
| Cierto | Falso | Cierto | Falso | Falso |
| Falso | Cierto | Cierto | Cierto | Cierto |
| Falso | Falso | Falso | Cierto | Falso |
Como podemos ver, cada valor de $ (A \ lor B) \ land (\ lnot A) $ tiene tanto "Verdadero" como "Falso", es una contingencia.
Equivalencias proposicionales
Dos declaraciones X e Y son lógicamente equivalentes si se cumple alguna de las dos condiciones siguientes:
Las tablas de verdad de cada declaración tienen los mismos valores de verdad.
La declaración bi-condicional $ X \ Leftrightarrow Y $ es una tautología.
Example - Demuestra que $ \ lnot (A \ lor B) y \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ son equivalentes
Prueba por el primer método (tabla de verdad coincidente)
| UNA | segundo | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Cierto | Cierto | Cierto | Falso | Falso | Falso | Falso |
| Cierto | Falso | Cierto | Falso | Falso | Cierto | Falso |
| Falso | Cierto | Cierto | Falso | Cierto | Falso | Falso |
| Falso | Falso | Falso | Cierto | Cierto | Cierto | Cierto |
Aquí, podemos ver que los valores de verdad de $ \ lnot (A \ lor B) y \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ son los mismos, por lo que las declaraciones son equivalentes.
Probando por 2 nd método (Bi-condicionalidad)
| UNA | segundo | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Cierto | Cierto | Falso | Falso | Cierto |
| Cierto | Falso | Falso | Falso | Cierto |
| Falso | Cierto | Falso | Falso | Cierto |
| Falso | Falso | Cierto | Cierto | Cierto |
Como $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ es una tautología, las declaraciones son equivalentes.
Inversa, Conversa y Contra-positiva
Implicación / if-then $ (\ rightarrow) $ también se llama declaración condicional. Tiene dos partes:
- Hipótesis, p
- Conclusión, q
Como se mencionó anteriormente, se denota como $ p \ rightarrow q $.
Example of Conditional Statement- “Si haces tu tarea, no serás castigado”. Aquí, "haces tus deberes" es la hipótesis, p, y "no serás castigado" es la conclusión, q.
Inverse- Una inversa del enunciado condicional es la negación tanto de la hipótesis como de la conclusión. Si el enunciado es "Si p, entonces q", la inversa será "Si no p, entonces no q". Por lo tanto, la inversa de $ p \ rightarrow q $ es $ \ lnot p \ rightarrow \ lnot q $.
Example - Lo inverso de "Si haces tu tarea, no serás castigado" es "Si no haces tu tarea, serás castigado".
Converse- El inverso del enunciado condicional se calcula intercambiando la hipótesis y la conclusión. Si el enunciado es "Si p, entonces q", la inversa será "Si q, entonces p". El recíproco de $ p \ rightarrow q $ es $ q \ rightarrow p $.
Example - Lo contrario de "Si haces tu tarea, no serás castigado" es "Si no eres castigado, haz tu tarea".
Contra-positive- El contra-positivo del condicional se calcula intercambiando la hipótesis y la conclusión del enunciado inverso. Si el enunciado es "Si p, entonces q", el contra-positivo será "Si no q, entonces no p". El contra-positivo de $ p \ rightarrow q $ es $ \ lnot q \ rightarrow \ lnot p $.
Example - El contra-positivo de "Si haces tu tarea, no serás castigado" es "Si te castigan, no hiciste tu tarea".
Principio de dualidad
El principio de dualidad establece que para cualquier enunciado verdadero, el enunciado dual obtenido al intercambiar uniones en intersecciones (y viceversa) e intercambiar un conjunto universal en un conjunto nulo (y viceversa) también es cierto. Si el doble de cualquier enunciado es el enunciado en sí, se diceself-dual declaración.
Example - El dual de $ (A \ cap B) \ cup C $ es $ (A \ cup B) \ cap C $
Formas normales
Podemos convertir cualquier proposición en dos formas normales:
- Forma normal conjuntiva
- Forma normal disyuntiva
Forma normal conjuntiva
Un enunciado compuesto está en forma normal conjuntiva si se obtiene operando Y entre variables (negación de variables incluidas) conectadas con OR. En términos de operaciones de conjuntos, es un enunciado compuesto obtenido por Intersección entre variables conectadas con Uniones.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ taza Q) \ cap (Q \ taza R) $
Forma normal disyuntiva
Un enunciado compuesto está en forma disyuntiva normal si se obtiene operando OR entre variables (negación de variables incluidas) conectadas con AND. En términos de operaciones de conjuntos, es un enunciado compuesto obtenido por Unión entre variables conectadas con Intersecciones.
Examples
$ (A \ tierra B) \ lor (A \ tierra C) \ lor (B \ tierra C \ tierra D) $
$ (P \ cap Q) \ cup (Q \ cap R) $