Formas normais

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1512 palavras )
  • Download(s) : 0
  • Publicado : 5 de abril de 2011
Ler documento completo
Amostra do texto
SUMÁRIO

SUMÁRIO ............................................................................................................. 1
1. FORMAS NORMAIS ........................................................................................ 2
2. FORMA NORMAL CONJUNTIVA .................................................................. 3
3. TRANSFORMAÇÃO EM FORMA NORMAL CONJUNTIVA EM ÁTOMOS NOVOS.................................................................................................................................. 4
4. FORMA NORMAL DISJUNTIVA ..................................................................... 5
5. TRANSFORMAÇÃO EM FORMA NORMAL DISJUNTIVA EM ÁTOMOS NOVOS.................................................................................................................................. 9
6. REFERENCIAS BIBLIOGRÁFICAS ............................................................... 10



1 FORMAS NORMAIS

Uma fórmula normal são as fórmulas da lógica proposicional apresentadas num formato definido, ou seja, são fórmulas que são moldadas para serem exibidas em um formato definido. Sendo duas as principais formas normais: FNC – forma normal conjuntivae a FND– forma normal disjuntiva.

Exemplos:

1º Exemplo: H = (¬P Λ Q) V (¬R Λ ¬Q Λ P) V (P Λ S) – forma normal disjuntiva (V)

2º Exemplo: G = (¬P V Q)Λ (¬R V ¬Q V P)Λ (P V S) – forma normal conjuntiva (Λ)

2 FORMA NORMAL CONJUNTIVA

A Forma normal conjuntiva é empregada no método de inferência chamado de resolução, que serve a programação lógica.

O elemento básico da forma normalconjuntiva é o literal que é uma fórmula atômica (por exemplo: p, chamado de positivo) ou sua negação (como exemplo: ¬p, chamado de negativo).

Exemplos:

1º Exemplo: (¬p V Y) Λ (¬p V Z) Λ (¬Y V ¬Z V p)

Onde n é o tamanho da cláusula, se n = 1, a cláusula é dita unitária, se n = 0, é dita vazia, neste caso, convenciona-se que uma cláusula vazia é dita falsa .

Uma cláusula: ¬q1 V ... V¬qk V p1 V ... V p1, pode ser reescrita na forma implicativa:
(q1 Λ ... Λ qk) → (p1 V ... V p1)

Quando em uma fórmula a negação só pode estar aplicada aos átomos, ela é dita Forma Normal de Negação, isto significa que não pode haver uma negação de uma cláusula, a negação deve ser empurrada para os átomos, conforme a lei De Morgan.

3 TRANSFORMAÇÃO DE UMA FORMA NORMAL CONUNTIVA SEM ÁTOMOSNOVOS

Entrada: Uma fórmula B.

Saída: Uma fórmula A na FNC, B A2.

1. Para todas as sub-fórmulas X, Y, Z de B faça

2. Redefinir “” em termos de “V” e “¬”:

(X  Y)  (¬X V Y)

3. Empurrar as negações para o interior por meio das leis De Morgan.

¬ (X V Y)  ¬XΛ¬Y
¬ (X Λ Y)  ¬X V ¬Y

4. Eliminação da dupla negação:

¬¬  X X

5. Distributividade de V sobre Λ:

X V (Y ΛZ)  (X V Y) Λ (X V Z)
6. Fim para

7. A fórmula A é obtida quando não há mais substituições possíveis.

Apesar de gerar uma fórmula normal conjuntiva, ele pode gerar fórmulas exponencialmente maiores que a fórmula de entrada. O problema esta no passo 5 da distributividade, que causa a duplicação da sub-fórmula X, que por sua vez pode ser no formato (X1 ΛX2), que poderá gerar uma novaduplicação.

4 FORMA NORMAL DISJUNTIVA
Na lógica booleana, uma forma normal disjuntiva é uma normalização de uma fórmula lógica no qual temos uma disjunção de conjunções de literais.
Uma conjunção de literais disjuntivos tem a forma de:
A1Λ A2 Λ... Λ An
Podemos encontrar na forma de polinômios, em que a conjunção é representada pela multiplicação (*), e a disjunção pela adição (+) e a negaçãopor uma barra sobre o átomo (Ū), por exemplo, a fórmula (¬p1Λ p2) V (p1Λ¬p2) pode ser expresso em notação matemática da seguinte forma:
Ū1U2 + Ū1U2
Toda fórmula proposicional podemos transformar em uma forma do tipo disjuntiva para isso podemos usar meios como as Lei da Dupla Negação, as Leis de De Morgan, e a distributividade de átomos.
A disjunção entre duas fórmulas só é verdadeira...
tracking img