Considere a seguinte fórmula proposicional no formato clausal:
Se aplicarmos unit propagation a essa fórmula, quais das seguintes cláusulas permanecerão na fórmula resultante após a propagação?
a)
b)
c)
d)
e)
a)
b)
c)
d)
e)
Passo 1
O enunciado nos dá a fórmula clausal
e pede para aplicar unit propagation. Vamos usar que, sempre que temos uma cláusula unitária
, atribuímos
, eliminamos todas as cláusulas que contêm
e removemos de cada cláusula restante todas as ocorrências de
.
Passo 2
Identificamos a cláusula unitária
. Logo atribuímos
Agora simplificamos a fórmula:
- Qualquer cláusula que contenha
é satisfeita e, portanto, removida. - Em qualquer cláusula que contenha
, removemos esse literal.
Das cláusulas originais:
perde
e vira
.
é satisfeita por
e some.
some por estar satisfeita.
As demais não contêm nem nem
e ficam inalteradas.
As demais não contêm nem
Passo 3
Após essa propagação obtemos a fórmula simplificada
Passo 4
Procuramos novas cláusulas unitárias: todas têm dois ou mais literais. Logo o processo para aqui.
Resposta
As cláusulas que permanecem (entre as da lista de alternativas) são:
a)
b)
e)
a)
b)
e)