Exercicios Equivalência

Prévia do material em texto

GABARITO Exercícios da Relação de Equivalência (()
Demonstre, utilizando tabelas-verdade, as seguintes relações de equivalência:
p ( ( p ( q ) ( p (equivalentes)
p ( ( p ( q ) ( p (equivalentes)
( p ( q ) ( ( p ( r ) ( p ( p ( r (não equivalentes)
p ( q ( ( p ( q ) ( ~( p ( q ) (equivalentes)
Negue em linguagem corrente as seguintes proposições:
Atlético é alvi-verde e Coritiba é rubro-negro.
Atlético não é alvi-verde ou Coritiba é rubro-negro.
As vendas diminuem e os preços aumentam.
As vendas não diminuem ou os preços não aumentam.
É falso que está frio ou que está chovendo.
~~(p ( q) ( p ( q : Está frio ou está chovendo.
Se João passar em Física então se formará.
João passa em Física e não se forma.
Não tenho carro e não tenho moto.
Tenho carro ou tenho moto.
Demonstre as relações abaixo utilizando as equivalências notáveis:
p ( q ( r ( ( p ( q ) ( ( p ( r )
p ( q ( r ( 
~p ( ( q ( r ) ( 	(reescrita da condicional)
(~p ( q) ( (~p ( r) (	(distributiva)
(p ( q) ( (p ( r) 	(reescrita da condicional)
p ( q ( r ( ( p ( q ) ( ( p ( r )
p ( q ( r ( 
~p ( ( q ( r ) (	(reescrita da condicional)
~p ( q ( r ( 	(associativa)
~p ( ~p ( q ( r (	(idempotente, adicionei um ~p, pois ~p ( ~p ( ~p)
 (~p ( q) ( (~p ( r ) ( 	(associativa)
(p ( q) ( (p ( r) 	(reescrita da condicional)
p ( ( r ( s ( t ) ( ( p ( r ) ( ( p ( s ) ( ( p ( t )
p ( ( r ( s ( t ) (
p ( ( r ( (s ( t)) ( 	(associativa em s ( t )
(p ( r) ( (p ( (s ( t)) ( 	(distributiva)
(p ( r) ( (p ( s) ( (p ( t) 	(distributiva)
p ( q ( r ( p ( ( q ( r )
p ( q ( r ( 
~(p ( q) ( r ( 	(reescrita da condicional)
~p ( ~q ( r ( 	(De Morgan)
~p ( (~q ( r) ( 	(associativa)
~p ( ( q ( r) ( 	(reescrita da condicional)
p ( (q ( r) 	(reescrita da condicional)
~( ~p ( ~q ) ( ~p ( q
~( ~p ( ~q ) ( 	
~( ~~p ( ~q) ( 	(reescrita da condicional)
~(p ( ~q) ( 	(dupla negação)
~p ( ~~q ( 	(De Morgan)
~p ( q	(dupla negação)
Demonstre as leis de Morgan para três proposições:
~( p ( q ( r ) ( ~p ( ~q ( ~r
~(p ( ( q ( r) ) ( 	(associativa)
~p ( ~(q ( r) ( 	(De Morgan)
~p ( ~q ( ~r	(De Morgan)
~( p ( q ( r ) ( ~p ( ~q ( ~r
~(p ( ( q ( r) ) ( 	(associativa)
~p ( ~(q ( r) ( 	(De Morgan)
~p ( ~q ( ~r	(De Morgan)
Demonstre, utilizando as equivalências notáveis, que as relações de implicação são válidas:
Exemplo.: Regra da simplificação: p ( q ( q 
Para provarmos uma relação de implicação temos que demonstrar que a condicional p ( q ( q é tautológica, ou seja, que a condicional p ( q ( q ( V
Desenvolvendo o lado esquerdo da equivalência, tem-se:
p ( q ( q ( 	(aplicando-se a equiv. de reescrita da condicional)
~( p ( q ) ( q ( (aplicando-se a Lei de Morgan)
~p ( ~q ( q ( 	(aplicando-se lei complementar, ~q ( q é uma tautologia)
~p ( V (		(pela lei da identidade ~p ( V é um tautologia)
V	Portanto, está provado que p ( q ( q é uma tautologia
Regra da adição: p ( p ( q
p ( p ( q ( V	(devemos demonstrar que a relação de implicação equivale a uma tautologia)
~p ( (p ( q) (	(condicional)
~p ( p ( q (	(associativa)
V ( q (	(complementares ~p ( p)
V	(identidade)
Regra do Silogismo Disjuntivo: (p ( q) ( ~q ( p
(p ( q) ( ~q ( p ( V	(devemos demonstrar que a relação de implicação equivale a uma tautologia)
(p ( ~q) ( (q ( ~q) ( p ( (distributiva)
(p ( ~q) ( F ( p (	(complementares)
(p ( ~q) ( p (	(identidade)
~(p ( ~q) ( p (	(condicional)
~p ( ~q ( p (	(De Morgan)
(~p ( p) ( ~q (	(associativa)
 V ( ~q (	(complementares)
V	(identidade)
Regra de Modus Ponens: (p ( q) ( p ( q
(p ( q) ( p ( q ( V	(devemos demonstrar que a relação de implicação equivale a uma tautologia)
(~p ( q) ( q ( q (	(condicional)
(q ( ~p) ( (q ( q) ( q (	(distributiva)
(q ( ~p) ( q ( q (	(idempotente)
~((q ( ~p) ( q) ( q (	(condicional)
( ~(q ( ~p) ( ~q ) ( q (	(De Morgan)
((~q ( p) ( ~q) ( q (	(De Morgan)
(~q ( ~q) ( (~q ( p) ( q ( (distributiva)
~q ( (~q ( p) ( q (	(idempotente)
(~q ( q) ( ( ~q ( p ) (	(associativa)
V ( (~q ( p ) (	(complementares)
V	(identidade)
Regra de Modus Tollens: (p ( q) ( ~q ( ~p
(p ( q) ( ~q ( ~p ( V	(devemos demonstrar que a relação de implicação equivale a uma tautologia)
(~p ( q) ( ~q ( ~p (	(De Morgan)
(~q ( ~p) ( (~q ( q) ( ~p ( (Distributiva)
(~q ( ~p) ( F ( ~p (	(Complementares)
(~q ( ~p) ( ~p (	(Identidade)
~(~q ( ~p) ( ~p (	(condicional)
~~q ( ~~p ( ~p (	(De Morgan)
q ( p ( ~p (	(Dupla Negação)
q ( V (	(complementares)
V
Reescreva os testes abaixo reduzindo as condições através das relações de equivalência:
SE fluxo_ext > fluxo_int ( ~( fluxo_ext > fluxo_int ( pressão < 1000 ) ENTÃO
 faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: fluxo_ext > fluxo_int e q: pressão < 1000 tem-se: 
p ( ~(p ( q) (
p ( (~p ( ~q) (	(De Morgan)
(p ( ~p) ( (p ( ~q) (	(Distrib.)
F ( (p ( ~q) (	(Complem.)
p ( ~q
Se fluxo_ext > fluxo_int ( pressão ( 1000
 faça bloco A
Senão
 faça bloco B
SE ​​ ~(idade > 21 ( sexo="F") ( ( ~(idade > 21) ( sexo="F") ENTÃO
 faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: idade > 21 e q: sexo = "F": 
~(p ( q) ( (~p ( q) (
(~p ( ~q) ( (~p ( q) (	(De Morgan)
~p ( (~q ( q) (	(Distributiva)
~p ( V (	(Complem.)
~p	(Identidade)
Se idade ( 21
 faça bloco A
Senão
 faça bloco B
SE (cab="loiro" ( pele="morena") ( (cab="loiro" ( pele="branca") ENTÃO
 	faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: cab="loiro", q: pele="morena" e r: pele="branca" tem-se:
(p ( q) ( (p ( r) (
p ( (q ( r)	(Distribuitiva)
Se cab="loiro" ( (pele="morena" ( pele="branca")
 faça bloco A
Senão
 faça bloco B
SE (cab="loiro" ( pele="morena") ( (cab="loiro" ( pele="branca") ENTÃO
 	faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: cab="loiro", q: pele="morena" e r: pele="branca" tem-se:
(p ( q) ( (p ( r) (
(p ( p) ( q ( r (	(Associativa)
p ( q ( r	(Idempotente)
Se cab="loiro" ( pele="morena" ( pele="branca"
 faça bloco A
Senão
 faça bloco B
SE (cidade="Curitiba") ENTÃO
 SE (bairro="Centro" ( bairro="Rebouças") ENTÃO
 faça bloco de comandos A.
Fazendo p: cidade="Curitiba", q: bairro="Centro" e r: bairro="Rebouças" tem-se:
p ( (q ( r)	(note que se aninhados são conectados por conjunção)
Se cidade="Curitiba" ( (bairro="Centro" ( bairro="Rebouças")
 faça bloco A
Reescreva os testes abaixo negando as condições:
SE i > 8 ENTÃO
 faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: i > 8 tem-se que a negação do teste é:
~p	
Reescrevendo o teste condicional (note a inversão entre os blocos de comando A e B):
Se i ( 8
 faça bloco B
Senão
 faça bloco A
SE i > 8 ( estado="OFF" ENTÃO
 faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: i > 8 e q: estado="OFF" tem-se que a negação do teste é:
~( p ( q) (
~p ( ~q	(DM)	 
Reescrevendo o teste condicional (note a inversão entre os blocos de comando A e B):
Se i ( 8 ( estado ( "OFF"
 faça bloco B
Senão
 faça bloco A
SE título_livro="Cortiço" ( autor="Machado de Assis" ( editora="LTC" ENTÃO
 faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: título_livro="Cortiço", q: autor="Machado de Assis" e r: editora = "LTC" tem-se que a negação do teste é:
~( p ( q ( r) (
~p ( ~q ( ~r	(DM)	 
Reescrevendo o teste condicional (note a inversão entre os blocos de comando A e B):
Se título_livro ( "Cortiço" ( autor( "Machado de Assis" ( editora( "LTC"
 faça bloco B
Senão
 faça bloco A
SE (assunto="redes" ( assunto="teleinformática") ( data_public> 20/12/1998 
 	faça bloco de comandos A
SENÃO
 	faça bloco de comandos B
Fazendo p: assunto="redes", q: assunto="teleinformática" e data_public > 20/12/1998 tem-se que a negação do teste é:
~( ( p ( q ) ( r) (
~( p ( q ) ( ~r (	(DM)	 
(~p ( ~q) ( ~r	(DM)
Reescrevendo o teste condicional (note a inversão entre os blocos de comando A e B):
Se (assunto ( "redes" ( assunto ( "teleinformática") ( data_public ( 20/12/1998
 faça bloco B
Senão
 faça bloco A
Escreva os testes condicionais do exercício 7a e 7b em linguagem lógica matemática. Faça o mesmo com os testes abaixo: 
Breve explicação: Existe um tipo de lógica matemática denominada Lógica de Floyd-Hoare que permite utilizar o raciocínio matemático sobre programas de computadores e suas especificações. Esta lógica permite verificar programas, ou seja, estabelecer conclusivamente que um determinado programa atende a sua especificação. Além disso, permite construí-los a partir de suas especificações. Esta lógica, estabelece uma tradução para todas as construções utilizadas num programa de computador. Assim, a tradução que ela estabelece para um teste condicional é a seguinte:
Se x < 0 Fazendo: p: x < 0 , q: bloco A executado e r: bloco B executado temos:
 Bloco A ( p ( q ) ( ( ~p ( r )
Senão
 Bloco B
Resposta da tradução do exercício 7a
Fazendo p: i > 8, a: bloco A executado e b: bloco b executado, tem-se:
( p ( a ) ( ( ~p ( b )
Resposta da tradução do exercício 7b
Fazendo p: i > 8 e q: estado="OFF" tem-se:
( p ( q ( a ) ( (~(p ( q) ( b )
SE (estado_fita="emprestada") ENTÃO
 SE (data_entrega < hoje) ENTÃO
 	 faça bloco de comandos A.
Fazendo p: estado_fita=”emprestada” e q: data_entrega < hoje tem-se:
( p ( q ( a ) 
SE (estado_fita="emprestada") ENTÃO
 SE (data_entrega < hoje) ENTÃO
 	 faça bloco de comandos A
 SENÃO
 faça bloco de comandos B
Fazendo p: estado_fita=”emprestada” e q: data_entrega < hoje tem-se:
( p ( q ( a ) ( (p ( ~q ( b)
Demonstre a validade dos argumentos abaixo mediante utilização de regras de inferência e equivalências notáveis:
p ( q, q ( r |— ~p ( r
p ( q
q ( r
----------------------
3.	p ( r	SH em 1 e 2
4.	~p ( r	COND em 3
~p ( ~q, q |— p
~p ( ~q
q 
----------------------
3.	~~q ( ~~p	CP em 1
4.	q ( p	DN em 3
5.	p	MP em 2 e 4
p ( ~q, q |— ~p
p ( ~q
q 
----------------------
3.	~p	MT em 1 e 2
p ( q, r ( ~q |— p ( ~r
p ( q
r ( ~q 
----------------------
3.	~q ( ~p	CP em 1
4.	r ( ~p 	SH em 2 e 3
5.	~~p ( ~r	CP em 4
6.	p ( ~r	DN em 5
p ( ( q ( r ), p ( q ( s |— p ( s
p ( ( q ( r )
p ( q ( s
----------------------
3.	( p ( q ) ( ( p ( r )	DIS em 1
4.	( p ( q)		SIM em 3
5.	s		MP em 2 e 4
6.	p ( s		AD em 5
p ( ~q, r (q, r |— ~p
p ( ~q
r ( q
r
----------------------
4.	q	MP em 2 e 3
5.	~p	MT em 1 e 4
r ( p ( q, ~p ( ~q, r ( s |— s
p ( p ( q
~p ( ~q
r ( s
----------------------
4.	~(p ( q)	DM em 2
5.	~r	MT em 1 e 4
6.	s	SD em 3 e 6
p ( q ( r, ~r, q ( ( ~s ( t ) |— s ( t
p ( q ( r
~r
q ( ( ~s ( t )
----------------------
4.	~(p ( q)	MT em 1 e 2
5.	~p ( ~q	DM em 4
6.	~q	SIM em 5
7.	~s ( t	SD em 3 e 6
8.	s ( t	COND em 7
p ( q ( r ( s, ~s |— ~q
p ( q ( r ( s
~s
----------------------
3.	~s ( ~r 	AD em 2
4.	~(s ( r)	DM em 3
5.	~(p ( q)	MT em 1 e 4
6.	~p ( ~q	DM em 5
7.	~q	SIM em 6
p ( q, q ( s, t ( ( r ( ~s ) |— p ( t
p ( q
q ( s
t ( (r ( ~s)
----------------------
4.	(q ( s) ( (s ( q)	BI em2
5.	q ( s		SIM em 4
6.	p ( s		SH em 1 e 5
7.	(t ( r) ( (t ( ~s)	DIS em 3
8.	t ( ~s		SIM em 7
9.	~s ( t 		COM em 8
10.	s ( t		COND em 9
11.	p ( t		SH em 6 e 10
p ( ( q ( r ), p ( s, s ( r |— r
p ( (q ( r)
p ( s
s ( r
----------------------
4.	p ( r 		SH em 2 e 3
5.	(p ( q) ( (p ( r)	DIS em 1
6.	p ( r		SIM em 5
7.	r ( p		COM em 6
8.	~~r ( p		DN em 7 (posso acrescentar uma DN pois ~~r ( r)
9.	~r ( p		COND em 8
10.	~r ( r		SH em 9 e 4
11. ~~r ( r		COND em 10
12.	r ( r		DN em 11
13	r		ID em 12
( p ( q ) ( ( r ( s ), ~q |— ~p ( s
(p ( q) ( (r ( s)
~q
----------------------
3.	( (p ( q) ( r ) ( ( (p ( q) ( s )	DIS em 1
4.	( p ( q ) ( s		SIM em 3
5.	~p ( q ( s		COND em 4
6.	q ( (~p ( s)		COM em 5
7.	~p ( s		SD em 2 e 6
( p ( q ) ( r ( s, ~r |— ~p
p ( q ( r ( s
~r
----------------------
3.	~(p ( q) ( (r ( s)	COND em 1
4.	~r ( ~s		AD em 2
5.	~(r ( s)		DM em 4
6.	~(p ( q)		SD em 3 e 5
7.	~p ( ~q		DM em 6
8.	~p		SIM em 7
lógica Aplicada - Prof. Tacla pg(� PAGE �1�/� NUMPAGES �1�)
arq.: � FILENAME �ExercEquivGabarito.doc�