Lista matematica discreta

Matematica Discreta

Lista de exerccios 1

Cada p denota um nvel de diculdade: p facil, pp medio e ppp difcil.

p 1. Considere que P e a sentenca \A comida e boa", Q e \O servico e bom" e R e \A classicac~ao e

tr^es estrelas". Escreva as seguintes sentencas usando P, Q, R e conectivos logicos:

1. Ou a comida e boa, ou o servico e bom, ou ambos.

2. Ou a comida e boa, ou o servico e bom, mas n~ao ambos.

3. A comida e boa, enquanto que o servico e pobre.

4. N~ao ha o caso em que a comida seja boa e a classicac~ao seja tr^es estrelas.

5. Se a comida e o servico s~ao bons, ent~ao a classicac~ao e tr^es estrelas.

6. N~ao e verdade que tr^es estrelas sempre signica boa comida e bons servicos.

p 2. Construa a tabela verdade para as seguintes sentencas:

1. (P ) :Q) _ :P

2. (P _ :Q) ) :Q

3. P () (:P _ :Q)

4. (P ) (Q ) R)) ) ((P ) Q) ) (P ) R))

pp 3. Considere a seguinte advert^encia feita na embalagem de um jogo:

1. Existem tr^es sentencas nesta advert^encia.

2. Duas das sentencas desta advert^ecia s~ao falsas.

3. O incremento medio do QI das pessoas que aprendem este jogo e de mais de 20 pontos.

A ultima sentenca e verdadeira ? Escreva a argumentac~ao de sua resposta.

pp 4. (OBMEP Nvel 1 - 2018) Vovo Vera quis saber qual de suas cinco netinhas fez um desenho na

parede de sua sala. As netinhas zeram as seguintes declarac~oes. Se apenas uma delas mentiu, descubra

quem fez o desenho. Escreva a argumentac~ao da sua resposta.

 Emlia: N~ao fui eu.

 Lusa: Quem desenhou foi a Marlia ou a Rafaela.

 Marlia: N~ao foi a Rafaela nem a Vitoria.

 Rafaela: N~ao foi a Lusa.

 Vitoria: Lusa n~ao esta dizendo a verdade.

ppp 5. Um naufrago chega em uma ilha onde convivem duas tribos A e B. Todos os nativos da tribo

A sempre mentem. Todos os nativos da tribo B sempre falam a verdade. Ao se deparar com um nativo,

o naufrago fez a seguinte pergunta: \Existe ouro nesta ilha ?". O nativo respondeu: \Existe ouro na ilha

se e somente se eu falo a verdade". Usando logica matematica, descubra se existe ou n~ao ouro na ilha.

p 6. Mostre quais das seguintes sentencas s~ao verdadeiras quando o \2" e colocado no lugar do \ ".

Em seguida, mostre quais delas s~ao verdadeiras quando \" e colocado no lugar do \ ":

1. f;g f;; f;gg.

2. f;g f;; ff;ggg.

3. ff;gg f;; f;gg.

4. ff;gg f;; ff;ggg.

5. ff;gg f;; f;; f;ggg.

pp 7. Demonstre que se B  C, ent~ao P(B)  P(C).