1. Grafos
1.1. Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde
1.1.1. V - conjunto não vazio: os vértices ou nodos do grafo.
1.1.2. A - conjunto de pares ordenados a=(v,w), v e w ∈ V: as arestas do grafo.
1.2. Ordem
1.2.1. A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G.
1.3. Adjacência
1.3.1. Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w.
1.3.1.1. Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w.
1.3.1.2. Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w.
1.4. Grau
1.4.1. O grau de um vértice é dado pelo número de arestas que lhe são incidentes.
1.4.2. Grau de emissão: o grau de emissão de um vértice v corresponde ao número de arcos que partem de v.
1.4.3. Grau de recepção: o grau de recepção de um vértice v corresponde ao número de arcos que chegam a v.
1.5. Fonte
1.5.1. Um vértice v é uma fonte se grauDeRecepção(v) = 0.
1.6. Sumidouro
1.6.1. Um vértice v é um sumidouro se grauDeEmissão(v) = 0.
1.7. Laço
1.7.1. Um laço é uma aresta ou arco do tipo a=(v,v), ou seja, que relaciona um vértice a ele próprio.
1.8. Grafo Regular
1.8.1. Um grafo é dito ser regular quando todos os seus vértices tem o mesmo grau.
1.9. Grafo Completo
1.9.1. Um grafo é dito ser completo quando há uma aresta entre cada par de seus vértices. Estes grafos são designados por Kn, onde n é a ordem do grafo.
1.10. Grafo Bipartido
1.10.1. Um grafo é dito ser bipartido quando seu conjunto de vértices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vértice de V1 a outro de V2.
1.11. Cadeia
1.11.1. Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices.
1.12. Ciclo
1.12.1. Um ciclo é uma cadeia simples e fechada (o vértice inicial é o mesmo que o vértice final).
1.13. Caminho
1.13.1. Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação.
1.14. Circuito
1.14.1. Um circuito é um caminho simples e fechado.
2. Indução e Recursão
2.1. Princípio da Indução Matemática
2.1.1. Técnica para lidar com tipos de dados.
2.1.2. Que têm uma relação de boa-ordem.
2.1.2.1. Todo conjunto não-vazio de elementos do tipo de dado tem um elemento mínimo segundo esta relação de ordem, exemplo: N
2.1.3. "Efeito Dominó"
2.1.3.1. Ao derrubar a primeira peça, todas as demais peças serão derrubadas.
2.1.4. p(m) é verdadeira para qualquer k ∈ M, p(k) ⇒ p(k + 1), então, para qualquer n ∈ N, p(n) é verdadeira.
2.1.5. Base de indução
2.1.5.1. p(m).
2.1.6. Hipótese de indução
2.1.6.1. p(k).
2.1.7. Passo de indução
2.1.7.1. p(k)⇒ p(k + 1).
2.2. Segundo Princípio da Indução Matemática
2.2.1. Considera não apenas o resultado anterior p(k) mas todos os anteriores para concluir p(k + 1).
2.2.2. p(m) é verdadeira para qualquer k ∈ M: p(m) ∧ p(m + 1) ∧ … ∧ p(k) ⇒ p(k + 1), então, para qualquer n ∈ N, p(n) é verdadeira.
2.3. Recursão
2.3.1. A recursão pode ser usada para definir sequências, funções e conjuntos.
2.3.2. É usado na implementação de algoritmos.
3. Relações
3.1. Intuitivamente, uma relação é uma comparação entre dois objetos; Dois ou mais objetos estão, ou não estão, relacionados de acordo com alguma regra.
3.2. Uma relação é uma correspondência (ou associação) entre elementos de dois conjuntos não vazios.
3.3. Relação Inversa
3.3.1. Seja R uma relação. A inversa de R, denotada por R ^−1, é a relação formada invertendo-se a ordem de todos os pares ordenados em R.
3.4. Propriedades
3.4.1. Seja R uma relação definida em um conjunto A.
3.4.1.1. Se ∀ x ∈ A temos x R x, então R é reflexiva.
3.4.1.2. Se ∀ x ∈ A temos x R x, então R é antirreflexiva.
3.4.1.3. Se ∀ x ∈ A, y ∈ A e z ∈ A temos x R y ∧ y R z ⟹ x R z, dizemos que R é transitiva.
3.4.1.4. Se ∀ x ∈ A e y ∈ A temos x R y ⟹ y R x , então R é simétrica.
3.4.1.5. Se ∀ x ∈ A e ∀y ∈ A temos x R y ∧ y R x ⟺ x = y, então R é assimétrica.
3.5. Relação Binária
3.5.1. Uma relação binária de A em B é todo conjunto R tal que R ⊆ A × B.
3.5.1.1. O conjunto A é chamado domínio da relação.
3.5.1.2. O conjunto B é denominado contradomínio da relação.
3.5.2. Definir uma relação binária R nos conjuntos A e B é especificar um subconjunto de A × B.
3.6. Relações de Ordem Parcial
3.6.1. Uma relação R em um conjunto S é chamada de ordenação parcial ou ordem parcial se tiver as seguintes propriedades
3.6.1.1. Reflexiva: ∀ x ∈ S temos que x, x ∈ R.
3.6.1.2. Anti-simétrica: ∀ x, y ∈ S, se x, y ∈ R → y, x ∉ R.
3.6.1.3. Transitiva: ∀ x, y, z ∈ S, se x, y ∈ R e y, z ∈ R → x, z ∈ R.
3.7. Relação de Ordem Total
3.7.1. Se quaisquer elementos de S forem comparáveis segundo uma relação ≼, então o poset (S, ≼) representa uma relação de ordem total.
4. Funções
4.1. Definição
4.1.1. Uma relação f: A → B recebe o nome de função de A em B se, e somente se, ∀x ∈ A existe um único y ∈ B tal que x, y ∈ f.
4.2. Domínio
4.2.1. Chamamos de domínio o conjunto dos elementos a ∈ A para os quais a função pode ser definida.
4.3. Contradomínio
4.3.1. Chamamos o conjunto de chegada da função de contradomínio.
4.4. Imagem
4.4.1. Chamamos de imagem o conjunto Im formado pelos elementos y ∈ B para os quais existe x ∈ A tal que x, y ∈ f; portanto: a imagem é subconjunto do contradomínio.
4.5. Funções Numéricas
4.5.1. As funções que apresentam maior interesse na Matemática são as funções numéricas, isto é, aquelas em que o domínio A e o contradomínio B são subconjuntos de R.
4.5.1.1. As funções numéricas são também chamadas funções reais.
4.5.2. Observemos que uma função f fica completamente definida quando são dados o seu domínio, seu contradomínio e a lei de correspondência y = f(x).
4.5.3. Quando nos referimos à função f e damos apenas a sentença aberta y = f(x) que a define, subentendemos que Dm é o conjunto de todos os números reais x para os quais é possível calcular f(x).
4.5.4. x ∈ D ⟺ f x ∈ R.
4.6. Igualdade entre funções
4.6.1. Duas funções f: A → B e g: C → D são iguais se, e somente se apresentarem
4.6.1.1. Domínios iguais (A = C).
4.6.1.2. Contradomínios iguais (B = D).
4.6.1.3. f(x) = g(x) para qualquer elemento x do domínio.
4.6.2. Isso equivale a dizer que duas funções f e g são iguais se, e somente se, forem conjuntos iguais de pares ordenados.
4.7. Função Crescente
4.7.1. Uma função f: A → B definida por y = f(x) é crescente em A1 se: x1 < x2 ⟹ f (x1) < f (x2).
4.7.2. Na prática isso significa que uma função é crescente em determinado intervalo (ou conjunto) de valores, se, o valor de y aumentar a medida que aumentarmos o valor de x.
4.8. Função Decrescente
4.8.1. Uma função f: A → B definida por y = f(x) é crescente em A1 se: x1 < x2 ⟹ f (x1) > f (x2).
4.8.2. Na prática isso significa que uma função é decrescente em determinado intervalo (ou conjunto) de valores, se, o valor de y diminuir a medida que aumentarmos o valor de x.
4.9. Composição de Funções
4.9.1. A composição das funções f e g, indicada por f ∘ g, é definida por: (f ∘ g)(x) = f(g(x)).
4.9.2. f ∘ g ≠ g ∘ f
4.10. Função Injetora
4.10.1. Uma função f: A → B é chamada de injetora se e somente se
4.10.1.1. ∀ a, b ∈ A.
4.10.1.2. f a = f b ⟹ a = b.
4.11. Função Sobrejetora
4.11.1. Uma função f: A → B é chamada de sobrejetora se e somente se
4.11.1.1. ∀ y ∈ B, ∃ x ∈ A | f x = y.
4.12. Função Bijetora
4.12.1. Uma função f: A → B é bijetora se, e somente se, f é injetora e sobrejetora.
4.13. Função Inversa
4.13.1. A função inversa de f é a função que leva a um elemento b ∈ B a um único a ∈ A, tal que f a = b.
5. Estruturas Algébricas
5.1. Seja A um conjunto não vazio e seja ¤ uma operação em A. A estrutura algébrica (A; ¤) é denominada um
5.1.1. Semi-grupo se ¤ é uma operação associativa.
5.1.2. Monóide se ¤ é uma operação associativa e tem um elemento neutro e 2 A.
5.1.3. Grupo se ¤ é associativa, tem um elemento neutro e 2 A, e cada elemento a 2 A é invertível na operação ¤.
5.2. Anéis
5.2.1. Um anel é uma estrutura algébrica (A; +; ¢) satisfazendo às seguintes propriedades
5.2.1.1. A estrutura (A; +) é um grupo abeliano (chamada grupo aditivo do anel A). Isto quer dizer que a operação + em A tem as seguintes propriedades
5.2.1.1.1. Para todo a; b; c 2 A, (a + b) + c = a + (b + c) (a operação + é associativa).
5.2.1.1.2. Para todo a; b pertencente A, a + b = b + a (a operação + é comutativa).
5.2.1.1.3. Existe um elemento 0A pertencente A que é elemento neutro da operação +, ou seja, para todo a pertencente A, a + 0A = 0A + a = a.
5.2.1.1.4. Para cada a pertencente A, existe um elemento (-a) pertencente A, chamado elemento oposto ou inverso aditivo de a, satisfazendo
5.2.1.2. A operação é associativa, ou seja, para todo a, b, c pertencente a A, (a . b) c = a . ¢ (b . c)
5.2.1.3. A operação ¢ é distributiva em relação à operação +, isto é, para todo a; b; c pertencente a A, tem-se
5.2.1.3.1. a . (b + c) = a . b + a . c.
5.2.1.3.2. (a + b) . c = a . c + a . c.
6. Lógica Matemática
6.1. Proposição
6.1.1. É todo conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo.
6.1.2. As proposições podem ser classificadas em verdadeiras ou falsas.
6.1.3. Podem ser classificadas também em simples ou compostas.
6.1.3.1. Chama-se Proposição Simples aquela que não contém nenhuma outra proposição como parte integrante de si mesma.
6.1.3.2. Chama-se Proposição Composta aquela formada por duas ou mais proposições.
6.2. Tabela Verdade
6.2.1. O valor lógico de uma proposição composta é determinado pelos valores lógicos das proposições simples que a constituem e pelo(s) conectivo(s) envolvido(s).
6.2.2. Para determinar o valor lógico utilizamos um instrumento chamado tabela verdade, no qual figuram todos os possíveis valores lógicos das proposições simples que integram a proposição composta.
6.3. Operadores Lógicos
6.3.1. Conjunção (^)
6.3.1.1. Conectivo “e”.
6.3.2. Negação (~) ou (¬)
6.3.2.1. Conectivo "não".
6.3.3. Disjunção (v)
6.3.3.1. Conectivo "ou".
6.3.4. Disjunção Exclusiva (⊻)
6.3.4.1. Conectivo "ou".
6.3.4.1.1. "Não ambos".
6.3.5. Condicional (→)
6.3.5.1. Conectivo "se... então".
6.3.6. Bicondicional (↔)
6.3.6.1. Conectivo "se e somente se".
6.4. Termos Fundamentais
6.4.1. Argumento
6.4.1.1. Um argumento é uma sequência finita de n + 1 proposições H1, H2, ... , Hn, T onde T é considerada consequência das demais.
6.4.1.1.1. As proposições H1, H2, ... , Hn são chamadas de premissas ou HIPÓTESES e T é denominada conclusão ou TESE.
6.4.2. Axiomas (ou postulado)
6.4.2.1. Premissa considerada necessariamente evidente e verdadeira, fundamento de uma demonstração, porém ela mesma indemonstrável.
6.4.3. Prova
6.4.3.1. Argumento válido que confirma a validade de sentenças matemáticas, ou seja, que uma afirmação é verdadeira.
6.4.4. Demonstração
6.4.4.1. É a prova de que um teorema é verdadeiro, o qual foi obtido por regras válidas.
6.4.5. Teorema
6.4.5.1. Proposição que é validada por uma prova, ou seja, que se demonstra ser verdadeira baseada em proposições anteriores.
6.4.6. Lema
6.4.6.1. Proposição provada que é utilizada para provar proposições mais relevantes (teoremas). Trata-se de teorema auxiliar utilizado para provar outros teoremas.
6.4.7. Corolário
6.4.7.1. Quando um teorema ou uma prova nos ajudam a concluir facilmente que outras afirmações são verdadeiras chamamos estas últimas de corolários do teorema.
6.4.8. Conjectura
6.4.8.1. Uma conjectura é uma proposição que ainda não foi provada e nem refutada.
6.5. Implicação Lógica
6.5.1. Uma proposição P implica logicamente uma proposição Q quando nas tabelas verdade não ocorre que P é V e Q é F ou P é F e Q é V.
6.5.2. Indica-se que a proposição P implica logicamente a proposição Q com a notação P ⇒ Q.
6.6. Equivalência Lógica
6.6.1. Uma proposição P é equivalente a uma proposição Q quando P e Q têm tabelas-verdade iguais, isto é, quando P e Q têm sempre o mesmo valor lógico.
6.6.2. Indica-se que a proposição P é equivalente a Q, com a notação P ⇔ Q.
6.7. Propriedade dos Operadores
6.7.1. Leis Comutativas
6.7.1.1. Propriedade I
6.7.1.1.1. p ∧ q ⇔ q ∧ p (conjunção).
6.7.1.2. Propriedade II
6.7.1.2.1. p ∨ q ⇔ q ∨ p (disjunção).
6.7.2. Leis de Idempotência
6.7.2.1. Propriedade III
6.7.2.1.1. p ∧ p ⇔ p (conjunção).
6.7.2.2. Propriedade IV
6.7.2.2.1. p ∨ p ⇔ p (disjunção).
6.7.3. Leis Associativas
6.7.3.1. Propriedade V
6.7.3.1.1. (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) (conjunção).
6.7.3.2. Propriedade VI
6.7.3.2.1. (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (disjunção).
6.7.4. Leis Distributivas
6.7.4.1. Propriedade VII
6.7.4.1.1. A conjunção é distributiva em relação à disjunção p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r).
6.7.4.2. Propriedade VIII
6.7.4.2.1. A disjunção é distributiva em relação à conjunção p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r).
6.7.5. Leis de Morgan
6.7.5.1. Propriedade IX
6.7.5.1.1. ~(p ∧ q) ⇔ ~p ∨ ~q.
6.7.5.2. Propriedade X
6.7.5.2.1. ~(p ∨ q) ⇔ ~p ∧ ~q.
6.8. Sentenças Abertas
6.8.1. Se uma proposição não pode ser classificada com V ou F, ela é chamada de função proposicional ou sentença aberta, a qual é denotada por p(x).
6.9. Conjunto Verdade
6.9.1. Se p(a) é uma função proposicional num conjunto A, então o conjunto dos elementos a ∈ A com a propriedade de que p(a) é verdadeiro é chamado de conjunto verdade Vp de p(x).
6.9.1.1. Ou seja, Vp = x x ∈ A, p x é verdadeiro}.
6.10. Quantificadores
6.10.1. Quantificador Universal
6.10.1.1. O quantificador universal traduz a ideia de abrangência de uma proposição a todo um conjunto.
6.10.1.2. É denotado pelo símbolo ∀ e lido como “para todo” ou “para qualquer” ou para “qualquer que seja”.
6.10.2. Quantificador Existencial
6.10.2.1. O quantificador existencial traduz a ideia de existência de condições para a validade de uma proposição em um conjunto.
6.10.2.2. É denotado pelo símbolo ∃ e lido como “existe” ou “existe pelo menos um” ou “para algum”.
6.10.3. Quantificador de Existência e Unicidade
6.10.3.1. Indica a existência de apenas um elemento capaz de tornar a proposição verdadeira.
6.10.3.2. É denotado pelo símbolo ∃! e tem o significado de “existe apenas um” ou “existe um único”.
6.11. Métodos de Demonstração
6.11.1. Por Exaustão
6.11.1.1. A comprovação é feita mostrar que a afirmação é verdadeira para cada elemento dessa coleção. Esgotando todos os casos possíveis.
6.11.2. Direta
6.11.2.1. Consiste em supor que a hipótese P é verdadeira, partir dessa hipótese e deduzir uma série de argumentos coerentes e válidos que leva até a tese Q.
6.11.3. Por Contraposição
6.11.3.1. Consiste em provar que H ⟹ T é verdadeira através da demonstração direta de ~T ⟹ ~H.
6.11.4. Por Contradição ou Absurdo
6.11.4.1. Esse método consiste em admitir que a tese é falsa e que a hipótese é verdadeira e chegar a uma contradição.
6.11.5. Por Indução
6.11.5.1. Um caso base é provado, e, uma regra de indução é usada para provar uma série de outros casos (efeito dominó).
7. Conjuntos
7.1. Relação Pertence
7.1.1. Considerando um conjunto A qualquer, se x é um elemento desse conjunto, dizemos que “x pertence a A” ou que “x é elemento de A”.
7.1.1.1. x ∈ A.
7.2. Relação Contém
7.2.1. Um conjunto A é subconjunto de um conjunto B se, e somente se, todo elemento de A pertence também a B.
7.2.1.1. A ⊂ B ⟺ ∀x x ∈ A → x ∈ B.
7.3. Relação de Igualdade Entre Conjuntos
7.3.1. Dois conjuntos A e B são iguais se, e somente se, todo elemento de A pertence a B e todo elemento de B pertence a A.
7.3.1.1. A = B.
7.3.2. A igualdade entre conjuntos apresenta as propriedades reflexiva, simétrica e transitiva.
7.3.2.1. Reflexibilidade
7.3.2.1.1. A = A.
7.3.2.2. Simetria
7.3.2.2.1. Se A = B, então B = A.
7.3.2.3. Transitividade
7.3.2.3.1. Se A = B e B = C, então A = C.
7.4. Tipos de Conjuntos
7.4.1. Finitos e Infinitos
7.4.1.1. Um conjunto é finito se consiste de um número específico de elementos diferentes, caso contrário é considerado um conjunto infinito.
7.4.2. Unitário e Vazio
7.4.2.1. Chama-se conjunto unitário aquele que possui um único elemento; Chama-se conjunto vazio aquele que não possui nenhum elemento, é indicado por ∅ ou { }.
7.4.3. Universo
7.4.3.1. É o conjunto de todos os objetos considerados como elementos de um referido assunto.
7.4.4. Conjunto de Partes
7.4.4.1. Dado um conjunto A, chama-se conjunto das partes de A, indicado por P(A), aquele que é formado por todos os subconjuntos de A.
7.5. União de Conjuntos
7.5.1. Dados dois conjuntos A e B, o conjunto de todos os elementos que pertencem a pelo menos um dos dois conjuntos é chamado de união ou reunião de A e B.
7.5.1.1. A ∪ B.
7.6. Interseção de Conjuntos
7.6.1. Dados dois conjuntos A e B, com os elementos que pertencem simultaneamente a ambos os conjuntos formamos o conjunto chamado interseção de A e B.
7.6.1.1. A ∩ B.
7.7. Partições
7.7.1. Uma partição P de um conjunto não-vazio X é uma subdivisão de X em subconjuntos que são disjuntos e cuja união resulta em X.
8. Análise Combinatória
8.1. Análise Combinatória é um conjunto de procedimentos que possibilita a construção de grupos diferentes formados por um número finito de elementos de um conjunto sob certas circunstâncias. Nesses grupos é possível realizar a análise das possibilidades e combinações.
8.2. Fatorial
8.2.1. Considerando n um número natural maior que 1 (um), podemos definir como fatorial desse número n (n!) o número: n! = n(n – 1)(n – 2)(n – 3)x…x3x2x1.
8.3. Princípio Fundamental da Contagem
8.3.1. Quando um evento é composto por n etapas sucessivas e independentes, de tal forma que as possibilidades da primeira etapa é m e as possibilidades da segunda etapa é n, consideramos então que o número total de possibilidades de o evento ocorrer é dado pelo produto m*n.
8.4. Arranjos Simples
8.4.1. Arranjos simples de n elementos tomados p a p (p ≤ n) são os diferentes agrupamentos ordenados que se podem formar com p dos n elementos dados. Indica-se por An,p ou Anp o total desses agrupamentos, que calculamos assim: An,p = n(n – 1)(n – 2) x…x(n – p + 1).
8.5. Permutações Simples
8.5.1. A permutação simples pode ser considerada como um caso particular de arranjo, onde os elementos formarão agrupamentos que se diferenciarão somente pela ordem. As permutações simples dos elementos P, Q e R são: PQR, PRQ, QPR, QRP, RPQ, RQP. Para determinarmos o número de agrupamentos de uma permutação simples utilizamos a seguinte expressão: P = n!. n! = nx(n-1)x(n-2)x(n-3)x…..x3x2x1.