Propriedades e Leis de Morgan

Prévia do material em texto

Propriedades e 
Leis de Morgan
Matemática Discreta
Carlos Antonio Fragoso
Propriedades
Idempotente
Comutativa
Associativa
Distributiva
Propriedade Idempotente
^ (Conjunção, E) 			P ^ P = P
v (Disjunção, OU)			P v P = P
v (Disjunção Exclusiva, XOR)	P v P ≠ P
	P	P ^ P	P v P	P v P
	V	V ^ V = V	V v V = V	V v V = F
	F	F ^ F = F	F v F = F	F v F = F
	P	P → P	P ↔ P
	V	V → V = V	V ↔ V = V
	F	F → F = V	F ↔ F = V
Propriedade Comutativa
 ^ (Conjunção E)
 V (Disjunção OU)		 V (Disjunção Exclusiva, OU EXCLUSIVO, XOR)
	P	Q	P ^ Q	Q ^ P
	V	V	V	V
	V	F	F	F
	F	V	F	F
	F	F	F	F
	P	Q	P v Q	Q v P
	V	V	V	V
	V	F	V	V
	F	V	V	V
	F	F	F	F
	P	Q	P v Q	Q v P
	V	V	F	F
	V	F	V	V
	F	V	V	V
	F	F	F	F
P ^ Q = Q ^ P
P v Q = Q v P
P v Q = Q v P
	P	Q	P → Q	Q → P
	V	V	V	V
	V	F	F	V
	F	V	V	F
	F	F	V	V
	P	Q	P↔ Q	Q ↔P
	V	V	V	V
	V	F	F	F
	F	V	F	F
	F	F	V	V
Propriedade Associativa (^, E, Conjunção)
(P ^ Q) ^ R = P ^ (Q ^ R)
	P	Q	R	(P ^ Q) ^ R	P ^ (Q ^ R)
	V	V	V	(V) ^ V = V	V ^ (V) = V
	V	V	F	(V) ^ F = F	V ^ (F) = F
	V	F	V	(F) ^ V = F	V ^ (F) = F
	V	F	F	(F) ^ F = F	V ^ (F) = F
	F	V	V	(F) ^ V = F	F ^ (V) = F
	F	V	F	(F) ^ F = F	F ^ (F) = F
	F	F	V	(F) ^ V = F	F ^ (F) = F
	F	F	F	(F) ^ F = F	F ^ (F) = F
Propriedade Associativa (v, OU, Disjunção)
(P v Q) v R = P v (Q v R)
	P	Q	R	(P v Q) v R	P v (Q v R)
	V	V	V	(V) v V = V	V v (V) = V
	V	V	F	(V) v F = V	V v (V) = V
	V	F	V	(V) v V = V	V v (V) = V
	V	F	F	(V) v F = V	V v (F) = V
	F	V	V	(V) v V = V	F v (V) = V
	F	V	F	(V) v F = V	F v (V) = V
	F	F	V	(F) v V = V	F v (V) = V
	F	F	F	(F) v F = F	F v (F) = F
Propriedade Associativa (v, OU EXCLUSIVO, XOR, Disjunção Exclusiva)
(P v Q) v R = P v (Q v R)
	P	Q	R	(P v Q) v R	P v (Q v R)
	V	V	V	(F) v V = V	V v (F) = V
	V	V	F	(F) v F = F	V v (V) = F
	V	F	V	(V) v V = F	V v (V) = F
	V	F	F	(V) v F = V	V v (F) = V
	F	V	V	(V) v V = F	F v (F) = F
	F	V	F	(V) v F = V	F v (V) = V
	F	F	V	(F) v V = V	F v (V) = V
	F	F	F	(F) v F = F	F v (F) = F
Propriedade Associativa (Implicação Unidirecional, →) 
(P → Q) → R ≠ P → (Q → R)
	P	Q	R	(P → Q) → R	P → (Q → R)
	V	V	V	(V) → V = V	V → (V) = V 
	V	V	F	(V) → F = F	V → (F) = F
	V	F	V	(F) → V = V	V → (V) = V
	V	F	F	(F) → F = V	V → (V) = V
	F	V	V	(V) → V = V	F → (V) = V
	F	V	F	(V) → F = F	F → (F) = V
	F	F	V	(V) → V = V	F → (V) = V
	F	F	F	(V) → F = F	F → (V) = V
Propriedade Associativa (Implicação Bidirecional, ↔)
(P ↔ Q) ↔ R = P ↔ (Q ↔ R)
	P	Q	R	(P ↔ Q) ↔ R	P ↔ (Q ↔ R)
	V	V	V	(V) ↔ V = V	V ↔ (V) = V
	V	V	F	(V) ↔ F = F	V ↔ (F) = F
	V	F	V	(F) ↔ V = F	V ↔ (F) = F
	V	F	F	(F) ↔ F = V	V ↔ (V) = V
	F	V	V	(F) ↔ V = F	F ↔ (V) = F
	F	V	F	(F) ↔ F = V	F ↔ (F) = V
	F	F	V	(V) ↔ V = V	F ↔ (F) = V
	F	F	F	(V) ↔ F = F	F ↔ (V) = F
Propriedade Distributiva (^, E, Conjunção)
P ^ (Q ^ R) = (P ^Q) ^ (P ^ R)
	P	Q	R	P ^ (Q ^ R)	(P ^ Q) ^ (P ^ R)
	V	V	V	V ^ (V) = V	(V) ^ (V) = V 
	V	V	F	V ^ (F) = F	(V) ^ (F) = F
	V	F	V	V ^ (F) = F	(F) ^ (V) = F
	V	F	F	V ^ (F) = F	(F) ^ (F) = F
	F	V	V	F ^ (V) = F	(F) ^ (F) = F
	F	V	F	F ^ (F) = F	(F) ^ (F) = F
	F	F	V	F ^ (F) = F	(F) ^ (F) = F
	F	F	F	F ^ (F) = F	(F) ^ (F) = F
Propriedade Distributiva (v, OU, Disjunção)
P v (Q v R) = (P v Q) v (P v R)
	P	Q	R	P v (Q v R)	(P v Q) v (P v R)
	V	V	V	V v (V) = V	(V) v (V) = V 
	V	V	F	V v (V) = V	(V) v (V) = V
	V	F	V	V v (V) = V	(V) v (V) = V
	V	F	F	V v (F) = V	(V) v (V) = V
	F	V	V	F v (V) = V	(V) v (V) = V
	F	V	F	F v (V) = V	(V) v (F) = V
	F	F	V	F v (V) = V	(F) v (V) = V
	F	F	F	F v (F) = F	(F) v (F) = F
Propriedade Distributiva (v, OU EXCLUSIVO, XOR, Disjunção Exclusiva)
P v (Q v R) ≠ (P v Q) v (P v R)
	P	Q	R	P v (Q v R)	(P v Q) v (P v R)
	V	V	V	V v (F) = V	(F) v (F) = F
	V	V	F	V v (V) = F	(F) v (V) = V
	V	F	V	V v (V) = F	(V) v (F) = V
	V	F	F	V v (F) = V	(V) v (V) = F
	F	V	V	F v (F) = F	(V) v (V) = F
	F	V	F	F v (V) = V	(V) v (F) = V
	F	F	V	F v (V) = V	(F) v (V) = V
	F	F	F	F v (F) = F	(F) v (F) = F
Propriedade Distributiva (E em relação ao OU)
P ^ (Q v R) = (P ^ Q) v (P ^ R)
	P	Q	R	P ^ (Q v R)	(P ^ Q) v (P ^ R)
	V	V	V	V ^ (V) = V	(V) v (V) = V 
	V	V	F	V ^ (V) = V	(V) v (F) = V 
	V	F	V	V ^ (V) = V	(F) v (V) = V
	V	F	F	V ^ (F) = F	(F) v (F) = F
	F	V	V	F ^ (V) = F	(F) v (F) = F
	F	V	F	F ^ (V) = F	(F) v (F) = F
	F	F	V	F ^ (V) = F	(F) v (F) = F
	F	F	F	F ^ (F) = F	(F) v (F) = F
Propriedade Distributiva (E em relação ao XOR)
P ^ (Q v R) = (P ^ Q) v (P ^ R)
	P	Q	R	P ^ (Q v R)	(P ^ Q) v (P ^ R)
	V	V	V	V ^ (F) = F	(V) v (V) = F 
	V	V	F	V ^ (V) = V	(V) v (F) = V 
	V	F	V	V ^ (V) = V	(F) v (V) = V
	V	F	F	V ^ (F) = F	(F) v (F) = F
	F	V	V	F ^ (F) = F	(F) v (F) = F
	F	V	F	F ^ (V) = F	(F) v (F) = F
	F	F	V	F ^ (V) = F	(F) v (F) = F
	F	F	F	F ^ (F) = F	(F) v (F) = F
Propriedade Distributiva (E em relação ao →)
P ^ (Q → R) ≠ (P ^ Q) → (P ^ R)
	P	Q	R	P ^ (Q → R)	(P ^ Q) → (P ^ R)
	V	V	V	V ^ (V) = V	(V) → (V) = V
	V	V	F	V ^ (F) = F	(V) → (F) = F
	V	F	V	V ^ (V) = V	(F) → (V) = V
	V	F	F	V ^ (V) = V	(F) → (F) = V
	F	V	V	F ^ (V) = F	(F) → (F) = V
	F	V	F	F ^ (F) = F	(F) → (F) = V
	F	F	V	F ^ (V) = F	(F) → (F) = V
	F	F	F	F ^ (V) = F	(F) → (F) = V
Propriedade Distributiva (E em relação ao ↔)
P ^ (Q ↔ R) ≠ (P ^ Q) ↔ (P ^ R)
	P	Q	R	P ^ (Q ↔ R)	(P ^ Q) ↔ (P ^ R)
	V	V	V	V ^ (V) = V 	(V) ↔ (V) = V 
	V	V	F	V ^ (F) = F	(V) ↔ (F) = F
	V	F	V	V ^ (F) = F	(F) ↔ (V) = F
	V	F	F	V ^ (V) = V	(F) ↔ (F) = V
	F	V	V	F ^ (V) = F	(F) ↔ (F) = V
	F	V	F	F ^ (F) = F	(F) ↔ (F) = V
	F	F	V	F ^ (F) = F	(F) ↔ (F) = V 
	F	F	F	F ^ (V) = F	(F) ↔ (F) = V
Propriedade Distributiva (OU em relação ao E)
P v (Q ^ R) = (P v Q) ^ (P v R)
	P	Q	R	P v (Q ^ R)	(P v Q) ^ (P v R)
	V	V	V	V v (V) = V	(V) ^ (V) = V 
	V	V	F	V v (F) = V	(V) ^ (V) = V 
	V	F	V	V v (F) = V	(V) ^ (V) = V
	V	F	F	V v (F) = V	(V) ^ (V) = V
	F	V	V	F v (V) = V	(V) ^ (V) = V
	F	V	F	F v (F) = F	(V) ^ (F) = F
	F	F	V	F v (F) = F	(F) ^ (V) = F
	F	F	F	F v (F) = F	(F) ^ (F) = F
Propriedade Distributiva (OU em relação ao XOR)
P v (Q v R) ≠ (P v Q) v (P v R)
	P	Q	R	P v (Q v R)	(P v Q) v (P v R)
	V	V	V	V v (F) = V	(V) v (V) = F 
	V	V	F	V v (V) = V	(V) v (V) = F 
	V	F	V	V v (V) = V	(V) v (V) = F
	V	F	F	V v (F) = V	(V) v (V) = F
	F	V	V	F v (F) = F	(V) v (V) = F
	F	V	F	F v (V) = V	(V) v (F) = V
	F	F	V	F v (V) = V	(F) v (V) = V
	F	F	F	F v (F) = F	(F) v (F) = F
Propriedade Distributiva (OU em relação ao →)
P v (Q → R) = (P v Q) → (P v R)
	P	Q	R	P v (Q → R)	(P v Q) → (P v R)
	V	V	V	V v (V) = V	(V) → (V) = V
	V	V	F	V v (F) = V	(V) → (V) = V 
	V	F	V	V v (V) = V	(V) → (V) = V
	V	F	F	V v (V) = V	(V) → (V) = V
	F	V	V	F v (V) = V	(V) → (V) = V
	F	V	F	F v (F) = F	(V) → (F) = F
	F	F	V	F v (V) = V	(F) → (V) = V
	F	F	F	F v (V) = V	(F) → (F) = V
Propriedade Distributiva (OU em relação ao ↔)
P v (Q ↔ R) = (P v Q) ↔ (P v R)
	P	Q	R	P v (Q ↔ R)	(P v Q) ↔ (P v R)
	V	V	V	V v (V) = V	(V) ↔ (V) = V
	V	V	F	V v (F) = V	(V) ↔ (V) = V
	V	F	V	V v (F) = V	(V) ↔ (V) = V
	V	F	F	V v (V) = V	(V) ↔ (V) = V
	F	V	V	F v (V) = V	(V) ↔ (V) = V
	F	V	F	F v (F) = F	(V) ↔ (F) = F
	F	F	V	F v (F) = F	(F) ↔ (V) = F
	F	F	F	F v (V) = V	(F) ↔ (F) = V
Propriedade Distributiva (XOR em relação ao E)
P v (Q ^ R) ≠ (P v Q) ^ (P v R)		
	P	Q	R	P v (Q ^ R)	(P v Q) ^ (P v R)
	V	V	V	V v (V) = F	(F) ^ (F) = F 
	V	V	F	V v (F) = V	(F) ^ (V) = F
	V	F	V	V v (F) = V	(V) ^ (F) = F
	V	F	F	V v (F) = V	(V) ^ (V) = V
	F	V	V	F v (V) = V	(V) ^ (V) = V
	F	V	F	F v (F) = F	(V) ^ (F) = F
	F	F	V	F v (F) = F	(F) ^ (V) = F
	F	F	F	F v (F) = F	(F) ^ (F) = F
Propriedade Distributiva (XOR em relação ao OU)
P v (Q v R) ≠ (P v Q) v (P v R)		
	P	Q	R	P v (Q v R)	(P v Q) v (P v R)
	V	V	V	V v (V) = F	(F) v (F) = F 
	V	V	F	V v (V) = F	(F) v (V) = V
	V	F	V	V v (V) = F	(V) v (F) = V
	V	F	F	V v (F) = V	(V) v (V) = V
	F	V	V	F v (V) = V	(V) v (V) = V
	F	V	F	F v (V) = V	(V) v (F) = V
	F	F	V	F v (V) = V	(F) v (V) = V
	F	F	F	F v (F) = F	(F) v (F) = F
Propriedade Distributiva (XOR em relação ao →)
P v (Q → R) ≠ (P v Q) → (P v R)
	P	Q	R	P v (Q → R)	(P v Q) → (P v R)
	V	V	V	V v (V) = F	(F) → (F) = V
	V	V	F	V v (F) = V	(F) → (V) = V
	V	F	V	V v (V) = F	(V) → (F) = F
	V	F	F	V v (V) = F	(V) → (V) = V 
	F	V	V	F v (V) = V	(V) → (V) = V
	F	V	F	F v (F) = F	(V) → (F) = F
	F	F	V	F v (V) = V	(F) → (V) = V
	F	F	F	F v (V) = V	(F) → (F) = V
PropriedadeDistributiva (XOR em relação ao ↔)
P v (Q ↔ R) ≠ (P v Q) ↔ (P v R)
	P	Q	R	P v (Q ↔ R)	(P v Q) ↔ (P v R)
	V	V	V	V v (V) = F	(F) ↔ (F) = V 
	V	V	F	V v (F) = V	(F) ↔ (V) = F 
	V	F	V	V v (F) = V	(V) ↔ (F) = F
	V	F	F	V v (V) = F	(V) ↔ (V) = V
	F	V	V	F v (V) = V	(V) ↔ (V) = V
	F	V	F	F v (F) = F	(V) ↔ (F) = F
	F	F	V	F v (F) = F	(F) ↔ (V) = F
	F	F	F	F v (V) = V	(F) ↔ (F) = V
Leis de Morgan
1ª Lei
A negação de uma conjunção (E) entre duas proposições é a disjunção (OU) da negação das proposições
2ª Lei
A negação de uma disjunção (OU) entre duas proposições é a conjunção (E) da negação das proposições
3ª Lei
A negação de uma implicação entre duas proposições é a conjunção (E) da negação da segunda proposição
1ª Leis de Morgan
A negação de uma conjunção (E) de duas proposições, é a disjunção (OU) da negação de cada uma das proposições
Negar que duas dadas proposições são ao mesmo tempo verdadeiras equivale a afirmar que uma pelo menos é falsa.
“Negar a simultaneidade de P e Q é afirmar pelo menos não P ou não Q”
 ~(P ^ Q) = ~P V ~Q				
	P	Q	~(P ^ Q)	~P V ~Q
	V	V	~(V) = F	F V F = F
	V	F	~(F) = V	F V V = V
	F	V	~(F) = V	V V F = V
	F	F	~(F) = V	V V V = V
2ª Lei de Morgan
A negação de uma disjunção (OU) de duas proposições, é a conjunção (E) da negação de cada uma das proposições
Negar que uma pelo menos de duas proposições é verdadeira equivale a afirmar que ambas são falsas.
“Negar a ocorrência de pelo menos P ou Q é afirmar nem P nem Q”
 ~(P V Q) = ~P ^ ~Q				
	P	Q	~(P V Q)	~P ^ ~Q
	V	V	~(V) = F	F ^ F = F
	V	F	~(V) = F	F ^ V = F
	F	V	~(V) = F	V ^ F = F
	F	F	~(F) = V	V ^ V = V
3ª Lei de Morgan
A negação de uma implicação (unidirecional) de duas proposições, é a conjunção (E) entre a primeira proposição e a negação da segunda proposição
 ~(P → Q) =	P ^ ~Q				
	P	Q	~(P → Q)	P ^ ~Q
	V	V	~(V) = F	V ^ F = F
	V	F	~(F) = V	V ^ V = V
	F	V	~(V) = F	F ^ F = F
	F	F	~(V) = F	F ^ V = F