Vol -1.pdf

  • Published on
    11-Dec-2015

  • View
    23

  • Download
    2

Embed Size (px)

Transcript

  • Recife, 2009

    Matemtica Discreta

    Francisco Flvio Modesto de Andrade

  • Universidade Federal Rural de Pernambuco

    Reitor: Prof. Valmar Corra de AndradeVice-Reitor: Prof. Reginaldo BarrosPr-Reitor de Administrao: Prof. Francisco Fernando Ramos CarvalhoPr-Reitor de Extenso: Prof. Paulo Donizeti SiepierskiPr-Reitor de Pesquisa e Ps-Graduao: Prof. Fernando Jos FreirePr-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo FerreiraPr-Reitora de Ensino de Graduao: Prof. Maria Jos de SenaCoordenao Geral de Ensino a Distncia: Prof Marizete Silva Santos

    Produo Grfica e EditorialCapa e Editorao: Allyson Vila Nova, Rafael Lira e Italo AmorimReviso Ortogrfica: Marcelo MeloIlustraes: Allyson Vila NovaCoordenao de Produo: Marizete Silva Santos

  • Sumrio

    Apresentao ........................................................................................5

    Captulo 1 - Conjuntos: uma breve reviso ........................................6

    1.1 Definies .....................................................................................6

    Captulo 2 - lgebra de Conjuntos: como operar com conjuntos? 15

    2.1 Operaes entre conjuntos .........................................................15

    2.2 Partio de um conjunto .............................................................23

    2.3 Cardinal da unio e da interseo ..............................................25

    2.4 Produto Cartesiano .....................................................................31

    2.5 Produto Cartesiano de k conjuntos .............................................33

    2.6 Identidades de conjuntos ............................................................34

    Captulo 3 - Introduo Lgica Matemtica ...................................40

    3.1 Proposies compostas ..............................................................41

    3.2 Tautologias e Contradies ........................................................47

    3.3 Negao de conjuno e de disjuno .......................................50

    3.4 lgebra das proposies ............................................................50

    3.5 Funes proposicionais. Quantificadores. ..................................55

    3.5.1 Quantificadores ...................................................................55

    3.5.2 Negao de sentenas quantificadas .................................56

  • Captulo 4 - Portas Lgicas ................................................................62

    4.1 Porta Not (No) ...........................................................................62

    4.2 Porta Or (Ou) ..............................................................................63

    4.3 Porta And (E) ..............................................................................63

    4.4 Porta Nand e Porta Nor ..............................................................64

    4.5 Portas XOR e XNOR ..................................................................65

    4.6 Portas Lgicas Equivalentes ......................................................65

    4.7 Propriedades das Portas Lgicas ...............................................66

  • Apresentao

    Caro (a) cursista,

    A importncia da Matemtica Discreta nos Cursos de Computao e Informtica destacada nas Diretrizes Curriculares do MEC ao se afirmar que A Matemtica, para a rea de computao, deve ser vista como uma ferramenta a ser usada na definio formal de conceitos computacionais (linguagens, autmatos, mtodos, etc). E ainda: Considerando que a maioria dos conceitos computacionais pertence ao domnio discreto, a Matemtica Discreta fortemente empregada.

    A Matemtica Discreta d nfase aos temas matemticos tomando por base os conjuntos contveis, finitos ou infinitos. A Matemtica do Continuum, ao contrrio da Matemtica Discreta, enfatiza os temas matemticos baseados em conjuntos no- contveis, como o conjunto dos nmeros reais, em disciplinas como o Clculo Diferencial e Integral.

    Iremos abordar contedos selecionados da Matemtica Discreta que realizam interface com os cursos das reas relacionadas informtica. Para tanto, o material ser apresentado em fascculos que trataro de maneira sistemtica os seguintes assuntos: Conjuntos, Operaes com conjuntos, Introduo Lgica Matemtica, Portas lgicas, Somas, Matrizes, Princpios de Contagem, Relaes, Funes, Recurso, Tcnicas de Provas e Princpio de Induo Finita.

  • 6Matemtica Discreta

    Captulo 1 - Conjuntos: uma breve reviso

    A ideia de conjuntos largamente utilizada em Computao e Informtica, tendo em vista que, praticamente todos os conceitos dessas reas, bem como os resultados correspondentes, so baseados em conjuntos ou as construes sobre conjuntos. Por isso, que tal fazermos uma reviso dos principais elementos da teoria dos conjuntos?

    1.1 Definies

    Conjuntos so geralmente designados por letras maisculas e reservam-se as letras minsculas para representar os seus elementos. A expresso xA significa que x elemento do conjunto A. Se x no elemento do conjunto A, escrevemos xA.

    Vrias maneiras podem ser usadas para descrever um conjunto. Entre elas, destacamos as seguintes:

    Listando seus elementos, isto , nomeando explicitamente todos os seus elementos, colocando-os entre chaves e separados por vrgula.

    Exemplo: A = { a, e, i, o, u }, B = { a, b, c, d }.

    Definindo uma propriedade de seus elementos. Em geral escrevemos { x : P(x) }, isto , o conjunto dos x tal que x tem a propriedade P.

    Exemplo: A = { x : x uma letra vogal do alfabeto portugus }, B = { x : x uma das quatro primeiras letras minsculas do alfabeto portugus }.

    Por meio de um Diagrama de Venn (1834-1923): O conjunto constitudo por todos os elementos sob considerao numa

  • 7Matemtica Discreta

    determinada situao denominado conjunto universo U e ser, em geral, representado por um retngulo. Dentro do retngulo, crculos (ou outras figuras geomtricas) representam conjuntos. Dentro dos crculos so colocados os elementos desses conjuntos.

    Por exemplo: Considere o conjunto universo U = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } e os conjuntos A = { 1, 2, 3, 4, 5, 9 } e B = { 2, 4, 6, 7, 8 }

    A ideia de conjunto universo U estar sempre presente mesmo quando no seja explicitamente mencionado num determinado problema ou situao. Em Matemtica, h conjuntos que constituem muito frequentemente os universos do discurso, sendo conveniente indicar nomes para eles. Entre os mais importantes, destacaremos:

    N = { 0, 1, 2, 3, 4, 5, ... } o conjunto dos nmeros naturais. (Perceba que 0 N)

    N*= { 1, 2, 3, 4, 5, ... } o conjunto dos nmeros naturais positivos.

    Z = { x : x um nmero inteiro } = { ..., -3, -2, -1, 0 , 1 , 2, 3, ... }

    Q = { x : x um nmero racional } o conjunto de todos os nmeros que podem ser escritos sob a forma de frao.

    R = { x : x um nmero real }

    I = { x : x um nmero irracional } o conjunto dos nmeros reais no racionais, isto , no podem ser escritos sob a forma de frao.

    Conjunto vazio o conjunto sem elementos, pode ser representado pelos smbolos ou { }

    Exemplo: A = { x N : 1 < x < 2 } um conjunto vazio, pois no existe nmero natural entre 1 e 2.

    Exemplo: B = { x Z : x2 = 3 } tambm um conjunto vazio. Voc sabe por qu? Existe nmero inteiro cujo quadrado seja igual a 3?

  • 8Matemtica Discreta

    Conjuntos iguais. Dois conjuntos so iguais se, e somente se, contm os mesmos elementos. Por exemplo: Os conjuntos A = { x Z : x2 = 4 } e B = { -2, 2 } so iguais.

    Subconjunto. Um conjunto A subconjunto do conjunto B se todo elemento do conjunto A tambm elemento de B. Usamos a notao A B para denotar que A subconjunto de B e lemos A est contido em B.

    Por exemplo: A = { 1, 2 } subconjunto de B = { 1, 2, 3 } mas no subconjunto de C = { 1, 3, 4 }.

    Agora, vamos lembrar algumas concluses relacionadas a subconjunto.

    Observao 1. De acordo com a definio de subconjunto, o conjunto vazio subconjunto de qualquer conjunto A, isto , A. Isso parece estranho a voc? Mas, existe algum elemento no conjunto que no esteja no conjunto A? A sua resposta foi no! Logo, o conjunto vazio subconjunto do conjunto A.

    Tambm dizemos que A A, qualquer que seja o conjunto A. Isso verdade, pois todo elemento de A, elemento de A.

    Observao 2. Se A B e A subconjunto de B, escrevemos A B para dizer que A subconjunto prprio de B. Por exemplo, { 1, 2, 3 } subconjunto prprio de { 1, 2, 3, 4, 5 }.

    Temos tambm que N Z, Z Q, Q R. Veja a figura a seguir.

  • 9Matemtica Discreta

    Observao 3. Se A B e B C ento A C.

    Exemplo: { 1, b } { 1, 2, b, c } { 1, 2, 3, a, b, c }.

    Exemplo: A figura da observao 2 mostra que N Z e Z R ento N R.

    Observao 4. Para provarmos que A B teremos que provar que, dado x A ento x B.

    Cardinal. Se A um conjunto com exatamente n elementos, tal que n um inteiro no negativo, dizemos que A um conjunto finito e que o cardinal de A n. Assim o cardinal de um conjunto A, denotado por #A o nmero de elementos do conjunto A. Desse modo, se A = { x Z : 3 x 7 } ento #A = 5. claro que # = 0.

    Observe que um conjunto A finito se podemos estabelecer uma correspondncia entre seus elementos e os elementos de um conjunto da forma { 1, 2, 3, ..., n } onde n o cardinal de A. Por exemplo, A = { a, b, c, d, e } finito pois podemos estabelecer a seguinte correspondncia entre seus elementos e os elementos do conjunto { 1, 2, 3, 4, 5 }:

    a 1, b 2, c 3, d 4, e 5. Voc ento conclui que o cardinal do conjunto A 5.

    Conjunto infinito. Um conjunto A infinito se no finito. Por exemplo, os conjuntos N, Z, Q e R so conjuntos infinitos. Voc concorda com a afirmao de que o conjunto A = { xR : 0 &lt