Matemática Discreta

Visualizações: 637
Classificação: (0)

Nova edição do livro Matemática Discreta, da Coleção Schaum. Este livro tem o objetivo de ajudar estudantes a entender e a usar sistemas finitos, que têm se tornado cada vez mais importantes à medida que a era do computador avança. O texto é escrito de forma direta e concisa, contendo exemplos, problemas cuidadosamente resolvidos e exercícios complementares.

FORMATOS DISPONíVEIS

eBook

Disponível no modelo assinatura da Minha Biblioteca

17 capítulos

Formato Comprar item avulso Adicionar à Pasta

Capítulo 1 - Teoria de Conjuntos

PDF Criptografado

Capítulo 1

Teoria de Conjuntos

1.1

INTRODUÇÃO

O conceito de conjunto aparece em toda a matemática. Este capítulo introduz a notação e a terminologia básicas da teoria de conjuntos usadas ao longo deste livro. O capítulo encerra com a definição formal de indução matemática e exemplos.

1.2

CONJUNTOS E ELEMENTOS, SUBCONJUNTOS

Um conjunto pode ser entendido como qualquer coleção bem definida de objetos, conhecidos como os elementos ou membros do conjunto. Geralmente se empregam letras maiúsculas A, B, X, Y,…, para denotar conjuntos, e letras minúsculas, a, b, x, y,…, para denotar elementos de conjuntos.† Sinônimos para “conjunto” são “classe”, “coleção” e “família”.

Pertinência em um conjunto é denotada como segue: a ∈ S denota que a pertence a um conjunto S a, b ∈ S denota que a e b pertencem a um conjunto S

Aqui, ∈ é o símbolo que significa “é um elemento de”. Empregamos �∈ para dizer “não é um elemento de”.

Especificando conjuntos

 

Capítulo 2 - Relações

PDF Criptografado

Capítulo 2

Relações

2.1

INTRODUÇÃO

O leitor está familizarizado com muitas relações, como “menor que”, “é paralela a”, “é um subconjunto de” e assim por diante. Em certo sentido, essas relações consideram a existência ou inexistência de uma certa conexão entre pares de objetos assumidos em uma determinada ordem. Formalmente, definimos uma relação em termos desses

“pares ordenados”.

Um par ordenado de elementos a e b, onde a é designado como o primeiro elemento e b é o segundo elemento,

é denotado por (a, b). Em particular,

(a, b) = (c, d) se, e somente se, a = c e b = d. Portanto (a, b) �= (b, a), a menos que a = b. Isso contrasta com conjuntos nos quais a ordem de elementos é irrelevante; por exemplo, {3, 5} = {5, 3}.†

2.2

PRODUTO CARTESIANO

Considere dois conjuntos quaisquer A e B. O conjunto de todos os pares ordenados (a, b), onde a ∈ A e b ∈ B, é chamado de produto ou produto cartesiano de A por B. Uma abreviação desse produto é A × B, que se lê “A cartesiano B”. Por definição,

 

Capítulo 3 - Funções e Algoritmos

PDF Criptografado

Capítulo 3

Funções e Algoritmos

3.1

INTRODUÇÃO

Um dos conceitos mais importantes em matemática é o de função. Os termos “mapa”, “mapeamento”, “transformação” e muitos outros significam a mesma coisa; a escolha sobre qual terminologia empregar em uma dada situação geralmente é determinada pela tradição e pela formação matemática de quem usa o termo.

O conceito de algoritmo está relacionado com a noção de função. A notação para a apresentação de um algoritmo e uma discussão sobre sua complexidade também são abordadas neste capítulo.

3.2

FUNÇÕES

Suponha que a cada elemento de um conjunto A assinalamos um único elemento de um conjunto B; a coleção de tais correspondências é chamada de função de A em B. O conjunto A é denominado domínio da função e o conjunto B é chamado de conjunto alvo ou codomínio.

Funções são comumente denotadas por símbolos. Por exemplo, seja f uma função de A em B. Então escrevemos f:A→B que se lê: “f é uma função de A em B”, ou “f leva (ou mapeia) A em B”. Se a ∈ A, então f (a) (lê-se: “f de a”) denota o único elemento de B que f associa a a; ele é chamado de imagem de a sob f, ou o valor de f em a. O conjunto de todas as imagens é conhecido como a imagem de f. A imagem de f : A → B é denotada por Im(f) ou f(A).

 

Capítulo 4 - Lógica e Cálculo Proposicional

PDF Criptografado

Capítulo 4

Lógica e Cálculo Proposicional

4.1

INTRODUÇÃO

Muitos algoritmos e demonstrações usam expressões lógicas como:

“SE p ENTÃO q” ou “SE p1 e p2, ENTÃO q1 OU q2”

Logo, é necessário conhecer os casos nos quais essas expressões são VERDADEIRAS ou FALSAS, ou seja, saber o “valor verdade” de tais expressões. Discutimos essas questões neste capítulo.†

Também investigamos o valor verdade de afirmações quantificadas, as quais são expressões que empregam os quantificadores lógicos “para todo” e “existe”.‡

4.2

PROPOSIÇÕES E SENTENÇAS COMPOSTAS

Uma proposição (ou sentença) é uma afirmação declarativa que é verdadeira ou falsa, mas não ambas. Considere, por exemplo, os seis itens a seguir:

(i) Gelo flutua na água.

(ii) A China é na Europa.

(iii) 2 + 2 = 4

(iv) 2 + 2 = 5

(v) Aonde você está indo?

(vi) Faça seu tema de casa.

Os quatro primeiros são proposições. Os dois últimos não. Além disso, (i) e (iii) são verdadeiras, mas (ii) e (iv) são falsas.

 

Capítulo 5 - Técnicas de Contagem

PDF Criptografado

Capítulo 5

Técnicas de Contagem

5.1

INTRODUÇÃO

Este capítulo desenvolve algumas técnicas para determinar, sem enumeração direta, o número de resultados possíveis de um evento em particular ou o número de elementos de um conjunto. Tal contagem sofisticada é, às vezes, chamada de análise combinatória. Ela inclui o estudo de permutações e combinações.

5.2

PRINCÍPIOS BÁSICOS DE CONTAGEM

Há dois princípios básicos de contagem usados ao longo deste capítulo. O primeiro envolve adição e, o segundo, multiplicação.

Princípio da Regra da Soma:

Suponha que algum evento E possa ocorrer de m maneiras e um segundo evento F possa ocorrer de n maneiras. Suponha também que ambos os eventos não podem acontecer simultaneamente. Então E ou F podem ocorrer de m + n maneiras.

Princípio da Regra do Produto:

Suponha que existe um evento E que possa ocorrer de m maneiras e, independente deste, há um segundo evento F que pode ocorrer de n maneiras. Então, combinações de E e F podem ocorrer de mn maneiras.

 

Capítulo 6 - Técnicas Avançadas de Contagem, Recursão

PDF Criptografado

Capítulo 6

Técnicas Avançadas de

Contagem, Recursão

6.1

INTRODUÇÃO

Consideramos aqui técnicas de contagem e problemas mais sofisticados. Isso inclui problemas envolvendo combinações com repetições, partições ordenadas e não ordenadas, e os princípios de Inclusão-Exclusão e da Casa dos

Pombos.

Também discutimos recursão neste capítulo.

6.2

COMBINAÇÕES COM REPETIÇÕES

Considere o seguinte problema. Uma confeitaria faz apenas M = 4 tipos de biscoitos: maçã (a), banana (b), cenoura (c) e tâmaras (d). Encontre o número de maneiras que uma pessoa pode comprar r = 8 biscoitos.

Observe que a ordem não é relevante. Esse é um exemplo de combinações com repetições. Em particular, cada combinação pode ser listada com os a’s primeiro, seguidos dos b’s, dos c’s e, finalmente, dos d’s. Quatro dessas combinações seguem: r1 = aa, bb, cc, dd; r2 = aaa, c, ddd; r3 = bbbb, c, ddd; r4 = aaaaa, ddd.

Contar o número m de tais combinações pode não ser fácil.

 

Capítulo 7 - Probabilidade

PDF Criptografado

Capítulo 7

Probabilidade

7.1

INTRODUÇÃO

Teoria de probabilidade é um modelo matemático dos fenômenos de acaso ou aleatoriedade. Se uma moeda é jogada de uma maneira aleatória, pode resultar em cara ou coroa, mas não sabemos qual dessas possibilidades ocorrerá em uma única jogada. Contudo, suponha que consideremos s o número de vezes que aparecem caras quando a moeda é jogada n vezes. À medida que n aumenta, a razão f = s/n, chamada de frequência relativa do resultado, se torna mais estável. Se a moeda é não viciada, então esperamos que ela resulte em cara aproximadamente 50% das vezes ou, em outras palavras, a frequência relativa se aproxima de . Além disso, assumindo que a moeda tem massa perfeitamente distribuída, podemos obter o valor por meios dedutivos. Isto é, qualquer lado da moeda é tão provável de ocorrer quanto o outro; logo, as chances de obter cara é de uma em duas, o que significa que a probabilidade de obter cara é . Apesar de o resultado específico de qualquer jogada ser desconhecido, o comportamento ao longo de muitas jogadas é determinado. Esse comportamento estável de longo termo de fenômenos aleatórios forma a base da teoria de probabilidades.

 

Capítulo 8 - Teoria dos Grafos

PDF Criptografado

Capítulo 8

Teoria dos Grafos

8.1

INTRODUÇÃO, ESTRUTURAS DE DADOS

Grafos, grafos orientados, árvores e árvores binárias aparecem em muitas áeras da matemática e da ciência da computação. Este e os próximos dois capítulos cobrem tais tópicos. Contudo, para entender como esses objetos podem ser armazenados em memória e para compreender algoritmos sobre eles, precisamos conhecer um pouco sobre certas estruturas de dados. Assumimos que o leitor compreenda arrays lineares e bidimensionais;† logo, discutimos a seguir apenas listas ligadas e apontadores (ou ponteiros), bem como pilhas e filas.

Listas ligadas e apontadores

Listas ligadas e apontadores são introduzidos por meio de um exemplo. Suponha que uma empresa de corretores mantenha um arquivo no qual cada registro contém um nome de cliente e vendedor; digamos que o arquivo contenha os seguintes dados:

Cliente

Adams

Brown

Clark

Drew

Evans

Farmer

Geller

 

Capítulo 9 - Grafos Orientados

PDF Criptografado

Capítulo 9

Grafos Orientados

9.1

INTRODUÇÃO

Grafos orientados são grafos nos quais as arestas são em um sentido. Tais grafos são frequentemente mais úteis em vários sistemas dinâmicos, como computadores e sistemas de fluxo. Contudo, essa característica extra torna mais difícil determinar certas propriedades sobre o grafo. Isto é, processar esses grafos pode ser semelhante a viajar em uma cidade por muitas ruas de sentido único.

Este capítulo nos dá as definições básicas e propriedades de grafos orientados. Muitas das definições são semelhantes àquelas do capítulo anterior sobre grafos (não orientados). Contudo, por motivos pedagógicos, este capítulo é, em grande parte, independente do anterior.

9.2

GRAFOS ORIENTADOS

Um grafo orientado G ou digrafo (ou, simplesmente, grafo) consiste em duas coisas:

(i) Um conjunto V cujos elementos são chamados de vértices, nós ou pontos.

(ii) Um conjunto E de pares ordenados (u, v) de vértices chamados de arcos ou arestas orientadas ou, simplesmente, arestas.

 

Capítulo 10 - Árvores Binárias

PDF Criptografado

Capítulo 10

Árvores Binárias

10.1

INTRODUÇÃO

A árvore binária é uma estrutura fundamental em matemática e ciência da computação. Parte da terminologia de

árvores enraizadas, como aresta, caminho, ramo, folha, profundidade e número de nível, é também empregada para

árvores binárias. Contudo, usamos o termo nó, no lugar de vértice, para árvores binárias. Enfatizamos que uma

árvore binária não é um caso especial de árvore enraizada; trata-se de objetos matemáticos distintos.

10.2

ÁRVORES BINÁRIAS

Uma árvore binária T é definida como um conjunto finito de elementos, chamados de nós, tal que:

(1) T é vazio (chamado de árvore nula ou árvore vazia), ou

(2) T contém um nó notável R, chamado de raiz de T, e os demais nós de T formam um par ordenado de árvores binárias disjuntas T1 e T2.

Se T contém uma raiz R, então as duas árvores T1 e T2 são chamadas, respectivamente, de subárvores de R à esquerda e à direita. Se T1 for não vazia, então sua raiz é chamada de sucessor à esquerda de R; analogamente, se T2 é não vazio, então sua raiz é chamada de sucessor à direita de R.

 

Capítulo 11 - Propriedades dos Inteiros

PDF Criptografado

Capítulo 11

Propriedades dos Inteiros

11.1

INTRODUÇÃO

Este capítulo investiga algumas propriedades básicas dos números naturais (ou inteiros positivos), ou seja, o conjunto

N = {1, 2, 3, . . .} bem como seus “primos”, os inteiros, isto é, o conjunto

Z = {. . . ,−2, −1, 0, 1, 2, . . .}

(A letra Z vem da palavra “Zahlen” que significa “números” em alemão.)

As seguintes regras simples relativas à adição e multiplicação desses números são assumidas (onde a, b e c são inteiros arbitrários):

(a) Lei associativa para multiplicação e adição:

(a + b) + c = a + (b + c) e (ab)c = a(bc)

(b) Lei comutativa para multiplicação e adição: a + b = b + a e ab = ba

(c) Lei distributiva: a(b + c) = ab + ac

(d) Identidade da adição 0 e identidade da multiplicação 1: a+0=0+a=aea·1=1·a=a

(e) Inverso aditivo −a para qualquer inteiro a: a + (−a) = (−a) + a = 0

O Apêndice B mostra que outras estruturas matemáticas têm as propriedades acima. Uma propriedade fundamental que diferencia os inteiros Z de outras estruturas é o Princípio de Indução Matemática (Seção 1.8), o qual novamente discutimos aqui. Também estabelecemos e provamos (Problema 11.30) o seguinte teorema.

 

Capítulo 12 - Linguagens, Autômatos, Gramáticas

PDF Criptografado

Capítulo 12

Linguagens, Autômatos, Gramáticas

12.1

INTRODUÇÃO

Este capítulo discute três tópicos: linguagens, autômatos e gramáticas. Tais tópicos estão intimamente relacionados entre si. Nossas linguagens serão as letras a, b, … para codificar dados, em vez dos dígitos 0 e 1, usados por outros textos.

12.2

ALFABETO, PALAVRAS E SEMIGRUPO LIVRE

Considere um conjunto A de símbolos não vazio. Uma palavra ou string no conjunto A é uma sequência finita de seus elementos. Por exemplo, suponha que A = {a, b, c}. Então, as sequências a seguir são palavras em A: u = ababb e v = accbaaa

Quando discutimos sobre palavras em A, frequentemente chamamos A de alfabeto, e seus elementos, de letras.

Também abreviamos nossa notação ao escrever a2 quando aa, a3 quando aaa, e assim por diante. Portanto, para as palavras acima, u = abab2 e v = ac2ba3.

A sequência vazia de letras, denotada por λ (a letra grega lâmbda), ou � (a letra grega épsilon), ou 1, é considerada, também, como sendo uma palavra em A, chamada de palavra vazia. O conjunto de todas as palavras em A é denotado por A∗ (lê-se: “A estrela”).

 

Capítulo 13 - Máquinas de Estado Finito e Máquinas de Turing

PDF Criptografado

Capítulo 13

Máquinas de Estado Finito e Máquinas de Turing

13.1

INTRODUÇÃO

Este capítulo discute dois tipos de “máquinas”. O primeiro é uma máquina de estado finito (FSM, finite state machine) que é semelhante a um autômato de estado finito (FSA, finite state automaton), exceto que a máquina de estado finito “imprime” uma saída usando um alfabeto que pode ser distinto daquele empregado na entrada. O segundo tipo

é a célebre máquina de Turing, a qual pode ser empregada para definir funções computáveis.

13.2

MÁQUINAS DE ESTADO FINITO

Uma máquina de estado finito (ou máquina sequencial completa) M consiste em seis componentes:

(1) Um conjunto finito A de símbolos de entrada.

(2) Um conjunto finito S de estados “internos”.

(3) Um conjunto finito Z de símbolos de saída.

(4) Um estado inicial s0 de S.

(5) Uma função de próximo-estado f de S × A em S.

(6) Uma função de saída g de S × A em Z.

Tal máquina M é denotada por M = M(A, S, Z, s0, f, g), quando queremos indicar suas seis componentes.

 

Capítulo 14 - Conjuntos Ordenados e Reticulados

PDF Criptografado

Capítulo 14

Conjuntos Ordenados e Reticulados

14.1

INTRODUÇÃO

Relações de ordem e de precedência aparecem em vários lugares diferentes na matemática e na ciência da computação. Este capítulo torna essas noções precisas. Definimos, também, um reticulado, que é um tipo especial de conjunto ordenado.

14.2

CONJUNTOS ORDENADOS

Suponha que R é uma relação em um conjunto S que satisfaz estas três propriedades:

[O1]

[O2]

[O3]

(Reflexiva) Para qualquer a ∈ S, temos aRa.

(Antissimétrica) Se Rb e bRa, então a = b.

(Transitiva) Se Rb e bRc, então aRc.

Então R é chamada de ordem parcial ou, simplesmente, de uma relação de ordem, e R tida como a relação que define uma ordenação parcial de S. O conjunto S com a ordem parcial é chamado de conjunto parcialmente odenado ou, simplesmente, um conjunto ordenado ou poset (abreviação em inglês para partially ordered set). Escrevemos

(S, R) quando queremos especificar a relação R.

 

Capítulo 15 - Álgebra Booleana

PDF Criptografado

Capítulo 15

Álgebra Booleana

15.1

INTRODUÇÃO

Tanto conjuntos quanto proposições satisfazem leis similares, que são listadas nas Tabelas 1-1 e 4-1 (nos Capítulos

1 e 4, respectivamente). Essas leis são usadas para definir uma estrutura matemática abstrata chamada de álgebra

Booleana, batizada em homenagem ao matemático George Boole (1815-1864).

15.2

DEFINIÇÕES BÁSICAS

Seja B um conjunto não vazio com duas operações binárias, + e ∗, uma operação unária¿ e dois elementos distintos,

0 e 1. Então B é chamado de álgebra Booleana se os axiomas a seguir forem válidos, onde a, b e c são quaisquer elementos em B:

[B1]

Leis Comutativas:

(1a) a + b = b + a

[B2] Leis Distributivas:

(2a) a + (b ∗ c) = (a + b) ∗ (a + c)

[B3] Leis de Identidade:

(3a) a + 0 = a

[B4] Leis de Complemento:

(4a) a + a¿ = 1

(1b)

a∗b=b∗a

(2b)

a ∗ (b + c) = (a ∗ b) + (a ∗ c)

(3b)

 

Apêndice A - Vetores e Matrizes

PDF Criptografado

Apêndice A

Vetores e Matrizes

A.1

INTRODUÇÃO

Dados são frequentemente distribuídos em arrays, isto é, conjuntos cujos elementos são indexados por um ou mais

índices. Se esses dados consistem em números, então um array unidimensional é chamado de vetor, enquanto um array bidimensional é chamado de matriz (de forma que a dimensão denota o número de índices.) Este apêndice investiga esses vetores e matrizes e certas operações algébricas nas quais eles se envolvem. Nesse contexto, os números em si são chamados de escalares.

A.2 VETORES

Por vetor u, nós nos referimos a uma lista de números, como a1, a2, . . . , an. Tal vetor é denotado por u = (a1, a2, . . . , an)

Os números ai são chamados de componentes ou entradas de u. Se todos os ai = 0, então u é chamado de vetor nulo. Dois desses vetores, u e v, são iguais, e escrevemos u = v, se possuem o mesmo número de componentes e esses componentes correspondentes são iguais.

Exemplo A.1

 

Apêndice B - Sistemas Algébricos

PDF Criptografado

Apêndice B

Sistemas Algébricos

B.1

INTRODUÇÃO

Este apêndice investiga alguns dos mais importantes sistemas algébricos na matemática: semigrupos, grupos, anéis e corpos. Definimos também as noções de homomorfismo e de estrutura quociente. Começamos com a definição formal de uma operação e discutimos vários tipos de operações.

B.2

OPERAÇÕES

O leitor está familiarizado com as operações de adição e multiplicação de números, união e interseção de conjuntos, e a composição de funções. Essas operações são denotadas como se segue: a + b = c,

a · b = c,

A ∪ B = C, A ∩ B = C,

g o f = h.

Em cada situação, um elemento (c, C ou h) é associado a um par original de elementos. Desenvolvemos maior precisão a essa noção.

Definição B.1: Seja S um conjunto não vazio. Uma operação em S é uma função ∗ de S × S em S. Em tal caso, em

vez de ∗ (a, b), escrevemos normalmente

a ∗ b ou, às vezes, ab

O conjunto S e uma operação ∗ em S é denotada por (S, ∗), ou apenas S, quando a operação é entendida.

 

Detalhes do Produto

Livro Impresso
Book
Capítulos

Formato
PDF
Criptografado
Sim
SKU
BPP0000266367
ISBN
9788565837781
Tamanho do arquivo
19 MB
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
Formato
PDF
Criptografado
Sim
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
SKU
Em metadados
ISBN
Em metadados
Tamanho do arquivo
Em metadados