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
Regras para negações
editar
Redução ao absurdo (ou Introdução da Negação)
editar
φ
⊢
ψ
{\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
editar
φ
{\displaystyle \varphi \,\!}
¬
φ
_
{\displaystyle {\underline {\lnot \varphi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Eliminação da dupla negação
editar
¬
¬
φ
_
{\displaystyle {\underline {\lnot \lnot \varphi }}\,\!}
φ
{\displaystyle \varphi \,\!}
Introdução da dupla negação
editar
φ
_
{\displaystyle {\underline {\varphi \quad \quad }}\,\!}
¬
¬
φ
{\displaystyle \lnot \lnot \varphi \,\!}
Regras de inferência para condicionais
editar
Introdução do condicional
editar
φ
⊢
ψ
_
{\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 \,\!}
Regras para conjunções
editar
Introdução da conjunção
editar
φ
{\displaystyle \varphi \,\!}
ψ
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}
φ
∧
ψ
{\displaystyle \varphi \land \psi \,\!}
Eliminação da conjunção
editar
φ
∧
ψ
_
{\displaystyle {\underline {\varphi \land \psi }}\,\!}
φ
{\displaystyle \varphi \,\!}
φ
∧
ψ
_
{\displaystyle {\underline {\varphi \land \psi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Regras para disjunções
editar
Introdução da disjunção
editar
φ
_
{\displaystyle {\underline {\varphi \quad \quad \ \ }}\,\!}
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
ψ
_
{\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}
φ
∨
ψ
{\displaystyle \varphi \lor \psi \,\!}
Eliminação da disjunção
editar
φ
∨
ψ
{\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 \,\!}
Regras para bicondicionais
editar
Introdução do bicondicional
editar
φ
→
ψ
{\displaystyle \varphi \rightarrow \psi \,\!}
ψ
→
φ
_
{\displaystyle {\underline {\psi \rightarrow \varphi }}\,\!}
φ
↔
ψ
{\displaystyle \varphi \leftrightarrow \psi \,\!}
Eliminação do bicondicional
editar
φ
↔
ψ
{\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
editar
Regras para universais
editar
Introdução do universal
editar
φ
(
α
:=
β
)
_
{\displaystyle {\underline {\varphi (\alpha :=\beta )}}\,\!}
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \,\!}
Restrição:
β
{\displaystyle \beta \,\!}
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \,\!}
Eliminação do universal
editar
∀
α
φ
{\displaystyle \forall \alpha \,\varphi \!}
φ
(
α
:=
β
)
¯
{\displaystyle {\overline {\varphi {(\alpha :=\beta )}}}\!}
Regras para existenciais
editar
Introdução do existencial
editar
φ
(
α
:=
β
)
_
{\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 \,\!}
Eliminação do existencial
editar
∃
α
φ
{\displaystyle \exists \alpha \,\varphi \,\!}
φ
(
α
:=
β
)
⊢
ψ
_
{\displaystyle {\underline {\varphi (\alpha :=\beta )\vdash \psi }}\,\!}
ψ
{\displaystyle \psi \,\!}
Restrição:
β
{\displaystyle \beta \,\!}
∃
α
φ
{\displaystyle \exists \alpha \varphi \,\!}
ψ
{\displaystyle \psi \,\!}
Regras de Inferência Derivadas
editar
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)
editar
α
⊢
α
{\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
Prefixação (PRF)
editar
α
⊢
β
→
α
{\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)
editar
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)
editar
{
α
,
¬
α
}
⊢
β
{\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 Tabela: Regras de Inferência
editar
Wikilivros
Referências
↑ Kenneth H. Rosen: Discrete Mathematics and its Applications , Fifth Edition, p. 58.
Ligações externas
editar
