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.
