R graficos

Sistema dedutivo de Resolução Proposicional

Este sistema dedutivo não usa a linguagem proposicional vista anteriormente, mas uma que é equivalente a essa. As fórmulas deste sistema são chamadas cláusulas, e cada cláusula corresponde a uma fórmula proposicional. Antes de apresentarmos a linguagem vamos a algumas definições sobre literais.

Definições
Um literal positivo é uma fórmula atômica.
Um literal negativo é uma fórmula que é a negação de uma fórmula atômica (e.g. P).
Dado um literal L (P ou P, para algum P), denotamos por |L|, a fórmula atômica que ocorre em L (P).
Dois literais tem sinais opostos sse um deles for positivo e o outro for negativo.
O complemento de um literal L, denotado por L, é o literal L' de sinal oposto a L tal que |L'| =|L|. Neste caso dizemos que L' e L são complementares.

Linguagem das cláusulas
Alfabeto:
Símbolos lógicos: negação )
Símbolos não lógicos: símbolos sentenciais (ou proposicionais ) e .
Um a cláusula sobre um alfabeto A é:
- uma seqüência não vazia de literais usando os símbolos de A ou - a seqüência vazia de literais , denotada por .

A linguagem das cláusulas sobre um alfabeto A é o conjunto de todas as cláusulas sobre A.

1. Obs. 1: Se não for explicitado, tomaremos como alfabeto de um conjunto de cláusulas  o alfabeto cujos símbolos não-lógicos são aqueles que ocorrem em .

Obs. 2: Ao manipularmos formalmente uma cláusula não vazia L1 L2..Ln na regra de inferência resolução, trataremos a cláusula como se fosse o conjunto { L1, L2,..Ln }. Daí usaremos a notação de conjuntos e de cláusulas indistintamente (e.g. usaremos ( - L) para denotar a cláusula obtida pela exclusão do literal L da cláusula .

Semântica

A semântica da linguagem das cláusulas proposicionais é dada através de correspondência das cláusulas com fórmulas proposicionais.
Uma cláusula não vazia L1L2...Ln é interpretada semanticamente como a fórmula  L1L2...Ln). Dizemos que a fórmula L1L2...Ln é a