Introdução à Lógica Computacional

Question 1

O que é uma proposição simples/sentença simples/proposição atômica? Dê um exemplo.

Answer 1

Uma frase declarativa simples sem conectivos lógicos cuja veracidade não depende outros fatores. Por exemplo: “Maria foi hoje à igreja.”

Question 1

O que são proposições compostas?

Answer 1

São formadas por um conjunto de proposições simples (duas ou mais proposições simples ligadas por “conectivos lógicos”).

Question 2

O que é uma proposição condicional? Qual seu valor semântico?

Answer 2

É uma sentença do formato p → q (uma proposição composta).

Essa sentença possui valor semântico de: “Se, então; significa que; implica em”.

Question 3

Quando uma proposição condicional assume o valor verdadeiro e quando assume o valor falso?

Answer 3

Valor verdadeiro:
- p e q verdadeiros.
- p e q falsos.
- p falso e q verdadeiro.

Valor falso:
- p verdadeiro e q falso.

Question 4

Sabendo que:

p: Está abaixo de zero.
q: Está nevando.

Escreva a frase “Está abaixo de zero, mas não está nevando.” usando p, q e conectivos lógicos.

Answer 4

p ^ ¬ q.

Question 5

Sabendo que:

p: Está abaixo de zero.
q: Está nevando.

Escreva a frase “Está nevando ou abaixo de zero(ou os dois).” usando p, q e conectivos lógicos.

Answer 5

p ∨ q.

Question 6

Sabendo que:

p: Está abaixo de zero.
q: Está nevando.

Escreva a frase “Está nevando ou abaixo de zero, mas não está nevando se estiver abaixo de zero.” usando p, q e conectivos lógicos.

Answer 6

(p ∨ q) ^ (p → ¬ q)

Question 7

Sabendo que:

p: Ursos-cinzentos são vistos na área.
q: Fazer caminhada na trilha é seguro.
r: As bagas estão maduras ao longo da trilha.

Escreva a frase “Caminhada não é segura ao longo da trilha sempre que os ursos-cinzentos são vistos na área e as bagas estão maduras ao longo da trilha.” usando p, q, r e conectivos lógicos.

Answer 7

(p ^ r) → ¬ q.

Question 8

Sabendo que:

p: Ursos-cinzentos são vistos na área.
q: Fazer caminhada na trilha é seguro.
r: As bagas estão maduras ao longo da trilha.

Escreva a frase “Ursos-cinzentos não são vistos na área e fazer caminhada na trilha é seguro, mas as bagas estão maduras ao longo da trilha.” usando p, q, r e conectivos lógicos.

Answer 8

r ^ ( ¬ p ^ q ).

Question 9

Sabendo que:

p: Ursos-cinzentos são vistos na área.
q: Fazer caminhada na trilha é seguro.
r: As bagas estão maduras ao longo da trilha.

Escreva a frase “Para a caminhada ser segura, é necessário, mas não suficiente que as bagas não estejam maduras ao longo da trilha e que os ursos-cinzentos não sejam vistos na área.” usando p, q, r e conectivos lógicos.

Answer 9

q → ( ¬ r ^ ¬ p).

Question 10

Determine se cada uma destas proposições condicionais e verdadeira ou falsa.

(a) Se 1+1 =2, então 2+2 = 5.
(b) Se 1+1 =3, então 2+2 = 4.
(c) Se 1+1 =3, então 2+2 = 5.
(d) Se macacos puderem voar, então 1 +1 = 3.

Answer 10

a) falsa.
b) verdadeira.
c) verdadeira.
d) verdadeira.

Question 11

Qual a diferença do “ou inclusivo” para o “ou exclusivo”?

Answer 11

A diferença é que no “ou inclusivo” a valoração é verdadeira se pelo menos uma das proposições for verdadeira.

Já no “ou exclusivo”, a valoração é verdadeira se apenas uma das proposições for verdadeira, não ambas.

Question 12

Escreva a seguinte frase na conversa (oposta), contrapositiva e inversa: “Se nevar hoje, esquiarei amanhã”.

p: Se nevar hoje. p → q = Se nevar hoje, então esquiarei amanhã.
q: Esquiarei amanhã.

Answer 12

conversa (q → p): Se eu esquiar amanhã, então hoje nevou.
contrapositiva (¬ q → ¬ p): Se eu não esquiar amanhã, então hoje não nevou.
inversa (¬ p → ¬ q): Se não nevar hoje, então não esquiarei amanhã.

Question 13

Quando é uma tautologia?

Answer 13

Quando todos os valores verdade de uma proposição são verdadeiros.

Question 14

Quando é uma contradição?

Answer 14

Quando todos valores verdade de uma proposição são falsos.

Question 15

Quando é uma contingência?

Answer 15

Quando nem todos os valores verdade de uma proposição são verdadeiros ou falsos (ou seja, quando não são nem uma tautologia, nem uma contradição).

Question 16

Qual o símbolo do OU exclusivo?

Answer 16

⊕.

Question 17

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

Answer 17

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 18

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

Answer 18

Contrapositiva: ¬q → ¬p
Conversa: q → p
Inversa: ¬ p → ¬q
A contrapositiva tem o mesmo valor lógico (equivalência lógica) de p → q.

Question 19

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

Answer 19

(p → q) ^ (q → p)

Question 20

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

Answer 20

Se e somente se, somente se, e vice-versa, desde que e apenas se, se e só se, Sse.

Question 21

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

Answer 21

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

Question 22

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

Answer 22

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 23

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

Answer 23

Significa dizer que existe uma valoração da proposição para o qual o problema possui valor verdadeiro.

Question 24

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 24

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 25

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

Answer 25

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 26

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

Answer 26

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

Question 27

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

Answer 27

Significa dizer que a valoração das proposições p e q que são idênticas, ou seja, p ↔ q é uma tautologia (ou seja, sempre que p é verdade, q também é e vice-versa).

Question 28

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

Answer 28

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 29

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

Answer 29

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 30

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 30

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 31

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 31

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 32

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

Answer 32

∀x ∈R ∃y(x < y)

Question 33

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

Answer 33

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

Question 34

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 34

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

Question 35

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 35

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 36

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 36

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 37

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

Answer 37

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

Question 38

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

Answer 38

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 39

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

Answer 39

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 40

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

Answer 40

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 41

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

Answer 41

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.

Question 42

Quando um argumento é válido como uma proposição condicional universal - ∀x, P(x) →Q(x)?

Answer 42

Se forem verdadeiras todas as combinações de valores-verdade das variáveis de uma sentença.
(Se as premissas são todas verdadeiras, então a conclusão também será).

Question 43

Coloque essa frase na negação de proposições quantificadas:
“Todos matemáticos usam óculos.”

Answer 43

“Alguns matemáticos não usam óculos.”, ou “Existe ao menos um matemático que não usa óculos.”, ou “Um ou mais matemáticos não usam óculos.”

Question 44

Coloque essa frase na negação de proposições quantificadas:
“∀ primos p, p é ímpar.”

Answer 44

“∃ um número primo p|p não é ímpar.”

Question 45

Coloque essa frase na negação de proposições existenciais:
“Alguns peixes respiram ar.”
¬(∃x ∈ D | Q(x)) ≡ ∀x ∈ D, ¬Q(x)

Answer 45

“Nenhum peixe respira ar.”

Question 46

Coloque essa frase em negação de proposição condicional universal:
“∀ pessoas p, se p é loura então p tem olhos azuis.”

Answer 46

∃ uma pessoa p | p é loura e p não tem olhos azuis.

Question 47

O que é um predicado em lógica? Qual sua definição?

Answer 47

Pode ser obtido removendo substantivos de uma proposição. É definido como:
“Um predicado é uma sentença que contém um número finito de variáveis (valores do domínio) e se torna uma proposição quando as variáveis são substituídas por valores específicos (valores do domínio).”

Question 48

Quais são os valores das variáveis dos predicados?

Answer 48

Os valores do domínio que são conjuntos de variáveis.

Question 49

O que é um conjunto verdade? Como é denotado?

Answer 49

É o conjunto de todos os valores de um domínio ao qual seu valor dentro do predicado é verdadeiro quando substituído por x.
É denotado por { x ∈ D | P(x) }.O

Question 50

P(x) -> Q(x) significa o que?
e P(x) ↔ Q(x)?

Answer 50

Que o conjunto verdade de P(x) está também em Q(x).
Que o conjunto verdade de P(x) é idêntico ao Q(x).

Question 51

Qual o símbolo de conclui-se que?

Answer 51

∴

Question 52

Qual a forma da proposição condicional universal? Quando o argumento é válido?

Answer 52

∀x, P(x) -> Q(x)
Para todo x, se P(x) então Q(x).
Um argumento da forma ∀x, P(x) -> Q(x) é válido se as premissas forem verdadeiras e a conclusão também.

Question 53

Estabeleça a negação da seguinte proposição quantificada multiplamente:
“∃ uma pessoa x, tal que ∀ as pessoas y, x ama y.”

Answer 53

“∀ as pessoas x, ∃ uma pessoa y tal que x não ama y.

Question 54

Estabeleça a negação da seguinte proposição quantificada multiplamente:
“∀ inteiros n, ∃ um inteiro k tal que n = 2k.”

Answer 54

∃ um inteiro n, tal que ∀ inteiro k, n ≠ 2k.

Question 55

A proposição universal é uma generalização de qual conectivo lógico?

Answer 55

Do conectivo lógico E (conjunção - ^).

Question 56

A proposição existencial é uma generalização de qual conectivo lógico?

Answer 56

Do conectivo lógico OU (disjunção - ∨).

Question 57

O que é uma “condição suficiente”? Dê um exemplo.

Answer 57

∀x, R(x) é uma condição suficiente para S(x).

∀x, R(x) -> S(x) (proposição condicional padrão)

Exemplo:
- Ser quadrado é uma condição suficiente para ser retangular.
- ∀x, se x é quadrado, então x é retangular.

Question 58

O que é uma “condição necessária”? Dê um exemplo.

Answer 58

∀x, R(x) é uma condição necessária para S(x).

∀x, ¬R(x) -> ¬S(x) ≡ ∀x, S(x) -> R(x) (a inversa é equivalente logicamente à conversa)

• Ter 35 anos é uma condição necessária para ser presidente do Brasil.
• ∀x, se x não tem 35 anos, então x não pode ser presidente do Brasil.
• ∀x, se x é presidente do Brasil então x tem 35 anos.

Question 59

O que diz a “regra da instanciação universal”? Dê um exemplo.
Essa regra é a ferramenta fundamental do quê?

Answer 59

Se uma propriedade é verdadeira para todos os elementos do domínio então é verdadeira para um elemento em particular do domínio.

Todos os seres humanos são mortais;
Sócrates é um ser humano;
∴ Sócrates é mortal.

Essa regra é ferramenta fundamental do raciocínio dedutivo.