Lógica para Computaç˜ao (IF61B-S71)

Curso de Engenharia de Computação – UTFPR
Lógica para Computação (IF61B-S71)
Prof. Celso Kaestner – 1a Verificação (24/04/2008)
(Esta prova é com consulta livre, mas é individual !)
1. (Valor 1,0 ponto) Indique a validade e a forma (termos, figura, diagrama) do silogismo:
Alguns estudantes de computação não são nerds;
Todos os nerds são inteligentes;
Alguns estudantes de computação não são inteligentes.
2. (Valor 1,0 ponto) Adicione parênteses à fórmula p → q → (¬¬p ∨ ¬r),
explicitando claramente a ordem de precedência dos conectivos. Em
seguida encontre, se possı́vel, uma valoração V que torna esta fórmula
falsa.
3. (Valor 1,0 ponto) Construa a tabela-verdade para a fórmula
q → ¬(p ∧ ¬q) → (¬p ∨ q), classificando-a quanto a satisfabilidade,
validade e falsidade.
4. (Valor 1,0 ponto) Escreva um texto de 5 a 8 linhas explicando o teorema da dedução: Γ, A |= B se e somente se Γ |= A → B.
5. (Valor 1,0 ponto) Prove por dedução natural:
p → q ∧ r, ¬q → ¬r ` ¬r → ¬p.
6. (Valor 1,0 ponto) Construa um tableau analı́tico que prove o teorema
` (¬((p → r) ∧ ¬q)) → (¬(p → r) ∨ ¬¬q).
7. (Valor 1,0 ponto) Utilizando o algoritmo de Wang mostre que
p → q ∨ r, q → s, r → s ` ¬s → ¬p.
8. (Valor 1,0 ponto) Encontre a forma normal conjuntiva equivalente
à fórmula p → q ∧ (¬p ∨ ¬(q → r)).
9. (Valor 1,0 ponto) Prove usando o princı́pio da resolução e refutação:
p → (q ∨ ¬r) → s, (p ∧ ¬r) → q, p ∧ q ` s ∨ r.
1
10. (Valor 1,0 ponto) A Lógica Proposicional pode ser diretamente relacionada à Álgebra de Boole, base da eletrônica digital. Dado um
conjunto {p, q . . .} de variáveis booleanas de entrada, uma função
booleana f retorna um valor booleano (0 ou 1) dependendo do valor
das entradas. f pode ser associada à formula em lógica proposicional,
de modo que sua saı́da corresponde ao valor final da fórmula obtido a
partir dos valores atribuı́dos às variáveis de entrada (equivalente a uma
linha da tabela-verdade correspondente).
Uma questão importante é como implementar a função desejada em
hardware. Muitos circuitos integrados implementam diretamente conectivos lógicos: por exemplo, o circuito integrado CMOS 4011 implementa
quatro portas NAND como indicado na figura 1.
Figura 1: Circuito integrado CMOS 4011
Seja a função booleana a três variáveis f (p, q, r) = p ∧ (r → q).
Considerando-se que uma porta NAND equivale ao conectivo de Sheffer
negação conjunta (#):
• como implementar a função f só com portas NAND ?
• quantos circuitos CMOS 4011 seriam necessários ?
• faça um diagrama correspondente ao circuito de f ;
• qual o valor de saı́da para a entrada p = 1, q = r = 0 ?
2