LISTA1 - Matematica Discreta B

Prévia do material em texto

MAT 01375 � Matemática Discreta B 2013/2
Lista de Exercícios 1
1. Sejam A e B duas proposições. Determine o valor lógico da proposição A sabendo
que:
(a) B é verdadeira e A ∧B é falsa.
(b) A −→ B é verdadeira e A ∧B é falsa.
(c) A←→ B é verdadeira e A ∨B é verdadeira.
2. Construa a tabela verdade das proposições abaixo.
(a) ∼ (A −→∼ B)
(b) (A −→ B)→ A ∧B
(c) (A ∧B −→ C) ∨ (∼ A←→ B∨ ∼ C)
(d) ∼∼ A −→ A
3. Mostre, usando tabela verdade, ou por equivalências, que os conectivos ∨ , −→ e
←→ são equivalentes a combinações de∼ e ∧; ou seja, podemos escrever os conectivos
acima a partir de ∼ e ∧.
4. Sejam A,B proposições. O operador XOR é um conectivo binário, que deno-
taremos por O, tal que AOB é verdadeiro se, e somente se, exatamente uma das
proposições A e B é verdadeira, enquanto que o operador NOR é um conectivo bi-
nário, que denotaremos por M, tal que A M B é verdadeiro se, e somente se, as
proposições A e B são ambas falsas.
(a) Escreva as tabelas verdade de AOB e A M B.
(b) Mostre que os conectivos A∨B, A∧B, A←→ B e A −→ B são equivalentes
a proposições expressas somente em termos de ∼, O e M.
(c) Determine se os operadores O e M são comutativos e associativos. Também
determine se vale a distributividade entre O e M, isto é, se, dadas proposições
A,B,C, temos AO(B M C) ⇐⇒ (AOB) M (AOC) e se A M (BOC) ⇐⇒
(A M B)O(A M C). Justifique.
5. Sejam p, q, r proposições. Mostre, através de tabelas-verdade, as seguintes equi-
valências e implicações:
a) p←→ q ⇐⇒ (p −→ q) ∧ (q −→ p)
b) (p −→ q) ∧ (q −→ r) =⇒ (p −→ r)
c) (p←→ q) ∧ (q ←→ r)⇐⇒ (p −→ q) ∧ (q −→ r) ∧ (r −→ p)
6. Use a lista de equivalências vista em aula para mostrar os seguintes fatos:
1
2
(a) ∼ (A←→ B)⇐⇒ A←→∼ B ⇐⇒∼ A←→ B
(b) ∼ (A ∨B) ∨ (∼ A ∧B)⇐⇒∼ A
(c) (A ∨B)∧ ∼ A =⇒ B
(d) (A ∨B) ∧ (A −→ C) ∧ (B −→ C) =⇒ C
7.Verifique se as proposições abaixo são tautologias ou contradições:.
a) p ∨ ∼ (p ∧ q)
b) (p ∧ q) ∧ ∼ (p ∨ q)
c) ∼ (∼ p ∧ q) ∧ (p ∨ q)←→ p
8.Sejam p e q duas proposições.
a) Construa a tabela verdade de ∼ (p −→ q).
b) Determine uma proposição equivalente à ∼ (p −→ q), ou seja: complete
∼ (p −→ q)⇐⇒ ...
9. Um argumento pode ser representado em forma simbólica como
P1 ∧ P2 ∧ · · · ∧ Pn −→ Q,
onde P1, P2, . . . , Pn são proposições dadas, chamadas de hipóteses, e Q é a conclusão
(ou tese) do argumento. Dizemos que um argumento é válido quando for uma tau-
tologia. Escreva cada um dos argumentos a seguir em forma simbólica, identificando
as hipóteses e a tese, e determine se é válido ou não.
(a) Se o programa é eficiente, é executado rapidamente. Ou o programa é eficiente
ou tem algum bug (ou exclusivo). No entanto, o programa não é executado
rapidamente. Logo, o programa tem um bug.
(b) Se José levou as joias e a Sra. Mendonça mentiu, então foi cometido um crime.
A Sra. Mendonça não estava na cidade. Se um crime foi cometido, então a
Sra. Mendonça estava na cidade. Portanto, José não levou as joias.
(c) Se o acusado fosse culpado, a faca estaria na gaveta no dia 11 de outubro. Ou
a faca não estava na gaveta no dia 11 de outubro ou a testemunha viu a faca.
Se a faca não estava na gaveta no dia 10 de outubro, segue que a testemunha
não viu a faca. Além disso, se a faca estivesse na gaveta no dia 10 de outubro,
o martelo estaria no celeiro. Mas o martelo não estava no celeiro. Então o
acusado é inocente.