Suponha que tem o seguinte conjunto de cláusulas: CNF={{ -1, 2}, {-1, 2, -3}, {-2}, {2, -3}, {2, 3}, {-2, -3}} Aplique o DPLL, de modo a verificar se o conjunto de cláusulas pode ser satisfeito.

Resumo da Resposta

O conjunto de cláusulas fornecido é insatisfatível (UNSAT). Ao aplicar as regras de propagação de unidades do algoritmo DPLL, surge imediatamente uma contradição na atribuição da variável x_3.

Análise Detalhada

Introdução

O algoritmo DPLL (Davis-Putnam-Logemann-Loveland) é utilizado para determinar a satisfatibilidade de fórmulas lógicas na Forma Normal Conjuntiva (CNF). Ele opera através de três etapas principais: eliminação de literais puros, propagação de unidades e divisão (backtracking). Neste caso, utilizaremos a propagação de unidades para simplificar o conjunto até encontrar uma solução ou uma contradição.

Desenvolvimento dos Passos

Primeiro, organizamos o conjunto de cláusulas inicial:

1. C_1 = \{-1, 2\}
2. C_2 = \{-1, 2, -3\}
3. C_3 = \{-2\}
4. C_4 = \{2, -3\}
5. C_5 = \{2, 3\}
6. C_6 = \{-2, -3\}

Passo 1: Identificação de Cláusula Unidade

Observamos que a cláusula C_3 contém apenas um literal: \{-2\}.

• Isso força a atribuição x_2 = \text{False} (ou seja, o literal -2 deve ser verdadeiro).
• Aplicamos a substituição no conjunto restante.

Passo 2: Simplificação das Cláusulas

Com x_2 = \text{False}:

• Literais positivos de $2$ são removidos das cláusulas.
• Literais negativos de -2 satisfazem as cláusulas (elas são removidas).

Atualização das cláusulas:

• C_1 (\{-1, 2\}) \Rightarrow \{-1\} (Unidade encontrada)
• C_2 (\{-1, 2, -3\}) \Rightarrow \{-1, -3\}
• C_3 (\{-2\}) \Rightarrow \text{Removida (satisfeita)}
• C_4 (\{2, -3\}) \Rightarrow \{-3\} (Unidade encontrada)
• C_5 (\{2, 3\}) \Rightarrow \{3\} (Unidade encontrada)
• C_6 (\{-2, -3\}) \Rightarrow \text{Removida (satisfeita)}

Passo 3: Detecção de Contradição

Após a primeira propagação, restam as seguintes cláusulas ativas relevantes:

• \{-1\}
• \{-1, -3\}
• \{-3\}
• \{3\}

Observamos agora duas novas cláusulas unidade:

1. \{-3\} exige que x_3 = \text{False}.
2. \{3\} exige que x_3 = \text{True}.

É impossível satisfazer ambas simultaneamente. Quando o algoritmo tenta atribuir valores para resolver \{-3\}, ele viola a exigência de \{3\}.

Conclusão

A aplicação do algoritmo DPLL revela uma inconsistência lógica direta entre as cláusulas simplificadas. Não existe nenhuma atribuição de verdade para as variáveis x_1, x_2, x_3 que satisfaça todas as cláusulas ao mesmo tempo. Portanto, o conjunto é inviável.