Buscar

matemc3a1tica matemc3a1tica discreta lc3b3gica de predicados universidade de caxias do sul

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 12 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 12 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 12 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

Lógica de Predicados - Profa. Márcia Rodrigues Notare 1
UNIVERSIDADE DE CAXIAS DO SUL – UCS
CENTRO DE CIÊNCIAS EXATAS E TECNOLOGIA – CCET
DEPARTAMENTO DE INFORMÁTICA – DEIN
PROFA. MÁRCIA RODRIGUES NOTARE
/yJL
�������
3UHGLFDGRV
4
�
XDQ
�	��
W
�
L
 I
�
L
 FDGR
� �����
U� H
�������
9
�
D
�
U� L
 i
ff
Y
fi
H
�
L
 V
�
Todos os homens são mortais.
Sócrates é um homem.
 ∴ Sócrates é mortal.
Como podemos avaliar a validade do argumento acima? Observe que ele não utilizada nenhum
dos cinco operadores lógicos e, portanto, não conseguimos avaliar sua validade. Se quiséssemos
formalizá-lo, obteríamos: P, Q fl fl R
A Lógica Proposicional, estudada até o momento, não é capaz de representar o argumento
acima! Assim, para representar essa forma de argumento, utilizaremos a Lógica de Predicados.
Considere a primeira premissa: Todos os homens são mortais.
Podemos reescrevê-la da seguinte forma, com a utilização de um condicional: Para tudo, se é
homem, então é mortal.
Numa primeira tentativa de formalização, teremos: Para tudo (homem →ffi mortal).
Podemos inserir uma variável para simplificar a formalização e o símbolo ∀� (lê-se "para todo"),
denominado quantificador universal para melhora-la: ∀ x (x é homem →ffi x é mortal).
As frases "é homem" e "é mortal" são denominadas, na lógica, de predicados. É usual, na
lógica, escrevermos o predicado e depois o sujeito (variável), como mostra a seguir:
Hx para representar "é homem"
Mx para representar "é mortal"
Logo, a formalização da premissa "Todos os homens são mortais" fica:
∀� x (Hx →! Mx)
A formalização de todo o argumento fica como segue:
∀� x (Hx →! Mx), Hs fl
fl
 Ms
onde s representa o nome Sócrates.
Vejamos algumas variações de frases envolvendo predicados:
Lógica de Predicados - Profa. Márcia Rodrigues Notare 2
Enunciado Formalização
Tudo é mortal (Para todo x, x é mortal) ∀" xMx
Tudo é imortal (Para todo x, x não é mortal) ∀" x¬# Mx
Nem tudo é mortal (que não é o mesmo que dizer Nada é mortal) ¬# ∀" xMx
Considere a sentença: "Nenhum homem é mortal". É o mesmo que dizer "Para todo x, se x é um
homem, então x não é mortal". Formalizando, temos:
∀" x (Hx →$ ¬# Mx)
Porém, além do quantificador universal, precisamos também de um outro quantificador (o
quantificador existencial ∃% - lê-se "para pelo menos um" ou "existe um...tal que") que represente
frases do tipo "Alguns pais são irresponsáveis". Tal frase pode ser reescrita como "Para pelo
menos um x, x é um pai e x é um irresponsável". Formalizando, teremos:
∃% x (Px ∧& Ix)
Vejamos mais algumas frases:
Enunciado Formalização
Existe um x tal que x é pai e x não é irresponsável ∃% x (Px ∧& ¬# Ix)
Não é verdade que alguns pais são irresponsáveis ¬# ∃% x (Px ∧& Ix)
Existe uma menina que é bonita (existe um x tal que x é
menina e x é bonita)
∃% x (Mx ∧& Bx)
Para todo x, se x é mortal e x é um homem, então x está
situado no espaço e no tempo
∀" x ((Mx ∧& Hx) →$ (Ex ∧& Tx))
Alguns enunciados não usam quantificadores. São enunciados do tipo sujeito-predicado
(formalizados na ordem predicado-sujeito) ou enunciados que utilizam verbos transitivos, como
amar, bater, odiar, que exigem sujeito e objeto e são formalizados na ordem predicado-sujeito-
objeto. Os nomes (sujeito e objeto) são representados por letras minúsculas, enquanto que os
predicados são representados por letras maiúsculas. Veja alguns exemplos:
Enunciado Formalização
Maria é inteligente Im
Maria ama João Amj
João ama Maria Ajm
Maria ama a si mesma Amm
Maria deu um livro para João Dmlj
Alguém ama João ∃% xAxj
Alguém ama a si mesmo ∃% xAxx
João ama ninguém ∀" x¬# Ajx ou ¬# ∃% xAjx
Alguém ama alguém ∃% x∃% yAxy
Existe um x tal que para todo y, x ama y ∃% x∀" yAxy
Para todo x, existe um y tal que x ama y ∀" x∃% yAxy
Todos amam todos ∀" x∀" yAxy
Lógica de Predicados - Profa. Márcia Rodrigues Notare 3
6LQW ')(+*-,.' U '/'10.2�3 L 4�'/56* 3UHGLFDGRV
O vocabulário da lógica de predicados é formado por símbolos lógicos (cuja interpretação é fixa
em qualquer contexto) e símbolos não-lógicos (cuja interpretação varia de problema para
problema).
Símbolos Lógicos:
Operadores lógicos: ¬ , ∧ , ∨ , → , ↔
Quantificadores: ∀ , ∃
Parênteses: ( )
Símbolos Não-lógicos:
Letras nominais: letras minúsculas de 'a' a 't'
Variáveis: letras minúsculas de 'u' a 'z'
Letras predicativas: letras maiúsculas
Definimos uma fórmula como sendo uma seqüência qualquer, finita, de elementos do
vocabulário. Uma fórmula atômica é uma letra predicativa seguida por zero ou mais letras
nominais.
Uma fórmula bem formada (wff) no cálculo de predicados é definida pelas seguintes regras de
formação:
1. Toda fórmula atômica é uma wff.
2. Se φ é uma wff, então ¬φ também é uma wff.
3. Se φ e ψ são wffs, então (φ ∧ ψ), (φ ∨ ψ), (φ → ψ) e (φ ↔ ψ) também são wffs.
4. Se φ é uma wff contendo uma letra nominal α, então qualquer fórmula da forma ∀β φβ/α ou
∃β φβ/α é uma wff, onde φβ/α é o resultado de se substituir uma ou mais ocorrências de α
em φ por uma variável β que não ocorre em φ.
A regra 4 tem o objetivo de gerar fórmulas quantificadas a partir de uma fórmula dada, não
quantificada. Para exemplificar, observe a seguinte fórmula (não quantificada):
(Ma ∧ Hab)
Esta fórmula contém duas letra sentenciais ‘a’ e ‘b’. Ambas são o que a regra 4 chama de α.
Consideremos a letra ‘a’. A regra permite substitui-la por uma variável β, que não ocorre na
fórmula. Seja ‘x’ essa variável. Então, teremos as seguintes fórmulas resultantes da substituição
de uma ou mais ocorrências de α (que é ‘a’) por β (que é ‘x’):
∀x (Mx ∧ Hab)
∀x (Ma ∧ Hxb)
∀x (Mx ∧ Hxb)
∃x (Mx ∧ Hab)
∃x (Ma ∧ Hxb)
∃x (Mx ∧ Hxb)
Observe que é necessário quantificar a variável inserida (prefixando-a com o quantificador
universal ou com o quantificador existencial), ou não teremos uma wff. Qualquer fórmula que
contém uma variável sem um quantificador correspondente não é uma wff; analogamente,
Lógica de Predicados - Profa. Márcia Rodrigues Notare 4
qualquer fórmula que contém um quantificador seguido de uma variável, sem a ocorrência
adicional dessa variável na fórmula, também não é uma wff.
([HUFtFLRV
1. As seguintes fórmulas não são wffs. Justifique cada uma delas:
a) ∀xLzx
b) (Fa)
c) (∃xFx ∧ Gx)
d) ∀x(Fx)
e) (∀xFx)
f) ∃x∀yFx
g) ∃x∃x(Fx ∧ ¬Gx)
h) ∃xFx ∧ ∃xGx
2. Algumas das expressões a seguir são wffs, outras não. Para as que são wff, diga como foram
construídas a partir das regras de formação e, para as demais, justifique porque não são.
a) ∀xLxx
b) ∃x∀xLxx
c) ∃aFa
d) ∃xFa
e) ∀x∀y(Lxy ↔ Lyx)
f) (Laa)
g) ¬∀x¬Fx
h) (∃xFx → ∃xFx)
i) (P → ∃xFx)
j) Lab → Lba
3. Formalize as seguintes sentenças, usando a interpretação indicada. A seguir, verifique sua
formalização através das regras de formação.
Nomes Predicados unários Predicados binários
a – Aristóteles F – é um feminista R - ridicularizou
n – Nietzsche G – é grego E – é mais esperto que
p - Platão P – é um filósofo W - escreveu
a) Aristóteles é grego.
b) Platão é um grego feminista.
c) Se Platão é um feminista, então alguém é um grego feminista.
d) Nenhum grego é feminista.
e) Todos os feministas são filósofos.
f) Todos os gregos feministas são filósofos.
g) Aristóteles escreveu algo.
h) Aristóteles escreveu tudo.
i) Aristóteles escreveu nada.
j) Nietzsche ridicularizou todos que são feministas.
k) Nietzsche ridicularizou todos que eram mais espertos que ele.
l) Alguns filósofos ridicularizam a si mesmos.
m) Alguns filósofos ridicularizam tudo.
Lógica de Predicados - Profa. Márcia Rodrigues Notare 5
,QIHUrQFL 7-8.7 U 7/7 /yJL 9�7/:6; 3UHGLFDGRV
O cálculo de predicados usa as mesmas dez regras do cálculo proposicional e as mesmas regras
derivadas. Entretanto, quatro novas regras serão introduzidas: introdução e eliminação para cadaum dos quantificadores.
Vejamos, antes de introduzir as novas regras, um exemplo de demonstração que utiliza apenas
as dez regras já conhecidas.
Prove: ¬< Fa ∨= ∃> xFx, ∃> xFx →? P @ Fa →? P
1. ¬Fa ∨ ∃xFx P
2. ∃xFx → P P
3. Fa H (PC)
4. ¬¬Fa 3, DN
5. ∃xFx 1, 4 SD
6. P 2, 5 MP
7. Fa → P 3-4 PC
Veja como as regras já conhecidas são tratadas da mesma forma que no cálculo proposicional. A
seguir, são introduzidas as novas regras.
Eliminação universal (EU): de uma wff quantificada universalmente, ∀βφ, podemos inferir
uma wff, da forma φα/β, a qual resulta da substituição de cada
ocorrência da variável β em φ por uma letra nominal α.
Esta regra é usada para provar a validade de formas de argumento como:
Todos os homens são mortais.
Sócrates é um homem.
 ∴ Sócrates é mortal.
que pode ser formalizado por:
∀A x (Hx →? Mx), Hs B
B
 Ms
Vamos provar a validade dessa forma:
1. ∀x (Hx → Mx) P
2. Hs P
3. Hs → Ms 1, EU
4. Ms 2, 3 MP
Exemplos:
Prove: ∀A x (Fx →? Gx), ∀A xFx @DC+E
1. ∀x (Fx → Gx) P
2. ∀xFx P
3. Fa → Ga 1, EU
4. Fa 2, EU
5. Ga 3, 4 MP
Lógica de Predicados - Profa. Márcia Rodrigues Notare 6
Prove: ¬F Fa G ¬F ∀H xFx
1. ¬Fa P
2. ∀xFx H (RAA)
3. Fa 2, EU
4. Fa ∧ ¬Fa 1, 3 ∧I
5. ¬∀xFx 2-4 RAA
Prove: ∀H x∀H yFxy G Faa
1. ∀x∀yFxy P
2. ∀yFay 1, EU
3. Faa 2, EU
Introdução universal (IU): para uma wff φ contendo uma letra nominal α que não ocorre em
qualquer uma das premissas ou em qualquer hipótese vigente na
linha em que φ ocorre, podemos inferir uma wff da forma ∀βφβ/α,
onde φβ/α é o resultado de se substituir todas as ocorrências de α
em φ por uma variável β que não ocorra em φ.
Essa regra é utilizada para provar formas de argumento como:
Todos os peixes são animais.
Todos os animais são vistosos.
 ∴ Todos os peixes são vistosos.
que pode ser formalizada por:
∀H x (Px →I Ax), ∀H x (Ax →I Vx) G ∀H x (Px →I Vx)
A prova da validade dessa forma é dada a seguir:
1. ∀x (Px → Ax) P
2. ∀x (Ax → Vx) P
3. Pa → Aa 1, EU
4. Aa → Va 2, EU
5. Pa → Va 3, 4 SH
6. ∀x (Px → Vx) 5, IU
Atente para as seguintes restrições, que são cruciais para que a regra seja utilizada corretamente:
a) A letra nominal α não pode ocorrer em qualquer premissa, ou seja, da suposição de que
Sócrates é peixe não podemos inferir que qualquer coisa é peixe.
b) A letra nominal α não deve ocorrer em qualquer hipótese vigente numa linha em que φ
ocorre.
c) φβ/α é o resultado de substituir todas as ocorrências de α em φ por uma variável β.
Veja mais exemplos:
Prove: ∀H x (Fx ∧J Gx) G ∀H xFx ∧J ∀H xGx
1. ∀x (Fx ∧ Gx) P
2. Fa ∧ Ga 1, EU
Lógica de Predicados - Profa. Márcia Rodrigues Notare 7
3. Fa 2, ∧E
4. Ga 2, ∧E
5. ∀xFx 3, IU
6. ∀xGx 4, IU
7. ∀xFx ∧ ∀xGx 5, 6 ∧I
Prove: ∀K x(Fx →L (Gx ∨M Hx)), ∀K x¬N Gx O ∀K xFx →L ∀K xHx
1. ∀x(Fx → (Gx ∨ Hx)) P
2. ∀x¬Gx P
3. Fa → (Ga ∨ Ha) 1, EU
4. ¬Ga 2, EU
5. ∀xFx H (PC)
6. Fa 5, EU
7. Ga ∨ Ha 3, 6 MP
8. Ha 4, 7 SD
9. ∀xHx 8, IU
10. ∀xFx → ∀xHx 5-9 PC
Prove: ∀K x(Fx →L (Gx ∨M Hx)), ∀K x¬N Gx O ∀K x(Fx →L Hx)
1. ∀x(Fx → (Gx ∨ Hx)) P
2. ∀x¬Gx P
3. Fa → (Ga ∨ Ha) 1, EU
4. ¬Ga 2, EU
5. Fa H (PC)
6. Ga ∨ Ha 3, 5 MP
7. Ha 4, 6 SD
8. Fa → Ha 5-7 PC
9. ∀x(Fx → Hx) 8, IU
Prove: ∀K xFax, ∀K x∀K y(Fxy →L Gyx) O ∀K xGxa
1. ∀xFax P
2. ∀x∀y(Fxy → Gyx) P
3. Fab 1, EU
4. ∀y(Fay → Gya) 2, EU
5. Fab → Gba 4, EU
6. Gba 3, 5 MP
7. ∀xGxa 6, IU
Prove: ∀K xFx →L ∀K xGx, ¬N Ga O ¬N ∀K xFx
1. ∀xFx → ∀xGx P
2. ¬Ga P
3. ∀xFx H (RAA)
4. ∀xGx 1, 3 MP
5. Ga 4, EU
6. Ga ∧ ¬Ga 2, 5 ∧I
7. ¬∀xFx 3-6 RAA
Lógica de Predicados - Profa. Márcia Rodrigues Notare 8
Introdução existencial (IE): dada uma wff φ contendo uma letra nominal α, podemos inferir
uma wff da forma ∃β φβ/α, onde φβ/α é o resultado da substituição
de uma ou mais ocorrências de α em φ por uma variável β, que
não ocorra em φ.
Diferentemente de IU, IE não coloca restrições em ocorrências prévias da letra nominal α. Com
relação a variável β, ela não precisa substituir todas as ocorrências de α em φ. Portanto, ambas
as demonstrações abaixo são corretas:
1. Fa ∧ Ga P
2. ∃x(Fx ∧ Ga) 1, IE
1. Fa ∧ Ga P
2. ∃x(Fx ∧ Gx) 1, IE
Vejamos alguns exemplo:
Prove: ∀P x(Fx ∨Q Gx) R ∃S x(Fx ∨Q Gx)
1. ∀x(Fx ∨ Gx) P
2. Fa ∨ Ga 1, EU
3. ∃x(Fx ∨ Gx) 2, IE
Prove: ∀P x(Fx ∨Q Gx) R ∃S xFx ∨Q ∃S xGx
1. ∀x(Fx ∨ Gx) P
2. Fa ∨ Ga 1, EU
3. Fa H (PC)
4. ∃xFx 3, IE
5. ∃xFx ∨ ∃xGx 4, ∨I
6. Fa → (∃xFx ∨ ∃xGx) 3-5 PC
7. Ga H (PC)
8. ∃xGx 7, IE
9. ∃xFx ∨ ∃xGx 8, ∨I
10. Ga → (∃xFx ∨ ∃xGx) 7-9 PC
11. ∃xFx ∨ ∃xGx 2, 6, 10 ∨E
Prove: ¬T ∃S xFx R ∀P x¬T Fx
1. ¬∃xFx P
2. Fa H (RAA)
3. ∃xFx 2, IE
4. ∃xFx ∧ ¬∃xFx 1, 3 ∧I
5. ¬Fa 2-4 RAA
6. ∀x¬Fx 5, IU
Prove: ¬T ∃S x(Fx ∧U ¬T Gx) R ∀P x(Fx →V Gx)
1. ¬∃x(Fx ∧ ¬Gx) P
2. Fa H (PC)
3. ¬Ga H (RAA)
4. Fa ∧ ¬Ga 2, 3 ∧I
5. ∃x(Fx ∧ ¬Gx) 4, IE
6. ∃x(Fx ∧ ¬Gx) ∧ ¬∃x(Fx ∧ ¬Gx) 1, 5 ∧I
7. ¬¬Ga 3-6 RAA
8. Ga 7, ¬E
Lógica de Predicados - Profa. Márcia Rodrigues Notare 9
9. Fa → Ga 2-8 PC
10. ∀x(Fx → Gx) 9, IU
Eliminação Existencial (EE): dada uma wff quantificada existencialmente ∃βφ e uma
derivação de alguma conclusão ψ de uma hipótese da forma
φα/β (o resultado de se substituir cada ocorrência da variável β
em φ por uma letra nominal α que não ocorre em φ), podemos
descartar φα/β e rearfirmar ψ.
Restrição: a letra nominal α não pode ocorrer em ψ, nem em qualquer premissa, nem em
qualquer hipótese vigente na linha em que EE é aplicada.
Observe que, da mesma forma que RAA e PC, a regra EE também é hipotética. Vejamos os
exemplos:
Prove: ∀W x(Fx →X Gx), ∃Y xFx Z ∃Y xGx
1. ∀x(Fx → Gx) P
2. ∃xFx P
3. Fa H (EE)
4. Fa → Ga 1, EU
5. Ga 3, 4 MP
6. ∃xGx 5, IE
7. ∃xGx 2, 3-6 EE
Prove: ∃Y x(Fx ∨[ Gx) Z ∃Y xFx ∨[ ∃Y xGx
1. ∃x(Fx ∨ Gx) P
2. Fa ∨ Ga H (EE)
3. Fa H (PA)
4. ∃xFx 3, IE
5. ∃xFx ∨ ∃xGx 4, ∨I
6. Fa → (∃xFx ∨ ∃xGx) 3-5 PC
7. Ga H (PC)
8. ∃xGx 7, IE
9. ∃xFx ∨ ∃xGx 8, ∨I
10. Ga → (∃xFx ∨ ∃xGx) 7-9 PC
11. ∃xFx ∨ ∃xGx 2, 6, 10 ∨E
12. ∃xFx ∨ ∃xGx 1, 2-11 EE
Prove: ∃Y xFx ∨[ ∃Y xGx Z ∃Y x(Fx ∨[ Gx)
1. ∃xFx ∨ ∃xGx P
2. ∃xFx H (PC)
3. Fa H (EE)
4. Fa ∨ Ga 3, ∨I
5. ∃x(Fx ∨ Gx) 4, IE
6. ∃x(Fx ∨ Gx) 2, 3-5 EE
7. ∃xFx → ∃x(Fx ∨ Gx) 2-6 PC
8. ∃xGx H (PC)
9. Ga H (EE)
10. Fa ∨ Ga 9, ∨I
11. ∃x(Fx ∨ Gx) 10, I
Lógica de Predicados - Profa. Márcia Rodrigues Notare 10
12. ∃x(Fx ∨ Gx) 8, 9-11 EE
13. ∃xGx → ∃x(Fx ∨ Gx) 8-12 PC
14. ∃x(Fx ∨ Gx) 1, 7, 13 ∨E
Prove: ∃\ x∀] yLxy ^ ∀] x∃\ yLyx
1. ∃x∀yLxy P
2. ∀yLay H (EE)
3. Lab 2, EU
4. ∃yLyb 3, IE
5. ∀x∃yLyx 4, IU
6. ∀x∃yLyx 1, 2-5 EE
Prove: ∀] x(Fx →_ ∃\ yLxy), ∃\ x(Fx ∧` Gx) ^ ∃\ x∃\ y(Gx ∧` Lxy)
1. ∀x(Fx → ∃yLxy) P
2. ∃x(Fx ∧ Gx) P
3. Fa ∧ Ga H (EE)
4. Fa → ∃yLay 1, EU
5. Fa 3, ∧E
6. ∃yLay 4, 5 MP
7. Lab H (EE)
8. Ga 3, ∧E
9. Ga ∧ Lab 7, 8 ∧I
10. ∃y(Ga ∧ Lay) 9, IE
11. ∃x∃y(Gx ∧ Lxy) 10, IE
12. ∃x∃y(Gx ∧ Lxy) 6, 7-11 EE
13. ∃x∃y(Gx ∧ Lxy) 2, 3-12 EE
Prove: ∀] x(Fx →_ ¬a Gx) ^ ¬a ∃\ x(Fx ∧` Gx)
1. ∀x(Fx → ¬Gx) P
2. ∃x(Fx ∧ Gx) H (RAA)
3. Fa ∧ Ga H (EE)
4. Fa → ¬Ga 1, EU
5. Fa 3, ∧E
6. ¬Ga 4,5 MP
7. Ga 3, ∧E
8. P ∧ ¬P 6,7 CONTRAD
9. P ∧ ¬P 2, 3-8 EE
10 ¬∃x(Fx ∧ Gx) 2-9 RAA
1
UNIVERSIDADE DE CAXIAS DO SUL – UCS
CENTRO DE CIÊNCIAS EXATAS E TECNOLOGIA – CCET
DEPARTAMENTO DE INFORMÁTICA – DEIN
PROFA. MÁRCIA RODRIGUES NOTARE
Lista de Exercícios da Apostila de Lógica de Predicados - Respostas
1. As seguintes fórmulas não são wffs. Justifique cada uma delas:
a) ∀xLzx
Não é uma wff porque a variável z não está quantificada.b) (Fa)
Não é uma wff porque possui parênteses desnecessários.
c) (∃xFx ∧ Gx)
Não é uma wff porque a segunda ocorrência de x não está quantificada.
d) ∀x(Fx)
Não é uma wff porque possui parênteses desnecessários.
e) (∀xFx)
Não é uma wff porque possui parênteses desnecessários.
f) ∃x∀yFx
Não é uma wff porque ∀y requer uma ocorrência de y na fórmula.
g) ∃x∃x(Fx ∧ ¬Gx)
Não é uma wff porque a variável x está quantificada duas vezes na mesma parte da fórmula.
h) ∃xFx ∧ ∃xGx
Não é uma wff porque faltam parênteses. Mas convencionaremos que será uma wff.
2. Algumas das expressões a seguir são wffs, outras não. Para as que são wff, diga como
foram construídas a partir das regras de formação e, para as demais, justifique
porque não são.
a) ∀xLxx
É uma wff: Laa (regra 1) ⇒ ∀xLxx (regras 4).
b) ∃x∀xLxx
Não é uma wff, pois possui dois quantificadores com a mesma variável x.
c) ∃aFa
Não é uma wff, pois não podemos quantificar letra nominal.
d) ∃xFa
Não é uma wff, pois a variável x está quantificada e não ocorre na fórmula.
e) ∀x∀y(Lxy ↔ Lyx)
É uma wff: Lab ↔ Lba (regra 3) ⇒ ∀y(Lay ↔ Lya) (regra 4) ⇒ ∀x∀y(Lxy ↔ Lyx) (regra 4).
f) (Laa)
Não é uma wff, pois possui parênteses desnecessários.
g) ¬∀x¬Fx
É uma wff: Fa (regra 1) ⇒ ¬Fa (regra 2) ⇒ ∀x¬Fx (regra 4) ⇒ ¬∀x¬Fx (regra 2).
h) (∃xFx → ∃xFx)
É uma wff: Fa e Fb (regra 1) ⇒ ∃xFx e ∃xFx (regra 4) ⇒ (∃xFx → ∃xFx) (regra 3).
2
i) (P → ∃xFx)
É uma wff: P e Fa (regra 1) ⇒ ∃xFx (regra 4) ⇒ (P → ∃xFx) (regra 3).
j) Lab → Lba
É uma wff: Lab e Lba (regra 1) ⇒ Lab → Lba (regra 3).
3. Formalize as seguintes sentenças, usando a interpretação indicada. A seguir, verifique
sua formalização através das regras de formação.
Nomes Predicados unários Predicados binários
a – Aristóteles F – é um feminista R - ridicularizou
n – Nietzsche G – é grego E – é mais esperto que
p - Platão P – é um filósofo W - escreveu
a) Aristóteles é grego.
Ga
b) Platão é um grego feminista.
Gp ∧ Fp
c) Se Platão é um feminista, então alguém é um grego feminista.
Fp → ∃x(Gx ∧ Fx)
d) Nenhum grego é feminista.
∀x(Gx → ¬Fx)
e) Todos os feministas são filósofos.
∀x(Fx → Px)
f) Todos os gregos feministas são filósofos.
∀x((Gx ∧ Fx) → Px)
g) Aristóteles escreveu algo.
∃xWax
h) Aristóteles escreveu tudo.
∀xWax
i) Aristóteles escreveu nada.
¬∃xWax ou ∀x¬Wax
j) Nietzsche ridicularizou todos que são feministas.
∀x(Fx → Rnx)
k) Nietzsche ridicularizou todos que eram mais espertos que ele.
∀x(Exn → Rnx)
l) Alguns filósofos ridicularizam a si mesmos.
∃x(Px ∧ Rxx)
m) Alguns filósofos ridicularizam tudo.
∃x∀yRxy

Outros materiais