(a) Defina uma fórmula H, tal que H seja satisfazível e (exists *) H seja válida.
(b) Defina uma fórmula G, tal que G seja satisfazível e (exists *) G não seja válida.
© Responda, justificando sua resposta, se a afirmação a seguir é verdadeira ou não:
Dada uma fórmula H, então H é satisfazível se, e somente se, (exists *) H é válida.

Passo 1

A questão trata de fórmulas de primeira-ordem com variáveis livres e seu fechamento existencial. Precisamos usar os conceitos de satisfatibilidade (existe um modelo e uma atribuição que tornam a fórmula verdadeira) e validade (em todo modelo a fórmula é verdadeira).

Passo 2

Para (a), podemos escolher a fórmula H com uma única variável livre, por exemplo H(x) = (x = x). Essa H é satisfazível porque em qualquer modelo, basta atribuir qualquer elemento de domínio a x para que x = x seja verdadeiro. O fechamento existencial é exists x, (x = x), que é válido em todos os modelos (o domínio em FO é sempre não-vazio), logo (exists *) H é válido.

Passo 3

Para (b), escolhemos G(x) = P(x), onde P é um predicado unário. Essa G é satisfazível porque podemos construir um modelo em que P interprete um conjunto não vazio e atribuir a x um elemento desse conjunto. Porém, o fechamento existencial exists x, P(x) não é válido, pois existe um modelo (aquele em que P^M=varnothing) em que exists x, P(x) é falso.

Passo 4

Para ©, a afirmação “H é satisfazível se, e somente se, (exists *)H é válida” é falsa. De fato, se (exists *)H for válido, então em particular existe algum modelo e atribuição que satisfaçam H, de modo que H é satisfazível. Mas o exemplo de (b) mostra que H (como P(x)) pode ser satisfazível sem que seu fechamento existencial seja válido. Portanto, só vale a implicação válida ⇒ satisfatível, não o inverso.

Resposta

(a) Uma escolha possível é H(x) = (x = x). H é satisfazível e exists x,(x = x) é válida.
(b) Uma escolha possível é G(x) = P(x). G é satisfazível mas exists x, P(x) não é válida.
© A afirmação é falsa: de (exists *)H válido segue H satisfazível, mas não o inverso.

Exercícios relacionados