Lista03_PredicadosQuantificadores[solucao]

Prévia do material em texto

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2019/02
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 03
(Predicados e Quantificadores)
Leitura necessária:
• Matemática Discreta e Suas Aplicações, 6a Edição (Kenneth H. Rosen):
– Caṕıtulo 1.3: Predicados e Quantificadores
– Caṕıtulo 1.4: Quantificadores Agrupados
Revisão.
1. Responda formalmente as seguintes perguntas:
(a) Defina o que é um predicado.
Solução do professor: Um predicado é uma sentença que contém um número finito de variáveis
e que se torna uma proposição quando as variáveis são substitúıdas por valores espećıficos.
(b) Qual a diferença principal entre um predicado e uma proposição lógica em termos de seu valor
de verdade? Explique o que pode ser feito com um predicado para se obter uma proposição com
um valor de verdade bem definido.
Solução do professor: A diferença principal entre um predicado e uma proposição é que
uma proposição sempre tem valor de verdade bem definido (verdadeiro ou falso), enquanto um
predicado não tem até que se dêem valores a suas variáveis ou se quantifique sobre as mesmas.
Exerćıcios.
2. (Rosen 1.3.7) Traduza as expressões abaixo para linguagem natural, sabendo que C(x) é “x é um
comediante”, F (x) é “x é engraçado”, e o universo de discurso é o conjunto de todas as pessoas.
(a) ∀x : (C(x)→ F (x))
Solução do professor: Todo comediante é engraçado.
(b) ∀x : (C(x) ∧ F (x))
Solução do professor: Todas as pessoas são comediantes engraçados.
(c) ∃x : (C(x)→ F (x))
Solução do professor: Existe uma pessoa que, se ela é comediante, então ela é engraçada.
(d) ∃x : (C(x) ∧ F (x))
1
Solução do professor: Alguns comediantes são engraçados.
3. (Rosen 1.3.15) Determine o valor de verdade das sentenças abaixo, sabendo que o domı́nio das variáveis
consiste nos números inteiros.
(a) ∀n : n2 ≥ 0
Solução do professor: Verdadeiro: todo inteiro ao quadrado é não-negativo.
(b) ∃n : n2 = 2
Solução do professor: Falso: não existe nenhum inteiro cujo quadrado seja 2.
(c) ∀n : n2 ≥ n
Solução do professor: Verdadeiro: o quadrado de qualquer inteiro é maior ou igual a este
inteiro.
(d) ∃n : n2 < 0
Solução do professor: Falso: o quadrado de nenhum inteiro é negativo.
4. (Rosen 1.3.27) Traduza cada uma das afirmações abaixo em expressões lógicas de 3 maneiras diferentes,
variando o domı́nio e utilizando predicados com uma e duas variáveis.
a) Um estudante na sua escola já morou no Vietnam.
Solução do professor: Dada no livro-texto.
5. (Rosen 1.3.50) Mostre que ∀x : P (x)∨∀x : Q(x) e ∀x : (P (x)∨Q(x)) não são logicamente equivalentes.
Solução do professor: Assuma que o universo de discurso seja o conjunto dos números inteiros.
Seja P (x) a proposição “x é par”, e Q(x), a proposição “x é ı́mpar”. Claramente, dizer que todo
inteiro é par ou é ı́mpar (i.e., ∀x : (P (x) ∨Q(x)), o que é verdadeiro) não é o mesmo que dizer que os
inteiros são todos pares ou todos ı́mpares (i.e., ∀x : P (x) ∨ ∀x : Q(x), o que é falso).
6. (Rosen 1.3.59) Sejam P (x), Q(x) e R(x) as proposições “x é um professor”, “x é ignorante”, e “x é con-
vencido”, respectivamente. Expresse cada uma das declarações utilizando quantificadores, conectivos
lógicos, P (x), Q(x) e R(x), onde o domı́nio consiste de todas as pessoas.
(a) Nenhum professor é ignorante.
Solução do professor: ∀x(P (x)→ ¬Q(x))
(b) Todas as pessoas ignorantes são convencidas.
Solução do professor: ∀x(Q(x)→ R(x))
(c) Nenhum professor é convencido.
2
Solução do professor: ∀x(P (x)→ ¬R(x))
(d) É verdade que (c) segue de (a) e (b)?
Solução do professor: Não, não é verdade. Ser ignorante é suficiente para ser convencido (c),
mas pode não ser necessário. Logo, mesmo que nenhum professor seja ignorante (a), um professor
ainda pode ser convencido.
7. (Rosen 1.4.1) Traduza as sentenças seguintes para linguagem natural, usando como domı́nio o conjunto
dos números reais.
(a) ∀x : ∃y : (x < y)
Solução do professor: Todo número real é menor que algum outro real.
(b) ∀x : ∀y : (((x ≥ 0) ∧ (y ≥ 0))→ (xy ≥ 0))
Solução do professor: O produto de dois números reais não-negativos é um número real
não-negativo.
(c) ∀x : ∀y : ∃z : (xy = z)
Solução do professor: Para todo par de números reais, existe um terceiro número real que é
exatamente o produto do par de números.
8. (Rosen 1.4.9) Seja L(x, y) o predicado “x ama y”, onde o domı́nio consiste de todas as pessoas no
mundo. Utilize quantificadores para expressar cada uma das afirmações abaixo:
(a) Todos amam Jerry.
Solução do professor: ∀x : L(x, Jerry)
(b) Todo mundo ama alguém.
Solução do professor: ∀x : ∃y : L(x, y)
(c) Existe alguém que é amado por todos.
Solução do professor: ∃y : ∀x : L(x, y)
(d) Ninguém ama a todos.
Solução do professor: ¬∃x : ∀y : L(x, y) ou ∀x : ∃y : ¬L(x, y)
(e) Há alguém que Lydia não ame.
Solução do professor: ∃x : ¬L(Lydia, x)
(f) Existe alguém que não é amado por ninguém.
3
Solução do professor: ∃y : ∀x : ¬L(x, y)
(g) Existe exatamente uma pessoa que é amada por todos.
Solução do professor: ∃y : ∀x : (L(x, y) ∧ (∀z : ((∀w : L(w, z))→ y = z)))
(h) Existem exatamente duas pessoas que Lynn ama.
Solução do professor: ∃x : ∃y : (L(Lynn,x) ∧ L(Lynn, y) ∧ x 6= y ∧ (∀z : L(Lynn, z) → z =
x ∨ z = y))
(i) Todo mundo ama a si mesmo(a).
Solução do professor: ∀x : L(x, x)
(j) Existe alguém que não ama a ninguém além de si mesmo(a).
Solução do professor: ∃x : ∀y : L(x, y)↔ x = y
9. (Rosen 1.4.11) Seja S(x) o predicado “x é um estudante”, F (x) o predicado “x é um funcionário”, e
A(x, y) o predicado “x fez uma pergunta a y”, onde o domı́nio das variáveis x e y consiste de todos as
pessoas associadas à universidade. Utilize quantificadores para expressar cada uma das afirmações.
(a) Lois fez uma pergunta ao Prof. Michael.
Solução do professor: A(Lois,Prof. Michael)
(b) Todos os estudantes fizeram uma pergunta ao Prof. Gross.
Solução do professor: ∀x : (S(x)→ A(x,Prof. Gross))
(c) Todos os funcionários fizeram uma pergunta ao Prof. Miller ou tiveram uma pergunta feita a si
pelo Prof. Miller.
Solução do professor: ∀x : (F (x)→ A(x,Prof. Miller) ∨A(Prof. Miller , x))
(d) Existe um estudante que não fez nenhuma pergunta a nenhum funcionário.
Solução do professor: ∃x : (S(x) ∧ ∀y : (F (y)→ ¬A(x, y)))
(e) Existe um funcionário que nunca recebeu uma pergunta de um estudante.
Solução do professor: ∃x : (F (x) ∧ (∀y : S(y)→ ¬A(y, x)))
(f) Todo funcionário já foi perguntado por algum estudante.
Solução do professor: ∀x : (F (x)→ (∃y : S(y) ∧A(y, x)))
(g) Existe um funcionário que já fez um pergunta a todo outro funcionário.
4
Solução do professor: ∃x : (F (x) ∧ (∀y : (F (y) ∧ x 6=y → A(x, y))))
(h) Existe um estudante que nunca recebeu uma pergunta de um funcionário.
Solução do professor: ∃x : (S(x) ∧ (∀y : F (y)→ ¬A(y, x)))
10. (Rosen 1.4.31) Expresse a negação de cada afirmação de forma que todos sinais de negação precedam
imediatamente os predicados.
(a) ∀x : ∃y : ∀z : T (x, y, z)
Solução do professor:
¬∀x : ∃y : ∀z : T (x, y, z) ≡ ∃x : ¬∃y : ∀z : T (x, y, z)
≡ ∃x : ∀y : ¬∀z : T (x, y, z)
≡ ∃x : ∀y : ∃z : ¬T (x, y, z)
(b) ∀x : ∃y : P (x, y) ∨ ∀x : ∃y : Q(x, y)
Solução do professor:
¬(∀x : ∃y : P (x, y) ∨ ∀x : ∃y : Q(x, y)) ≡ ¬∀x : ∃y : P (x, y) ∧ ¬∀x : ∃y : Q(x, y)
≡ ∃x : ¬∃y : P (x, y) ∧ ∃x : ¬∃y : Q(x, y)
≡ ∃x : ∀y : ¬P (x, y) ∧ ∃x : ∀y : ¬Q(x, y)
(c) ∀x : ∃y : (P (x, y) ∧ ∃z : R(x, y, z))
Solução do professor:
¬∀x : ∃y : (P (x, y) ∧ ∃z : R(x, y, z)) ≡ ∃x : ¬∃y : (P (x, y) ∧ ∃z : R(x, y, z))
≡ ∃x : ∀y : ¬(P (x, y) ∧ ∃z : R(x, y, z))
≡ ∃x : ∀y : (¬P (x, y) ∨ ¬∃z : R(x, y, z)))
≡ ∃x : ∀y : (¬P (x, y) ∨ ∀z : ¬R(x, y, z)))
(d) ∀x : ∃y : (P (x, y)→ Q(x, y))
Solução do professor:
¬∀x : ∃y : (P (x, y)→ Q(x, y)) ≡ ∃x : ¬∃y : (P (x, y)→ Q(x, y))
≡ ∃x : ∀y : ¬(P (x, y)→ Q(x, y))
≡ ∃x : ∀y : (P (x, y) ∧ ¬Q(x, y))
11.(Rosen 1.4.44) Utilize quantificadores e conectivos lógicos para expressar que um polinômio quadrático
com coeficientes em R tem no máximo duas ráızes em R.
5
Solução do professor: Assuma que a proposição R(p, x) signifique ”o polinômio p tem o valor real
x como raiz”. Então a afirmativa acima pode ser escrita da seguinte forma, onde p varia sobre o
conjunto de todos os polinômios quadráticos, e x1, x2, x3 variam sobre o conjunto dos números reais.
∀p : ∀x1 : ∀x2 : ∀x3 : ((R(p, x1) ∧R(p, x2) ∧R(p, x3))→ ((x1 = x2) ∨ (x1 = x3) ∨ (x2 = x3))).
12. Argumente se a proposição “O atual rei da França é careca” é verdadeira ou falsa. (Dica: converta a
proposição para uma expressão lógica quantificada e avalie sua veracidade.)
Solução do professor: A resposta a esta pergunta depende de como você converte a sentença em
linguagem natural “O atual rei da França é careca” para uma representação lógica.
Há duas maneiras razoáveis de se fazer isso. Em qualquer caso, seja R(x) o predicado “x é o atual rei
da França” e C(x) o predicado “x é careca”, ambos definidos sobre o universo de discurso consistindo
no conjunto de todas as pessoas.
• A primeira alternativa é interpretar “O atual rei da França é careca” como
∃x : (R(x) ∧ C(x)),
ou seja, “Existe uma pessoa que é o atual rei da França, e esta pessoa é careca”. Sob esta
interpretação a afirmativa é falsa, já que ninguém no mundo é o atual rei da França (após uma
revolução convoluta e desdobramentos posteriores, a França não tem mais reis há séculos...).
• A segunda alternativa é interpretar “O atual rei da França é careca” como
∀x : (R(x)→ C(x)),
ou seja, “Para todas as pessoas do mundo, se ela é o atual rei da França, então ela é careca”.
Sob esta interpretação a afirmativa é verdadeira por vacuidade (i.e., a hipótese da implicação é
falsa para todo elemento do domı́nio, já que ninguém é o atual rei da França).
6