Matemática Discreta [Jorge Cavalcanti]

1

Universidade Federal do Vale do São FranciscoCurso de Engenharia da Computação

Prof. Jorge [email protected]

www.univasf.edu.br/~jorge.cavalcanti

www.twitter.com/jorgecav

Matemática Discreta Matemática Discreta -- 0101

Matemática Discreta - Prof. Jorge Cavalcanti - Univasf

2

Matemática Discreta

� Apresentação da Disciplina

� Dicas de (boa) convivência acadêmica� Conteúdo da Disciplina:

1. Introdução/Conceitos Básicos2. Noções de Lógica3. Demonstrações e teoremas.4. Indução e Recursão5. Teoria de conjuntos e cardinalidade de conjuntos6. Conjuntos enumeráveis7. Relações8. Funções parciais e totais9. Funções de Hash10. Teoria dos Grafos e Árvores11. Introdução a Álgebra de Boole12. Conceitos básicos de Teoria das Categorias


3

Matemática Discreta

� Avaliação: 3 + Final.� Material disponibilizado na página

www.univasf.edu.br/ ~jorge.cavalcanti.

� Bibliografia:� Básica

� Fundamentos Matemáticos para a Ciência da Computação. Gersting, J. L., 5 Ed.,LTC.

� Complementar� Matemática Discreta Uma Introdução. Scheineman. E. R.,

Ed. Pioneira Thomson.� Matemática Discreta. Menezes, P.B., 2 Ed. Sagra Luzzato.� Teoria das Categorias. Menezes, P. B., Haeuler, E. H., 2

Ed. Sagra Luzzato.


4

Introdução

� Por que “Matemática Discreta?”� Discreto x contínuo (intervalo números reais)

� Recursos computacionais finitos (conjuntos contáveis)

� Objetivos:� Desenvolver a capacidade de raciocínio lógico-matemático;

� Obter uma visão abrangente de uma parte significativa da computação;

� Aplicar os conceitos da disciplina como uma ferramenta matemática para investigações e aplicações precisas em computação;

� Abordar problemas aplicados e enfrentar ou propor com naturalidade novas tecnologias.


5

Introdução

� Tratamento de Problemas:

Lógica

Teoremas+

Demonstrações

Computação

Algoritmos+

Implementações


6

Conceitos Iniciais:� A Lógica tem, por objeto de estudo, as leis gerais do pensamento,

e as formas de aplicar essas leis corretamente na investigação da verdade.

� Aristóteles - filósofo grego - 342 a.C, sistematizou os conhecimentos existentes em Lógica, elevando-os à categoria de ciência.

� Em sua obra chamada Organum (“ferramenta para o correto pensar”), estabeleceu princípios tão gerais e tão sólidos que até hoje são considerados válidos.

� Para descrever o mundo, usamos sentenças declarativas tais como:i. Toda mãe ama seus filhosii. Maria é mãe e Paulo é Filho de Maria

� Aplicando algumas regras gerais de raciocínio, podemos concluir a partir dessas afirmações:iii. Maria ama Paulo

Introdução à Lógica Formal


7

Conceitos Iniciais:� Proposição: É uma construção (frase, sentença,

pensamento) à qual se pode atribuir juízo.� O juízo atribuído é que a sentença pode ser falsa ou

verdadeira.� Ex.: Verificar se são proposições:

1. Dez é menor que sete.2. Como está você?3. 3 + 4 > 54. Existe vida em outros planetas.5. Parabéns!

� Proposições compostas: Duas ou mais proposições podem sem agrupadas usando os conectivos lógicos.� Linux é um sistema operacional e Java é uma linguagem de

programação.� Vou comprar uma camisa azul ou branca.� Se chover hoje, então não terá o show.



8


� O conectivo lógico e é representado pelo símbolo ∧ e as proposições são representadas por letras maiúsculas.

� Se A e B são proposições verdadeiras, então A ∧ B deve ser considerada verdadeira.

� Podemos então apresentar a tabela com os valores lógicos de A ∧ B para todos os valores lógicos possíveis dos elementos A e B.� Cada linha da tabela representa um possível valor lógico

associado a cada uma das letras de proposição e apresenta o valor lógico resultante da expressão composta.

� Essa tabela é chamada de tabela verdade.

A B A ∧∧∧∧ B

V V VV F FF V FF F F


9


� Um outro conectivo lógico é a palavra ou, simbolizado por ∨ ∨ ∨ ∨, que representa a disjunção.

� A tabela abaixo apresenta os valores lógicos de A ∨ B para todos os valores lógicos possíveis dos elementos A e B.

� ∧∧∧∧ e ∨∨∨∨ são conectivos lógicos binários, pois juntam duas expressões.

A B A ∨∨∨∨ B

V V V

V F V

F V V

F F F


10


� A negação de uma proposição é construída colocando a palavra não de forma apropriada ou prefixando-se a proposição “não é fato que”.� Brasil não é um país livre;� Não é fato que o Windows seja um software livre.

� A negação de A é representada por A’ ou por ¬A (lida como “não A”).

� A negação de uma proposição deve ser feita com cuidado. Por exemplo:

A A’

V ?F ?

Proposição Negação incorreta Negação Correta

Pedro é alto e magro Pedro é baixo e gordo Pedro é baixo ou gordoPedro não é alto ou não é magro


11


� Proposições podem ser combinadas na forma “se proposição A, então proposição B”.� O conectivo lógico é o condicional (ou implicação)� A proposição composta é denotada por A → B (A implica B). � A é a proposição antecedente e B é a proposição consequente.� A proposição composta A → B é falsa quando A é verdadeira e

B é falsa. Caso contrário é verdadeira.� A tabela verdade do conectivo condicional é a seguinte:

A B A →→→→ B B →→→→ A

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


12


� O conectivo bi-condicional (ou equivalência) é simbolizado por ↔.� A expressão A ↔ B é uma abreviação de:

(A → B) ∧ (B → A)� Conforme a tabela abaixo, A ↔ B é verdadeira

somente quando A e B têm os mesmos valores lógicos.

A B A →→→→ B B →→→→ A A ↔↔↔↔ B

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


13


� Resumindo...� Para a compreensão do raciocínio lógico, a tabela abaixo é

essencial.

A B A →→→→ B B →→→→ A A ↔↔↔↔ B A’

V V V V V FV F F V FF V V F F VF F V V V


14


Fórmulas Lógicas� Podemos encadear letras de proposição, conectivos e

parênteses (colchetes), para forma novas expressões como:(A → B) ∧ (B → A)

� Uma cadeia deve formar uma expressão válida (fbf).� Fórmulas atômicas são as que não podem ser decompostas

em proposições mas simples (A → B) . � Ordem de precedência:

1. Conectivos dentro dos parênteses, do mais interno para o mais externo.

2. Negação ‘3. Conjunção ∧ e Disjunção ∨4. Condição →5. Bicondição ↔

� Ex.: A ∨ B’ = A ∨ (B’) e não (A ∨ B’)� A ∧ B → C = (A ∧ B) → C e não A ∧ (B → C)


15


Fórmulas Lógicas� Letras maiúsculas perto do final do alfabeto (P, Q, R, S) são

usadas para representar fbfs, para abstrairmos detalhes da fórmula em dado momento:

((A ∨ B) ∧ C) → (B ∨ C’) Podemos representar simplesmente por

P → Q� No caso acima, o conectivo principal é o → . Na construção

das tabelas verdade, esse conectivo aparece na última coluna da tabela.

� Para se escrever tabelas verdades para qualquer fbf, a partir dos seus componentes, deve-se explicitar todos os valores lógicos possíveis das fórmulas.

� Para cada tabela, são necessárias 2n linhas, onde n é o numero de fórmulas atômicas.


16


Tabelas Verdade� O número de linhas é igual ao número de

combinações V/F possíveis entre as letras da proposição.


17


Tabelas Verdade� Ex 01. Construir a tabela-verdade para a fórmula:

A ∨ B’ → (A ∨ B)’� Conectivo principal : →� Número de linhas: 22 = 4� Fazendo P = A ∨ B’ e Q =(A ∨ B)’

A B B’ A ∨∨∨∨ B’ A ∨∨∨∨ B (A ∨∨∨∨ B)’ P → Q

V V

V F

F V

F F


18



(A → B) ↔ (B → A)� Conectivo principal : ↔� Número de linhas: 22 = 4� Fazendo P = (A → B) e Q =(B → A)

A B A →→→→ B B →→→→ A P ↔ Q

V V

V F

F V

F F


19



(A ∨ A’) → (B ∧ B’)� Conectivo principal : � Número de linhas: � Fazendo P = e Q =

A B

V V

V F

F V

F F


20



(A → B) ↔ (B’ → A’)� Conectivo principal : � Número de linhas: � Fazendo P = e Q =

A B

V V

V F

F V

F F


21


Tautologia e Contradição� Uma fbf que assume sempre o valor V (Ex.:04) é

denominada de tautologia.� O exemplo mais simples de uma tautologia é A ∨ A’� Podemos representar pelo valor 1

� Uma fbf cujo valor lógico é sempre falso (Ex.: 03) é uma contradição.� O exemplo mais simples de uma contradição é A ∧ A’� Podemos representar pelo valor 0

� Se P ↔ Q for uma tautologia, P e Q são ditas equivalentes, denotando essa propriedade por: P ⇔ Q.


22


Equivalências Tautológicas

� Note que em 2a e 2b podemos escrever a fórmula sem a necessidade de parênteses.


23


Leis de De Morgan� Duas equivalências adicionais muito úteis foram

enunciadas pelo matemático inglês Augusto de Morgan (Séc XIX).

(A ∨∨∨∨ B)’ ⇔⇔⇔⇔ A’ ∧∧∧∧ B’

(A ∧∧∧∧ B)’ ⇔⇔⇔⇔ A’ ∨∨∨∨ B’

� Importante!! Resolver exercícios livro-texto.


24


Conectivos Lógicos no Mundo Real

� O uso de conectivos é a base para construção de circuitos lógicos digitais.

� O uso adequado de conectivos pode facilitar buscas em mecanismos de busca na rede, assim como restringir os inúmeros resultados.� Ex: carros usados� “carros usados”� “carros usados” e Ford� “carros usados” e (Ford ou Fiat) e Não caminhões� Ver Google QuickRef (Links na pagina pessoal ou

http://migre.me/4yCB)

� Os conectivos lógicos E (and), OU (or) e NÃO (Not) estão disponíveis em muitas linguagens de programação.

1





Matemática Discreta - 02

2

Argumento� O objetivo de um argumento é justificar uma

afirmação que se faz, ou dar as razões para uma certa conclusão obtida.

Exemplo:

Você me enganou. Pois, disse que ia estudar e meu irmão lhe viu jogando bola.

� Um argumento demonstra/prova como a partir dos dados de um problema chegou-se a uma conclusão.

Lógica Proposicional


3

� Para convencer que você sabe a resposta (que não é um chute!) você tem de expor as razões que o levaram a conclusão (justificar).

Pontos de Partida

Caminhos Seguidos

Conclusão

� Um argumento poderia ser considerado uma reconstrução explícita do raciocínio efetuado

Raciocínio ou

Processo de Inferência

Argumento - Raciocínio e Inferência


4

� Inferência é a relação que permite passar das premissas para a conclusão (um “ encadeamento lógico”)

� A palavra inferência vem do latim, Inferre, e significa “conduzir para”.

� O objeto de estudo da lógica é determinar se a conclusão de um argumento é ou não decorrente das premissas (uma inferência).

Argumento - Raciocínio e Inferência


5

� Em um argumento válido, as premissas são consideradas provas evidentes da verdade da conclusão, caso contrário não é válido.

� Quando é válido, podemos dizer que a conclusão é uma consequência lógica das premissas, ou ainda que a conclusão é uma inferência decorrente das premissas.

Validade de um Argumento


6


� As formas simbólicas como fbfs em lógica formal para representar proposições são chamadas fbfs proposicionais.

� Usando ferramentas da lógica formal, podemos chegar a conclusões de proposições dadas.

� O sistema formal que usa fbfs proposicionais é chamado de lógica proposicional, lógica declarativa ou cálculo proposicional.

� Argumentos Válidos: um argumento pode ser representado em forma simbólica como:

P1 ∧∧∧∧ P2 ∧∧∧∧ P3 ∧∧∧∧ ... ∧∧∧∧ Pn →→→→ Q

� P1, ...Pn são as proposições dadas, chamadas de hipótesesdo argumento e Q é a conclusão do argumento.

� P e Q representam fbfs e não somente letras de proposição.� Quando um argumento pode ser considerado válido?


7


� Q é uma conclusão lógica de P1, ...Pn sempre que a verdade das proposições P1, ...Pn implica na verdade de Q.

� Uma fbf proposicional P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q é um argumento válido quando for uma tautologia.

� Para testarmos se P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q é uma tautologia, podemos construir uma tabela verdade, ou mais simplificadamente, utilizaremos um sistema de regras de dedução.� Essas regras modificam uma fbf sem modificar seu valor

lógico.� Começando a partir das hipóteses P1, ...Pn (supostas

verdadeiras) para se chegar à conclusão Q verdadeira.


8


� Uma sequência de demonstração é uma sequência de fbfs nas quais cada fbf é uma hipótese ou resultado de se aplicar uma das regras de dedução às fbfs anteriores na sequência.

� Usando lógica formal para provar que Q é uma conclusão válida de P1, ...Pn, vamos produzir uma sequência de demonstração da forma:

P1 (hipótese)P2... (hipótese)Pn (hipótese)fbf1 (obtida aplicando-se uma regra de dedução às anteriores)fbf2...Q (obtida aplicando-se uma regra de dedução às anteriores)


9


Regras de Dedução para a Lógica Proposicional

� Dois tipos: equivalências e inferência.� As regras de equivalência permitem que fbfs

individuais sejam reescritas mantendo o mesmo valor lógico.

� As regras de inferência permitem a dedução de novas fbfs a partir de fbfs anteriores na sequência de demonstração.

� As regras de equivalência dizem que determinados pares de fbfs são equivalentes (R⇔S, onde R↔S é uma tautologia).� R pode ser substituído por S sem mudança do valor lógico.

As regras preservam os valores


10


(*) Demonstrar.

Expressão Equivalente a Nome/Abreviação

P ∨∨∨∨ Q

P ∧∧∧∧ Q

Q ∨∨∨∨ P

Q ∧∧∧∧ P

Comutatividade / Com

(P ∨∨∨∨ Q) ∨∨∨∨ R

(P ∧∧∧∧ Q) ∧∧∧∧ R

P ∨∨∨∨ (Q ∨∨∨∨ R)

P ∧∧∧∧ (Q ∧∧∧∧ R)

Associatividade / Ass

(P ∨∨∨∨ Q)’

(P ∧∧∧∧ Q)’

P’ ∧∧∧∧ Q’

P’ ∨∨∨∨ Q’

Leis de De Morgan / De Morgan

P →→→→ Q P’ ∨∨∨∨ Q Condicional / Cond (*)

P (P’)’ Dupla negação / Dn

P ↔↔↔↔ Q (P→→→→Q) ∧∧∧∧(Q→→→→P) Equivalência / Equi

Regras de Equivalência


11


12


� Ex.: Suponha que uma hipótese de um argumento proposicional pode ser simbolizada como

(A’ ∨ B’) ∨ C� Então, o primeiro passo de uma sequência de

demonstração para o argumento poderia ser:1. (A’ ∨ B’) ∨ C (Hip)2. (A ∧ B)’ ∨ C (De Morgan)3. (A ∧ B) → C (Cond)

Regras de Equivalência


13


� Se uma ou mais fbfs fazem parte de uma sequência de demonstração, então podemos adicionar uma nova fbf na sequência, substituindo uma anterior por uma nova fbf correspondente.

� Ao contrário das regras de equivalência, as regras de inferência não funcionam em ambas as direções.

� A idéia básica de se utilizar inferência é da dedução de novas proposições a partir de proposições já conhecidas.

Regras de Inferência


14



De Podemos Deduzir Nome/Abreviação

P, P →→→→ Q Q Modus ponens / mp

P →→→→ Q, Q’ P’ Modus Tollens / mt

P, Q P ∧∧∧∧ Q Conjunção / conj

P ∧∧∧∧ Q P, Q Simplificação / simp

P P ∨∨∨∨ Q Adição / ad

Ex.: P P →→→→ Q Q

V V ?V F ?F V ?F V ?

• Se P, então Q.• P.• Portanto Q.

1. Se chover, então fico em casa.2. Choveu.3. Portanto fico em casa.


15



Ex.: P →→→→ Q Q’ P’

V F F

• Se P, então Q.• Q é falso.• então P é falso

1. Se existe fogo aqui, então tem

oxigênio

2. Não há oxigênio aqui

3. Então aqui não há fogo


16



Ex.:1. A→(B∧C) - hip2. A - hip3. B ∧ C – 1,2 mp

Ex.:1. (A∧B’) → C - hip2. C’ - hip3. (A∧B’)’ – 1,2 mt

� Para usar uma regra de dedução, as fbfs tem que ter a mesma forma descrita na regra.

Ex.:1. (A→B) ∨ C - hip2. A - hip3. ? (mp não se aplica)


17


� Usando a lógica proposicional, provar que o argumento abaixo é válido.

A ∧(B→C) ∧ [(A ∧ B)→(D ∨ C’)] ∧ B → D1. A hip2. B→C hip3. (A ∧ B)→(D ∨ C’) hip4. B hip5. C 2,4, mp6. A ∧ B 1,4, conj7. D ∨ C’ 3,6, mp8. C’ ∨ D 7, com9. C→D 8, cond10. D 5, 9, mp


18


� Usando a lógica proposicional, provar que o argumento abaixo é válido.

[(A ∨ B’)→ C)] ∧(C→D) ∧ A → D

1. (A ∨ B’)→ C hip2. C→D hip3. A hip4. A ∨ B’ 3, ad5. C 1,4, mp6. D 2,5, mp


19


Exercícios

� Usando a lógica proposicional, provar que os argumentos abaixo são válidos.

a) (A’ → B) ∧∧∧∧ A’ ∧∧∧∧ (B’ V C) → Cb) (A ∧∧∧∧ C’ → B’) ∧∧∧∧ A ∧∧∧∧ C’ → B’c) (A’ → B’) ∧∧∧∧ B ∧∧∧∧ (A → C) → C

• Regra de equivalência - Contraposição


20


Sugestões de Dedução

� Modus ponens é a regra mais intuitiva e deve ser usada muitas vezes.

� Fbfs da forma (P ∧ Q)’ e (P ∨ Q)’ dificilmente são úteis em uma sequência de demonstração. Usar as leis de De Morgan para convertê-las em P’ ∨ Q’ e P’ ∧ Q’ respectivamente.

� Fbfs na forma P ∨ Q também não são úteis em sequências de demonstração. Usar a dupla negação para converter P ∨ Q em (P’)’ ∨ Q e depois usar a condicional para obter P’ → Q.


21


Métodos Dedutivos e Outras Regras

� Suponha que o argumento que queremos provar tem a forma:

P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → (R → S)� A conclusão é uma implicação. Mas, ao invés de

usar P1, ...Pn como hipóteses e inferir R → S, o método dedutivo nos permite adicionar R como hipótese adicional e depois inferir S, na seguinte forma:

P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn ∧ R → S� A vantagem é que nos dá mais uma hipótese para

demonstração.


22


� Use a lógica proposicional, usando o método dedutivo, para provar que o argumento abaixo é válido.

[A →→→→(A →→→→ B)] →→→→ (A →→→→ B)

[A →(A → B)] ∧ A → B

1. A →(A → B) hip2. A hip3. A → B 1,2, mp4. B 2,3, mp


23


� Use a lógica proposicional, usando o método dedutivo, para provar que o argumento abaixo é válido.

(A →→→→ B) ∧∧∧∧ (B →→→→ C) →→→→ (A →→→→ C)

(A → B) ∧ (B → C) ∧ A → C1. A → B hip2. B → C hip3. A hip4. B 1,3, mp5. C 2,4, mp� A demonstração acima descreve a regra para o

Silogismo Hipotético.


24


Silogismo Hipotético

� De P → Q e Q → R pode-se deduzir P → R.� De maneira formal:

(P →→→→ Q) ∧∧∧∧ (Q →→→→ R) →→→→ (P →→→→ R)

� Por ser uma outra regra de dedução legítima, o silogismo hipotético pode ser usado em um passo de uma demonstração.

� Ex.: Demonstrar a validade do argumento abaixo.(A’ ∨ B) ∧∧∧∧ (B → C) → (A → C)1. A’ ∨ B hip2. B → C hip3. A → B 1, cond4. A → C 2,3, sh


25


Silogismo Disjuntivo

� De P ∨∨∨∨ Q e P’, pode-se deduzir Q.� De maneira formal:

(P ∨∨∨∨ Q) ∧∧∧∧ P’ →→→→ Q

� É outra regra de dedução adicional, chamada de silogismo disjuntivo, que pode ser usada em um passo de uma demonstração.

� Ex.: Demonstrar a validade do argumento abaixo.(A ∨ B) ∧ A’ → B1. A ∨ B hip2. A’ hip3. A’ → B 1, cond4. B 2,3, mp


26


Argumentos Verbais

� Um argumento verbal formado por declarações simples, pode ser testado logicamente por um processo de duas etapas:1. Simbolize cada declaração usando fbfs proposicionais.2. Prove a validade do argumento construindo uma sequência de

demonstração através das regras de dedução.

� Considere o argumento: “Se as taxas de juros caírem, o mercado imobiliário vai melhorar. Ou a taxa federal de descontos vai cair, ou o mercado imobiliário não vai melhorar. As taxas de juros vão cair. Portanto, a taxa federal de descontos vai cair.”� Definir a notação do argumento em lógica proposicional e

provar a validade do argumento, por sequência de demonstração.


27


“Se as taxas de juros caírem, o mercado imobiliário vai melhorar. Ou a taxa federal de descontos vai cair, ou o mercado imobiliário não vai melhorar. As taxas de juros vão cair. Portanto, a taxa federal de descontos vai cair.”

Usando a notação:J A taxa de juros vai cair.I O mercado imobiliário vai melhorar.F A taxa federal de descontos vai cair.

O argumento fica:(J → I) ∧ (F ∨ I’) ∧ J → F

1.J → I hip2.(F ∨ I’) hip3.J hip4.I’ ∨ F 2, com5.I → F 4, cond6.J → F 1,5, sh7.F 3,6 mp


28


Nos exercícios abaixo que regra de inferência é ilustrada pelo argumento dado.

1) Se Martins é o autor, então o livro é de ficção. Mas o livro não é de ficção. Portanto, Martins não é o autor.

2) Se a firma falir, todos os seus bens tem que ser confiscados. A firma faliu. Então todos os bens foram confiscados.

3) Se Paulo é um bom nadador, então ele é um bom corredor. Se Paulo é um bom corredor, então ele é um bom ciclista. Portanto, se Paulo é um bom nadador, então ele é um bom ciclista.


29


Nos exercícios abaixo que regra de inferência é ilustrada pelo argumento dado.

4) A condição suficiente para que a caixa d’água encha é que a válvula esteja aberta. Sabe-se que a válvula está aberta. Portanto a caixa d’água vai encher.

5) A moqueca não pode ser feita nem de Baiacu e nem de Cação. Isto é equivalente a dizer que é falso afirmar que: a moqueca é feita de Baiacu ou de Cação.

6) Se o show deu muita gente então é porque fez sol. Mas, sabe-se que não fez sol. Portanto o show não deu muita gente.


30


Ex.: Verifique a validade do argumento: “Meu cliente é canhoto mas, se o diário não tiver sumido, então meu cliente não é canhoto; portanto, o diário sumiu.”

Usando a notação:C Meu cliente é canhotoD O diário sumiu.

O argumento fica: C ∧ (D’ → C’) → D1.C hip2.(D’ → C’) hip3.(D’)’ ∨ C’ 2, cond4.D ∨ C’ 3, dn5.C’ ∨ D 4, com6.C → D 5, cond7.D 1,6 mpObs: A validade do argumento é uma função apenas do seu formato lógico e não tem nada a ver com a verdade fatual de nenhum dos seus componentes.


31


Ex.: Verifique a validade do argumento: “Se a segurança é um problema, então o controle será aumentado. Se a segurança não é um problema, então os negócios na internet irão aumentar. Portanto, se o controle não for aumentado, os negócios na internet crescerão.”

Usando as letras de proposição S, C, N:



32

� Você foi convocado a participar de um júri em um processo criminal. Jason está sendo acusado de um crime.

� O advogado de defesa faz o seguinte argumento:Se meu cliente fosse culpado, a faca estaria na gaveta. Ou a faca não estava na gaveta ou Jason viu a faca. Se a faca não estava lá no dia 10 de outubro então Jason não viu a faca. Além disso, se a faca estava lá no dia 10 de outubro, então a faca estava na gaveta e o martelo estava no celeiro. Mas todos sabemos que o martelo não estava no celeiro. Portanto, senhoras e senhores, meu cliente é inocente.

� O argumento do advogado está correto? –Verifique a validade do argumento.

� Como você votaria?

1






2

Quantificadores, predicados e validade� Fbfs proposicionais tem uma possibilidade limitada de

expressão.� A expressão “Para todo x, x>0” pode ser considerada uma

proposição verdadeira sobre os inteiros positivos.� Porém ela não pode ser simbolizada adequadamente usando

apenas letras, parênteses e conectivos lógicos.� Para expressões desse tipo, é necessário o uso de

quantificadores e predicados.� Quantificadores são representações de expressões do tipo

“para todo”, “para cada”, isto é frases que dizem quantos objetos tem determinada propriedade.

� O quantificador universal (para todo, para cada etc.) é representado por ∀∀∀∀.

� A sentença acima ficaria (∀x)(x>0).� O quantificador age sobre a expressão dentro do segundo

parênteses.


3

Quantificadores, predicados e validade� A frase “x>0” descreve uma propriedade da

variável x de ser positiva.� Uma propriedade é chamada de predicado.� A notação P(x) é usada para representar alguma

propriedade ou predicado, não explicitada, que a variável x possa ter.

� A expressão anterior assume a seguinte forma geral:(∀x)P(x)

� O valor lógico da expressão depende do domínio dos objetos que estamos referenciando.� Se o domínio for o conjunto dos inteiros positivos, a

expressão tem valor lógico verdadeiro.� Caso contrário, por exemplo, todos os inteiros, a

expressão teria valor falso.


4

Quantificadores, predicados e validade� O quantificador existencial é simbolizado por ∃ e

se lê “existe”, “há pelo menos um”. � Assim, a expressão

(∃x)(x > 0)� Pode ser lida “existe um x tal que x é maior que zero”.� Generalizando a expressão anterior:

(∃x)P(x)

� O valor lógico da expressão depende do domínio dos objetos que estamos referenciando.� Se o domínio contiver um número inteiro positivo, a

expressão tem valor lógico verdadeiro.� Caso contrário, a expressão terá valor falso.


5

Quantificadores, predicados e validade� Os predicados vistos até agora, que envolvem apenas uma

variável, são chamados de unários.� Os predicados também podem ser binários, ternários e

n-ários.

� A expressão (∀x)(∃y)Q(x,y), lida como “para todo x existe um y tal que Q(x,y)”, contém dois quantificadores para as duas variáveis da propriedade binária.� A ordem dos quantificadores é importante.

� Podemos ter constantes nas expressões (qualquer que seja o número de variáveis), como objeto específico do domínio. Ex. (∀x)Q(x,a).


6

Quantificadores, predicados e validade

Observações:

� A ordem dos quantificadores é importante:

� Seja Q(x,y) a propriedade x<y, para todos os inteiros:� (∀x)(∃y)Q(x,y) - Para todo inteiro x, existe um y maior que ele.

� (∃y)(∀x)Q(x,y) – Existe um inteiro y que é maior que todo x.

7

Interpretação� Uma interpretação para uma expressão envolvendo

predicados consiste em:� Uma coleção de objetos, chamada de conjunto universo ou

domínio da interpretação, incluindo pelo menos 01 objeto.� A especificação de uma propriedade dos objetos do domínio

para cada predicado da expressão.� A atribuição de um objeto particular no conjunto universo para

cada símbolo constante na expressão.

� Ex.01 – Dê uma interpretação (isto é, o conjunto universo e o significado de P(x)) para qual (∀x)P(x) tem o valor verdadeiro.

� Ex.02 – Dê uma interpretação para qual (∀x)P(x) tem o valor falso.

� Ex.03 – É possível encontrar uma interpretação na qual, ao mesmo tempo, (∀x)P(x) seja V e (∃x)P(x) seja F?


8

� Assim com temos as fbfs proposicionais, que agrupam colchetes, parênteses, letras e conectivos, temos as fórmulas que agrupam predicados e quantificadores.� Essas fórmulas são chamadas de fbfs predicadas.� Seguem regras de sintaxe para ser considerada fbfs.1. P(x) ∨∨∨∨ Q(y)2. (∀x)[P(x)→Q(x)]3. (∀x)((∃y)[P(x,y) ∧ Q(x,y)] →R(x))4. (∃x)S(x) ∨∨∨∨ (∀x)T(y)� Os símbolos entre colchetes e parênteses identificam o escopo

de um quantificador, isto é, a parte da fbf onde o quantificador se aplica.� Em 1, não existe escopo. Em 2, o escopo de (∀x) é [P(x)→Q(x)].� Em 3, o escopo de (∃y) é P(x,y) ∧ Q(x,y) e o de (∀x) é a

expressão inteira que o segue.


9

Tradução� Muitas declarações em português podem ser

expressas como fbfs predicadas.� “Todo papagaio é feio”, significa que “dada uma coisa, se

é um papagaio, então é feio”.� Usando P(x) para a frase “x é um papagaio” e por F(x) “é

feio”, a proposição pode ser simbolizada como(∀x)[P(x)→F(x)]

� O quantificador ∀∀∀∀ e o conectivo →→→→ estão quase sempre juntos.� Analogamente, “Existe um papagaio feio” significa que

“Existe alguma coisa que é, ao mesmo tempo, papagaio e feio”, que pode ser representado por:

(∃x)[P(x)∧F(x)]� O quantificador ∃∃∃∃ e o conectivo ∧∧∧∧ estão quase

sempre juntos.


10

Tradução� Para traduzir uma declaração em português para

uma fbf, pode ser útil escrever primeiro alguma proposição intermediária em português e depois simbolizar essa proposição.

� Advérbios “só”, “somente”, “apenas” podem confundir a tradução, pois sua colocação na sentença pode alterar completamente o significado.� João ama apenas Maria.� Apenas João ama Maria.� João apenas ama Maria.


11

Tradução� Ex.: Usando os símbolos predicados abaixo,

escreva as fbfs que representam as proposições logo a seguir (o domínio consiste em todas as pessoas):� E(x) é “x é um estudante”� I(x) é “x é inteligente”� M(x) é “x gosta de música”

� Proposições:a. Todos os estudantes são inteligentes.b. Alguns estudantes inteligentes gostam de música.c. Todo mundo que gosta de música é um estudante burro.d. Apenas estudantes inteligentes gostam de música.


12

� Ex.: Usando os símbolos predicados indicados e quantificadores apropriados, escreva cada declaração em português como uma fbf predicada: B(x): x é uma bola.R(x): x é redondo.S(x): x é uma bola de futebol

a) Todas as bolas são redondas.b) Nem todas as bolas são bolas de futebol.c) Todas as bolas de futebol são redondas.d) Algumas bolas não são redondas.e) Toda bola redonda é uma bola de futebol.

Tradução

13

Validade� O valor lógico de uma fbf proposicional depende dos

valores lógicos atribuídos às letras de proposição.� O valor lógico de uma fbf predicada depende da

interpretação.� Escolher uma interpretação para uma fbf predicada é

análogo a escolher valores lógicos para uma fbf proposicional.� Entretanto, existe uma infinidade de interpretações

possíveis de uma fbf predicada e apenas 2n linhas possíveis em uma tabela verdade.

� Uma tautologia é uma fbf proposicional que assume o valor verdadeiro em todas as linhas da tabela verdade.

� O análogo de uma tautologia para uma fbf é a validade.


14

Validade� Uma fbf predicada é válida se ela é verdadeira

para todas as interpretações possíveis� A validade deve ser deduzida de sua forma, já que a

validade é independente de qualquer interpretação particular.

� Uma fbf válida é intrinsecamente verdadeira.

� Como definir a validade de uma fbf predicada?� Não existe algoritmo para definir a validade.� Necessidade de determinar se a forma de uma fbf torna-

a verdadeira em todas as interpretações.� Não pode haver valor falso ou alguma proposição sem

valor lógico.


15

Comparação entre Fbfs Proposicionais e Predicadas


Fbfs proposicionais Fbfs PredicadasValores Lógicos V ou F, dependendo

dos valores lógicos atribuídos às letras de proposição.

Verdadeiro, falso ou talvez (se a fbf tiver uma variável livre) sem valor lógico, dependendo da interpretação.

“Intrinsecamente verdadeiro”

Tautologia – Verdade para todas as atribuições de valores lógicos.

Fbf Válida – Verdade para todas as interpretações.

Metodologia Tabela Verdade (algoritmo) para determinar de uma fbf é uma tautologia.

Não existe algoritmo para determinar se uma fbf é válida.

� Ex: Determine o valor lógico de cada uma das Fbfs a seguir, com a interpretação de que o conjunto universo consiste em todos os inteiros, I(x) significa “x é ímpar”, L(x) que “x<0” e G(x) que “x >9”. 1. (∃x)(I(x))2. (∀x)L(x) →I(x)3. (∃x)[L(x) ∧ G(x)]4. (∀ x) [L(x) ∨∨∨∨ G(x)]

16

Validade

17

Validade

� Ex: Verificar a validade das fbfs abaixo:1. (∀x)P(x) →(∃x)P(x)2. (∀x)P(x) →P(a)3. (∀x) [P(x) ∧ Q(x)] ↔ (∀x) P(x) ∧ (∀x) Q(x)4. (∃x) P(x) → ( x)P(x)5. (∀x) [P(x) ∨ Q(x)] ↔ (∀x) P(x) ∨ (∀x) Q(x)

� Mais lógica??? Próximos semestres...


1

Universidade Federal do Vale do São Francisco Curso de Engenharia da Computação

Prof. Jorge Cavalcanti

[email protected]




2

Técnicas de demonstração

Teoremas e Demonstrações Informais

Os argumentos lógicos formais tem a forma P Q, onde P e Q podem representar proposições compostas.

Temos que demonstrar a validade do argumento.

As vezes temos que provar argumentos que não são universalmente verdadeiros, sendo apenas em certos contextos.

Temos que provar que, se P é verdadeiro nesse contexto, Q também o é.

Se pudermos provar essa condição, então P Q torna-se um teorema sobre aquele assunto.

Os teoremas podem ser enunciados e demonstrados de maneira menos formal do que usando argumentos da lógica formal.

Teoremas e Demonstrações

3


Um teorema é uma proposição que é garantida

por uma prova.

Um axioma é uma proposição que se assume

como verdadeira e que não precisa de prova.

Uma conjectura é uma proposição que ainda não foi provada e nem refutada.


4


Provar ou Não Provar Raciocínio indutivo – Algo que se conclui baseado na

experiência. Por exemplo, observando que, em diversos casos nos quais

sempre P é verdade, Q também o é, formula-se uma conjectura: Quanto mais verifica-se que Q segue de P, mais confiante que a conjectura é verdadeira.

Raciocínio dedutivo – Verificação de fato se a conjectura é verdadeira. Produzir uma demonstração que P Q, transformando a

conjectura em um teorema.

Ou encontrando um contra-exemplo, mostrando que a conjectura está errada, com um caso onde P é verdadeiro e Q é falso.

Não é simples a decisão de qual a abordagem: provar ou buscar um contra-exemplo.


5


Provar ou Não Provar Ex. 01: Para um inteiro positivo n, n! é definido com sendo

n(n-1)(n-2)...1. Prove ou encontre um contra-exemplo para a conjectura “para todo inteiro positivo n, n! n2.

Testa-se alguns casos:

Até agora a conjectura foi sempre verdadeira. O caso seguinte:


n n! n2 n! n2

1 1 1 V

2 2 4 V

3 6 9 V

n n! n2 n! n2

4 24 16 F

Esse caso é suficiente para

provar a falsidade

Os casos verdadeiros não

provam a validade

6


Demonstração exaustiva

Encontrar um contra-exemplo pode não ser simples. Então o caminho para provar uma conjectura é usar métodos para demonstrá-la.

Quando temos uma conjectura sobre uma coleção finita, ela pode ser provada verificando se ela é válida para cada elemento da coleção.

Uma demonstração por exaustão significa que foram exauridos todos os casos possíveis.

Ex.02: Provar a conjectura: “Se um inteiro entre 1 e 20 é divisível por 6, então também é divisível por 3.”

Como existe um número finito de casos, a conjectura pode ser provada mostrando que é verdadeira para todos os inteiros de 1 a 20, por exemplo, usando uma tabela.


7


Demonstração exaustiva

Ex.03: Provar a conjectura: “Para qualquer inteiro positivo menor ou igual a 5, o quadrado do inteiro é menor ou igual à soma de 10 mais 5 vezes o inteiro.”

Ex.04: Dê um contra-exemplo para a conjectura: “Para qualquer inteiro positivo, o quadrado do inteiro é menor ou igual à soma de 10 mais 5 vezes o inteiro.”


8

Demonstração Direta Uma demonstração ou prova é dita direta quando

pressupões verdadeira a hipótese e, a partir desta, prova ser verdadeira a tese.

Ex.05: Considere a seguinte conjectura: “A soma de dois números pares é um número par”. Podemos efetuar a demonstração direta a partir dos seguintes passos:

1. Reescrevendo na forma P Q: Se n e m são dois números pares quaisquer, então n+m é um número par.

2. Lembrando que um numero par n pode ser definido por n=2r, onde r é um numero inteiro qualquer.

3. Se n e m são pares, então existem r, s tais que: n=2r e m=2s, então: n+m=2r+2s => 2(r+s), como r+ s é um número inteiro, logo, n+m é um número par.


9

Demonstração Direta Ex.06: Considere a seguinte conjectura: “O

produto de dois números inteiros pares é um número par”. Faça a demonstração direta (informal) da mesma.


10

Contraposição Se a demonstração direta P Q, não foi

atingida, pode-se tentar algumas variantes da técnica de demonstração direta.

Se puder provar o teorema Q’ P’, pode-se concluir que P Q, usando a tautologia (Q’ P’) (P Q). Q’ P’ é a contrapositiva de P Q

A técnica de provar P Q através de uma demonstração direta de Q’ P’ é chamada de demonstração por contraposição. A tautologia (Q’ P’) (P Q) vem da regra de

inferência onde P Q pode ser deduzida de Q’ P’.


11

Contraposição Ex. 07: Prove o seguinte teorema (n ):

n! > (n+1) n>2

Por equivalência, pode-se demonstrar por contraposição, que:

n 2 n! (n+1)

Testando a proposição para n=0, 1 e 2.


n n! n+1

0 1 1

1 1 2

2 2 3

12

Contraposição Ex.08: Mostre que se n + 1 senhas diferentes

foram distribuídas para n alunos, então algum aluno recebe 2 senhas. A contrapositiva é “Se todo aluno recebe < 2 senhas,

então não foram distribuídas n + 1 senhas”.


13

Demonstração por absurdo Quando a demonstração de P Q, consiste em

supor a hipótese P, supor a negação de Q e concluir uma contradição (em geral Q Q’), a demonstração é chamada de por absurdo.

Lembrando que uma contradição é uma fbf cujo valor lógico é sempre Falso. Ela pode ser denotada por 0. Por exemplo, a fbf A A’ tem sempre valor falso.

Para provar P Q, podemos levar em conta a seguinte fbf: (P Q’ 0) (P Q). Construindo a tabela verdade, concluímos a que a fbf é

uma tautologia.

Então se provarmos que P Q’ 0, isto implicará em P Q


14

Demonstração por absurdo Portanto, na demonstração por absurdo, assume-

se o oposto do que se quer provar, ao chegar a uma contradição, a prova é finalizada.

Ex.10: Demonstrar por absurdo a proposição: “Se um número somado a ele mesmo é igual a ele mesmo, então esse número é 0”. Representando x por um numero qualquer.

A hipótese é x+x=x e a conclusão é x=0.

Para demonstrar por absurdo, supomos que x+x=x e x0. Então 2x=x e x0.

Dividindo ambos os lados da eq. 2x=x por x, obtém-se 2=1, uma contradição, que buscamos.

Portanto, (x+x=x) (x=0)


15

Demonstração por absurdo Ex.11: Demonstrar por absurdo que o produto de

inteiros ímpares não é par.


16

Resumo das técnicas de demonstração

Técnica Abordagem para provar P Q

Observações

Exaustão Demonstre P Q para todos os casos possíveis

Pode ser usada para provar um número finito de casos.

Direta Suponha P, deduza Q Abordagem padrão – o que se deve tentar em geral.

Contraposição Suponha Q’, deduza P’ Use a técnica se Q’ parece dar mais munição que P.

Por Absurdo Suponha P Q’, deduza uma contradição

Use essa técnica quando Q disser que alguma coisa não é verdade.

1





MatemMatemáática Discreta tica Discreta -- 0505

2

Primeiro Princípio de Indução� Imagine que você está subindo uma escada infinitamente

alta. Como você será capaz de saber se será capaz de chegar a um degrau arbitrariamente alto?� Você pode inicialmente fazer as seguintes hipóteses sobre a

sua capacidade de subir:1. Você consegue alcançar o primeiro degrau.2. Uma vez chegado a um degrau, você sempre será capaz de

chegar ao próximo.� Se a proposição 1 e o condicional 2 são verdadeiros, então,

pela proposição 1, você consegue chegar no primeiro degrau e, portanto, pela 2, consegue chegar no segundo. Novamente pela 2, consegue chegar no terceiro.

� Mais uma vez, pela 2, chega no quarto degrau e assim por diante.

� Você poderá subir tão alto quanto quiser.

Indução

3

Primeiro Princípio de Indução� Nesse caso, ambas as hipóteses são necessárias. Se

apenas a primeira fosse V, não teríamos a garantia de passar do primeiro degrau.� Se apenas a 2ª fosse V, poderíamos não ser capazes de

começar nunca.� Numerando os degraus...

� Seja uma propriedade de que cada número que identifica o degrau possa ter.� Ao invés de chegar a um degrau arbitrário, podemos buscar

um número inteiro positivo que tenha essa propriedade.

Indução

...

3

1

2

4

Primeiro Princípio de Indução� Usando a notação P(n) para dizer que o inteiro positivo n

tem a propriedade P.� Por analogia, vamos usar a mesma “técnica” usada para

subir a escada, para provar que, qualquer que seja o inteiro positivo n, temos P(n).� Precisamos provar as proposições:1. P(1) - (1 tem a propriedade P)2. Para qualquer inteiro positivo k, P(k)→P(k+1) – Se qualquer

número tem a propriedade P, o próximo também tem.

� Se pudermos provar ambas as proposições 1 e 2, então P(n) é válida para qualquer inteiro positivo n.

� O fundamento para argumentos desse tipo é o primeiro princípio de indução matemática.

Indução

5

Primeiro Princípio de Indução

1. P(1)

2. (∀∀∀∀k) [P(k) verdade →→→→ P(k+1) verdade]

Indução

P(n) é verdade para todo inteiro

positivo n

� O primeiro princípio de indução matemática é um condicional, com uma conclusão na forma “P(n) é verdade para todo inteiro positivo n”.� A técnica da indução se mostra mais apropriada para

provarmos que alguma coisa é verdade para todo inteiro positivo n (conjunto dos números naturais).

6

Indução

Primeiro Princípio de Indução

1. P(1)2. (∀k) [P(k) verdade → P(k+1) verdade]� Para mostrar que a conclusão dessa condicional

é verdadeira, precisamos provar que as hipóteses 1 e 2 são.� Para provar a proposição 1, basta mostrar que o

número 1 tem a propriedade P, o que pode ser trivial (Base da Indução).

� A proposição 2 é um condicional que tem que ser válido para todo k (Passo da Indução).

� Para provar essa condicional, suponha que P(k) (Hipótese da Indução) é verdade para um inteiro positivo k e mostre que, baseado nesta hipótese, que p(k+1) é verdade.

7

Indução

Primeiro Princípio de Indução - Resumo

1. Passo 1 – Prove a base da indução P(1) (ou o menor inteiro positivo em questão.

2. Passo 2 – Suponha P(k)3. Passo 3 – Prove P(k+1)

8

Indução

Demonstração por Indução Matemática� Ex. 01:Suponha a árvore genealógica de uma família cuja

característica fundamental é que cada casal tem sempre dois filhos e que cada um desses filhos também tem dois filhos. A árvore é ilustrada abaixo:

...

......

23=83

22=42

21=21

DescendentesGeração

9

Indução

Demonstração por Indução Matemática� Há de se perceber que a geração n contém 2n

descendentes. Precisamos demonstrar essa propriedade.� Formalmente, se denotarmos por P(n) o número de

descendentes em cada geração, nossa conjectura é que:

P(n) = 2n

� Vamos usar a indução para provar que a conjectura estácorreta.

1. O passo básico é estabelecer P(1), que é a equação:

2. Isso é verdadeiro pois o primeiro elemento da genealogia teve 02 filhos.

3. Supondo agora que a conjectura está correta para uma geração arbitrária k, k≥1:

P(1) = 21 = 2

P(k) = 2k Vamos mostrar que P(k+1) = 2k+1

10

Indução

Demonstração por Indução Matemática� Vamos mostrar que P(k+1) = 2k+1

� Nessa família, cada descendente tem 2 filhos, de modo que o número de descendentes na geração k+1 será o dobro da geração k.

� Ou seja P(k+1) = 2P(k)� Pela hipótese de indução:

.

.

.P(k) = 2k

P(k+1) = 2P(k) = 2(2k) = 2k+1

De fato, P(k+1) = 2k+1

11

Indução

Demonstração por Indução Matemática� Ex. 02: Sejam as seguintes definições:

20 = 1 = 21 – 120 + 21 = 1 + 2 = 3 = 22 – 1

20 + 21 + 22 = 1 + 2 + 4 = 7 = 23 – 120 + 21 + 22 + 23 = 1 + 2 + 4 + 8 = 15 = 24 – 1

� No exemplo acima o padrão mais geral parece com:20 + 21 + 22 +…+ 2n = 2n+1 – 1

� Mas, não podemos afirmar que este padrão será sempre verdadeiro para todos os valores de n a menos que provemos.

� Prove que para todo número inteiro positivo n, 20 + 21 + 22 +…+ 2n = 2n+1 – 1.

12

Indução

Demonstração por Indução Matemática� Ex. 02: 20 + 21 + 22 +…+ 2n = 2n+1 – 1.� Pelo princípio da indução:P(1) é a equação 1 + 2 = 21+1 ou 3=22-1 (base da indução)� Supondo P(k) como hipótese de indução:1 + 2 + 22 +…+ 2k = 2k+1 – 1� Provar que P(k+1) é verdadeira:1 + 2 + 22 +… + 2k + 2k+1 = 2k+1+1 – 1Considerando a soma à esquerda 1 + 2 + 22 +… + 2k + 2k+1

Usando a hipótese de indução: 1 + 2 + 22 +…+ 2k = 2k+1 – 1em p(k+1):= 2k+1 – 1 + 2k+1

=2(2k+1) – 1= 2k+1+1 – 1

Portanto P (k+1): 1 + 2 + 22 +… + 2k + 2k+1 =2k+1+1 – 1

13

Indução

Demonstração por Indução Matemática� Ex. 03: Demonstre que, para qualquer n, 2n >n.1. Base da indução: P(1) = 21=2, então 2>1 (verdadeira)2. Hipótese da indução: supondo que para algum k

inteiro positivo, P(k): 2k > k é verdadeira.3. Passo da indução: Provar que para P(k+1): 2k+1> k+1

é verdadeira.4. Como P(k): 2k > k e P(k+1): 2k+1> k+1, então, à

esquerda da desigualdade temos que:

2k+1= 2k.21

Pela hipótese de indução 2k > k (x2) = 2k.21 > k.22k+1>k.2, como k.2=k+k, e k+k ≥ k+1,Ou seja,2k+1> k+1

14

Indução

Demonstração por Indução Matemática� O primeiro passo de uma demonstração por indução

não é necessariamente obrigado ser P(1). Podemos começar por P(0) ou por outro valor.

� O mesmo princípio se aplica, independente do grau que se começa a subir.

� Ex. 04: Prove que n2 >3n, para n ≥4.� Nesse caso, é melhor começar a base da indução em

P(4).1. Base da indução - P(4): 42> 3(4) é verdadeira2. Hipótese da indução - k2 >3k, para k ≥43. Queremos mostrar que (k+1)2 > 3(k+1)(k+1)2=k2+ 2k + 1>3k + 2k +1 (pela hipótese da indução)≥ 3k + 8 + 1 (pois k ≥ 4)> 3k + 3 = 3(k+1) Portanto P(k+1): (k+1)2 > 3(k+1)

15

Indução

Demonstração por Indução Matemática

�Ex. 05: Prove por indução que a soma dos n primeiros números naturais é dada por P(n) = n (n+1) / 2�Temos: P(n) = 1 + 2 + 3 + 4 + ... + n = n(n + 1) / 21. Base da indução: P(1) = 1 (1 + 1) / 2 = 12. Hipótese da indução: P(k): 1 + 2 + 3 + ... + k = k(k + 1)/23. Devemos mostrar quer P(k+1) = 1+2+3+ ... + k + (k + 1)=[(k+1)(k+1+1)]/2Usando a hipótese de indução, vamos substituir na expressão acima, o valor de P(k), teremos:P(k + 1) = k (k + 1) / 2 + (k + 1) =[(k+1)(k+1+1)]/2Desenvolvendo o lado esquerdo, fica:P(k +1) = [k(k+1)/2]+(k+1) = [k (k + 1) + 2(k + 1)] / 2= [(k + 1) (k + 2)] / 2 = (k+1) [(k+1) + 1] / 2que é a mesma fórmula para (k+1).Logo, P(n) = n (n+1) / 2 é verdadeira para todo n natural.

16

Segundo Princípio de Indução (ou Indução forte)

1. P(1) é verdade2. (∀k) [P(r) verdade para todo r, 1 ≤ r ≤ k →

P(k+1) verdade]

Indução

P(n) é verdade para todo inteiro

positivo n

� Na proposição 2 do primeiro princípio, precisamos provar que para um inteiro positivo k, P(k+1) é verdadeira baseado na hipótese de indução que P(k) é verdade.

� Na proposição 2 do segundo princípio, podemos supor que P(r) é verdadeira para todos os inteiros r entre 1 e k para provar P(k+1).

17

Indução

Segundo Princípio de Indução� Precisamente, a proposição 2 necessita que

provemos que P(1)∧ P(2)∧... ∧P(k) → P (k+1)� Ou seja, o segundo princípio considera não apenas o

resultado anterior P(k), mas também os anteriores para concluir P(k+1)

18

Indução

Segundo Princípio de Indução� Ex. 06: Prove que qualquer quantia para postagem

maior ou igual a 8 centavos pode ser composta usando-se apenas selos de 3 e 5 centavos.� Queremos provar que todo inteiro ≥ 8 pode ser

representado com a soma de 3 e 51. Base da indução: P(8) = 3 + 5 (Verdade)2. Pelo primeiro princípio, o próximo k seria

necessariamente 8 + 3 = 11, ou seja (k+1)=11 e não se conseguiria provar para P(9) e P(10).� São necessários, então, outros casos anteriores a

P(k+1) e a partir daí, usar o segundo princípio.� P(9) = 3+3+3� P(10) = 5+5

19

Indução

Segundo Princípio de Indução3. A hipótese de indução agora é que, para qualquer r, 8 ≤ r ≤ k, P(r) é verdadeira, isto é P(r) é a sentença que resulta da soma de 3s e 5s.

4. Queremos provar também que k+1 também pode ser representado por somas de 3s e 5s.Temos que k+1 ≥ 11, pois já vimos P(r) para 8, 9 e 10.Como (k+1) – 3 ≥ 11 – 3 (para usarmos a hipótese)Então (k-2) ≥ 8Pela hipótese, para qualquer r, 8 ≤ r ≤ k , P(r) éverdadeira. Daí P(k-2) é verdadeira, ou seja, pode ser escrita como uma soma de 3s e 5s.É rápida a verificação pois:(k-2) + 3 = k+1 (o elemento seguinte a k).

1

1





Matemática Discreta Matemática Discreta -- 0606

2

Recursividade e relações de recorrência

2

3

Definições Recorrentes� Uma definição onde o item a ser definido aparece como

parte da definição é chamada de definição recorrente ou definição por recorrência ou ainda definição por indução.

� Como definir algo em torno de si mesmo?1. Uma base, ou condição básica, onde alguns casos simples

(pelo menos um) do item que está sendo definido são dadosexplicitamente.

2. Um passo de indução ou recorrência, onde novos casos doitem que está sendo definido são dados em função dos casosanteriores.

� O item 1 nos dá o começo, fornecendo casos simples e concretos.

� O item 2 nos permite construir novos casos, a partir dos simples e ainda outros casos a partir desses novos e assim por diante.

Recursividade e Relações de Recorrência

4

Sequências definidas por Recorrência� Uma sequência S é uma lista de objetos que

são numerados em uma determinada ordem.� Existe um primeiro objeto, um segundo e

assim por diante.� S(k) denota o k-ésimo objeto da sequência.� Uma sequência é definida por recorrência

nomeando-se o primeiro valor (ou alguns primeiros) na sequência e depois definindo os demais valores subsequentes em termos dos valores anteriores.


3

5

Sequências definidas por Recorrência� Ex. 01:A seqüência S é definida por recorrência por

1.S(1) = 22.S(n) = 2S(n -1) para n ≥ 2Pela proposição 1, S(1) = 2. Depois, pela proposição 2, o segundo objeto em S é S(2) = 2S(1) = 2(2)=4.Novamente, pela proposição 2, S(3)=2S(2) = 2(4) = 8.Continuando desse modo, vemos que a sequência S é:2, 4, 8, 16, 32...

� Uma regra como a da proposição 2, que define um valor de uma sequência em termos de um ou mais valores anteriores é uma relação de recorrência.


6

Sequências definidas por Recorrência� Ex. 02:A seqüência T é definida por recorrência por

1.T(1) = 12.T(n) = T(n -1) + 3 para n ≥ 2� Escreva os cinco primeiros valores da sequência T.

� Ex. 03: A famosa sequência de Fibonacci é uma sequência de números definida por recorrência por:F(1) = 1F(2) = 1F(n) = F(n-2) + F(n-1), para n>2� Nesse caso, são dados os dois primeiros valores e relação de recorrência define o n-ésimo valor em termos dos dois valores precedentes.� Na sua forma mais geral, a relação de recorrência é a soma de F em seus dois valores anteriores.

� Ex. 04: Escreva os oito primeiros valores da sequência de Fibonacci.


4

7

Sequências definidas por Recorrência� Ex. 05: Prove diretamente que, na sequência de Fibonacci, a fórmula F(n+4)=3F(n+2) – F(n), para todo n ≥ 1, é verdadeira.A relação de recorrência da sequência de Fibonacci pode ser escrita como: F(n+2)=F(n)+F(n+1) ou,F(n+1) = F(n+2) – F(n) (1)Logo, F(n+4)=F(n+2)+F(n+3)F(n+4)=F(n+2)+F(n+2)+F(n+1) //Reescrevendo F(n+3)F(n+4)=F(n+2)+ F(n+2)+[F(n+2)-F(n)] // de (1)F(n+4)=3F(n+2)-F(n)


8

Sequências definidas por Recorrência� Ex. 06: Prove diretamente que, na sequência de Fibonacci, a fórmula F(n+1)+F(n-2) = 2F(n), para todo n ≥ 3, é verdadeira.Da relação de Recorrência:F(n+1)=F(n-1) + F(n) eF(n)=F(n-1)+F(n-2) = F(n-1)+F(n) + F(n-2) = [F(n-1)+F(n-2)] + F(n)=F(n)+ F(n) = 2F(n)

Observar que só é válida porque n ≥ 3.


5

9

Sequências definidas por Recorrência� Ex. 07: Prove diretamente que, na sequência de Fibonacci, a fórmula F(n+3)=2F(n+1) + F(n), para todo n ≥ 1, é verdadeira.


10

Operações definidas por Recorrência� Certas operações comuns em objetos podem ser

definidas de forma recorrente, conforme os exemplos a seguir:

� Ex. 08: Uma definição recorrente da operação de exponenciação an de um número real não nulo a, onde n é um inteiro não negativo é:

1. a0=12. an=(an-1)a para n≥1

� Ex. 09: Uma definição recorrente para a multiplicação de dois inteiros positivos m e n é:

1. m(1) = m2. m(n) = m(n-1) + m para n≥2


6

11

Resolvendo Relações de Recorrência� Tomando por base novamente o Exemplo 01� Ex.01: A seqüência S é definida por recorrência por

� S(1) = 2 (1)� S(n) = 2S(n -1) para n ≥ 2 (2)

� Como:S(1) = 2 = 21

S(2) = 4 = 22

S(3) = 8 = 23

S(4) = 16 = 24

e assim por diante, vemos queS(n) = 2n (3)

� É possível calcular diretamente S(n) sem ter que calcular explicitamente ou por recorrência.


Solução em forma fechada para a relação de recorrência (2) sujeita à condição básica (1)

12

Resolvendo Relações de Recorrência� Relações de recorrência são usadas em programas

computacionais, estudos de decaimento químico, crescimento populacional etc.

� Seria bom encontrar sempre soluções fechadas!� Uma técnica para resolver relações de recorrência é

uma abordagem do tipo “expandir, conjecturar e verificar”.

� Essa técnica usa repetidamente a relação de recorrência para expandir a expressão a partir do n-ésimo termo até que se tenha uma idéia da forma geral.

� Após obtida a forma geral, a conjectura é provada por indução matemática.


7

13

Resolvendo Relações de Recorrência� Ex. 10: Considere novamente a seqüência S

� S(1) = 2 (1)� S(n) = 2S(n -1) para n ≥ 2 (2)

� Desconsiderando que já sabemos a solução fechada, vamos usar a abordagem de expandir, conjecturar e verificar para encontrar a solução.

� A relação S(n) = 2S(n -1) estabelece que um elemento S pode ser substituído por duas vezes o elemento anterior.

� Seguindo essa receita, expandimos para n, n-1, n-2, assim por diante:

� S(n) = 2S(n -1)� = 2[2S(n -2)] = 22S(n-2)� = 22[2S(n-3)] = 23S(n-3)� Olhando o padrão que está se formando, conjecturamos

que, após k expansões, a equação tem a forma:S(n) = 2kS(n-k)


14

Resolvendo Relações de Recorrência� Ex. 10: Forma geral da expansão:

S(n) = 2kS(n-k)

� A expansão dos elementos de S em função dos elementos anteriores pára quando n-k=1 (significa que estamos com o último e o penúltimo elemento da relação).

� n-k =1 então, k=n-1 e nesse ponto temos:� S(n) = 2n-1S[n-(n-1)] = 2n-1S(1)� 2n-1(2) = 2n que é a solução em forma fechada

� A solução encontrada é apenas a conjectura, que precisa ser confirmada, ou seja devemos provar que S(n)=2n para n≥ 1.

� Provaremos usando a indução matemática.


8

15

Resolvendo Relações de Recorrência� Ex. 10: Provar que S(n) = 2n para n≥ 1.

1. Base da indução S(1) = 21 é verdadeiro2. Hipótese da indução S(k) = 2k

3. Devemos provar que S(k+1) = 2k+1

S(k+1) = 2S(k)S(k+1) =2(2k)S(k+1) =2k+1 – Isso prova que a solução fechada

encontrada está correta.


1






2

Teoria dos Conjuntos

� Conjunto não se define formalmente. Usa-se uma idéia intuitiva de que se trata de uma coleção de objetos.

� Esses objetos de um conjunto possuem alguma propriedade em comum.

� Notação – Usa-se letras maiúsculas para denotar conjuntos e o símbolo ∈ para designar a pertinência em um conjunto.

� Assim, a ∈∈∈∈ A significa que a pertence ao conjunto A ou éum elemento do conjunto A.

� Da mesma forma, b ∉∉∉∉ A signfica que b não pertence a A.� Usamos chaves para indicar um conjunto.

� Se A = {azul, verde, branco}, então verde ∈ A e preto ∉A.

� Os elementos em um conjunto não tem nenhuma ordem, de modo que {azul, verde, branco} é o mesmo que {branco, azul, verde}.

3


Notação

� Dois conjuntos são iguais se contêm os mesmos elementos. Usando a notação da lógica de predicados, temos:

� A = B significa (∀x)[(x ∈ A → x ∈ B) ∧ (x ∈ B →x ∈ A)]� Ao descrever um conjunto particular, temos que identificar

seus elementos.� Para um conjunto finito (com n elementos para n > 0), isso

é feito listando-se todos os seus elementos.� Para um conjunto infinito, podemos indicar a forma geral

listando os primeiros elementos.� S é o conjunto de todos os inteiros positivos pares, então

S={2, 4, 6,…}.� S também pode ser definido por recorrência, explicitando

um dos elementos de S e descrevendo os demais em termos dos elementos já conhecidos.

1. 2 ∈ S2. Se n ∈ S, então (n+2) ∈ S.

4


� Mas a maneira mais clara de se descrever esse conjunto S é através da propriedade que caracteriza os elementos do conjunto em palavras, isto é:

� S = { x | x é um inteiro positivo par}� Então, podemos descrever um conjunto das seguintes

maneiras, dentre outras:� Listar (total ou parcialmente) seus elementos.� Usar recorrência para descrever como gerar seus elementos.� Descrever uma propriedade P que caracteriza seus

elementos.� A notação para um conjunto cujos elementos é caracterizado

por uma propriedade P é { x | P(x)}, onde P(x) é um predicado unário (única variável).

� A notação baseada na lógica formal torna mais claro a propriedade que caracteriza os elementos de um conjunto.

S = { x |P(x)} significa que (∀x)[(x ∈ S→ P(x))∧(P(x) →x ∈ S]

5


� Ex.01: Descreva cada um dos conjuntos a seguir listando seus elementos:

a) { x | x é um inteiro e 3<x ≤ 7}b) { x | x é um mês com exatamente 30 dias}

� Ex.02: Descreva cada um dos conjuntos a seguir através de uma propriedade que caracterize seus elementos:

a) {1, 4, 9, 16}b) {2, 3, 5, 7, 11, 13, 17,…}

6


� É conveniente usarmos uma notação padrão para determinados conjuntos, de modo que se possa se referir mais facilmente a eles.

= Números naturais=Números inteiros= Números reais= Números racionaisI = Números Irracionais

I

7


� O Conjunto vazio é denotado por ∅ ou por { }.� Por exemplo, se S = {x | x ∈ e x<0}, então S = ∅.

� Note que ∅ ≠ {∅}

� Ex. 03: Seja um conjunto A dado por:A = {x | (∃y)(y ∈ {0, 1, 2} e x=y3}.

� Esse conjunto é da forma A=(x|P(x)}.� Encontra-se cada elemento de A atribuindo-se a y cada

um dos valores e elevando-os ao cubo.� Então A = {0, 1, 8}.

� Ex. 04: Seja um conjunto B dado por:B = {x | x ∈ e (∃y)(y ∈ e x ≤ y}.

� Para y=0, x=0; para y=1, x=0 ou 1; para y=2, x=0, 1 ou 2....

� B consiste em todos os inteiros não negativos menores ou iguais a um inteiro não negativo.

8


� Ex. 05: Seja um conjunto C dado por:C = {x | x ∈ e (∀y)(y ∈ → x ≤ y}.

� Dessa forma, obtemos C={0}.� 0 é o único inteiro não-negativo que é menor ou igual a

todos os inteiros não-negativos.� Ex. 06: Descreva cada um dos conjuntos a seguir:

� A = {x | x ∈ e (∀y)(y ∈ {2, 3, 4, 5} → x ≥ y}.

� B = {x | (∃y)(∃z)(y ∈{1,2} e z ∈{2,3} e x=y+z}.

9


Relações entre conjuntos

� Para A={2, 3, 5, 12} e B={2, 3, 4, 5, 9, 12}, todo elemento de A é, também, elemento de B.

� A é um subconjunto de B� Definição: (∀x)(x ∈ A→ x ∈ B)

� Se A é um subconjunto de B, então A ⊆⊆⊆⊆ B.� Se A ⊆ B mas A≠B, então A é um subconjunto próprio

de B, e escrevemos A ⊂⊂⊂⊂ B.� Use a notação da lógica formal para definir A ⊂⊂⊂⊂ B.

� Ex. 07: Sejam A={1, 7, 9, 15}, B={7, 9} e C={7, 9, 15, 20}, então as seguintes proposições são verdadeiras (entre outras):

B ⊆⊆⊆⊆ C 15 ∈ C

B ⊆⊆⊆⊆ A {7, 9} ⊆⊆⊆⊆ B

B ⊂⊂⊂⊂ A {7} ⊂⊂⊂⊂ A

A ⊆⊆⊆⊆ C ∅∅∅∅ ⊆⊆⊆⊆ C

10


Ex. 08: Sejam A = {x | x ∈ N e x ≥ 5}, B = {10, 12, 16, 20} e C = {x | (∃y)(y ∈ N e x = 2y)}Quais das proposições abaixo são verdadeiras:

a. B ⊆ C b. B ⊂ Ac. A ⊆ C d. 26 ∈ Ce. {11, 12, 13} ⊆ A f. {11, 12, 13} ⊂ Cg. {12} ∈ B h. {12} ⊆ Bi. {x | x ∈ N e x < 20} ⊄ B j. 5 ⊆ Ak. {∅} ⊆ B l. ∅ ∉ A

11


Conjuntos de Conjuntos

� Para um conjunto S, podemos formar um novo conjunto cujos elementos são subconjuntos de S.� Esse novo conjunto é chamado de conjunto das partes de S e é denotado por ℘(S).

� Para S={0,1}, ℘(S) = { ∅, {0}, {1}, {0,1}}. � Os elementos do conjunto das partes de S são

conjuntos.� Para qualquer conjunto S, ℘(S) sempre tem, pelo

menos ∅ e S como elementos, já que é sempre verdade que ∅ ⊆ S e S ⊆ S.

� Para encontrar ℘(S), comece com ∅, depois coloque os conjuntos formados por 1 elemento de S, depois ao formados por 2 elementos de S, por 3 e assim por diante, até o próprio S.

12


Conjuntos de Conjuntos

� Ex.09:Para A={1,2,3}, encontre ℘(A). Observe que o número de elementos de℘(A) é igual a 2n, onde n é o numero de elementos de A.

13


Operações em Conjuntos

� A maior parte das operações que envolvem números podem ser efetuadas também em conjuntos.

� Dado um conjunto S, podemos definir operações no conjunto ℘(S).

� S, nesse caso, é chamado de conjunto universo, que define o contexto dos objetos em discussão.

� Se S= , então os subconjuntos conterão apenas inteiros.

� Operação unária e binária� Unária: quando age em apenas um elemento do

conjunto (por exemplo, uma negação de um elemento).� Binária: quando acontece em dois inteiros do conjunto

(por exemplo, uma subtração).

14



� Uma operação binária em ℘(S) tem agir em dois subconjuntos de S para produzir um único subconjunto de S. Isso pode acontecer de duas maneiras naturais:� Seja S o conjunto de todos os estudantes da

UNIVASF. Então elementos de ℘(S) são conjuntos de estudantes.

� Seja A o conjunto de estudantes de Administração e B os de Computação. Ambos pertencem a ℘(S).

� Um novo conjunto pode ser definido por todos os alunos que são de administração ou de computação (ou ambos). Esse conjunto é a união de A e B.

� Outro conjunto pode ser definido pelos alunos que estudam simultaneamente administração e computação. Esse conjunto (que pode ser vazio) échamado a interseção de A e B.

15



� Definições: Sejam A e B ∈ ℘(S).� A União de A e B, denotada por A ∪∪∪∪ B é {x | x ∈ A ou

x ∈ B}� A Interseção de A e B, denotada por A ∩∩∩∩ B é {x | x ∈ A e x ∈ B}

� Ex. 10: Sejam A={1,3,5,7,9} e B={3,5,6,10,11}, com A e B sendo ℘().

� Então A ∪ B é ={1,3,5,6,7,9,10,11} e A ∩ B ={3,5}. Ambos são ℘().

� Ex. 11: Sejam A e B ∈ ℘(S) Para um conjunto arbitrário S. Ésempre verdade que A ∩ B ⊆ A ∪ B ?

16



� Diagramas de Venn – usados para representação visual das operações entre conjuntos.

� Complemento de um conjunto.

� Para um conjunto A ∈ ℘(S), o complemento de A, A’ é {x | x ∈ S e x ∉ A}.

� Ex. 12: Ilustre A’ como um Diagrama de Venn.

17



� Diferenças entre conjuntos – Uma outra operação binária em conjuntos A e B ∈ ℘(S) é a diferença entre conjuntos A - B={x | x ∈ A e x ∉ B}.

� Essa operação pode ser reescrita como A-B={x | x ∈ A e x ∈ B’} ou como A - B=A ∩ B’.

� Ex. 13: Ilustre A-B como um Diagrama de Venn.

� Dois conjuntos são ditos disjuntos quando A ∩ B = ∅.� Então A – B e B – A, por exemplo, são disjuntos.

� Ex. 14: Sejam A={1,2,3,5,10}, B={2,4,7,8,9}, C={5,8,10}, subconjuntos de S={1,2,3,4,5,6,7,8,9,10}. Encontre:

a) A ∪ B b) A – C c) B’ ∩ (A ∪ C)

18



� Produto Cartesiano – Sejam os subconjuntos A e B de S. O produto cartesiano de A e B, denotado por A X B, é definido por:� A X B = {(x,y)| x ∈ A e y ∈ B}.� Os elementos do resultado não pertencem a S mas são

pares ordenados de elementos de S.� O produto A X A é denotado por A2.� An denota o conjunto (x1, x2, ..., xn) de elementos de

A.� Ex. 15: Sejam A={1,2} e B={3,4}. Encontre:

a) A X B b) B X A c) A2 d)A3

19


Identidades básicas envolvendo Conjuntos

� Existem várias igualdades entre conjuntos nas operações de união, interseção, diferença e complementação.

� Essas igualdades são independentes dos subconjuntos particulares utilizados e são chamadas de identidades.

� Essas identidades são semelhantes às equivalências tautológicas da lógica formal.

1a. A ∪ B = B ∪ A 1b. A ∩ B = B ∩ A (comutatividade)

2a. (A ∪ B) ∪ C = 2b. (A ∩ B) ∩ C = (associatividade)

A ∪ (B ∪ C) A ∩ (B ∩ C) 3a. A ∪ (B ∩ C)= 3b. A ∩ (B ∪ C)= (distributividade)

(A ∪ B) ∩ (A ∪ C) (A ∩ B) ∪ (A ∩ C)4a. A ∪ ∅ = A 4b. A ∩ S = A (existência de elemento neutro)

5a. A ∪ A' = S 5b. A ∩ A' = ∅ (propriedades do complemento)

Note que 2a e 2b nos permitem eliminar os parênteses.

20


Identidades envolvendo Conjuntos

� Provando identidades:Ex. 16: 3a. A ∪ (B ∩ C)= (A ∪ B) ∩ (A ∪ C) Queremos então provar que

A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C) e que

(A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C) Podemos, então proceder da seguinte maneira:(seja x um elemento arbitrário de A ∪ (B ∩ C)):

x ∈ A ∪ (B ∩ C) → x ∈ A ou x ∈ (B ∩ C)→ x ∈ A ou (x ∈ B e x ∈ C)→ (x ∈ A ou x ∈ B) e (x ∈ A ou x ∈ C)→ x ∈ (A ∪ B) e x ∈ (A ∪ C)→ x ∈ (A ∪ B) ∩ (A ∪ C)

Para mostrarmos que (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C), basta fazer o argumento de trás para frente.

21



� Provando identidades: Ex. 17: 4a. A ∪ ∅ = A

� Ex. 18: Use as identidades básicas para provar que:[A ∪ (B ∩ C)] ∩ ([A' ∪ (B ∩ C)] ∩ (B ∩ C)') = ∅

para A, B e C subconjuntos arbitrários de S. � Na demonstração a seguir, o número à direita denota a

identidade básica usada em cada passo.[A ∪ (B ∩ C)] ∩ ([A' ∪ (B ∩ C)] ∩ (B ∩ C)')

= ([A ∪ (B ∩ C)] ∩ [A' ∪ (B ∩ C)]) ∩ (B ∩ C)' (2b)= ([(B ∩ C) ∪ A] ∩ [(B ∩ C) ∪ A']) ∩ (B ∩ C)' (1ª - 2 vezes)= [(B ∩ C) ∪ (A ∩ A')] ∩ (B ∩ C)' (3a)= [(B ∩ C) ∪ ∅] ∩ (B ∩ C)' (5b)= (B ∩ C) ∩ (B ∩ C)' (4a)= ∅ (5b)

22



� O dual de cada identidade é obtida permutando-se ∪com ∩ e S com ∅. O dual da identidade do exemplo anterior: [A ∪ (B ∩ C)] ∩ ([A'∪(B ∩ C)]∩(B ∩ C)') = ∅é [A ∩ (B ∪ C)] ∪ ([A'∩(B ∪ C)]∪(B ∪ C)') = S

� Essa identidade também pode ser provada substituindo cada identidade básica pela sua dual.

� Ex.19: Usando as identidades básicas, mostre a identidade:

[C ∩ (A ∪ B)] ∪ [(A ∪ B) ∩ C'] = A ∪ B(A, B e C são subconjuntos arbitrários de S.)

� Ex. 20: Enuncie a identidade dual do exemplo anterior.

23


Resumo dos métodos para provar identidades envolvendo conjuntos

Método Comentário

Desenhe um diagrama de Venn Não é um bom plano, já que nenhum diagrama vai cobrir todos os casos e não demonstrará a identidade no caso geral.

Prove a inclusão em cada direção Tome um elemento arbitrário de um dos termos da identidade e mostre que ele pertence ao outro termo, e reciprocamente.

Use identidades já demonstradas Verifique se a forma da expressão éexatamente igual à forma da identidade que você quer usar.

24


Conjuntos Contáveis e Não-Contáveis� Em um conjunto finito S, sempre podemos designar

um elemento como sendo o primeiro, s1, um outro como o segundo s2, e assim por diante.

� Se existem k elementos no conjunto, eles podem ser listados na ordem selecionada: s1, s2, ..., sk.

� Essa lista representa o conjunto todo.� O número de elementos em um conjunto finito é a cardinalidade do conjunto. Logo, esse conjunto teria a cardinalidade k.

� Se o conjunto for infinito, se pudemos ainda selecionar um primeiro elemento, s1, um segundo s2, e assim por diante, de modo que a lista s1, s2, s3, ... representa todos os elementos do conjunto.

� Tal conjunto infinito é dito enumerável. Tanto conjuntos finitos quanto os enumeráveis são conjuntos contáveis.

25


Conjuntos Contáveis e Não-Contáveis� Ser contável não significa que podemos dizer qual o

número total de elementos no conjunto.� Significa que podemos dizer quem é o primeiro, o

segundo e assim por diante.� Existem, no entanto, conjuntos infinitos que são não-contáveis (ou não-enumeráveis).

� Um conjunto não-enumerável é tão grande que não existe uma maneira de se contar os elementos e se obter todo o conjunto.

� Apesar de se provar que existem conjuntos não-enumeráveis, vamos considerar alguns conjuntos enumeráveis.

� Ex.21: O Conjunto é enumerável.� Para o conjunto , de inteiros não negativos, é claro que

0, 1, 2, 3... é uma enumeração que incluirá todos os elementos do conjunto.

� O conjunto dos inteiros positivos pares é enumerável.

26


Conjuntos Contáveis e Não-Contáveis� Ex. 22: O conjunto + dos racionais positivos é

enumerável. � Escrevendo cada racional positivo como uma fração de

inteiros positivos, com numerador 1 na primeira linha, 2 na segunda linha e assim por diante:

� Nesse formato, como poderemos enumerar o conjunto?� Para provar que esse arranjo é enumerável, podemos

passar um fio, com uma seta apontando o sentido, percorrendo todo o arranjo, começando em 1/1.

1/1 1/2 1/3 1/4 1/5 ...2/1 2/2 2/3 2/4 2/5 ...3/1 3/2 3/3 3/4 3/5 ...4/1 4/2 4/3 4/4 4/5 ...… … … … … …

27


Conjuntos Contáveis e Não-Contáveis� Assim, por exemplo, a fração 1/3 é o quarto elemento

da enumeração.

� Começando por um dos cantos, observa-se que o arranjo é enumerável. Se começarmos seguindo apenas a primeira linha, jamais vamos terminar para chegar nas outras linhas.

� Para melhorarmos a enumeração, ainda podemos simplificar frações, por exemplo (1/1 = 2/2, 1/2=2/4…)

� Portanto, a enumeração de + começa com 1/1, 2/1, 1/2, 3/1, 4/1...

1/1 1/2 1/3 1/4 1/5 ...2/1 2/2 2/3 2/4 2/5 ...3/1 3/2 3/3 3/4 3/5 ...4/1 4/2 4/3 4/4 4/5 ...… … … … … …

1



[email protected]




2

Contagem

A combinatória é o ramo da matemática que trata de contagem.

Problemas de contagem são importantes sempre que temos recursos finitos.

Quanto espaço de armazenamento um banco de dados usa?

Quantos usuários uma determinada configuração de servidor pode suportar?

Problemas de contagem se resumem, muitas vezes, em determinar o número de elementos em algum conjunto finito.

Quantas linhas tem uma tabela-verdade com n letras de proposição?

Quantos subconjuntos tem um conjunto com n elementos?

3

Contagem

O Princípio da Multiplicação

Muitos problemas de contagem podem ser resolvidos a partir de uma árvore de possibilidades.

Ex.01: Uma criança pode escolher uma entre duas balas, uma rosa e outra preta, e um entre três chicletes, um amarelo, outro verde e outro branco. Quantos conjuntos diferentes a criança pode ter?

Podemos resolver o problema, separando a escolha dos doces em 2 etapas sequenciais: escolher primeiro a bala e depois o chiclete.

Escolha do chiclete.

R P

A V B A V B

{R,A} {R,V} {R,B} {P,A} {P,V} {P,B}

Escolha da bala.

4

Contagem


Pela árvore anterior, percebe-se que existem 2 x 3=6 possibilidades: {R,A}, {R,V},{R,B}, {P,A}, {P,V} e {P,B}.

Mesmo que a sequencia de eventos fosse trocada, o número de possibilidades seria o mesmo (3X2=6).

O exemplo anterior ilustra o fato de que o número total de resultados possíveis para uma sequência de eventos pode ser obtido multiplicando-se o numero de possibilidades do primeiro evento pelo número do segundo.

Princípio da Multiplicação: Se existem n1 resultados possíveis para um primeiro evento e n2 para o segundo, então existem n1.n2 resultados possiveis para a sequência dos dois eventos.

5

Contagem


Ex. 02: A última parte do seu número de telefone possui 04 dígitos. Quanto desses números de 04 dígitos existem?

A sequência de tarefas é: escolher o primeiro, depois o segundo, o terceiro e finalmente o quarto.

O primeiro pode ser escolhido entre 0 a 9, ou seja 10 dígitos, ou seja, há 10 possibilidades para a primeira opção.

As seguintes também terão cada uma 10 opções. Usando o princípio da multiplicação, devemos multiplicar essas possibilidades para cada tarefa.

10 . 10 . 10 . 10 = 10.000 números diferentes.

Se um elemento não puder ser usado de novo (não são permitidas repetições), o número de possibilidades é afetado.

6

Contagem


Ex. 03: Em relação ao exemplo anterior, quantas possibilidades existem se um mesmo dígito não puder ser repetido.

Ex. 04: De quantas maneiras podemos escolher três representantes em um grupo de 25 pessoas?

Ex. 05: De quantas maneiras podemos escolher três representantes, para três comissões, em um grupo de 25 pessoas, se um representante pode participar de mais de uma comissão?

Ex. 06: Se um homem tem quatro ternos, oito camisas e cinco gravatas, de quantas maneiras diferentes ele pode se vestir?

7

Contagem


Ex. 07: Para qualquer conjunto finito S, denote por |S| o número de elementos em S. Se A e B são conjuntos finitos, então |A X B| = |A|.|B|

A X B denota todos os pares ordenados com a primeira componente em A e a segunda em B.

Podemos formar tais pares ordenados como a sequência de duas tarefas: escolher a primeira componente, com |A| possibilidades e depois a segunda, com |B| possibilidades.

Esse resultado segue o princípio da multiplicação.

8

Contagem

O Princípio da Adição

Suponha que queremos selecionar uma sobremesa entre três tortas e quatro bolos. De quantas maneiras isso pode ser feito?

Temos 02 eventos, um com 03 resultados possíveis e outro com 04.

No entanto, não temos uma sequência de dois eventos possíveis, já que somente uma sobremesa será escolhida.

O número de escolhas possíveis sera o número total de possibilidades que temos, 3+4=7. Isso ilustra o Princípio da Adição.

Princípio da Adição – Se A e B são eventos disjuntos, com n1 e n2 resultados possíveis, respectivamente, então o número total de possibilidades para o evento A ou B é n1 + n2.

Este princípio pode ser usado sempre para contar o número total de possibilidades em casos disjuntos.

9

Contagem


Ex. 08: Uma pessoa deseja comprar um veículo de uma concessionária, que tem 23 automóveis e 14 caminhões em estoque. Quantas escolhas possíveis a pessoa tem?

Ex. 09: Sejam A e B conjuntos disjuntos. Então |AB|=|A|+|B|.

Podemos encontrar AB separando em dois casos disjuntos. Primeiro conta-se os elementos de A, |A| e depois os de B, |B|.

Ex. 10: Se A e B são conjuntos finitos, então,

|A-B|=|A|-|AB| (I) e |A-B|=|A|-|B| se B A (II)

Para provar a primeira identidade, note que

(A – B) (A B) = (A B') (A B)

= A (B' B)

= A S

= A

10

Contagem


Ex. 10 (Cont.):Se A e B são conjuntos disjuntos, então,

|A-B|=|A|-|AB| e |A-B|=|A|-|B| se B A

Então A = (A – B) (A B), sendo que (A – B) e (A B) são conjuntos disjuntos. Então, pelo exemplo 09:

|A| = |(A – B) (A B)| = |A –B| + |A B| ou |A – B| = |A| - |A B|

A segunda equação segue da primeira, já que, se B A, então A B = B.

11

Contagem

Usando os dois princípios juntos

Os dois princípios são frequentemente usados juntos.

Ex. 11: Tomando por base o exemplo 01, suponhamos que queremos encontrar de quantas maneiras diferentes a criança pode escolher o doce, ao invés do número de conjuntos de doces que ela pode ter.

Escolher uma bala rosa e depois um chiclete amarelo não é a mesma coisa que escolher um chiclete amarelo e depois uma bala rosa.

Podemos considerar dois casos disjuntos: a escolha das balas ou de chicletes primeiro.

Cada um desses casos, pelo princípio da multiplicação, tem 06 possibilidades.

Então, pelo princípio da adição, existem 6+6=12 maneiras diferentes de escolher os doces.

12

Contagem


Ex. 12: Quantos números de quatro dígitos começam com 4 ou 5?

Ex. 13: Se uma mulher tem 07 blusas, 05 saias e 09 vestidos, de quantas maneiras diferentes ela pode se vestir?

Um problema de contagem pode ser resolvido, muitas vezes, de mais de uma forma.

Uma segunda opção, embora possa causar confusão, é uma boa maneira de verificarmos o resultado obtido.

No Ex. 12, podemos não usar o princípio da adição, considerando o problema como dividido em 04 tarefas sucessivas. Para a primeira tarefa, escolher o primeiro dígito, tem 02 possibilidades – 4 ou 5. Para as demais, 10 possibilidades.

Existem, então 2.10.10.10 = 2.000 possibilidades.

13

Contagem


Ex. 14: Quantos inteiros de 03 dígitos (números entre 100 e 999) são pares?

14

Contagem

Árvores de Decisão

Árvores como a mostrada no exemplo da escolha dos doces, que ilustram o número de possibilidades de um evento baseado em uma série de escolhas possíveis são chamadas de árvores de decisão.

O estudo de árvores será introduzido posteriormente, mas elas já podem ser usadas para resolver problemas de contagens adicionais.

Árvores regulares são as que os números de resultados possíveis em qualquer nível da árvore é o mesmo em todo o nível, como as do exemplo mostrado.

Árvores menos regulares podem ser usadas para resolver problemas de contagem onde a multiplicação não se aplica.

15

Contagem


Ex. 15: Antonio está jogando moedas. Cada jogada resulta em cara(C) ou coroa(K). Quantos resultados possíveis ele pode obter se jogar 05 vezes sem cair 02 caras consecutivas?

Cada jogada da moeda tem dois resultados possíveis; o ramo da esquerda está marcado com um C, denotando cara, e o da direita, com um K, denotando coroa.

Veremos, na árvore a seguir, que existem 13 possibilidades.

16

Contagem


K K

C

C K

K C C

K

K

C K K C K K K C

K K C K C K C K C K C K K C

C

K

C

K

C

C

K

C

K

K

C

K

K

C

K

C

K

K

K

C

C

K

K

K

K

K

C

K

C

K

K

C

K

K

C

K

C

K

K

K

K

K

C

K

C

K

K

C

K

K

K

K

K

C

K

K

K

K

K

C

K

K

K

K

K

Jogada 1

Jogada 2

Jogada 3

Jogada 4

Jogada 5

1



[email protected]




2

Princípio da Inclusão e Exclusão

Este é mais um princípio utilizado para resolver problemas de contagem.

Para desenvolvermos o princípio, observamos primeiro que, se A e B são subconjuntos de um conjunto universo S, então A-B, B-A e AB são disjuntos, conforme a figura abaixo:

A B B - A A - B

A B S

Se x A - B, então x B, logo x B - A e x A B

Ex. 01: Qual um outro nome para o conjunto (A - B) (B - A) (A B)?

3


De |AB| = |A| + |B|, estendido para os três conjuntos finitos disjuntos anteriores, obtemos: |(A - B) (B - A) (A B)| = |A - B|+|B – A|+| A B| (1)

Temos também que |A-B|=|A|-|AB| e |B-A|=|B|-|AB|

Usando essas expressões com o resultado do Ex.01:

|AB|=|A| - |A B| + |B| - |A B| + |A B|, então:

|AB|= |A| + |B| - |A B| (2)

Princípio da Inclusão e Exclusão para dois conjuntos.

Ao contar o número de elementos na união de A e B, precisamos incluir o número de elementos de A e o de B, mas precisamos excluir os elementos de A B para evitar contá-los duas vezes.

Se A e B forem disjuntos, então |AB|=0.

4


Ex. 02: Um pesquisador de opinião pública entrevistou 35 eleitores, todos apoiando o referendo 1, o referendo 2 ou ambos, e descobriu que 14 eleitores apóiam o referendo 1 e 26 apóiam o referendo 2. Quantos eleitores apóiam ambos?

|AB|= 35, |A|=14 e |B|=26. Queremos |A B|

Como |AB|= |A| + |B| - |A B|, então

|A B| = |A| + |B| - |AB| = 14+26-35 = 5

5


A equação do princípio de inclusão e exclusão pode ser estendida a 03 conjuntos, da seguinte maneira:

|A B C| = |A (B C)| = |A| + |B C| - |A (B C)| = |A| + |B| + |C| - |B C| - |(A B) (A C)| = |A| + |B| + |C| - |B C| - (|A B| + |A C| - |A B C|) = |A| + |B| + |C| - |A B| - |A C| - |B C| + |A B C|

Então a equação do princípio de inclusão e exclusão para a 03 conjuntos é:

|ABC| =|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| (3)

6


Além do argumento formal, podemos usar um argumento geométrico conforme a figura abaixo para |ABC|.

Quando somamos |A| + |B| + |C|, estamos contando cada elemento em |AB|, |AC| e |BC| duas vezes, de modo que temos que retirar cada um deles uma vez.

Nessa mesma soma, estamos contando cada elemento em |A B C| três vezes, mas ao subtrairmos as interseções anteriores, eliminamos três vezes esses elementos, logo precisamos colocá-los de volta uma vez, somando |A B C| ao final.

A B

C

S

7


Ex. 03: Um grupo de estudantes está planejando encomendar pizzas. Se 13 comem lingüiça calabresa, 10 comem salame italiano, 12 comem queijo extra, 4 comem tanto calabresa quanto salame, 5 comem tanto salame quanto queijo extra, 7 comem tanto lingüiça calabresa quanto queijo extra e 3 comem de tudo, quantos estudantes há no grupo?

Sejam: A = {estudantes que comem linguiça calabresa} B = {estudantes que comem salame italiano} C = {estudantes que comem queijo extra} Então |A|=13, |B|=10, |C|=12, |A B| = 4, |B C| = 5,

|A C| = 7 e |A B C| = 3. Da Eq. (3), |A B C| = 13 + 10 + 12 - 4 - 5 - 7 + 3 = 22

8


Esse problema poderia ser resolvido usando um diagrama de Venn.

Começando da parte de dentro para fora, sabemos que existem 3 pessoas em A B C (fig. a).

Temos também o número das pessoas em A B, B C e A C (fig. b).

Conhecemos também o tamanho de A, B e C (fig. c)

O número total de estudantes, 22, é obtido somando-se todos os elementos.

C

A B

3

C

A B

3

C

A B

1

4 2 3

1

4 2

5 4

3

fig. a fig. b fig. c

9


Ex. 04: Um feirante vende apenas brócolis, cenoura e quiabo. Em um dia, o feirante atendeu 207 pessoas. Se 114 pessoas compraram brócolis, 152 compraram cenoura, 25 compraram quiabo, 64 compraram brócolis e cenoura, 12 compraram cenoura e quiabo e 9 compraram os três produtos, quantas pessoas compraram brócolis e quiabo?

Sejam A = {pessoas que compraram brócolis} B = {pessoas que compraram cenoura} C = {pessoas que compraram quiabo} Então |A B C| = 207, |A| = 114, |B| = 152, |C| = 25, |A B| = 64, |B C| = 12 e |A B C| = 9. Da Eq. (3), |A C| = 114 + 152 + 25 - 64 - 12 + 9 - 207 = 17

10

Princípio das Casas de Pombo

O princípio das casas de pombo recebeu esse nome exótico da seguinte idéia: se mais de k pombos entram em k casas de pombos, então pelo menos uma casa vai ter mais de um pombo.

Embora isso pareça óbvio, podemos aprofundar esse ponto.

Suponha que cada casa contenha no máximo um pombo. Então existem no máximo k pombos e não os “mais de k” pombos que supostamente entraram nas casas.

O princípio pode ser enunciado da seguinte forma:

Princípio das Casas de Pombo - Se mais de k itens são colocados em k caixas, então pelo menos uma caixa contém mais de um item.

Escolhendo corretamente itens e caixas, pode-se resolver vários problemas de contagem.

11

Princípio das Casas de Pombo

Ex. 05: Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o nome começando com a mesma letra?

O alfabeto (incluindo K, Y e W) tem 26 letras (caixas). Se a sala tiver 27 pessoas, então existem 27 iniciais (itens) para se colocar em 26 caixas, de modo que pelo menos uma caixa vai conter mais de uma inicial.

Ex. 06: Quantas vezes é preciso jogar um dado de modo a garantir que um mesmo valor apareça duas vezes?

1


Matemática Discreta – 10

Prof. Jorge Cavalcanti [email protected] - www.univasf.edu.br/~jorge.cavalcanti

Matemática Discreta – 10

2

1 - Grafos e Árvores

Muitas aplicações em computação necessitam considerar

conjunto de conexões entre pares de objetos:

Existe um caminho para ir de um objeto a outro seguindo as

conexões?

Qual é a menor distância entre um objeto e outro?

Quantos outros objetos podem ser alcançados a partir de um

determinado objeto?

Grafos são utilizados para modelar tais problemas.

Alguns exemplos de problemas práticos que podem ser

resolvidos através de uma modelagem em grafos:

Ajudar máquinas de busca a localizar informação relevante na

Web.

Descobrir qual é o roteiro mais curto para visitar as principais

cidades de uma região turística.

3


Definição informal - Um grafo é um conjunto não-vazio de nós (vértices) e um conjunto de arcos (arestas) tais que cada arco conecta dois nós.

Os grafos que serão estudados terão sempre um número finito de nós e arcos.

4


O grafo a seguir tem cinco nós e seis arcos:

A definição informal de um grafo funciona bem se tivermos sua representação visual, mostrando que arcos se conectam aos nós.

Sem essa visualização, precisamos de uma definição formal de mostrar esse grafo.

1 3

2

4 5 a5

a4

a2

a1

a3

a6

5


Definição Formal - Um grafo é uma tripla ordenada (N, A, g), onde:

N = um conjunto não-vazio de nós (vértices)

A = um conjunto de arcos (arestas)

g = uma função que associa a cada arco a a um par não-ordenado x-y de nós, chamado de extremidades de a

1 3

2

4 5 a5

a4

a2

a1

a3

a6

Ex. 01: No grafo acima, a função g que associa arcos a suas extremidades é a seguinte: g(a1)=1-2, g(a2)=1-2, g(a3)=2-2, g(a4)=2-3, g(a5)=1-3 e g(a6)=3-4.

6


Grafo direcionado (dígrafo) – Um grafo é uma tripla ordenada (N, A, g), onde N = um conjunto não-vazio de nós (vértices)

A = um conjunto de arcos (arestas)

g = uma função que associa a cada arco a a um par ordenado (x, y) de nós, onde x é o ponto inicial e y é o ponto final de a.

Em um grafo direcionado, cada arco tem um sentido ou orientação.

Ex. 02: No grafo acima, a função g que associa arcos a suas extremidades é a seguinte: g(a1)=(1,2), g(a2)=(1,4), g(a3)=(1,3), g(a4)=(3,1) e g(a5)=(4,4).

1

3

2

4

a5

a4

a1

a2 a3

7


Terminologia Além da orientação, podemos colocar informações nos nós (rótulos),

gerando um grafo rotulado. Pode-se também atribuir valores ou pesos aos arcos, gerando um gráfico com pesos.

Nós adjacentes – se ambos são extremidades de algum arco.

Laço - é um arco com extremidades n-n para algum nó n.

Arcos paralelos – dois arcos com a mesma extremidade.

Grafo Simples – é um grafo sem laços ou arcos paralelos.

Nó isolado – é um nó que não é adjacente a nenhum outro.

Grau – é o número de extremidades de arcos que se conectam a um nó.

Grafo completo - é um grafo no qual dois nós distintos quaisquer são adjacentes.

Subgrafo – consiste em um conjunto de nós e arcos que são subconjuntos do conjunto original de nós e arcos.

1 3

2

4 5 a5

a4 a2

a1

a3

a6 1 3

2

a5

a4 a1

8


Terminologia Caminho – do nó n0 para o nó nk é uma sequência:

n0, a0, n1, a1,.. Nk-1, ak-1, nk

O comprimento de um caminho é o número de arcos que ele contém.

Grafo conexo – se existe um caminho de qualquer nó para outro.

Ciclo – é um caminho de algum nó n0 para ele mesmo tal que nenhum arco aparece mais de uma vez. n0 é o único nó que aparece mais de uma vez e apenas nas

extremidades.

Um grafo sem ciclos é dito acíclico.

1 3

2

4 5 a5

a4 a2

a1

a3

a6 1 3

2

a5

a4 a1

9


Exercício

Ex. 03: Esboce um grafo com nós {1,2,3,4,5}, arcos {a1, a2 ,

a3 , a4 , a5 , a6 } e função g, dada por g(a1)=1-2, g(a2)=1-3,

g(a3)=3-4, g(a4)=3-4, g(a5)=4-5 e g(a6)=5-5. Depois

responda o que se segue:

a) Encontre 2 nós que não são adjacentes

b) Encontre um nó adjacente a si mesmo

c) Encontre um laço

d) Encontre 2 arcos paralelos

e) Encontre o nó de grau 3

f) Encontre um caminho de comprimento 5

g) Encontre um ciclo

h) Esse grafo é completo?

i) Esse grafo é conexo?

10


Terminologia As figuras abaixo ilustram os grafos simples completos de 1

a 4 vértices. Um grafo simples completo é denotado por Kn.

O grafo simples da figura abaixo não é completo, pois nem todo nó é adjacente a todos os outros.

1

K1

5 3 4

K2 K3 K4

K5= ?

2

11


Terminologia

Entretanto, os nós podem ser divididos em 2 conjuntos disjuntos {1,2} e {3,4,5}, tais que os nós de cada conjunto não são adjacentes, mas dois nós escolhidos um em cada conjunto são adjacentes.

Esse tipo de grafo é chamado de bipartido completo.

Grafo bipartido completo – se os seus nós podem ser divididos em 2 conjuntos disjuntos não-vazios N1 (m elementos) e N2 (n elementos), tais que 2 nós são adjacentes se, e somente se, um deles pertence a N1 e o outro pertence a N2.

Um tal grafo é denotado por Km,n 1 2

5 3 4

K2,3

12


Terminologia

Dois grafos podem parecer diferentes na sua representação visual, mas podem ser o mesmo grafo de acordo com sua representação formal.

Grafos Isomorfos – dois grafos (N1, A1, g1) e (N2, A2, g2) são isomorfos se existem bijeções f1:N1 N2 e f2: A1 A2 tais que, para cada arco a A1, g1(a) = x-y se, e somente se g2[f2(a)] = f1(x)-f1(y).

1

3

4

2

a1 a2

1

3

b

2

4

a1

a2 e1

e2

a

d c

f1: 1 a

2 c

3 b

4 d f2: a1 e2 a2 e1

13


Terminologia

Em outras palavras, deve ser possível re-rotular os nós de um grafo para serem rótulos de outro, mantendo os arcos correspondentes em cada grafo.

Ex. 04: Nos grafos isomorfos abaixo, complete as bijeções que estabelecem o isomorfismo.

1

2

a1

a2

3

4 5

a4

a3

a5 a6

a7

a8

a

b

c e d

e8

e7

e3 e2

e4

e1

e6

e5

f1: 1 c

2 e

3 d

4 b

5 a f2: a1 e1 a2 e4 . .

14


Terminologia

Ex. 05: Nos grafos abaixo verifique se são isomorfos e, em caso positivo, descreva as bijeções que estabelecem o isomorfismo.

1

5

3 2

4

6

a

b

e f

c

d

15


Terminologia Teorema sobre Isomorfismo de Grafos Simples

Dois grafos simples (N1, A1, g1) e (N2, A2, g2) são isomorfos se existem bijeções f1:N1 N2 tal que, quaisquer que sejam os nós ni e nj de N1, ni e nj são adjacentes se, e somente se, f(ni) e f(nj) são adjacentes.

A função f é chamada de um isomorfismo do grafo 1 no grafo 2.

Para provar que dois grafos são isomorfos é necessário encontrar a bijeção e depois mostrar que a propriedade de adjacência é preservada.

Por outro lado, provar que dois grafos não são isomorfos, é preciso mostrar que as bijeções necessárias não existem. Esse método pode ser inviável em grafos maiores.

Existem algumas condições que deixam claro que os grafos não são isomorfos, tais como:

16


Condições de não isomorfismo 1. Um grafo tem mais nós que o outro.

2. Um grafo tem mais arcos que o outro.

3. Um grafo tem arcos paralelos e o outro não.

4. Um grafo tem um laço e o outro não.

5. Um grafo tem um nó de grau k e o outro não.

6. Um grafo é conexo e o outro não.

7. Um grafo tem um ciclo e o outro não.

Mesmo assim, ainda podemos falhar..

(a) (b)

17


Grafo planar – é um grafo que pode ser representado de modo que seus arcos se intersectam apenas em nós. Um grafo isomorfo a um grafo planar também é planar.

Ex. 06: Mostre que K4 é um grafo planar.

Ex. 07: K5 também é planar ?

Outra Forma ?

18


O matemático suíço Leonard Euler descobriu que um grafo planar, simples e conexo, divide o plano em um determinado número de regiões, incluindo regiões limitadas por arcos e uma região exterior ilimitada.

Euler observou uma relação entre o número n de nós, o número a de arcos e o número r de regiões em um tal grafo. Fórmula de Euler:

n – a + r = 2

Verifique a Fórmula de Euler no grafo abaixo:

19


Representação de grafos no computador Maior vantagem do grafo é a sua representação visual da

informação.

E se quisermos armazenar o grafo em forma digital? Imagem digital – Difícil manipulação e ocupa mais espaço.

O que precisamos é armazenar os dados essenciais que fazem parte da definição do grafo. Os nós e quais são extremidades de arcos e outras informações

pertinentes (pesos, cores etc.).

As representações computacionais usuais envolvem uma das estruturas de dados: Matriz de adjacência

Lista de adjacências

20


Representação de grafos no computador Matriz de Adjacência

Seja um grafo com n nós numerados (n1, n2..,nn) arbitrariamente. Após a ordenação dos nós, podemos formar uma matriz n x n onde o elemento i, j é o número de arcos entre os nós ni e nj.

A matriz de um grafo não-direcionado é simétrica

1 2

3 4

A = 0 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

21



Encontre a matriz de adjacência para o grafo abaixo:

A matriz de adjacência de um grafo direcionado não será simétrica, pois a existência de um arco de ni para nj não implica em um arco de nj para ni.

1 3

2

A = 0 2 1

2 1 1

1 1 0

1

3

2

4

A = 0 1 1 1

0 0 0 0

1 0 0 0

0 0 0 1

22



1. Vantagens:

Fácil visualização para vértices adjacentes Muito útil para algoritmos em que necessitamos saber com

rapidez se existe uma aresta ligando dois vértices

Fácil cálculo do grau do nó. A soma dos números de uma linha retorna o grau do vértice,

em grafos não direcionados

Em grafos direcionados A soma dos números de uma linha retorna o grau de saída

A soma dos números de uma coluna retorna o grau de entrada

2. Desvantagens:

Requer muito espaço de armazenamento Deve ser mais utilizada para grafos densos

23


Representação de grafos no computador Lista de Adjacências

Se um grafo tem n nós, precisamos de n2 dados para representar a matriz (ou n2/2), mesmo que muitos desses dados seja igual a zero.

Um grafo com poucos arcos pode ser representado de modo mais eficiente armazenando-se somente os elementos não nulos da matriz de adjacência.

Essa representação consiste em uma lista, para cada nó, de todos os nós adjacentes a ele. Cada linha da matriz representa uma lista.

3

4

5

2

1

3

2

4

1

1

2

3

3

5

2

1 ●

4 3 ● 2 4

4 1 4 ●

●

24


Representação de grafos no computador Lista de Adjacências

Mais utilizada para grafos esparsos, pois também exige muito espaço para armazenamento

Verificação de grau:

Não Direcionais: quantidade de nós em uma linha

Direcionais: A quantidade de nós de uma linha representa o grau de saída.

Como saber o grau de entrada de cada nó?

Deve-se pesquisar em todos os vértices do grafo, excluindo ele, se existe alguma referência para o nó em questão!!!

25


Representação de grafos no computador Exercícios

1. Escreva a matriz e a lista de adjacência do seguinte grafo:

2. Desenhe o grafo representado pela matriz de adjacência:

3. Desenhe o grafo direcionado representado pela lista de adjacência a seguir:

A = 0 2 0

2 0 2

0 2 0

1

2

3

4

●

1 ●

2 4 ●

1 2 ●

2 4

3

1

26


Árvores e suas representações

Árvore é um tipo especial de grafo, útil na representação de dados

Por definição – é um grafo conexo, acíclico e com um nó especial, denominado de raiz.

r

r

27



Uma árvore também pode ser definida de maneira recorrente. O único nó é uma árvore (esse nó como raiz).

Sejam T1, T2, ...Tt árvores disjuntas com raízes r1, r2,... rt. Um grafo formado colocando-se um novo nó r, ligado, por um único arco a cada um dos nós r1, r2...r é uma árvore com raiz r.

r

r2 r1

T1

T2

Nó pai

Nó filho Nó filho

28



Como a árvore é acíclica e conexa, existe somente um caminho da raiz para qualquer outro nó da árvore.

A profundidade de um nó é o comprimento do caminho da raiz ao nó.

A altura de uma árvore é a maior profundidade dos nós na árvore.

Um nó sem filhos é chamado de folha da árvore.

Uma floresta é uma coleção de árvores disjuntas.

29



As árvores binárias são as que cada nó tem, no máximo, dois filhos (esquerdo e direito).

Árvore binária cheia é uma árvore com todos os nós internos com dois filhos e todas as folhas estão à mesma profundidade.

Árvore binária completa é uma árvore binária quase cheia, o nível mais baixo vai se completando da esquerda para direita, mas pode ter folhas faltando.

30



Como um árvore também é um grafo, as representações de grafos podem ser usadas para árvores.

Árvores binárias têm características especiais na representação, tal como a identidade dos filhos esquerdo e direito.

O equivalente à matriz de adjacência é uma tabela onde os contém os dados de cada nó.

O equivalente de uma lista de adjacência é uma coleção de registros com três campos contendo o nó em questão, um ponteiro para registro de cada nó filho.

1

2

5 4

3

6

NÓ FILHO ESQ FILHO DIR

1 2 3

2 4 5

3 0 6

4 0 0

5 0 0

6 0 0

1

2 3 ●

6 5 4 ● ● ● ● ● ●

31


Árvores e suas aplicações

Árvores genealógicas

Fluxo organizacional

Estrutura de organização de informações

Demonstração de propagação de informação

N = 4n

32


Árvores e suas aplicações Expressões algébricas envolvendo operações podem ser

representadas por árvores algébricas rotuladas.

Para qualquer nó interno, a operação binária de seu rótulo é efetuada com as expressões associadas às sub-árvores.

Ex.: (2+x) – (y*3)

-

+

x 2

*

3 y

Qual a árvore que representa a expressão (2+3) * 5?

33


Algoritmos de percurso em Árvores Se uma estrutura de árvore está sendo usada para armazenar

dados, é útil termos um mecanismo sistemático de escrita de dados nos nós;

Isso pode ser feito percorrendo-se a árvore, visitando-se todos os nós na sua estrutura;

Os três algoritmos mais comuns de percurso em árvores são os percursos em pré-ordem, em ordem simétrica e em pós-ordem. Seja uma árvore T com uma raiz r, com sub-árvores da esquerda

para a direita, T1, T2.. Tt.

r

r1

T1 T2

...

Tt

r2

rt

34


Algoritmos de percurso em Árvores Os termos pré-ordem, em ordem simétrica e em pós-

ordem, referem-se à ordem da visita da raiz em comparação com os nós das sub-árvores.

No percurso em pré-ordem, a raiz é visitada primeiro e depois processam-se as sub-árvores, da esquerda para a direita, cada uma em pré-ordem.

ALGORITMO Pré-Ordem

Pré-ordem(árvore T)

//Escreve os nós de uma árvore com raiz r em pré-ordem escreva (r) para i=1 até t faça Pré-ordem (Ti) fim do para

fim Pré-ordem

35


Algoritmos de percurso em Árvores No percurso em ordem simétrica, a sub-árvore da

esquerda é percorrida em ordem simétrica, depois a raiz é visitada e, em seguida, as outras sub-árvores, da esquerda para a direita, sempre em ordem simétrica. Se a árvore for binária, a raiz é visitada entre as duas sub-árvores.

ALGORITMO OrdemSimétrica

OrdemSimétrica(árvore T)

//Escreve os nós de uma árvore com raiz r em ordem simétrica OrdemSimétrica(T1) escreva (r) para i=2 até t faça OrdemSimétrica (Ti) fim do para

fim OrdemSimétrica

36


Algoritmos de percurso em Árvores

No percurso em pós-ordem, a raiz é a última a ser

visitada , após o percurso, em pós-ordem, de todas as sub-

árvores da esquerda para a direita.

ALGORITMO Pós-Ordem

Pós-ordem(árvore T)

//Escreve os nós de uma árvore com raiz r em pós-ordem para i=1 até t faça Pós-ordem (Ti) fim do para escreva (r)

fim Pós-ordem

37



Em árvores binárias:

Pré-ordem: raiz, esquerda, direita

Ordem simétrica: esquerda, raiz, direita

Pós-ordem: esquerda, direita, raiz.

a

b

e d

c

g f

i h

Pré-ordem: a b d e c f h i g

Ordem simétrica: d b e a h f i c g

Pós-ordem: d e b h i f g c a

38



Escreva os percursos em pré-ordem, ordem simétrica e

pós-ordem da árvore abaixo:

a

b

e d

c

h g

k i

f

j

Pré-ordem: a b d i e f c g j k h

Ordem simétrica: i d b e f a j g k c h

Pós-ordem: i d e f b j k g h c a

39


Algoritmos de percurso em Árvores Vimos que expressões algébricas podem ser representadas

por árvores binárias.

Se fizermos um percurso em ordem simétrica na árvore abaixo, obteremos a expressão (2+x) * 4 – Notação infixa.

Um percurso em pré-ordem fornece a expressão *+ 2 x 4 O símbolo precede o operando.

Essa forma de expressão é chamada de notação prefixa ou notação polonesa.

* + 2 x 4 * (2 + x) 4 (2 + x) * 4

*

+

x 2

4

40


Algoritmos de percurso em Árvores Um percurso em pós-ordem fornece a expressão 2 x + 4*

O símbolo vem após os operandos.

Essa forma de expressão é chamada de notação posfixa ou notação polonesa reversa (NPR).

2 x + 4 * (2 + x) 4 * (2 + x) * 4

Embora pouco familiares, essas notações dispensam parênteses para evitar ambiguidades e são mais eficientes.

Compiladores normalmente mudam expressões algébricas de programas para NPR para obter processamento mais eficiente.

*

+

x 2

4

41



Exercício: Escreva a árvore que representa a expressão:

a + (b * c – d) e escreva a expressão em notações polonesa e polonesa reversa.

1


Prof. Jorge Cavalcanti [email protected] - www.univasf.edu.br/~jorge.cavalcanti

Matemática Discreta – Parte 11

2

Relações e Funções

Revisão Conceitos Básicos

Produto Cartesiano - Dados os conjuntos A e B, o produto cartesiano de A por B, denotado A X B, é o conjunto formado por todos os pares ordenados (a, b) onde a A e b B, isto é:

A X B = {(a,b) | a A, b B}

Ex.: Dados A={a} e B={a,b}

A X B = {(a,a), (a,b)} / B X A = {(a,a), (b,a)}

Relação - Dados os conjuntos A e B, uma relação R de A em B, denotada R: AB, é qualquer subconjunto do produto cartesiano A X B.

Ex.: Dados A={1,3,5} e B={3,9,15,20}, a relação R: AB, tal que:

R = {(a,b) | b=3a} é dada pelos pares ordenados R = {(1,3), (3,9), (5,15)}.

3


Relações Binárias

O Produto Cartesiano de um conjunto S com ele mesmo, S X S ou S2 é o conjunto de todos os pares ordenados de elementos de S.

Ex. 01. Seja S={1,2}, então, S X S = {(1,1), (1,2), (2,1), (2,2)}

Se estivermos interessados na relação de igualdade (x=y), então (1,1) e (2,2) seriam os elementos de S que satisfazem a relação.

Se estivermos interessados na relação de um número ser menor que outro (x<y), teríamos o par (1,2) como único que atende à relação.

Ou seja, definir uma relação binária R em um conjunto S é especificar um subconjunto de S X S.

4


Relações Binárias

Em geral, uma relação binária é definida por uma descrição da relação, ao invés da lista dos pares ordenados.

A descrição fornece uma caracterização dos elementos pertencentes à relação.

Ex.02: Seja S={1,2}, como no Ex. 01. Seja R a relação em S dada por R={(x,y) S X S | x + y = ímpar}.

Então R = {(1,2), (2,1)}.

5


Tipos de Relações Binárias

Seja uma relação em S com os pares ordenados na forma (s1, s2).

Uma relação é do tipo um para um se cada primeira componente (s1) e cada segunda componente (s2) do par ordenado aparece uma única vez na relação.

Uma relação é do tipo um para muitos se alguma primeira componente (s1) aparece em mais de um par.

A relação é dita muitos para um se alguma segunda componente s2 aparecer em mais de um par.

Finalmente, a ela é muitos para muitos se pelo menos um s1 aparece em mais de um par e pelo menos um s2 também aparece em mais de um par.

6


Tipos de Relações Binárias

Um para um Um para muitos

Muitos para um Muitos para muitos

7


Propriedades das Relações Binárias

Seja uma relação R em um conjunto S com a seguinte descrição: R={(x,y) S X S | x = y}. Essa relação de igualdade tem três propriedades: Para qualquer x S, (x,x) R;

Para qualquer x e y S, se x=y, então y=x, ou seja (x,y) R (y,x) R

Para qualquer x, y e z S, se x=y, y=z, então x=z, ou seja, [(x,y) R e (y,z) R] (x,z) R.

Essas três propriedades fazem com que a relação de igualdade seja reflexiva, simétrica e transitiva.

R ser reflexiva significa (x)(x S (x,x) R)

R ser simétrica significa (x)(y)(x S y S (x,y) R (y,x) R)

R ser transitiva significa (x)(y)(z)(xS yS zS (x,y) R (y,z) R (x,z) R)

8


Propriedades das Relações Binárias

Ex.03: Considere a relação no conjunto N. Ela é reflexiva, pois para qualquer inteiro não-negativo x, x x.

Ela é transitiva pois quaisquer inteiros não-negativos x, y, e z, se x y e y z, então x z.

Entretanto ela não é simétrica, pois 3 4 não implica que 4 3.

Dizer que uma relação R é anti-simétrica significa (x)(y)(x S y S (x,y) R e (y,x) R x = y).

Ex. 04: Seja S = (N) e A, B e C subconjuntos de S. Considere uma relação binária em S definida por R: AB (a,b) | A B.

Então R é reflexiva, já que todo conjunto é subconjunto de si mesmo.

R é transitiva pois se A é subconjunto de B e B é subconjunto de C, então A é subconjunto de C.

R é anti-simétrica pois se A é um subconjunto de B e B é subconjunto de A, então A=B.

9


Propriedades das Relações Binárias -

Resumo

Reflexiva é uma relação na qual todo elemento está relacionado consigo mesmo. Na igualdade sobre os números reais isso é claramente verificado.

Simétrica indica que toda vez que um elemento estiver relacionado com outro, a vice-versa também estará relacionada. Numa relação de parentesco entre duas pessoas isso é um fato verdadeiro.

Transitiva significa que se um número relaciona-se com um segundo número e este com um terceiro, pode-se obter a relação do primeiro com o terceiro. A relação menor sobre os números naturais ilustra essa propriedade.

Anti-simétrica não é o inverso da simétrica e sim estabelece que não é possível inverter os elementos, ou seja (y,x) R, a menos que x=y.

10


Ex. 05: Seja S={1,2,3} e R uma relação em S. Se R é

reflexiva, quais os pares ordenados tem que pertencer a R?

Ex. 06: Se uma relação R em S é simétrica e se (a,b) R,

que outro par ordenado tem que pertencer a R?

Ex. 07: Se uma relação R em S é anti-simétrica e se (a,b) e

(b,a) R, o que tem que ser verdade nessa condição?

Ex. 08: Identifique as propriedades de cada relação abaixo:

a. S = N; R={(x,y) | x + y é par}

b. S = Z+; R={(x,y) | x divide y}

11


Representação – A relação pode ser representada através de Diagrama de Venn.

Domínio e Imagem de uma Relação - O Domínio de uma relação R, denotado D(R), é o conjunto formado pelos primeiros elementos de cada par ordenado da relação. No exemplo anterior, o domínio é o conjunto D(R) = {1,3,5}

A Imagem de uma relação R, denotada I(R), é o conjunto formado pelos segundos elementos de cada par ordenado da relação. exemplo anterior, o domínio é o conjunto I(R) = {3,9,15}

1

3

5

3

9

15

20

12


Relação como Grafos

Toda relação R: AB pode ser representada a partir de um

grafo direcionado com arestas ligando cada par ordenado (a,b), com origem em a e destino em b.

Ex.: Dados A={1,2,3} e B={4,5}

A X B: AB {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5)}

<:AA = {(1,2), (1,3), (2,3)}

1

2

3

4

5

1 2

3

13


Relação como Matrizes

A relação R: AB pode ser representada na forma de matriz, o que facilita sua implementação em sistemas computacionais.

Seja A={a1, a2, ...an} e B={b1, b2, ...bm} dois conjuntos finitos. A representação da relação R como matriz é como se segue: O número de linhas é n (número de elementos do domínio).

O número de colunas é m (n° de elementos do Contra-Domínio)

A matriz tem n * m posições e cada posição contém um valor lógico – verdadeiro ou falso.

Se (ai, bj) R, então a posição contém o valor verdadeiro (1); caso contrário, contém o valor falso (0).

Ex.: Sejam A={a}, B={a,b} e C={0,1,2}. As seguintes relações são representadas como matrizes:

1 - A X B: AB 2 – S={(0,a), (1,b)}: CB 3 - =: AB

A X B a b

a 1 1

S a b

0 1 0

1 0 1

2 0 0

= a b

a 1 0

14


Relação Dual

Seja relação R: AB. A Relação Dual, Oposta ou Inversa é denotada

por: R-1: BA e é obtida pela inversão dos componentes de cada par ordenado.

R-1= {(b,a) | (a,b) R}

A X B: AB , (A X B)-1 = B X A: BA

A matriz da relação dual é a matriz transposta da matriz da relação.

O grafo da relação dual é o grafo resultante da inversão dos sentidos das arestas.

Composição de Relações

Sejam as relações R: AB e S:B C. A composição de R e S, resultando na relação:

S R: A C, tal que:

S R = {(a,c) | (b B)(aRb bSc)}

15


Composição de Relações

Ex: A composição das relações R: AB e S:B C é SR: A C, sendo que:

R = {(a,1), (b,3), (b,4), (d,5)}

S = {(1,x), (2,y), (5,y), (5,z)}

S R = {(a,x), (d,y), (d,z)}

A composição das relações é mostrada no diagrama abaixo:

a b c d

1 2 3 4 5

x y z

A B C

R S

S R

16


Tipos de Relações – Uma relação pode ser classificada nos

seguintes tipos, os quais não são mutuamente exclusivos:

Funcional

Injetora

Total

Sobrejetora

Monomorfismo

Epimorfismo

Isomorfismo

Os tipos acima possuem noção de dualidade que pode simplificar o

estudo e a respectiva compreensão de cada tipo.

Funcional é o dual de injetora e vice-versa

Total é o dual de sobrejetora e vice-versa.

Monomorfismo é o dual de epimorfismo e vice-versa.

Isomorfismo é dual de si mesmo.

17


Relação Funcional – define o conceito de função.

Seja a relação R: AB. R é funcional se e somente se:

(aA)(b1B)(b2B)(aRb1 aRb2 b1=b2)

Ou seja, em uma relação funcional, cada elemento de A está relacionado com, no máximo, um elemento de B.

Ex.: Sejam A={a}, B={a,b} e C={0,1,2}. Então:

Matriz: existe, no máximo, um valor verdadeiro em cada linha da matriz.

Grafo: existe, no máximo, um arco partindo de cada nó.

São relações funcionais:

: AB

{(0,a), (1,b)}: CB

=: AB

Não são relações funcionais:

A X B: AB

<: CC

18


Relação Injetora – o inverso (dual) de uma funcional.

Seja a relação R: AB. R é injetora se e somente se:

(bB)(a1A)(a2A)(a1Rb a2Rb a1=a2)

Ou seja, em uma relação injetora, cada elemento de B está relacionado com, no máximo, um elemento de A.


Matriz: existe, no máximo, um valor verdadeiro em cada coluna da matriz.

Grafo: existe, no máximo, um arco chegando em cada nó.

São relações injetoras:

: AB

{(0,a), (1,b)}: CB

=: AB

A X B: AB

Não são relações injetoras:

B X A: BA

<: CC

19


Relação Total

Seja a relação R: AB. R é total se e somente se: (aA)(bB)(aRb)

Ou seja, em uma relação total, para cada elemento de A, existe pelo menos, um elemento de B.


Matriz: existe, pelo menos, um valor verdadeiro em cada linha da matriz.

Grafo: existe, pelo menos, um arco partindo de cada nó.

São relações totais:

=: AB

A X B: AB

Não são relações totais:

: AB

{(0,a), (1,b)}: CB

<: CC

20


Relação Sobrejetora

Seja a relação R: AB. R é sobrejetora se e somente se: (bB)(aA)(aRb)

Ou seja, em uma relação sobrejetora, para cada elemento de B, existe pelo menos, um elemento de A.


Matriz: existe, pelo menos, um valor verdadeiro em cada coluna da matriz.

Grafo: existe, pelo menos, um arco chegando em cada nó.

São relações sobrejetoras:

=: AA

{(0,a), (1,b)}: CB

A X B: AB

Não são relações sobrejetoras:

=: AB

: AB

<: CC

21


Monomorfismo ou monorrelação

Seja a relação R: AB. R é um monomorfismo se e somente se for simultaneamente TOTAL e INJETORA.

Ou seja, em um monomorfismo, cada elemento de B, está relacionado com, no máximo, um elemento de A e para cada elemento de A, existe pelo menos, um elemento de B.


Matriz: existe, pelo menos, um valor verdadeiro em cada linha (total) e no máximo um valor verdadeiro em cada coluna(injetora) da matriz.

Grafo: existe, pelo menos, um arco partindo (total) e no máximo, um arco chegando (injetora) em cada nó.

São monomorfismos:

=: AB

A X B: AB

Não são monomorfismos:

B X C: BC

: AB

{(0,a), (1,b)}: CB

<: CC

22


Epimorfismo ou Epirrelação

Seja a relação R: AB. R é um Epimorfismo se e somente se for simultaneamente FUNCIONAL e SOBREJETORA.

Ou seja, em um Epimorfismo, cada elemento de A, está relacionado com, no máximo, um elemento de B e para cada elemento de B, existe pelo menos, um elemento de A.


Matriz: existe, pelo menos, um valor verdadeiro em cada coluna (sobrejetora) e no máximo um valor verdadeiro em cada linha(funcional) da matriz.

Grafo: existe, pelo menos, um arco chegando (sobrejetora) e no máximo, um arco partindo (funcional) em cada nó.

São epimorfismos:

=: AA

{(0,a), (1,b)}: CB

Não são epimorfismos:

=: AB

: AB

A X B: AB

<: CC

23


Isomorfismo ou Isorrelação

Seja a relação R: AB. R é um Isomorfismo se e somente se for simultaneamente TOTAL, FUNCIONAL, INJETORA E SOBREJETORA.


Definição para grafos e matrizes ? Enviar por e-mail – [email protected]

São isomorfismos:

:

{(0,1), (1,2), (2,0)}: CC

Não são isomorfismos:

: AB

A X B: AB

<: CC

24


Exercício

1. Dados os conjuntos A = {2,3,4,5} e B = {3,4,5,6,10},

determine as relações R1 = A X B: AB e R2= <: A X B

AB, determinando o(s) tipo(s) de relação de R1 e R2 e

faça a representação de cada uma por matriz e por grafo.

25


Funções Parciais Uma função parcial é uma relação funcional. Se a relação

funcional for total, então é denominada de função total ou

simplesmente função.

É uma função que não é definida para todos os elementos

do domínio. Normalmente, as abordagens matemáticas são

focadas no conceito de função total, mas o estudo de funções

parciais é tão importante quanto o de total.

Relações

Funções Parciais

Funções Totais

26


Função Parcial Todos os conceitos vistos para uma relação funcional são válidos para

funções parciais, como por exemplo:

As terminologias de domínio, imagem etc..

Os tipos injetora, sobrejetora etc..

Definição: uma Função Parcial é uma relação funcional f A x B

Cada elemento do domínio está relacionado com no máximo,

um elemento do contradomínio.

Uma função parcial é denotada por f: AB e o par (a,b)f é

denotado por f(a)=b.


São funções parciais:

: AB

{(0,a), (1,b)}: CB

=: AB

Não são funções parciais:

A X B: AB

<: CC

T A x B, T={(a,a), (a,b)}

27


Função Parcial

Matriz: existe, no máximo, um valor verdadeiro em cada linha da matriz.

Grafo: existe, no máximo, um arco partindo de cada nó.

Ex.: Sejam A ={0,1,2}, B ={a,b} e f={(0,a), (1,b)}: AB

A operação div: tal que div(x, y) = x/y é uma função parcial pois não é definida para (x, 0), qualquer que seja x.

f a b

0 1 0

1 0 1

2 0 0

0 a

1 b

28


Função Parcial Dual (oposta, inversa)

A relação dual de uma função parcial não necessariamente é uma função parcial.

Seja A={0,1,2} e a função parcial f:A x A tal que f={(0,2),(1,2) }. Assim, a relação dual (inversa) de f é f-1 ={(2,0),(2,1)}, que claramente não é uma relação funcional e então, não é uma função parcial.

Lembrar que o dual de uma relação funcional é injetora.

Composição de Funções Parciais

Por definição, a composição de relações funcionais é uma

relação funcional. Daí, a composição resultante de funções

parciais também é uma função parcial.

29


Composição de Funções Parciais

Ex.: A composição das funções parciais f: AB e g: B C é g f: A C, sendo que:

f = {(a,1), (c,5), (d,5)}

g = {(1,x), (2,y), (4,y), (5,z)}

g f = {(a,x), (c,z), (d,z)}

A composição das funções é mostrada no diagrama abaixo:

a b c d

1 2 3 4 5

x y z

A B C

f g

g f

30


Função Total

Uma função total ou simplesmente função é uma função parcial f: AB a qual é total.

É uma função que é definida para todos os elementos do domínio (A), ou seja devem ser válidas as seguintes proposições:

(aA)(bB)(aRb) e

(aA)(b1B)(b2B)(aRb1 aRb2 b1=b2)

Sejam A={a}, B={a,b} e C={0,1,2}. Então:

São funções:

h C X B, h={(0,a), (1,b), (2,b)}

{(0,a), (1,b), (2,b)}: CB

p A X B, xpy x=y, p = {(a,a)}

=: AB

Não são funções:

R A X B, R=

: AB

S C X B, S={(0,a), (1,b)}

{(0,a), (1,b)}: CB

<: CC

31


Função Em termos de notação como matriz ou grafo, basta

considerar que uma função é uma relação funcional e total. Assim:

Matriz: existe, exatamente, um valor verdadeiro em cada linha da matriz.

Grafo: existe, exatamente, um arco partindo de cada nó.

Função Injetora - Seja a função f: AB. f é injetora se e somente se: (bB)(a1A)(a2A)(f(a1) =b f(a2) =b a1=a2)

Ou seja, em uma função injetora, cada elemento de B está relacionado com, no máximo, um elemento de A.

Ex1. f: | f(x) = x3, é injetora.

Ex2. f: | f(x) = x2, não é injetora.

Ex3. f: | f(x) = x2, é injetora.

32


Em uma Função injetora, cada elemento do co-domínio é imagem de no máximo, um elemento do domínio.

Função Sobrejetora - Seja a função f: AB. f é sobrejetora se e somente se:

(bB)(aA)(f(a)=b)

Ou seja, em uma relação sobrejetora, para cada elemento de B, existe pelo menos, um elemento de A.

Em uma Função sobrejetora, todo elemento do co-domínio é imagem de pelo menos, um elemento do domínio.

Função bijetora (ou isomorfismo) – Quando uma função é, simultaneamente, injetora e sobrejetora.

Em uma Função bijetora, todo elemento do co-domínio é imagem, exatamente, de um elemento do domínio.

3 4 5

x

y

x

A B

f

33


Exercício

1. Considerem-se as funções adição sobre o conjunto dos números naturais

(+: x ), divisão, sobre o conjunto dos números reais (/: x

), e raiz quadrada, sobre o conjunto dos números inteiros (: ).

Verificar as propriedades (injetora, sobrejetora e total) de cada função (1).

= Números naturais {0,1,2..} =Números inteiros {...-2,-1,0,1,2...} = Números reais.

Injetora Sobrejetora Total

+: x Não Sim Sim

/: x Não Sim Não

: Sim Não Não

(1) Do Livro Linguagens Formais – Teorias, Modelagem e Implementação, Ramos, M. V. M., Neto, J.J. e Vega, I. S. – Bookman, 2009.

34


Função Dual (Oposta)

Da mesma forma que em funções parciais, a relação dual de uma função (total) não necessariamente é uma função.

Exemplos

Seja A = {0,1,2} e a função R A x A tal que R={(0,2),(1,2),(2,1)}. Assim, a relação dual (inversa) de R é R-1 = {(2, 0), (2, 1), (1, 2) }, que não é uma relação funcional e então, não é uma função.

Seja f: {0, 1} → {0, 1, 2} tal que f = { (0, 0), (1, 1) }. Assim,

sua dual possui o mesmo conjunto de pares ordenados, { (0, 0), (1, 1) }, mas não é função.

35


Composição de Funções Totais

A composição das funções totais f: AB e g: B C é g f: A C, sendo que:

f = {(a,1), (b,2), (c,5), (d,5)}

g = {(1,x), (2,y), (3,y), (4,y), (5,z)}

g f = {(a,x), (b,y), (c,z), (d,z)}

A composição das funções é mostrada no diagrama abaixo:

a b c d

1 2 3 4 5

x y z

A B C

f g

g f


Composição de Funções

Sejam f: AB e g: B C, então a função g f: A C, é uma função definida por (g f)(a) = g[f(a)] onde a A.

Ex. 1: Sejam A={1,2,3,4,5}, B={6,7,8,9} e C={10,11,12,13}. Sejam f: AB e g: B C, definidas por:

f = {(1,6), (2,6), (3,9), (4,7), (5,7)}

g = {(6,10), (7,11), (8,12), (9,13)}

Então g f = {(1,10), (2,10), (3,13), (4,11), (5,11)}

(g f)(2) = g[f(2)] = g[6] = 10

1 2 3 4 5

6 7 8 9

10 11 12 13

A B C

f g



Ex. 2: Sejam f, g: dada por f(x) = x2+1 e g(x)=2x-3. Quanto vale (g f)(4)?

(g f)(4) = g[f(4)] = g(42+1) = g(17) = 2(17)-3 = 31.

De modo geral:

(g f)(x) = g[f(x)] = g(x2+1) = 2(x2+1) -3 = 2x2+2-3 = 2x2- 1

Por que g f e não f g?

A notação g f significa que primeiro calculamos f e em seguida g (em g f (a), f está “mais próximo” de (a)).

O domínio de g f é o mesmo domínio de f.

A existência da função g f, não assegura a definição de f g.

Veja g(6) no Ex. 1.

Quando ambas são definidas, geralmente g f f g.



Ex. 3: Sejam A={1,2,3,4,5}, f: AA e g: A A, definidas por:

f = {(1,1), (2,1), (3,1), (4,1), (5,1)}

g ={(1,5), (2,4), (3,3), (4,2), (5,1)}

Então g f e f g são:

g f = {(1,5), (2,5), (3,5), (4,5), (5,5)}

f g = {(1,1), (2,1), (3,1), (4,1), (5,1)}

g f f g

Exercício: Sejam f, g: dada por f(x) = x2+1 e g(x)=2x-3. Mostre que:

a) (g f)(4) (f g)(4)

b) (g f)(x) (f g)(x)



Associatividade – Sejam os conjuntos A, B, C e D e sejam f: AB, g: B C e h: DC, então:

h (g f) = (h g) f

[h (g f) (a)] = h [(g f) (a)] = h[g[f(a)]]

[(h g) f](a) = (h g) [f(a)] = h[g[f(a)]]

Logo: h (g f) = (h g) f


Função Identidade

Seja um conjunto A. A função identidade em A (IdA) é a função cujo domínio é A e para todo a A, IdA= a, ou f(a) = a.

IdA = [(a,a) a A]

Sejam os conjuntos A e B, f: AB, então:

f IdA = IdB f = f

(f IdA) (a)= f (IdA(a)) = f(a) = f

(IdB f) (b)= IdB(f (b)) = IdB (b) = f

Ex.: Seja A={1,2,3}, B={4,5,6}, f: AB dada por f:{(1,4), (2,5), (3,6)}. Verifique que f IdA = IdB f = f

IdA = {(1,1), (2,2), (3,3)} Idb= {(4,4), (5,5), (6,6)}


41

1 2 3

1 2 3

4 5 6

A A B

IdA f

f IdA

Ex.: Seja A={1,2,3}, B={4,5,6}, f: AB dada por f:{(1,4), (2,5), (3,6)}. Verifique que f IdA = IdB f = f

IdA = {(1,1), (2,2), (3,3)} Idb= {(4,4), (5,5), (6,6)} f IdA = f[IdA] = {(1,4), (2,5), (3,6)} = f IdB f = IdB[f] = {(1,4), (2,5), (3,6)} = f

4 5 6

B

IdB

IdB f


1

Prof. Jorge [email protected] - www.univasf.edu.br/~jorge.cavalcanti

Matemática Discreta Matemática Discreta ––1212

Hashing

� Introdução� Hashing (espalhamento) é uma forma simples, fácil de

implementar e intuitiva de se organizar grandes quantidades de dados.

� Permite armazenar e encontrar rapidamente dados por chaves.� Possui como idéia central a divisão de um universo de dados a ser organizado em subconjuntos mais gerenciáveis.

2

� Possui dois conceitos centrais:� Tabela de Hashing – estrutura que permite acesso aos subconjuntos;

� Função de Hashing – função que realiza o mapeamento entre valores da chave e entradas da tabela.

Função Hashingh(k)

Tabela Hashingchaves

Subconjuntos

Ex: Arrays e listas Ex: Árvores

Hashing

� Por que usar Hashing?

� Estruturas de busca sequencial levam tempo até encontrar o elemento desejado.

3

5 2 6 1 7 8 4 9

5 2 6 1 4

8

2

6

4

1

9

Hashing

� Por que usar Hashing?

� Em algumas aplicações, é necessário obter o valor com poucas comparações, logo, é preciso saber a posição em que o elemento se encontra, sem precisar varrer todas as chaves.

� A estrutura com tal propriedade é chamada de tabela hashing.

4

64 11 20 7

0 1 2 3 4 5 6 7

20 ?

20 % 8 = 4

20 45 ?

45 % 8 = 5

hashing.� A tabela segue a propriedade da função de hashing estabelecida.

� Ex: h(k)= k mod n, n=8

Hashing

� Ex.: Considere uma chave de identificação numérica com valores entre 0 e 1000 bem como uma tabela de armazenamento com entradas indexadas de 1 a 23. Uma função de hashing simples e razoável seria:hash= h:{0,1,...,1000}→{1,2,3,...,23}, tal que para c∈{0,1,...,1000}, tem-se que:h(c) = (c mod 23) + 1, onde mod calcula o resto da divisão inteira.

5


Tabela Hashing0 … 134 … 237 … 360 … 387 … 452 … 766 … 1000

Subconjuntos

(c mod 23) + 1

1 … 8 … 16 … 20 … 23

Chave 452 623 766 237 134 360 285

End 16 3 8 8 20 16 10

Hashing

� Então, se possuímos um universo de dados classificáveis por chaves, podemos:

� Criar um critério simples para dividir este universo em subconjuntos com base em alguma qualidade do domínio das chaves;

� Saber em qual subconjunto procurar e colocar uma chave;� Gerenciar esses subconjuntos menores por algum método simples;

� Para isso, precisamos:Saber quantos subconjuntos eu quero criar e uma regra de cálculo

6

� Saber quantos subconjuntos eu quero criar e uma regra de cálculo que nos diga, dada uma chave, em qual subconjunto devo procurar pelos dados com esta chave ou colocar este dado, caso seja um novo elemento;

� Esta regra é uma Função de Hashing, também chamada de função de cálculo de endereço, função de randomização ou função de aleatorização.

� Possuir um índice que permita encontrar o início do subconjunto certo, depois de calcular o hashing. Isto é uma tabela de hashing.

� A função hash é a responsável por gerar um índice a partir de determinada chave.

� A Tabela hash pode apontar para posições na forma de vetores simples ou listas.

Função Hashing

Tabela Hashingcha

Hashing

7

Função Hashingh(k)a

ves

Vetor simples com valores


Tabela Hashingchaves

Vetor de listas

Hashing

� Ex.:

8

Hashing

� Função de Hashing� Possui o objetivo de transformar o valor de chave de um elemento de dados em uma posição para este elemento em um dos b subconjuntos definidos.

� Deve procurar dividir o universo de chaves K = {k0,..,km}em b subconjuntos de mesmo tamanho.

� A probabilidade de uma chave kj pertencente a K aleatória qualquer cair em um dos subconjuntos bi: i

9

aleatória qualquer cair em um dos subconjuntos bi: i pertencente a [1,b] deve ser uniforme.

� Se a função de Hashing não dividir K uniformemente entre os bi, a tabela de hashing pode degenerar. � O pior caso de degeneração é aquele onde todas as chaves caem em um único conjunto bi.

� A função "primeira letra" do exemplo anterior é um exemplo de uma função ruim. � A letra do alfabeto com a qual um nome inicia não é distribuída uniformemente. Quantos nomes começam com "X"?

Hashing

� Uma função de Hashing deve procurar satisfazer as seguintes condições: � Ser simples de calcular; � Assegurar que elementos distintos tenham índices distintos; � Gerar uma distribuição equilibrada para os elementos dentro do array ou subconjuntos;

� Deve ser aleatória, ou pseudo-aleatória, para prevenir adivinhações do valor original;

10

adivinhações do valor original; � Deve ser única, onde é praticamente impossível dois endereços diferentes serem gerados a partir da mesma chave.

� Deve ter mão única, o que significa ser muito difícil a partir do endereço e dos valores originais obter a função.

� A forma de transformação mais simples e utilizada é a Divisão, como vista anteriormente:� h(kj) = mod(kj,b) + 1, onde b (preferencialmente um número primo) é o número de subconjuntos em dividimos os dados.

Hashing

� A função ideal é aquela que gera um endereço diferente para cada um dos possíveis valores das chaves (Função injetora).

� Porém nem sempre é possível e ai geram colisões, ou seja, em alguns casos, podem ser atribuídos mesmos endereços a chaves com valores diferentes.

� Diferenças entre hashing e indexação:No espalhamento os endereços parecem ser aleatórios –

11

� No espalhamento os endereços parecem ser aleatórios –não existe conexão óbvia entre a chave e o endereço, apesar da chave ser utilizada no cálculo do endereço

� No espalhamento duas chaves podem levar ao mesmo endereço (colisão) – portanto as colisões devem ser tratadas.

Hashing

� Chaves não-numéricas:

� Ex.:Suponha que foi reservado espaço para manter 1.000 registros e considere a seguinte h(K):– Obter as representações ASCII dos dois primeiros caracteres do nome;

– Multiplicar estes números e usar os três dígitos menos significativos do resultado para servir de endereço.

12

Nome Cod ASCII 2 primeiras letras

Produto Endereço

BALL 66 65 66 x 65 = 4.290 290

LOWELL 76 96 76 x 96 = 6.004 004

TREE 84 82 84 x 82 = 6.888 888

Hashing

� Continuação Exemplo:

13

� O ideal é usar uma função de espalhamento perfeita, que não produz colisão, mas...

� Duas palavras diferentes podem produzir o mesmo endereço (colisão), pois as chaves são sinônimas

� Temos, h(LOWELL)=h(LOCK)=h(OLIVER)

Hashing

� Colisões� Colisão: quando duas ou mais chaves são mapeadas na mesma posição da tabela de hash;

� Tipicamente, o número de posições numa tabela de hash é pequeno comparado com o universo de chaves possíveis;

� A maioria das funções de hash usadas na prática mapeiam várias chaves na mesma posição na tabela de hash.

14

várias chaves na mesma posição na tabela de hash.

� Problemas de hashing:� Encontrar funções de hash que distribuam as chaves de modo uniforme e minimizem o número de colisões;

� Resolver colisões.

Colisões� Devido ao fato de existirem mais chaves que posições, é comum que várias chaves sejam mapeadas na mesma posição.

� Ex: 45 % 8 = 5 1256 % 15 = 1121 % 8 = 5 356 % 15 = 1193 % 8 = 5 506 % 15 = 11

Hashing

15

93 % 8 = 5 506 % 15 = 11

� O que fazer quando mais de um elemento for inserido na mesma posição de uma tabela hash?

Endereçamento Fechado (Closed Addressing)

� No endereçamento fechado, a posição de inserção não muda, logo, todos devem ser inseridos na mesma posição, através de uma lista ligada em cada uma.

Hashing

16

0

1

2

3

4

20 % 5 = 0 20

18 % 5 = 3

1825 % 5 = 0colisão com 20

25

� A busca é feita do mesmo modo: calcula-se o valor da função hash para a chave, e a busca é feita na lista correspondente.

� Se o tamanho das listas variar muito, a busca pode se tornar ineficiente, pois a busca nas listas é seqüencial:


Hashing

17

tornar ineficiente, pois a busca nas listas é seqüencial:

0

1

2

3

20 4 0 88 32

15 11

60

� Por esta razão, a função hash deve distribuir as chaves entre as posições uniformemente:

0 1 2 3 4 5 6


Hashing

18

0 15 10

31

4

88

13

20

� Se o tamanho da tabela for um número primo, há mais chances de ter uma melhor distribuição.

� No endereçamento aberto, quando uma nova chave é mapeada para uma posição já ocupada, uma nova posição é indicada para esta chave.

� A nova posição é incrementada até que uma posição vazia seja encontrada (linear probing):

Endereçamento Aberto (Open Addressing)

Hashing

19

64 11 20 7

0 1 2 3 4 5 6 7

27 ?

27 % 8 = 3

11 20 27

Valores: 52, 78, 48, 61, 81, 120, 79, 121, 92Função: hash(k) = k % 13

Tamanho da tabela: 13

0 1 2 3 4 5 6 7 8 9 10 11 12

Endereçamento Aberto (Open Addressing)

Hashing

20

0 1 2 3 4 5 6 7 8 9 10 11 12

52

52

78

78 48

48

61

61

81

81

120

120

79

79

121

121

92

92

� Para fazer uma busca com endereçamento aberto, basta aplicar a função hash, e a função de incremento até que o elemento ou uma posição vazia sejam encontrados.

� Porém, quando um elemento é removido, a posição vazia pode ser encontrada antes, o que significaria fim de busca, MESMO que o elemento PERTENÇA à tabela:

Endereçamento Aberto – Remoção

Hashing

21

MESMO que o elemento PERTENÇA à tabela:

64 11 20 7

Inserção do 27

Remoção do 20

Busca pelo 2711 272011 27

27? Não

11

Fim da busca? Sim

� Para contornar esta situação, mantemos um bit (ou um campo booleano) para indicar que um elemento foi removido daquela posição:

27? Não

Endereçamento Aberto – Remoção

Hashing

22

64 11 20 711 2720X11 27

27? Não

11

Fim da busca? Não

X 27

� Esta posição estaria livre para uma nova inserção, mas não seria tratada como vazia numa busca.

� Nesta política de hashing, há o que chamamos de fator de carga (load factor). Este fator indica a porcentagem de células da tabela hash que estão ocupadas, incluindo as que foram removidas.

� Quando este fator fica muito alto (ex: excede 50%), as operações na tabela passam a demorar mais, pois o

Endereçamento Aberto – Expansão

Hashing

23

64 1 X 11 X 9 7

operações na tabela passam a demorar mais, pois o número de colisões aumenta.

9 ? 1 X 11 X 9

� Quando isto ocorre, é necessário expandir o array que constitui a tabela, e reorganizar os elementos na nova tabela. Como podemos ver, o tamanho atual da tabela passa a ser um parâmetro da função hash.


Hashing

24

Tamanho = 13

34 40 X 11 95

3440 1195

Tamanho = 7

� O momento ou critério para expandir a tabela pode variar:� Impossibilidade de inserir um elemento� Metade da tabela está ocupada� O load factor atingiu um valor limite escolhido


Hashing

25

� A terceira opção é a mais comum, pois é um meio termo entre as outras duas.

� Muitas colisões diminuem muito o tempo de acesso e modificação de uma tabela hash. Para isso é necessário escolher bem:� a função hash� o tratamento de colisõeso tamanho da tabela

Quando não usar Hashing?

Hashing

26

� o tamanho da tabela� Quando não for possível definir parâmetros eficientes, pode ser melhor utilizar árvores balanceadas (como AVL), em vez de tabelas hash.

� + Hashing em Estruturas de Dados…

1 - Ilustre a organização final de uma Tabela Hash após a inserção das seguintes chaves: 35, 99, 27, 18, 65, 45. Considere a tabela com tamanho 6 (posições 0 a 5), o método da divisão inteira como função de hashing e tratamento de colisão por endereçamento fechado.Considere também que os números possíveis de chaves

Exercícios:

Hashing

27

Considere também que os números possíveis de chaves estão no intervalo entre 1 a 100.

2 - Idem à questão anterior, porém o tratamento de colisão será por endereçamento aberto (linear probing).

3 – Seja uma função h(k) = k % 11 e os dados abaixo obtidos para uma seqüência de chaves:

Resolva as colisões por endereçamento aberto.

Exercícios:

Hashing

key 82 31 28 4 45 27 59 79 35

h(key) 5 9 6 4 1 5 4 2 2

28

Resolva as colisões por endereçamento aberto.

1


Prof. Jorge [email protected]/~jorge.cavalcantiwww.twitter.com/jorgecav


2

Introdução à Álgebra de Boole

� Podemos lembrar das fbfs da lógica proposicional e associar a elas um certo tipo de função.

� Uma fbf proposicional com n letras, define uma função com domínio {V,F}n e um contradomínio {V,F}.

� O domínio consiste em todas as n-uplas de valores V/F. Para cada n-upla, associamos umm único valor V ou F.

� Ex. 01: Seja a fbf A∨∨∨∨B’. Sua tabela-verdade é:

A B B’ A ∨∨∨∨ B’

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

� A imagem da dupla (F,V) sobre essa função é F.� Se chamarmos essa função de w, então w(F,V)=F, w(V,V) = V.

3


� Ex. 02: Denote por f a função definida pela fbf A∧∧∧∧(B∨∨∨∨C’). Qual o valor de f(V,V,F) e f(F,V,F)?

A B C C’ B∨∨∨∨C’ A ∧∧∧∧ (B∨∨∨∨C’)

V V V F V V

V V F V V V

V F V F F F

V F F V V V

F V V F V F

F V F V V F

F F V F F F

F F F V V V

�f(V,V,F)=V�f(F,V,F)=F

4


� Supondo que uma fbf proposicional P tem n letras de proposição.

� Então cada linha da tabela-verdade da fbf associa um valor, V ou F a uma n-upla de valores V/F.

� A tabela-verdade inteira define uma função f:{V,F}n →{V,F}, conforme os exemplos 01 e 02.

� As funções associadas a tautologias são da forma {V,F}n → {V} e as contradições são da forma {V,F}n →{F}.

� Podemos convencionar que qualquer fbf proposicional P com n letras de proposição, o símbolo P não denota apenas a fbf, mas também a função correspondente definida pela tabela-verdade.

� Se P e Q são fbfs equivalentes, então tem a mesma tabela-verdade, logo definem a mesma função.

� Podemos então escrever P=Q ao invés de P⇔Q.

5


� Dessa forma, a lista de equivalências tautológicas da lógica proposicional podem ser escritas como a seguir:

1a. A ∨ B = B ∨ A 1b. A ∧ B = B ∧ A (comutatividade)2a. (A∨B)∨C = A∨(B∨C) 2b. (A∧B)∧C = A∧(B∧C) (assoc.)3a. A∨(B∧C)=(A∨B)∧(A∨C) 3b.A∧(B∨C)= (A∧B)∨(A∧C) (distrib.) 4a.A ∨ 0 = A 4b. A ∧ 1 = A (elementos neutros) 5a. A ∨ A' = 1 5b. A ∧ A' = 0 (complemento)

� Analogamente, as identidades básicas envolvendo conjuntos são listadas a seguir:

1a. A ∪ B = B ∪ A 1b. A ∩ B = B ∩ A (comutatividade)2a. (A∪B)∪C=A∪(B∪C) 2b.(A∩B)∩C = A∩(B ∩C) (assoc.)3a. A∪(B∩C)=(A∪B)∩(A∪C) 3b.A∩(B∪C)= (A∩B)∪(A∩C) (distrib.)4a. A ∪ ∅ = A 4b. A ∩ S = A (elementos neutros)5a. A ∪ A' = S 5b. A ∩ A' = ∅ (complemento)

� ∨ e ∪, ∧ e ∩, 0 e ∅, 1 e S. � Que conclusões podemos tirar dessa semelhança? 6


� Dois exemplos que tem propriedades em comum (equivalências tautológicas e identidades entre conjuntos).

� Abstraindo as propriedades comuns, é possível definir uma estrutura matemática que incorpora essas propriedades, como um modelo ou generalizaçãodessas propriedades.

� Supondo que queremos caracterizar formalmente as semelhanças entre a lógica proposicional e a teoria dos conjuntos.

� Em cada caso estamos falando de elementos de um conjunto: um conjunto de fbfs ou um conjunto de subconjuntos de S.

� Em cada caso temos duas operações binárias e uma operação unária que age nos elementos do conjunto:

� Disjunção/conjunção/negação� União/interseção/complemento

7


� Existem 02 elementos diferenciados no conjunto: 0/1 ou ∅/S.

� São válidas 10 propriedades em cada caso (1a....5b).� Sempre que todas essas características estiverem presentes, dizemos que temos uma Álgebra de Boole.

� Álgebra de Boole – é um conjunto B no qual estão definidas duas operações binárias, + (ou) e • (e), e uma operação unária ´, e que contém dois elementos distintos, 0 e 1, tais que as seguintes propriedades são válidas, quaisquer que sejam x, y e z ∈ B:

1a. x + y = y + x 1b. x • y = y • x (comutatividade)2a. (x+y)+z = x+(y+z) 2b. (x•y)•z = x•(y•z) (assoc.)3a. x+(y•z)=(x+y)•(x+z) 3b.x•(y+z)= (x•y)+(x•z) (distrib.) 4a.x + 0 = x 4b. x • 1 = x (elementos neutros) 5a. x + x' = 1 5b. x • x' = 0 (complemento)

8


� Álgebra de Boole são estruturas algébricas que "capturam a essência" das operações lógicas E, OU e NÃO, bem como das operações da teoria de conjuntos soma, produto e complemento.

� Ela também é o fundamento da matemática computacional, baseada em números binários.

� Uma álgebra de Boole é denotada por [B, +, • , ´, 0, 1]� Ex. 03: Seja B={0,1}. Defina as operações binárias + e

• em B por x+y=máx(x,y) e x • y = mín (x,y), a operação unária ‘ e, em seguida, mostre as propriedades 2b (associatividade), 4a e 4b (elementos neutros).

As operações + e • são ilustradas nas tabelas a seguir:+ 0 1

0 0 1

1 1 1

•••• 0 1

0 0 0

1 0 1

9


� Cont Ex. 03: Seja B={0,1}. Defina as operações binárias + e • em B por x+y=máx(x,y) e x • y = mín(x,y), a operação unária ‘ e, em seguida, mostre as propriedades 2b (associatividade) para • e 4a e 4b (elementos neutros).

� A operação unária ‘ é definida também por uma tabela:Como 0’= 1 e 1’= 0, então [B, +, •, 0, 1] é uma álgebra de Boole.

� Pode-se provar as 10 propriedades, verificando todos os casos possíveis.

� A propriedade 2b (associatividade) de • é dada como segue:

‘0 11 0

10


� Cont Ex. 03 – Propriedade associativa para • :

� Propriedade 4a.

� Propriedade 4b.

(0 ⋅ 0) ⋅ 0 = 0 ⋅ (0 ⋅ 0) = 0 (0 ⋅ 0) ⋅ 1 = 0 ⋅ (0 ⋅ 1) = 0 (0 ⋅ 1) ⋅ 0 = 0 ⋅ (1 ⋅ 0) = 0 (0 ⋅ 1) ⋅ 1 = 0 ⋅ (1 ⋅ 1) = 0(1 ⋅ 0) ⋅ 0 = 1 ⋅ (0 ⋅ 0) = 0 (1 ⋅ 0) ⋅ 1 = 1 ⋅ (0 ⋅ 1) = 0 (1 ⋅ 1) ⋅ 0 = 1 ⋅ (1 ⋅ 0) = 0 (1 ⋅ 1) ⋅ 1 = 1 ⋅ (1 ⋅ 1) = 1

0 + 0 = 01 + 0 = 1

0 . 1 = 01 . 1 = 1

11


� Existem propriedades adicionais que são válidas e que podem ser demonstradas usando as propriedades da definição.

� A idempotência da soma x + x = x é válida em qualquer álgebra de Boole, pois:

� Embora a aritmética usual dos inteiros tenha muitas propriedades de uma álgebra de Boole, a idempotência da soma deve convencê-lo de que os inteiros não formam uma álgebra de Boole.� A propriedade x+x=x não é válida para os inteiros com a soma usual, a menos que x seja nulo.

x + x = (x + x) . 1 (4b) = (x + x) . (x + x’) (5a)= x + (x . x’) (3a)= x + 0 (5b)= x (4a)

12


� Cada propriedade na definição de álgebra de Boole tem a sua propriedade dual como parte da definição.

� A dual é obtida permutando-se + com • e 1 com 0.� Cada passo da demonstração de uma propriedade de uma álgebra de Boole pode ser substituída por sua dual, resultando em uma demonstração válida da dual.

� Ex. 04: Demonstre que o dual da idempotência x+x=x, x . x = x

� Uma vez demonstrada uma propriedade de álgebras de Boole, ela pode ser usada para demonstrar outras propriedades.

� Ex.05: a)Provar que a propriedade x + 1 = 1 é válida em qualquer álgebra de Boole. b) Explicitar a propriedade usada em cada passo da demonstração. c) Qual a sua propriedade dual?

13


� A tabela abaixo sugere algumas maneiras para ajudar a provar que uma álgebra de Boole tem uma propriedade da forma “alguma expressão = outra expressão”.

Sugestões para Demonstrações de Identidades

Em geral, é melhor começar pela expressão mais complexa e tentar mostrar que se reduz à expressão mais simples.

Considere somar 0 em alguma forma (como x.x’) ou multiplicar por 1 em alguma forma (como x+x’).

Lembrar da propriedade 3a (distributividade da multiplicação), pois ela não é válida na aritmética usual.

Lembrar da idempotência da soma e da multiplicação x+ x = x e x . x = x.

14


� Se x é um elemento de uma álgebra de Boole B, o elemento x’ é chamado de complemento de x e satisfaz: x + x’= 1 e x . x‘ = 0

� Teorema da Unicidade do Complemento – Dado um elemento x em uma álgebra de Boole, se existe um elemento x1, tal que x + x1 = 1 e x . x1 = 0, então x1 = x’.

� Ex. 05: Seja B = {0, 1, a, a'} e sejam + e • operações binárias em B. A operação unária ' é definida pela tabela

aaáá

‘0 11 0

Suponha que sabemos que [B, +,.,', 0, 1 ] é uma álgebra de Boole. Usando as propriedades válidas para qualquer álgebra de Boole, preencha as tabelas a seguir, que definem as operações binárias + e .:

15


� Cont Ex. 05:

� Ex. 06: Prove as propriedades a seguir para álgebras de Boole, justificando cada passo:

a) (x´)´= x (dupla negação) b)(x+y)´=x´.y´ e (x.y)´=x´+ yć) x + (x.y) = x e x.(x+y)=x (absorção) d) x+y´=x + (x´.y+x.y)´

1

a

1 a+ 0 a´

0

a´

1

a

1 a•••• 0 a´

0

a´

Documents

Matemática Discreta [Jorge Cavalcanti]