lista 03 - FTC

Prévia do material em texto

Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Fundamentos de Teoria da Computação
Prof. Rodrigo Yoshikawa Oeiras
Lista de Exercícios 03: Quantificadores
1. Qual o valor lógico de cada uma das FBFs abaixo? O conjunto universo é o conjunto 
dos inteiros. 
a) ( x)( y)(x<y y<x).∀ ∀ ∧
b) ( x)( y)(x∃ ∃ 2=y).
c) ( x)[x<0→( y)(y>0 x+y=0)].∀ ∃ ∧
d) ( x)(x∀ 2>0).
2. Considerando a interpretação de que o conjunto universo é todos os estados do Brasil 
e que:
Q(x,y) é “x está ao norte de y”;
P(x) é “x começa com a letra M”;
a é o estado “Mato Grosso do Sul”,
Determine o valor lógico de cada FBF abaixo:
a) ( x)P(x).∀
b) ( y)( x)Q(x,y).∃ ∃
c) ( y)Q(a,y).∃
d) ( x)( y)( z)[Q(x,y) Q(y,z)→Q(x,z)]∀ ∀ ∀ ∧
e) ( x)( y)[P(y) Q(x,y)]∀ ∃ ∧
3. Nas FBFs abaixo, faça a análise das interpretações e verifique se as FBFs são 
verdadeiras ou falsas.
a) ( x)( y)[P(x,y)→P(y,x)] ; onde o domínio é uma coleção de linhas no plano e∀ ∀ 
P(x,y) é a propriedade de que x é paralelo a y.
b) ( x)[P(x)→( y)Q(x,y)] ; onde o domínio é a coleção de todas as pessoas e P(x) é∀ ∃ 
a propriedade “x é masculino” e Q(x,y) é a propriedade “y é irmão de x”. 
c) ( x)[A(x) ( y)B(x,y)]; onde o domínio é dos números positivos e A(x) é “par” e∃ ∧ ∀ 
B(x,y) é “x≤y”;
d) [( x)A(x)→( x)B(x)]→( x)[A(x)→B(x)]; onde o domínio é dos inteiros e A(x) é∀ ∀ ∀ 
“x>0” e B(x) é “x≥0”;
4. Identifique as variáveis livres.
a) ( x)[P(x)→Q(y)]∀
b) ( x)[A(x) ( y)B(y)]∃ ∧ ∀
5. Usando os símbolos predicados indicados e os quantificadores apropriados, escreva 
cada declaração em português como uma FBF predicada. O conjunto universo é o 
mundo inteiro.
B(x) é “x é uma bola”;
R(x) é “x é redondo”;
S(x) é “x é uma bola de futebol”.
a) Todas as bolas são redondas;
b) Nem todas as bolas são bolas de futebol;
c) Todas as bolas de futebol são redondas;
d) Algumas bolas não são redondas;
e) Algumas bolas são redondas, mas as bolas de futebol não são;
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
f) Toda bola redonda é uma bola de futebol;
g) Só bolas de futebol são bolas redondas;
h) Se todas as bolas de futebol são redondas, então todas as bolas são redondas.
6. Usando os símbolos predicados indicados e os quantificadores apropriados, escreva 
cada declaração em português como uma FBF predicada. O conjunto universo é o 
mundo inteiro.
P(x) é “x é uma pessoa”;
T(x) é “x é um período de tempo”;
E(x,y) é “x é enganado por y”.
a) Você pode enganar algumas pessoas todo o tempo;
b) Você pode enganar todas as pessoas durante algum tempo;
c) Você não pode enganar todas as pessoas todo o tempo.
7. Usando os símbolos predicados indicados e os quantificadores apropriados, escreva 
cada declaração em português como uma FBF predicada. O conjunto universo é o 
mundo inteiro.
J(x) é “x é um juiz”;
F(x) é “x é um farmacêutico”;
L(x) é “x é um advogado”;
M(x) é “x é uma mulher”;
A(x,y) é “x admira y”.
a) Existem algumas mulheres advogadas que são farmacêuticas;
b) Nenhuma mulher é, ao mesmo tempo, advogada e farmacêutica;
c) Alguns advogados só admiram juízes;
d) Todos os juízes admiram apenas juízes;
8. Dê versões em português para as FBFs abaixo. Considere as propriedades:
A(x,y) é “x ama y”;
V(x) é “x é vistoso”;
H(x) é “x é um homem”;
B(x) ẃ “x é bonita”;
j é “João”;
c é “Cátia”;
M(x) é “x é uma mulher”.
a) V(j)∧A(c,j);
b) ( x)[H(x)→V(x)];∀
c) ( x)(M(x)→( y)[A(x,y)→H(y) V(y)]);∀ ∀ ∧
d) ( x)(M(x) B(x) ( y)[A(x,y)→V(y) H(y)])∃ ∧ ∧ ∀ ∧
9. Escreva a negação das proposições a seguir:
a) Algumas páginas na rede têm som;
b) Todas as páginas na rede têm som e vídeo;
c) Todas as páginas na rede têm som ou vídeo;
d) Algumas páginas na rede não têm som nem vídeo;
10.Negue as declarações a seguir:
a) Alguns fazendeiros só produzem milho;
b) Todos os fazendeiros produzem milho;
c) Milho só é produzido por fazendeiros.
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Respostas
1. a) F; b) V (x=2 e y=4); c) V (x=-y); d) F (não vale para x=0);
2. a) F; b) V; c) V; d) V (analisar o termo Q(x,y)∧Q(y,z)); e) F (Vai ter um x em que o y 
não está ao norte)
3. a) V; b) F (pode ser irmã); c) F; d) V.
4. a) y; b) sem variáveis livres.
5. a) ( x)[B(x)→R(x)]; b) [( x)(B(x)→S(x))]'; c) ( x)[S(x)→R(x)]; d) ( x)[B(x) [R(x)]']; e)∀ ∀ ∀ ∃ ∧ 
( x)[B(x) R(x)] ( x)(S(x)→[R(x)]'); f) ( x)[B(x) R(x)→S(x)]; g)( x)[B(x) R(x)→S(x)];∃ ∧ ∧ ∀ ∀ ∧ ∀ ∧ 
h) ( x)[S(x) R(x)]→( x)[B(x) R(x)];∀ ∧ ∀ ∧
6. a) ( x)[P(x) ( y)[T(y)→E(x,y)]]; b) ( x)[P(x)→( y)(T(y) E(x,y))]; c) {( x)[P(x)→( y)∃ ∧ ∀ ∀ ∃ ∧ ∀ ∀
[T(y)→E(x,y)]]}' ou {( x)( y)(P(x) T(y)→E(x,y))}' ou ( x)( y)(P(x) T(y) [E(x,y)]')∀ ∀ ∧ ∃ ∃ ∧ ∧
7. a) ( x)[M(x) L(x) F(x)]; b) ( x)(M(x)→[L(x) F(x)]'); c) ( x)(L(x) ( y)(A(x,y)→J(y)));∃ ∧ ∧ ∀ ∧ ∃ ∧ ∀ 
d) ( x)∀ { J(x)→( y)∀ [ A(x,y)→J(y )] }
8. a) João é vistoso e Cátia ama João; b) Todos os homens são vistosos; c) Todas as 
mulheres amam os homens vistosos; d) Algumas mulheres bonitas amam os homens 
vistosos.
9. Supondo que P(x) é “x é uma página na rede com som” e V(x) é “x é uma página na 
rede com vídeo”; a) [( x)P(x)]'=( x)[P(x)]' Todas as páginas na rede não tem som; b)∃ ∀ 
[( x)(P(x) V(x))]' = ( x)(P(x) V(x))'=( x)[(P(x))'∀ ∧ ∃ ∧ ∃ ∨(V(x))'] “Existem algumas páginas na 
rede sem om ou sem vídeo”; c) [( x)(P(x)∀ ∨V(x))]'= ( x)(P(x)∃ ∨V(x))'=( x)∃
[(P(x))' (V(x))'] “Existem algumas páginas na rede sem som e sem vídeo”; d) [( x)∧ ∃
((P(x))' (V(x))')]' = ( x)((P(x))' (V(x))')' = ( x)(P(x)∧ ∀ ∧ ∀ ∨V(x)) “Todas as páginas na rede 
tem som ou tem vídeo”.
10.a) Todos os fazendeiros produzem tudo com exceção de milho; b) Alguns fazendeiros 
não produzem milho; c) Algumas pessoas produzem milho e não são fazendeiros.