Buscar

Resumo de Lógica

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 15 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 15 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 15 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

0.0.1 Linguagem LP da Lógica Proposicional Clássica
De…nição 1 O alfabeto a ser utilizado consiste dos seguintes símbolos:
a) Variáveis Proposicionais: p0; p1; p2; ::: .(uma lista in…nita);
b) Sinais de Pontuação: (e).
c) Conectivos: :;^;_;�! e ! :
símbolo nome leitura
: negação não
^ conjunção e
_ disjunção ou
�! condicional se...então...
 ! bicondicional ...se e somente se ...
De…nição 2 Uma expressão lógica proposicional clássica é dita ser uma fór-
mula1 se satisfazer ao menos uma das seguintes condições:
a) Cada variável proposicional é uma fórmula;
b) Se X é uma fórmula, então (:X) é uma fórmula;
c) Se X e Y são fórmulas, então (X ^ Y ) ; (X _ Y ) ; (X �! Y ) e (X ! Y )
são fórmulas;
d) Só é fórmula o que advém das condições acima.
As seguintes expressões são exemplos de fórmulas da linguagem LP :
� (p1 �! p2)
� (: (: (:p1)))
� (((p2 ^ p3) �! p5) _ (p1 �! (:p2)))
� p5:
1Uma fórmula é uma expressão bem formada.
1
0.0.2 Parênteses
De…nição 3 Convenções para eliminação (e restauração) de parênteses.
i) parênteses externos podem ser omitidos;
ii) para partes de fórmulas com o mesmo conectivo adota-se o príncipio de
associação à esquerda;
iii) a seguinte ordem hierárquica de colocação de conectivos é adotada: ":"; "^
"; " _ "; " �! "; " ! ":
As convenções de eliminação de parênteses são as mesmas con-
venções utilizadas para restauração de parênteses.
a) A fórmula ((p1 ^ p2) �! p3) torna-se p1 ^ p2 �! p3 após aplicação das
convenções;
b) A fórmula ((p1 �! p2) ^ p3) torna-se (p1 �! p2) ^ p3 após aplicação das
convenções quanto a eliminação dos parênteses;
c) :::p1advém de (: (: (:p1))) ;
d) p1 �! p7 �! p9 ^p8 advém de ((p1 �! p7) �! (p9 ^ p8)) após aplicação
das convenções quanto a eliminação dos parênteses.
0.1 Semântica
0.1.1 Valorações Proposicionais
De…nição 4 Seja F o conjunto de todas as fórmulas da linguagem L: Uma val-
oração proposicional v é uma aplicação de F em fV; Fg que satisfaz as seguintes
condições para quaisquer fórmulas X;Y de F :
i) v (:X) =
�
V , se v (X) = F e
F; caso contrário.
ii) v (X _ Y ) =
�
F; se v (X) = v (Y ) = F e
V; caso contrário.
iii) v (X ^ Y ) =
�
V; se v (X) = v (Y ) = V e
F; caso contrário.
iv) v (X �! Y ) =
�
F; se v (X) = V e v (Y ) = F e
V; caso contrário.
v) v (X ! Y ) =
�
V; se v (X) = v (Y ) e
F; caso contrário.
2
0.1.2 Tabela Verdade
Uma tabela verdade é um procedimento efetivo (mecânico) utilizado para anal-
isar os valores verdade de uma fórmula da linguagem LP :
Sejam X e Y fórmulas quaisquer de F:
X (:X)
V F
F V
X Y (X ^ Y ) (X _ Y ) (X �! Y ) (X ! Y )
V V V V V V
V F F V F F
F V F V V F
F F F F V V
De um modo geral, para uma fórmula com n variáveis proposicionais difer-
entes, a tabela terá 2n linhas.
Exemplo 5
p0 p1 p2 (p0 �! p1) (p0 _ p2) (: (p0 _ p2)) ((p0 �! p1) ^ (: (p0 _ p2)))
V V V V V F F
V V F V V F F
V F V F V F F
V F F F V F F
F V V V V F F
F V F V F V V
F F V V V F F
F F F V F V V
Tabela verdade da fórmula ((p0 �! p1) ^ (: (p0 _ p2))) :
0.1.3 Propriedades semânticas
De…nição 6 Uma fórmula X é dita ser uma tautologia se v (X) = V para toda
a valoração proposicional v:
Uma fórmula é dita ser uma contradição se e somente se v(X) = F para
toda valoração proposicional.
As fórmulas que não são contradições nem tautologias, são chamadas de
contigentes.
Símbolo Nome Leitura De…nição
> verum constante de verdade > =def (X _ :X)
? falsum constante de falsidade ? =def (X ^ :X)
De…nição 7 Um conjunto de fórmulas � é "satisfazível"se existir uma valo-
ração proposicional v tal que v(X) = V para todo X 2 �:
3
Seja � = fA1; A2; :::; Ang um conjunto de fórmulas da lógica. Seja a tabela
verdade de cada fórmula de � exposta abaixo.
Li !
A1 A2 A3 . . . An
...
...
...
...
...
V V V . . . V
...
...
...
...
...
Se existir ao menos uma linha Li na tabela verdade acima, de tal forma que
nessa linha Li se tem que v(X) = V para todo X 2 �; então � é satisfazível.
Neste texto a palavramodelo será utilizada, quando não houver dúvidas no
contexto, como sinônimo de satisfazível. O conjunto � tem modelo se e somente
se existe uma valoração proposicional v; tal que v(Z) = V para toda fórmula
Z 2 �:
De…nição 8 Seja � um conjunto de fórmulas. Diz-se que a fórmula X é con-
sqüência lógica do conjunto de fórmulas � (em símbolos, � j= X) se para toda
valoração proposicional v, se v(C) = V para todo C 2 � então v (X) = V:
De…nição 9 Diz-se que as fórmulas X e Y são logicamente eqüivalentes (em
símbolos, X � Y ) se para toda valoração proposicional v; v (X) = v (Y ) :
A fórmula : (p0 _ p1) é logicamente eqüivalente a fórmula (:p0 ^ :p1) ; pois
ambas tem a mesma atribuição de valores verdade.
p0 p1 (p0 _ p1) : (p0 _ p1) :p0 :p1 :p0 ^ :p1
V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V
0.2 Forma Normal Conjuntiva
De…nição 10 Uma fórmula na forma normal conjuntiva é uma conjunção (X1 ^X2 ^ ::: ^Xn)
onde para cada X1; com 1 � i � n :
1. ou Xi é uma variável proposicional,
2. ou Xi é uma disjunção (Y1 _ Y2 _ ::: _ Ym) onde:
i) Para cada Yj (1 � j � m) ; ou Yj é uma variável proposicional ou é uma
negação de uma variável proposicional, exclusivamente.
4
0.2.1 Algoritmo para obter fórmuas na FNC
Para transformar uma fórmula X numa fórmula normal conjuntiva, procede-se
segundo os seguintes passos:
1. Os conectivos "�!"e " !"que por ventura existam na fórmulaX, devem
ser substituídos por :Y _Z e por (:Y _ Z)^: (Y _ Z) respectivamente.
2. Utilizar as leis de De Morgan.
3. Eliminar multiplas negações.
2. Caso necessário, aplicar a lei distributiva: Y _(Z ^W ) ou do tipo (Z ^W )_
Y; deve-se substituir por (Y _ Z) ^ (Y _W )
0.3 Forma Normal Disjuntiva
De…nição 11 Uma fórmula na forma normal disjuntiva é uma disjunção (X1 _X2 _ ::: _Xn)
onde para cada Xi;com 1 � i � n :
1. ou Xi é uma variável proposicional,
2. ou Xi é uma conjunção (Y1 ^ Y2 ^ ::: ^ Ym) onde:
i) Para cada Yj (1 � j � m) ; ou Yj é uma variável proposicional ou é uma
negação de uma variável proposicional, exclusivamente.
0.3.1 Algoritmo para obter fórmulas na FND
A transformação de uma fórmula X qualquer para uma fórmula logicamente
eqüivalente na FND é semelhante ao algoritmo elaborado para FNC a menos
do último passo. O algoritmo é:
1. Os conectivos "�!"e " !"que por ventura existam na fórmulaX, devem
ser substituídos por :Y _Z e por (:Y _ Z)^: (Y _ Z) respectivamente.
2. Utilizar as leis de De Morgan.
3. Eliminar multiplas negações.
2. Caso necessário, aplicar a lei distributiva: Y ^ (Z _W ) ou (Z _W ) ^ Y;
deve-se substituir por (Y ^ Z) _ (Y ^W ) :
1 Tableaux Analítico
Desenvolvimentos sobre o método tableaux podem ser encontrados em Beth
(1959) e Hintikka (1955) ou Smullyan (1968).
5
1.1 Sistema formal baseado em Tableaux Analíticos
Os tableaux são procedimentos de demonstração (procedimentos formais) elab-
orados em forma de árvores binárias. Se se quer mostrar que X é um teorema
através de tableaux, as únicas fórmulas envolvidas na demonstração (em forma
de árvores) são as fórmulas que se constituem como partes de X. Desse modo,
(para a lógica proposicional), se uma fórmula X não for um teorema, o tableau
para X mostra todas as possibilidades que tornam X falso.
Uma árvore binária contém nós, em cada nó ocorre uma fórmula de LP . A
construção de um tableau inicia-se pela origem da árvore a qual é um nó único.
Em um tableau para a fórmula X, tem-se que no nó de origem ocorre a
fórmula (:X). Essa é a primeira regra de construção de tableaux.
Sempre inicia-se por (:X) um tableau para a fórmula X. A partir do nó
de origem estabelece-se regras que possibilitem a extensão da árvore, caracter-
izando seus ramos e suas bifurcações. Após todas as possíveis aplicações de
regras de extensão da árvore tem-se um tableaucompleto, ou seja, uma árvore
que se estendeu o máximo possível através das aplicações de regras para todas
as fórmulas que ocorrem na árvore.
A partir dessa “árvore completa”, onde nos nós ocorrem fórmulas, é possível
analisar e certi…car-se se a fórmula X é um teorema ou se X não é um teorema
(numa árvore para a fórmula X).
Em cada nó
ocorre uma
fórmula de Lp
(ØX)
origem
um ramo
sucessor da
esquerda
sucessor da
direita
ponto
simples
ponto de
junção
ponto
final
1.1.1 Fórmulas do tipo � e fórmulas do tipo �
As fórmulas de � são fórmulas do tipo (�1^�2) e as fórmulas de � são fórmulas
do tipo (�1 _ �2).
6
� - fórmulas �1 �2
(X _ Y ) X Y
(X �! Y ) :X Y
: (X ^ Y ) :X :Y
� - fórmulas �1 �2
: (X _ Y ) :X :Y
: (X �! Y ) X :Y
(X ^ Y ) X Y
::X X :?
1.1.2 Extensões de ramos
Extensões a partir de um nó p, para fórmulas do tipo-� e fórmulas do tipo-�;
respectivamente.
extensões de p
produzindo bifurcaçãoextensões de p no
mesmo ramo
p
p
As regras de extensões de ramos são de dois tipos:
� Regra �. Regra de extensão no mesmo ramo.
� Regra �. Regra de extensão em ramos separados (bifurcação).
7
De…nição 12 Uma fórmula X é um teorema (ou um teorema-tableau) se existir
um tableau com contradições para X. Ou seja, um tableau que comece com
\(1) (:X) � e de tal forma que cada ramo seja um ramo com contradições.
Indica-se `t X para X é um teorema–tableaux.
Seja � um conjunto de fórmulas e X uma fórmula qualquer. Diz-se que X é
dedutível-tableaux a partir de � (em símbolos, � `t X) se existir um tableau com
contradições que comece por \(1) (:X) � e de tal forma que qualquer fórmula de
� puder ser adicionada em qualquer nó do tableau que começa por \(1) (:X) �:
Se � `t X diz-se que o ocorreu uma dedução-tableau de X a partir de �. Se
� = ? diz-se que X é um teorema-tableau.
Se � = fX1; X2; :::; Xng então � ` X se o tableau começado por
e estendido através das regras � e �, de modo que nenhuma fórmula …que
sem sofrer aplicação de alguma regra de extensão de ramos, for um tableau cujos
ramos (todos) são ramos com contradições.
Exemplo 13 Seja � = f(p1 �! p2);:p2g e X = :p1:
8
O tableau acima é uma dedução-tableau de X a partir de �.
2 Cálculo de Quanti…cadores
Seja 8 o símbolo que representa "para todo”. Este é chamado de quanti…cador
universal. Seja 9 o símbolo que representa a palavra “existe”, chamado de
quanti…cador existencial.
Seja P um símbolo de predicado. P (x) representa o predicado P com sujeito
x. Por exemplo, Se o predicado P representar “é um livro azul”, então P (x)
representa “x é um livro azul”.
Sejam os símbolos a1, a2, a3, ...,an representando constantes individuais. Se-
jam x; y e z representando variáveis sobre sujeitos. Assim (8x)P (x) representa
um quanti…cador universal e (9x)P (x) representa um quanti…cador existencial.
P (a1); P (a2), ..., representam proposições do cálculo proposicional, as quais são
verdadeiras ou falsas.
O comportamento de um quanti…cador universal (8) pode ser entendido,
de modo intuitivo, como uma conjunção iterada
P (a1) ^ P (a2) ^ P (a3) ^ ::: ^ P (an) :
O quanti…cador existencial (9x)P (x) pode ser entendido, intuitivamente,
como uma disjunção iterada.
P (a1) _ P (a2) _ P (a3) _ ::: _ P (an) :
Exemplo 14 Algumas equivalências entre quanti…cadores.
: (8x)P (x) � : (P (a1) ^ ::: ^ P (an)) � (:P (a1) _ ::: _ :P (an)) � (9x):P (x)
: (9x)P (x) � : (P (a1) _ ::: _ P (an)) � (:P (a1) ^ ::: ^ :P (an)) � (8x):P (x)
(8x)P (x) � (P (a1) ^ ::: ^ P (an)) � : (:P (a1) _ ::: _ :P (an)) � : (9x):P (x)
(9x)P (x) � (P (a1) _ ::: _ P (an)) � : (:P (a1) ^ ::: ^ :P (an)) � : (8x):P (x)
Alguns exemplos de predicados:
� I(x; y): “x é igual a y”
9
� F (x; y): “x é pai de y”
� O(x): “x é um número ímpar”
� H(x; y; z): “x é menor que y mais z”
� C(x; y): “x é casado com y”
Todo A é B (8x) (A (x) �! B (x)) A…rmativa Universal
Todo A não é B (8x) (A (x) �! :B (x)) Negativa Universal
Algum A é B (9x) (A (x) ^B (x)) A…rmativa Particular
Algum A não é B (9x) (A (x) ^ :B (x)) Negativa Particular
Exemplo 15
Nenhum jóquei é alto.
J(x) : "x é um jóquei"
H(x) : "x é alto"
(8x) (J (x) �! :H (x))
Exemplo 16
Todas as baleias são mamíferos.
B(x) : "x é uma baleia"
M(x) : "x é um mamífero"
(8x) (B (x) �!M (x))
Exemplo 17
Nem todos cachorros são bravos.
C(x) : "x é um cachorro"
T (x) : "x é bravo"
(9x) (C (x) ^ :B (x))
Exemplo 18
Todo solteiro é triste.
H(x) : "x é um homemi"
C(x; y) : "x é casado com y"
(8x) ((H (x) ^ (8y) :C (x; y)) �! T (x))
Exemplo 19
O único número primo par é 2.
P (x) : "x é um inteiro par"
D(x) : "x é um inteiro primo"
I(x; y) : "x é igual a y"
a : 2.
(8x) (P (x) ^D (x)) �! I (x; a)
2.1 Semântica de LQ
Sejam as seguintes fórmulas:
a) P 21 (x1; x2) ;
b) (8x1) (9x2)P 21 (x1; x2) ;
c) (9x2) (8x1)P 21 (x1; x2) :
10
2.1.1 Uma interpretação I1
� A letra de predicado P 21 representa a relação �;
� P 21 (x1; x2) representa "x1 é menor ou igual que x2"
� conjunto de constantes individuais (domínio) é N:
A leitura das três fórmulas acima, sob essa interpretação, é:
a) x1 � x2; P 21 (x1; x2)
b) Para todo x1; existe x2 tal que x1 � x2; (8x1) (9x2)P 21 (x1; x2)
c) Existe x2 tal que para todo x1; se tem que x1 � x2: (9x2) (8x1)P 21 (x1; x2)
Os valores verdade das fórmulas sob a interpretação I1 são:
Para a): Essa fórmula é verdadeira para todos os pares (a; b) números naturais
tais que a � b:Por exemplo (3; 4); (1; 1); :::. Note que, a fórmula P 21 (5; 6)
é verdadeira e a fórmula P 21 (32; 4) é falsa Como não se sabe a princípio
quem são x1 e x2; a fórmula é verdadeira para alguns elementos do domínio
e falsa para outros;
Para b): Essa fórmula é verdadeira. Note que não tem variáveis livres (todas
as variáveis estão sob o escôpo de algum quanti…cador). De fato, esta
representa a seguinte frase: para cada número natural existe um número
maior ou igual.
Para o primeiro número natural existe um número natural que é maior, para
o segundo número natural existe um número natural que é maior, para o
terceiro existe um que é maior, ... . Para o número 1 existe o número 2
que é maior, o número 3 que é maior, o número 4 que é maior, ....
Para c): Essa fórmula é falsa em N; pois a…rma que existe um número natural
maior ou igual a todos os outros. Ou seja, para x1 = 0; x1 = 1; x1 = 2; :::
existe um x2 tal que x1 � x2: A fórmula caracteriza que existe um número
natural que é maior ou igual que todos os outros, ou seja, que é maior ou
igual ao primeiro, que é maior ou igual ao segundo, que é maior ou igual
ao terceiro, etc.
2.1.2 Uma interpretação I2
� A letra de predicado P 21 representa a relação "... é …lho de ..."
� P 21 (x1; x2) representa "x1 é pai de x2"
� conjunto de constantes individuais (domínio) é o conjunto das pessoas do
mundo.
A leitura das três fórmulas acima, sob a interpretação, é:
11
a) x1 é pai de x2; P 21 (x1; x2)
b) Para todo x1; existe x2 tal que x1 é …lho de x2; (8x1) (9x2)P 21 (x1; x2)
c) Existe x2 tal que para todo x1; se tem que x1 é …lho de x2: (9x2) (8x1)P 21 (x1; x2)
Os valores verdade das fórmulas sob a interpretação I2 são:
Para a): Representa que x1 é pai de x2. Esta é verdadeira por todo par (a; b)
de pessoas tais que a seja …lho de b.
Para b): A fórmula pode ser representada pela frase: Todos tem um pai. Esta
frase é verdadeira.
Para c): A frase que representa a fórmula é: Todos tem um único pai.
Nota-se que o valor verdade de uma fórmula em uma linguagem de primeira
ordem depende da interpretação envolvida.
2.1.3 Interpretação de LQ
De…nição 20 Seja LQ uma linguagem. Uma interpretação I para LQ consiste
de:
1) Um conjunto não vazio D, chamado de domínio de I;
2) Uma função V que associa a cada letra de predicado Pnk uma relação n��aria
V (Pnk ) de elementos de D: Denomina-se essa função V de valoração de
primeira ordemO domínio de uma interpretação consiste do conjunto de constantes individ-
uais. A partir dos predicados da linguagem associa-se a cada letra n� �aria de
predicado uma relação n� �aria constituída de elementos do domínio.
Por exemplo, seja I4 a seguinte interpretação:
� Domínio: N ;
� P 21 (x1; x2) : "x1 � x2";
� P 11 (x1) : "x1 é par"
Tem-se duas letras de predicados, cada uma determina uma relação. A letra
de predicado P 21 determina uma relação binária, ou seja, determina um conjunto
de elementos
�
(a; b) 2 N2 j a � b	 = f(0; 0) ; (0; 1) ; (1; 1) ; (1; 2) ; :::g : A função
V associa a cada letra de predicado, neste caso à letra P 21 ; a relação binária
V
�
P 21
�
= f(0; 0) ; (0; 1) ; (1; 1) ; (1; 2) ; :::g : Já, a letra de predicado P 11 determina
uma relação unária (1��aria), a qual é dada pelo conjunto f0; 2; 4; 6; 8; :::g cujos
elementos satisfazem a relação 1 � �aria determinada por P 11 : A valoração de
primeira ordem V (função V ) associa a letra de predicado P 11 a relação 1�ária
V
�
P 11
�
= f0; 2; 4; 6; 8; 10; :::g :
12
� (8x1)
�
P 11 (x1) �! P 12 (x1)
� �! (P 11 (x1) �! (8x1)P 12 (x1))
De…nição 21 Uma fórmula A de uma linguagem LQ é LQ-satisfatível se A é
verdadeira em pelo menos uma interpretação.
De…nição 22 Seja I uma interpretação de uma linguagem LQ, e A uma fór-
mula fechada de LQ. Então, A é uma fórmula válida (em símbolos, j= A) se
para toda interpretação I, j=I A.
De…nição 23 Seja � um conjunto de fórmulas em uma linguagem LQ: Um
modelo para � é uma interpretação na qual todas as fórmulas de � sejam ver-
dadeiras. Um modelo para uma fórmula A é uma interpretação onde A é ver-
dadeira.
De…nição 24 Seja � um conjunto de fórmulas e A uma fórmula em uma lin-
guagem uma LQ: A fórmula A é conseqüência lógica do conjunto de fórmulas �
(em símbolos, � j= A) se todo o modelo de � é modelo de A:
1) A fórmula (8x)P (x) �! P (y) é uma fórmula válida.
2) A fórmula (8x) (P (x) �! P (y)) não é uma fórmula válida.
3) A fórmula (8x) (P (x) �! Q (x)) �! (P (x) �! (8x)Q (x)) é uma fórmula
válida.
4) A fórmula (8x) (9y) (P (x) �! P (y)) é uma fórmula válida.
5) A fórmula (9x) (9y) (P (x) �! P (y)) não é uma fórmula válida.
Justi…cativa: Seja uma interpretação I onde o domínio é o conjunto dos
números naturais. P (x) representa “x é um número primo”. A leitura
da fórmula acima é: “Existem números naturais x e y, tais que se x é
primo então y também é primo. Logo, existe um número natural igual a
3 e existe um número natural igual a 8, mas não se tem que se 3 é um
número primo então 8 também é um número primo, ou seja a fórmula
P (3) �! P (8) é falsa. Desse modo, I é uma interpretação onde a fórmula
(9x) (9y) (P (x) �! P (y)) é falsa, portanto não é válida.
3 Tableaux analíticos para LQ
3.1 Regras Tableaux para LQ.
Regra 
(k)
onde k é qualquer constante
Regra �
13
�
�(k)
onde k é uma nova constante
A regra 
 é de simples utilização. Se uma fórmula do tipo 
 ocorre num nó
de um tableau, então no nó seguinte (ou nas terminações a partir do nó corrente)
é possível adicionar 
(k) para qualquer que seja a constante individual k.
Regra 
 :
(8x)A
A(x/k )
: (9x)A
:A(x/k )
para qualquer constante individual k.
Ao se utilizar a regra � deve-se ter algum cuidado. Se alguma fórmula do
tipo � ocorre num nó de um tableau, então pode-se estendê-la adicionando � (k),
desde que a constante individual k não tenha aparecido em fórmulas anteriores
no tableau.
Regra � :
(9x)A
A(x/k )
: (8x)A
:A(x/k )
para alguma constante individual k que não tenha ocorrido em fórmulas
anteriores no tableau.
Exemplo de uma prova tableau em LQ para a fórmula (8x)P (x) �! (9x)P (x).
(1) : ((8x)P (x) �! (9x)P (x))
(2) (8x)P (x)
(3) : (9x)P (x)
(4) P (k1)
(5) :P (k1)
�
O tableau acima é completo e está fechado pois ocorreu uma contradição,
P (k1) e :P (k1). A fórmula da linha (4) adveio da fórmula da linha (2) pela
aplicação da regra 
. A fórmula da linha (5) adveio da fórmula da linha (3) pela
aplicação da regra 
. Como a regra 
 não tem restrições foi possível acrescentar
a mesma constante individual k1 na duas aplicações da regra 
.
O seguinte é um exemplo de um tableau completo e aberto para a fórmula
(8x) (9y)P (x; y) �! (9x) (8y)P (x; y)
(1) : ((8x) (9y)P (x; y) �! (9x) (8y)P (x; y))
(2) (8x) (9y)P (x; y) regra � aplicada em (1)
(3) : (9x) (8y)P (x; y) regra � aplicada em (1)
(4) (9y)P (k1; y) regra 
 aplicada em (2)
(5) : (8y)P (k1; y) regra 
 aplicada em (3)
(6) P (k1; k2) regra � aplicada em (4)
14
(7) :P (k1; k3) regra � aplicada em (5)
O tableau não fechou pois não ocorreu contradição. Nota-se que nas linhas
(6) e (7) a regra � foi utilizada e foi aplicado a restrição imposta nessa
regra, qual seja, que a constante a ser introduzida não apareça em fórmulas
anteriores no tableau.
Exemplo de tableau para a fórmula (8x)P (x)! (9x)P (x)
15

Outros materiais