Lista de regras de inferência

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

Regras para negações

Redução ao absurdo (ou Introdução da Negação)

${\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 \,\!}$

Eliminação da negação

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\lnot \varphi }}\,\!}$

${\displaystyle \psi \,\!}$

Eliminação da dupla negação

${\displaystyle {\underline {\lnot \lnot \varphi }}\,\!}$

${\displaystyle \varphi \,\!}$

Introdução da dupla negação

${\displaystyle {\underline {\varphi \quad \quad }}\,\!}$

${\displaystyle \lnot \lnot \varphi \,\!}$

---

Regras de inferência para condicionais

Introdução do condicional

${\displaystyle {\underline {\varphi \vdash \psi }}\,\!}$

${\displaystyle \varphi \rightarrow \psi \,\!}$

Modus ponens (ou Eliminação do 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 \,\!}$

---

Regras para conjunções

Introdução da conjunção

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \land \psi \,\!}$

Eliminação da conjunção

${\displaystyle {\underline {\varphi \land \psi }}\,\!}$

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\varphi \land \psi }}\,\!}$

${\displaystyle \psi \,\!}$

---

Regras para disjunções

Introdução da disjunção

${\displaystyle {\underline {\varphi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

Eliminação da disjunção

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle \varphi \rightarrow \chi \,\!}$

${\displaystyle {\underline {\psi \rightarrow \chi }}\,\!}$

${\displaystyle \chi \,\!}$

Silogismo disjuntivo

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!}$

${\displaystyle \psi \,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!}$

${\displaystyle \varphi \,\!}$

---

Regras para bicondicionais

Introdução do bicondicional

${\displaystyle \varphi \rightarrow \psi \,\!}$

${\displaystyle {\underline {\psi \rightarrow \varphi }}\,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

Eliminação do bicondicional

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\varphi \quad \quad }}\,\!}$

${\displaystyle \psi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\psi \quad \quad }}\,\!}$

${\displaystyle \varphi \,\!}$

---

Regras de Inferência para Lógica Clássica de Primeira Ordem

Regras para universais

Introdução do universal

${\displaystyle {\underline {\varphi (\alpha :=\beta )}}\,\!}$

${\displaystyle \forall \alpha \,\varphi \,\!}$

Restrição: ${\displaystyle \beta \,\!}$ não pode ocorrer livre em ${\displaystyle \forall \alpha \,\varphi \,\!}$ ou em qualquer hipótese vigente.

Eliminação do universal

${\displaystyle \forall \alpha \,\varphi \!}$

${\displaystyle {\overline {\varphi {(\alpha :=\beta )}}}\!}$

---

Regras para existenciais

Introdução do existencial

${\displaystyle {\underline {\varphi (\alpha :=\beta )}}\,\!}$

${\displaystyle \exists \alpha \,\varphi \,\!}$

A esta regra coloca-se a restrição de que ${\displaystyle \beta \,\!}$ deve ser substituível por ${\displaystyle \alpha ,\!}$ em ${\displaystyle \varphi \,\!}$.

Eliminação do existencial

${\displaystyle \exists \alpha \,\varphi \,\!}$

${\displaystyle {\underline {\varphi (\alpha :=\beta )\vdash \psi }}\,\!}$

${\displaystyle \psi \,\!}$

Restrição: ${\displaystyle \beta \,\!}$ não pode ocorrer livre em ${\displaystyle \exists \alpha \varphi \,\!}$, em ${\displaystyle \psi \,\!}$ ou em qualquer hipótese vigente.

---

Regras de Inferência Derivadas

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.

Repetição (R)

${\displaystyle \alpha \vdash \alpha \,\!}$

1.   ${\displaystyle \alpha \,\!}$   Premissa 2.   ${\displaystyle \neg \neg \alpha \,\!}$   1 DN 3.   ${\displaystyle \alpha \,\!}$   2 DN

Modus Tollens (MT)

${\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

Prefixação (PRF)

${\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

Contraposição (CT)

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

Contradição (CTR)

${\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

Lei de Duns Scotus (DS)

${\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

Lei de De Morgan I (DM)

${\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

Lei de De Morgan II (DM)

${\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

Legendas

• 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

Tabela: Regras de Inferência

As regras acima podem ser colocadas na seguinte tabela. ^[1] A coluna de "Tautologias" mostra como interpretar a notação de determinada regra.

Regras de Inferência	Tautologias	Nomes
${\displaystyle {\begin{aligned}p\\p\rightarrow q\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((p\wedge (p\rightarrow q))\rightarrow q}$	Modus ponens
${\displaystyle {\begin{aligned}\neg q\\p\rightarrow q\\\therefore {\overline {\neg p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((\neg q\wedge (p\rightarrow q))\rightarrow \neg p}$	Modus tollens
${\displaystyle {\begin{aligned}(p\vee q)\vee r\\\therefore {\overline {p\vee (q\vee r)}}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))}$	Associativa
${\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {q\wedge p}}\\\end{aligned}}}$	${\displaystyle (p\wedge q)\rightarrow (q\wedge p)}$	Comutativa
${\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow p\\\therefore {\overline {p\leftrightarrow q}}\\\end{aligned}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow (\ p\leftrightarrow q)}$	Introdução do bicondicional
${\displaystyle {\begin{aligned}(p\wedge q)\rightarrow r\\\therefore {\overline {p\rightarrow (q\rightarrow r)}}\\\end{aligned}}}$	${\displaystyle ((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))}$	Exportação
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)}$	Transposição da contrapositiva
${\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r))\rightarrow (p\rightarrow r)}$	Silogismo hipotético
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg p\vee q}}\\\end{aligned}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg p\vee q)}$	Implicação material
${\displaystyle {\begin{aligned}(p\vee q)\wedge r\\\therefore {\overline {(p\wedge r)\vee (q\wedge r)}}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\wedge r)\rightarrow ((p\wedge r)\vee (q\wedge r))}$	Distributiva
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {p\rightarrow (p\wedge q)}}\\\end{aligned}}}$	${\displaystyle p\rightarrow (p\wedge q)}$	Absorção
${\displaystyle {\begin{aligned}p\vee q\\\neg p\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\wedge \neg p)\rightarrow q}$	Silogismo disjuntivo
${\displaystyle {\begin{aligned}p\\\therefore {\overline {p\vee q}}\\\end{aligned}}}$	${\displaystyle p\rightarrow (p\vee q)}$	Introdução da disjunção
${\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle (p\wedge q)\rightarrow p}$	Eliminação da conjunção
${\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}$	${\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}$	Introdução da conjunção
${\displaystyle {\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}}$	${\displaystyle p\rightarrow (\neg \neg p)}$	Dupla negação
${\displaystyle {\begin{aligned}p\vee p\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle (p\vee p)\rightarrow p}$	Simplificação da disjunção
${\displaystyle {\begin{aligned}p\vee q\\\neg p\vee r\\\therefore {\overline {q\vee r}}\\\end{aligned}}}$	${\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

Ver também

• Regra de inferência
• Axioma
• Axioma esquemático

Referências

Ligações externas

• https://web.archive.org/web/20070911103236/http://pucrs.campus2.br/~annes/inflog_aula6.html
• http://www.mathpath.org/proof/proof.inference.htm