Cap. 1 - Linguagem Matemática e Lógica Informal Flashcards
Princípio da Não Contradição?
Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.
Princípio do Terceiro Excluído?
Ou é vdd ou é falsa.
Como fica. a equivalência traduzida de símbolo para português?
Se e só se.
O que torna uma fórmula bem formulada válida/não válida?
O facto de ser uma tautologia/não ser uma tautologia, ou seja, verdade para qualquer interpretação.
O que torna uma fbf inconsistente? Qual é a diferença para uma fbf não válida?
É que seja o simétrico de uma tautologia, ou seja, falsa para qualquer interpretação.
Como é que se prova a equivalência entre duas fbfs?
São equivalentes se a sua tabela de verdade for uma tautologia.
Modus ponens?
[p ∧ (p ⇒ q)] ⇒ q
Modus tollens?
[(p ⇒ q) ∧ ¬q] ⇒ ¬p
Silogismo hipotético?
[(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)
Como sabemos se um conjunto é subconjunto próprio de um outro conjunto?
B é subconjunto prórpio de B se B ⊂ A e B ≉ A.
Tal que exista pelo menos um x ∈ A e x ∉ B.
O que resulta da diferença simétrica entre dois conjuntos?
Resulta o conjunto formado pelos elementos que estão nos dois conjuntos menos na sua interseção.
Que conjunto resulta do produto cartesiano entre dois conjuntos A e B
A × B = {(x, y) : x ∈ A ∧ y ∈ B}
Todas as relações binárias são um subconjunto do produto cartesiano entre esses conjuntos em causa.
OK
O que faz uma Relação Reflexiva?
Se (x, x) ∈ R.
O que faz uma Relação Simétrica?
Se (x, y) ∈ R ⇒ (y, x) ∈ R
O que faz uma Relação Anti-Simétrica?
Se [(x, y) ∈ R ∧ (y, x) ∈ R] ⇒ x = y
O que faz uma Relação Transitiva?
Se [(x, y) ∈ R ∧ (y, z) ∈ R] ⇒ (x, z) ∈ R
O que compõe um relação de ordem parcial?
RAT
O que compõe um relação de equivalência?
RST
Qual é a definnição de classe de equivalência?
[x] = {y ∈ A : (x, y) ∈ R}
O que é o conjunto quociente?
É o conjunto de todas as classes de equivalência de um dado conjunto A.
O que são partições de um conjunto?
São subconjuntos das partes de um conjunto.
Teorema sobre as relações de equivalência e as suas partições:
Se R é uma relação de equivalência, então o conjunto quociente A/R é uma partição de A.
Condição para ser função?
Um elemento do conjnunto de partida corresponder a apenas um elemento do conjunto de chegada.
Qual a condição para uma função ser considerada injetiva?
f(x) = f(y) ⇒ x = y
A objetos diferentes correspondem imagens diferentes.
Não podem existir objetos diferentes com a mesma imagem.
Qual a condição para uma função ser considerada sobrejetiva?
A todo o elemento no conjunto de chegada corresponde um elemento no conjunto de partida.
Não pode haver um elemento no conjunto de chegada que não tenha um elemento correspondido no conjunto de partida.
Qual a condição para que uma função seja invertível?
Tem de ser bijetiva.
Passos a tomar para se encontrar a função inversa de uma função?
- Partir de f(x) = y.
- Resolver em ordem a x.
- Substituir y por x.
Que condição define conjuntos como equipotentes?
A condição que constata que tem de existir uma bijeção entre os dois conjuntos.
Ou seja é possível establecer um função bijetiva entre os dois conjuntos.
O que são conjuntos equipotentes?
Conjuntos com o mesmo número de elementos, ou com o mesmo cardinal.
Teorema: Comparação da cardinalidade entre dois conjuntos injetivos entre si.
Dados dois conjuntos A e B, a cardinalidade de A não é superior à de B se existe uma função injetiva entre os dois.
Condições para que um conjunto seja numerável?
Seja finito ou equipotente ao conjunto N.
O que constata o teorema de Dedekind-Cantor?
Um conjunto é infinito se e só se é equipotente a um
subconjunto próprio.
Ou seja um dado conjunto é infinito se tiver o mesmo número de elementos que um subconjunto próprio.
O que constata o teorema de Schröder-Bernstein?
É uma propriedade transitiva entre conjuntos:
Sejam X e Y dois conjuntos.
Se f : X → Y e g : Y → X são
funções injectivas, então existe uma bijecção h : X → Y.
Como se define um termo? O que pode ser considerado um termo?
Uma constante, uma variável e funções cujos argumentos sejam termos são consideradas também elas termos.
Exemplos:
1) 12;
2) y;
3) pai de(Luisa).
Como se define um predicado?
Um predicado é uma função que a uma dada lista de
constantes faz corresponder um valor lógico.
Exemplo:
Maior(x, y) é um predicado que traduz a relação “x é maior do que y”.
Como se define um átomo?
Um átomo é a junção um predicado, ou seja, uma função que relaciona duas constantes, com termos, ou seja, os argumentos do predicados são termos, se assim for essa expressão toda é um átomo.
Neste caso identifique o alcançe de cada um dos quantificadores:
(∀ x) (∃ y) (P(x, y)).
Alcance de ∀: (∃ y) (P(x, y)).
Alcance de ∃: P(x, y).
Como se identifica uma variaável livre? E uma variável ligada?
Se estiver no alcançe de um qualquer quantificador então essa variável diz-se ligada, se não é livre.
Exemplos
1) ∀ x (P(x, y)); —-> x é ligado, y é livre
2) ∀ x (P(x, y) ∨ ∀ y (Q(y)));; —-> x é ligado, y é ligado e livre
3) ∀ x (P(x)) ⇒ Q(x).; —-> x é ligado e livre
Quais são as fórmulas que não podem ser avaliadas?
Fórmulas com variáveis livres.
A menos que se introduza uma função que atribui valores no domínio D às variáveis livres.
O que é necessário para que uma fórmula seja consederada válida/inválida?
Uma fórmula F diz-se válida (ou uma tautologia) se é
verdadeira para qualquer das suas possíveis interpretações e diz-se não válida (ou inválida) se não é válida.
Exemplo
A fórmula (∀ x) (P(x) ⇒ P(x)) é válida.
O que é necessário para que uma fórmula seja consederada consistente/inconsistente?
Uma fórmula F diz-se inconsistente (ou uma contradição) se é falsa qualquer que seja a sua interpretação e diz-se consistente se não é inconsistente.
Exemplo
A fórmula (∃x) (P(x) ∧ ¬(P(x))) é inconsistente.
O que constata o teorema da consequência lógica?
Dadas fórmulas F1(…) e uma fórmula G, a fórmula G é consequência lógica de F1(….) se e só se:
(F1 ∧ F2 ∧ F3 · · · ∧ Fn) ⇒ G
for uma fórmula válida, ou seja, uma tautologia.
Que condições são precisas para que uma fórmula esteja na forma normal prenex?
Se estiver na seguinte forma:
(Q1x1)(Q2x2) … (Qnxn) M
Ou seja, todos os quantificadores à esquerda da fórmula em si, dada por M.
Exemplos: (∀x)(∀y)(P(x, y) ∧ Q(y)); (∀x)(∀y)(¬P(x, y) ∨ Q(y)); (∀x)(∀y)(∃z)(Q(x, y) ∨ R(z)); (∀x)(∀y)(∃z)(Q(x, y) ⇒ R(z)).
Qual é a definição de literal?
Um literal é um átomo ou a negação de um átomo.
Dois literais dizem-se complementares quando um é a negação do outro.
Qual é a condição para que uma fórmula esteja na fórmula normal conjuntiva?
Seja uma conjunção de fórmulas. ∧
P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q
Qual é a condição para que uma fórmula esteja na fórmula normal dijuntiva?
Seja uma dijunção de fórmulas. ∨
P ∧ R) ∨ (¬P ∧ Q
O que é uma cláusula?
É uma dijunção (∨) de um conjunto de literais (átomos) finitos:
P(x) ∨ Q(a) ∨ ¬R(y)
¬P(x, f(x)) ∨ Q(x, f(x), g(x))
Ligação entre o conjunto de cláusulas e a forma normal conjuntiva?
O conjunto de cláusulas
S = {¬P(x, f(x)) ∨ Q(x, f(x), g(x)), T(x, f(x)), R(y)}
corresponde à fórmula (na forma normal conjuntiva)
(¬P(x, f(x)) ∨ Q(x, f(x), g(x))) ∧ T(x, f(x)) ∧ R(y).
Quais são as condições para que uma fórmula esteja na forma normal de Skolem?
É uma conjunção de cláusulas (dijunção (∨) de um conjunto de literais) universalmente quantificadas, ou seja,
sem variáveis livres e sem quantificadores existenciais.
Exemplos:
∀x∀y(P(x) ∨ ¬Q(a, y))
∀y∀z(¬Q(g(y, f(z))) ∨ ¬P(b))
Como se procede à redução de fórmulas normais prenex à fórmula normal de Skolem de modo a que possam ser demonstrados Teoremas?
(∀x)(∃y)(∃z)((¬P(x, y) ∨ Q(x, z))
(∀x)(∃y)(∃z)((¬P(x, y) ∨ Q(x, z))
• Uma vez que (∃y) e (∃z) são precedidos por (∀x), as
variáveis y e z são substituídas, respectivamente, pelas
funções de uma variável f(x) e g(x).
• Logo, obtém-se
(∀x)((¬P(x, f(x)) ∨ Q(x, g(x))).
Como se procede, usando o princípio de Robinson, à resolução de problemas?
Está no slide 5 do LPO4 o exemplo.
Exemplo de substituição de variaveis?
Está no slide 4 da LPO5
Exemplo da aplicação do unificador mais geral?
Está no último slide da LPO5
Qual é a definição de factor?
Dado o unificador mais geral (σ) de uma cláusula C, então o factor de C é Cσ
Exemplo:
C = P(x) ∨ P(f(y)) ∨ Q(x)
σ = {f(y)/x}.
Então
Cσ = P(f(y)) ∨ Q(f(y))
é um factor de C.
Qual é a definição de resolvente binária dadas duas cláusulas?
Dadas duas cláusulas (dijunção (∨) de um conjunto de literais (átomos)) que não tenham variável em comum.
E dois literais, onde L1 e ¬L2 têm o mesmo u.m.g então a seguinte expressão é a resolvente binária das duas cláusulas:
(C1σ − L1σ) ∪ (C2σ − L2σ)
Exemplo:
C1 : P(x) ∨ Q(x); C2 : ¬P(a) ∨ R(y)
L1 : P(x); ¬L2 : P(a)
σ = {a/x}
(C1σ − L1σ) ∪ (C2σ − L2σ) = Q(a) ∨ R(y)
Logo, Q(a) ∨ R(y) é a resolvente binária de C1 e C2.
Se existe uma bijeção entre dois conjuntos o que se pode concluir face à sua cardinalidade?
Que são iguais.
