Relações Semânticas entre os Conectivos da Lógica Proposicional

Relações Semânticas entre os Conectivos da Lógica Proposicional

Conjunto de Conectivos Completos

Seja X um conjunto de conectivos.

        X é um conjunto completo se as condições a seguir são satisfeitas.

        Dada uma fórmula H do tipo

        ¬P˘, (P˘1 ∨ P˘2), (P˘1 ∧ P˘2),

             (P˘1 → P˘2) ou (P˘1 ↔ P˘2),

        Então é possível determinar uma outra fórmula G, tal que:

G é equivalente a H, G contém apenas conectivos do conjunto X e os símbolos P˘1 e P˘2 presentes em H.

Equivalência entre → e os conectivos ¬ e v

O conectivo → pode ser expressado semanticamente pelos conectivos ¬ e v.

Ou seja, (P → Q) equivale a (¬P v Q)

Equivalência entre ^ e os conectivos ¬ e v

O conectivo ^ pode ser expressado semanticamente pelos conectivos ¬ e v.

Ou seja, (P ^ Q) equivale a ¬ (¬P v Q)

Equivalência entre ↔ e os conectivos ¬ e v

O conectivo ↔ pode ser expressado semanticamente pelos conectivos ¬ e v.

Ou seja, (P ↔ Q) equivale a ¬ (¬ (¬P v Q) v ¬ (¬Q v P))

Regra de Substituição

Sejam Eg, Eh, G e H fórmulas da Lógica Proposicional tais que:

G e H são subfórmulas de Eg e Eh respectivamente.

Eh é obtida de Eg substituindo todas as ocorrências da fórmula G em Eg por H.

Se G equivale a H, então Eg equivale a Eh.

Relação Semântica entre Conectivos(nand)

Seja K uma fórmula da Lógica Proposicional.

Então existe uma fórmula K1, equivalente a K que possui apenas os conectivos ¬ e ∨ e os símbolos proposicionais e de verdade presentes em K.

Conectivo NAND

Ele é definido pela correspondência:

(P nand Q) = (¬(P ^ Q)

O conjunto NAND é completo.

Equivalências:

Entre ¬ e {nand}

¬P equivale a (P nand P)

Entre v e {nand}

(P v Q) equivale a (P nand P) nand (Q nand Q)

Conclusão:

Seja K uma fórmula qualquer da Lógica Proposicional. K pode ser expressa, equivalentemente, utilizando apenas o conectivo nand e os símbolos proposicionais e de verdade presentes em K.

Relação Semântica entre Conectivos(nor)

Seja W uma fórmula qualquer da Lógica Proposicional. W pode ser expressa, equivalentemente, utilizando apenas o conectivo nor e os símbolos proposicionais e de verdade presentes em W.

Conectivo NOR

Ele é definido pela correspondência:

(P nor Q) = (¬(P v Q)

Exemplos destas Relações utilizando as Formas Normais Conjuntivas e Disjuntiva 

Normal Conjuntiva:

(¬Q ^ R)

(¬R v S)

Normal Disjuntiva:

(P nand Q)

(R nor S)

Tableaux Semântico

É a regra que mais se aproxima da linguagem computacional.

Possui 3 elementos principais:

Alfabeto Proposicional – A,B,C,D, P,Q,R,S ou qualquer outra letra de nosso alfabeto.

Conjunto das fórmulas

Conjunto de Regras de dedução – Este se divide em 9 regras.

Regras:

1 – X ^ Y – X e Y    

          X

          Y

2 – X v Y -  X ou Y

      ↓  ↓

      X        Y

3 – X → Y – X implica Y

       ↓ ↓

     ¬X   Y

4- X ↔ Y – Se Somente se

    ↓      ↓

X ^ Y  ¬A ^ ¬B

5- ¬¬X – Negação Dupla de X – volta ao seu estado original

      ↓

      X

6 - ¬(X ^ Y) – Negação de X e Y – Nega toda a sentença

        ↓   ↓

      ¬X   ¬Y        

7 - ¬(X v Y) – Negação de X ou Y – Nega os elementos

           ¬X    

           ¬Y

8 - ¬(X → Y) – Negação de Implica

        X

           ¬Y

9- ¬(X ↔ Y) – Negação de Se somente se – Pode gerar mais traços dependendo do caso

...