Regras de inferência são regras de transformação sintáticas que podem ser usadas para inferir uma conclusão a partir de uma premissa, para criar um argumento. Um conjunto de regras pode ser usada para inferir qualquer conclusão válida, se esta conclusão for completa. Entretanto nunca se pode inferir uma conclusão inválida, se isto for assegurado. Um completo e seguro conjunto de regras não precisa incluir cada regra da listagem a seguir, já que muitas delas são redundantes, e podem ser provadas com o uso de outras regras.
Regras de Inferência Para Cálculo Proposicional Clássico [ editar | editar código-fonte ] φ ⊢ ψ {\displaystyle \varphi \vdash \psi \,\!} φ ⊢ ¬ ψ _ {\displaystyle {\underline {\varphi \vdash \lnot \psi }}\,\!} ¬ φ {\displaystyle \lnot \varphi \,\!} Redução ao absurdo (Relacionada à lei do terceiro excluído)
¬ φ ⊢ ψ {\displaystyle \lnot \varphi \vdash \psi \,\!} ¬ φ ⊢ ¬ ψ _ {\displaystyle {\underline {\lnot \varphi \vdash \lnot \psi }}\,\!} φ {\displaystyle \varphi \,\!} φ {\displaystyle \varphi \,\!} ¬ φ _ {\displaystyle {\underline {\lnot \varphi }}\,\!} ψ {\displaystyle \psi \,\!} ¬ ¬ φ _ {\displaystyle {\underline {\lnot \lnot \varphi }}\,\!} φ {\displaystyle \varphi \,\!} φ _ {\displaystyle {\underline {\varphi \quad \quad }}\,\!} ¬ ¬ φ {\displaystyle \lnot \lnot \varphi \,\!} φ ⊢ ψ _ {\displaystyle {\underline {\varphi \vdash \psi }}\,\!} φ → ψ {\displaystyle \varphi \rightarrow \psi \,\!} φ → ψ {\displaystyle \varphi \rightarrow \psi \,\!} φ _ {\displaystyle {\underline {\varphi \quad \quad \quad }}\,\!} ψ {\displaystyle \psi \,\!} φ → ψ {\displaystyle \varphi \rightarrow \psi \,\!} ¬ ψ _ {\displaystyle {\underline {\lnot \psi \quad \quad \quad }}\,\!} ¬ φ {\displaystyle \lnot \varphi \,\!} φ {\displaystyle \varphi \,\!} ψ _ {\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!} φ ∧ ψ {\displaystyle \varphi \land \psi \,\!} φ ∧ ψ _ {\displaystyle {\underline {\varphi \land \psi }}\,\!} φ {\displaystyle \varphi \,\!} φ ∧ ψ _ {\displaystyle {\underline {\varphi \land \psi }}\,\!} ψ {\displaystyle \psi \,\!} φ _ {\displaystyle {\underline {\varphi \quad \quad \ \ }}\,\!} φ ∨ ψ {\displaystyle \varphi \lor \psi \,\!} ψ _ {\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!} φ ∨ ψ {\displaystyle \varphi \lor \psi \,\!} φ ∨ ψ {\displaystyle \varphi \lor \psi \,\!} φ → χ {\displaystyle \varphi \rightarrow \chi \,\!} ψ → χ _ {\displaystyle {\underline {\psi \rightarrow \chi }}\,\!} χ {\displaystyle \chi \,\!} φ ∨ ψ {\displaystyle \varphi \lor \psi \,\!} ¬ φ _ {\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!} ψ {\displaystyle \psi \,\!}
φ ∨ ψ {\displaystyle \varphi \lor \psi \,\!} ¬ ψ _ {\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!} φ {\displaystyle \varphi \,\!} φ → ψ {\displaystyle \varphi \rightarrow \psi \,\!} ψ → φ _ {\displaystyle {\underline {\psi \rightarrow \varphi }}\,\!} φ ↔ ψ {\displaystyle \varphi \leftrightarrow \psi \,\!} φ ↔ ψ {\displaystyle \varphi \leftrightarrow \psi \,\!} φ _ {\displaystyle {\underline {\varphi \quad \quad }}\,\!} ψ {\displaystyle \psi \,\!}
φ ↔ ψ {\displaystyle \varphi \leftrightarrow \psi \,\!} ψ _ {\displaystyle {\underline {\psi \quad \quad }}\,\!} φ {\displaystyle \varphi \,\!} φ ( α := β ) _ {\displaystyle {\underline {\varphi (\alpha :=\beta )}}\,\!} ∀ α φ {\displaystyle \forall \alpha \,\varphi \,\!} Restrição: β {\displaystyle \beta \,\!} ∀ α φ {\displaystyle \forall \alpha \,\varphi \,\!}
∀ α φ {\displaystyle \forall \alpha \,\varphi \!} φ ( α := β ) ¯ {\displaystyle {\overline {\varphi {(\alpha :=\beta )}}}\!} φ ( α := β ) _ {\displaystyle {\underline {\varphi (\alpha :=\beta )}}\,\!} ∃ α φ {\displaystyle \exists \alpha \,\varphi \,\!} A esta regra coloca-se a restrição de que β {\displaystyle \beta \,\!} α , {\displaystyle \alpha ,\!} φ {\displaystyle \varphi \,\!}
∃ α φ {\displaystyle \exists \alpha \,\varphi \,\!} φ ( α := β ) ⊢ ψ _ {\displaystyle {\underline {\varphi (\alpha :=\beta )\vdash \psi }}\,\!} ψ {\displaystyle \psi \,\!} Restrição: β {\displaystyle \beta \,\!} ∃ α φ {\displaystyle \exists \alpha \varphi \,\!} ψ {\displaystyle \psi \,\!}
Por meio das regras de inferência diretas e hipotéticas podemos demonstrar vários raciocínios bastante recorrentes. Estes raciocínios, uma vez demonstrados, podem ser usados como regras de inferência diretas. Elas não são necessárias, mas são bastante úteis, tornando nossas derivações muito mais sucintas.
Agora ampliaremos nossa lista de regras de inferência, além de fazer suas respectivas demonstrações.
α ⊢ α {\displaystyle \alpha \vdash \alpha \,\!}
1. α {\displaystyle \alpha \,\!} Premissa 2. ¬ ¬ α {\displaystyle \neg \neg \alpha \,\!} 1 DN 3. α {\displaystyle \alpha \,\!} 2 DN
{ α → β , ¬ β } ⊢ ¬ α {\displaystyle \left\{\alpha \to \beta ,\neg \beta \right\}\vdash \neg \alpha \,\!}
1. α → β {\displaystyle \alpha \to \beta \,\!} Premissa 2. ¬ β {\displaystyle \neg \beta \,\!} Premissa
3. α {\displaystyle \alpha \,\!} Hipótese 4. β {\displaystyle \beta \,\!} 1,3 MP 5. β ∧ ¬ β {\displaystyle \beta \land \neg \beta \,\!} 2,4 C
6. ¬ α {\displaystyle \neg \alpha \,\!} 3,5 RAA
α ⊢ β → α {\displaystyle \alpha \vdash \beta \to \alpha \,\!}
1. α {\displaystyle \alpha \,\!} Premissa
2. β {\displaystyle \beta \,\!} Hipótese 3. α {\displaystyle \alpha \,\!} 1 R
4. β → α {\displaystyle \beta \to \alpha \,\!} 2,3 RPC
Utilizaremos o Modus Tollens como regra de inferência.
α → β ⊢ ¬ β → ¬ α {\displaystyle \alpha \to \beta \vdash \neg \beta \to \neg \alpha \,\!}
1. α → β {\displaystyle \alpha \to \beta \,\!} Premissa
2. ¬ β {\displaystyle \neg \beta \,\!} Hipótese 3. ¬ α {\displaystyle \neg \alpha \,\!} 1,2 MT
4. ¬ β → ¬ α {\displaystyle \neg \beta \to \neg \alpha \,\!} 2,3 RPC
{ α , ¬ α } ⊢ β {\displaystyle \left\{\alpha ,\neg \alpha \right\}\vdash \beta }
1. α {\displaystyle \alpha \,\!} Premissa 2. ¬ α {\displaystyle \neg \alpha \,\!} Premissa 3. α ∨ β {\displaystyle \alpha \lor \beta \,\!} 1 E 4. β {\displaystyle \beta \,\!} 2,3 SD
¬ α ⊢ α → β {\displaystyle \neg \alpha \vdash \alpha \to \beta }
1. ¬ α {\displaystyle \neg \alpha \,\!} Premissa
2. α {\displaystyle \alpha \,\!} Hipótese 3. β {\displaystyle \beta \,\!} 1,2 CTR
4. α → β {\displaystyle \alpha \to \beta \,\!} 2,3 RPC
¬ ( α ∨ β ) ⊢ ¬ α ∧ ¬ β {\displaystyle \neg \left(\alpha \lor \beta \right)\vdash \neg \alpha \land \neg \beta \,\!}
01. ¬ ( α ∨ β ) {\displaystyle \neg \left(\alpha \lor \beta \right)\,\!} Premissa
02. α {\displaystyle \alpha \,\!} Hipótese 03. α ∨ β {\displaystyle \alpha \lor \beta \,\!} 2 E 04. ( α ∨ β ) ∧ ¬ ( α ∨ β ) {\displaystyle \left(\alpha \lor \beta \right)\land \neg \left(\alpha \lor \beta \right)\,\!} 1,3 C
05. ¬ α {\displaystyle \neg \alpha \,\!} 2,4 RAA
06. β {\displaystyle \beta \,\!} Hipótese 07. α ∨ β {\displaystyle \alpha \lor \beta \,\!} 6 E 08. ( α ∨ β ) ∧ ¬ ( α ∨ β ) {\displaystyle \left(\alpha \lor \beta \right)\land \neg \left(\alpha \lor \beta \right)\,\!} 1,7 C
09. ¬ β {\displaystyle \neg \beta \,\!} 6,8 RAA
10. ¬ α ∧ ¬ β {\displaystyle \neg \alpha \land \neg \beta \,\!} 5,9 C
¬ ( α ∧ β ) ⊢ ¬ α ∨ ¬ β {\displaystyle \neg \left(\alpha \land \beta \right)\vdash \neg \alpha \lor \neg \beta \,\!}
01. ¬ ( α ∧ β ) {\displaystyle \neg \left(\alpha \land \beta \right)} Premissa
02. ¬ ( ¬ α ∨ ¬ β ) {\displaystyle \neg \left(\neg \alpha \lor \neg \beta \right)} Hipótese
03. ¬ α {\displaystyle \neg \alpha \,\!} Hipótese 04. ¬ α ∨ ¬ β {\displaystyle \neg \alpha \lor \neg \beta } 3 E 05. ( ¬ α ∨ ¬ β ) ∧ ¬ ( ¬ α ∨ ¬ β ) {\displaystyle \left(\neg \alpha \lor \neg \beta \right)\land \neg \left(\neg \alpha \lor \neg \beta \right)} 5,2 C
06. ¬ ¬ α {\displaystyle \neg \neg \alpha } 3,5 RAA 07. α {\displaystyle \alpha \,\!} 6 DN
08. ¬ β {\displaystyle \neg \beta \,\!} Hipótese 09. ¬ α ∨ ¬ β {\displaystyle \neg \alpha \lor \neg \beta } 8 E 10. ( ¬ α ∨ ¬ β ) ∧ ¬ ( ¬ α ∨ ¬ β ) {\displaystyle \left(\neg \alpha \lor \neg \beta \right)\land \neg \left(\neg \alpha \lor \neg \beta \right)} 9,2 C
11. ¬ ¬ β {\displaystyle \neg \neg \beta } 8,10 RAA 12. β {\displaystyle \beta \,\!} 11 DN 13. α ∧ β {\displaystyle \alpha \land \beta \,\!} 7,12 C 14. ( α ∧ β ) ∧ ¬ ( α ∧ β ) {\displaystyle \left(\alpha \land \beta \right)\land \neg \left(\alpha \land \beta \right)} 13,1 C
15. ¬ ¬ ( ¬ α ∨ ¬ β ) {\displaystyle \neg \neg \left(\neg \alpha \lor \neg \beta \right)} 2,14 RAA 16. ¬ α ∨ ¬ β {\displaystyle \neg \alpha \lor \neg \beta } 15 DN
DN - Dupla Negação SD - Sislogismo Disjuntivo C - Conjunção S - Separação E - Expansão MP - Modus Ponens BC - Bicondicionais para bicondicionais RAA - Redução ao absurdo RPC - Regra de prova condicional As regras acima podem ser colocadas na seguinte tabela. [ 1]
Regras de Inferência Tautologias Nomes 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 ) ∨ r ) → ( p ∨ ( q ∨ r ) ) {\displaystyle ((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))} Associativa 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)} Comutativa 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)} Introdução do bicondicional ( 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 ) → ( p → ( q → r ) ) {\displaystyle ((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))} Exportação 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)} Transposição da contrapositiva 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)} Implicação 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)} Absorção 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 disjuntivo p ∴ p ∨ q ¯ {\displaystyle {\begin{aligned}p\\\therefore {\overline {p\vee q}}\\\end{aligned}}} p → ( p ∨ q ) {\displaystyle p\rightarrow (p\vee q)} Introdução da disjunção 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} Eliminação da conjunção 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)} Introdução da conjunção p ∴ ¬ ¬ p ¯ {\displaystyle {\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}} p → ( ¬ ¬ p ) {\displaystyle p\rightarrow (\neg \neg p)} Dupla negação 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} Simplificação da disjunção 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)} Resolução
Todas as regras usam operadores lógicos básicos. A tabela completa de "operadores lógicos" é mostrada por uma tabela verdade , dando valoração verdade a todas as possíveis (16) funções verdade para 2 variáveis booleanas (p,q):
p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T T F F F F F F F F T T T T T T T T T F F F F F T T T T F F F F T T T T F T F F T T F F T T F F T T F F T T F F F T F T F T F T F T F T F T F T
Wikilivros Referências ↑ Kenneth H. Rosen: Discrete Mathematics and its Applications , Fifth Edition, p. 58.
Visão global
Áreas Conceitos
French
Deutsch
