Introdução à Lógica Computacional Flashcards
O que é uma proposição simples/sentença simples/proposição atômica? Dê um exemplo.
Uma frase declarativa simples sem conectivos lógicos cuja veracidade não depende outros fatores. Por exemplo: “Maria foi hoje à igreja.”
O que são proposições compostas?
São formadas por um conjunto de proposições simples (duas ou mais proposições simples ligadas por “conectivos lógicos”).
O que é uma proposição condicional? Qual seu valor semântico?
É 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”.
Quando uma proposição condicional assume o valor verdadeiro e quando assume o valor falso?
Valor verdadeiro:
- p e q verdadeiros.
- p e q falsos.
- p falso e q verdadeiro.
Valor falso:
- p verdadeiro e q falso.
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.
p ^ ¬ q.
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.
p ∨ q.
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.
(p ∨ q) ^ (p → ¬ q)
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.
(p ^ r) → ¬ q.
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.
r ^ ( ¬ p ^ q ).
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.
q → ( ¬ r ^ ¬ p).
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.
a) falsa.
b) verdadeira.
c) verdadeira.
d) verdadeira.
Qual a diferença do “ou inclusivo” para o “ou exclusivo”?
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.
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ã.
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ã.
Quando é uma tautologia?
Quando todos os valores verdade de uma proposição são verdadeiros.
Quando é uma contradição?
Quando todos valores verdade de uma proposição são falsos.
Quando é uma contingência?
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).
Qual o símbolo do OU exclusivo?
⊕.
Respectivamente, o que significam os operadores ¬, v e ^ ? Eles são unários ou binários ? Quando eles assumem o valor de verdade ?
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.
Dada uma implicação p → q, qual é a sua contrapositiva, conversa e inversa? Qual tem o mesmo valor lógico de p → q?
Contrapositiva: ¬q → ¬p
Conversa: q → p
Inversa: ¬ p → ¬q
A contrapositiva tem o mesmo valor lógico (equivalência lógica) de p → q.
Como se escreve uma bi-implicação p ↔ q usando apenas os operadores de implicação e conjunção?
(p → q) ^ (q → p)
Dê exemplos de expressões da língua portuguesa que exprimem a ideia de bi-implicação.
Se e somente se, somente se, e vice-versa, desde que e apenas se, se e só se, Sse.
Em lógica proposicional, qual a ordem de procedência dos operadores?
Negação > conjunção > disjunção > implicação > bi-implicação.
Em lógica proposicional, o que dizem os dois teoremas de De Morgan?
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)
Em lógica proposicional, o que significa afirmar que um problema é satisfatível?
Significa dizer que existe uma valoração da proposição para o qual o problema possui valor verdadeiro.
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?
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 ∃.
Como mostrar que a quantificação universal de P(X) é falsa? E a existencial?
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.
De forma simplificada, o que significa o predicado “∀x ∈ R. x + 1 > x” ?
Ele significa que, para todo número real, seu sucessor será um número maior.
O que significa dizer que duas expressões p e q são logicamente equivalentes?
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).
O que acontece quando tentamos aplicar o quantificador universal em um domínio vazio? E o existencial? Por que essas coisas ocorrem?
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.
Em lógica de predicados, o que dizem os dois teoremas de De Morgan?
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)).
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
1 - ∀x∀y A(x, y)
2 - ∃x∀y A(x, y)
3 - ∃y∀x A(x, y)
4 - ∀y∃x A(x, y)
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)
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.
Escreva a seguinte frase usando lógica de predicados:
“Para todo número real, existe um número maior”
∀x ∈R ∃y(x < y)
De forma simplificada, o que significa o predicado “∀x. ∃y. (x + y = 0)” ?
Ele significa que, para todo x, existe um y que somado a ele resulta em zero.
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”
∃x ∈N ¬∃y (y > x)
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 ?
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.
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.
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.
De maneira resumida, como construir uma prova direta de uma implicação p → q?
Para construir uma prova direta, assuma que p é verdadeiro e mostre que sempre que p for verdadeiro, q também será.
De maneira resumida, como construir uma prova por contraposição de uma implicação p → q? Por que essa prova é válida ?
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.
De maneira resumida, como construir uma prova por casos de uma implicação p → q?
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.
De maneira resumida, como construir uma prova por vacuidade de uma implicação p → q?
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.
De maneira resumida, como construir uma prova trivial de uma implicação p → q?
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.
Quando um argumento é válido como uma proposição condicional universal - ∀x, P(x) →Q(x)?
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á).
Coloque essa frase na negação de proposições quantificadas:
“Todos matemáticos usam óculos.”
“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.”
Coloque essa frase na negação de proposições quantificadas:
“∀ primos p, p é ímpar.”
“∃ um número primo p|p não é ímpar.”
Coloque essa frase na negação de proposições existenciais:
“Alguns peixes respiram ar.”
¬(∃x ∈ D | Q(x)) ≡ ∀x ∈ D, ¬Q(x)
“Nenhum peixe respira ar.”
Coloque essa frase em negação de proposição condicional universal:
“∀ pessoas p, se p é loura então p tem olhos azuis.”
∃ uma pessoa p | p é loura e p não tem olhos azuis.
O que é um predicado em lógica? Qual sua definição?
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).”
Quais são os valores das variáveis dos predicados?
Os valores do domínio que são conjuntos de variáveis.
O que é um conjunto verdade? Como é denotado?
É 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
P(x) -> Q(x) significa o que?
e P(x) ↔ Q(x)?
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).
Qual o símbolo de conclui-se que?
∴
Qual a forma da proposição condicional universal? Quando o argumento é válido?
∀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.
Estabeleça a negação da seguinte proposição quantificada multiplamente:
“∃ uma pessoa x, tal que ∀ as pessoas y, x ama y.”
“∀ as pessoas x, ∃ uma pessoa y tal que x não ama y.
Estabeleça a negação da seguinte proposição quantificada multiplamente:
“∀ inteiros n, ∃ um inteiro k tal que n = 2k.”
∃ um inteiro n, tal que ∀ inteiro k, n ≠ 2k.
A proposição universal é uma generalização de qual conectivo lógico?
Do conectivo lógico E (conjunção - ^).
A proposição existencial é uma generalização de qual conectivo lógico?
Do conectivo lógico OU (disjunção - ∨).
O que é uma “condição suficiente”? Dê um exemplo.
∀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.
O que é uma “condição necessária”? Dê um exemplo.
∀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.
O que diz a “regra da instanciação universal”? Dê um exemplo.
Essa regra é a ferramenta fundamental do quê?
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.
