Upload
phamnga
View
224
Download
0
Embed Size (px)
Citation preview
Seja R uma relação.
Propriedades da Equivalência
Sejam p, q e r proposições, V tautologia e F contradição 1. Idempotência: , 2. Comutatividade: , 3. Associatividade:
4. Distributividade:
5. Identidade: Elemento Neutro Elemento Absorvente
, , 6. Complementares: , 7. Dupla Negação / Involução: 8. Leis de De Morgan: 9. Absorção: , 10. Transitividade:
Para conjuntos,
Conjunto das partes de A
Lista 3 – Ex 1. a) A soma de dois pares é um par b) A soma de dois ímpares é um par c) A soma de um par com um ímpar é
um ímpar d) A soma de 3 ímpares é um ímpar e) A soma de 4 ímpares é um par f) g) h) i)
2. A soma de três números naturais
consecutivos é um número natural múltiplo de três
3. 4. Se a soma de dois primos é um
primo, então um deles é dois. 5. Existem infinitos números primos 6.
7. 8.
9.
Distributividade do produto cartesiano sobre a união e a intersecção:
Lista 1 – Ex 2.
Ex 4.
a) b)
(contraposição) c)
(redução ao absurdo) d) e) f) g) h) i)
é subconjunto de qualquer conjunto
Diagonal principal da matriz possui somente 1
Matriz simétrica em relação à diagonal principal
Cada elemento de A está relacionado com, no máximo, um elemento de B.
Matriz: Existe, no máximo, um 1 por linha Grafo: Existe, no máximo, uma aresta partindo de cada nodo
Cada elemento de B está relacionado com, no máximo, um elemento de A.
Matriz: Existe, no máximo, um 1 por coluna Grafo: Existe, no máximo, uma aresta chegando em cada nodo
Domínio = Origem Cada elemento de A está relacionado com ao menos um
elemento de B. Matriz: Existe, ao menos, um 1 por linha
Grafo: Existe, ao menos, uma aresta partindo de cada nodo
Imagem = Destino Cada elemento de B está relacionado com, ao menos, um
elemento de A. Matriz: Existe, ao menos, um 1 por coluna
Grafo: Existe, ao menos, uma aresta chegando em cada nodo
Relação Dual = Inversa
Matriz: Transposta. Grafo: Sentidos opostos. Funcional é o dual de injetora e vice-versa Total é o dual de sobrejetora e vice-versa
Associatividade da composição de relações:
Lista 4 – Ex 9.
a) b) c) d) e) f) g) h) i) j)
k) l) m)
Seja R uma relação não-reflexiva. Fecho reflexivo = menor relação que contém R e é reflexiva.
Matriz: Troca-se os 0s da diagonal principal de R por 1s
Seja R uma relação não-simétrica. Fecho simétrico = menor relação
que contém R e é simétrica
Seja R uma relação não-transitiva. Fecho transitivo = menor relação
que contém R e é transitiva
Adição:
Simplificação:
Vacuidade:
Trivial:
Seja
Todo conjunto finito totalmente ordenado é bem ordenado
Ordem Lexicográfica
É a ordem lexicográfica induzida de A* em A
Podemos representar uma ordem parcial em um conjunto finito procedendo do seguinte modo:
Iniciamos com o grafo que representa a relação I. Como a relação é reflexiva, temos um loop em cada nodo. Remova-os. II. Como a relação é transitiva, temos várias arestas só de transitividade.
Remova-as III. Rearranje os nodos de modo que os nodos iniciais fiquem abaixo dos finais
IV. Remova todas as setas. O diagrama final é chamado DIAGRAMA DE HASSE da relação, e contém
informação suficiente para determinar a ordem
Seja um conjunto parcialmente ordenado.
Os elementos minimais e maximais não são necessariamente únicos.
Sejam um conjunto parcialmente ordenado e
Termo inicial = Razão = r
Termo inicial = Razão = r
Seja S um conjunto qualquer.
Uma seqüência é uma função de um subconjunto
de em S.
Seja um conjunto parcialmente ordenado, dizemos que é um RETICULADO se, e somente se, o conjunto formado por quaisquer dois elementos de A possui sup e inf. Ou
seja:
Dados se , entao inf {a,b} = a e sup {a,b} = b Logo, se dois elementos estão relacionados, seu sup e seu inf sempre existem. Desse modo,
para mostrar que um conjunto é um reticulado, basta mostrar que cada par de elementos não comparáveis (não relacionados) possui sup e inf.
Dizemos que uma ordem total T é compatível com uma ordem parcial R se, e somente se, aTb sempre que aRb.
Lema: Seja um conjunto parcialmente ordenado e finito, então A possui pelo menos um elemento minimal
Procedimento: Dados e finito, conjunto parcialmente ordenado
Tomamos a1=elemento minimal de A (existe pelo lema) é um conjunto finito parcialmente ordenado
Se ( , existe, pelo lema, um elemento minimal de .
Tomamos a2=elemento minimal de
Somas e séries
Somas duplas
Troca de Índices
Propriedades das somas
Soma Telescópica
Princípio da Indução
Uma construção é definida indutivamente ou recursivamente se:
A base de indução explica casos elementares
O passo de indução determina como os demais casos são definidos em termos dos anteriores
Uma operação binária (domínio = dois conjuntos), interna (domínio = conjuntos iguais) e fechada (contradomínio = domínio) em um conjunto A é
uma relação Dada uma operação
Dado um conjunto e dada uma operação binária e interna , dizemos que é um:
(sua tabela de operações é simétrica em relação à diagonal principal)
Proposições: 7.2.1: O elemento neutro de
um grupo é único 7.2.2: Seja um grupo e
, então o inverso de é único
7.2.3: (Lei do Cancelamento) Seja um grupo e
, então
Se é um conjunto finito, dizemos que é um
grupo finito Se , dizemos que a
ordem do grupo é .
Pela lei do cancelamento, . Logo, na tabela de operações de um grupo finito não pode haver elementos repetidos na mesma linha ou coluna. Além disso, em cada linha e coluna deve aparecer
o elemento neutro, e onde este aparecer, temos o inverso do elemento. Lista 10 1.Seja uma álgebra de Boole: a) b) c) d)
e) 2. a) b)
(Elemento Neutro) (Elemento Absorvente) (Elemento Absorvente)
(Elemento Neutro)