Tautología (lógica)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de noviembre de 2018; las comprobaciones requieren 4 ediciones .

Una tautología en lógica es una proposición idénticamente verdadera .

El hecho de que la fórmula A sea una tautología se denota por . Cada cálculo lógico tiene su propio conjunto de tautologías. $\vGuión A$

Construcción de tautologías

Para averiguar si una fórmula dada es una tautología, hay una manera simple en el álgebra proposicional: construir una tabla de verdad . En cálculo proposicional, las tautologías son axiomas (más precisamente, esquemas de axiomas), así como todas las fórmulas que se pueden obtener de tautologías conocidas usando reglas de inferencia dadas (la mayoría de las veces son Modus ponens y la regla de sustitución ). Comprobar si una fórmula dada en el cálculo proposicional es una tautología es más complicado y también depende del sistema de axiomas y reglas de inferencia disponibles.
El problema de determinar si una fórmula arbitraria en lógica de predicados es una tautología es algorítmicamente indecidible.

Ejemplos de tautologías

Tautologías del cálculo proposicional (y álgebra proposicional)

$A\flecha derecha A$ ("De A sigue a A ") - la ley de identidad
$(A)\or (\lno A)$ (" A o no- A ") - la ley del tercero excluido
$\neg (P\tierra \neg P)$ - la ley de la negación de la contradicción
$\neg \neg P\rightarrow P$ - ley de la doble negación
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - ley de los opuestos
$(P\land Q)\leftrightarrow (Q\land P)$ — conmutatividad de la conjunción
$(P\lor Q)\leftrightarrow (Q\lor P)$ — conmutatividad de la disyunción
$[(P\land Q)\land R]\leftrightarrow [P\land (Q\land R)]$ - asociatividad de la conjunción
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - asociatividad de la disyunción
$(P\land (P\rightarrow Q))\rightarrow Q$
$A\flecha derecha (B\flecha derecha A)$ (la verdad se sigue de cualquier cosa)
$(A\rightarrow B)\cuña (B\rightarrow C)\rightarrow (A\rightarrow C)$ - cadena de reglas
$(A\vee B)\cuña C\leftrightarrow (A\cuña C)\vee (B\cuña C)$ — distributividad de la conjunción con respecto a la disyunción
$(A\cuña B)\vee C\leftrightarrow (A\vee C)\cuña (B\vee C)$ — distributividad de la disyunción con respecto a la conjunción
$(P\land P)\leftrightarrow P$ - conjunción idempotente
$(P\lor P)\leftrightarrow P$ — idempotencia de la disyunción
$(P\rightarrow Q)\leftrightarrow (\neg P\lor Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\tierra (Q\lor P)\leftrightarrow P$ - la primera ley de absorción
$(P\lor (Q\land P)\leftrightarrow P$ - la segunda ley de absorción
$\neg (A\wedge B)\leftrightarrow (\neg A\vee \neg B)$ - Primera ley de De Morgan
$\neg (A\vee B)\leftrightarrow (\neg A\cuña \neg B)$ - Segunda ley de De Morgan
$(A\rightarrow B)\leftrightarrow (\neg B\rightarrow \neg A)$ - ley de la contraposición
Si y son fórmulas, entonces ( regla de sustitución ) $\vGuión F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vGuión F(H_{1},...,H_{n})$

Tautologías del cálculo de predicados (y álgebra de predicados)

Si es una tautología en cálculo proposicional y son predicados, entonces es una tautología en cálculo de predicados $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\leftrightarrow (\exists x)\neg P(x)$

$\neg (\existe x)P(x)\leftrightarrow (\forall x)\neg P(x)$ ( Ley de Morgan )

$(\para todas las x)(P(x)\cuña Q(x))\flecha izquierda-derecha (\para todas las x)P(x)\cuña (\para todas las x)Q(x)$
$(\existe x)(P(x)\vee Q(x))\leftrightarrow (\existe x)P(x)\vee (\existe x)Q(x)$
$Q\leftrightarrow (\existe x)Q$
$Q\leftrightarrow (\forall x)Q$
$(\para todo x)P(x)\rightarrow P(y)$
$P(y)\rightarrow (\existe x)P(x)$
$(\para todo x)(\para todo y)P(x,y)\leftrightarrow (\para todo y)(\para todo x)P(x,y)$
$(\existe x)(\existe y)P(x,y)\leftrightarrow (\existe y)(\existe x)P(x,y)$
$(\existe x)(\para todo y)P(x,y)\rightarrow (\para todo y)(\existe x)P(x,y)$

Véase también

Notas

Literatura

V. Igoshin, Lógica Matemática y Teoría de Algoritmos. — Academia, 2008.
Karpov Yu. G. "Teoría de los autómatas". - P., 2003. - S. 49, 60.
Mendelsohn E. "Introducción a la lógica matemática". - M. Nauka, 1971.
V. Igoshin «Libro-taller de problemas de lógica matemática». - Ilustración, 1986.