Lógica Proposicional - Equivalências Lógicas fileL ogica Proposicional Equival^encias L ogicas Profa. Sheila Morais de Almeida DAINF-UTFPR-PG junho - 2018 Sheila Almeida (DAINF-UTFPR-PG)

Logica ProposicionalEquivalencias Logicas

Profa. Sheila Morais de Almeida

DAINF-UTFPR-PG

junho - 2018

Sheila Almeida (DAINF-UTFPR-PG) Logica Proposicional junho - 2018 1 / 36

Este material e preparado usando como referencias os textos dos seguinteslivros.

GERSTING, Judith L.,Mathematical Structures For Computer Science:A Modern Approach to Discrete Mathematics, 6th ed., 2007.

ROSEN, Kenneth H., Discrete Mathematics and its applications, 6thed., 2007.


Operador de Biimplicacao

Lembre-se: uma proposicao bicondicional P ↔ Q e verdade quando P e Qtem o mesmo valor verdade, e so neste caso.

Tabela verdade da biimplicacao

P Q P ↔ Q

V V VV F FF V FF F V


Equivalencias Logicas

Se duas proposicoes compostas, P e Q, possuem o mesmo valor-verdadeem todos os casos, sao chamadas de logicamente equivalentes.

Exemplo: A→ B e logicamente equivalente a ¬B → ¬A.

A B A→ B ¬B ¬A ¬B → ¬AV V V F F VV F F V F FF V V F V VF F V V V V

Nestes casos, P ↔ Q e uma tautologia.



Se duas proposicoes compostas, P e Q, possuem o mesmo valor-verdadeem todos os casos, sao chamadas de logicamente equivalentes.

Exemplo: A→ B e logicamente equivalente a ¬B → ¬A.

A B A→ B ¬B ¬A ¬B → ¬AV V V F F VV F F V F FF V V F V VF F V V V V

Neste caso, (A→ B)↔ (¬B → ¬A) e uma tautologia.



Quando duas proposicoes logicas A e B sao equivalentes, indicamos poruma das seguintes formas:

• A ≡ B

• A⇔ B

Atencao!!

Os sımbolos ≡ e ⇔ nao sao operadores logicos!

Sao apenas sımbolos matematicos usados para dizer que as proposicoes Ae B tem os mesmos valores verdade em todos os casos.



Exemplos:

• A→ B ≡ ¬B → ¬A (Contrposicao)

• ¬(A ∨ B) ≡ (¬A ∧ ¬B) (Lei de De Morgan)

• ¬(A ∧ B) ≡ (¬A ∨ ¬B)

• (A ∧ B) ≡ (B ∧ A) (Propriedade Comutativa)

• (A ∨ B) ≡ (B ∨ A)

• (A ∧ B) ∧ C ≡ A ∧ (B ∧ C ) (Propriedade Associativa)

• (A ∨ B) ∨ C ≡ A ∨ (B ∨ C )

• A ∧ (B ∨ C ) ≡ (A ∧ B) ∨ (A ∧ C ) (Propriedade Distributiva)

• A ∨ (B ∧ C ) ≡ (A ∨ B) ∧ (A ∨ C )



Como saber se duas proposicoes logicas compostas sao logicamenteequivalentes?

Use tabelas verdade!



Como saber se duas proposicoes logicas compostas sao logicamenteequivalentes?

Use tabelas verdade!


Equivalencia Logica

Exemplo: (A→ B)→ B e logicamente equivalente a (¬B → ¬A)→ B.

A B A→ B (A→ B) ¬A ¬B ¬B → ¬A (¬B → ¬A)→ B → B

V V V V F F V VV F F V F V F VF V V V V F V VF F V F V V V F


Equivalencia Logica

Exemplo: (A→ B)→ B e logicamente equivalente a (¬B → ¬A)→ B.

A B A→ B (A→ B) ¬A ¬B ¬B → ¬A (¬B → ¬A)→ B → B

V V V V F F V VV F F V F V F VF V V V V F V VF F V F V V V F


Equivalencia Logica

Exemplo: (A→ B) ≡ ¬A ∨ B.

A B A→ B ¬A ¬A ∨ B

V V V F VV F F F FF V V V VF F V V V

Vamos chamar essa equivalencia logica de regra da implicacao.


Equivalencia Logica

Exemplo: (A→ B) ≡ ¬A ∨ B.

A B A→ B ¬A ¬A ∨ B

V V V F VV F F F FF V V V VF F V V V

Vamos chamar essa equivalencia logica de regra da implicacao.


Equivalencia Logica

Exemplo: A ≡ ¬(¬A).

A ¬A ¬(¬A)

V F VV F VF V FF V F

Essa equivalencia logica e a dupla negacao.


Equivalencia Logica

Exemplo: A ≡ ¬(¬A).

A ¬A ¬(¬A)

V F VV F VF V FF V F

Essa equivalencia logica e a dupla negacao.



Exemplo: Sera que e mesmo verdade que ¬(A ∧ B) ≡ ¬A ∨ ¬B?




A B A ∧ B ¬(A ∧ B) ¬A ¬B ¬A ∨ ¬BV V V F F F FV F F V F V VF V F V V F VF F F V V V V

Esta e uma das Leis de De Morgan!




A B A ∧ B ¬(A ∧ B) ¬A ¬B ¬A ∨ ¬BV V V F F F FV F F V F V VF V F V V F VF F F V V V V

Esta e uma das Leis de De Morgan!



Augustus De Morgan (1806 - 1871)

• Foi um matematico indiano.

• Foi professor de Augusta Ada, Condessa de Lovelace.




• Escreveu milhares de artigos para mais de 15 periodicos e muitoslivros teoricos.

• Formalizou conceitos como inducao matematica e limite.




• Deu contribuicoes fundamentais para o desenvolvimento da logicasimbolica.

• Criou notacoes que ajudaram a provar equivalencias logicas e as Leisde De Morgan.



Leis de De Morgan:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B.

• ¬(A ∨ B) ≡ ¬A ∧ ¬B.

Exercıcio: Use as Leis de De Morgan para negar:

“Miguel tem um celular e um laptop”.

Miguel nao tem um celular ou nao tem um laptop.



Leis de De Morgan:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B.

• ¬(A ∨ B) ≡ ¬A ∧ ¬B.

Exercıcio: Use as Leis de De Morgan para negar

“Miguel tem um celular e um laptop”.

Miguel nao tem um celular ou nao tem um laptop.



Leis de De Morgan:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B.

• ¬(A ∨ B) ≡ ¬A ∧ ¬B.


“Rodrigo ou Carlos vai ao concerto”.

Rodrigo e Carlos nao vao ao concerto.



Leis de De Morgan:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B.

• ¬(A ∨ B) ≡ ¬A ∧ ¬B.


“Rodrigo ou Carlos vai ao concerto”.

Rodrigo e Carlos nao vao ao concerto.


Provando Equivalencias Logicas

Mostre que ¬(A→ B) ≡ A ∧ ¬B.

¬(A→ B) ≡ ¬(¬A ∨ B) (Regra da implicacao.)

≡ ¬(¬A) ∧ ¬B (Lei de De Morgan.)

≡ A ∧ ¬B (Regra da dupla negacao.)





















Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.

¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬(¬A ∧ B) (Lei de De Morgan.)

≡ ¬A ∧ (¬(¬A) ∨ ¬B) (Lei de Demorgan.)

≡ ¬A ∧ (A ∨ ¬B) (Regra da Dupla Negacao.)

≡ (¬A ∧ A) ∨ (¬A ∧ ¬B) (Propriedade distributiva.)

≡ F ∨ (¬A ∧ ¬B) (Pois A ∧ ¬A e falso.)

≡ ¬A ∧ ¬B (Regra do elemento neutro.)



Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.









Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.









Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.









Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.









Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.









Mostre que ¬(A ∨ (¬A ∧ B)) ≡ ¬A ∧ ¬B.








Documents

Lógica Proposicional - Equivalências Lógicas fileL ogica Proposicional Equival^encias L ogicas Profa. Sheila Morais de Almeida DAINF-UTFPR-PG junho - 2018 Sheila Almeida (DAINF-UTFPR-PG)