matematica discreta

Fundação Universidade Federal do Rio Grande
Curso de Tecnologia em Análise e Desenvolvimento de Sistemas

MATEMÁTICA DISCRETA – LISTA

DE

EXERCÍCIOS 3

1. Construa tabelas-verdade para as expressões abaixo. Note quaisquer tautologias ou contradições.

a)
b)
c)
d)

A → (B → A)
A ∧ B ↔ B' ∨ A'
(A ∨ B') ∧ (A ∧ B)'
[(A ∨ B) ∧ C'] → A' ∨ C

2. Justifique cada passo (dizendo ao lado de cada linha qual a regra foi aplicada) na demonstração de validade dos argumentos abaixo:

a) C ∧ (D' → C ' ) → D
1.
2.
3.
4.
5.
6.
7.

C
D' → C '
(D' )' ∨ C '
D∨ C'
C'∨ D
C→D
D

b) [(A ∨ B') → C] ∧ (C → D) ∧ A → D
1.
2.
3.
4.
5.
6.

(A ∨ B') → C
C→D
A
A ∨ B'
C
D

3. Usando lógica proposicional, prove que cada argumento verbal abaixo é válido:

a) Se segurança é um problema, então o controle será aumentado. Se segurança não é um problema, então os negócios na Internet irão aumentar. Portanto, se o controle não for aumentado, os negócios na Internet crescerão.
b) Não é verdade que, se as tarifas de energia subirem, então o uso diminuirá, nem é verdade que ou novas usinas elétricas serão construídas ou as contas não serão pagas com atraso.
Portanto, o uso não vai diminuir e as contas serão pagas com atraso.
c) Se José levou as jóias ou a Sra. Krasov mentiu, então foi cometido um crime. O Sr. Krasov não estava na cidade. Se um crime foi cometido, então o Sr. Krasov estava na cidade.
Portanto, José não levou as jóias.

Fundação Universidade Federal do Rio Grande
Curso de Tecnologia em Análise e Desenvolvimento de Sistemas

4. Encontre o valor lógico da expressão
(∃

x)(A(x) ∧ (∀y)[B(x,y) → C(y)])

com a interpretação de que o conjunto universo é o conjunto dos inteiros, A(x) significa que “x > 0”, B(x) significa que x > y e C(x) é “y ≤ 0”.
5. Usando os símbolos predicados indicados e quantificadores apropriados, escreva cada declaração em português como uma expressão lógica. Considere o conjunto universo como o mundo inteiro.
P(x) = x é uma pessoa
T(x) = x é um período de tempo
E(x, y, z) = x