lista 01 - FTC

Prévia do material em texto

Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Fundamentos de Teoria da Computação
Prof. Rodrigo Yoshikawa Oeiras
Lista de Exercícios 01: Proposições.
1. Nas frases abaixo, use as palavras “sim” e “não” para indicar se as frases são 
proposições.
a) Ele é, certamente, um homem alto.
b) Dois é um número primo.
c) Os juros vão subir ano que vem.
d) X2 – 4 = 0
2. Dados os valores lógicos: A é verdadeira, B é falsa e C é verdadeira, qual o valor 
lógico das proposições a seguir:
a) A (B C)˄ ˅
b) (A B)' C˄ ˅
c) (A B) C˄ ˅
d) A' (B' C)'˅ ˄
3. Encontre o antecedente e o consequente de cada uma das proposições a seguir.
a) O crescimento sadio de plantas é consequência de quantidade suficiente de água.
b) A economia de energia para aquecimento implica boa insulação ou vedação de 
todas as janelas.
c) Serão introduzidos erros apenas se forem feitas modificações no programa.
DICA :
O fogo é umacondição necessária paraa fumaça .
Se houver fumaça , então haverá fogo.
4. Qual o valor lógico para cada uma das proposições a seguir?
a) 8 é par ou 6 é ímpar.
b) 8 é par e 6 é ímpar.
c) 8 é ímpar ou 6 é ímpar.
d) 8 é ímpar e 6 é ímpar.
e) Se 8 for ímpar, então 6 é ímpar.
f) Se 8 for par, então 6 é ímpar.
g) Se 8 for ímpar, então 6 é par.
h) Se 8 for ímpar e 6 for par, então 8 < 6.
5. São dadas diversas formas de negação para cada uma das proposições a seguir. 
Quais estão corretas?
a) A resposta é 2 ou 3.
1. A resposta é nem 2 nem 3.
2. A resposta não é 2 ou não é 3.
3. A resposta não é 2 e não é 3.
b) Pepinos são verdes e têm sementes.
1. Pepinos não são verdes e não têm sementes.
2. Pepinos não são verdes ou não têm sementes.
3. Pepinos são verdes e não têm sementes.
c) 2 < 7 e 3 é ímpar
1. 2 > 7 e 3 é par.
2. 2 ≥ 7 e 3 é par.
3. 2 ≥ 7 ou 3 é ímpar.
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
4. 2 ≥ 7 ou 3 é par.
6. Escreva a negação de cada uma das afirmações a seguir:
a) O processador é rápido, mas a impressora é lenta.
b) O processador é rápido ou a impressora é lenta.
c) Se o processador é rápido, então a impressora é lenta.
d) Ou o processador é rápido e a impressora é lenta, ou então o arquivo está 
danificado.
7. Se A, B e C representam as seguintes proposições:
A. Rosas são vermelhas
B. Violetas são azuis
C. Açúcar é doce.
Escreva as FBFs abaixo em português.
a) B C'˅
b) B' (A˅ ⟶C)
c) (C A')˄ ⟷B
d) C (A'˄ ⟷B)
8. Se A, B e C representam as seguintes proposições:
A. Rosas são vermelhas
B. Violetas são azuis
C. Açúcar é doce.
Escreva as proposições compostas a seguir em notação simbólica.
a) Rosas são vermelhas e violetas são azuis.
b) Sempre que violetas são azuis, rosas são vermelhas e açúcar é doce.
c) Rosas são vermelhas apenas se violetas não forem azuis ou se açúcar for 
amargo.
d) Rosas são vermelhas e, se açúcar for amargo, então ou violetas não são azuis ou 
açúcar é doce.
9. Escreva cada uma das preposições compostas em notação simbólica, usando letras 
de proposição para denotar componentes.
a) Se Anita ganhar a eleição, então os impostos serão reduzidos.
b) Os impostos serão reduzidos somente se Anita ganhar as eleições e a economia 
permanecer forte.
c) Os impostos serão reduzidos se a economia permanecer forte.
d) Uma economia forte virá se Anita ganhar a eleição.
e) A economia permanecerá forte se, e somente se, Anita ganhar a eleição ou os 
impostos forem reduzidos.
10.Sejam A, B, C e D as seguintes proposições:
A O bandido é francês.
B O herói é americano.
C A heroína é inglesa.
D O filme é bom.
Escreva em notação simbólica as proposições compostas a seguir:
a) O herói é americano e o filme é bom.
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
b) Embora o bandido seja francês, o filme é bom.
c) Se o filme é bom, então o herói é americano ou a heroína é inglesa.
d) O herói não é americano, mas o bandido é francês.
e) Uma heroína inglesa é uma condição necessária para o filme ser bom.
11.Escreva cada uma das proposições compostas a seguir em notação simbólica, 
usando letras de proposição para denotar as componentes.
a) Se o cavalo estiver descansado, o cavaleiro vencerá.
b) O cavaleiro vencerá apenas se o cavalo estiver descansado e a armadura forte.
c) Um cavalo descansado é uma condição necessária para o cavaleiro vencer.
d) O cavaleiro vencerá se, e somente se, a armadura for forte.
e) Uma condição suficiente para o cavaleiro vencer é que a armadura seja forte ou o 
cavalo esteja descansado.
12.Construa tabelas verdade para as FBFs a seguir. Note quaisquer tautologias ou 
contradições.
a) (A → B) ↔ A' B˅
b) (A B) C˄ ˅ → A (B C)˄ ˅
c) A (A' B')'˄ ˅
d) A B → A'˄
e) (A → B) → [(A C) → (B C)]˅ ˅
f) A → (B → A)
g) A B ↔ B' A'˄ ˅
h) (A B') (A B)'˅ ˄ ˄
i) [(A B) C'] → A' C˅ ˄ ˅
13.Um chip de memória de um microprocessador tem 24 elementos com dois estados, 
ligado e desligado. Qual o número total de configurações de ligado/desligado 
possíveis?
14. Prove as tautologias a seguir usando as tabelas adequadas.
a) (A^B’)^C ↔ (A^C)^B’
b) (A^B’)’ ˅ B ↔ A’ ˅ B
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
Tabelas
Expressão em Português Conectivo Lógico Expressão Lógica
e; mas; também; além disso Conjunção A^B
Ou Disjunção A ˅ B
Se A, então B.
A implica B.
A, logo B.
A só se B; A somente se B.
B segue A.
A é uma condição suficiente para B; basta A para B.
B é uma condição necessária para A.
Condicional A→ B
A se e comente se B
A é condição necessária e suficiente para B.
Bicondicional A ↔ B
Não A
É falso que A …
Não é verdade que A ...
Negação A’
Equivalências Tautológicas
A B <═> B A˄ ˄ A B <═> B A˅ ˅ Comutatividade
(A B) C <═> A (B C)˄ ˄ ˄ ˄ (A B) C <═> A (B C)˅ ˅ ˅ ˅ Associatividade
A (B C) <═> (A B) (A C)˄ ˅ ˄ ˅ ˄ A (B C) <═> (A B) (A C)˅ ˄ ˅ ˄ ˅ Distributividade
A 1 <═> A˄ A 0 <═> A˅ Elemento neutro
A A’ <═> 0˄ A A’ <═> 1˅ Complementares
Respostas
1. a) não b) sim c) sim d) não
2. a) V b) V c) V d) F
3. a) antecedente: quantidade suficiente de água; consequente: crescimento sadio de 
plantas. b) antecedente: economia de energia; consequente: boa insulação ou 
vedação de todas as janelas c) antecedente: erros introduzidos, consequente: 
modificações no programa.
4. a) V ; b) F ; c) F; d)F; e)V; f) F; g) V; h)V
5. a) 1 e 3; b) 2; c) 4
6. a) O processador é lento ou a impressora é rápida. b) O processador é lento e a 
impressora é rápida. c) O processador é rápido, mas impressora também. d) O 
processador é lento ou a impressora é rápida, mas também o arquivo não está 
danificado.
7. a) Violetas são azuis ou açúcar não é doce. b) Violetas não são azuis ou, se rosas 
são vermelhas, então o açúcar é doce. c) Açúcar é doce e rosas não são vermelhas, 
se e apenas se violetas são azuis. d) Açúcar é doce, mas rosas não são vermelhas se 
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
e apenas se violetas são azuis.
8. a) A ^ B; b) B→ (A^C); c) A→ (B’˅C’); d) A^[C’ → (B’ C˅ )]
9. a) A⟶B. b) B⟶(A˄C). c) C⟶B. d) A⟶C. e) C⟷(A B˅ ).
10. a) B^D; b) A^D; c) D→ (B˅C); d) B’^A; e) D→ C.
11.A: cavalo descansado, B: cavaleiro vencer, c: armadura forte. a) A→B; b) B→ A^C; c) 
B→ A; d) B↔C; e) (C˅A )→ B.
12.
a) TAUTOLOGIA
A B (A⟶B) A' B⟷ ˅
V V V
V F V
F V V
F F V
b)
A B C (A B) C˄ ˅ A (B C)⟶ ˄ ˅
V V V V
V V F V
V F V V
V F F V
F V V F
F V FV
F F V F
F F F V
c)
A B A (A' B')'˄ ˅
V V V
V F F
F V F
F F F
d)
A B A B A'˄ ⟶
V V F
V F V
F V V
F F V
e) TAUTOLOGIA
A B C (A B) [(A C) (B C)]⟶ ⟶ ˅ ⟶ ˅
V V V V
V V F V
V F V V
V F F V
F V V V
F V F V
F F V V
F F F V
f)TAUTOLOGIA
A B A (B A)⟶ ⟶
V V V
V F V
F V V
F F V
g)CONTRADIÇÃO
A B A B B' A'˄ ˅⟷
V V F
V F F
F V F
F F F
h)
A B (A B') (A B)'˅ ˄ ˄
V V F
V F V
F V F
F F V
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
i)
A B C [(A B) C'] A' C˅ ˄ ˅⟶
V V V V
V V F F
V F V V
V F F F
F V V V
F V F V
F F V V
F F F V
13. 2 elevado a 24.
14. a) (A^B’)^C | A^(B’^C) | A^(C^B’) | (A^C)^B’ ; b) (A^B’)’ B | (A’ B’’) B | (A’ B) B | ˅ ˅ ˅ ˅ ˅
A’ (B B) | A’ B.˅ ˅ ˅