prova01[sub][questoes]

Prévia do material em texto

DCC/ICEx/UFMG
DCC 638 - Introdução à Lógica Computacional
2o semestre de 2019
Área de Teoria
Prova substituta 1 - TZ2, TW5, TW6
2019/12/04
Estudante: Matrícula:
Instruções:
i. Esta prova possui 4 página(s). Confira se sua prova está completa.
ii. Você pode usar o espaço de rascunho à vontade, mas você deve fornecer sua resposta final para cada questão
dentro dos espaços designados. Somente serão consideradas as respostas fornecidas dentro destes espaços.
iii. A clareza e concisão das respostas também é objeto de avaliação.
iv. Nesta prova estão distribuídos 110 pontos. Se você atingir 100 pontos ou mais já é considerado que você tirou total
nesta prova, e os pontos acima de 100 serão desconsiderados.
1. (20 pontos) Preencha cada quadrado abaixo com V ou F de acordo com se a afirmativa correspondente é verdadeira
ou falsa, respectivamente.
Não é necessário justificar suas repostas, mas cada resposta errada anulará uma correta.
(a) A proposição “Estar chovendo é condição suficiente para eu não ir a pé para o trabalho” é equivalente à
proposição “Estar chovendo é condição necessária para eu não ir a pé para o trabalho”.
(b) A proposição “Se estiver chovendo, não vou a pé para o trabalho.” é equivalente à proposição “Se vou a pé
para o trabalho, não está chovendo”.
(c) ¬(q → p)→ ¬p é uma tautologia.
(d) Uma proposição é satisfazível se não é uma contradição
(e) É o caso de que ∀x : ∃y : P (x, y) ≡ ∃x : ∀y : P (x, y).
(f) A negação de “Todo mundo gosta de bolo e sorvete” é “Ninguém gosta de bolo e sorvete”.
(g) A negação de “Existe alguém que não gosta de bolo nem sorvete” é “Todo mundo gosta de bolo ou de
sorvete”.
(h) Um argumento pode ser inválido e ter conclusão verdadeira ao mesmo tempo.
(i) O seguinte argumento é válido: “Todos os dias eu acordo cedo. Nem todo dia em que eu acordo cedo eu
tomo café. Portanto eu nunca tomo café.”
(j) O seguinte argumento é válido: “Se r é um número real tal que
√
r > πr, então r8 < π. Suponha que√
r ≤ πr. Logo r8 > r + 7.”
1
2. (30 pontos) Mostre que as expressões ¬p→ (q → r) e q → (p ∨ r) são equivalentes da forma pedida.
(a) Usando uma tabela da verdade.
(b) Usando manipulação de conectivos lógicos. Justifique os passos de sua derivação.
2
3. (20 pontos) Prove o refute as seguintes afirmações
(a) ∃x : (P (x)→ Q(x)) ≡ ∃x : P (x)→ ∃x : Q(x)
(b) ∀x : (P (x)→ q) ≡ ¬∃x : (P (x) ∧ ¬q).
4. (20 pontos) Seja M(x) o predicado “x é mineiro(a)”, A(x) o predicado “x é aluno(a) da UFMG”, e C(x, y) o
predicado “x conhece y”, onde o universo de discurso de todas as variáveis é o conjunto de todas as pessoas. Utilize
quantificadores para expressar cada uma das afirmações abaixo.
(a) Existe um mineiro que conhece ninguém que é aluno da UFMG.
(b) Maria conhece uma pessoa que não é mineira mas estuda na UFMG.
3
5. (20 pontos) Considere cinco garotas (Ana, Bia, Cida e Drica), três qualidades possíveis (ser levada, ser inteligente
e ser sensível), e as afirmações:
(a) “Ana é inteligente ou Drica é inteligente.”
(b) “Se Cida é sensível, Bia não é levada.”
(c) “Se Ana é inteligente, Bia é levada.”
(d) “Cida é sensível.”
Para cada garota encontre uma qualidade que ela com certeza tem ou com certeza não tem. Explique as regras de
inferência utilizadas em cada passo.
4