Lista Matemática Discreta: Logica Proposicional

Matematica Discreta 2019/01

Area de Teoria DCC/UFMG

~

LISTA DE EXERCICIOS (SOLUCAO)

Logica Proposicional

(Rosen - Cap tulo 1)

Leitura necessaria para esta lista: Discrete Mathematics and Its Applications (Rosen, 7a Edic~ao):

Cap tulo 1.1: Propositional Logic

Cap tulo 1.2: Applications of Propositional Logic

Cap tulo 1.3: Propositional Equivalences

Observac~ao: Os exerc cios est~ao classi cados em n veis de di culdade: [Facil], [Medio] e [Dif cil]. Esta classi cac~ao, entretanto, e apenas indicativa. Pessoas diferentes podem discordar sobre o n vel de di culdade de um mesmo exerc cio. N~ao desanime ao ver um exerc cio dif cil, voc^e pode descobrir que ele e facil, encontrando uma maneira de resolv^-lo mais simples do que a do professor!

1. [Facil] (Rosen 1.1.1) Quais das sentencas abaixo s~ao proposic~oes? Qual o valor de verdade das que s~ao proposic~oes?

(a) Boston e a capital de Massachusetts.

Soluc~ao do professor: E uma proposic~ao verdadeira.

(b) Miami e a capital da Florida.

Soluc~ao do professor: E uma proposic~ao falsa.

(c) 2 + 3 = 5

Soluc~ao do professor: E uma proposic~ao verdadeira.

(d) 5 + 7 = 10

Soluc~ao do professor: E uma proposic~ao falsa.

(e) x + 2 = 11

Soluc~ao do professor: N~ao e uma proposic~ao.

(f) Responda a esta pergunta.

1

Soluc~ao do professor: N~ao e uma proposic~ao.

2. [Facil] (Rosen 1.1.7) Suponha que durante o ultimo ano scal, o faturamento da Acme Computer

foi de 138 bilh~oes de dolares, e seu lucro l quido foi de 8 bilh~oes de dolares; o faturamento da Nadir

Software foi de 87 bilh~oes de dolares, e seu lucro l quido foi de 5 bilh~oes de dolares; e o faturamento da

Quixote Media foi de 111 bilh~oes de dolares, e seu lucro l quido foi de 13 bilh~oes de dolares. Determine

o valor de verdade de cada uma das proposic~oes abaixo sobre o ultimo ano scal.

(a) A Quixote Media teve o maior faturamento. Soluc~ao do professor: Proposic~ao falsa.

(b) A Nadir Software teve o menor lucro l quido e a Acme Computer teve o maior faturamento. Soluc~ao do professor: Proposic~ao verdadeira.

(c) A Acme Computer teve o maior lucro l quido ou a Quixote Media teve o maior lucro l quido. Soluc~ao do professor: Proposic~ao verdadeira.

(d) Se a Quixote Media teve o menor lucro l quido, ent~ao a Acme Computer teve o maior faturamento. Soluc~ao do professor: Proposic~ao verdadeira.

(e) A Nadir Software teve o menor lucro l quido se, e somente se, a Acme Computer teve o maior faturamento.

Soluc~ao do professor: Proposic~ao verdadeira.

3. (Rosen 1.1.9) Sejam p e q as proposic~oes \E permitido nadar na costa de New Jersey" e \Tubar~oes foram avistados perto da costa", respectivamente. Expresse cada uma das proposic~oes compostas abaixo em uma sentenca em linguagem natural.

(a) :p _ q (c) p $ :q

(b) p ! :q (d) :p ^ (p _ :q)

Soluc~ao do professor:

(a) :p _ q: \N~ao e permitido nadar na costa de New Jersey."

(b) p ! :q: \Se e permitido nadar na costa de New Jersey, ent~ao n~ao foram avistados tubar~oes perto da costa."

$ :

(c) p q: \E permitido nadar na costa de New Jersey se, e somente se, n~ao foram avistados tubar~oes perto da costa."

(d) :p ^ (p _ :q): \N~ao e permitido nadar na costa de New Jersey e ou e pertmitido nadar na costa de New Jersey ou tubar~oes n~ao foram avistados perto da costa."

2

4. [Medio] (Rosen 1.1.15) Sejam p, q e r as seguintes proposic~oes:

p : Ursos pardos foram vistos na area.

q : E seguro caminhar na trilha.

r : Ha frutas maduras ao longo da trilha.

Escreva as seguintes proposic~oes utilizando p, q, r e conectivos logicos.

(a) Ha frutas maduras ao longo da trilha, mas ursos pardos n~ao foram vistos na area. Soluc~ao do professor: r ^ :p

(b) Ursos pardos n~ao foram vistos na area e caminhar na trilha e seguro, mas frutas est~ao maduras ao longo da trilha.

Soluc~ao do professor: :p ^ q ^ r

(c) Se ha frutas maduras ao longo da trilha, caminhar e seguro se, e somente se, ursos pardos n~ao foram vistos na area.

Soluc~ao do professor: r ! (q $ :p)

(d) N~ao e seguro caminhar na trilha, mas ursos pardos n~ao foram vistos na area e ha frutas maduras ao longo da trilha.

Soluc~ao do professor: :q ^ :p ^ r

(e) Para que seja seguro caminhar na trilha, e necessario mas n~ao su ciente que n~ao haja frutas maduras ao longo da trilha e que ursos pardos