Apostila Matematica Discreta - Prof. Andressa Assaka, Notas de estudo de Matemática

Baixe Apostila Matematica Discreta - Prof. Andressa Assaka e outras Notas de estudo em PDF para Matemática, somente na Docsity! me FACET FACULDADES MATEMÁTICA DISCRETA SISTEMAS DE INFORMAÇÃO 1º PERÍODO FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI MATEMÁTICA DISCRETA Carga Horária: 72 horas/aula Avaliações Cada nota bimestral será baseada na média das notas obtidas nos trabalhos (peso 3,0) e da nota da prova bimestral (peso 7,0), isto é: NB = 3 trabalhos + NP Datas das Avaliações 20/04 — Prova Bimestral (em horário de aula) 22/06 — Prova Bimestral (em horário de aula) 04/07 — Prova Final (horário extraordinário, turma unificada, verificar ensalamento) Observações Importantes e O curso é presencial, isto é, a presença em 75% das aulas é obrigatória (Obs.: legalmente, não são justificadas faltas por motivo de trabalho); e Deixe seu celular mudo, por educação. Não é permitido o uso de celular em noite de prova; e A utilização de laptops, notebooks, netbooks, smartphones, tablets, etc. será permitida somente nas aulas que requerem uso de planilhas eletrônicas; e Material requerido para as aulas: calculadora científica (qualquer marca e modelo); e Não serão aceitos trabalhos enviados por email; e Trabalhos entregues fora do prazo valerão nota inversamente proporcional ao tempo de entrega (quanto mais tempo demorar, menor a nota máxima do trabalho), e Alunos que atingirem média semestral igual ou superior a 7,0 são aprovados por média; e Alunos que atingirem média semestral inferior a 7,0 e igual ou superior a 4,0 farão avaliação final (valor 10,0 — conteúdo de todo o semestre, sem consulta); e Alunos com média semestral abaixo de 4,0 devem refazer a disciplina no próximo semestre. Em caso de dúvidas relativas à confecção dos trabalhos, perguntas podem ser enviadas por email: Andressa. Assaka(D gmail.com ou podem ser feitas pessoalmente nas instalações da FACET de terça a sexta, das 18:30 às 18:55, ou no intervalo das aulas. Curitiba, fev 2011. PROBABILIDADE & ESTATÍSTICA 1 — PROFA. ANDRESSA ASSAKA 1 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES 4.4.1 ARGUMENTO VÁLIDO ..... 4.4.2 ARGUMENTO INVÁLIDO...... 4.4.3 CONSTRUÇÃO DO SILOGISMO 4.44 As REGRAS DO SILOGISMO..... 4.5 ARGUMENTAÇÃO E TABELAS-VERDAD) 5 Crcurros Lócicos, 5.1 SITUAÇÕES PRÁTICAS... CAPÍTULO 3-TEORIA DOS GRAFOS, 1 INTRODUÇÃO. 1.1 As SETE PONTES DEK ÓNIGSBERG....... 1.2 O PROBLEMA DA COLORAÇÃO DE MAPAS 2 ELEMENTOS DOS GRAFOS. 2.1 VERTICES E ARESTAS 2.2 ORDEM DE UM GRAFO 2.3 ISOMORFISMOS.... 2.4 GRAU DE UM VÉRTICE... 24.1 OLEMA DOS APERTOS DEMÃO! 24 CAMINHOS... 3 CONEXIDADEDEGRAFOS, 4 CRRCUITOSE CiRcurTOS EULERIANOS 4.1 O TEOREMA DE EULER...... 4.2 PROVA DO TEOREMA DE EULER...... 5 Graros EULERIANOS 6 Graros HAMLTONANOS, 6.1 O PROBLEMA DO CAIXEIRO VIAJANTE. ..... 7 Crios 7.1 CICLOS HAMILTONIANO! 7.2 CONDIÇÃO SUFICIENTEPARA A EXISTÊNCIA DE UM CICLO HAMILTONIANO.. 7.3 O PRINCÍPIO DAS GAVETAS ..... 8 ÁrvoREs 8.1 SUBGRAFOS...... 8.2 CRITÉRIOS PARA DETERMINAR SE UM GRAFO É UMA ÁRVORE. 8.3 RAÍZES E ÁRVORES BINÁRIAS...... 8.4 ÁRVORES E EXPRESSÕES ALGÉBRICAS. 9 Graros PLANARES BEBLIOGRARA .75 MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 2 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES Capítulo 1 — Teorias dos Conjuntos 1 CoNJuNTOS, ELEMENTOS E CONCEITOS O conceito de conjunto é fundamental, pois, praticamente, todos os conceitos desenvolvidos em Computação e Informática, bem como seus resultados, são baseados em conjuntos ou construções sobre conjuntos. Um conjunto é uma coleção, sem repetições e sem ordenação, de nenhum ou diversos objetos denominados elementos. Frequentemente, os conjuntos são simbolizados por letras maiúsculas: A, B, X, Y, M,... e os elementos são representados por letras minúsculas: a, b, x, y, 1... Exemplos: a) as vogais b) os dígitos c) os números pares Go AL] q Cria SS, e) os dias da semana Observando os exemplos, deve ficar claro que um conjunto não precisa ser constituído de elementos que compartilhem as mesmas características ou propriedades. Um conjunto que lista todos os seus elementos, em qualquer ordem, separados por vírgulas e entre chaves, é denominado denotação por extensão: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 3 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI A definição de um conjunto por propriedades é denominada denotação por compreensão: Que pode ser interpretada como sendo: o conjunto de todos os elementos n, tal que n é um mimero par. Assim, a forma geral de definição de um conjunto por propriedades fica: E é tal que um determinado elemento a é elemento desse conjunto se a propriedade for verdadeira para a, ou seja, para o conjunto: Tem-se que Pelé é elemento do conjunto B e Bill Gates não é elemento de B. Embora seja possível definir qualquer conjunto por compreensão, é conveniente especificar conjuntos de outra forma: 1.1 PERTINÊNCIA Se um determinado elemento a é elemento de um conjunto A, então: Caso contrário, afirma-se que a não pertence ao conjunto A: Exemplo: Relativamente ao conjunto de vogais, V, tem-se que: a V h v Relativamente ao conjunto B, composto por brasileiros: Pelé B Bill Gates B MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 4 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 1.5 SUBCONJUNTOS E IGUALDADE DE CONJUNTOS Além da noção de pertinência, outra noção importante é a de continência, que permite introduzir os conceitos de subconjunto e de igualdade dos conjuntos. Se todos os elementos de um conjunto A também são elementos do conjunto B, então se pode afirmar que A está contido em B: Ou, altemativamente, que B contém A: Nesse caso, ACB ou BD A, afirma-se que A é subconjunto de B. Adicionalmente, se AC B, mas existe bEB tal que bg A, então se afirma que A está contido propriamente em B, ou que A é subconjunto próprio de B: Exemplo: a) db) e) d) e) 9 Um conjunto especial e importante é o conjunto universo, denotado por U, que contém todos os conjuntos que estão em consideração. Ou seja, o conjunto universo define o “contexto da discussão” (entenda que U não é um conjunto fixo). Uma vez definido o conjunto universo U, para qualquer conjunto A: Os conjuntos A e B são ditos iguais se, e somente se, possuírem os mesmo elementos. Formalmente: Exemplo: a) db) e) MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 7 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Teorema: (1) Para todo conjunto A, tem-se 2C ACU (ii) Para todo conjunto A, AC A (ii)Se AcBeBcC,enão ACC (iv) A=B,seesomentese ACBeBCA Esse último item ilustra claramente a definição de igualdade. Verifique que a repetição dos elementos pode ser desconsiderada. É importante distinguir claramente os conceitos de pertinência e continência. Exemplo: Considere o conjunto A = [1,2,3,0, fa), (b,c)) ati) af a Vo AD A c) fa) A, fb,cy A DLL AÍ. A 1.6 DIAGRAMAS DE VENN Um diagrama de Ven é uma representação em forma de figura, na qual os conjuntos são representados por áreas delimitadas por curvas no plano. O conjunto universo U é representado pelo interior de um retângulo, e os outros conjuntos, por discos contidos dentro desse retângulo. Se A C B, o disco que representa A deve estar inteiramente contido no disco que representa B: Se A e B são disjuntos, isto é, se eles não possuem elementos em comum, então o disco representado por A estará separado do disco representado por B: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 8 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Entretanto, se A e B são dois conjuntos arbitrários, é possível que alguns objetos estejam em A, mas não em B, alguns estejam em B, mas não em A, alguns estejam em ambos e alguns não estejam nem em A nem em B; portanto, em geral: Considere o conjunto de todos os carros vendidos em cesta concessionária. Um vendedor classificou os carros em três subconjuntos, de acordo com os opcionais de cada carro. D = (carros com direção hidráulica), A = fcarros com ar condicionado), V = (carros com vidro elétrico) Os diagramas abaixo representam as seguintes situações: a) Carros com, pelo menos, alguma das três opções. b) Carros com ar condicionado, mas sem direção hidráulica e sem vidro elétrico. c) Carros com direção hidráulica ou ar condicionado, mas sem vidro elétrico. d) Carros com vidro elétrico e ar condicionado. e) Carros com vidro elétrico, ar condicionado e direção hidráulica. f) Conjunto dos carros vendidos sem nenhum dos três opcionais. 1.6.1 ARGUMENTOS E DIAGRAMAS DE VENN Muitas afirmativas feitas verbalmente são afirmativas sobre conjuntos e podem ser descritas através de Diagramas de Venn. Assim, eles podem ser usados para determinar se um argumento é válido ou não válido. Exemplo: Mostre que o seguinte argumento é válido: S1: Minhas panelas são os únicos objetos de metal que possuo. S2: Eu acho todos os seus presentes muito úteis. S3: Nenhuma das minhas panelas é de muita utilidade. S: Seus presentes para mim não são feitos de metal. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 9 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 2 ÁLGEBRA DECONJUNTOS 2.1 UNIÃO E INTERSEÇÃO A união entre dois conjuntos A e B, escrita por, é o conjunto de todos os elementos que pertencem a A, juntamente com todos os elementos que pertencem a B, isto é, A UB= fx] XE Aouxe B) A representação da união entre A ou B, pelo diagrama de Vemn, fica: A interseção dos dois conjuntos A e B, representada por AB, é o conjunto dos elementos comuns que pertencem a A eB,istoé AÍIB= fx|xe A exe B) . A representação da interseção entre A e B, pelo diagrama de Venn, fica: Teorema: São equivalentes ACB, ANB=A e AUB=B EXERCÍCIOS RESOLVIDOS 01) Seja A = [1,2,3,4), B= ([3,4,5,6,7), C= [2,3,5,7). Encontre: a) AUB b) AUC co) ANB d ANC 02) Suponha que M denote o conjunto de estudantes do sexo masculino de uma universidade C, e F denote o conjunto de estudantes do sexo feminino na universidade C. Como seria representado o total de estudantes da universidade C? O total de estudantes que têm o mesmo sexo? MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 12 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 2.2 COMPLEMENTARES Todos os conjuntos considerados em cada situação são subconjuntos de um conjunto universo fixo, U. O complementar absoluto, ou simplesmente, complementar de um conjunto A, denotado por AS, é o conjunto dos elementos que peitencem a U, mas não pertencem a A; isto é, AC = |x|xc U,x e A) : Atenção!!! Algumas referências bibliográficas utilizam a notação A!-A ou >A para o complementar de A. Exemplos: - Dados o conjunto universo U = (0, 1,2,3,4,5,6,7,8,9) e o conjunto A = (0, 1, 2), tem-se que AC= - Dados o conjunto universo e o conjunto A = (0, 1, 2), tem-se que AC= 2.3 DIFERENÇA Sejam A e B conjuntos. A diferença entre os conjuntos A e B, denotada por À — B, considera todos os elementos que pertencem ao conjunto A e que não pertencem ao conjunto B, ou seja: A-B=[x|xeAnxe B) O conjunto A-B é chamado de “A menos B” . Seu diagrama de Vemn se encontra a seguir: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 13 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI EXERCÍCIO RESOLVIDO 01) Suponha que U = t 2, 3.5), o conjunto de inteiros positivos, seja o conjunto universo, e que A= 11,2,3, 4. B= (3,4,5,6,7) , C= (6,7,8,9 e E= (2,4,6,8,..3 . Quais os conjuntos complementares deA,B,C,DeE?Encontre A-B, C-DeE-A. 2.4 CONJUNTO DAS PARTES A operação que, aplicada a um conjunto A, resulta num conjunto constituído de todos os subconjuntos de A é denominada conjunto das partes de A e é denotada por: P(AJ=[sncA) Se o número de elementos de um conjunto X é n, então o números de elementos de P(X) é 2". Exemplo: Dados os conjuntos A = (a), B= (a, b) e C= (a, b, c), tem-se que: -PMO)= -P(A)= -P(B)= -P(C)= 2.5 PRODUTO CARTESIANO Antes de definir a operação produto cartesiano, será definida uma sequência de n elementos como sendo uma n-upla ordenada, ou seja, n objetos em ordem fixa. Particularmente, dizemos que uma 2-upla é uma par ordenado e é representada por (x, y) ou (x, y) . Observação: A ordem dos elementos é importante! Logo, (x, y) A (y,x) . Sejam A e B conjuntos. O produto cartesiano de A por B é como segue: AxB=((a,bJaeAnbeB) MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 14 ANDRESSA.ASSAKAQ GMAIL.COM [gm] FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI a) AUB=BUA Lei de Comutatividade d) ANB=BNA a) AU(BNC)=(AUB)N(AUC) ») AN(BUC)=(ANB)U(ANC) Lei de Distributividade a) AUD=A Lei de Identidade d) ANU=A c) AUU=U JAND-D Lei de Involução (AS y =A a) AUAC-=U Lei dos Complementares c DANA =D qUS-o Vou a) (AUB)S = AC NBS Lei DeMorgan d) (ANB)S=ACUBC Existem dois métodos de demonstrar as leis listadas. Uma delas é através das definições das operações e, a outra, é pelo diagrama de Venn. Por exemplo, considere a Lei DeMorgan (A U BJ =atnpº Método 1: Método 2: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 17 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 3.1 CONJUNTOS FINITOS Conforme visto anteriormente, um conjunto é dito finito se contém exatamente m elementos distintos, onde m denota um número inteiro e não negativo. Caso contrário, o conjunto é dito infinito. Por exemplo, o conjunto vazio, 2, e o conjunto de letras do alfabeto são conjuntos finitos, enquanto que o conjunto de positivos inteiros pares, (2, 4,6,8, “> éinfinito. A notação n(A) será usada para indicar o número de elementos de um conjunto finito AS. outras notações para os mesmos elementos: HA, al ou card(A). Se A e B são conjuntos finitos disjuntos, então AUB é também finitoe n(AUB)=n(A)+n(B). Ao contar os elementos de AUB, primeiramente, conte os que estão em A. Existem n(A) elementos em A. Os únicos outros elementos de AUB são aqueles que estão em B, mas não em A. Mas como A e B são disjuntos, nenhum elemento de B está em A e, portanto, existem n(B) elementos que estão em B, mas não estão em A. Assim, n(AUB)=n(A)+n(B). Há também uma maneira de encontrar n(A U B) mesmo quando os conjuntos não estão disjuntos. Se A, Be C são conjuntos finitos, então AUBUC também é n(A,B,C)=n(A)+n(B)+n(C)-n(ANB)-n(ANC)-n(BNC)+n(ANBNC) EXERCÍCIOS RESOLVIDOS 01) Considere os dados a seguir sobre 120 estudantes de matemática no que diz respeito aos idiomas francês, alemão e russo. 65 estudam francês 45 estudam alemão 42 estudam russo 20 estudam francês e alemão 25 estudam Francês e russo 15 estudam alemão e russo 8 estudam os três idiomas Determine o número de alunos que estuda pelo menos um dos três idiomas e faça o diagrama de Venn com o número correto de estudantes. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 18 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Os problemas a seguir se referem ao conjunto universo U= (L2,3,...,8,9) e aos conjuntos A=(12,3,4,5/, B=[4,5,6,7), C=[5,6,7,8,9), D= [1,3,5,7,9), E = [2,4,6,8), F= (1,5,9). 02) Determine: a) AUBe ANB bd) AUCe ANC co) BUD e BND d) DUE e DNE e) EUE eENE f) DUF e DNF 03) Determine: aJA,B,D'cE' b)A-B,B-A, DE, FD co) ABB, COD, EOF 04) Determine: a) AN(BUE) DI (A-E) o (AND)-B a) (BNFJU(CNE) 05) Mostre que é possível que ANB=AÍIC semque B=C. 06) Determine quais os conjuntos finitos: a) A= festações do ano) b) B= festados do Brasil) c) C= finteiros positivos menores que b à) D= finteiros ímpares) e) E = [divisores inteiros positivos de 12) f) F= fcães do Brasil) 07) em uma pesquisa com 60 pessoas, verificou-se que: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 19 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Pode-se visualizar uma relação funcional no diagrama de Venn. Considerando a relação REA 5 A, talque R= ia, a),(b, co) eA=(a b,c),o correspondente diagrama fica: Observe que, de fato, cada elemento do conjunto origem está relacionado a, no máximo, um elemento do conjunto destino (o que significa que podem haver elementos da origem não relacionados a algum elemento do destino). 4.2.2 RELAÇÃO INJETORA Relação injetora é o conceito dual (inverso) de relação funcional. Uma relação binária R: A > B é uma relação injetora se, e somente se: (Vbe B)(vae A)(Va,e A)(aRbNa,Rb>aj=a,) Em outra palavras, para um relação ser injetora, cada elemento do conjunto destino deve estar relacionado a, no máximo, um elemento do conjunto origem. Exemplo: Dada a telação R:A > B, tal que A=(1,2),B=(1,2,3)eR= ((1,1),(12),(2,3)). tem-se que cada elemento de B está relacionado a, no máximo, um elemento de A. Veja a seguir o diagrama que representa a relação R. 4.2.3 RELAÇÃO TOTAL Uma relação binária R: A —> B é uma relação total se, e somente se: (vae A)(Ibe B)(aRb) MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 22 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Em outras palavras, para uma relação ser total, todos os elementos do conjunto origem devem estar relacionados a algum elemento do conjunto destino. O domínio de definição é o próprio conjunto A. Exemplo: Dada atelação R:A > B,talque A=(1,2), B=(1,2,3)eR= ((1,1),(2,2).(2,3) , tem-se que cada elemento de A está relacionado a algum elemento de B. Veja a seguir o diagrama que representa a relação R. 4.2.4 RELAÇÃO SOBREJETORA Relação sobrejetora é o conceito dual (inverso) de relação total. Uma relação binária R:A > B é uma relação sobrejetora se, e somente se: (vbeB)(Zae A)(aRb) Em outras palavras, para uma relação ser sobrejetora, todos os elementos do conjunto destino devem estar relacionados a algum elemento do conjunto origem. O conjunto imagem é o próprio conjunto B. Na matriz de uma relação sobrejetora, deve existir pelo menos um valor lógico verdadeiro em cada coluna. Exemplo: Dada a relação R:A >B,talque A=(a bc), B=(a b)eR= (la, b).(c,a)) , tem-se que cada elemento de B está relacionado a algum elemento de A. Veja a seguir o diagrama que representa a relação R. 4.3 MONOMORFISMO Uma relação R:A —>B é um monomorfismo se, e somente se, for simultaneamente uma relação total e injetora. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 23 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Dessa forma, o domínio de definição é o próprio conjunto A e cada elemento de B está relacionado com no máximo um elemento de A. Exemplo: Avtelação =: A > B, onde A = (a) e B= (a, b), é um monomorfismo. 4.4 EPIMORFISMO Epimorfismo é o conceito dual (inverso) de monomorfismo. Uma relação R:A>B é um epimorfismo se, e somente se, for simultaneamente uma relação funcional e sobrejetora. Dessa forma, o conjunto imagem é o próprio conjunto B e cada elemento de A está relacionado com no máximo um elemento de B. Exemplo: São exemplos epimorfismo, sendo que onde A =(a),B=(a,b)eC=(0,1,2): -=ASA -S:C>Btal que S= ((0,2),(1,b)) 4.5 ISOMORFISMO Uma telação R: A — B é um isomorfismo se, e somente se, existe uma relação S:B > A tal que: RoS-idy e SoR-=idg onde ida é uma endorrelação de igualdade em A (A, =) e idB é uma endorrelação de igualdade em B (B,=), chamadas de relação identidade. Assim, se RoS=id, e SoR =idp, pode-se afirmar que a relação R possui inversa. Ainda, se existe um isomorfismo entre dois conjuntos, eles podem ser chamados de conjuntos isomorfos. Exemplo: Dados os conjuntos A = (a b c) e B = (e f g)earelaçãoR:A-sB tal que R= (la, e(b, fds co) . Prove que R é um caso de isomorfismo. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 24 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 14) Avalie a validade do seguinte argumento: Todos os girassóis são amarelos e alguns pássaros são amarelos, logo nenhum pássaro é girassol. 15) Alguns baianos são surfistas. Alguns surfistas são louros. Não existem professores surfistas. Avalie a validade das conclusões: a) Alguns baianos são louros b) Alguns professores são baianos c) Alguns louros são professores d) Existem professores louros 16) Determine a validade do seguinte argumento: “Todos os meus amigos são músicos. João é meu amigo. Nenhum dos meus vizinhos é músico. João não é meu vizinho.” 17) Quais dos seguintes conjuntos são iguais? A=[x|x2-4x43-0), B=[x|x2-3x+2-0), C=(x|xeN,x<3), D= fxjxe N,x éimpar,x<S5b. E=(1,2). F=[1,2,1). G=(3,1), H=(11,3) 18) Liste os elementos dos conjuntos seguintes considerando o conjunto universo U = (a,b,c,d,...,y,Z). Identifique também os conjuntos iguais se existirem: A= fxjx é vogal) , B= fax é uma letra da palavra "carroça ” , C= fxlx precede "f' no alfabeto), D= fxjx é uma letra da palavra "caroço" 19) Encontre os elementos de X, considerando que A=(1,2,..,8,9), B=[2,4,6,8), C=11,3,5,7,9), D=(3,4,5), E=(3,5) a) X e B são disjuntos D) XCDmasXa&B )XCA mas XgC d)XcCmas XgZA Os problemas a seguir, referem-se aos conjuntos U=[1,2,..8,9), A=[1,2,5,6), B=(2,5,7), C=[1,3,5,7,9). 20) Encontre: a) ANB e ANC b) AUBe AUC JA ec 21) Encontre: a) A-Be A-C d) ABB e ADC 22) Encontre: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 27 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACE ADES a) (AUC)-B db) (AUB)' o) (BEC)-A 23) Sejam A= fa,b,c,d,e), B= (a,b,d,f,g), C= fb,c,e,g.h), D= (d,e,f,g,h). Encontre: a) AUB b) BNC o) AN(BUD) a) B-(CUD) e) (AUD)-C 9 BNCAD 2) AGB h CED CB j) (ANDJUB KW (C-A)-D D(AGD)-B 24) Sejam A e B conjuntos pertencentes ao universo U. Avalie as assertivas a seguir, atribuindo a cada uma (V) para verdadeira ou (F) para falsa. Justifique o motivo de considerar determinada assertiva falsa. a AUA'=U dD AUA!=O JANU=A ad AUD=A eJAUA=A DANA=A g(A)=A hm 9'=U i) AUB=BUA ) ANB=BNA k (AUB)'= ANB' D (ANBJ'=AUB' m) AU(BNC)=(AUB)N(BUC) n) AN(BUC)=(ANB)U(BNC) o) (AUB)UC= AU(BUC) p) (ANBJNC=AN(BNC) 25) Dentre as proposições a seguir, assinale as verdadeiras. Considere que: S=(2,3,3,4),R=(a,3,4,1)e U é o conjunto universo. ajaes baeR )R=S dfajcs efajes DOCS g) DER mÍidjes )UDS 26) Quais declarações são verdadeiras e quais são falsas? a)lefL2,3) b) 12 (12,3) o (lhe (12,3 à je (1,23 9 (ctL23) Dic) 27) Determine, explicitando os elementos constituintes, quais os conjuntos a seguir definidos: a) Números inteiros, positivos e ímpares; b) Números inteiros, positivos e cujo resto é 1 quando dividido por 4; c) Números inteiros, negativos e cujo resto seja -3 quando dividido por 4; d) Números primos e ímpares; e) Números primos e pares. 28) Sejam os conjuntos A = (1,1,2,2,2),B=(1,2,3),C=(1,2,3,4) eU é o conjunto universo. Ordene A,B,Ceo (2 de forma que o conjunto da direita seja um subconjunto do conjunto da esquerda. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 28 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 29) Seja o conjunto universo, U, aquele que corresponde a todas as pessoas. A é o conjunto de todos os bacharéis em Ciência da Computação, B é o conjunto de todos os contadores (mulheres e homens), C é o conjunto de todas as mulheres e, finalmente, D é o conjunto de todas as pessoas com idade igual ou superior a 40 anos. Determine o seguinte: a) O conjunto de todas as mulheres bacharéis em Ciência da Computação e que são também contadoras; b) O conjunto de todos os homens contadores com idade igual ou superior a 40 anos; c) O conjunto de todas as mulheres bacharéis em Ciência da Computação com idade abaixo de 40 anos e que são contadoras. 30) Simplifique a expressão (AU(BUC)N AN(BNC)UA), sabendo que A, B e C são conjuntos finitos. 31) Seja A= (1, 2, 3). Detemine Ax(A-(2)) e A?. 32) Sabe-se que A = (a,b,c). Determine A? e 22. 33) Sabendo-se que A= (1,2,3)eB=(2,3,4), determine P(A U B). 34) Sejam: A = (2,34,5) e B = (3,4,5,6,10). Para cada uma das relações, explicite seus elementos (pares) e determine o domínio e a imagem. a)R= (ts, y) E Ax Blx é divisível por y) b) R= (ts, y) E Ax B| xy=12) 9 R=((x,7)eAxB|x=y+1) gR=((xy)eAxB|x<y) 35) Determine quais dos seguintes conjuntos são finitos: a) O conjunto das retas paralelas ao eixo x b) O conjunto das letras do alfabeto c) O conjunto dos números múltiplos de 5 d) O conjunto dos animais que vivem na Terra 7.sx-15=0 e) O conjunto dos números que são solução da equação x2 4x f) O conjunto dos círculos contendo a origem (0,0) 36) Foi realizada uma pesquisa com uma amostragem de 25 carros novos à venda para verificar quais dos opcionais mais populares: ar condicionado (A), rádio (R) e vidros elétricos (V) já estavam instalados. A pesquisa concluiu que: 15 tinham ar condicionado 12 tinham rádio 11 tinham vidros elétricos 5 tinham ar condicionado e vidros elétricos 9 tinham ar condicionado e rádio 4 tinham rádio e vidros elétricos 3 tinham as três opções MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 29 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI a) algumas plantas verdes são comestíveis. b) algumas plantas verdes não são comestíveis. c) algumas plantas comestíveis têm clorofila. d) todas as plantas que têm clorofila são comestíveis. e) todas as plantas verdes são comestíveis. 45) Foi feita uma pesquisa em sala de aula com 50 alunos e obteve-se o seguinte resultado. 17 gostavam somente de coxinha e 21 gostavam somente de risólis. Sabendo que cada aluno gostava de pelo menos um desses salgadinhos, quantos gostavam de ambos? 46) Numa escola com 630 alunos, 250 estudam matemática, 210 estudam fisica e 90 deles estudam as duas matérias. Pergunta-se: a) Quantos alunos estudam somente matemática? b) Quantos alunos estudam somente fisica? c) Quantos alunos estudam matemática ou fisica? d) Quantos alunos não estudam nenhuma das duas matérias? 47) Numa pesquisa verificou-se que das pessoas consultadas, 100 liam o jornal A, 150 liam o jomal B, 20 liam os dois jomais e 110 não liam nenhum dos dois. Quantas pessoas foram consultadas? 48) Numa pesquisa de mercado, verificou-se que 2000 pessoas utilizam os produtos A ou B. O produto B é utilizado por 800 pessoas e 320 utilizam os dois produtos ao mesmo tempo. Quantas pessoas usam o produto A? 49) Num grupo de 99 esportistas, 40 jogam vôlei, 20 jogam vôlei e xadrez, 22 jogam xadrez e tênis, 18 jogam vôlei e tênis, e 11 jogam as três modalidades. O número de pessoas que jogam xadrez é igual ao número de pessoas que jogam tênis. a) Quantos esportistas jogam tênis e não jogam vôlei? b) Quantos jogam xadrez ou tênis e não jogam vôlei? c) Quantos jogam vôlei e não jogam tênis? 50) Sabe-se que o sangue das pessoas pode ser classificado em quatro tipos quanto a antigenos. Em uma pesquisa efetuada em um grupo com 120 pacientes de um hospital, constatou-se que 40 deles têm o antigeno A, 35 têm o antigeno B e 18 deles têm o antigeno AB. Nessas condições pede-se o número de pacientes cujo sangue tem o antigeno O. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 32 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Capítulo 2 - Lógica 1 ProPosiçõEs De maneira geral, podemos classificar as sentenças de um idioma da seguinte forma: Declarativas: Hoje é domingo. Eu não saí de casa o dia todo. Interrogativas: Quem vem lá? Qual é o seu nome? Exclamativas: Lógico! Viva! Imperativas: Não matarás! Feche a porta! 1.1 SENTENÇAS MATEMÁTICAS Sob o ponto de vista da lógica, um valor verdade pode ser atribuído apenas às sentenças declarativas, isto é, só se pode julgar que uma sentença seja verdadeira ou falsa, quando se tratar de uma declaração. x>3,7<10 e ? = 6 são sentenças matemáticas, sendo que, as duas primeira são verdadeiras e, a última, falsa. Alguns exemplos de sentenças às quais não podemos atribuir valor verdade: 1. Vá mais devagar! 2. Quanto custa este livro? 3. Fulano é carioca. Uma situação parecida pode surgir no contexto matemático. A frase x + 3 = 11 pode ser verdadeira (caso o valor de x seja 8) ou pode ser falsa (caso x seja diferente de 8). Leia as seguintes sentenças. Algumas são verdadeiras e outras são falsas: 1. A grama é verde. 2. Dezembro tem 31 dias. 3. Uma semana tem 8 dias. 4. O Sol é uma estrela. 5. O verão é a estação mais fria do ano. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 33 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 1.2 FUNÇÕES PROPOSICIONAIS Expressões, que contêm uma ou mais variáveis, são chamadas de funções proposicionais. Quando as variáveis são substituídas por constantes, a expressão torna-se uma proposição (verdadeira ou falsa, conforme as constantes atribuídas). Por exemplo, “x é homem”. Essa função proposicional toma-se uma proposição verdadeira se x = Sócrates e falsa se x = cadeira. Estas expressões também podem ser chamadas de sentenças abertas. 1.3 AXIOMAS E TEOREMAS Usando as regras da lógica, pode-se provar quando uma determinada sentença é verdadeira ou falsa. De acordo com essas regras, parte-se de um conjunto inicial de sentenças básicas, consideradas verdadeiras, os axiomas, e, usando as regras definidas pela lógica, prova-se a veracidade de novas sentenças. Estas novas sentenças verdadeiras são chamadas teoremas e podem também ser usadas na demonstração de novos teoremas. Em lógica, são consideradas apenas as sentenças que podem ser qualificadas como falsas ou verdadeiras. Tais sentenças são chamadas de proposições”. Usa-se letras minúsculas, como p, q our, para representá-las. Proposição, ou sentença, é todo conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo. 1.3.1 PRINCÍPIOS DAS PROPOSIÇÕES 1º Princípio da Não-Contradição Uma proposição não pode ser verdadeira e falsa, simultaneamente. 2º Princípio do Terceiro Excluído Uma proposição só pode ter dois valores verdades, isto é, é verdadeiro (V) ou falso (F), não podendo ter outro valor. 1 A palavra proposição também é usada em Matemática, fora do contexto estrito da lógica, como sinônimo de teorema. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 34 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Os exemplos apresentam o quantificador existencial, representado pelo símbolo 3 (existe). Mais uma vez, todas as proposições têm o mesmo significado. * Alguma pessoa é bonita. * Existe pessoa bonita. * Pelo menos uma pessoa é bonita Exemplo: dae R,sena=1 Os quantificadores universais e existenciais são trocados um pelo outro quando é feita a negação de uma proposição iniciada por um deles. Exemplo: ap: Existe aluno que não é estudioso. p: Todo aluno é estudioso. Outra maneira de enunciar a proposição —p seria: pelo menos um aluno não é estudioso, ou mesmo, há pelo menos um aluno não estudioso. Atenção! A proposição q: “Nenhum aluno é estudioso” não é a negação de p. 2.5 TABELAS-VERDADE O valor-verdade de cada proposição é sempre, ou verdadeiro (V), ou falso (F). O valor-verdade de uma proposição composta é determinado pelos valores-verdade de cada uma das proposições que a compõem e apresentados em forma de tabelas, denominadas tabelas-verdade. Por exemplo, considere a conjunção das proposições p e q, que denotamos por pA q. Lembre-se de que pA q é verdadeira apenas quando ambas as proposições, p e q, são verdadeiras. Há quatro possibilidades: * p é verdadeira e q é verdadeira. * p é verdadeira e q é falsa. * pé falsa e q é verdadeira. * pé falsa e q é falsa. A tabela-verdade correspondente é: cpa pag vivia virla eva FIF | MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 37 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI As tabelas-verdade correspondentes às proposições “p (não p)e Pv q (pouq) são: plalpva pop VIV V V F VIF v FIV FIV| YV Er 1 2.6 PROPOSIÇÕES CONDICIONAIS Há frases que se compõem de uma condição e uma consequência, conforme os exemplos: Se não chover irei a sua festa. Se n é um inteiro ímpar, então nº é impar. Se 1 é um número natural, tal quer <2, então r=1. Sejam p e q duas proposições. A proposição “Se p, então q” é chamada de implicação, onde o conectivo “Se ..., então...” caracteriza uma condição. A notação desta proposição é p>q As seguintes expressões podem ser empregadas como equivalentes de “Se A, então B”: Se A, B. B,se A. Todo A é B. A implica B. A somente se B. A é suficiente para B. B é necessário para A. A proposição p é chamada de hipótese e a proposição q de conclusão ou tese. O valor-verdade da proposição p — q depende dos valores-verdade da hipótese e da conclusão, sendo falsa apenas quando p é verdade e q é falsa. Há maneiras ligeiramente diferentes de enunciar a proposição p — q: * Se p, então q. * pimplicaq. * Para que p seja verdadeira, é necessário que q seja verdadeira. * Para que q seja verdadeira, é suficiente que p seja verdadeira. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 38 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Na verdade, a proposição p —»> q é logicamente equivalente à proposição “pv q, cuja tabela verdade fica: plal=-pl=pvg |p=>g WVIV F v v VIF ; F I FIV V v M Fr V v M Exemplo: 01) Considerando a proposição: Se eu ganhar na loteria, então nós viajaremos para Fortaleza. A tabela verdade fica: É importante perceber que a implicação depende diretamente da conclusão, e não da hipótese. A primeira possibilidade corresponde à situação ideal, isto é, p e q verdadeiras: Viajamos para Fortaleza porque eu ganho na loteria, a promessa é cumprida e p — q é verdadeira. No caso de não viajarmos para Fortaleza e eu ganhar na loteria, a promessa estará quebrada. Isto corresponde ao caso p verdadeira e q falsa, tomando p — q falsa. Agora, viajamos para Fortaleza, apesar de eu não ter ganhado na loteria. Ótimo! A condição não pode ser contestada. Isto corresponde ao caso p falsa, q verdadeira e, consequentemente, p — q verdadeira. Como última possibilidade, não viajamos à Fortaleza porque eu não ganhei na loteria. A condição não foi quebrada — corresponde ao caso p e q falsas e p — q se torna verdadeira. Note que, quando a hipótese p é falsa, independente do valor-verdade da consequência q, a implicação p — q é verdadeira. Portanto, a única chance de p —> q ser falsa é quando temos uma situação em que a hipótese é verdadeira e a consequência é falsa. 2.7 PROPOSIÇÕES BICONDICIONAIS Quando a hipótese é trocada pela consequência de uma proposição p —> q, cria-se uma nova proposição q — p chamada de conversão de p — q, que não são logicamente equivalentes. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 39 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI As tabelas-verdade são úteis para detectar quando duas proposições são logicamente equivalentes. O exemplo — “Não é verdade que Marcos é pintor e gosta de pescar” é um caso particular da situação — (PA q) equivalente a “p V q, em que p é “Marcos é pintor” e q é “Marcos gosta de pescar”. Exemplo: Ao montar uma tabela-verdade para =(pA q) e “pv-q, pode ser facilmente mostrado que as proposições são logicamente equivalentes. Nesse problema, constrói-se uma tabela com cindo linhas, na primeira delas, são alinhadas as diferentes etapas e, nas outras quatro, consideram-se todas as possibilidades, uma vez que há duas proposições básicas, p e q. plalpaglelpag)oe-plegl=pv-=g Exemplo: Construir a tabela-verdade de p N (q v r) . p glredqvrr dl palgrr) 3.1 LEIS DA LÓGICA Pode-se utilizar o conceito de equivalência lógica para expressar algumas das leis da lógica. Lei de Idempotência: Para qualquer proposição p, PAP=P Pvp=P Além disso, os conectivos V e A são comutativos e associativos. Leis de Comutatividade: Dadas duas proposições quaisquer, p e q, PAqg=q"p Ppvqg=qvp Leis de Associatividade: Dadas três proposições quaisquer, p, qe r, MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 42 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI (pag)ar=pa(gar) (pva)vr=pv(gvr) ou, simplificadamente: p Aq Ar pvquvr Leis de Distributividade: Dadas três proposições quaisquer, p, qe r, pv(grr)=(pvg)n(pvr) po(qvr)=(pag)v(par) Leis de DeMorgan: Para quaisquer proposições, p e q. =(pvg)=-pA-q =(png)=-pv-q Leis de Absorção: Para quaisquer duas proposições, p e q, pv(pAg)=p pA(pvq Exemplo: Consideremos as seguintes proposições: p: 2 é um número inteiro; q: 2 é maior do que 3; 1: 2 é um número primo. Conectando-as pode-se montar as seguintes proposições: a: 2 é um número inteiro, ou 2 é maior do que 3 e primo. b: 2 é um número inteiro ou maior do que 3, e 2 é um número inteiro ou primo. As proposições a = p v(q A r) eb= (p va) n(p V r) são logicamente equivalentes. Este é um caso particular da lei de distributividade. Determine o valor verdade dessas proposições. A palavra “princípio” pode ser usada como sinônimo de axioma ou de teorema. A mesma coisa acontece com a palavra “lei”, que está sendo usada para indicar quando determinadas proposições são logicamente equivalentes e, para isso, deve-se constatar a equivalência usando tabelas-verdade. Exemplo: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 43 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES As leis de DeMorgan são usadas para reescrever as negações de proposições. Considere a seguinte proposição: “Todo número par é divisível por 2 e existe um número inteiro n tal que 2n=3”. Reescreva a negação, usando as leis de DeMorgan. 3.1.1 QUADRO-RESUMO Para finalizarmos esta parte, vamos montar um quadro com o resumo das principais leis da lógica. Leis de Distributividade poqcer= rvqra por] pedaert= pique (pr) Leis de De Morgan ce pvagl= epoca ce lgtogl= ea py ma Leis de Absorção peipági=p pálpvagl=p EXERCÍCIO RESOLVIDO 01) Reescreva as proposições abaixo de diferentes maneiras e faça a tabela verdade: a) Se o tempo estiver bom, irei à praia. b) Se recebermos uma boa oferta, venderemos o terreno. 4 ARGUMENTOS E PROVAS 4.1 TAUTOLOGIAS Uma proposição composta formada pelas proposições A, B, C, ... é uma tautologia se ela for sempre verdadeira, independentemente dos valores lógicos das proposições A, B, C, ... que a compõem. Exemplo: A proposição “Se (A e B) então (A ou BJ” é uma tantologia, pois é sempre verdadeira, independentemente dos valores lógicos de A e de B, como se pode observar na tabela-verdade abaixo: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 44 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI válido, a verdade das premissas deve garantir a verdade da conclusão do argumento. Isto significa que jamais se pode chegar a uma conclusão falsa quando as premissas forem verdadeiras e o argumento for válido. É importante observar que, ao discutir a validade de um argumento, é irrelevante o valor de verdade de cada uma das premissas. Em Lógica, o estudo dos argumentos não leva em conta a verdade ou falsidade das proposições que compõem os argumentos, mas tão-somente a validade destes. Exemplo: O silogismo: “Todos os pardais (P) adoram jogar xadrez (X). Nenhum enxadrista gosta de óperas (Op). Portanto, nenhum pardal gosta de óperas.” está perfeitamente bem construído (veja o diagrama abaixo), sendo, portanto, um argumento válido, muito embora a verdade das premissas seja questionável. Pelo diagrama pode-se perceber que nenhum elemento do conjunto P (pardais) pode pertencer ao conjunto Op (os que gostam de óperas). 4.4.2 ARGUMENTO INVÁLIDO Um argumento é inválido, também denominado ilegítimo, mal construído ou falacioso, quando a verdade das premisssas não é suficiente para garantir a verdade da conclusão. Exemplo: O silogismo: “Todos os alunos do curso(C) passaram (P). Maria (m) não é aluna do curso. Portanto, Maria não passou” é um argumento inválido, falacioso, mal construído, pois as premissas não garantem (não obrigam) a verdade da conclusão (veja o diagrama abaixo). Maria pode ter passado mesmo sem ser aluna do curso, pois a primeira premissa não afirmou que somente os alunos do curso haviam passado. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 47 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Aqui, Maria não é do curso, mas passou ] A Aqui, Maria não passou. m A tabela abaixo traz um resumo das situações possíveis para um argumento: Quando um argumento é ... E as premissas... Então a conclusão será: Válido são todas verdadeiras Necessariamente Verdadeira (bem construido) não são todas verdadeiras ou Verdadeira ou Falsa Inválido são todas verdadeiras ou Verdadeira ou Falsa (mal construido) não são todas verdadeiras ou Verdadeira ou Falsa 4.4.3 CONSTRUÇÃO DO SILOGISMO A estrutura básica do silogismo consiste na determinação de uma premissa maior (ponto de partida), de uma premissa menor (termo médio) e de uma conclusão, inferida a partir da premissa menor. Em outras palavras, o silogismo sai de uma premissa maior, progride através da premissa menor e infere, necessariamente, uma conclusão adequada. Exemplo: “Todos os atos que ferem a lei são puníveis (Premissa Maior) A concussão é um ato que fere alei (Premissa Menor) Logo, a concussão é punível” (Conclusão) O silogismo estrutura-se por premissas. No âmbito da lógica, as premissas são chamadas de proposições que, por sua vez, são a expressão oral ou gráfica de frases assertivas ou juízos. O termo é uma palavra ou um conjunto de palavras que exprime um conceito. Os termos de um silogismo são necessariamente três: maior, médio e menor. O termo maior é aquele cuja extensão é maior (normalmente, é o predicado da conclusão); o termo médio é o que serve de intermediário ou de conexão entre os outros dois termos (não figura na conclusão) e o termo menor é o de menor extensão (normalmente, é o sujeito da conclusão). No exemplo acima, punível é o termo maior, ato que fere a lei é o termo médio e concussão é o menor. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 48 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 4.4.4 As REGRAS DO SILOGISMO 1º Qualquer silogismo possui somente três termos: maior, médio e menor. Exemplo de formulação correta: Termo Maior: Todos os gatos são mamíferos. Termo Médio: Mimi é um gato. Termo Menor: Mimi é um mamífero. Exemplo de formulação incorreta: Termo Maior: Toda gata(1) é quadrúpede. Termo Médio: Maria é uma gata(2). Termo Menor: Maria é quadrúpede. O termo “gata” tem dois significados, portanto, há quatro termos ao invés de três. 2º Os termos da conclusão nunca podem ser mais extensos que os termos das premissas. Exemplo de formulação correta: Termo Maior: Todas as onças são ferozes. Termo Médio: Nikita é uma onça. Termo Menor: Nikita é feroz. Exemplo de formulação incorreta: Termo Maior: Antônio e José são poetas. Termo Médio: Antônio e José são surfistas. Termo Menor: Todos os surfistas são poetas. “Antonio e José” é um termo menos extenso que “todos os surfistas”. 3º0 predicado do termo médio não pode entrar na conclusão. Exemplo de formulação correta: Termo Maior: Todos os homens podem infringir a lei. Termo Médio: Pedro é homem. Termo Menor: Pedro pode infringir a lei. Exemplo de formulação incorreta: Termo Maior: Todos os homens podem infringir a lei. Termo Médio: Pedro é homem. Termo Menor: Pedro ou é homem (?) ou pode infringir a lei. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 49 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Usando uma tabela-verdade: plalr=a|b=>00pllip=>9)Ap=a A primeira linha da tabela mostra que, quando p, = (p > q) e p;=Pp são ambas verdadeiras, temos que a conclusão c = q é verdadeira. Isto significa que os argumentos da forma Premissas: p > q Pp Conclusão: q são válidos. O argumento exemplificado é chamado de método direto ou modus ponens. Exemplo Este exemplo ilustrará outro tipo de argumento muito usado. Premissas: pl: Se não chover, Mateus irá ao parque. p2: Se Mateus for ao parque, ele brincará com seus amigos. Conclusão: c: Se não chover, Mateus brincará com seus amigos. Para analisá-lo, serão consideradas as seguintes proposições básicas: p: Não chove. q: Mateus vai ao parque. 1: Mateus brinca com seus amigos. A estrutura deste argumento é Premissas: p > q q>r Conclusão: p > r Este argumento é válido. A tabela-verdade: plalrip=>elg=>r|p=>rip=qgale=>"]=(p=>r) MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 52 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI As linhas 1, 5, 7 e 8 indicam que sempre que as premissas são verdadeiras, a conclusão é verdadeira. A Lei do Silogismo afirma que os argumentos do tipo Premissas: p > q q>r Conclusão: p > r são válidos. Exemplo Premissas: pl: Se eu ganhar o prêmio de fim de ano da companhia, compro carro novo p2: Compro carro novo Conclusão: c: Ganhei o prêmio da companhia. Este argumento é formado por apenas duas proposições simples: p: ganhar prêmio q: comprar carro A estrutura deste argumento é Premissas: p > q q Conclusão: p Esse argumento não é válido, conforme visto anteriormente. A tabela-verdade de (p > q)nq SP: [p | q [p=>4] pq (p>d)rg)=>p EXERCÍCIOS RESOLVIDOS Em cada um dos argumentos abaixo, destaque as proposições simples que compõem as premissas e as conclusões. Construa uma tabela-verdade com base nas proposições simples e nas premissas. Determine, então, a validade ou não do argumento. 01) Se o cachorro escapar, ele pegará o gato. Se o gato for pego, eu estarei em apuros. Portanto, se o cachorro escapar, eu estarei em apuros. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 53 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI 02) Todas as pessoas inteligentes gostam de Matemática. Romeu é uma pessoa. Romeu não gosta de Matemática, portanto, Romeu não é inteligente. EXERCÍCIOS PROPOSTOS 01) Determine quais das frases abaixo são proposições: * Cenouras são saudáveis. * O Brasil é um país tropical. * Todos os homens são astutos. * Faça as malas. * A paciência é uma virtude. * Debussy compôs duas sinfonias. * A paciência é um jogo. * Para todo mal há cura. * Todo mundo tem um segredo. * Não fume! * Todo amor é forte. * Quantos anos você tem? * O quadrado de cada número é não negativo. + Que calor! * Tom Jobim é um compositor brasileiro. * Quanto custa esta mesa? 02) Construa a negação de cada uma das seguintes proposições: * A pera é uma fiuta. * Algumas óperas são longas. * Todos gostam de dançar. * Algumas pessoas não têm carro. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 54 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 19) Se o mal existe, a vida é absurda. Se a vida é absurda, o mal existe. Logo, a vida é absurda se, e só se, o mal existe. 20) Se Sócrates tem razão, a vida por examinar é absurda. Sócrates tem razão. Logo, a vida por examinar é absurda. 21) Sócrates era grego. Kant não era grego. Logo, Deus existe. 22) A Justiça é possível se, e só se, Platão tiver razão. Platão tem razão. Logo, a Justiça é possível. 23) Não é verdade que nada é real e que tudo é uma ilusão. Nada é real. Logo, não é verdade que tudo é uma ilusão. 24) Não se pode definir a arte nem se pode definir o conhecimento. Logo, não é verdade que se pode definir a arte e se pode definir o conhecimento. 25) Se o conhecimento não for possível, a filosofia é inútil. Logo, se a filosofia não é inútil, o conhecimento é possível. 26) Se não é verdade que Deus existe e é sumamente bom, a vida não faz sentido. Deus não existe ou não é sumamente bom. Logo, a vida não faz sentido. 27) Tudo é uma ilusão e se tudo é uma ilusão, nada vale à pena. Logo, nada vale à pena. 28) Não é verdade que nada vale à pena e se tudo é uma ilusão, nada vale a pena. Logo, não é verdade que tudo é uma ilusão. 29) Não é verdade que se pode definir a arte e o conhecimento. Logo, não se pode definir a ate ou não se pode definir o conhecimento. 30) Se o conhecimento não for possível e tudo for uma ilusão, a filosofia é imútil. Se a filosofia for inútil, Platão e Kant estavam enganados. 31) Não é verdade que Platão e Kant estavam enganados. Logo, o conhecimento é possível ou não é verdade que tudo é uma ilusão. 32) Se legalizarmos as drogas, toda a gente poderá drogar-se. Se toda a gente puder drogar-se, acabaremos na mais completa barbárie. Logo, se legalizarmos as drogas, acabaremos na mais completa barbárie. 33) Se Sócrates era ateniense, era grego. Se era grego, não era egípcio. Logo, se Sócrates era ateniense, não era egípcio. 34) Ou podemos conhecer tudo ou não podemos conhecer nada. Mas não podemos conhecer tudo. Logo, não podemos conhecer nada. 35) Ou existo ou não existo. Mas não é verdade que eu não existo. Logo, eu existo. 36) Três alunos são suspeitos de não estarem matriculados no Curso de Raciocínio Lógico. O Aparecido entrevistou os três, para cobrar a matrícula, e obteve os seguintes depoimentos: AURO: “Joaquim não pagou e Cláudia pagou” JOAQUIM: “Se Auro não pagou, Cláudia também não pagou” CLÁUDIA: “Eu paguei, mas pelo menos um dos outros não pagou” Pede-se: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 57 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI a) Exprimir simbolicamente os depoimentos b) Identificar os pagantes e os não pagantes, supondo que todos os depoimentos são verdadeiros 4) Identificar os mentirosos, supondo que todos pagaram as matrículas. 37) Se Beto briga com Glória, então Glória vai ao cinema. Se Glória vai ao cinema, então Carla fica em casa. Se Carla fica em casa, então Raul briga com Carla. Ora, Raul não briga com Carla. Logo. a) Carla não fica em casa e Beto não briga com Glória. b) Carla fica em casa e Glória vai ao cinema. c) Carla não fica em casa e Glória vai ao cinema. d) Glória vai ao cinema e Beto briga com Glória. e) Glória não vai ao cinema e Beto briga com Glória. 38) Se Carlos é mais velho do que Pedro, então Maria e Julia tem a mesma idade. Se Maria e Julia tem a mesma idade, então João é mais moço do que Pedro. Se João é mais moço do que Pedro, então Carlos é mais velho do que Maria. Ora, Carlos não é mais velho do que Maria. Então: a) Carlos não é mais velho do que Leila, e João é mais moço do que Pedro. b) Carlos é mais velho que Pedro, e Maria e Julia tem a mesma idade. c) Carlos e João são mais moços do que Pedro. d) Carlos é mais velho do que Pedro, e João é mais moço do que Pedro. e) Carlos não é mais velho do que Pedro, e Maria e Julia não tem a mesma idade. 39) José quer ir ao cinema assistir ao filme “Fogo Contra Fogo”, mas não tem certeza se o mesmo está sendo exibido. Seus amigos, Maria, Luis e Julio têm opniões discordantes sobre se o filme está ou não em cartaz. Se Maria estiver cesta, então Julio está enganado. Se Julio estiver enganado, então Luis está enganado. Se Luis estiver enganado, então o filme não está sendo exibido. Ora, ou o filme “Fogo contra Fogo” está sendo exibido, ou José não ira ao cinema. Verificou-se que Maria está certa. Logo, a) O filme “Fogo contra Fogo” está sendo exibido. b) Luis e Julio não estão enganados. c) Julio está enganado, mas Luis não. d) Luis está enganado, mas Julio não. e) José não irá ao cinema. O texto abaixo refere aos exercícios de 40 a 43: Chapéuzinho Vermelho ao entrar na floresta, perdeu a noção dos dias da semana. A Raposa e o Lobo Mau eram duas estranhas criaturas que frequentavam a floresta. A Raposa mentia às segundas, terças e quartas- feiras, e falava a verdade nos outros dias da semana. O Lobo Mau mentia às quintas, sextas e sábados, mas falava a verdade nos outro dias da semana. (Adaptado de Linguagem Lógica de Iole de Freitas Druck) 40) Um dia Chapéuzinho Vermelho encontrou o Raposa e o Lobo Mau descansando à sombra de uma árvore. Eles disseram: Raposa: Ontem foi um dos meus dias de mentir. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 58 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI a CULDADES Lobo Mau: Ontem foi um dos meus dias de mentir. A partir dessas afirmações, Chapéuzinho Vermelho descobriu qual era o dia da semana. Qual era? 41) Em outra ocasião Chapéuzinho Vermelho encontrou o Raposa sozinha. Ela fez as seguintes afirmações: Eu menti ontem. Eu mentirei daqui a 3 dias. Qual era o dia da semana? 42) Em qual dia da semana é possível a Raposa fazer as seguintes afirmações? Eu menti ontem. Eu mentirei amanhã. 43) Em que dias da semana é possível a Raposa fazer cada uma das seguintesafirmações: a) Eu menti ontem e eu mentirei amanhã. b) Eumenti ontem ou eu mentirei amanhã. c) Se menti ontem, então mentirei de novo amanhã. d) Menti ontem se e somente se mentirei amanhã. 44) Três amigas, Tânia, Janete e Angélica, estão sentadas lado a lado em um teatro. Tânia sempre fala a verdade; Janete às vezes fala a verdade; e Angélica nunca fala a verdade. A que está sentada à esquerda diz: “Tania é quem está sentada no meio”. A que está sentada no meio diz: “Eu sou Janete”. Finalmente, a que está sentada à direita diz: “Angélica é quem está sentada no meio”. A que está sentada à esquerda, a que está sentada no meio e a que está sentada à direita são, respectivamente: a) Janete, Tânia e Angélica b) Janete, Angélica e Tânia c) Angélica, Janete e Tânia d) Angélica, Tânia e Janete e) Tânia, Angélica e Janete 45) Se Nestor disse a verdade, Júlia e Raul mentiram. Se Raul mentiu, Lauro falou a verdade. Se Lauro falou a verdade, há um leão feroz nesta sala. Ora, não há um leão feroz nesta sala. Logo, a) Nestor e Júlia disseram a verdade b) Nestor e Lauro mentiram c) Raul e Lauro mentiram d) Raul mentiu ou Lauro disse a verdade e) Raul e Júlia mentiram. 46) Uma sentença lógica equivalente a “Se Pedro é economista, então Luisa é solteira” é: a) Pedro é economista ou Luisa é solteira. b) Pedro é economista ou Luisa não é solteira. c) Se Luisa é solteira, Pedro é economista. d) Se Pedro não é economista, então Luisa não é solteira. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 59 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Os circuitos lógicos são usados para produzir decisões do tipo verdadeiro ou falso, baseados nas múltiplas entradas de sinais, que podem ser de dois tipos: tensão elétrica alta (ligado) ou tensão elétrica baixa (desligado). Eles são formados por linhas condutoras, chamadas de entradas, que recebem os sinais iniciais, e estão ligadas umas às outras por conectores diversos, chamados de portas, e terminam em uma saída que emite o sinal resultante. Na verdade, as portas são os tipos mais básicos, mais elementares, de circuitos lógicos. O nível de voltagem na saída de cada um deles depende dos sinais dados nas entradas, de acordo com as leis da lógica. A voltagem, ou tensão elétrica, alta corresponde ao valor-verdade verdadeiro, enquanto que a voltagem baixa corresponde ao valor-verdade falso. As três portas básicas estão listadas abaixo, com os seus respectivos diagramas: 1. Porta de inversão ou porta “NÃO” 2. Porta “E” p PAq g 3. Porta “OU” Pp q Exemplo Construir o circuito lógico correspondente à função proposicional (p V q) nar. p q Peg + Agora, para completar o circuito, fazemos a conexão destas duas partes com uma porta “E”: 2 Para nós é natural realizar tarefas matemáticas com dez dígitos. No entanto, para que um circuito use dez dígitos, é necessário que ele opere com dez níveis diferentes de voltagem - um para cada dígito — aumentando a complexidade em projetar e construi-los. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 62 ANDRESSA.ASSAKAQ GMAIL.COM [a] FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI p————— lovg)sn=r q ———— —— r A tabela-verdade desta proposição esclarece o funcionamento do circuito. Por exemplo, sob que circunstâncias se dará a saída um sinal de alta voltagem? Isto é equivalente a querer saber quando (pug)a-r. A tabela-verdade fica: p q rilpvglerl (pvghrsr A tabela indica que a saída estará ligada, isto é, um sinal de alta voltagem será gerado, quando a entrada r estiver desligada e pelo menos uma das fontes p ou q estiver ligada. É muito comum construir uma tabela usando apenas os dígitos O e 1 em lugar das letras F e V (sistema binário), permitindo “operar” com os números, usando a seguinte regra: V (ou) funciona como soma enquanto que / (e) funciona como produto. Atenção!!! Para facilitar a compreensão, convenciona-se como “soma” de 1 com 1 o valor 1, isto é, lvi=1. Nas tabelas-verdade: plalpva piglipÃg O comutador “NÃO”, —, apenas reverte de um dígito para o outro: E a Exemplo MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 63 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI A tabela do circuito lógico equivalente à função proposicional (p A q) Nr pode ser escrita usando o sistema binário: [p | q] r| pVq| =] (eVGA =p A saída emitirá sinal de alta voltagem (ligada) nos casos onde o número 1 aparece. Isto ocorrerá em três situações: sempre que a entrada r estiver ligada aparecerá o dígito O na coluna r e, pelo menos, uma das entradas p ou q estiver ligada. 5.1 SITUAÇÕES PRÁTICAS A seguir, duas situações práticas, que requerem construção de circuitos lógicos, serão abordadas. Exemplo Quer-se instalar um alarme sonoro num carro (saída) que soará caso o motorista desligue a chave de ignição (entrada) com os faróis acesos (entrada). Construindo a tabela-verdade associada a esta situação, pode-se perceber que a campainha deve soar apenas quando os faróis estiverem acesos e a ignição estiver desligada. Ignição | Faróis | Campainha A tabela-verdade da função proposicional —i AÍ fica: Plgflciloiaf Este circuito é formado de uma porta de inversão no sinal, que vem da chave de ignição, e uma porta “E” unindo os dois sinais resultantes: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 64 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES EXERCÍCIOS PROPOSTOS 01) Desenhe o circuito lógico correspondente à proposição (p A q) V (p A 1) V (a A (=1)) . Construa sua tabela-verdade e mostre que é equivalente ao circuito (p Ar) v(gn(=r)). Desenhe o circuito lógico correspondente a última proposição. 02) Desenhe um circuito lógico com apenas quatro portas e que seja equivalente ao circuito lógico abaixo. Para isto, escreva a proposição correspondente e use as leis da lógica para simplificá-la. SS 03) Considerando o diagrama lógico da figura, determine a expressão lógica da função F representada no diagrama. E F — 4 D— 04) Determine as expressões das funções lógicas representadas no diagrama. A 05) Determine e simplifique a expressão lógica da função F. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 67 ANDRESSA.ASSAKAQ GMAIL.COM [a] FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES 06) A tripulação de um avião é composta de dois pilotos e um engenheiro. Descreva um circuito que gere um alarme quando o engenheiro deixa seu posto ou quando ambos os pilotos deixam seus lugares. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 68 ANDRESSA.ASSAKAQ GMAIL.COM [a] FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES Capítulo 3 — Teoria dos Grafos 1 INTRODUÇÃO 1.1 AS SETE PONTES DE KÔNIGSBERG Conta-se que, no século XVIII, havia sete pontes cruzando o rio Pregel, que banhava a pequena cidade universitária prussiana de Kônigsberg, hoje Kaliningrad, Rússia. Quatro delas ligavam as margens opostas a uma pequena ilha formada nesse rio, outras duas ligavam as margens opostas a uma outra ilha, próxima à primeira, e a última ponte ligava as duas ilhas, conforme a figura. Os habitantes de Kônigsberg costumavam passear na cidade nas tardes ensolaradas de Domingo, mas nunca tinham conseguido dar um passeio especial: sair de casa, atravessar todas as pontes uma só vez e regressar a casa. No entanto, a dúvida quanto à possibilidade persistia. Euler, em 1735, conseguiu provar, com clareza, que não era possível dar o tal passeio. Para demonstrar esta impossibilidade apresentou à Academia de Ciências Russa de São Petersburgo um diagrama em que fazia a seguinte analogia: à terra, representada pelas duas margens, e às duas ilhas, associou quatro pontos; às sete pontes, associou sete linhas. O diagrama era algo parecido com o da figura: Feita tal associação, o problema das sete pontes ficou restrito a traçar o diagrama descrito, com um movimento contínuo, sem levantar o lápis do papel e sem traçar uma linha mais de uma vez. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 69 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Segundo esta definição, o diagrama representando as Pontes de Kônigsberg não representa um grafo, pois seria impossível distinguir, por exemplo, as duas arestas que conectam C com A. Isto porque, segundo a definição, dois vértices podem ser ligados por, no máximo, uma aresta. Esta dificuldade pode ser contornada introduzindo novos vértices, nomeados de acordo com as pontes. Desta forma podemos distinguir a passagem de A para C pela ponte c ou pela ponte d. Desenhe o grafo das Pontes. Identifique o conjunto vértices e o conjunto arestas. O grafo G com v'ertices V (G)= (A,B,C,D, a, b, c, de, fg) e arestas A(G) = (Ac, Ad Aa, Ab,Cc, Cd Cg,Ba,Bb,Bf, ÍD, eD, gD) pode ser representado da seguinte maneira: 2.2 ORDEM DE UM GRAFO O número de vértices de um grafo G é chamado de ordem do grafo G. Um mesmo grafo pode ter diferentes representações gráficas, dependendo da posição que os vértices são dispostos e as arestas são desenhadas. Exemplo: Os dois diagramas a seguir representam o mesmo grafo G com ordem 5. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 72 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI “4 A diferença básica de um diagrama para o outro é o posicionamento do vértice va. Escreva os conjuntos V e A de cada caso. Um grafo G é completo se quaisquer dois de seus vértices são adjacentes. Denota-se por K" o grafo completo de ordem n. Exemplo: Dado um conjunto de três elementos V = (vi, v>, V3), quantos grafos simples podem ser construídos, tais que V(G)=V? 2.3 ISOMORFISMOS Dois grafos G e G" são isomorfos se houver uma correspondência biunívoca entre os conjuntos dos seus vértices que preserva suas adjacências, isto é, se dois vértices de G são adjacentes, então os seus correspondentes véitices de G” também são adjacentes e viceversa. Exemplos: 01) Qual correspondência entre os vértices deve ser estipulada para que os grafos a seguir sejam isomorfos? vs A 2. N uv G Y MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 73 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 02) Mostre qual correspondência entre vértices faz com que os grafos G e G” sejam isomorfos. vi Y vi vi 2.4 GRAU DE UM VÉRTICE Seja G um grafo e seja v E v(G) um vértice de G. Chama-se grau de v o número de arestas ligadas av e denotamos esse número por grau(v,). Se v é um vértice isolado, então o grau(v,) é nulo. Exemplo Calcule o grau de cada vértice do grafo representado pela figura a seguir. Pode-se montar uma tabela: [ Um | grau(tm) Note que, grau(v:) + grau(vo)+ - - + grau(vs) = Pode-se perceber que a soma dos graus dos vértices é 2x7, igual a duas vezes o número de arestas. Teorema: Seja G uma grafo com vértices vi, V>, ..., Vn. Se m é o número de arestas de G, então n Sgrau(v;)=2m HI MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 74 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI 05) Determine quais grafos do exercício 4 são isomorfos uns aos outros. 06) Construa Ks. Qual é o grau de cada vértice de K,? Se você fosse construir Ko, quantas arestas desenharia? Em geral, quantas arestas tem K,? Verifique a validade do Lema do Aperto de Mãos. 2.4 CAMINHOS Um caminho ligando o vértice v até o vértice w é uma sequência de vértices adjacentes vo, Vi, V> ...» vk (ou de arestas a, = VoVi, & = ViV2, ..., ak = Vk-1Vk adjacentes), tais que a)vo=v bDw=w Esse caminho é demonstrado escrevendo a sequência de vértices VoViV2V3 ... Vk-1Vk Exemplo: Seja G o grafo representado na figura abaixo: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 77 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI O traço reforçado indica um caminho ligando o vértice vo até o vértice vs. Descreva o caminho: Outro caminho entre estes dois vértices pode ser representado por: Reproduza os vertices e trace os caminhos: a) ViVaVoViVaVs D) vovavavo C) VoVI VaViVaV4Vs Lembre!!! Para que uma palavra represente um caminho, é necessário que dois vértices seguidos sejam adjacentes. 3 CONEXIDADE DEGRAFOS Um grafo G é conexo se quaisquer dois de seus vértices podem ser ligados por algum caminho. Em particular, se um grafo G é conexo e tem mais do que um vértice, ele não pode ter vértices isolados. Um grafo não é conexo quando pelo menos dois de seus vértices não podem ser conectados por algum caminho. Neste caso, o grafo será composto de uma união disjunta de grafos conexos. Cada um destes grafos conexos é chamado de uma componente conexa do grafo. Na figura estã dois grafos, um conexo e o outro composto por três components conexas: v v V v v A representação do grafo pode ser formada de um só pedaço, mas o grafo não ser conexo, como acontece no grafo a seguir: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 78 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI 4 CiRcurTOS E CIRCUITOS EULERIANOS Diz-se que um caminho entre v e w é um caminho simples se cada uma das arestas que o compõem é usada uma só vez. Quando v é igual a w, tem-se um caminho simples e fechado, que chamamos de circuito. Finalmente, um dado circuito é euleriano se ele contém todos os vértices do grafo. Relembrando as pontes, reflita se o grafo da figura admite um circuito euleriano. Isto é, se existe um caminho simples (sem arestas repetidas) e fechado (começando e terminando num mesmo vértice) que percorra todos os vertices. 4.1 O TEOREMA DE EULER Leonhard Euler publicou nos anais da Academia de Ciência da Rússia, em 1736, o atigo Solutio problematis ad geometriam situs pertinentis - Uma solução de um problema da geometria da posição, onde ele respondia a questão das pontes. Teorema: Um grafo G admite um circuito euleriano se, e somente se, G é conexo e todos os vértices de G têm grau par. Note que todos os vértices do grafo do Problema das Pontes, rotulados por letras maiúsculas, têm grau impar, não permitindo um circuito euleriano, respondendo a questão definitivamente. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 79 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES Teorema: Um grafo G admite um caminho euleriano se, e somente se, é conexo e tem, no máximo, dois véitices de grau impar. EXERCÍCIOS PROPOSTOS 01) Considere o grafo G a seguir e identifique quais dos caminhos indicados são simples, quais são circuitos e quais são circuitos eulerianos: a) VyViVaVo D) vsVov avi Vo v V, C) VaV4VSVoViVaV3 d) VoViV2V3 Vi VaVsVoV3 Va €) VaVaVi VoVaVaVi BD VivaVsvovi B) V3Vi Va Va VoViVaVa h) ViV3VoVSVaVIV3V2Vi 02) Quais dos grafos a seguir são conexos? Indique quais são as components conexas daqueles grafos que não são conexos. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 82 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES 03) Considere os grafos representados a seguir. Determine quais admitem um circuito euleriano e quais são grafos eulerianos. Nos casos afirmativos, encontre um circuito euleriano ou atravesse o grafo, caso ele seja um grafo euleriano. 04) Para que valores de n o grafo K, admite um circuito euleriano? 05) As informaçõees necessárias para construir um determinado grafo podem ser armazenadas numa tabela, da seguinte forma: Se o grafo for de ordem n a tabela será quadrada com uma linha e uma coluna reservada para cada vértice, respectivamente. A interseção de uma coluna com uma linha é preenchida com o número 1 ou com o número 0, caso os véitices correspondentes sejam adjacentes ou não, respectivamente. Observe que a diagonal que vai do canto superior esquerdo do quadrado para o canto inferior direito será preenchida com zeros, pois num grafo não há laços. Por exemplo, o grafo G a seguir tem ordem 4 e sua tabela está disposta ao seu lado. v, V, v, Vv, a | 0/1 La Note que a tabela é simétrica em relação à diagonal, pois se o vértice v; é adjacente ao vértice v;, então v;também é adjacente a v;. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 83 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI No exemplo dado, a quata coluna tem um zero na primeira posição indicando que v, não é adjacente av; e, como a terceira coluna tem três números 1 e um número 0, sabemos que o grau de v; é 3. Esta tabela é chamada de matriz de adjacência do grafo. Represente o gráfico G de ordem 5 correspondente à seguinte matriz de adjacência: | vos [usas os a lmfolafifoli . Mufifofifo(1 “e na lusfalafofaila lufolofifolo fesfalilifolo vo “my, 06) Um jovem casal morava no interior de um certo estado, na cidade de Altamira. As cidades mais próximas de Altamira são Bicas, Candeias, Diamantina, Estrela do Sul, Figueiras e Galo Branco. Elas são conectadas por uma rede de estradas um tanto mal cuidadas. O rapaz prometeu casar-se com a moça assim que terminasse o trabalho de recuperação destas estradas, pois havia acabado de firmar um contrato com as prefeituras das cidades para fazer isto. Ele prometeu à jovem que iniciaria os trabalhos em Altamira e prosseguiria sobre cada trecho de estrada retornando, no fim do trabalho, à Altamira. Será que o jovem é sincero? Poderá a moça confiar em seu noivo? Para responder as questões, uma tabela sera fomecida. Nela estão marcadas com 1 as cidades que estão ligadas por uma estrada, e com O onde não há estrada conectando as cidades. Bpilojijojolo/o o I LiOoljijú o A Elilololilolila ; . . Glojoltijijiji o MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 84 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Para visualizar o problema não é necessário usar um modelo de dodecaedro, basta planificar o problema. O quebra-cabeça proposto por Sir Hamilton consiste em encontrar um ciclo hamiltoniano para o grafo obtido do dodecaedro pelo processo de planificação: 7.2 CONDIÇÃO SUFICIENTE PARAA EXISTÊNCIA DE UM CICLO HAMILTONIANO A questão da existência ou não de um ciclo hamiltoniano para um determinado grafo é mais dificil do que sua contrapartida euleriana. No entanto, a experiência sugere que, quanto mais arestas, melhor. Sendo que, a distribuição destas arestas entre os véitices também é importante. Se as condições do enunciado forem satisfeitas por um certo grafo G, então ele admitirá um ciclo hamiltoniano. Porém, há grafos que não satisfazem as hipóteses do teorema e, no entanto, admitem ciclos hamiltonianos. Teorema: Seja G um grafo de ordem n (n > 3). Se grau(V) > n/2 para cada vértice V de G, então G admite um ciclo hamiltoniano. Se um grafo tem 4 vértices, para podermos usar o teorema, cada vértice deverá ter pelo menos grau 2, mas, atenção, caso ele seja de ordem 5, cada um dos véitices deverá ter pelo menos grau 3. Exemplo Usando lápis e papel, construa alguns exemplos de grafos com 5, 6 e 7 vértices, cada um deles com todos os vértices de grau maior ou igual a 3, 3 e 4, respectivamente. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 87 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Atenção!!! O converso do teorema é falso, isto é, há grafos com muitos vértices, mas com graus pequenos, que admitem ciclos hamiltonianos. Por exemplo, um polígono com 17 lados admite um ciclo hamiltoniano (basta percorrer o polígono uma vez), mas o grau de cada um de seus vértices é 2. Prova do Teorema A primeira etapa consiste em constatar que o grafo G é conexo. Note que ser conexo é uma condição necessária para que o grafo admita um ciclo hamiltoniano. Considere o seguinte exemplo: 1 Ny o Du AZ V, Ve E impossível chegar a qualquer vértice de índice par começando em algum vértice de índice ímpar e vice-versa. A razão disto é que este grafo não é conexo, mas formado por duas componentes conexas, cada uma delas sendo um ciclo. Lema: Se G é um grafo de ordem n(> 3) e grau(V ) > n/2 para todo vértice V de G, então o grafo G é conexo Suponha que G satisfaça a hipótese do lema, mas não seja conexo. Então G é composto por mais de uma componente conexa. Vamos chamar de C a componente conexa que tem o menor número de vértices. A ordem de C é menor ou igual a n/2. Note que, em grafos conexos, o grau de cada vértice é, no máximo, igual à ordem do grafo menos um. G Mas cada véitice de C tem grau maior ou igual que n/2, por hipótese, e isto é uma contradição. Conclui-se, então, que G é conexo. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 88 ANDRESSA.ASSAKAQ GMAIL.COM A FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI = a A segunda etapa será a de conseguir um caminho K com as seguintes propriedades: a) K é um caminho simples (as arestas não se repetem) sem vértices repetidos; b) Qualquer caminho que tenha estas duas características é, no máximo, tão longo quanto K. A partir deste caminho especial conseguiremos o desejado ciclo hamiltoniano. Seja G o grafo seguinte: c » A ordem de G é 6 e cada um de seus vértices tem grau 3. Como G é um grafo conexo, as hipóteses do teorema são satisfeitas. Considere K o seguinte caminho simples, onde todos os vértices de G comparecem: A CFBDE. Este caminho satisfaz as duas características que mencionamos antes: as arestas AC, CF, FB, BD e DE comparecem uma única vez, e como todos os vértices estão presentes, não há caminho mais longo sem que haja repetição de vértices. Observe os vértices que estão nos extremos do caminho: A e E. O vértice A está ligado ao vértice C pela aresta que já faz parte do caminho K, além de ser, também, adjacente a Be D. O vértice E, por sua vez, está ligado aos vértices C e F, além de ser adjacente a D pela aresta que faz parte do caminho K. Colocando estas informações em um esquema: Note que os vértices B e F, adjacentes a A e E, respectivamente, estão dispostos um após o outro, no caminho K. MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 89 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES A) ViVaVaVI VoVaVa €) V4VIV3VoVsVa 02) Quais dos seguintes grafos admitem um ciclo hamiltoniano? Caso sua resposta seja afirmativa, encontre- os pada cada grafo. 03) Divida um retângulo de tamanho m por n em quadrados iguais de tamanho 1 por 1 e considere isto como uma representação de um grafo que tem cada cruzamento por vértice. As figuras abaixo representam os casos 2x4, 3x4 e 4x4. Estes grafos admitem ciclos hamiltonianos? MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 92 ANDRESSA.ASSAKAQ GMAIL.COM O FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ FACET MATEMÁTICA DISCRETA - 1ºSI FACULDADES 8 ÁRVORES 8.1 SUBGRAFOS Sejam G = (V,A)e G' = (V',A”) dois grafos. As operações de conjuntos podem ser usadas para criar novos grafos: GUG'=(VUVLAUVM. GNG'=(VNVLANV') Se V'CV e A'CA, pode-se afiimar que G” é um subgrafo de G denotado, simplesmente, por G'cG. Exemplo Sejam G e G” grafos de ordem 5 e 4, respectivamente, com V (G) = (Vi, V2, Va, Va VsJe V(G )= (vs, Va, Vs, Vo). Suas representações gráficas, bem como as representações gráficas de GUG'e GNG' ficam: Ag Vi “q Ve Va V vi 3 Va 5 Gg i 6 5 vi wa “ Va “e —————s Ya Y5 GUG' GnG' va Vs MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 93 ANDRESSA.ASSAKAQ GMAIL.COM FACULDADE DE CIÊNCIAS SOCIAIS E APLICADAS DO PARANÁ MATEMÁTICA DISCRETA - 1ºSI Exemplo Os grafos G1 e G2 representados a seguir são tais que Gy UG, = K>. v Ys va vs Yz Va Y “a vá Vs Gi q Neste exemplo os dois grafos têm exatamente os mesmos vértices, mas qualquer aresta de um deles não é aresta do outro. Desta forma, G, N G, é o grafo de ordem 5, com todos os vértices isolados. O grafo Kº 'e o menor grafo que contém um ciclo (circuito onde não há repetição de vértices). No exemplo anterior, viu-se que Kº pode ser escrito como a união de dois subgrafos, pois K* admite dois ciclos (hamiltonianos) de 5 vértices: ViV>VaV4VsVi € VIV3VsV2VaVI. K 3 1 q Uma árvore é um grafo conexo e que não tem ciclos, como as árvores genealógicas, por exemplo. Quando um grafo G não tem ciclos, é chamado de acíclico. Assim, uma árvore é um grafo conexo e acíclico. Exemplo Considere todas as árvores possíveis contendo 5 vértices: MATEMÁTICA DISCRETA — PROFA. ANDRESSA ASSAKA 94 ANDRESSA.ASSAKAQ GMAIL.COM