Matemática Discreta - 1 (ILC)

Question 1

Respectivamente, o que significam os operadores ¬, v e ^ ? Eles são unários ou binários ? Quando eles assumem o valor de verdade ?

Answer 1

Negação (not) é um operador unário que é verdadeiro quando seu operando é falso.
Disjunção (ou) é um operador binário que é verdadeiro quando um de seus operandos é verdadeiro.
Conjunção (e) é um operador binário que é verdadeiro quando ambos seus operandos são verdadeiros.

Question 2

O que é uma proposição atômica? Qual é seu contraponto?

Answer 2

Proposições atômicas são proposições que não podem ser expressas em termos de proposições mais simples. Seu contraponto são proposições compostas (combinações de proposições simples).

Question 3

Dada uma implicação p → q, qual é a sua contrapositiva, conversa e inversa? Qual tem o mesmo valor lógico de p → q?

Answer 3

Contrapositiva: ¬q → ¬p
Conversa: q → p
Inversa: ¬ p → ¬q

A contrapositiva tem o mesmo valor lógico de p → q.

Question 4

Defina tautologia, contradição e contingência.

Answer 4

Tautologia: Expressão que é sempre verdade
Contradição: Expressão que é sempre falsa
Contingência: Expressão que não é nem uma tautologia nem uma contradição

Question 5

Quando uma implicação p → q é falsa?

Answer 5

Apenas quando p é verdadeiro e q é falso.

Question 6

Como se escreve uma bi-implicação p ↔ q usando apenas os operadores de implicação e conjunção?

Answer 6

(p → q) ^ (q → p)

Question 7

Dê exemplos de expressões da língua portuguesa que exprimem a ideia de implicação.

Answer 7

Se, somente se, quando, logo, por consequência, então.

Question 8

Dê exemplos de expressões da língua portuguesa que exprimem a ideia de bi-implicação.

Answer 8

Se e somente se. Sse.

Question 9

Em lógica proposicional, qual a ordem de procedência dos operadores?

Answer 9

Negação > conjunção > disjunção > implicação > bi-implicação.

Question 10

Em lógica proposicional, o que dizem os dois teoremas de De Morgan ?

Answer 10

1 - A negação de uma conjunção é a disjunção da negação de seus elementos (ou seja, ¬ (p ^ q) = ¬p v ¬q)

2 - A negação de uma disjunção é a conjunção da negação de seus elementos (ou seja, ¬ ( p v q) = ¬p ^ ¬q)

Question 11

Em lógica proposicional, o que significa afirmar que um problema é satisfatível ?

Answer 11

Significa dizer que existe uma valoração de suas variáveis para o qual o problema possui valor verdadeiro.

Question 12

Em lógica de predicados, o que é a quantificação universal de P(X)? E a existencial? Qual é a notação utilizada em ambos os casos?

Answer 12

A quantificação universal é a afirmação “P(X) é verdadeiro para todos os valores no domínio” e é denotada pelo símbolo ∀. A quantificação existencial é a afirmação “P(X) é verdadeiro para algum elemento no domínio” e é denotada pelo símbolo ∃.

Question 13

Como mostrar que a quantificação universal de P(X) é falsa? E a existencial?

Answer 13

Para provar que a quantificação universal de P(X) é falsa, é necessário identificar um item para o qual P(X) é falso. Para provar a existencial, é necessário mostrar que P(X) é falso para todos os X dentro do domínio.

Question 14

De forma simplificada, o que significa o predicado “∀x ∈ R. x + 1 > x” ?

Answer 14

Ele significa que, para todo número real, seu sucessor será um número maior.

Question 15

O que significa dizer que duas expressões p e q são logicamente equivalentes?

Answer 15

Significa dizer que p ↔ q é uma tautologia (ou seja, sempre que p é verdade, q também é e vice-versa).

Question 16

O que acontece quando tentamos aplicar o quantificador universal em um domínio vazio? E o existencial? Por que essas coisas ocorrem?

Answer 16

Se o domínio for vazio, qualquer afirmação universal feita sobre ele será verdadeira. Isso ocorre porque para provar que ela é falsa é necessário apontar um elemento para o qual ela é falsa. Se não existe nenhum elemento é impossível identificá-lo, logo, ela será sempre verdadeira.

Por consequência, toda afirmação existencial será falsa visto que não é possível apontar um elemento para o qual ela é verdadeira.

Question 17

Em lógica de predicados, o que dizem os dois teoremas de De Morgan ?

Answer 17

1 - Negar uma afirmação da forma “para todo X, P(x) é verdade” é o mesmo que dizer “Existe um X para o qual P(X) é falso” (ou seja, ¬∀x. P(x) ≡ ∃x. ¬P(x) ).

2 - Negar uma afirmação da forma “existe um X para o qual P(X) é verdade” é o mesmo que dizer “Para todo X, P(X) é falso” (ou seja, ¬∃x. P(x) ≡ ∀x. ¬P(x)).

Question 18

Considere uma função A(x, y) que significa “x ama y”. A partir disso, como você afirmaria:
1 - Todo mundo ama todo mundo
2 - Alguém ama todo mundo
3 - Alguém é amado por todo mundo
4 - Todo mundo é amado por alguém

Answer 18

1 - ∀x∀y A(x, y)
2 - ∃x∀y A(x, y)
3 - ∃y∀x A(x, y)
4 - ∀y∃x A(x, y)

Question 19

Para cada uma das expressões a seguir, explique quando elas serão falsas:
1 - ∀x∀y P(x, y)
2 - ∃x∀y P(x, y)
3 - ∀y∃x P(x, y)
4 - ∃x∃y P(x, y)

Answer 19

1 - Quando existir um par ordenado(x, y) que faz P(x, y) ser falso
2 - Quando, para todo x, existir ao menos um y que faz P(x, y) ser falso
3 - Quando existir um y tal que, para todo x, P(x, y) é falso.
4 - Quando para todo x e y, P(x, y) é falso.

Question 20

Escreva a seguinte frase usando lógica de predicados:
“Para todo número real, existe um número maior”

Answer 20

∀x ∈R ∃y( y > x)

Question 21

De forma simplificada, o que significa o predicado “∀x. ∃y. (x + y = 0)” ?

Answer 21

Ele significa que, para todo x, existe um y que somado a ele resulta em zero.

Question 22

Escreva a seguinte frase usando lógica de predicados:
“Existe um número natural que não tem nenhum outro número menor que ele”

Answer 22

∃x ∈N ¬∃y (y > x)

Question 23

O que é um argumento em lógica ? O que são suas premissas? O que é sua conclusão? O que significa dizer que um argumento é válido ?

Answer 23

Um argumento é uma sequência de proposições. A última proposição é a conclusão, as outras são as premissas. Um argumento é válido se a conclusão for verdadeira sempre que as premissas também forem.

Question 24

Toda conclusão de um argumento válido é verdadeira e toda conclusão de um argumento inválido é falsa. Essa afirmação é verdadeira ou falsa? Justifique.

Answer 24

Falsa. Um argumento válido pode ter uma conclusão falsa se as premissas forem falsas. Um argumento inválido pode, por sorte, chegar a uma conclusão verdadeira.

Question 25

De maneira resumida, como construir uma prova direta de uma implicação p → q?

Answer 25

Para construir uma prova direta, assuma que p é verdadeiro e mostre que sempre que p for verdadeiro, q também será.

Question 26

De maneira resumida, como construir uma prova por contraposição de uma implicação p → q? Por que essa prova é válida ?

Answer 26

Para construir uma prova por contraposição, assuma que q é falso e mostre que sempre que q for falso, p também será. Essa prova é válida porque a contrapositiva (¬q → ¬p) é logicamente equivalente à original.

Question 27

De maneira resumida, como construir uma prova por contradição de uma afirmação p ?

Answer 27

Para construir uma prova por contradição, assuma que p é falso e mostre que p ser falso implica em uma contradição.

Question 28

De maneira resumida, como construir uma prova por casos de uma implicação p → q?

Answer 28

Para construir uma prova por casos, enumere todos os cenários possíveis que podem ocorrer com p. Em seguida, mostre que não existe nenhum caso em que p é verdadeiro e q é falso.

Question 29

De maneira resumida, como construir uma prova por vacuidade de uma implicação p → q?

Answer 29

Para construir uma prova por vacuidade, mostre que p é falso. Pela definição de implicação, se p for falso, a implicação será verdadeira independente do valor de q.

Question 30

De maneira resumida, como construir uma prova trivial de uma implicação p → q?

Answer 30

Para construir uma prova trivial, mostre que q é sempre verdadeiro. Pela definição de implicação, se q for sempre verdadeiro, a implicação será verdadeira independente do valor de p.