1º Teste Flashcards
O que é um termo? Exemplos
Uma variável pode ser um termo. (x,y,z…)
Uma constante pode ser um termo. (a,b,c…)
Dada uma função F que aceita termos como argumentos, isto é:
F(t1), então conclui-se que F(t1) na sua totalidade também é um termo.
O que é um predicado?
É uma função que tendo um domínio de constantes faz corresponder um valor lógico, ou seja, verdadeiro ou falso.
Exemplo:
maior(x,y) => x é maior que y
O que é um átomo?
Se P for um predicado, ou seja, uma função que aceita constantes e retorna um valor lógico, com n argumentos, os quais são termos, então:
P(t1,t2,…,tn) é um átomo.
No seguinte exemplo qual é 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 caracteriza uma variável livre?
Se uma dada variável estiver fora do alcançe de um quantificador, quer seja, ele existêncial ou universal. a variável diz-se livre.
Como se caracteriza uma variável ligada?
Uma variável ligada é uma variável que está dentro do alcançe de um quantificador.
O que é uma forma válida?
É uma tautologia.
Como é que sabemos se uma fórmula está na forma normal prenex?
Quando temos os quantificadores todos à esquerda de uma fórmula sem quantificadores.
Exemplo:
(∀x)(∀y)(P(x, y) ∧ Q(y));
O que é um literal?
É um átomo ou a negação de um átomo.
Um átomo é um predicado, ou seja, uma função que aceita variáveis e retorna valores lógicos, que tem n termos como argumentos.
Logo um literal é a negação disso mesmo.
Como é que sabemos se uma fórmula está na forma normal conjuntiva?
Se for uma fórmula composta pela conjunção de literais.
Ex:
P ∨ ¬Q ∨ R) ∧ (¬P ∨ Q
Como é que sabemos se uma fórmula está na forma normal dijuntiva?
Se for uma fórmula composta pela dijunção de literais.
Ex:
P ∧ R) ∨ (¬P ∧ Q
O que é uma cláusula?
Uma r-cláusula é uma dijunção finita de r literais:
P(x) ∨ Q(a) ∨ ¬R(y);
Quando é que uma fórmula se diz na forma normal de Skolem?
Se for uma conjunção de cláusulas universalmente quantificadas, ou seja, sem variáveis livres e sem quantificadores existênciais:
∀x∀y(P(x) ∨ ¬Q(a, y))
∀y∀z(¬Q(g(y, f(z))) ∨ ¬P(b))
Passos a tomar para reduzir esta fórmula à forma normal de Skolem?
(∀x)(∃y)(∃z)((¬P(x, y) ∨ Q(x, z))
Como na forma normal de Skolem só podem existir quantificadores universais temos de nos livrar dos quantificadores existênciais, neste caso, (∃y)(∃z).
Como estes quantificadores existênciais precedem o quantificador uniersal o que fazemos é substitui cada um deles por uma função:
(∀x)((¬P(x, f(x)) ∨ Q(x, g(x)))
Se nenhum quantificador universal aparecer à esquerda de um quantificador existêncial que passos devemos tomar para eliminar esse quantificador existêncial?
Escolhemos uma constante que não apareça na fórmula à qual estão associados os quantificadores.
Agora vemos qual é a variável que está associada ao quantificador existêncial e vamos substituir. na fórmula, em si, pela constante e assim eliminamos o quantificador.
O que são classes de equivalência?
São conjuntos de elementos de A que cumprem esta condição:
Pertencem a A, e existe uma dada relação que está incluída em A, tiramos um elemento de A e vamos descobrir a sua classe de equivalência.
Depois vamos escolher outro elemento de A, diferente do 1º e depois vamos ver se esse par ordenado de (X,Y) pertence à relação.
O que é o conjunto quociente?
É o conjunto de todas as classes de equivalência.
O que é que se pode concluir se R é uma relação de equivalência definida em A?
Se R é uma relação de equivalência em A, então o conjunto quociente de A é uma partição de A.
O que torna uma função injetiva?
f(x) = f(y) ⇒ x = y
Para qualquer x e y pertencentes ao domínio de f.
O que torna uma função subjetiva?
É sobrejetiva se para todo y ∈ ao contradomínio existe x ∈ domínio tal que f(x) = y;
Como se desenvolve g(x) após f(x)?
g ◦ f(x) = g(f(x))
