leis algebricas

Prévia do material em texto

15/04/2024
1
Lógica Proposicional
Propriedades Algébricas 
Lógica proposicional como álgebra 
• George Boole e Augustus De Morgan conseguiram relacionar 
a lógica com a álgebra. 
• Publicaram os fundamentos da chamada Álgebra Booleana, 
que utiliza símbolos e operações algébricas para representar 
proposições e suas relações.
nmb
• As ideias de Boole tornaram-se a base da 
Lógica Simbólica, cuja aplicação estende-se 
por alguns ramos da eletricidade, da 
eletrônica e da computação.
nmb
Lógica proposicional como álgebra
A prova da equivalência de fórmulas por meio do 
método da tabela-verdade é inadequado (muito 
trabalhoso) quando tem-se muitos símbolos 
proposicionais (2n).
• As leis algébricas são importantes para provar a 
equivalência de fórmulas da lógica proposicional.
nmb
Exemplo
Resolva a fórmula usando o método da tabela-
verdade e escreva se a relação de equivalência (
) lógica se verifica.
1. ~( Q v P )  ~Q ^ ~P 
1. P  Q  ~P v Q
nmb
Exemplo
1. (~P v ~R) ^ (Q  ~R) ^ ( R → Q) ^ (~P v R )  ???
1. (~P v Q) ^ (S  ~R v ~P) ^ ((P ^ R) → S)  ???
Fica bastante extenso para resolver por tabela verdade, 
não é mesmo (principalmente na 2) ?
Por isso outros métodos (diferentes da tabela verdade) 
podem ser utilizados.
A equivalência por meio das Leis Algébricas é um 
facilitador.
Exemplo
• a) R v ( ~P → ~Q )
• b) ~(R v P) → ~Q
nmb
15/04/2024
2
Leis Algébricas
• Álgebra Proposicional
Lei Conectivo ̂ (conjunção) Conectivo v (disjunção)
Identidade P ^ V  P P v V  V
Identidade P ^ F  F P v F  P
Idempotente P ^ P  P P v P  P
Complemento P ^ ~P  F P v ~P  V
Comutativa P ^ Q  Q ^ P P v Q  Q v P
nmb
Leis Algébricas
• Álgebra Proposicional
Lei Conectivo ̂ (conjunção) Conectivo v (disjunção)
Associativa P ^ (Q ^ R)  (P ^ Q) ^ R P v (Q v R)  (P v Q) v R
Distributiva P ^ (Q v R)(P ̂ Q) v (P ^ R) P v (Q ^ R)(P v Q) ^ (P v R)
De Morgan ~(P ^ Q)  ~P v ~Q ~(P v Q)  ~P ^ ~Q
Absorção 1 (P v Q) ^ Q  Q (P ^ Q) v Q  Q
Absorção 2 (P v Q) ^ ~Q  P ^ ~Q (P ^ Q) v ~Q  P v ~Q
nmb
Leis Algébricas
• Álgebra Proposicional
Lei
Complemento ~V  F
Complemento ~F  V
Dupla Negação ~(~P)  P
Implicação P  Q  ~P v Q
Equivalência P Q  (P  Q) ^ (Q  P)
Contrapositiva P  Q  ~Q  ~P
nmb
Distributiva: P ^ (Q v R)(P ̂ Q) v (P ^ R)
P ^ (Q v R) (P ^ Q) v (P ̂R)
P Q R Q v R P ^ (Q v R) (P ̂Q) (P ̂R) (P ̂Q) v (P ̂R)
V V V V V V V V
V V F V V V F V
V F V V V F V V
V F F F F F F F
F V V V F F F F
F V F V F F F F
F F V V F F F F
F F F F F F F F
nmb
De Morgan: ~(P ̂ Q) ~P v ~Q Implicação: P --> Q ~P v Q
~(P ^ Q) ~P v ~Q P --> Q ~P v Q
P Q P ̂ Q ~(P ^ Q) ~P ~Q ~P v ~Q P Q P --> Q ~P ~P v Q
V V V F F F F V V V F V
V F F V F V V V F F F F
F V F V V F V F V V V V
F F F V V V V F F V V V
nmb
Dicas
• Continuar até que não ser mais possível reduzir 
a fórmula;
• Nas regras P, Q, R, ..., são figurativos;
• Sempre manter os ( ) o máximo possível;
• Complemento: P v ~P = V; P ^ ~P = F 
• Identidade: P ^ VP P v VV P ^ FF P v FPnmb