Trabalho 1 de mat discreta - Respostas

Prévia do material em texto

Trabalho 1 de Matemática Discreta 
 
1. (MACKENZIE – SP) Se 𝐴 e 𝐵 são dois conjuntos tais que 𝐴 ⊆ 𝐵 e 𝐴 ≠ ∅. Assinale a 
alternativa correta. 
a) sempre existe 𝑥 ∈ 𝐴 tal que 𝑥 ∉ 𝐵. 
b) sempre existe 𝑥 ∈ 𝐵 tal que 𝑥 ∉ 𝐴. 
c) se 𝑥 ∈ 𝐵 então 𝑥 ∈ 𝐴. 
d) se 𝑥 ∉ 𝐵 então 𝑥 ∉ 𝐴. 
A expressão A ⊂ B e A ≠ Φ, significa dizer que conjunto A está todo contido em B e ele 
não é vazio (existe no mínimo um elemento). Então, se não existe em B, também não 
existirá em A. 
e) 𝐴 ∩ 𝐵 = ∅. 
 
2. No concurso para o CPCAR foram entrevistados 979 candidatos, dos quais 527 
falam a língua inglesa, 251 a língua francesa e 321 não falam nenhum desses idiomas. O 
número de candidatos que falam as línguas inglesa e francesa é 
a) 778 b) 120 c) 658 d) 131 
Temos que o total de candidatos entrevistados foi de 979. 
Dentre estes, sabemos que 321 não falam inglês, nem francês. 
Se subtrairmos estes valores, encontraremos o número de candidatos que falam uma ou 
ambas as línguas. 
Temos que 658 entrevistados falam inglês e/ou francês. 
O enunciado nos disse que 527 falam inglês e 251 falam francês, a soma destes 
candidatos é de 778. Mas só sobraram 658 entrevistados que falam alguma destas 
línguas. 
Então, o "excesso" de candidatos destes 658 falam ambas as línguas. 
Desta forma: 778 - 658 = 120 candidatos falam as duas línguas. 
 
3. (UFC-2003) Sejam 𝑀 e 𝑁 conjuntos que possuem um único elemento em comum. 
Se o número de subconjuntos de 𝑀 é igual ao dobro do número de subconjuntos de 𝑁, o 
número de elementos do conjunto 𝑀 ∪ 𝑁 é: 
a) o triplo do número de elementos de 𝑀. 
b) o triplo do número de elementos de 𝑁. 
c) o quádruplo do número de elementos de 𝑀. 
d) o dobro do número de elementos de 𝑀. 
e) o dobro do número de elementos de 𝑁. 
Número de subconjuntos de M => 2^m 
Número de subconjuntos de N => 2^n 
2^m = 2.2^n 
2^m = 2^(n+1) 
m = n+1 
(A U B) = n(M)+n(N)-n(M ∩ N) 
(A U B) = (n+1)+(n)-1 
(A U B) = 2n 
Logo,o número de elementos do conjunto união é igual ao dobro do número de 
elementos de N 
 
4. Lógicas Fuzzy são utilizadas em inteligência artificial. Na lógica fuzzy, a proposição 
tem um valor-verdade que é um número entre 0 e 1, inclusive. Uma proposição com 
valorverdade 0 é falsa e com valor-verdade 1 é verdadeira. Valores entre 0 e 1 indicam 
variantes de grau de verdade. Por exemplo, o valor-verdade 0,8 pode ser indicado para 
uma proposição “Fred é feliz”, porque ele é feliz na maior parte do tempo; e o 
valorverdade 0,4 pode ser indicado para a proposição “John é feliz” porque ele é feliz 
menos que a metade do tempo. 
a) O valor-verdade da negação de uma proposição em lógica fuzzy é 1 menos o 
valorverdade da proposição. Quais são os valores-verdade das proposições “Fred não é 
feliz” e “John não é feliz”? 
Denote por: 
pf = 0, 8: "Fred é feliz"; 
pj = 0, 4: "John é feliz". 
Agora, de acordo com o texto, podemos considerar 
¬pf = 1 − pf = 1 − 0, 8 
O que nos dá ¬pf= 0, 2, isto é, "Fred não é feliz". De modo análogo, 
¬pj = 1 − pj = 1 − 0, 4 = 0, 6, isto é, "John não é feliz". 
b) O valor-verdade da conjunção de duas proposições em lógica fuzzy é o mínimo 
dos valores-verdade das proposições. Quais os valores-verdade para as proposições “Fred 
e John são felizes” e “Nem Fred nem John são felizes”? 
"Fred e John são felizes" 
pf ∧ pj = min(0,8;0,4) = 0,4 
"Nem Fred nem John são felizes" 
¬pf ∧ ¬pj = min(0,2;0,6) = 0,2 
c) O valor-verdade da disjunção de duas proposições em lógica fuzzy é o máximo 
dos valores-verdade das duas proposições. Quais os valores-verdade das proposições 
“Fred é feliz ou John é feliz” e “Fred não é feliz ou John não é feliz”? 
"Fred é feliz ou John é feliz" 
pf ∨ pj = max(0,8;0,4) = 0,8 
"Fred não é feliz ou John não é feliz" 
¬pf ∨ ¬pj = max(0,2;0,6) = 0,6 
 
5. A n-ésima proposição de uma lista de 100 proposições é “Exatamente n dessas 
proposições nesta lista são falsas”. 
a) Quais conclusões você pode obter sobre os valores verdade dessas proposições? 
"Exatamente n dessas proposições nesta lista são falsas" é um paradoxo e não pode 
ser avaliada como verdadeira ou falsa de forma consistente, independentemente do 
valor de n. 
b) Responda o item a) se a n-ésima proposição for “No mínimo n dessas proposições nesta 
são falsas”. 
A proposição "No mínimo n dessas proposições nesta lista são falsas" não é um 
paradoxo e pode ser avaliada como verdadeira ou falsa de forma consistente. Se 
assumirmos que a proposição é verdadeira, então sabemos que pelo menos n 
proposições na lista são falsas. Além disso, também sabemos que, no máximo, 100 - n 
proposições podem ser verdadeiras. Portanto, podemos concluir que exatamente n ou 
mais proposições na lista são falsas. 
c) Responda o item b), assumindo que a lista contém 99 proposições. 
Se a lista contém 99 proposições, então a proposição "No mínimo n dessas proposições 
nesta lista são falsas" é verdadeira para qualquer valor de n entre 1 e 99, inclusive. 
Isso ocorre porque sempre há pelo menos uma proposição que é falsa na lista, 
portanto, a proposição é verdadeira para n = 1. Além disso, se escolhermos n = 99, 
sabemos que todas as proposições, exceto uma, são falsas, o que satisfaz a proposição. 
Portanto, a proposição é verdadeira para n = 1 a 99, inclusive. 
 
 
6. Determine a negação para a proposição “Se estudar então irei bem na prova”. 
"Se eu não fui bem na prova então não estudei.". 
 
7. (VUNESP – TJ/SP – 2017) Considerando falsa a afirmação “Se Ana é gerente, então 
Carlos é diretor”, a afirmação necessariamente verdadeira é: 
a) Ana não é gerente, ou Carlos é diretor. 
b) Ana não é gerente, e Carlos não é diretor. 
c) Ana é gerente. 
"Se Ana é gerente, então Carlos é diretor", é falso. 
Para que a condicional seja falsa, temos que A é verdadeiro e B é falso. Sendo 
assim: 
A = "Ana é gerente." (verdadeiro) 
B = "Carlos é diretor." (falso) 
d) Ana é gerente, e Carlos é diretor. 
e) Carlos é diretor. 
 
8. (VUNESP – TJ/SP – 2017) Uma afirmação equivalente para “Se estou feliz, então 
passei no concurso” é: 
a) Passei no concurso e não estou feliz. 
b) Estou feliz e passei no concurso. 
c) Se não passei no concurso, então não estou feliz. 
A afirmação "Se estou feliz, então passei no concurso" pode ser reescrita na forma 
contrapositiva como "Se não passei no concurso, então não estou feliz". Isso 
ocorre porque a contrapositiva de uma afirmação condicional (se A, então B) é 
outra afirmação condicional que mantém a verdade lógica da primeira (se não B, 
então não A). Portanto: 
(Se A, então B) é equivalente a (Se Não B, então Não A) 
A = "estou feliz" 
B = "passei no concurso" 
Não A = "não estou feliz" 
Não B = "não passei no concurso" 
Uma afirmação equivalente para “Se estou feliz, então passei no concurso” é: 
"Se não passei no concurso, então não estou feliz". 
d) Se passei no concurso, então estou feliz. 
e) Não passei no concurso e não estou feliz. 
9. Quais os valores-verdade das proposições abaixo? 
a) ∃! 𝑥𝑃(𝑥) ⟶ ∃𝑥𝑃(𝑥) 
O valor verdade desta proposição é verdadeiro. 
b) ∀𝑥𝑃(𝑥) ⟶ ∃!𝑥𝑃(𝑥) 
O valor verdade desta proposição é falso. 
c) ∃! 𝑥¬𝑃(𝑥) ⟶ ¬∀𝑥𝑃(𝑥) 
O valor verdade desta proposição é verdadeiro. 
 
10. Mostre que ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) e ∀𝑥𝑃(𝑥) ∨ ∀𝑥𝑄(𝑥) não são logicamente equivalentes. 
 Podemos mostrar que ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) e ∀𝑥𝑃(𝑥) ∨ ∀𝑥𝑄(𝑥) não são logicamente 
equivalentes através de um contraexemplo. Vamos considerar um conjunto universo 
com dois elementos, a saber, 𝑎 e 𝑏, e definir as propriedades: 
P(𝑥) como "𝑥 é 𝑎" e Q(𝑥) como "𝑥 é 𝑏". 
Assim, temos que: 
∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) é verdadeira, pois para todos os elementos 𝑥 no conjunto universo, ou 
𝑃(𝑥) é verdadeira (no caso, 𝑥 = 𝑎), ou 𝑄(𝑥) é verdadeira (no caso, 𝑥 =𝑏). 
∀𝑥𝑃(𝑥) ∨ ∀𝑥𝑄(𝑥) é falsa, pois não podemos encontrar um único elemento quesatisfaça 
ambas as propriedades 𝑃(𝑥) e 𝑄(𝑥). 
Portanto, ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) e ∀𝑥𝑃(𝑥) ∨ ∀𝑥𝑄(𝑥) não são logicamente equivalentes, já 
que encontramos um modelo onde a primeira é verdadeira e a segunda é falsa. 
11. Mostre que ∃𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) e ∃𝑥𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥) são logicamente equivalentes. 
 Tabela-verdade para ∃𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)): 
𝑃(𝑥) 𝑄(𝑥) 𝑃(𝑥) ∨ 𝑄(𝑥) ∃𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) 
V V V V 
V F V V 
F V V V 
F F F F 
 
 
 
 
 
Tabela-verdade para ∃𝑥𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥) 
 
𝑃(𝑥) 𝑄(𝑥) ∃𝑥𝑃(𝑥) ∃𝑥𝑄(𝑥) ∃𝑥𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥) 
V V V V V 
V F V F V 
F V F V V 
F F F F F 
 
Podemos ver que as duas tabelas-verdades são idênticas. Em outras palavras, para 
cada combinação de valores de 𝑃(𝑥) e 𝑄(𝑥), as duas fórmulas têm o mesmo valor 
lógico. Portanto, ∃𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) e ∃𝑥𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥) são logicamente equivalentes. 
12. Mostre que as premissas “Se meu cliente fosse culpado, a faca estaria na gaveta”. “Ou 
a faca não estava na gaveta ou José da Silva viu a faca”. “Se a faca não estava lá no 
dia 10 de outubro, então José da Silva não viu a faca”. Além disso, “se a faca estava 
lá no dia 10 de outubro, então a faca estava na gaveta e o martelo estava no celeiro”. 
“Mas todos sabemos que o martelo não estava no celeiro” levam à conclusão 
“Senhoras e senhores, meu cliente é inocente”. 
Podemos representar as premissas e a conclusão usando símbolos lógicos da seguinte 
forma: 
p → q 
¬q → r ∨ s 
¬r → ¬s 
r → (t ∧ u) 
¬u 
Conclusão: ¬p 
Podemos então usar dedução natural para mostrar que a conclusão é uma 
consequência lógica das premissas: 
Suponha que p é verdadeiro. 
Da premissa 1, segue que q é verdadeiro. 
Suponha que ¬q é verdadeiro. 
Da premissa 2, segue que r ∨ s é verdadeiro. 
Se r é verdadeiro, então t ∧ u é verdadeiro, pela premissa 4. 
Mas ¬u é verdadeiro, pela premissa 5. 
Isso implica que ¬t é verdadeiro. 
Da premissa 3, segue que ¬r é verdadeiro. 
Mas isso contradiz o fato de que r ∨ s é verdadeiro. 
Portanto, ¬¬q é verdadeiro, ou seja, q é verdadeiro. 
Da premissa 1, segue que ¬p é falso. 
Portanto, ¬p é verdadeiro, concluindo que "Senhoras e senhores, meu cliente é 
inocente".