Discutindo as Relações (Relações entre conjuntos) 01

Esse conjunto de postagens é uma revisão para podermos fazer a lista de exercícios, uma boa leitura e bons raciocínios. Qualquer coisa podem postar comentários.

RELAÇÃO

Um conjunto R, é uma relação de A em B (AxB) se e somente se R está contido em AxB.

Exemplo:

A = {0, 1} e B= {2, 4}

AxB = {(0,2),(0,4),(1,2),(1,4)}

Duvidas…

1 ) R = Ø é uma relação de A em B?

Sim pois o conjunto vazio esta contido em qualquer conjunto.

2 ) R = {(0,4),(1,4)} é uma relação de A em B?

Sim pois todos os elementos de R estão em AxB, ou seja R⊂ AxB.

3 ) R = {(1,2)} é uma relação de A em B?

Sim pois todos os elementos de R estão em AxB, ou seja R⊂ AxB.

RELAÇÕES REFLEXIVAS, SIMÉTRICAS E TRANSITIVAS.

- REFLEXIVA

Seja A um conjunto e R uma relação de A em A, dizemos que tal relação é REFLEXIVA se e somente se para todo x ∈ A, tem-se x R x.

Ou para todo x ∈ A, (x,x)∈ R

Uma outra explicação. Uma relação e REFLEXIVA apenas quando, para cada elemento de A, tem se esse elemento duplicado na relação.

Exemplo (AxA)

A = {1,2,3}

R = {(1,1),(2,2),(,3,3)}

Duvidas…

R = {(1,2),(1,1),(,3,3)} é reflexiva ? Não pois o elemento 2 não se repete na relação (faltou 2,2). 2 ∈ A, mas (2,2)∉ R.

S = {(1,1),(1,3,)(2,2),(2,1),(3,2)(,3,3)} é reflexiva? Sim pois todos os elementos de A se repetem na relação.

REFLEXIVA é a relação espelho, o primeiro conjunto tem que está completamente espelhado na relação.

- SIMÉTRICA

Seja R uma relação de A em A, (R⊂ AxA), dizemos que R é SIMÉTRICA se dado (x,y) ∈ R, então (y,x)∈ R.

Se para quaisquer que sejam x, y ∈ A, tem-se :

xRy⇒ yRx

ou seja se tem na relação (x,y) tem que ter o contrário (y,x) para ser simétrica.

Exemplo:

A = {a,b,c}

R = {(a,b),(a,a),(b,a),(c,c)} é simétrica pois o contrário de cada elemento da relação existe.

S = {(a,b)} não é simétrica pois deveria ter (b,a) o contrário na relação

T = {(a,b), (b,a)} é simétrica.

- TRANSITIVA

Seja R⊂ AxA (R é uma relação de A em A). É TRANSITIVA se dados (x,y) ∈ R e (y,z) ∈R, então (x,z) ∈ R.

Se para quaisquer que sejam x, y, z ∈ A, tem-se:

x R y e y R z ⇒ x Rz,

dizemos que a relação R é transitiva.

outra explicação: se tive na relação um par (x,y) e não um correspondente (y,z) tudo bem. Mas se tiver (x,y) e (y,z) então obrigatoriamente tem que ter (x,z).

Exemplo:

A = {1,2,3}

R = {(1,1),(1,3),(2,3),(3,1)} não é transitiva pois (2,3)∈R e (3,1)∈R mas (2,1)∉R

S = {(1,3),(3,2),(2,1),(1,2),(2,2)} é transitiva?

não pois (3,2) e (2,1) ∈ S, mas (3,1) ∉ S. (por  Lafaiet)

Aproveite para fazer a lista de exercícios até o número 03. 3a[1].lista.mat.disc.(2009-2)

só para  contar. As relações que são simultaneamente reflexivas, simétricas e transitivas são
chamadas relações de equivalência.

Prova por Indução Matemática

Indução Matemática:

1.Base: Provar que uma afirmação P(menor) é verdadeira
para o “menor” elemento sobre o qual incide a afirmação
2. Passo indutivo: Assumir que a afirmação é verdadeira
para P(k) com k=1, 2, …, n , então pode provar-se que:
P(n) → P(n+1) .
3. Conclusão: Usando 1. e 2. prova-se que: ∀n P(n)

Exemplo 01:
Provar que se n é um inteiro maior do que 1, então n pertence ao conjunto de números inteiros positivos.

1+2+3+4+…+n= n(n+1)/2 é verdadeiro ∀n Є Z+

Por indução matemática temos:

1. P(1) é verdadeiro? (primeiro valor da sequência)

1=1(1+1)/2
1=1 é verdadeiro

2.P(k) é verdadeiro? (último valor da sequência)

1+2+3+4…k=k(k+1)/2

Por demostrar que P(k+1) é verdadeiro
1+2+3+4…k+(k+1) = (k+1).((k+1)+1)/2

Temos que:

1+2+3+4…(k+1) = 1+2+3+4…(k+1)
= k*(k+1)/2 + (k+1)
= k (k+1) + (2(k+1))
= (k2+k+2k+2)/2
usando fatoração pelo método de Ruffine temos:

1 3 2

-1 -2
-1
1 2 0

(k+1)*(k+2)
=((k+1)*((k+1)+1))/2
logo
1+2+3+4+…+(k+1)=((k+1)-(k+1)+1)/2

isto é p(k+1) é verdadeiro.
Finalmente
de 1. e 2. por indução matemática temos;
p(n) é verdadeiro para todo n ou seja ∀n Є Z+
isto é, 1+2+3+4+…+n=(n(n+1))/2 é verdadeiro em ∀n Є Z+

Exemplo 02:
Provar que :
2^3n-1 é divisível por 7
Observação: um número mЄZ é divisível por rЄZ se e somente se existe tЄZ tal que m = r * t.

Exemplo 15(m) é divisível por 5(r) pois 15(m) = 5(r) * 3(t). “m” é divisível por “r” é equivalente a “m” é múltiplo de r.
Por indução matemática.

1.p(1) = 2^3*1-1 = 7 = 8 – 1 = 7 é divisível por 7, logo p(1) é verdadeiro.

2.Seja p(k) verdadeiro por demostrar que
p(k+1) é verdadeiro.
Temos:
2^3k-1 é divisível por 7
isto é 2^3k-1 = 7*t t Є Z
demostrando:
2^3(k+1)-1 = 2^3k+3-1
2^3(k+1)-1 = 2^3k * 2^3-1
2^3(k+1)-1 = 8 * 2^3k-1
2^3(k+1)-1 = 7 * 2^3k+2^3k -1
2^3(k+1)-1 = 7 * 2^3k+7 *t
2^3(k+1)-1 = 7 * (2^3k+t)
portanto:
3(k+1)
2^3(k+1)-1 = 7 * (2^2k+t)
isto é 2^3(k+1)-1 é divisível por 7 é verdadeiro.

Finalmente temos 1. e 2. é verdadeiro
2^3n-1 é divisível por 7 ∀n Є Z+

Esta é a primeira parte de indução matemática, as próximas postagens serão das aulas ministradas nas próximas semanas.

segue a lista de exercícios sobre conjuntos e indução matemática.
Lista 1 Matemática discreta.

Thiago Amorim

Não explica que complica.

Tentando explicar a piada da postagem anterior.

O fato é que para a lógica proposicional, em uma disjunção como é o nosso caso você pode afirmar qualquer que seja o elemento (no nosso caso menino ou menina), que será verdadeira a inferência.

Então se uma pessoa pergunta, se o filho que a mulher do lógico esta esperando vai ser menina ou menino ele está falando uma verdade, que pode ser respondida com outra verdade, sim ele será um do dois. Bom mas existe a possibilidade de nascer com os dois sexos, mesmo assim podemos responder sim para o que foi colocado na pertgunta.

Existem dois tipos de disjunções, segue explicações:

Disjunação inclusiva

O bebe será menino ou menina exprime uma proposição que só será falsa no caso de o bebe não nascer ou da mulher do lógico não está grávida. E isto acontece com qualquer proposição da forma «P ou Q»: só será falsa se
P e Q forem ambas falsas; caso contrário, será verdadeira. Podemos representar
isto graficamente numa tabela de verdade:

P Q P ou Q
V V V
V F V
F V V
F F F

Disjunção exclusiva
Uma disjunção exclusiva só é verdadeira caso uma e uma só das proposições disjuntas seja verdadeira.

A tabela de verdade da disjunção exclusiva é a seguinte:
P Q P ou Q
V V F
V F V
F V V
F F F

Nos dois casos a afirmação é verdadeira. Agora sei o significado de “não explica que complica.”

Mais em:

http://dmurcho.com/docs/introprop.pdf

Descontração…

Perguntaram ao Lógico quando do nascimento do seu primeiro bebê:
- É menino ou menina?
Ao que ele respondeu, logicamente:
- Sim!

não entendeu?? então comenta…

Matemática Discreta (Conjuntos e Relações)

Primeiramente falaremos sobre os elementos utilizados na formação dos conjuntos e depois de suas relações.

Um conjunto é uma coleção de objetos, por exemplo, o conjunto de matérias que compõem a matriz do curso de sistemas de informação ou também o conjunto das teclas do seu teclado.
Um elemento ou objeto é um componente de um conjunto, seguindo o exemplo acima temos respectivamente o elemento matemática discreta e a tecla delete como elemento do conjunto.
Para mostrar que um elemento pertence ou não a um conjunto usamos o símbolo de pertinência: ∈ pertence, ∉ não pertence.

Temos também o conjunto vazio Ø, {} , conjunto sem elemento. E o conjunto universo U , conjunto que contém todos os elementos dos conjuntos do contexto que estamos trabalhando.

Usaremos como exemplo os seguintes conjuntos A={1, 2, 3} e B={2, 4, 6}
Sendo A e B conjuntos definimos:

1 ) A, união com B: A∪B={x : x∈AVx∈B} = A ou B = {1, 2, 3, 4, 6}
2 ) A, intersecção com B: A ∩ B ={x : x ∈A Λx ∈B} = A e B = {2}
3 ) A, menos (diferença) B: A – B ={x : x ∈A Λx ∉B} = A-B = {1, 3}

Subconjuntos:
A ⊆B ⇔∀x ∈A ⇒x ∈B(A está contido em B).
Dois conjuntos são iguais A = B,se:A ⊆B ∧ B ⊆A.
Se A ⊆ B mas A ≠ B então A é um subconjunto próprio de B, denotando-se: A ⊂B

Propriedades de conjuntos: quaisquer que sejam os conjuntos, as proposições abaixo serão verdadeiras:

Reflexiva: A∪A = A e A ∩ A = A, não vejo a necessidade de provar.

Inclusão: A ⊂ A∪B, B ⊂ A∪B, A∪B ⊂ A, A∪B ⊂ B.
Provando: A ⊂ A∪B
Tendo que A ⊂ B = se x∈A, então x∈B.
Solução: seja a x∈A qualquer, então x∈A(p), então x∈A(p) ou x∈B(q).
p→(p v q) é verdade, então x⊂ A∪B, logo A ⊂ A∪B C.Q.D

Um conjunto vazio é um elemento neutro para união:
A ∪ Ø = A
Um conjunto vazio e um elemento nulo para intersecção:
A ∩ Ø = Ø
Logo podemos afirmar que se A ∩ B = Ø, então A – B = A.

Conjunto de partes
Definição:
Seja A um conjunto, definimos.
P(A) = {x: x⊂A}
Sendo A={1,2}, seu conjunto de partes é igual a { Ø , {1}, {2}, {1,2}}
P(A) = { Ø , {1}, {2}, {1,2}}
Se A tem n elementos, o conjunto de partes tem 2 elevado a n (sendo n o número de elementos de A).
Logo sendo B={1, 2, 3} o conjunto de partes terá 8 elementos
P(B) = { Ø , {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3}, {1, 2, 3}}

Relações: uma relação é um subconjunto do produto cartesiano de dois ou mais conjuntos:
Para entendermos melhor faremos a prova das seguintes relações:
P(A ∩ B) = P(A) ∩ P(B)
Solução:
por demostrar P(A ∩ B) ⊂ P(A) ∩ P(B)
:.x⊂A e x⊂B
:.x∈P(A) e x∈P(B)
:.x∈P(A) ∩ P(B)
logo P(A ∩ B) ⊂ P(A) ∩ P(B)

Demostração pelo absurdo:

Prove que A ∩ Ø = Ø
seja x∈A e x∈ Ø então … (não tem como provar dessa forma desmembrando).
A⊂ Ø e Ø⊂A se e somente se:
(A⊂Ø) → (A ∩ Ø = Ø)
para provar a proposição acima usamos a demostração pelo absurdo que consiste em supor falso o predica a ser provado. A partir desse devemos chegar a uma contradição, logo o suposto falso será verdadeiro.
Assim supondo que A ∩ Ø ≠ Ø, temos se que existe pelo menos um elemento x∈A ∩ Ø, então x∈A e x∈Ø logo x∈A ∩ Ø (contradição)
Ø∉Ø

então:
A ∩ Ø ≠ Ø, é falso

isto é: A ∩ Ø = Ø é verdadeiro

como demonstrado acima, quando tem um conjunto que não tem como provar desmembrado. Nega se o operador principal para termos a demostração pelo absurdo.

É isso aí, esse é o nosso pequeno resumo do que será necessário relembrar no próximo semestre. Na próxima postagem falaremos sobre indução matemática, até lá e bons estudos.

Thiago Amorim

Matemática Discreta

Vamos ver nesta séria de postagens, alguns conceitos contidos e estudados na matemática discreta e que provavelmente serão passados no semestre 2009/2. O conceito visto nesse primeiro artigo, será teoria de conjuntos, isso mesmo, aquele assunto que nós “aprendemos” nas últimas séries de ensino médio.
Além do que veremos nessa sequência de artigos os demais assuntos:

1 – Conjuntos e Relações (operações) => Estruturas / bases de dados

2 – Indução Matemática

3 – Funções => Estruturas / bases de dados

4 – Lógica proposicional e cálculos de predicados => Inteligência artificial

5 – Contagem => segurança / criptografia

6 – Grafos => topologias de redes e arquitetura de computadores paralelos