(a) Defina uma fórmula
, tal que
seja satisfazível e
seja válida.
(b) Defina uma fórmula
, tal que
seja satisfazível e
não seja válida.
© Responda, justificando sua resposta, se a afirmação a seguir é verdadeira ou não:
Dada uma fórmula
, então
é satisfazível se, e somente se,
é válida.
(b) Defina uma fórmula
© Responda, justificando sua resposta, se a afirmação a seguir é verdadeira ou não:
Dada uma fórmula
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 é
, que é válido em todos os modelos (o domínio em FO é sempre não-vazio), logo
é 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
não é válido, pois existe um modelo (aquele em que
) em que
é falso.
Passo 4
Para ©, a afirmação “H é satisfazível se, e somente se,
é válida” é falsa. De fato, se
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
é válida.
(b) Uma escolha possível é G(x) = P(x). G é satisfazível mas não é válida.
© A afirmação é falsa: de válido segue H satisfazível, mas não o inverso.
(b) Uma escolha possível é G(x) = P(x). G é satisfazível mas
© A afirmação é falsa: de