Esta es una lista de reglas de inferencia , leyes lógicas que están relacionadas con fórmulas matemáticas.
Introducción
editar
Las reglas de inferencia son reglas de transformación sintácticas que se pueden usar para inferir una conclusión a partir de una premisa para crear un argumento. Se puede utilizar un conjunto de reglas para inferir cualquier conclusión válida si es completa, mientras que nunca se infiere una conclusión válida, si no es segura. Un conjunto de reglas completo y seguro no necesita incluir todas las reglas de la siguiente lista, ya que muchas de las reglas son redundantes, y se pueden probar mediante las demás reglas.
Las reglas de descarga permiten la inferencia de una subderivación basada en una suposición temporal. La notación siguiente
φ
⊢
ψ
{\displaystyle \varphi \vdash \psi \,\!}
indica dicha subderivación a partir del supuesto temporal
φ
{\displaystyle \varphi \,\!}
ψ
{\displaystyle \psi \,\!}
Reglas para la lógica sentencial clásica
editar
La lógica sentencial también se conoce como lógica proposicional .
Reglas para la negaciones
editar
Reductio ad absurdum (o Introducción de la Negación )
φ
⊢
ψ
{\displaystyle \varphi \vdash \psi \,\!}
φ
⊢
¬
ψ
_
{\displaystyle {\underline {\varphi \vdash \lnot \psi }}\,\!}
¬
φ
{\displaystyle \lnot \varphi \,\!}
Reductio ad absurdum (relacionada con el principio del tercero excluido )
¬
φ
⊢
ψ
{\displaystyle \lnot \varphi \vdash \psi \,\!}
¬
φ
⊢
¬
ψ
_
{\displaystyle {\underline {\lnot \varphi \vdash \lnot \psi }}\,\!}
φ
{\displaystyle \varphi \,\!}
No contradicción (o Negación de la eliminación )
φ
{\displaystyle \varphi \,\!}
¬
φ
_
{\displaystyle {\underline {\lnot \varphi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Eliminación de la doble negación
¬
¬
φ
_
{\displaystyle {\underline {\lnot \lnot \varphi }}\,\!}
φ
{\displaystyle \varphi \,\!}
Introducción de la doble negación
φ
_
{\displaystyle {\underline {\varphi \quad \quad }}\,\!}
¬
¬
φ
{\displaystyle \lnot \lnot \varphi \,\!}
Reglas para condicionales
editar
Teorema de la deducción (o Introducción del Condicional
φ
⊢
ψ
_
{\displaystyle {\underline {\varphi \vdash \psi }}\,\!}
φ
→
ψ
{\displaystyle \varphi \rightarrow \psi \,\!}
Modus ponens (o Eliminación del Condicional )
φ
→
ψ
{\displaystyle \varphi \rightarrow \psi \,\!}
φ
_
{\displaystyle {\underline {\varphi \quad \quad \quad }}\,\!}
ψ
{\displaystyle \psi \,\!}
Modus tollens
φ
→
ψ
{\displaystyle \varphi \rightarrow \psi \,\!}
¬
ψ
_
{\displaystyle {\underline {\lnot \psi \quad \quad \quad }}\,\!}
¬
φ
{\displaystyle \lnot \varphi \,\!}
Reglas para conjunciones
editar
Adjunción (o Introducción de la Conjunción )
φ
{\displaystyle \varphi \,\!}
ψ
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}
φ
∧
ψ
{\displaystyle \varphi \land \psi \,\!}
Simplificación (o Eliminación de la Conjunción )
φ
∧
ψ
_
{\displaystyle {\underline {\varphi \land \psi }}\,\!}
φ
{\displaystyle \varphi \,\!}
φ
∧
ψ
_
{\displaystyle {\underline {\varphi \land \psi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Reglas para disyunciones
editar
Adición (o Introducción de la Disyunción )
φ
_
{\displaystyle {\underline {\varphi \quad \quad \ \ }}\,\!}
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
ψ
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
Análisis de casos
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
φ
→
χ
{\displaystyle \varphi \rightarrow \chi \,\!}
ψ
→
χ
_
{\displaystyle {\underline {\psi \rightarrow \chi }}\,\!}
χ
{\displaystyle \chi \,\!}
Silogismo disyuntivo
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
¬
φ
_
{\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!}
ψ
{\displaystyle \psi \,\!}
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
¬
ψ
_
{\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!}
φ
{\displaystyle \varphi \,\!}
Reglas para bicondicionales
editar
Introducción del bicondicional
φ
→
ψ
{\displaystyle \varphi \rightarrow \psi \,\!}
ψ
→
φ
_
{\displaystyle {\underline {\psi \rightarrow \varphi }}\,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
Eliminación del bicondicional
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
φ
_
{\displaystyle {\underline {\varphi \quad \quad }}\,\!}
ψ
{\displaystyle \psi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
ψ
_
{\displaystyle {\underline {\psi \quad \quad }}\,\!}
φ
{\displaystyle \varphi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
¬
φ
_
{\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!}
¬
ψ
{\displaystyle \lnot \psi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
¬
ψ
_
{\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!}
¬
φ
{\displaystyle \lnot \varphi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
ψ
∨
φ
_
{\displaystyle {\underline {\psi \lor \varphi }}\,\!}
ψ
∧
φ
{\displaystyle \psi \land \varphi \,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
¬
ψ
∨
¬
φ
_
{\displaystyle {\underline {\lnot \psi \lor \lnot \varphi }}\,\!}
¬
ψ
∧
¬
φ
{\displaystyle \lnot \psi \land \lnot \varphi \,\!}
En las siguientes reglas,
φ
(
β
/
α
)
{\displaystyle \varphi (\beta /\alpha )\,\!}
φ
{\displaystyle \varphi \,\!}
β
{\displaystyle \beta \,\!}
φ
{\displaystyle \varphi \,\!}
α
{\displaystyle \alpha \,\!}
Generalización Universal (o Introducción Universal )
φ
(
β
/
α
)
_
{\displaystyle {\underline {\varphi {(\beta /\alpha )}}}\,\!}
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \,\!}
Restricción 1:
β
{\displaystyle \beta }
φ
{\displaystyle \varphi }
β
{\displaystyle \beta }
Instanciación Universal (o Eliminación Universal )
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \!}
φ
(
β
/
α
)
¯
{\displaystyle {\overline {\varphi {(\beta /\alpha )}}}\!}
Restricción: No hay ocurrencia libre de
α
{\displaystyle \alpha \,\!}
φ
{\displaystyle \varphi \,\!}
β
{\displaystyle \beta \,\!}
Generalización Existencial (o Introducción Existential )
φ
(
β
/
α
)
_
{\displaystyle {\underline {\varphi (\beta /\alpha )}}\,\!}
∃
α
φ
{\displaystyle \exists \alpha \,\varphi \,\!}
Instanciación Existencial (o Eliminación Existential )
∃
α
φ
{\displaystyle \exists \alpha \,\varphi \,\!}
φ
(
β
/
α
)
⊢
ψ
_
{\displaystyle {\underline {\varphi (\beta /\alpha )\vdash \psi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Restricción 1:
β
{\displaystyle \beta }
φ
{\displaystyle \varphi \,\!}
β
{\displaystyle \beta \,\!}
ψ
{\displaystyle \psi \,\!}
β
{\displaystyle \beta }
Tabla: Reglas de Inferencia
editar
Las reglas anteriores se pueden resumir en la siguiente tabla.[ 1] Tautología " muestra cómo interpretar la notación de una regla dada.
Regla de inferencia
Tautología
Nombre
p
p
→
q
∴
q
¯
{\displaystyle {\begin{aligned}p\\p\rightarrow q\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}
(
(
p
∧
(
p
→
q
)
)
→
q
{\displaystyle ((p\wedge (p\rightarrow q))\rightarrow q}
Modus ponens
¬
q
p
→
q
∴
¬
p
¯
{\displaystyle {\begin{aligned}\neg q\\p\rightarrow q\\\therefore {\overline {\neg p\quad \quad \quad }}\\\end{aligned}}}
(
(
¬
q
∧
(
p
→
q
)
)
→
¬
p
{\displaystyle ((\neg q\wedge (p\rightarrow q))\rightarrow \neg p}
Modus tollens
(
p
∨
q
)
∨
r
∴
p
∨
(
q
∨
r
)
¯
{\displaystyle {\begin{aligned}(p\vee q)\vee r\\\therefore {\overline {p\vee (q\vee r)}}\\\end{aligned}}}
(
(
p
∨
q
)
∨
c
)
→
p
∨
(
p
∨
q
)
{\displaystyle ((p\vee q)\vee c)\rightarrow p\vee (p\vee q)}
Asociativas
p
∧
q
∴
q
∧
p
¯
{\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {q\wedge p}}\\\end{aligned}}}
(
p
∧
q
)
→
(
q
∧
p
)
{\displaystyle (p\wedge q)\rightarrow (q\wedge p)}
Conmutativa
p
→
q
q
→
p
∴
p
⇔
q
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow p\\\therefore {\overline {p\Leftrightarrow q}}\\\end{aligned}}}
(
(
p
→
q
)
∧
(
q
→
p
)
)
→
p
⇔
q
{\displaystyle ((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow \ p\Leftrightarrow q}
Ley de proposiciones bicondicionales
(
p
∧
q
)
→
r
∴
p
→
(
q
→
r
)
¯
{\displaystyle {\begin{aligned}(p\wedge q)\rightarrow r\\\therefore {\overline {p\rightarrow (q\rightarrow r)}}\\\end{aligned}}}
p
→
(
q
→
r
)
{\displaystyle p\rightarrow (q\rightarrow r)}
Exportación
p
→
q
∴
¬
q
→
¬
p
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}}
(
p
→
q
)
→
(
¬
q
→
¬
p
)
{\displaystyle (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)}
Transposición o ley del contrarrecíproco
p
→
q
q
→
r
∴
p
→
r
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}
(
(
p
→
q
)
∧
(
q
→
r
)
)
→
(
p
→
r
)
{\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r))\rightarrow (p\rightarrow r)}
Silogismo hipotético
p
→
q
∴
¬
p
∨
q
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg p\vee q}}\\\end{aligned}}}
(
p
→
q
)
→
(
¬
p
∨
q
)
{\displaystyle (p\rightarrow q)\rightarrow (\neg p\vee q)}
Implicación material
(
p
∨
q
)
∧
r
∴
(
p
∧
r
)
∨
(
q
∧
r
)
¯
{\displaystyle {\begin{aligned}(p\vee q)\wedge r\\\therefore {\overline {(p\wedge r)\vee (q\wedge r)}}\\\end{aligned}}}
(
(
p
∨
q
)
∧
r
)
→
(
(
p
∧
r
)
∨
(
q
∧
r
)
)
{\displaystyle ((p\vee q)\wedge r)\rightarrow ((p\wedge r)\vee (q\wedge r))}
Distributiva
p
→
q
∴
p
→
(
p
∧
q
)
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {p\rightarrow (p\wedge q)}}\\\end{aligned}}}
p
→
(
p
∧
q
)
{\displaystyle p\rightarrow (p\wedge q)}
Absorción
p
∨
q
¬
p
∴
q
¯
{\displaystyle {\begin{aligned}p\vee q\\\neg p\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}
(
(
p
∨
q
)
∧
¬
p
)
→
q
{\displaystyle ((p\vee q)\wedge \neg p)\rightarrow q}
Silogismo disyuntivo
p
∴
p
∨
q
¯
{\displaystyle {\begin{aligned}p\\\therefore {\overline {p\vee q}}\\\end{aligned}}}
p
→
(
p
∨
q
)
{\displaystyle p\rightarrow (p\vee q)}
Adición
p
q
∴
p
∧
q
¯
{\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}
(
(
p
)
∧
(
q
)
)
→
(
p
∧
q
)
{\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}
Adjunción
p
∧
q
∴
p
¯
{\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}
(
p
∧
q
)
→
p
{\displaystyle (p\wedge q)\rightarrow p}
Simplificación
p
q
∴
p
∧
q
¯
{\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}
(
(
p
)
∧
(
q
)
)
→
(
p
∧
q
)
{\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}
Conjunción
p
∴
¬
¬
p
¯
{\displaystyle {\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}}
p
→
(
¬
¬
p
)
{\displaystyle p\rightarrow (\neg \neg p)}
Doble negación
p
∨
p
∴
p
¯
{\displaystyle {\begin{aligned}p\vee p\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}
(
p
∨
p
)
→
p
{\displaystyle (p\vee p)\rightarrow p}
Simplificación disyuntiva
p
∨
q
¬
p
∨
r
∴
q
∨
r
¯
{\displaystyle {\begin{aligned}p\vee q\\\neg p\vee r\\\therefore {\overline {q\vee r}}\\\end{aligned}}}
(
(
p
∨
q
)
∧
(
¬
p
∨
r
)
)
→
(
q
∨
r
)
{\displaystyle ((p\vee q)\wedge (\neg p\vee r))\rightarrow (q\vee r)}
Resolución
Todas las reglas de uso de los operadores lógicos básicos. Se muestra una tabla completa de "operadores lógicos" mediante una tabla de verdad , dando definiciones de todas las posibles (16) funciones de verdad de las 2 variables booleanas (p , q ):
p q
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
V
V
F
F
F
F
F
F
F
F
V
V
V
V
V
V
V
V
V
F
F
F
F
F
V
V
V
V
F
F
F
F
V
V
V
V
F
V
F
F
V
V
F
F
V
V
F
F
V
V
F
F
V
V
F
F
F
V
F
V
F
V
F
V
F
V
F
V
F
V
F
V
donde V = verdadero y F = falso, y, las columnas son los operadores lógicos: 0 , falso, Contradicción ; 1 , NOR, NOR lógico ; 2 , Conversión no implicación ; 3 , ¬p, Negación ; 4 , No implicación material ; 5 , ¬Q, Negación ; 6 , XOR, Disyunción exclusiva ; 7 , NAND, NAND lógico ; 8 , Y, Conjunción lógica ; 9 , XNOR, Si y solo si , Bicondicional lógico ; 10 , q, Función de proyección; 11 , si/entonces, Implicación lógica ; 12 , p, Función de proyección; 13 , entonces/si, Implicación inversa ; 14 , O, Disyunción lógica ; 15 , verdad, Tautología .
Cada operador lógico se puede utilizar en una afirmación acerca de variables y operaciones, mostrando una regla básica de inferencia. Ejemplos:
El operador de la columna-14 (O), muestra la Regla de la adición : cuando p =V (la hipótesis selecciona las dos primeras líneas de la tabla), vemos (en la columna-14) que p ∨q =V.
Se puede ver también que, con la misma premisa, otras conclusiones son válidas: las columnas 12, 14 y 15 son V.
El operador de la columna-8 (Y), muestra la Regla de simplificación : cuando p ∧q =V (primera línea de la tabla), se ve que p =V.
Con esta premisa, también se concluye que q =V, p ∨q =V, etc. como se muestra por columnas 9-15.
El operador de la columna-11 (SI/ENTONCES), muestra la Regla Modus ponens : cuando p →q =V y p =V sólo una línea de la tabla de verdad (la primera) satisface estas dos condiciones. En esta línea, q también es cierta. Por lo tanto, cada vez que p→q es cierta y p es cierta, q también debe ser cierta. Consideremos los siguientes supuestos: "Si llueve hoy, entonces no vamos a entrar en una canoa. Si hoy no nos vamos en un viaje en canoa, entonces vamos a ir en un viaje en canoa mañana. Por lo tanto (símbolo matemático para "por lo tanto", es
∴
{\displaystyle \therefore }
q
{\displaystyle q}
r
{\displaystyle r}
p
→
q
q
→
r
∴
p
→
r
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}
Consideremos un conjunto más complejo de hipótesis: "No está soleado hoy y hace más frío que ayer". "Vamos a ir a nadar solamente si está soleado", "Si no vamos natación, entonces tendremos una barbacoa", y "Si vamos a tener una barbacoa, entonces vamos a estar en casa a la puesta del sol" lleva a concluir que "Vamos a estar en casa a la puesta del sol". Demostrado por reglas de inferencia: Sea
p
{\displaystyle p}
q
{\displaystyle q}
r
{\displaystyle r}
s
{\displaystyle s}
t
{\displaystyle t}
¬
p
∧
q
,
r
→
p
,
¬
r
→
s
{\displaystyle \neg p\wedge q,r\rightarrow p,\neg r\rightarrow s}
s
→
t
{\displaystyle s\rightarrow t}
t
{\displaystyle t}
Paso
Razón
1.
¬
p
∧
q
{\displaystyle \neg p\wedge q}
Hipótesis
2.
¬
p
{\displaystyle \neg p}
Simplificación usando Paso 1
3.
r
→
p
{\displaystyle r\rightarrow p}
Hipótesis
4.
¬
r
{\displaystyle \neg r}
Modus tollens usando el Paso 2 y 3
5.
¬
r
→
s
{\displaystyle \neg r\rightarrow s}
Hipótesis
6.
s
{\displaystyle s}
Modus ponens usando el Paso 4 y 5
7.
s
→
t
{\displaystyle s\rightarrow t}
Hipótesis
8.
t
{\displaystyle t}
Modus ponens usando el Paso 6 y 7
↑ Kenneth H. Rosen: Discrete Mathematics and its Applications ,5.ª edición, p. 58.
Enlaces externos
editar
