Matematica Discreta

Implicação e Equivalência

Implicação Lógica

Como visto anteriormente que uma proposição condicional é representada simbolicamente por pq, que se lê da forma “se p, então q”. Agora essa condicional será relacionada com a implicação lógica.

Definição: Uma proposição condicional pq é uma implicação lógica se for uma tautologia.

Notação: p q (lê-se p implica q)

As proposições p e q são denominadas HIPÓTESE e TESE, respectivamente.

Implicação lógica é uma relação entre duas proposições compostas dadas e uma tautologia. Portanto, na composição de uma tabela-verdade que apresenta tautologia, a partir da condicional pq, ter-se-á o valor lógico V na última coluna.

Exemplo: Considerando as proposições p e q, temos a seguinte tabela-verdade da proposição composta (p^q)p

p	q	(p^q)	(p^q)p
V	V	V	V
V	F	F	V
F	V	F	V
F	F	F	V

Por esta tabela observa-se que a proposição condicional (p^q)p é uma tautologia (pois apresenta V na última coluna). Logo, pela definição anterior, (p^q)p

Atividade 3

Determine os valores lógicos da proposição ~q~p, completando a tabela abaixo.

p	q	~p	~q	~q~p
V	V
V	F
F	V
F	F

Comentário: Veja que na 2ª linha ~q~p é Falso pois ~q (Verdadeiro) e ~p (Falso).

Relações de equivalência

Definição: Duas proposições A e B são ditas logicamente equivalentes se suas tabelas-verdade forem idênticas. Ou seja, quando, a partir das mesmas proposições simples, duas proposições A e B assumirem o mesmo valor lógico.

Notação: AB (Lê-se: A é equivalente a B)

No lugar do símbolo também se utiliza.

Exemplo: Comparando-se os valores lógicos de A=p e B=~(~p), observa-se que são os mesmos. Portanto, p é equivalente a ~(~p), isto é, ~(~p) p.

p	q	~(~p)
V	F	V
F	V	F
~(~p) p ou BA

Exemplo: A proposição “Não é verdade que nossos carros são baratos e duram muito” é logicamente equivalente a “Nossos carros não são baratos ou não duram muito”. De fato, negar a conjunção “Nossos carros são baratos e duram muito” é negar pelo menos uma das proposições componentes.

Escreve-se:

p:		Nossos carros são baratos.
~p:		Nossos carros não são baratos.
q:		Nossos carros duram muito.
~q:		Nossos carros não duram muito.
~(pq):		Não é verdade que nossos carros são baratos e duram muito.
~p~q:		Nossos carros não são baratos ou não duram muito.

Construindo as duas tabelas-verdade, teremos.

p	q	pq	~(pq)
V	V	V	F
V	F	F	V
F	V	F	V
F	F	F	V

p	q	~p	~q	~p~q
V	V	F	F	F
V	F	F	V	V
F	V	V	F	V
F	F	V	V	V

Comparando os valores lógicos da última coluna das duas tabelas, concluímos que

~(pq) ~p~q

Este resultado vale para quaisquer que sejam as proposições p e q.

Exemplo: Analogamente, pode-se verificar na proposição: "Não é verdade que o piloto ganha a corrida ou é despedido", que é equivalente a outra proposição: "O piloto não ganha a corrida e não é despedido".

Conforme a tabela abaixo, a negação da disjunção pq é equivalente a negar, simultaneamente as proposições p e q.

p	q	pq	~(pq)
V	V	V	F
V	F	V	F
F	V	V	F
F	F	F	V

p	q	~p	~q	~p~q
V	V	F	F	F
V	F	F	V	F
F	V	V	F	F
F	F	V	V	V

Desta forma, tem-se que:

~(pq) ~p~q

Os dois últimos exemplos correspondem às leis de Morgan estabelecidos na tabela seguinte.

Álgebra de Proposições

Teorema

Sejam as proposições p, q, r, v, f, onde v e f correspondem, respectivamente, a proposições verdadeiras e falsas. As seguintes proposições são, LOGICAMENTE EQUIVALENTES:

Leis da Álgebra de Proposições
Leis Idempotentes
(1a) p p p	(1b) ppp
Leis Associativas
(2a) (pq) r p (q r)	(2b) (pq)r p(qr)
Leis Comutativas
(3a) p q qp	(3b) pq qp
Leis Distributivas
(4a) p(qr)(pq)(pr)	(4b) p(qr) (pq)(pr)
Leis de Identidade
(5a) p f p	(5b) pv p
(6a) p v v	(6b) pf f
Leis Complementares
(7a) p~p v	(7b) p~p f
(8a) ~ ~pp	(8b) ~v f, ~fv
Leis de De Morgan
(9a) ~ (pq) ~p~q	(9b) ~ (pq) ~p~q

O teorema acima pode ser demonstrado, construindo-se as tabelas-verdade de cada item.

Equivalência Lógica

Dizer que A e B são logicamente equivalentes é o mesmo que dizer que a bicondicional AB é uma tautologia. Portanto, as tabelas-verdades de A e B são idênticas.
Neste caso, utiliza-se a seguinte notação:
(lê-se A é equivalente a B)

Exemplo: De acordo com o último exemplo, se A=~(pq) e B=~p~q, tem-se a seguinte tabela-verdade:

p	q	~(pq)	~p~q	~(pq) ~p~q
V	V	F	F	V
V	F	F	F	V
F	V	F	F	V
F	F	V	V	V

Note que os valores lógicos de A e B são iguais, portanto a bicondicional AB é uma tautologia e pode ser representada pela equivalência: AB

Exemplo: As Leis de De Morgan são outros exemplos de equivalência lógica.

~(pq)~p~q