LOG-Aula-07

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
UTFPR - Ciência da Computação
Lógica Matemática - Aula 07 - Lógica e Teoria dos Conjuntos
Professor: Gleifer Vaz Alves
gleifer@utfpr.edu.br
Universidade Tecnológica Federal do Paraná - Campus Ponta Grossa
COCIC - Coordenação do Curso de Ciência da Computação
Primeiro semestre de 2011.
1 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Outline
1 Mundo dos Blocos
Atividade
2 Regras Lógicas e Teoria dos Conjuntos
3 Exercícios
2 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos.
Mundo dos Blocos (Tarki’s World):
editor para construção de provas através da representação
gráfica do mundo dos blocos.
BARWISE, K. J.; ETCHEMENDY, J. Language, Proof and
Logic. 2002.
Alfred Tarski - filósofo, matemático, lógico polonês.
3 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação gráfica.
4 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Blocos = {1,2,3,4,5,6,7,8,9,10,11,12}
Esferas = {3,5,6}
Cubos = {1,2,9}
Cones = {4,10,11,12}
Cilindros = {7,8}
Mesas = {m}
Brancos = {1,2,3,m}
Vermelhos = {4,5,6}
Amarelos = {7,8,9}
Verdes = {10,11,12}
5 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Blocos = {1,2,3,4,5,6,7,8,9,10,11,12}
Esferas = {3,5,6}
Cubos = {1,2,9}
Cones = {4,10,11,12}
Cilindros = {7,8}
Mesas = {m}
Brancos = {1,2,3,m}
Vermelhos = {4,5,6}
Amarelos = {7,8,9}
Verdes = {10,11,12}
5 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Blocos = {1,2,3,4,5,6,7,8,9,10,11,12}
Esferas = {3,5,6}
Cubos = {1,2,9}
Cones = {4,10,11,12}
Cilindros = {7,8}
Mesas = {m}
Brancos = {1,2,3,m}
Vermelhos = {4,5,6}
Amarelos = {7,8,9}
Verdes = {10,11,12}
5 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Objetos = Blocos ∪ Mesas
Esferas Vermelhas = Esferas ∩ Vermelhas
Esferas Vermelhas = {5,6}
Cilindros Amarelos = Clindros ∩ Amarelos
Cilindros Amarelos = {7,8}
Cilindros ⊆ Amarelos
6 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Objetos = Blocos ∪ Mesas
Esferas Vermelhas = Esferas ∩ Vermelhas
Esferas Vermelhas = {5,6}
Cilindros Amarelos = Clindros ∩ Amarelos
Cilindros Amarelos = {7,8}
Cilindros ⊆ Amarelos
6 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem dos
conjuntos.
Objetos = Blocos ∪ Mesas
Esferas Vermelhas = Esferas ∩ Vermelhas
Esferas Vermelhas = {5,6}
Cilindros Amarelos = Clindros ∩ Amarelos
Cilindros Amarelos = {7,8}
Cilindros ⊆ Amarelos
6 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Definição de Propriedades dos objetos:
a tem a propriedade P ≡ P(a)
ex.: Amarelo(b)
Bloco(1)
Bloco(2)
Bloco(3)
...
Bloco(12)
Mesas(m)
7 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Branco(1)
Branco(2)
Branco(3)
Branco(m)
Vermelho(4)
Vermelho(5)
...
8 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Branco(1)
Branco(2)
Branco(3)
Branco(m)
Vermelho(4)
Vermelho(5)
...
8 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Cone(4)
Cone(10)
Cone(11)
Cone(12)
Esfera Vermelha(5)
Esfera Vermelha(6)
Esfera Vermelha(x)⇔ Esfera(x) ∧ Vermelha(x)
Objeto(x) = Bloco(x) ∨ Mesa(x)
Cilindro(x)⇒ Amarelo(x)
9 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Cone(4)
Cone(10)
Cone(11)
Cone(12)
Esfera Vermelha(5)
Esfera Vermelha(6)
Esfera Vermelha(x)⇔ Esfera(x) ∧ Vermelha(x)
Objeto(x) = Bloco(x) ∨ Mesa(x)
Cilindro(x)⇒ Amarelo(x)
9 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Cone(4)
Cone(10)
Cone(11)
Cone(12)
Esfera Vermelha(5)
Esfera Vermelha(6)
Esfera Vermelha(x)⇔ Esfera(x) ∧ Vermelha(x)
Objeto(x) = Bloco(x) ∨ Mesa(x)
Cilindro(x)⇒ Amarelo(x)
9 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Cone(4)
Cone(10)
Cone(11)
Cone(12)
Esfera Vermelha(5)
Esfera Vermelha(6)
Esfera Vermelha(x)⇔ Esfera(x) ∧ Vermelha(x)
Objeto(x) = Bloco(x) ∨ Mesa(x)
Cilindro(x)⇒ Amarelo(x)
9 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Mundo dos Blocos - apresentação via linguagem da
lógica.
Cone(4)
Cone(10)
Cone(11)
Cone(12)
Esfera Vermelha(5)
Esfera Vermelha(6)
Esfera Vermelha(x)⇔ Esfera(x) ∧ Vermelha(x)
Objeto(x) = Bloco(x) ∨ Mesa(x)
Cilindro(x)⇒ Amarelo(x)
9 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 1 – apresentação gráfica.
Mesa.
E Blocos: 9, 11 e 12.
10 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 1 – linguagem dos conjuntos
Blocos1 = {m,1,9,12}
Sobre = {(1,m), (9,1), (12,9)}
Sobre−1 = {(m,1), (1,9), (9,12)}
11 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 1 – linguagem da lógica
Relação:
a tem relação R com b = R(a,b)
aRB
1 está sobre a mesa = Sobre(1,m)
9 sobre 1 = Sobre(9,1)
12 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 1 – linguagem da lógica
Relação:
a tem relação R com b = R(a,b)
aRB
1 está sobre a mesa = Sobre(1,m)
9 sobre 1 = Sobre(9,1)
12 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 2 – apresentação gráfica.
Mesa.
E Blocos: 7, 8 e 12.
8 entre 7 e 12
13 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 2 – linguagem dos conjuntos
Entre = {(8,7,12)}
14 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Situação 2 – linguagem da lógica
8 entre 7 e 12 = Entre(8,7,12)
Se R ⊆ A× B:
R−1 = {(y , x)/(x , y) ∈ R}
yR−1x ⇔ xRy
R−1(y , x) = R(x , y)
À esquerda = {(7,8), (8,12)}
Entre = {(8,7,12)}
Entre = {(y , x , z)/(x , y) ∈ À Esq. ∧(y , z) ∈ À Esq. }
À Esq. (x , y)∧ À Esq. (y , z)⇒ Entre (y , x , z)
15 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Applet Java:
http://www-rohan.sdsu.edu/ ituba/block/index.html
16 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Atividade – Livraria.
Representar na linguagem dos conjuntos e da lógica.
Livros = {1,2,3, . . . ,12}
Categorias de Livros = { Romance, Ficção, Informática,
Turismo, Política, Cultura, Idiomas }
Ficção = {2, 8}
Informática = {. . . }
. . .
Cores = { Azul, Amarelo, Verde }
Verde = {1, 2, 3, 4}
Amarelo = {5, 6, 7, 8}
Azul = {9, 10, 11, 12}
Prateleira = {13}
Livraria = Livros ∪ Prateleira
17 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Atividade
Atividade – Livraria.
Representar na linguagem dos conjuntos e da lógica.
Descrever:
Livros de Informática da cor verde.
Livros de Idiomas da cor azul.
Livros de Ficção da cor amarela.
Situação 1.
Envolvendo os objetos: 3, 7, 11 e 13.
Situação 2.
Envolvendo os objetos: 10, 11, 12 e 13.
18 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Outline
1 Mundo dos Blocos
Atividade
2 Regras Lógicas e Teoria dos Conjuntos
3 Exercícios
19 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Lógica e Teoria dos Conjuntos.
Linguagem dos Conjuntos
Conjuntos, Tuplas.
Operadores: ∩,∪,⊆.
Linguagem Lógica
Propriedades, relações.
Operadores: ∧,∨,→.
20 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Lógica e Teoria dos Conjuntos.
Linguagem dos Conjuntos
Conjuntos, Tuplas.
Operadores: ∩,∪,⊆.
Linguagem Lógica
Propriedades, relações.
Operadores: ∧,∨,→.
20 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Intersecção (∩) e Conjunção (∧)
Interpretação da intersecção via conjunção.
A ∩ B = {x/x ∈ A ∧ x ∈ B}
x ∈ A ∩ B ⇔ x ∈ A ∧ x ∈ B
Suponha que x ∈ A ∩ B
Portanto, x ∈ A
x ∈ B.
Prova:
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B Eliminação ∧
x ∈ A
x ∈ B
21 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Intersecção (∩) e Conjunção (∧)
Interpretação da intersecção via conjunção.
A ∩ B = {x/x ∈ A ∧ x ∈ B}
x ∈ A ∩ B ⇔ x ∈ A ∧ x ∈ B
Suponha que x ∈ A ∩ B
Portanto, x ∈ A
x ∈ B.
Prova:
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B Eliminação ∧
x ∈ A
x ∈ B
21 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ A e x ∈ B.
Portanto, x ∈ A ∩ B.
Prova:
x ∈ A x ∈ B Introdução ∧
x ∈ A ∧ x ∈ B Def. ∩x ∈ A ∩ B
22 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ A e x ∈ B.
Portanto, x ∈ A ∩ B.
Prova:
x ∈ A x ∈ B Introdução ∧
x ∈ A ∧ x ∈ B Def. ∩x ∈ A ∩ B
22 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – conjunção (∧).
Regras Lógicas – conjunção (∧)
Eliminação ∧
P ∧Q E-∧P
P ∧Q E-∧Q
Introdução ∧
P Q I-∧P ∧Q
23 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – conjunção (∧).
Regras Lógicas – conjunção (∧)
Eliminação ∧
P ∧Q E-∧P
P ∧Q E-∧Q
Introdução ∧
P Q I-∧P ∧Q
23 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos – exercício.
Teorema:
Suponha, x ∈ A ∩ B.
Então, x ∈ B ∩ A.
Prova:
24 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos – exercício.
Teorema:
Suponha, x ∈ A ∩ B.
Então, x ∈ B ∩ A.
Prova:
24 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos – exercício.
Teorema:
Suponha, x ∈ A ∩ B.
Então, x ∈ B ∩ A.
Prova:
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B E-∧x ∈ B
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B E-∧x ∈ A I-∧x ∈ B ∧ x ∈ A Def. ∩x ∈ B ∩ A
25 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos – exercício.
Teorema:
Suponha, x ∈ A ∩ B.
Então, x ∈ B ∩ A.
Prova:
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B E-∧x ∈ B
x ∈ A ∩ B Def. ∩x ∈ A ∧ x ∈ B E-∧x ∈ A I-∧x ∈ B ∧ x ∈ A Def. ∩x ∈ B ∩ A
25 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
União (∪) e Disjunção (∨)
Interpretação da união via disjunção.
A ∪ B = {x/x ∈ A ∨ x ∈ B}
x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B
26 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – disjunção (∨).
Regras Lógicas – disjunção (∨)
Introdução ∨
P I-∨P ∨Q
Q I-∨P ∨Q
27 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ A.
Portanto, x ∈ A ∪ B.
Prova:
x ∈ A I-∨x ∈ A ∨ x ∈ B Def. ∪x ∈ A ∪ B
28 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ A.
Portanto, x ∈ A ∪ B.
Prova:
x ∈ A I-∨x ∈ A ∨ x ∈ B Def. ∪x ∈ A ∪ B
28 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ B.
Portanto, x ∈ A ∪ B.
Prova:
x ∈ B I-∨x ∈ A ∨ x ∈ B Def. ∪x ∈ A ∪ B
29 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que x ∈ B.
Portanto, x ∈ A ∪ B.
Prova:
x ∈ B I-∨x ∈ A ∨ x ∈ B Def. ∪x ∈ A ∪ B
29 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Contido (⊆) e Implicação (→)
Interpretação da operação “estar contido" via implicação
(condicional).
A ⊆ B = {x/x ∈ A→ x ∈ B}
30 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – implicação (→).
Regras Lógicas – implicação (→)
Eliminação→
P P → Q E-→Q
31 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que A ⊆ B e que x ∈ A.
Portanto, x ∈ B.
Prova:
x ∈ A
A ⊆ B
Def. ⊆x ∈ A→ x ∈ B E-→x ∈ B
32 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas via Teoria dos Conjuntos.
Suponha que A ⊆ B e que x ∈ A.
Portanto, x ∈ B.
Prova:
x ∈ A
A ⊆ B
Def. ⊆x ∈ A→ x ∈ B E-→x ∈ B
32 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Suposições Temporárias e Implicação.
Exemplo:
Suponha que x ∈ A.
Então, A ⊆ B → x ∈ B.
Prova:
x ∈ A
[A ⊆ B]a
Def. ⊆x ∈ A→ x ∈ B E-→x ∈ B I-→aA ⊆ B → x ∈ B
Suposições Temporárias e Introdução da Implicação.
33 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – implicação (→).
Regras Lógicas – implicação (→)
Eliminação→
P P → Q E-→Q
Introdução→
[P]
...
R
P → R
34 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Regras Lógicas – disjunção (∨).
Regras Lógicas – disjunção (∨)
Introdução ∨
P I-∨P ∨Q
Q I-∨P ∨Q
Eliminação ∨
P ∨Q P → R Q → R E-∨R
35 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Outline
1 Mundo dos Blocos
Atividade
2 Regras Lógicas e Teoria dos Conjuntos
3 Exercícios
36 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Exercícios – regras lógicas via conjuntos.
Exercício 1.
Suponha que A ⊆ B, B ⊆ C e x ∈ A.
Então, x ∈ C.
Prova: . . .
Exercício 2.
Suponha que A ⊆ B.
Então, x ∈ A→ x ∈ B.
Prova: . . .
37 / 38
Mundo dos Blocos
Regras Lógicas e Teoria dos Conjuntos
Exercícios
Exercícios – regras lógicas via conjuntos.
Exercício 3.
Suponha que A ⊆ B.
Então, x ∈ A ∩ C → x ∈ B ∩ C.
Prova: . . .
Exercício 4.
Suponha que x ∈ A ∪ B.
Então, x ∈ B ∪ A.
Prova: . . .
Exercício 5.
Suponha que x ∈ A ∪ B e A ⊆ B.
Então, x ∈ B.
Prova: . . .
38 / 38
	Mundo dos Blocos
	Atividade
	Regras Lógicas e Teoria dos Conjuntos
	Exercícios