Árvores Semânticas
Componentes: Lucas, Ítalo, Wagner, Newton e Gabriel
 Validade
de uma fórmula a partir de uma
estrutura denominada árvore.
 Árvore é um conjunto de nós (vértices)
ligados por arestas.
 Os nós finais são chamados “folhas”.
 O nó inicial é denominado “raiz”.
Durante a validação, as arestas que ligam o
nó raiz aos outros nós recebem um rótulo,
indicando os possíveis valores de uma
determinada variável proposicional,
escolhida aleatoriamente. Se a partir de
uma interpretação for possível obter o valor
da fórmula, este é associado ao nó folha
correspondente.

Encontrar uma prova para um conjunto de
cláusulas S é gerar uma árvore semântica
fechada!

Árvores semânticas completas contém
todas as possibilidades.

Mas, se S é insatisfatível, uma árvore
semântica sobre H é fechada e finita!
Considere S = {P(x), P(a)}. O conjunto de
átomos de S é {P(a)}.
Considere S = {P(x), Q(f(x))}.
O conjunto de átomos de S é:
A = {P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),
Q(f(f(a))), ...}


S = {P, Q v R, P v Q, P v R}
B = {P, Q, R}.


S = {P(x),
P(x) v Q(f(x)),
Q(f(a))}
B = {P(a), Q(a),
P(f(a)), Q(f(a)), ...}


Haverá algum barbeiro que barbeia toda a
gente da cidade(1), mas somente aqueles que
não se barbeiam a si próprios(2)?
O paradoxo surge quando tentamos saber se
o barbeiro faz a própria barba ou não. Se ele
o faz, não poderá, pois violaria a condição 2;
mas se não fizer a própria barba, então tem
de fazer, pois esta é a condição 1.
Conclusão: O argumento “Haverá algum
barbeiro que barbeia toda a gente da cidade,
mas somente aqueles que não se barbeiam a
si próprios?” É inconsistente pois a arvore
esta terminada e os seus ramos ainda estão
abertos. Como esta é uma demonstração por
redução ao absurdo, estando a arvore aberta,
não há contradição em nenhum dos seus
ramos.