Matemática Discreta - Lógica Matemática, Teoria dos Conjuntos e Aplicações na Computação

MATEMÁTICA DISCRETA Prof ESP RONIE CESAR TOKUMOTO 004 Aula 01 015 Aula 02 024 Aula 03 034 Aula 04 041 Aula 05 049 Aula 06 057 Aula 07 065 Aula 08 074 Aula 09 082 Aula 10 087 Aula 11 096 Aula 12 102 Aula 13 111 Aula 14 120 Aula 15 127 Aula 16 Lógica Matemática Teoria dos Conjuntos Lógica Proposional Contagem e Quantificação Lógica de Predicados Relações Funções Indução Matemática Teoria dos Números Somatórias e Produtórias Teoria de Grafos Árvores em Grafos Grafos Eulerianos e Hamiltonianos Fluxos em Redes e Emparelhamentos Probabilidade Álgebra Booleana Introdução A Matemática é uma das ciências mais antigas do conhecimento humano tendo séculos e séculos de estudos realizados e teorias desenvolvidas por grandes matemáticos e contribuintes de outras formações Por sua vez a Matemática Discreta possui bastante conexão com a Computação pois toda a lógica utilizada na construção de algoritmos para o desenvolvimento de softwares para solucionar problemas reais por meio de soluções computacionais utiliza conceitos matemáticos de lógica normalmente Veremos aqui assuntos fundamentais tais como a teoria dos números teoria dos conjuntos e lógica de predicados que servem como base para muitos conceitos de computação bem como outros conceitos como os de relações grafos e funções que são amplamente utilizados na computação em várias áreas Assim dentro dos estudos além de muitos conceitos fundamentais matemáticos sempre que possível alguma referência à área da Computação será feita por meio de exemplos e associações de ideias Bons estudos 3 Aula 01 Lógica Matemática Considerada uma ciência voltada ao estudo do raciocínio e seu desenvolvimento a lógica se vale de métodos e princípios para validar conclusões em busca da verdade como dizia Aristóteles 384 aC 322 aC Derivada do termo grego logos que pode ter mais de uma correspondência em português inicialmente como estudo princípio ou explicação e posteriormente em interpretações como as de Herácito 535 aC 475 aC passou a ter mais relação com a ideia de pensamento Por meio da lógica é possível que o pensamento seja organizado tanto para a matemática em si quanto para todas as demais áreas exatas contribuindo também para estudos em certas áreas humanas que tenham como base as atividades racionais Um problema que gerou a necessidade de uma padronização foram os diferentes idiomas que produziam ambiguidades em argumentos ou de compreensão difícil em função da forma como as frases eram elaboradas para explicar esses argumentos e assim com o passar dos tempos símbolos foram introduzidos para padronizar e reduzir as ambiguidades na leitura e interpretação mais precisa Dessa forma com uma simbologia padronizada definida é possível a formulação de argumentos para a lógica matemática que também é utilizada na computação mesmo com algumas mudanças em virtude de particularidades como a não utilização de parte dos símbolos padrões matemáticos em algumas linguagens de programação Relações entre proposições são definidas a partir de fórmulas com base nesses símbolos reduzindo possíveis ambiguidades de linguagens formais e podendo ser utilizadas com conjuntos e regras que as transformam George Boole 18151864 Gottlob Frege 18481895 e Augustus De Morgan 1806 1871 estudiosos mais recentes propuseram obras como Álgebra Booleana e regras para uso em demonstrações matemáticas Mais recentemente ainda o autor Copi 1978 p 19 propõe que a lógica é um estudo que utiliza mecanismos para avaliar raciocínios corretos ou incorretos e Salmon 1978 p 13 traz a ideia complementar de que a lógica trabalha com argumentos que se referem a raciocínios lógicos para se chegar a conclusões e inferências que obtêm conclusões com base em dados 5 Um dos temas mais importantes da tecnologia da informação TI nos dias atuais é a inteligência artificial IA que utiliza como base os conceitos associados à lógica em geral para gerar novos conhecimentos a partir de conjuntos de dados A área que mais utiliza a lógica dentro da TI é a programação em geral que é a ferramenta para o desenvolvimento de soluções computacionais em forma de algoritmos ou códigos em linguagens de programação Os conceitos da lógica são a base da programação devido a tudo que ela oferece em termos de produção de soluções computacionais pois a base destas é a maior automatização possível de processos e para isso mecanismos lógicos como decisões baseadas em expressões lógicas são bastante comuns O estudo da lógica em si pode parecer bastante complexo e de difícil assimilação mas através do aprendizado dos conceitos básicos com exemplos adaptados à tecnologia da informação sempre que possível este aprendizado pode ser facilitado obtendose melhor absorção de novos conhecimentos além da compreensão de sua aplicação direta ou indireta no desenvolvimento de software principalmente O uso da lógica não é feito apenas por suposições pois cada lógica utilizada na área de TI necessita estar corretamente formulada através de provas ou demonstrações para que seja adequada para uso em soluções pois erros em aplicações podem 6 ocorrer devido a equívocos e erros na formulação de condições que controlam a execução das aplicações Acesse o link Disponível aqui Lógica Inferência Conclusão é consequência necessária da premissa Texto bastante didático para complementar os estudos desta aula Para avançar nos estudos é preciso conhecer alguns termos que são utilizados ao longo de todo o curso e que representam conceitos fundamentais da lógica matemática que são também utilizados nos estudos da área de TI Sendo a lógica baseada em argumentações para a validação do que se propõe cada argumento é constituído de proposições e assim a proposição é o termo inicial a ser estudado Proposição pode ser dita como uma sentença e ser avaliada como verdadeira V ou falsa F e pode ser escrita com base na linguagem natural de cada idioma ou em linguagem simbólica padrão matemática ou adaptada para a TI Observe os exemplos da imagem 2 7 Imagem 2 Fonte O autor A água é líquida O gelo é sólido O vapor é gasoso A temperatura do vapor é maior que a temperatura do gelo A densidade do gelo é igual à densidade da água Nos exemplos da imagem 2 temos alguns exemplos de proposições que podem ser avaliadas como verdadeiras ou falsas a partir da informação que é transmitida pela composição dos elementos e dados fornecidos mas um detalhe importante é que as proposições para serem avaliadas pressupõem conhecimentos préadquiridos Outro ponto a ser observado é que todas as proposições são construídas a partir da linguagem natural sem o uso de símbolos matemáticos ou de lógica computacional sendo então mais facilmente interpretadas e compreendidas Os três primeiros exemplos da imagem 2 trazem dados com relação a estados físicos da água e seus nomes sendo então facilmente avaliados como V ou F caso o leitor esteja familiarizado com esses conceitos físicos de líquido sólido e gasoso No exemplo seguinte é feita uma comparação entre dois dos estados citados nas proposições anteriores de forma que o resultado da proposição depende não da avaliação pura de um elemento mas do valor de um em relação a outro elemento da proposição Por fim no último exemplo é feita outra comparação nos mesmos moldes do exemplo anterior mudando apenas o critério de comparação e os elementos utilizados mas o uso da lógica em si é semelhante para avaliar se a comparação entre 8 dados resulta verdadeira ou falsa Também podese elaborar exemplos utilizando linguagem simbólica para avaliar proposições e retornar valores V ou F como nos exemplos da imagem 2 Observe os exemplos trazidos na imagem 3 para análise Imagem 3 Fonte O autor 5 5 10 8 3 7 1 4 2 2³ 8 Nestes exemplos da imagem 3 novas proposições são elaboradas utilizando agora símbolos lógicos em todos os exemplos e estes podem ser ou não iguais tanto na lógica matemática quanto na lógica computacional No primeiro exemplo é comparado o resultado de uma soma simples entre dois valores numéricos inteiros a outro valor numérico inteiro utilizandose símbolos para a soma e para a comparação de igualdade entre os dois lados da comparação No segundo exemplo da imagem 3 um valor à esquerda é comparado a um valor à direita e o símbolo utilizado na comparação maior que é padrão tanto na lógica matemática quanto na computacional facilitando os estudos 9 No terceiro exemplo antes da comparação a ser realizada através de novo operador lógico que varia entre a matemática e a computação em função da ausência do mesmo símbolo utilizado comumente na matemática em teclados utilizados em computadores em geral assim um símbolo alternativo foi definido para uso na TI Os resultados dos cálculos efetuados em cada lado do operador lógico da proposição são utilizados para avaliação da proposição lógica no final resultando em valor verdadeiro neste caso No último exemplo da imagem 3 um cálculo de exponenciação é realizado antes da comparação com o dado contido no outro lado da proposição desse modo é importante sempre observar que não há uma obrigatoriedade na realização de uma comparação sempre em proposições pois existem mais regras matemáticas adaptadas à TI para a construção de proposições como regras de precedência na avaliação e uso efetivo de símbolos em proposições para evitar resultados equivocados Exercitar a criação de proposições é muito importante pois além de realizar o treino da lógica matemática e computacional é possível conhecer e praticar as linguagens natural e simbólica para o desenvolvimento de proposições A quantidade necessária para uma boa fixação e devida compreensão varia de pessoa para pessoa mas é fato que sem o treino da construção dessas proposições e demais conceitos estudados pode haver a falsa impressão do completo aprendizado do que é lido mas na verdade há muitos conceitos que podem não ter sido compreendidos e assim o aprendizado fica falho logo em seu início 10 Existem formas de se compor sentenças que poderiam ser consideradas proposições pela forma como parecem conter informações que podem ser avaliadas como verdadeiras ou falsas mas na verdade certos tipos como sentenças imperativas ou exclamativas representam verdades sempre na ideia de quem as define dessa forma não representam argumentos Sentenças interrogativas também não podem ser utilizadas pois não podem ser avaliadas como verdadeiras ou falsas pois carecem de dados para avaliação Observe os exemplos da imagem 4 para ter uma ideia desses tipos de sentenças não válidas como argumentos Imagem 4 Fonte O autor 11 Nestes exemplos da imagem 4 são definidas sentenças que podem conter algum tipo de informação mas estas ou carecem de elementos para avaliação em termos de serem verdadeiras ou falsas ou possuem apenas a possibilidade de serem sempre verdadeiras ou sempre falsas por representarem instruções ou afirmações independentemente de demonstrações ou comprovações científicas Com isso podese passar ao conceito de argumento em si que representa um conjunto de proposições em que algumas são premissas para que se possa obter conclusões indicadas em outras proposições contidas no argumento As premissas funcionam como mecanismos para comprovar e sustentar a ideia proposta na proposição de conclusão Uma conclusão não deve ser indicada sem que as premissas sejam capazes de alguma forma de comprovar o que é indicado na conclusão Os argumentos podem se basear em lógica indutiva ou dedutiva sendo ambos os tipos elaborados de forma semelhante através de premissas e conclusões Argumentos ditos indutivos são formados por premissas que tendem a servir como motivos para se chegar à conclusão proposta sem que estas sejam provas científicas ou definitivas para a conclusão Neste caso o argumento não deve ser dito como válido ou inválido mas sim utilizamse os termos forte ou fraco Argumentos dedutivos são baseados em premissas que representam provas formais necessárias para que a conclusão seja aceita como verdadeira assim como as premissas senão todo o argumento é invalidado ou dito não válido Salmon 1978 p 30 cita que em argumentos dedutivos se todas as premissas são verdadeiras a conclusão também deve ser e as premissas devem conter toda a informação para a conclusão Também afirma que em argumentos indutivos se todas as premissas forem verdadeiras é provável mas não garantido que a conclusão também seja e a conclusão pode conter informação não presente nas premissas 12 Imagem 5 Fonte O autor Todos os mamíferos amamentam seus filhotes Todas as espécies de macacos amamentam seus filhotes Portanto macacos são mamíferos Se consigo ser escolhido em um processo seletivo sou contratado Infelizmente não fui contratado em um processo seletivo Portanto estou desempregado Um objeto foi atirado em um lago e afundou Outro objeto foi atirado no mesmo lago e afundou Um terceiro objeto foi atirado no mesmo lago e afundou Logo se qualquer outro objeto for atirado no mesmo lago afundará Através dos exemplos da imagem 5 é possível compreender como funciona o mecanismo de elaboração de argumentos com base em premissas que servem de base para as conclusões precedidas pelo termo portanto No primeiro argumento exemplo é citado que todo animal mamífero amamenta seus filhotes em uma primeira premissa e numa segunda premissa que todas as espécies de macacos também amamentam seus filhotes Com base no conceito de que animais que amamentam são mamíferos podese incluir os macacos como um subconjunto do conjunto de todas as espécies de animais mamíferos No segundo exemplo a primeira premissa diz que uma pessoa escolhida em um processo seletivo é contratada e na sequência a segunda premissa informa que a pessoa não foi escolhida A conclusão não é necessariamente verdadeira pois mesmo pessoas empregadas podem tentar processos seletivos para outras ofertas de emprego 13 O terceiro exemplo traz um exemplo de argumentação indutiva pois se utiliza de três situações que servem como premissas de que vários objetos foram jogados em um lago e afundaram e a partir dessas premissas foi concluído que um outro objeto atirado no mesmo lago afundaria mas como não se sabe a exata natureza dos objetos e se são iguais ou não existe sim a probabilidade de o quarto objeto também afundar mas pode não acontecer Para concluir esta aula casos como esses de premissas verdadeiras suscitarem conclusões que podem ser a princípio verdadeiras mas que na verdade são inconclusivas são perigosas e conhecidas como falácias ou sofismas que representam falsas crenças segundo Copi 1978 p 73 que cita que falácias podem representar argumentos psicologicamente persuasivos mesmo que sendo incorretos os argumentos Um meio de melhor aprender sobre a construção de argumentos é com a repetida construção desses com temas diferentes visando à obtenção tanto de argumentos verdadeiros quanto falsos observando a correta elaboração a partir dos estudos realizados até então Criar argumentos pensando nas premissas e a partir delas tentar obter conclusões diversas se possível é uma boa atividade de treino lógico que se constitui em uma das habilidades mais importantes em desenvolvedores de software Também é possível elaborar proposições que representem conclusões verdadeiras e a partir destas elaborar as proposições necessárias e verdadeiras para que a conclusão seja também verdadeira Criar exemplos de casos incorretos também ajuda no aprendizado pois também é necessário certo trabalho mental para que se possam criar proposições falsas ou verdadeiras que permitam diferentes composições e conclusões também falsas ou verdadeiras 14 Aula 02 Teoria dos Conjuntos Considerada a base da matemática moderna a teoria dos conjuntos é relativamente recente se comparada à história da matemática em si e foi idealizada pelo matemático russo Georg Cantor 18451917 que a definiu como elementos que compõem um todo mas que sejam nitidamente diferentes uns dos outros A partir dessa ideia várias definições foram sendo idealizadas como significados para infinito e demais definições contribuíram para unificar diversas áreas da matemática e outras aplicações ligadas a áreas do conhecimento Essa teoria permite relacionar elementos cotidianos e definir relações entre estes de forma a organizálos a partir de critérios variados e permitir avaliações diversas dos elementos de forma isolada de conjuntos de elementos e das relações entre os elementos contidos ou não em conjuntos Alguns conceitos primitivos dessa teoria são os de conjunto elemento e relação sendo que esses conceitos se apoiam em conceitos complementares como o de que pode ser considerado como uma coleção não ordenada de objetos de forma que não se repitam e que possuam alguma característica em comum Tais elementos podem ou não estar num conjunto e que existe uma relação que define a pertinência ou não de cada elemento a um conjunto Conjuntos podem ser descritos por seus elementos pelas características de seus elementos ou até graficamente através de diagramas planos como o descrito na imagem N que representa um conjunto exemplo A que contém os elementos 0 1 e 2 Imagem N A 0 1 2 A x x é inteiro e 0 x 2 0 1 2 16 Para este conjunto é possível definir uma representação utilizando linguagem simbólica para a relação existente entre os elementos do conjunto como a indicada na imagem N que diz que o conjunto A é composto por elementos que podem ser definidos por uma variável x tal que x seja um número inteiro maior ou igual a 0 e menor ou igual a 2 Existem alguns conjuntos padronizados nesta teoria indicados por símbolos especiais como N para números ditos naturais ou inteiros maiores ou iguais a 0 Z para os números inteiros entre infinito e infinito Q para o conjunto dos números ditos racionais que envolvem frações que podem resultar em valores decimais finitos ou periódicos infinitos R para os números reais que envolvem todos os números inteiros racionais ou irracionais e C para os números ditos complexos que possuem uma forma padronizada como a bi sendo a e b números reais e i2 1 Observe os exemplos de elementos de cada conjunto na imagem 7 Imagem 7 Fonte O autor A x 2x N 0 2 4 6 B x x é inteiro e x Z 3 2 1 0 1 2 C x 2x Q e 3 x 5 23 24 25 D x x R e x 3 5 7 3 5 7 E x 1xi C e 2 x 4 12i 13i 14i Nestes exemplos da imagem 7 temos um conjunto contendo elementos de cada tipo definido anteriormente N Z Q R e C em que todos são compostos por elementos característicos destes conjuntos especiais e tendo ou não uma relação claramente 17 definida entre eles nestes exemplos No conjunto A por exemplo temos a relação que diz que qualquer número pertencente aos números naturais multiplicados por 2 estão contidos neste conjunto assim como o conjunto B é formado pelos números inteiros do conjunto Z No conjunto C os elementos são definidos como todas as frações em que 2 pode ser dividido por um número maior ou igual a 3 e menor ou igual a 5 O conjunto D é definido como um conjunto das raízes quadradas dos números inteiros 3 5 e 7 e o conjunto E é definido pelos números complexos 1xi onde x aceita números maiores ou iguais a 2 e menores ou iguais a 4 Dentre os conjuntos definidos pelos exemplos da imagem 7 é possível observar intuitivamente que nenhum desses conjuntos possui os mesmos elementos mas é importante definir como se pode garantir ou não a igualdade entre elementos de dois conjuntos e para que isto seja possível todos os elementos de um conjunto A por exemplo sejam elementos de um conjunto B e viceversa Outras definições importantes sobre conjuntos são de que existe um chamado conjunto universo U que é composto por todos os elementos de um determinado contexto e o conjunto vazio um que não contenha elemento algum sendo este um conjunto único com notação Ø ou Também é importante nomear alguns tipos de conjuntos específicos como o conjunto unário que possui apenas um elemento conjunto finito que contém uma determinada quantidade de elementos finitos e conjunto infinito no qual não se pode determinar a quantidade total de elementos do conjunto N Z Q R e C Outro conceito importante é o de subconjunto em que todo elemento de um conjunto também esteja contido em outro conjunto ou seja para todo a A a B Uma notação bem específica para isto seria que A B que significa que A está contido ou é igual a B Exemplos práticos para este conceito aplicados na tecnologia da informação são de alunos de uma turma em relação ao todo de uma escola ou funcionários de um setor em relação ao todo de uma empresa No caso de o subconjunto A de um conjunto B não ter exatamente os mesmos elementos tendo então A menos elementos que B aplicase a notação A B que significa que o conjunto A está contido mas não é igual a B 18 Aos poucos é perceptível que existem muitos símbolos associados à matemática e à lógica matemática mais especificamente e para auxiliar nos estudos a imagem 8 traz uma lista com os principais símbolos utilizáveis nesta disciplina e seus significados Imagem 8 Fonte O autor Igualdade Diferença Maior que Menor que Maior ou igual a Menor ou igual a Existe Não existe Pertence Não pertence U União Intersecção Ø Vazio Infinito Contém Contido Contém e igual Contido e igual Não contém Não contido Não contém e não igual Não contido e não igual Para todo Somatório Condicional Produtório Bicondicional 19 Imagem 9 Fonte O autor Muitos dos símbolos apresentados na imagem 8 serão pouco utilizados ao longo dos estudos mas outros farão parte das explicações e notações utilizadas em muitos dos conceitos estudados neste material e também poderão ser encontrados em outras fontes de pesquisa sendo assim importante que se conheça sua existência Pouco a pouco com a evolução dos estudos a tendência é que esses símbolos matemáticos vão sendo assimilados e o estudo se torne mais fácil com a familiaridade sempre que encontrados em algum conceito Assim complementando os estudos sobre subconjuntos e aproveitando a simbologia apresentada na imagem 8 várias definições podem se aplicar a subconjuntos e relação a conjuntos aos quais pertençam Um subconjunto A pode estar contido e não ter exatamente os mesmos elementos de um conjunto B mas pode também estar contido e ser igual tendo ambos os conjuntos exatamente os mesmos elementos Também pode ocorrer de o subconjunto A não estar contido no conjunto B ou A não estar contido e B e nem ser igual Complementarmente podemos dizer que um conjunto B pode conter todos os elementos de um subconjunto A assim como pode B conter exatamente os mesmos elementos do subconjunto A Pode ocorrer também de o conjunto B não conter os elementos do subconjunto A ou B não conter e nem ser igual a A A imagem 9 ilustra algumas das definições de subconjuntos citadas até então usando os chamados diagramas de Venn ideais para uso com a teoria de conjuntos Pela imagem 9 é possível observar a ocorrência de várias das notações apresentadas de forma gráfica e bastante intuitiva em que há um exemplo de subconjunto A contido em um conjunto B sendo que A possui menos elementos que B 20 Também há um exemplo no qual o subconjunto A está contido no conjunto B mas ambos possuem os mesmos elementos sendo assim considerados iguais e por fim um exemplo onde o conjunto A não pode ser dito como subconjunto de B pois está apenas parcialmente contido em B assim é dito como não contido Um conceito muito importante relacionado ao estudo dos conjuntos são as operações que podem ser realizadas entre conjuntos conceito muito útil tanto na matemática quanto na computação Uma das operações se chama União em que os elementos de um conjunto A são agrupados com os elementos de um conjunto B independentemente de um ser subconjunto do outro ou não e a notação para esta operação é A U B x x A ou x B Outra operação importante se chama Intersecção que representa o conjunto formado por todos os elementos que estejam contidos tanto num conjunto A quanto num conjunto B A notação geral seria A B x x A e x B Observe que a única diferença na notação da união em relação à intersecção é o uso dos conectivos E e OU que diferenciam de forma adequada os conceitos destas operações Conjuntos são aplicados em muitas áreas além da matemática e da computação sua aplicação é muito forte na área de banco de dados e uma boa referência que ajuda a lembrar dos conceitos de conjuntos é a linguagem SQL usada em banco de dados para os que trabalham na área pois as consultas unem tabelas e cruzam dados assim como funcionam os operadores de U e em conjuntos Além disso para ter bom rendimento no tema desta aula é essencial resolver diversos problemas de operações com conjuntos para que se torne bem claro cada conceito e operação estudados 21 Imagem 10 Fonte O autor Outra operação básica é a de Complemento de um conjunto A que representa o conjunto de todos os elementos fora de um conjunto A Para isto é necessário que se definam quais seriam estes elementos todos fora do conjunto A A totalidade de elementos dentro e fora do conjunto é chamada de conjunto U universo e o conjunto formado pelos elementos contidos no universo mas fora do conjunto A é o conjunto complemento A Como notação temos A x x U e x B Outra operação relevante é a de Diferença entre conjuntos que seria uma subtração de elementos de um conjunto A que não estejam em um conjunto B Como notação temos A B x x A e x B Observe a imagem 10 para uma ilustração das operações citadas através de diagramas de Venn 22 Problema Supondo três conjuntos A 1 2 3 4 5 B 5 6 7 8 9 e C 1 2 5 8 9 10 11 quais seriam os conjuntos A U C e A B C supondo que elementos iguais de cada conjunto significam estar nos dois ou mais conjuntos ao mesmo tempo Solução Para se obter um conjunto união de outros dois basta agrupar todos os elementos dos dois conjuntos sem repetir elementos pois como citado um número repetido nos conjuntos significa que o mesmo elemento está em mais de um conjunto simultaneamente A U C 1 2 3 4 5 8 9 10 11 sendo elementos em A e C sem repetições A B C 5 sendo que apenas o elemento 5 está nos 3 conjuntos ao mesmo tempo ou seja o único que se repete em todos 23 Aula 03 Lógica Proposional Imagem 12 Fonte O autor Após a introdução de alguns conceitos importantes na disciplina iniciase nova etapa de estudos com o aprendizado da chamada lógica proposicional muito relevante para os estudos em programação O chamado valor lógico de uma proposição está relacionado com a possibilidade de uma proposição ser verdadeira ou falsa e estas se baseiam em princípios básicos como o da não contradição que diz que uma proposição não pode ser verdadeira e falsa ao mesmo tempo e do terceiro excluído que propõe que toda proposição só pode ter valor lógico verdadeiro ou falso não havendo outra possibilidade As proposições podem ser classificadas como simples ou compostas e basicamente a diferença se dá por conta de proposições simples conterem uma única afirmação verdadeira ou falsa e as compostas conterem em sua estrutura duas ou mais proposições conectadas por conectivos lógicos que permitem que os valores lógicos individuais de cada proposição contida na proposição composta possam ser também avaliadas com base no conectivo lógico como verdadeiras ou falsas Os conectivos lógicos servem então para que resultados de proposições sejam combinados e cada conectivo lógico retorne diferentes resultados para cada combinação possível de valores lógicos Os conectivos lógicos mais conhecidos estão indicados na imagem 12 Estes três símbolos ilustrados na imagem 12 são representativos para os conectivos mais utilizados na tecnologia da informação em diversas áreas de estudo mas principalmente na programação pois são essenciais na elaboração de expressões condicionais que também podem resultar em valores verdadeiros ou falsos e são equivalentes às proposições 25 Estes conectivos também são importantes na lógica matemática assim como outros que também são muito utilizados na lógica matemática mas que na programação são utilizados de formas distintas da disciplina Observe os conectivos matemáticos fundamentais na imagem 13 Imagem 13 Fonte O autor SÍMBOLO CONECTIVO E conjunção v Ou disjunção NÃO negação SESENÃO condicional SE E SOMENTE SE bicondicional Complementando a imagem 12 a imagem 13 traz além dos três conectivos E OU e NÃO citados como bastante comuns na programação os conectivos e que podem ter sua funcionalidade disponibilizada em programação através de recursos mais complexos e não simples símbolos representativos com função de conectivos normalmente O uso de conectivos está associado à composição de proposições e para representar de forma simbólica e abreviada as regras de cada conectivo em relação ao seu uso e resultados possíveis podese padronizar notações como as que seguem indicadas na imagem 14 dadas proposições quaisquer p e q 26 Imagem 14 Fonte O autor p não p p q p E q p v q p OU q p q se p então q p q p se e somente se q A partir das formas de uso de conectivos para unir proposições de forma que sejam avaliadas em conjunto é possível a elaboração de exemplos para complementação da explanação de cada conectivo mas antes é importante saber que cada conectivo utilizado entre duas proposições pode resultar em resultados verdadeiros ou falsos mas tendo variações de resultados com o uso de cada conectivo mesmo utilizandose um mesmo par de proposições p e q Estas variações possíveis de resultados ocorrem em função das possíveis combinações de resultados prováveis das proposições p e q que podem resultar em verdadeiro ou falso de acordo com cada conectivo e composição de resultados verdadeiros ou falsos das proposições No caso do conectivo de negação uma proposição no formato p onde se lê não p funciona como um inversor do valor resultante da proposição p seja ele verdadeiro ou falso Observe a imagem 15 para conhecer a chamada tabelaverdade que indica as possíveis variações de resultados para a proposição e como são afetadas pelo conectivo 27 Imagem 15 Fonte O autor p p V F F V Como exemplo associado ao conectivo negação podese simplesmente negar qualquer proposição tendo ela valor lógico verdadeiro ou falso como numa proposição p que representa a sentença 0 é um número e sua negação p seria algo como 0 não é um número A conjunção já indica um conectivo que necessita de duas proposições de forma a uni las para que os valores lógicos de cada proposição possam ser utilizados pelo conectivo para a obtenção de outro valor lógico resultante e baseado na regra de que se todos os valores lógicos das proposições conectados pela conjunção forem verdadeiros o resultado na conjunção é também verdadeiro Observe a tabelaverdade na imagem 16 Imagem 16 Fonte O autor p q p q V V V V F F F V F F F F 28 Um exemplo de conjunção poderia ser escrito em função de proposições p e q onde p q poderiam representar uma avaliação das proposições p 0 é um número e q 0 é par poderia ser obtido como resultado da proposição composta verdadeiro pois ambas as proposições possuem valor lógico verdadeiro também Outro conectivo importante é a disjunção que traz uma ideia de que duas proposições unidas por este conectivo podem ambas ser verdadeiras ou pelo menos uma para que o resultado da operação utilizando a disjunção seja verdadeiro Assim para que este conectivo retorne verdadeiro a única possibilidade é quando as duas proposições sendo avaliadas retornem falso satisfazendo a condição para este conectivo lógico Veja a imagem 17 e observe as variações de resultados deste operador através de sua tabelaverdade Imagem 17 Fonte O autor p q p v q V V V V F V F V V F F F Nessa tabela verdade da disjunção é importante observar que apenas quando as duas proposições forem falsas o resultado da proposição composta será falso diferentemente da conjunção que resulta verdadeiro apenas quando as duas proposições simples possuem valor lógico verdadeiro para cálculo da conjunção Como exemplo de disjunção partindo de duas proposições p e q onde p v q poderiam representar uma avaliação das proposições p 0 é um número e q 0 é ímpar um resultado válido para esta proposição composta seria verdadeiro pois 29 mesmo a proposição q tendo valor lógico falso a proposição p é verdadeira sendo esta condição suficiente para que a proposição composta como um todo resulte verdadeiro O conectivo a seguir chamado de condicional é diferente dos três anteriores pois não é comumente utilizado como símbolo único em programação na maioria das linguagens de programação mas tanto na lógica matemática quanto na computacional são amplamente utilizados Observe a imagem 18 contendo a tabelaverdade deste conectivo Imagem 18 Fonte O autor p q p q V V V V F F F V V F F V Nesta tabela da imagem 18 é possível observar que em apenas uma situação o resultado falso é obtido quando se operam duas proposições simples com um conectivo condicional Apenas quando se a primeira proposição for verdadeira a proposição à direita do conectivo que deve ser induzida pela proposição à esquerda resulta falsa indicando uma situação confusa e por isto resultando falsa para este conectivo Para exemplificar o uso do conectivo condicional e partindo de duas proposições p e q onde p q poderiam representar uma avaliação das proposições p todo número divisível por 2 é par e q 4 é ímpar temos que o valor lógico verdadeiro de p é falso de q resultam em falso para a proposição composta pela avaliação do conectivo condicional 30 Na construção de proposições compostas utilizando este conectivo em p q p representa uma hipótese ou base para a avaliação do conectivo e q é a conclusão ou consequência Existe um detalhe que pode complicar a compreensão do uso deste conectivo que se refere ao caso onde em p q se p é falsa mas q é verdadeira então a condicional resulta verdadeira Algumas proposições especiais estão associadas ao conectivo condicional como as chamadas contrapositiva que tem como base a notação q p recíproca com a notação q p e inversa com a notação p q Por fim o chamado conectivo bidirecional se refere a proposições com a notação onde sendo p e q proposições a proposição p se e somente se q ou p q resulta verdadeira sempre que as duas proposições simples da proposição bicondicional forem verdadeiras ou ambas falsas Quando o valor lógico das proposições contidas na bicondicional tiverem valores lógicos distintos o resultado da bicondicional também será falso Observe a imagem 19 para observar a tabelaverdade desse conectivo lógico Imagem 19 Fonte O autor p q p q V V V V F F F V F F F V Por ser uma bicondicional é possível concluirse que sendo p e q proposições p q pode ser interpretada como sendo p condição necessária e suficiente para q e q sendo condição necessária e suficiente para p 31 Para exemplificar este conectivo bicondicional assumimos duas proposições p e q onde p q poderiam representar uma avaliação das proposições p todo número divisível por 2 é par e q 4 é ímpar temos que tendo as duas proposições valores lógicos falsos o conectivo bicondicional gera um valor lógico verdadeiro para a proposição composta Percebese então a importância de se conhecer a elaboração e compreensão de tabelasverdade pois além de serem visualmente mais rápidas de serem avaliadas e compreendidas podem oferecer um modo mais prático para se avaliar proposições compostas mais complexas com mais de um conectivo lógico por exemplo Partindo de uma proposição composta S p q q podemos elaborar uma tabela verdade para que todas as possíveis combinações de valores lógicos possíveis sejam indicados e as avaliações dos conectivos lógicos sejam feitas lembrando que o uso de parênteses torna uma proposição prioritária em relação a outra Observe a imagem 20 que contém a tabelaverdade completa para esta proposição S Imagem 20 Fonte O autor p q p q q V V V V V F F V F V F F V V F V F F V F F F F F F F V V PRIORIDADE 1 3 2 Pela análise da tabelaverdade gerada pela proposição S proposta no exemplo da imagem 20 é importante observar a ordem em que são realizadas as etapas até que se obtenha a coluna final de valores lógicos para a proposição S como um todo 32 Para isto primeiro devemos preencher as colunas de valores base para as proposições simples p e q com as possibilidades V e F possíveis Em seguida pelo padrão geral utilizado na matemática as operações dos conectivos vão sendo sequencialmente resolvidas da esquerda para a direita e as operações entre parênteses têm prioridade de resolução Outra regra importante na resolução de proposições deste tipo usando tabelas verdade é a de precedência de conectivos e o operador de maior precedência ou seja a ser primeiro verificado é o de negação seguido do conectivo disjunção depois conjunção em seguida o conectivo condicional e por fim com menor prioridade nas proposições compostas o conectivo bicondicional Assim inicialmente é calculado o valor de p q por estar a proposição inserida entre parênteses e estar mais à esquerda na proposição composta toda Depois podese calcular p pela regra de precedência e tendo os valores lógicos destas duas proposições p q e p pode calcular a última e de menor prioridade o conectivo condicional neste caso Complementando este estudo sobre lógica proposicional existem tabelasverdade com especial significado e nomenclatura como é o caso de tabelas verdade que tenham como resultado final todas as possibilidades verdadeiras que são chamadas de tautologias Outro conceito importante é o de tabelaverdade do tipo contradição na qual todos os resultados finais possíveis numa tabelaverdade sejam todos falsos para determinadas proposições compostas Acesse o link Disponível aqui Um complemento para o tema de lógica proposicional estudado nesta aula pode ser encontrado nesta indicação de fonte de pesquisa que traz de forma bem resumida os operadores lógicos e tabelasverdade para eles 33 AULA 04 Contagem e Quantificação Para melhor compreender propriedades de conjuntos numéricos existe a teoria da contagem que é utilizada para comprovar conhecimentos intuitivos a respeito da ordem dos elementos de conjuntos desta natureza A contagem envolve a associação de números a elementos de um conjunto de forma que esta associação impeça repetições ou sobras de elementos sem associação Pequenos conjuntos de elementos diversos como os que compõem uma palavra frase objetos ou uma quantidade finita de números podem todos ser quantificados e enumerados sequencialmente permitindo a contagem e organização dos elementos Com isso podese indicar uma função específica para cada conjunto citado de forma que o domínio da função seriam os números que estão associados a cada elemento do conjunto imagem da função que contém os elementos finitos associados à contagem Como exemplo imagine um conjunto contendo as letras da palavra CONTAGEM Os elementos deste conjunto podem ser associados a números ordenados do conjunto N dos números inteiros naturais de forma que o número 1 seja equivalente à letra C 2 com a letra O 3 com N e assim por diante até 8 com a letra M Neste exemplo uma função associou os elementos dos dois conjuntos e os números de 1 a 8 do conjunto N representam o domínio da função que associa os elementos e as letras da palavra e o conjunto imagem desta função que atendem aos requisitos de injetora e sobrejetora ou seja bijetora O uso deste conceito na computação é bastante comum pois todo tipo de estrutura de dados que é armazenada temporária ou permanentemente com dados precisa ser identificada e organizada para acesso a esses dados e a teoria de contagem permite que seja ordenada a lista de dados de forma a garantir a sequência e não repetição A teoria da contagem pode ser aplicada em diversas áreas e para diferentes aplicações pois seu princípio é bastante utilizado na matemática como um todo e uma aplicação válida para esse estudo na disciplina é a de subconjuntos possíveis em um conjunto 35 Problemas relacionados a números sempre serão constantes na sociedade pois é com base na contagem que muitas atividades do mercado se baseiam como otimização de recursos valores financeiros estoques etc Além disso áreas como a estatística e outras dependem muito da contagem para seus estudos e assim como muitas destas áreas são atendidas com ferramentas de TI é comum que os algoritmos trabalhem com esses temas e necessitem processar dados a partir da contagem por exemplo Como exemplo é possível utilizar um conjunto A a b c d e a partir deste conjunto obter a totalidade de subconjuntos possíveis tendo como base apenas que a quantidade de elementos do conjunto é 4 Como se pode criar subconjunto com 0 a 4 elementos de A assim temos que são possíveis os subconjuntos Ø a b c d a b a c a d b c b d c d a b c a b d a c d b c d a b c d A partir da obtenção de 16 subconjuntos de elementos sem repetição de elementos em cada subconjunto ou de subconjuntos excluindo também troca na ordem de elementos é possível chegarmos a uma função fn 2ⁿ sendo n a quantidade de elementos de um conjunto A Relações sobre conjuntos como U ou podem ser quantificadas pois geram quantidades mensuráveis de elementos muitas vezes e por isso podem ser organizados e ordenados de forma a atender os requisitos de sequencialidade e não repetição de elementos A partir de conjuntos A e B finitos uma relação de união entre os elementos dos conjuntos pode ser também quantificada pois não há como a soma de dois valores numéricos finitos gerar um número infinito mesmo que sendo quantidades muito grande de elementos continuam sendo finitas as quantidades 36 O mesmo ocorre com a intersecção entre dois conjuntos A e B finitos pois como as quantidades são quantificáveis a intersecção entre 0 ou no máximo todos os elementos dos conjuntos resulta em números finitos em todos os casos Acesse o link Disponível aqui Um complemento para o tema de contagem é apresentado nesta fonte você verá que um problema foi resolvido de uma forma bastante intuitiva Outro exemplo de problema matemático e computacional se relaciona com a ideia de combinações de elementos de um conjunto como no caso das possíveis combinações de letras partindo de um conjunto A a c d e e tendo como regra o não uso de cada elemento mais de uma vez mas usando todas as letras em cada combinação possível Assim alguns exemplos de combinações possíveis entre os elementos do conjunto A atendendo às regras de formação de novos elementos para o conjunto gerado seriam acde cdea deac e eacd por exemplo Para se chegar ao total de combinações possíveis pela matemática o cálculo é feito através do chamado cálculo fatorial representado por n ou neste caso 4 que é calculado com a quantidade de elementos sendo multiplicada por ela mesma decrescida em uma unidade até que o valor chegue a um de forma recursiva Nesse exemplo apresentado 4 Seria então calculado com 4 x 3 x 2 x 1 resultando em 24 possibilidades distintas de combinações de elementos mantendo o uso de todos sem repetições ou quantidade diferente de 4 elementos em cada combinação Este cálculo será mais bem explorado na aula sobre indução 37 Muitos termos e símbolos matemáticos já foram utilizados neste material e continuarão a ser durante a evolução das aulas em função dos conteúdos serem em parte acumulativos mas também pelo fato de muitas notações serem padronizadas para os conteúdos Um termo muito importante utilizado é existe que se refere à ideia de que pelo menos um elemento que satisfaça uma condição por possuir as propriedades adequadas para determinado conjunto ou função por exemplo O símbolo é utilizado em notações para representar o termo existe e contribuindo para que uma definição possa ser escrita com a maior proporção de linguagem simbólica ao invés de linguagem natural É comum que proposições como existe determinado valor pertencente aos números inteiros que é maior que zero possam ser reescritas com linguagem simbólica de forma a manter o propósito e reduzir redundâncias Utilizando a linguagem simbólica temos x N x 0 Pelas duas formas é clara a ideia de que certamente há pelo menos um valor inteiro maior que zero no conjunto dos números naturais Outro quantificador importante se chama para todo e possui sentido de que qualquer elemento de um conjunto ou todo elemento de um conjunto atende a uma determinada proposição 38 O símbolo representa a expressão para todo e é importante frisar sua diferença em relação ao símbolo pois enquanto este representa que em um conjunto existe pelo menos um elemento que atenda uma relação o símbolo significa que todos os elementos do conjunto ao qual se refere o uso do símbolo devem satisfazer a relação proposta Adaptando o exemplo anterior utilizado para o símbolo temos a proposição todos os valores pertencentes aos números inteiros são maiores ou iguais a zero pode ser definido como x N x 0 Da mesma forma as duas proposições em linguagens distintas se referem ao fato de que todo elemento do conjunto dos números naturais é maior ou igual a 0 É possível a utilização do conectivo para uso conjunto dos quantificadores e de forma que proposições elaboradas com este conectivo mudem seu sentido e seus valores lógicos sejam invertidos em determinado ponto da interpretação Uma proposição que diz que não existe número positivo e negativo simultaneamente no conjunto Z dos números inteiros pode ser definida como x Z x é positivo e x é negativo Assim a negação na proposição permite que a mesma seja toda avaliada mas seu valor final seja invertido de verdadeiro para falso e viceversa dependendo da avaliação da proposição Mesmo proposições que se baseiem no símbolo podem ser negadas e terem seu valor lógico invertido ao final como no caso da proposição a Z a 0 A partir da proposição temos a leitura e que nem todo elemento do conjunto dos números inteiros Z é maior que zero Em determinados casos a combinação de quantificadores pode ser também necessária em função de especificidades de proposições em que os elementos referenciados por estas podem ter comportamentos diferenciados uns dos outros É comum o uso de dois diferentes quantificadores em casos nos quais se elaboram proposições com elementos de mais de um conjunto onde haja uma relação entre elementos destes conjuntos Um exemplo é a proposição x y Z x y 0 Ela se refere ao fato de que para qualquer número pertencente ao conjunto de números inteiros certamente existe um número complementar que somado resulta em zero 39 A melhor forma para se compreender este assunto é através de exercícios relacionados como por exemplo solucionar problemas simples de contagem de elementos de conjuntos possibilidades de ocorrências e combinações etc Assuntos complementares a este serão abordados em aulas posteriores a fim de aprofundar alguns dos temas tratados nesta aula como recursividade e análise combinatória 40 AULA 05 Lógica de Predicados A elaboração de sentenças é bastante complexa e para que boas proposições sejam formadas é preciso que certos componentes estejam presentes de forma a contribuir com um sentido completo além da possibilidade de obtenção de valores lógicos verdadeiros ou falsos Proposições são compostas normalmente por símbolos parênteses e conectivos lógicos como itens básicos mas existem também outros componentes utilizáveis como quantificadores vistos na aula 4 e os chamados predicados tema principal desta aula Como já visto os quantificadores são identificados por símbolos como para todo e existe sendo utilizados em proposições que representam relacionamentos entre elementos de conjuntos Os predicados representam outra parte importante de uma proposição pois se referem às propriedades das variáveis utilizadas nas proposições que indicam a forma como os elementos do conjunto domínio são utilizados nas relações Uma forma alternativa para se referir a um predicado não especificado em uma proposição é simplesmente Px e pode ser amplamente utilizado na composição de proposições mais genéricas como xPx ou xPx por exemplo Uma proposição como xx 0 pode resultar verdadeiro ou falso dependendo do conjunto domínio utilizado e este não é especificado na proposição Escrevendo x Zx 0 temos a indicação do uso do conjunto Z dos números inteiros como domínio e sabese que este conjunto possui infinitos números negativos tornando a proposição falsa mas escrevendo x Nx 0 temos um valor lógico verdadeiro devido à indicação do conjuntos N dos números naturais como base para a proposição tendo então valor lógico verdadeiro Segundo Gersting 1995 a interpretação é um termo utilizado na análise de proposições quando algumas situações devem obrigatoriamente ser respeitadas como a existência de um conjunto domínio com pelo menos um elemento a possibilidade de atribuição da propriedade de elementos do domínio nos predicados da proposição e a atribuição de um elemento do domínio em cada símbolo da proposição É importante estar atento à correta estruturação de proposições pois não se pode apenas incluir componentes simbólicos conectivos etc numa proposição sem que sejam respeitadas regras desta construção 42 Geralmente uma proposição é formada na sequência por quantificadores e elementos de um conjunto domínio especificado ou não seguido dos predicados que definem as relações para aplicações de elementos do conjunto domínio e possível obtenção de elementos para um conjunto imagem Conectivos podem ser utilizados para a criação de proposições compostas sendo que cada proposição que esteja na composta também seja formalmente estruturada com quantificadores e predicados além dos demais símbolos A partir do momento em que são incluídos predicados em sentenças estas podem deixar de ser simples proposições avaliáveis como verdadeiras ou falsas e podem ter diferentes interpretações e não serem de resolução tão direta quanto proposições com valor lógico Gersting 1995 separa sentenças formais em proposicionais ou predicativas sendo as primeiras elaboradas com símbolos proposicionais e conectivos lógicos e as outras contendo também predicados e variáveis respectivamente Assim o valor lógico de uma sentença proposicional depende dos valores lógicos dos símbolos utilizados ao passo que sentenças predicativas permitem interpretações diversas em uma quantidade muito maior de variações que possíveis combinações em sentenças proposicionais 43 Quando uma sentença proposicional que resulta verdadeiro em todas as suas possibilidades em uma tabelaverdade ela é dita tautologia e quando o mesmo ocorre em uma sentença predicativa é chamada validade ou seja resulta verdadeiro para qualquer interpretação possível Como as interpretações são mais complexas que tabelasverdade provar que sentenças predicativas possuem sempre valor lógico verdadeiro independentemente da interpretação é bastante complexo e não existe um algoritmo específico para esta finalidade sendo a base para uma prova deste tipo o raciocínio lógico Geralmente é mais fácil tentar descobrir alguma interpretação que resulte em um valor lógico falso que já elimina a validade de uma sentença predicativa que tentar provar que sempre obteremos resultados verdadeiros Uma forma de se aplicar os conceitos dessa unidade é através do aprendizado de uma linguagem de programação apropriada para este tipo de linguagem formal matemática e a linguagem Prolog pode ser um excelente caminho para unir uma prática dos conceitos com o aprendizado de uma nova ferramenta de desenvolvimento A área de Inteligência artificial utiliza muito a lógica de predicados e linguagens de programação relacionadas como a Prolog para criar software com aprendizado de máquina Machine Learning As chamadas tautologias representam sentenças bemformadas contendo proposições que sempre resultam em verdadeiro independentemente da composição de valores aplicados em suas variáveis A composição de tabelasverdade em tautologias sempre resulta em valores verdadeiros servindo como mecanismo de prova da veracidade das sentenças 44 A equivalência é um bom indicativo de tautologia pois permite que certas proposições diferentes possam ser provadas como verdadeiras para todas as combinações de valores verdadeiros e falsos possíveis em tabelasverdade Observe a imagem 23 para conhecer algumas equivalências que representam tautologias Imagem 23 Fonte Adaptado de Gersting 1995 1 Propriedades Comutativas A v B B V A ou A B B A 2 Propriedades Associativas A v B v C A v B v C ou A B C A B C 3 Propriedades Distributivas A v B C A v B A v C ou A B v C A B v A C 4 Propriedades de Identidade A v 0 A ou A 1 A 5 Propriedades Complementativas A v A 1 ou A A 0 Considerando A B e C proposições a aplicação de conectivos lógicos de forma adequada assim como todos os demais símbolos utilizados permite que sejam escritas equivalências muito importantes como as comutativas e associativas que determinam que a inversão da ordem das proposições ou a colocação de delimitadores como parênteses ou colchetes em uma sentença não é afetada pelo conectivo lógico 45 Como exemplo temos as operações de soma e multiplicação que mantêm os mesmos resultados mesmo que os números a serem calculados sejam invertidos ao passo que as operações de subtração e divisão não podem ter seus valores invertidos em função da não obtenção dos mesmos resultados indicando a não equivalência Em um novo conceito a chamada lógica de predicados traz que sentenças válidas e bemformadas contêm quantificadores predicados conectivos lógicos e símbolos para agrupamento dos demais componentes Segundo Gersting 1995 com base na ideia de que toda sentença predicativa que seja válida resulte verdadeiro em todas as interpretações possíveis podese definir teoremas que sejam provados por axiomas e regras de inferência Para a lógica de predicados temos os seguintes axiomas indicados na imagem 24 Imagem 24 Fonte Gersting 1995 pág 27 1 P Q P 2 P Q R P Q P R 3 Q P P Q 4 xPx Qx xPx xQx 5 xPx Px ou xPx Pa onde a é uma constante 6 xPx Pt onde t é uma constante ou nome de uma variável ainda não usada no decorrer da demonstração 7 Px xPx ou Pa xPx onde a é uma constante e x não ocorre em Pa 8 xPx xPx Nesses oito axiomas trazidos na imagem N P Q e R representam sentenças predicativas bemformadas com todas as interpretações possíveis verdadeiras equivalentes a tautologias 46 Como são todos válidos é possível observar a validade dos axiomas intuitivamente como no caso do axioma 1 que diz que toda sentença predicativa P aplicável a uma variável x que resulte verdadeiro implica que uma outra sentença predicativa Q válida para a mesma variável x implica na mesma sentença predicativa P No segundo axioma temos que uma sentença P implica em uma sentença Q que implica em uma sentença R é equivalente a dizer que a sentença P implica diretamente na sentença R pois P implica em Q e Q implica em R No terceiro axioma temos que se Q derivada de Q implica em P derivada de P pode se dizer que isto implica que P implica em Q lembrando que todas as sentenças P P Q e Q são sentenças predicativas válidas tautologias Gersting 1995 pág 27 afirma que O Axioma 4 diz que se todos os elementos do domínio que tiverem a propriedade P também tiverem a propriedade Q e se todos os elementos do domínio de fato tiverem a propriedade P então todos os elementos do domínio têm a propriedade Q O quinto axioma coloca que se qualquer elemento x de um domínio for aplicável a uma sentença predicativa P obtendo valor lógico verdadeiro também será válida para um elemento x específico ou até um valor constante a O sexto axioma se refere à ideia de que sendo P verdadeiro para x podese determinar um outro nome para a variável desde que este ainda não tenha sido utilizado O axioma sete diz que se P for verdadeiro para certo elemento x de um domínio certamente existe um elemento do domínio para o qual P é verdadeiro Por fim o oitavo axioma se refere à ideia de que se existe um elemento do domínio para o qual P não é verdadeiro automaticamente a sentença que usa o símbolo também é falsa sendo que o sentido contrário da proposição também é válido 47 Uma forma de exercitar os conceitos desta aula é através da prática de resolução de exercícios e sendo assim observe a solução do exercício a seguir Considere Pxy onde x é a capital de y Quais são os valores verdade das proposições abaixo a PSão Paulo São Paulo Verdadeiro b PCuritiba Santa Catarina Falso pois Florianópolis é capital de Santa Catarina e Curitiba do Paraná c PCaxias do Sul Porto Alegre Falso pois Caxias do Sul e Porto Alegre são cidades Porto Alegre é a capital do Rio Grande do Sul d PBrasília Brasil Verdadeiro pois não é especificado se é capital de estado ou país 48 AULA 06 Relações Os conjuntos de elementos podem ter algum tipo de elo que os torne parte do conjunto no entanto também podem ter elos com elementos de outros conjuntos Este tipo de ligação entre elementos é chamado de relação Todo tipo de agrupamento de elementos pode ser considerado um conjunto desde números a elementos mais complexos como pessoas objetos etc Para a tecnologia da informação os conjuntos podem representar agrupamentos de dados desde simples listagens de números até complexas estruturas de bancos de dados Alguns conceitos comuns da matemática podem ser utilizados na lógica para computação como as relações de Ɔ Ȼ C Ø U etc mas os símbolos em si podem ser substituídos por outros adequados ao teclado ou por algoritmos que implementam a relação Além das tradicionais relações matemáticas existem relações diversas entre elementos de quaisquer tipos ligados à matemática computação ou qualquer outro tipo de elemento que se possa imaginar As relações estabelecem elos que são muito importantes para o desenvolvimento de soluções para problemas em geral e principalmente para problemas computacionais pois relações trazem informações como idades de pessoas quantidade de unidades fabricadas de determinado produto máquinas mais ou menos produtivas etc Um tipo de relação importante é chamada de binária e é utilizada para distinguir ordem em pares de elementos de conjuntos A e B em que a relação é representada por A x B que pode ser denotada como R A B Se tivermos como exemplo conjuntos A 1 2 e B 3 4 5 a relação A x B 1 3 1 4 1 5 2 3 2 4 2 5 indica que todos os elementos do conjunto A foram relacionados com todos os elementos do conjunto B Uma representação gráfica para este exemplo é vista na imagem 26 50 Imagem 26 Fonte O autor Imagem 27 Fonte O autor Complementando o conceito de relação dada uma relação R A B o subconjunto de elementos de A que possui relação com elementos de B é chamado de conjunto domínio ou Dom R e o subconjunto dos elementos de B que possui relação com elementos do conjunto A é chamado de conjunto imagem ou Im R Para exemplificar este novo conceito observe o exemplo da imagem 27 baseado nos conjuntos A 1 2 3 4 5 e B 2 4 e sendo R x y A x B x y Dentro do contexto de relações binárias existem tipos distintos que indicam como ocorrem as relações entre elementos de conjuntos e uma delas é a relação do tipo um para um em que um elemento x do conjunto domínio A só pode se relacionar com um elemento y do conjunto imagem B em cada par representado pela relação RA B 51 Imagem 28 Fonte O autor Outra relação é representada como um para muitos em que um elemento x do conjunto domínio A pode se relacionar com mais de um elemento y do conjunto imagem B em cada par representado pela relação RA B Outra variante é a relação do tipo muitos para um em que mais de um elemento x do conjunto domínio A pode se relacionar com um elemento y do conjunto imagem B em cada par representado pela relação RA B Por fim um quarto tipo de relação chamada muitos para muitos em que elementos x do conjunto domínio A podem se relacionar com elementos y do conjunto imagem B em cada par representado pela relação RA B E uma particularidade é que cada elemento x do conjunto A pode se relacionar com um ou mais elementos y do conjunto B que podem estar relacionados com mais de um elemento x do conjunto A A imagem 28 traz alguns exemplos de relações dos quatro tipos considerando conjuntos A 1 2 3 4 5 e B 6 7 8 9 para serem relacionados por relações R1 A B R2 A B R3 A B e R4 A B 52 Imagem 29 Fonte O autor Um conceito adicional para o estudo das relações entre conjuntos se baseia em diferentes formas de se representar as relações podendo aproximar mais as teorias matemáticas da tecnologia da informação Uma forma de se representar relações é indicar quais elementos de um conjunto A se relacionam com quais elementos de um conjunto B em uma típica relação R A B Observe o exemplo da imagem 29 para conhecer esta forma alternativa de representação de relações Após a observação da imagem 29 é importante notar que o preenchimento da tabela de relações deve ser feito de forma que os elementos que se relacionem indiquem linhas e colunas e a posição indicada por eles na matriz da relação R3 seja preenchida com valor 1 ao passo que todas as posições que não representam coordenadas relativas à relações recebem o valor 0 Por meio deste exemplo é fácil perceber como é possível a aplicação destes princípios na TI imaginando todo tipo de solução computacional que possa se beneficiar deste conceito para o desenvolvimento de elementos em jogos aplicações comerciais etc Os valores 1 e 0 são os padrões matemáticos mas é possível buscar variadas formas de utilização desta representação e de preenchimento destas tabelas 53 Uma forma de se praticar estes conceitos é o desenvolvimento de outros exemplos similares de conjuntos e relações entre seus elementos pensando não apenas em números mas substituindoos por elementos diferentes do mundo real como frutas e cores marcas e modelos de produtos etc Os números são utilizados para a elaboração de teoremas matemáticos que possam ser provados mas depois podem ser substituídos por elementos de outros tipos para se adequarem às soluções de problemas desejados da mesma forma que elementos de outros tipos podem ser enumerados para serem aplicados como se vê nos estudos desta aula Outra forma também bastante relacionada à TI baseiase na representação gráfica do que está contido em uma relação R qualquer Com a diferença de que ela não adiciona novos valores como nas tabelas mas indica as relações com setas indicativas para separar os elementos de domínio e imagem quando se utiliza apenas um conjunto de elementos em uma relação por exemplo Os chamados grafos são representações gráficas muito importantes na área de TI não só pela parte gráfica mas também pela quantidade de soluções computacionais que se baseiam pelo menos em parte nos conceitos ligados a este conteúdo Os grafos são basicamente pontos ligados por setas mas esta forma de representação se adéqua perfeitamente ao que está sendo estudado nesta unidade pois numa relação em que os elementos de um conjunto possuem alguma relação com eles mesmos é facilmente representada por meio de um grafo como se pode observar no exemplo da imagem 30 54 Imagem 30 Fonte O autor Neste exemplo da imagem 30 é fácil observar que as setas saem dos elementos 1 2 3 ou 4 indicados na coluna em direção aos elementos 1 2 3 ou 4 indicados na linha superior da matriz da relação R5 Um detalhe importante visível tanto na matriz da relação R5 quanto no grafo gerado por ela é a relação que existe entre o elemento 2 com ele mesmo fazendo com que seja utilizada uma seta que sai do elemento e chega nele mesmo diretamente indicando esta relação em particular A teoria dos grafos será tratada com mais detalhes em aulas posteriores Um conceito complementar importante em relação às relações é que relações aplicadas em elementos de um conjunto A podem possuir algumas características particulares que representam relações especiais identificadas como reflexivas simétricas antissimétricas ou transitivas Uma relação R é reflexiva se a A a R a indicando que um elemento relacionado com ele mesmo seja uma relação válida ao passo que uma relação simétrica é em que a A e b A a R b e b R a indicando que a ordem de dois elementos relacionados não altera o resultado tornandose uma equivalência de a R b b R a Uma relação antissimétrica se a A e b A a R b e b R a são verdadeiras a b indicando que para isto a e b devem representar um mesmo elemento de um conjunto A Por fim uma relação transitiva ocorre se a b c A a R b e b R c a R c indicando que tendo três elementos de um conjunto A se o primeiro se relaciona com o segundo e o segundo com o terceiro automaticamente o primeiro se relaciona com o terceiro 55 Acesse o link Disponível aqui As relações estão presentes em muitas áreas mas uma muito importante para profissionais da área de TI é aquela dos estudos dos bancos de dados relacionais que são utilizados há muitos anos e representam uma grande fatia do mercado A Oracle é uma das empresas que compõem as especializadas nesta área e capazes de desenvolver grandes soluções computacionais para este problema 56 Aula 07 Funções Imagem 32 Fonte O autor Complementando os conceitos de relações tratados na aula 5 as chamadas funções possuem características de relações mas representam um estudo a parte por suas características específicas que são muito importantes para os estudos na área de desenvolvimento de soluções computacionais Estas relações chamadas de funções são comumente associadas a conjuntos de elementos que podem ser aplicados em uma relação para a obtenção de um elemento ou novo conjunto de elementos Cálculos que geram resultados a partir da aplicação de valores prédeterminados são muito comuns em soluções computacionais pois representam um dos fundamentos da TI que é o processo de entrada de dados aplicados a um mecanismo de processamento para a geração de saídas Usando uma notação formal sendo A e B conjuntos não vazios uma função f aplicada de A em B significa que todos os elementos a A está relacionado a apenas um elemento de b B Sendo f uma função de um conjunto A para B temos como notação f A B em que tendo um elemento a A então f a está associado a um único b B Esta notação pode ser graficamente representada como é mostrada na imagem 32 A imagem N traz uma representação simples do que ocorre com os elementos a do conjunto A quando aplicados a uma função f para que elementos b sejam obtidos para compor um conjunto B imagem do conjunto domínio A 58 Imagem 33 Fonte O autor Os termos domínio e imagem são bastante comuns na lógica matemática para a teoria dos conjuntos e assim é importante ter a ideia bem clara de que os elementos de um conjunto A em que é aplicada uma função para a obtenção de elementos b de um conjunto B compõem o chamado domínio de f ou Dom f Em contrapartida os elementos b B obtidos pela função f aplicada a elementos a A fazem parte da chamada imagem de f ou Im f Um termo complementar é contradomínio que se refere ao conjunto B que contém necessariamente os elementos de Im f e pode também conter outros elementos que não sejam resultantes da aplicação de f a em que a A Um exemplo para este conceito poderia se basear nos conjuntos A 1 2 3 e B 1 2 3 4 5 6 e uma função f definida por f a 2a em que a A podemos a partir de então definir os conjuntos domínio e imagem da função como Dom f 1 2 3 e Im f 2 4 6 Observe a imagem 33 para um exemplo que mostra graficamente a composição dos conjuntos Neste diagrama da imagem 33 fica mais fácil a compreensão de como são estruturados os tipos de conjuntos vistos até então em que existe o conjunto A e dele obtémse o conjunto Dom f para que seus elementos sejam aplicados à função f a 1 2 3 em que a A e sejam obtidos os elementos do conjunto Im f 2 4 6 tal que f a b onde b B 59 Imagem 34 Fonte O autor As funções também podem ser representadas de outra forma gráfica sem o uso de diagramas de conjuntos mas como gráficos lineares baseados nos elementos numéricos dos conjuntos domínio e imagem para compor os valores utilizados dos eixos de dados para a indicação de pontos na área do gráfico que podem fornecer informações importantes como evolução dos valores obtidos pela aplicação de números em uma função tendências e probabilidades por exemplo A notação matemática usada para este tipo de gráfico diz que sendo f uma função aplicada em um conjunto A para um conjunto B é possível construir um gráfico por meio do conjunto resultante de pares ordenados dos valores a Dom f e b Im f Usando os mesmos conjuntos A 1 2 3 e B 1 2 3 4 5 6 e uma função f definida por f a 2a onde a A podemos obter outra função g x y x A f e y g x Observe a imagem 34 para visualizar o gráfico resultante da função g x Pela análise do gráfico é possível compreender de forma simples e intuitiva a evolução da função g x obtida a partir dos conjuntos Dom f e Im f Uma linha reta e inclinada que representa uma crescente na evolução dos valores obtidos pela aplicação dos elementos do conjunto A na função F a em que a A 60 Acesse o link Disponível aqui As funções são formas de se realizar processos ou cálculos mais específicos e estes podem ser reutilizados em outras aplicações por serem específicos mas adaptáveis a outras situações ou mudanças de valores a serem aplicados Nesta fonte é possível conhecer algumas funções matemáticas que recebendo valores específicos como entradas geram gráficos bastante conhecidos na área de exatas Outro conceito importante relacionado às funções nesta aula é o das funções especiais que são aqueles conceitos que possuem definições bastante específicas que devem ser atendidas por uma função para se adequar a cada categoria Um tipo especial de função é chamada de injetora que possui como requisito ter apenas um elemento de imagem para todo elemento a A sendo assim essa função representada por um diagrama em que apenas uma seta sai de cada elemento a A para um elemento b B O exemplo da imagem 34 serve como exemplo de função injetora pois atende ao requisito fundamental deste tipo de função Um exemplo ligado à TI para este tipo de conjunto é a de nomes ligados a um número de CPF Outro tipo de função especial é chamada de sobrejetora em que uma função f A B se e somente se Im f é igual ao contradomínio ou seja para todo b B existe um elemento relacionado a A Um detalhe neste caso é que não há uma restrição para a quantidade de relações que existam dos elementos de A com elementos de B desde que todos os elementos de B tenham alguma relação com um elemento de A Como exemplo suponhamos conjuntos A 1 2 3 4 5 e B 6 7 8 9 e para todo b B existe a A fa b Esta relação específica pode ser ilustrada por um diagrama como o contido na imagem 35 61 Imagem 35 Fonte O autor Imagem 36 Fonte O autor É importante reforçar que para atender à regra de uma função sobrejetora a imagem mostra que todos os elementos do conjunto B possuem relação com algum elemento do conjunto A mas os elementos do conjunto domínio podem ter apenas relação com um elemento do conjunto B Um exemplo voltado a dados para TI seria em um controle escolar de alunos de educação infantil ligados ao único professor ao qual podem estar vinculados em sua turma e cada turma podendo ter um ou mais alunos Outro tipo especial de função é chamada de bijetora se ela atender aos requisitos de uma função injetora e sobrejetora simultaneamente e para isto tendo conjuntos A 1 2 3 4 5 e B 6 7 8 9 e para todo b B existe apenas um a A fa b Assim temos resumidamente que ambos os conjuntos A e B devem conter uma mesma quantidade de elementos e cada elemento a A está relacionado a apenas uma b B e viceversa Observe a imagem 36 com uma ilustração deste conceito 62 Imagem 37 Fonte O autor Aplicações práticas na área de TI envolvendo este tipo de função bijetora estão ligados a bases de dados que devem possuir ligações completas e sem repetições como no caso em que duas bases tenham como um dos dados fundamentais números de CPF nas duas bases e estes sejam utilizados para referenciar os demais dados cadastrados entre as duas bases sabendo que em ambas deve existir uma quantidade igual de registros associados um para cada número de CPF Outro tipo especial e amplamente utilizável na área de TI se chama função composta em que com base nas funções f A B tal que f a b em que a A e b B Também temos uma segunda função g B C tal que g b c onde b B e c C A partir destas definições de funções é possível definir uma função complexa g o f a g f a tal que a A Observe a imagem 37 que traz uma ilustração da composição das funções para que sejam utilizadas seguidamente É preciso respeitar algumas considerações para este tipo de função como a de que g o f de A em C precisa que o conjunto Im f seja subconjunto de Dom g pois senão elementos podem não ser aplicados à função e operações deixarem de ser efetuadas Outra consideração importante é que g o f gera um conjunto diferente de f o g e por isto não existe a ideia da comutatividade que se baseia na ideia de que invertendo a ordem de execução das funções não se altera o resultado A comutatividade ocorre por exemplo no cálculo da multiplicação em que 2 x 3 3 x 2 mas não ocorre na subtração em que 2 3 não é igual a 3 2 Na prática é bastante comum o uso deste recurso em soluções computacionais em que os resultados obtidos por uma função alimentam uma ou mais outras funções ou até ela mesma para dar sequência aos processos da execução de softwares 63 Por fim existe uma função especial chamada inversa que permite que seja possível fazer o caminho inverso da relação de uma função em que geralmente temos f a b onde a A e b B Mas pode ser necessário que a partir do valor de b seja necessária a descoberta do valor a Isto é possível em casos em que temos conversões de valores entre conjuntos e haja uma regra reversível de processamento da função que possa ser utilizada para se obter o elemento do conjunto domínio a partir de um elemento do conjunto imagem Para que isto seja possível cada elemento b B esteja associado a apenas um elemento a A em que f a b Assim é preciso que seja garantido que cada elemento de B se relacione com apenas um elemento de A concluindose então que esta função inversa só é aplicável em funções que também sejam bijetoras injetoras e sobrejetoras ao mesmo tempo Conversões de moedas e unidades de medida são exemplos comuns de aplicações para soluções de problemas computacionais além de muitas outras aplicações que podem ser utilizadas com base neste tipo de função Uma excelente forma de aplicar os conceitos de funções estudados nesta aula é na programação em uma linguagem que permita o uso de funções ou de algoritmos organizados em funções Para uma melhor experiência em termos de aprendizado duplo da matemática e prática da programação é por meio do desenvolvimento de algoritmos ou softwares para realização de cálculos variados organizandoos em funções separadas que possam ser executadas a partir de um menu de opções por exemplo 64 Aula 08 Indução Matemática A demonstração de provas para argumentos formais pode ser realizada de várias formas utilizando técnicas como por demonstração direta por contraposição ou por absurdo Uma técnica bastante relevante para a área de tecnologia da informação é chamada de indução Esta técnica trabalha com a ideia de que a partir de proposições contidas num argumento podese trabalhar com a ideia de que o princípio básico da indução é uma proposição condicional diz que uma proposição Pn seja verdadeira para qualquer valor de n dentro de conjunto específico como N ou Z por exemplo Com isto uma boa aplicação deste método é a prova de que qualquer número de um conjunto específico aplicado em uma proposição Pn resulte em verdadeiro Como exemplo podese imaginar uma situação em que 0 seja considerado par e todo número inteiro multiplicado por 2 também seja par pois o resultado destas multiplicações dividido por 2 sempre deve retornar resto zero Observe a imagem 39 a seguir que contém um exemplo de como poderiam ser elaboradas proposições para realizar a demonstração por indução desta situação Imagem 39 Fonte O autor 1 P1 21 é verdadeiro 2 Pn 2n e 2n 2 possui resto 0 é verdadeiro Um segundo princípio de indução 1 P1 é verdade 2 para todo k Pr é verdade para todo r 1 r k Pk1 verdade implica que Pn verdade para todo inteiro positivo n 66 Uma diferença importante entre os princípios citados é que na proposição 2 é preciso provas a relação 2n e 2n 2 resto 0 por meio da aplicação de ao menos um elemento do conjunto domínio ao passo que na proposição é preciso assumir que todos os elementos do conjunto domínio a proposição seja verdadeira O princípio da indução matemática segundo Menezes 2013 indica que sendo Pn uma proposição aplicada a um conjunto A a E N a b e b E N Pn deve ser considerada verdadeira assim como k E A Pk Pk1 e então a E A Pn é verdadeira Podese trabalhar com indução para este princípio da maneira exibida na imagem 40 Imagem 40 Fonte O autor Base de indução Pa Hipótese de indução Pk Passo de indução Pk Pk1 A prova indutiva é uma forma para se demonstrar sentenças verdadeiras com uma base de indução e a partir de um valor k devese supor que Pk também seja válida como hipótese para a indução e depois Pk1 seja o passo para cada etapa da indução Outro princípio da indução matemática diz que sendo pa uma proposição com A a E N a b e b E N por indução temos o que é trazido na imagem 41 67 Imagem 41 Fonte O autor Pa é verdadeira Paratodo k E A Pk Pk1 Então paratodo a E A Pa é verdadeira Temos a partir daí seja Pa uma proposição sobre o conjunto A a E N a b e b E N pode ser escrita de forma equivalente como mostrado na imagem 42 Imagem 42 Fonte O autor Pa é verdadeira Paratodo k E A Pa Pa1 Pk p k 1 Então paratodo a E A PA é verdadeira Este princípio pode ser utilizado em aplicações diversas da área de TI como para provar conceitos relacionados com árvores em algoritmos sendo úteis para situações em que se deseja garantir que um algoritmo trata dados armazenados em estruturas de árvores com segurança e integridade 68 Nem sempre a proposta de uma base e de passos de indução é válida obviamente mas nem sempre é fácil saber quando uma indução está sendo estruturada de forma equivocada ou não É preciso testar a base e os passos de indução para que se tenha provas da assertividade da estrutura elaborada aplicando testes para validação das hipóteses partindo sempre das bases existentes Segue exemplo para análise 1 O número 10 é par e 3 é ímpar 2 logo todo número com dois algarismos é par e todo número com um algarismo é ímpar Este é um exemplo claro de falha pois 11 é ímpar e 2 é par por exemplo na elaboração de uma definição mas nem sempre se pode identificar tão facilmente estas falhas A chamada definição indutiva ou recursiva se baseia na ideia de que existem casos elementares e outros que podem ser tratados pela base de indução e pelo passo de indução em que um passo de indução serve de base para outros posteriores e estes tomam por base o que é definido no caso base A recursividade é muito presente na tecnologia da informação e reduz de maneira muito eficiente a quantidade de linhas de código necessárias para se produzir soluções computacionais devido a sua forma indutiva de funcionamento Um exemplo de recursividade muito utilizado para exemplificar o método é o cálculo do fatorial de um número natural n representado por n e que pode ser facilmente convertido em algoritmo recursivo Observe a forma como se pode definir o cálculo do fatorial ou uma função fatorial para computação na imagem 43 69 Imagem 43 Fonte O autor 1 0 1 2 n n n 1 n0 ou 1 F0 1 2 Fn n Fn1 n0 Analisando as formas como se definiu o cálculo do fatorial na imagem 3 temos nas duas formas o mesmo resultando alterandose apenas detalhes na escrita para que seja ajustada entre uma forma mais voltada à matemática e outra mais própria para desenvolvimento de algoritmos Em ambas a base para a indução seria que partindo de um menor número possível e aceito 0 o fatorial de 0 resulta 1 por convenção Partindo disso podese induzir os próximos passos da recursão aplicando a fórmula que multiplica o valor de n pela aplicação do cálculo a um valor n1 Este passo é repetido sucessivamente até que n1 resulte 0 e se atinja o passo inicial base para o cálculo A partir do momento em que se atinge n10 automaticamente é substituído o processo de chamada de novo passo de indução pelo valor 1 e assim os cálculos serão realmente executados em forma de retornos sucessivos dos passos realizados aplicando os resultados que vão sendo obtidos nos retornos aos passos anteriores até que o passo inicial n seja atingido e um valor final possa ser calculado conforme pode ser observado na imagem 44 70 Imagem 44 Fonte O autor 5 54 543 5432 54321 543210 543211 54321 5432 546 524 120 Pela imagem 44 é possível vermos a aplicação da recursão para o valor 5 no cálculo do fatorial e nele os passos de indução vão sendo aplicados e os passos incrementados a partir de uma nova aplicação do método de cálculo com base no decremento em uma unidade do valor de n a cada novo passo que seja executado Num primeiro passo n5 depois n4 n3 num terceiro passo n2 num quarto passo depois n1 e por fim n0 num último passo em que a convenção resulta 1 e os cálculos vão sendo retomados até a cálculo final de 524 obtendo o resultado final 120 71 A prática de resolução de problemas de indução pode ser adequada para o aprendizado dos conceitos desta aula Para a área de computação a prática do desenvolvimento de soluções relacionadas à recursividade é bastante útil pois é uma aplicação importante para o aprendizado dos conceitos desta aula e uma forma de expandir sua capacidade de propor algoritmos para a solução de problemas computacionais É possível a aplicação desse método de cálculo por indução e recursão em diversas situações sendo aplicável a diversos algoritmos desde cálculos simples como no caso da multiplicação até cálculos de sequências numéricas com características especiais como no caso dos números primos sequência de Fibonacci como se pode observar na imagem 45 Imagem 45 Fonte Gersting 1995 pág 68 F1 1 F2 2 Fn Fn2 Fn1 para n 2 72 Neste cálculo da sequência de Fibonacci mostrado na imagem 45 existem duas bases para a indução e depois a forma como se realizam os passos indutivos para números posteriores aos indicados na base Acesse o link Disponível aqui Um local em que se pode encontrar alguns exemplos de recursividade aplicando conceitos de indução é na plataforma Khan Na fonte indicada é demonstrada a indução para um algoritmo recursivo para o cálculo de potenciação além de outros exemplos 73 Aula 09 Teoria dos Números A aritmética é uma das áreas de pesquisa mais antigas da matemática estudada desde a antiguidade por matemáticos como Pitágoras e Euclides faz parte da chamada matemática pura pela forma como lida com as relações entre com números e a lógica que está relacionada a eles Tornouse tema de relevância para a tecnologia da informação mais especificamente na área de segurança da informação Trata das propriedades relacionadas aos números inteiros do conjunto Z e N e sequências básicas obtidas a partir destes conjuntos como o conjunto dos números pares n N 2n 0 2 4 números ímpares n N 2n1 1 3 5 quadrados perfeitos n N 2n 1 4 9 números primos n N Pn 2 3 5 etc A base para a geração dos conjuntos e da primeira prova formal da ordem dos elementos foram os axiomas de Peano 18581932 que diziam que todo número natural possui apenas um único sucessor também número natural que se dois números naturais tivessem um mesmo sucessor então seriam o mesmo que neste conjunto existe apenas o número 1 como elemento que não é sucessor de nenhum outro e por fim se A um conjunto em que 1 A e se n A n1 A indicando que este conjunto A se refere ao conjunto de números naturais N Assim temos que 1 é o elemento inicial do conjunto dos números naturais N e o próximo elemento é obtido pelo uso do operador que significa próximo pelo fato de que para todos os elementos é adicionada apenas uma unidade dando esta ideia de sequência mais diretamente que uma soma propriamente dita Existem algumas propriedades básicas dos números além da sequência existente entre os elementos do conjunto dos números naturais N e inteiros Z como a adição e a multiplicação que representam funções baseadas em cálculos recorrentes e serão tratadas posteriormente com mais detalhes A ordem dos elementos no conjunto dos números naturais é algo importante e junto desta propriedade existem as propriedades de triconomia em que dois elementos a e b sendo diferentes se a b resultar falso então temos que b a A propriedade da monotonia se refere à ideia de que se o elemento a b então am bn sendo m e n também elementos do conjunto dos números naturais e m n assim como am bn Uma propriedade relevante é a de que entre dois números naturais seguidos não existe outro número natural ou seja a N e b N a b então a b1 Esta propriedade mostra que não existe a possibilidade de que números não inteiros 75 estejam inclusos no conjunto dos números naturais Segundo Burton 1980 dentre as propriedades relativas à teoria dos números um se refere à divisibilidade entre números naturais em que a e b N q r N a qb r e 0 r b ou seja existe número a que é obtido pela multiplicação de um número b por um outro número q somado a um número complementar r que pode ser maior ou igual a zero e menor que o próprio número b Um detalhe importante é que o número b seja obrigatoriamente maior que zero pois qualquer número multiplicado por zero resulta zero impedindo que outros números além de zero possam ser obtidos a partir de zero neste caso Uma definição relevante é a do máximo divisor comum de dois números a b c N pode ser representado pela função c mdc a b Sendo a é divisível por c e b também é divisível por c Um tipo especial de conjunto contendo elementos dos números naturais é o conjunto formado pelos números primos maiores que zero Os elementos deste conjunto possuem uma característica importante que diz que estes números são divisíveis apenas por si mesmos e por 1 76 Os números primos são um ponto importante na teoria dos números em função da particularidade de sua sequência e um tipo de número primo dito relativamente primo em que dois números quaisquer primos pertencentes aos números naturais são primos entre si ou seja com a b N mdc a b 1 sempre Segundo Burton 1980 é possível obter conclusões a partir do que se sabe a respeito da divisibilidade dos números naturais como a relação entre a b c N em que a é divisível por c e b é divisível por c A partir disso se mdc a b 1 então ab também é divisível por c Assim como consequência também é possível afirmar que sendo a b c N a é divisível por bc e mdc a b 1 então a é divisível por c Segundo Burton 1980 esta propriedade é conhecida como lema de Euclides Uma consequência deste lema é que com base nas mesmas variáveis a b e c mdc a b mdc a c 1 e assim concluise que mdc a bc 1 indicando b e c sendo dois números que possuem um máximo divisor em comum com a significa que multiplicados continuam tendo um mdc com a Segundo Burton 1980 a partir dos conceitos vistos podemos avaliar o chamado algoritmo Euclidiano em que para a e b temos rn mdc a b que significa que o último resto não nulo resultante deste algoritmo é o valor do mdc a b Outro tipo de cálculo bastante conhecido na teoria dos números se chama mínimo múltiplo comum mmc e sua função é descobrir o menor valor que possa ser dividido por dois valores a e b N 77 Disciplinas mais conceituais e que se baseiam em teoremas propriedades e definições tendem a dificultar seu entendimento Ajuda supor aplicações mais práticas para alguns conceitos pois assim utilizase estes conceitos na abstração de problemas reais Exemplo Uma indústria siderúrgica fabrica peças usando grandes placas de metal Após cortes nas placas para obtenção de peças inteiras verificouse que três partes de tamanhos relevantes sobraram com os seguintes tamanhos 50 80 e 100 centímetros A partir do conhecimento destas sobras surgiu o interesse em produzir peças de tamanhos iguais para compor um novo produto no portfólio e evitar maiores descartes de partes ainda úteis Qual seria um tamanho apropriado Solução Calcular o MDC entre 50 80 e 100 Decomposição em fatores primos 100 2 2 5 5 80 2 2 2 2 5 50 2 5 5 MDC 50 80 100 2 5 10 Apenas os números que ocorrem em todos os cálculos individuais são usados nesta multiplicação na geração do MDC e consequentemente a descoberta do tamanho ideal a ser cortado para redução de desperdício e maior aproveitamento de peças para uso em um novo produto 78 Segundo Burton 1980 duas propriedades definem o cálculo do mínimo múltiplo comum em que a b N a é múltiplo de m e é múltiplo de m então m é múltiplo tanto de a quanto de b Outra propriedade é a de que se a é múltiplo de c e b também é múltiplo de c c N então c é também múltiplo de m Um grupo especial da teoria dos números é a dos números primos que são definidos como números p N se p 1 p só é divisível por 1 e pelo próprio p Assim podese definir P p N p é primo Segundo a partir desta definição podese dizer então que p P a b N p a p e b 1 ou a 1 e b p indicando a composição dos elementos do conjunto P de números primos Complementarmente o chamado conjunto dos números compostos contêm como elementos todos os números não primos ou seja números a N que podem ser divididos por 1 por a e por algum outro número b N Os números naturais e inteiros possuem algumas propriedades fundamentais bastante importantes e são úteis para obter outras propriedades que vão agregando mais conhecimento matemático na área Tomando por base a b e c números inteiros existem 6 propriedades importantes para as operações de soma e multiplicação A propriedade ab ba ou ab ba é chamada de comutatividade que diz que nestas operações a ordem dos elementos não altera os resultados Outra propriedade importante é abc abc ou abc abc chamada de associatividade que diz que a ordem do cálculo entre operações com um mesmo operador não faz diferença no resultado para estas duas operações 79 Outra propriedade é 0aa e 1a a se referem à existência de um elemento neutro ou nulo para as operações dentro dos números inteiros Também existe a propriedade a 1a e aa aa 0 se referem à propriedade de que existem números complementares a cada número do conjunto dos inteiros que aplicados às duas operações resultam nos elementos nulos da propriedade anterior Existe também a propriedade abc ab ac que é chamada de distributividade e mostra que uma operação de multiplicação aplicada a uma expressão de soma equivale a multiplicar individualmente o valor a com cada um dos números da expressão de soma e por fim a propriedade 0a 0 e se ab 0 então a0 ou b0 Além de propriedades relacionadas com operações matemáticas de soma e multiplicação existem propriedades relacionadas com a ordem dos elementos do conjunto dos números inteiros Uma é se a 0 então a 0 ou a 0 que garante a não nulidade de um elemento a pertencente ao conjunto dos inteiros seja positivo ou negativo Outra propriedade é se ab e bc então ac que garante que se um elemento a é menor que outro b e b menor que outro elemento c verificase então que pela relação de ordem dos elementos do conjunto Z dos inteiros a é menor que c 80 Outra propriedade diz que se ab então ac bc independente do valor de c nulo ou não pois somar um mesmo número a dois outros quaisquer e diferentes do conjunto Z sempre resultará em novos números diferentes Outra propriedade diz que se ab e 0c então ac bc que mostra que na multiplicação ignorandose números negativos e o nulo quaisquer multiplicações de um mesmo número c com outros dois a e b geram dois novos valores que mantém a mesma ordem existente entre os dois números a e b usados na multiplicação Por fim existe a propriedade em que se ab e c0 então bc ac que é similar à propriedade anterior mas por se tratar de valores negativos invertese a relação de ordem dos resultados obtidos comparandoos com os valores originais de a e b Praticar o uso das propriedades é importante para o aprendizado dos conceitos dessa aula Assim uma forma de se exercitar o uso das propriedades na demonstração de igualdades seria usando as propriedades básicas para demonstrar outras propriedades Para demonstrar que ab a b usase as propriedades 11a depois aba abac e por fim 11a novamente Com isto primeiro obtémse ab 1ab 1a 1b a b 81 Aula 10 Somatórias e Produtórias Também existem estruturas que permitem que uma instrução ou conjunto de instruções sejam executadas repetidas vezes de uma forma controlada para que determinadas situações encerrem as repetições se desejado Cálculos matemáticos podem ser realizados por meio da repetição de uma regra por um determinado número de vezes sendo a soma o exemplo mais comum provavelmente Supondo um número n N e n1 seu sucessor temos que uma relação R 1 11 e R n1 R n 1 indica que qualquer número n segue a mesma relação do número 1 para descobrir seu sucessor dentro dos elementos do conjunto N A partir da teoria da sucessão de elementos do conjunto dos números naturais pode se obter uma nova operação com base na sucessão chamada de soma que permite que dois ou mais números do conjunto N possam ser utilizados num cálculo que tem por base o cálculo da sucessão visto Segundo Bertone 2014 n k N n 1 R n e n R k R n k em que sendo n 1 o número sucessor de n e k N k 1 e assim tanto n quanto k são elementos de um mesmo conjunto ordenado de números inteiros podendo ser iguais ou não A operação de soma por ser associativa permite que se afirme que n k 1 n k 1 permitindo que se possa concluir que estando todos os números no mesmo conjunto e este sendo composto de elementos que estão ordenados sequencialmente n k ou n k n 1 e k 1 Importante citar que a soma é uma operação comutativa e assim n k k n sendo esta uma importante propriedade assim como a associatividade pois facilita o uso da operação em aplicações para computação Um importante conceito relacionado com a aplicação da operação de soma é o chamado somatório e utiliza a letra grega letra sigma maiúscula que representa a simples soma de n números inteiros sendo que o número inicial a ser somado pode ser escolhido e n é definido pela indicação do valor final da sequência de números a serem somados Seguindo a notação que serve para indicar além dos valores indicativos de início e fim dos números inteiros a serem aplicados à função específica do somatório observando que esta função pode conter qualquer tipo de operação desejada n12 n2 n 83 Outra propriedade interessante sobre os números naturais se refere à chamada Lei do Cancelamento em que sendo a b c N se a b b c então a c observando que existem casos em que os 3 valores de a b e c podem ser iguais sem prejudicar a propriedade A multiplicação se baseia na ideia da repetição de somas por um determinado número de vezes de forma recursiva até que ao final o resultado da operação seja obtido Assim segundo Bertone 2014 nk k k k k k sendo então k somado com seu mesmo valor n vezes podendo este ser um bom exemplo de aplicação da recursividade Assim como a operação de soma a multiplicação também é comutativa e dois números n e k N multiplicados implicam em nk kn e com isto não importa de o número k é somado n vezes ou o número n é somado k vezes pois o resultado será sempre o mesmo Outra propriedade importante que também está presente na multiplicação é a associatividade em que sejam três números a b e c N abc abc sendo o mesmo resultado obtido independentemente de serem multiplicados primeiro a e b ou b e c 84 A mesma Lei do Cancelamento se aplica na multiplicação em que sendo a b c N se a b b c então a c observando que existem casos em que os 3 valores de a b e c podem ser iguais sem prejudicar a propriedade O chamado produtório utiliza o símbolo da letra grega pi maiúscula para representar multiplicações em que sua notação seria representando sucessivas multiplicações de um valor ou expressão x contadas de 1 a n conforme indicação da notação produtório É possível combinar operações matemáticas em expressões de forma que novas alternativas de processamento de números podem ser realizadas como uma fórmula nn 1 2 utilizada para se calcular a soma dos n primeiros números naturais A elaboração de expressões é bastante útil pois contribui para a solução de problemas mais complexos que necessitem de combinações de diferentes operações e propriedades relacionadas a estas Há várias propriedades interessantes que relacionam as operações de soma e multiplicação entre si como é o caso da distributiva da multiplicação com respeito à adição citada por Bertone 2014 Nela sendo 3 números a b e c N temos que a b c a b a c A comutatividade neste tipo de expressão utilizando os dois tipos de operações também é válida e pode ser utilizada diretamente entre variáveis aplicadas à operadores ou operações realizadas com o uso de parênteses Um exemplo seria partindo de 3 números a b e c N a b c a b a c a c b a c a b ou supondo a2 b3 e c4 teríamos 234 2324 243 2423 Existe também a possibilidade da comutatividade além de expressões contidas entre parênteses em que se supõe que 3 números a b e c N a b c a b a c a b c a c b c ou supondo a2 b3 e c4 teríamos 234 2434 234 2324 n i0 xi 85 Acesse o link Disponível aqui O uso de estruturas de repetição é bastante importante e permite que algoritmos realizem tarefas repetitivas com menos código A escolha adequada entre as opções depende de preferências do programador mas também é influenciada pelo tipo de processamento a ser realizado e da condição para que ocorra Estruturas de repetição são excelentes recursos para o desenvolvimento de algoritmos É importante observar que o tipo de laço contado representado nesta aula pela palavra reservada PARA é uma opção que possui sintaxe que permite que todos os parâmetros colocados definam exatamente a quantidade de iterações a serem realizadas mas é possível ajustar esta opção de laço omitindo partes dos parâmetros e utilizandoos fora do comando PARA de forma a poder controlar a quantidade de iterações a partir dos processos ocorridos durante as iterações O uso dos comandos ENQUANTO FAÇA ou REPITA ATÉ possui a particularidade de terem a diferença da condição colocada no início do laço ou no final variando o controle realizado e tendo assim a possibilidade de ocorrerem ou não iterações no laço 86 Aula 11 Teoria de Grafos Uma cidade europeia chamada Königsberg foi berço de importantes matemáticos como Chistian Goldbach e David Hilbert mas em função de sua particular composição de pontes sobre um rio que isolava ilhas bem ao centro da cidade criouse a ideia da possibilidade ou não de um passeio pela região passando por todas as pontes sem que nenhuma fosse utilizada mais de uma vez e nenhuma rota alternativa fosse utilizada A ideia do passeio era não restringir ponto de início e término do passeio ordem de passagem pelos pontos mas era sempre preciso passar completamente por cada ponte mas este problema aparentemente simples parecia não ter solução à medida que as pessoas tentavam solucionálo A imagem 49 traz uma foto de satélite da cidade de Königsberg nos dias atuais na qual é possível ver alterações geográficas em relação à época da formulação do problema e os círculos indicam as posições das pontes da época Imagem 49 Fonte Adaptada Disponível aqui 88 Imagem 50 Fonte Adaptada A partir das indicações das pontes na imagem 50 podese gerar uma imagem 51 derivada da imagem 50 que indicaria os possíveis caminhos representando os pontos pontos de início e fim do percurso de caminhada através de cada ponte Leonhard Euler um matemático suíço reduziu o problema de forma que todas as partes irrelevantes do passeio fossem eliminadas e apenas os trechos relevantes das pontes fossem considerados em uma possível solução matemática Observe a imagem 50 que traz uma indicação de onde estariam as pontes do problema em relação à época para iniciarmos os estudos do problema Na imagem de fundo são adicionadas formas para simular as posições das pontes originais de forma a permitir a diagramação do problema como fez Euler na época Disponível aqui 89 Imagem 51 Fonte O autor A partir deste diagrama da imagem 51 e eliminando as pontes do diagrama pois já são destacadas pelas arestas ligando os pontos consideremos as arestas os pontos e os pontos áreas de terras por onde se pode acessar um ponto ou saída de alguma das pontes Algumas percepções matemáticas que Euler apreendeu foram que como todo ponto liga dois pontos e estes são a única forma de se locomover entre os pontos exceto os pontos de início e fim do passeio todos os demais possuem a mesma quantidade de ocorrências de chegada e saída do ponto Também percebeu que para cada ponto do diagrama a quantidade de arestas representando pontes deve ser par sendo metade de chegada e metade de saída tendo assim a conclusão de que de cada ponto do diagrama devem sair ao menos duas arestas assim a quantidade total de arestas ligadas aos pontos deve ser par Segundo Bertone 2014 o que foi observado por Euler no diagrama específico de Königsberg e que gera problemas com a resolução do mesmo baseandose nas regras do problema é que no caso das pontes de Königsberg a partir das áreas que representam pontos de chegada ou saída existem ligações apenas com quantidades 90 ímpares de pontes Isso gera a necessidade de que todos os pontos do diagrama sejam ao mesmo tempo chegadas ou saídas para garantir a regra de número par de pontos que sejam chegada ou saída mas isso não é possível tornando insolúvel o problema da forma como foi concebido Este foi o ponto de partida de um conteúdo bastante relevante para a matemática e mais ainda para a informática pois permite que diversos problemas relacionados a elementos e relações entre eles complementam a teoria de conjuntos e relações Não é somente em jogos de tabuleiros em que é possível imaginar grafos para as posições da movimentação de peças de acordo com os possíveis movimentos de cada diferente peça do jogo mas também pode representar posições de elementos sobre planos cartesianos ou seja personagens em um cenário representado por uma matriz São muitas aplicações e todas muito úteis para o mercado e o desenvolvimento de algoritmos para atender demandas por soluções que envolvam problemas que possam ser representados por pontos e arestas com ou sem pesos Os chamados grafos podem ser representados como conjuntos não vazios e finitos de elementos que representam pontos do grafo vértices e que possam estar ou ligados uns aos outros por relações representadas pelas arestas que ligam os vértices Segundo Bertone 2014 podemos definir um conjunto de vértices de um grafo e outro de relações existentes entre elementos do primeiro conjunto Podemos então exemplificar com um conjunto V 1 2 3 4 de vértices e um conjunto A 12 23 34 representando arestas entre vértices do conjunto V e partindo destes dois conjuntos é possível obter um terceiro conjunto G V A para um grafo representativo neste exemplo Observe a imagem 52 para uma ilustração exemplo para o grafo G definido 91 Imagem 52 Fonte O autor Partindo da imagem 52 é possível associar esta forma de representação a diversas situações reais que também podem ser adaptadas como grafos em problemas relacionados à logística como nos meios de transporte trânsito rotas etc Uma consequência das definições de grafos é que é possível calcular o número máximo de arestas possíveis para um conjunto V com n vértices através da fórmula n n12 e assim obter uma importante informação a respeito de um conjunto de vértices que compõem um conjunto relativo a um problema Por exemplo um conjunto V 1 2 3 4 de vértices pode gerar um conjunto A de arestas com no máximo 4412 6 arestas sendo então a 12 13 14 23 24 34 imaginando que não haja vértices ligando um vértice a ele mesmo e não seja aceito mais de uma aresta ligando os mesmos dois vértices Grafos que contêm todas as possíveis arestas entre vértices são chamados de grafo completo Outra definição importante é que um grafo seja ele um conjunto completo ou não possui um conjunto complementar que contém apenas as arestas não utilizadas mesmo que este conjunto seja vazio como complemento de um grafo completo Como exemplo um conjunto V 1 2 3 e um conjunto A 13 são capazes de gerar um grafo não completo G V A e G pode ser dito como um grafo complementar de G onde G V A sendo A 12 23 complemento de A Outra propriedade importante é que o subconjunto B de arestas de um conjunto A de todas as arestas de um grafo mostra quais são os elementos adjacentes de um elemento x V onde y V x y A ou B Ø Esses vértices adjacentes ou vizinhos de um vértice x são importantes em diversas soluções para problemas computacionais de rotas melhores caminhos etc O chamado grau de um vértice se refere à quantidade de vértices adjacentes a x que existem em um grafo e podem também representar importante informação no desenvolvimento de soluções matemáticas e computacionais Observe a imagem 53 para um exemplo de graus em um grafo 92 Imagem 53 Fonte O autor Neste grafo de exemplo da imagem 53 temos cinco vértices com diferentes arestas ligando alguns dos pares possíveis de vértices disponíveis A partir das arestas é possível identificar os vértices adjacentes uns dos outros e também o grau de cada vértice O vértice 1 por exemplo possui arestas ligandoo aos vértices 2 e 5 portanto sabese que este vértice 1 é de grau 2 Da mesma forma é possível identificar os vértices 2 tendo grau 3 o vértice 3 tendo grau 2 o vértice 4 com grau 2 e por fim o vértice 5 com grau 3 A forma gráfica como se representa um grafo pode ter relação com a sua aplicação real como no caso das pontes de Königsberg em função de sua disposição física representada graficamente mas há casos em que a representação gráfica não possui relevância e não altera o significado matemático do mesmo As relações que geram arestas entre vértices são o meio de se gerar grafos e a forma como se representam graficamente pode ser feita de mais de uma maneira dando assim a impressão de serem grafos distintos Mas dois grafos visualmente distintos que sejam baseados nos mesmos vértices e seguindo as mesmas relações são isomorfos como mostrado na imagem 54 93 Imagem 54 Fonte O autor Nos grafos da imagem 54 temos exemplos de grafos isomorfos onde suas aparências visuais são distintas mas são baseados em dois conjuntos V 1 2 3 4 e A 12 23 34 sendo então iguais em suas definições e validade para fins matemáticos e computacionais Acesse o link Disponível aqui Um dos grandes exemplos de aplicação de grafos em algoritmos foi no desenvolvido para o Uber e seu gerenciamento de transporte de pessoas por veículos a terceiros Segue uma análise do caso e da evolução da ideia original do GPS Os grafos podem assumir regras em suas arestas que definem que as mesmas podem seguir apenas em um sentido entre dois vértices tornando o grafo com arestas deste tipo um grafo direcionado Grafos direcionados também são importantes tanto para problemas matemáticos quanto computacionais pois existem situações nas quais é obrigatório que apenas uma direção seja aceita para que se possa seguir de um vértice a outro pelo grafo 94 Imagem 55 Fonte O autor A imagem 55 é uma alteração do exemplo contido na imagem 54 na qual não havia direção indicada nas arestas mas que neste exemplo adiciona esta restrição que impede por exemplo um caminho saindo do vértice 1 e seguindo até o vértice 4 pois não é permitido seguir do vértice 3 para o vértice 4 sendo aceito apenas o sentido contrário Por fim outra informação que pode ser adicionada a um grafo é um peso para cada aresta representando um valor referente a uma espécie de custo relacionado à passagem pela aresta indo de um vértice a outro As duas variações de grafos são importantes para problemas computacionais aqueles relacionados ao transporte em que existem custos de deslocamento entre dois pontos que podem estar localizados em diferentes endereços de uma cidade representar diferentes cidades ou locais mais distantes como países para rotas para navios e aviões 95 Aula 12 Árvores em Grafos Imagem 56 Fonte O autor Após iniciar os estudos na área de grafos e conhecer os conceitos fundamentais de sua estruturação a partir de vértices e arestas baseandose em relações que possam existir entre vértices de um conjunto conhecido é possível avançar na teoria relacionada aos grafos e compreender melhor possíveis utilizações para a área da tecnologia da informação Uma árvore representa um tipo bastante específico de grafo em que este não pode conter ciclos onde arestas ligadas a vértices formem caminhos que podem se tornar repetições infinitas das mesmas relações Para diferenciar grafos cíclicos ou que contenham ciclos observe a imagem 56 Nestes exemplos de grafos da imagem 56 o exemplo da esquerda traz um grafo cíclico que forma um ciclo a partir do uso de todas as suas arestas sendo então um exemplo de grafo totalmente em ciclo enquanto o exemplo da direita traz um grafo que possui parte de sua estrutura formando um ciclo não sendo todo ele cíclico mas tendo parte onde pode ocorrer a repetição de relações seguidamente Esses exemplos não fazem parte do tipo de grafo necessário para os estudos desta unidade pois para a construção de árvores em grafos a estrutura do grafo não pode conter ciclo algum de acordo com as definições de árvores em grafos Além da não existência de ciclos todos os vértices do grafo devem estar ligados a pelo menos uma aresta sendo que existe um vértice considerado raiz que seria uma espécie de ponto de partida para toda a estrutura sendo desta forma particularmente muito importante para estudos na área de TI 97 Imagem 57 Fonte O autor Uma árvore pode ser toda estruturada a partir de uma repetição de processos conhecida como recursividade por isso estes conceitos de árvore e grafos são aplicados em muitas soluções computacionais Observe a imagem 57 para um exemplo de árvore típica em grafo Neste exemplo de grafo da imagem 57 temos uma árvore representando um grafo que não possui ciclos em nenhuma parte de sua composição tendo um vértice raiz inicial de onde se pode alcançar qualquer outro vértice partindo desta raiz passando por arestas existentes na árvore Partindo desse exemplo da imagem 57 temos algumas definições importantes que podem ser aproveitadas como a de que a árvore por ter apenas uma ou duas arestas ligadas a cada vértice pode ser chamada de binária sendo este um tipo de árvore muito importante para algoritmos de organização de dados em TI Também se pode observar que a árvore binária no exemplo da imagem 57 é completa ou seja todas as possibilidades de arestas que podem ser obtidas em uma árvore binária com esta configuração de vértices foram obtidas sendo este tipo de árvore um bom exemplo para compreensão de grafos Em árvores além da raiz representando um vértice inicial existem os demais vértices que compõem a árvore do grafo que caso estejam posicionados como pontas da árvore ou seja exista aresta onde ele seja fim mas a partir deste vértice não haja uma aresta que saia em direção a outro vértice o vértice é chamado de folha 98 Assim podemos então definir mais formalmente uma árvore binária como sendo aquela onde cada vértice também chamado de nó pode ter ligação adjacente com apenas no máximo outros dois nós a partir dele e com um adjacente anterior a ele exceto pela raiz que não possui vértices adjacentes anteriores a ele Os nós adjacentes que saem de um nó qualquer da árvore são definidos como filho à esquerda e filho à direita sendo então esta árvore da imagem 57 completa pois todos os nós que não sejam folhas possuem dois nós filhos e todas as folhas estão em um mesmo nível ou seja partindo da raiz para se chegar a todas as folhas da árvore são utilizadas as mesmas quantidades de passagens por arestas ligadas a nós adjacentes de cada nível da árvore Outra definição importante é a obtenção da quantidade de arestas possíveis em uma árvore binária supondo que esta tenha pelo menos um vértice ou mais indicados por n 1 uma árvore pode ter zero arestas no caso de apenas um nó A partir daí como cada nó a partir da raiz que não seja folha deve ter dois nós adjacentes ligados por arestas cada trio de nós é ligado por duas arestas e à medida que aumenta a quantidade de nós este aumento deve ser proporcional e seguir a regra da estruturação de árvores binárias completas já citadas Então a quantidade de arestas possíveis em uma árvore desse tipo é obtida pela fórmula n1 arestas para n vértices Muito utilizadas em algoritmos para manipulação de dados e seu armazenamento as árvores binárias completas ou não oferecem um excelente mecanismo de organização de dados de forma elaborada pois sua estrutura permite fácil implementação de algoritmos de criação inserção de dados ordenação destes dados e manipulação dos mesmos Um exemplo de algoritmo de busca que utiliza o conceito de função recursiva é mostrado na imagem 58 onde chama a si mesma repetidas vezes até que um determinado critério de parada ocorra sendo neste caso o fim da varredura pelos nós de uma árvore binária X para encontrar determinado elemento Y 99 Imagem 58 Figura 1 Titulo da figura busca árvore X elemento Y se X Ø Árvore vazia se Xno Y Elemento encontrado se Xno Y busca Xesq Y senão busca Xdir Y Através do exemplo da imagem 58 podemos analisar o algoritmo de busca por um elemento Y numa árvore qualquer X onde primeiramente é avaliado se a árvore é vazia retornando esta informação com resposta Outra possibilidade avaliada é do nó da árvore sendo avaliado se durante a busca possui o elemento Y procurado fazendo com que uma mensagem de sucesso na busca seja exibida Caso nenhuma dessas duas possibilidades ocorra entra em funcionamento o mecanismo de recursividade que faz com que a função chame a si mesma direcionando a busca para a esquerda ou direita na sequência dos nós adjacentes a partir da comparação que verifica se o valor do nó atual é maior que o valor do elemento procurado Caso seja maior a busca acaba sendo direcionada à parte esquerda da árvore que contém apenas valores menores que o valor do nó atual senão caso o valor procurado seja maior que o contido no nó atual a busca é direcionada à parte direita da árvore onde estão apenas valores maiores que o do nó atual 100 Acesse o link Disponível aqui Tecnologias modernas como a de localização geográfica como se usa em GPS é baseada na teoria dos grafos Veja uma explicação bastante simples sobre um uso destes conceitos Compreender a forma de uso para estruturas heterogêneas é bastante importante visto que são estruturas heterogêneas e assim aceitam dados de tipos diferentes podendo aumentar rapidamente a complexidade da elaboração de algoritmos utilizando esses tipos de estruturas de dados ainda mais se utilizadas em conjunto com vetores para a criação de lista de registros a ser manipulada em tempos de execução 101 Grafos Eulerianos e Hamiltonianos Imagem 59 Fonte O autor Dando sequência ao estudo de grafos existem dois tipos particulares que serão estudados por terem características interessantes e úteis para aplicações matemáticas e computacionais A partir dos estudos de Euler sobre as pontes de Königsberg um tipo específico de grafo foi definido sendo este baseado na definição de caminho Euleriano onde existe um caminho que passa pelas arestas de um grafo assim como todos os vértices acabam sendo utilizados também no caminho Segundo Macedo 2012 esse percurso chamado Euleriano que passa por todos os vértices e arestas pode existir em grafos também chamados de Eulerianos e este tipo de grafo deve ser um grafo G V E não orientado ou seja não deve haver um sentido específico nas arestas sendo estas de livre sentido para que tanto um vértice quanto outro seja ponto de partida O grafo também deve ser conexo ou seja todo vértice está ligado a pelo menos uma aresta sem que existam vértices soltos sem ligação com outros vértices através de arestas e além disso o grafo para ser Euleriano precisa que todos os seus vértices tenham grau par A imagem 59 traz exemplos de grafos Eulerianos que atendem às especificidades desse tipo de grafo e que pode ter um caminho definido que passe por todas as arestas e vértices uma única vez exceto pelo vértice inicial que pode servir de final também 103 Imagem 60 Fonte O autor Pela imagem 59 é possível observar as características que indicam o grafo do tipo Euleriano pois todos os vértices possuem grau 2 par e estão todos ligados a arestas sendo então conexo o grafo Um problema tradicional como o das pontes de Königsberg poderia ter solução se o mesmo fosse Euleriano ou seja tendo vértices de grau par apenas e não uns graus ímpares como no problema original onde os vértices possuem graus três e cinco ferindo a regra básica de um grafo Euleriano O que podemos observar na representação do problema das pontes na imagem 60 Outro tipo de grafo particularmente interessante se chama Hamiltoniano em homenagem a Sir William Rowan Hamilton cuja definição também é facilmente descrita sendo grafos que possuem ciclos que incluem todos os vértices do conjunto V formador do grafo 104 Imagem 61 Fonte O autor Grafos como o exibido na imagem 61 trazem um típico grafo Hamiltoniano onde existe um ciclo que permite que todos os vértices sejam visitados saindo de um dos vértices e retornando a ele ao final do ciclo mas todos os demais nós devem ser visitados apenas uma vez O exemplo da imagem 62 a seguir traz grafos Hamiltonianos em que se podem escolher quaisquer dos vértices e partir do mesmo em um ciclo que passe por todos os demais retornando a nó inicial assim como os grafos utilizados como exemplos na imagem 59 que traz mais dois exemplos de grafos Imagem 62 Fonte Macedo 2012 pág 114 adaptado 105 Um dos exemplos mais clássicos de grafo Hamiltoniano e que foi a base do estudo de Sir Hamilton é baseado nessa forma do icosaedro mostrado na imagem 62 mas pode ser aplicado a todos os chamados sólidos platônicos que representam polígonos formados por grafos convexos como pirâmides cubos etc Basicamente então um grafo Hamiltoniano possui ao menos 3 vértices e o grau de todos eles devem ser maiores ou iguais a 2 representando assim matematicamente grafos Hamiltonianos com ciclos O teorema de Dirac elaborado em 1952 pelo matemático Gabriel Andrew Dirac 19251984 diz que um grafo com n 3 vértices os quais possuam grau de pelo menos n2 pode considerar que satisfaz este teorema e garante que um grafo seja Hamiltoniano Outro Teorema para grafos Hamiltonianos foi definida em 1960 por outro matemático chamado Øystein Ore 18991968 que dizia que quaisquer pares de vértices não adjacentes de um grafo com pelo menos 3 vértices se somados seus graus esta soma deve ser maior ou igual ao número de vértices do grafo todo Um terceiro teorema complementar ao dos grafos Hamiltoniano foi elaborado pelos matemáticos Václav Chvátal e John Adrian Bondy em 1976 que partindo do que foi proposto por Ore 1960 que os graus de dois vértices adjacentes somados devem ser maior ou igual à quantidade de vértices total de um grafo concluíram também que um grafo só pode ser Hamiltoniano se e somente se uma nova aresta for adicionada ligando um par de vértices não adjacentes ao conjunto do grafo este permanece Hamiltoniano Partindo desse teorema foi definido o chamado fecho de um grafo G que se refere a outro grafo FG obtido a partir deste primeiro onde o acréscimo de arestas que liguem pares não adjacentes sendo acrescentados recursivamente até que todas as possibilidades tenham sido acrescentadas A ordem da inserção das arestas não tem influência no resultado do conjunto FG e assim é possível a obtenção de apenas um fecho a partir de um grafo observandose que a soma dos graus dos vértices não adjacentes a serem ligados a ser pelo menos a quantidade de vértices do grafo Nos exemplos da imagem 63 é possível observar como as arestas não existentes em um grafo são adicionadas seguindo o proposto pelo teorema de Bondy e Chvátal 106 Fonte O autor Imagem 63 Pelo exemplo da imagem 63 é possível avaliar a forma como o teorema de Bondy e Chvátal pode ser aplicado a um grafo Hamiltoniano mas que não esteja com todas as possíveis arestas ligando vértices não adjacentes Assim a cada etapa indicada na imagem uma nova aresta vai sendo inserida no grafo até que todas as possíveis ligações estejam feitas e não haja mais vértices não adjacentes no grafo É importante deixar claro que nem todos os grafos são Euleriano ou Hamiltonianos e também nem todos os grafos Hamiltonianos atendem ao que é proposto nos teoremas de Dirac Ore ou Bondy e Chvátal sendo estes teoremas que buscam definir casos específicos de grafos O uso de variáveis e outras estruturas internamente a subrotinas é bastante comum mas é preciso lembrar que qualquer estrutura de dados declarada dentro de uma subrotina se torna local a ela Assim é preciso estar ciente de que dados gerados em subrotinas e armazenados em estruturas locais são todos perdidos quando se sai de uma subrotina e retornase ao trecho do algoritmo que chamou a subrotina 107 O Problema do Caixeiro Viajante Imaginemos um caixeiro viajante chamado Zé Pedro O Zé tem clientes em cinco cidades que abreviamos por A B C D e E e ele precisa planejar uma viagem de negócios com a cidade de partida e a cidade de destino final A a cidade onde ele mora em que ele passará por quatro cidades no trajeto O grafo abaixo representa o custo de cada viagem ida ou volta entre cada par de cidades Qual o percurso mais barato para esta viagem do Zé Pedro Em outras palavras qual é o ciclo hamiltoniano optimal isto é cuja soma do peso das arestas é menor no grafo apresentado Veja na tabela Exemplo Zé Pedro o caixeiro viajante Uma forma de resolver o problema do Zé Pedro é usar o método de exaustão em que se calculam os pesos dos 4 24 ciclos hamiltonianos possíveis em k₅ 108 Ciclo hamilt Custo total Ciclo inverso ABCDEA 185 121 174 199 133 812 AEDCBA ABCEDA 185 121 120 199 152 777 ADECBA ABDCEA 185 150 174 120 133 762 AECDBA ABDECA 185 150 199 120 199 773 ACEDBA ABECDA 185 200 120 174 152 831 CDCEBA ABEDCA 185 200 199 174 119 877 ACDEBA ACBDEA 119 121 150 199 133 722 AEDBCA ACBEDA 119 121 200 199 152 791 AEDBCA ACDBEA 119 174 150 200 133 776 ADEBCA ACEBDA 119 120 200 150 152 741 ADBDCA ADBCEA 152 150 121 120 133 676 AECBDA ADCBEA 152 174 121 200 133 780 AEBCDA Verificamos assim que há exatamente dois ciclos optimais o ciclo ADBCEA e o seu inverso o ciclo AECBDA Em qualquer dos casos o Zé Pedro gasta 676 Euros na sua viagem e esta é a melhor solução 109 Acesse o link Disponível aqui O uso de funções em programação é muito comum e a estruturação de código em funções é inclusive foco de uma forma de programação que se baseia na implementação de funções para todas as aplicabilidades O chamado paradigma de programação funcional trabalha com funções como base de toda a programação assim como nos cálculos matemáticos 110 Fluxos em Redes e Emparelhamentos Algoritmos computacionais são utilizados para diversas finalidades e muitos deles são baseados em conceitos matemáticos para que possam ser definidos e a partir destes soluções computacionais viáveis podem ser implementadas Um dos grandes problemas da tecnologia da informação é justamente como os dados necessários para o processamento em si ocorrem a solução de dois problemas é essencial para que se possa trabalhar com informação armazenamento e comunicação Os grafos podem ser usados para representar de maneira bastante precisa estruturas de comunicação em infraestruturas de TI tendo como base os equipamentos capazes de emitir ou receber sinais como vértices e os meios de comunicação como arestas sendo estes meios com ou sem fio Numa rede de computadores por exemplo um grafo pode indicar todos os equipamentos da rede que tenham alguma função na comunicação como computadores e equipamentos de envio e recepção de sinal Geralmente representamse essas infraestruturas com grafos conexos indicando que todos os equipamentos estejam interligados entre si ou com um ou mais nós principais simulando equipamentos centrais de infraestrutura Mas é possível que o grafo seja desconexo em função da infraestrutura toda de um local por existirem redes isoladas umas das outras por segurança ou falhas na comunicação entre algum equipamento e a rede tornando o nó da rede isolado indicado por não haver uma aresta de conexão Muitas vezes de forma a prever esses problemas de conexão por rompimento de cabos ou falha no alcance de sinal de uma rede sem fio podem ser disponibilizados meios alternativos de comunicação indicados por arestas extras entre dois nós fazendo com que o grafo tenha mais arestas do que o necessário pelas regras básicas de elaboração de grafos conexos Gersting 1995 define que uma articulação é um vértice em um grafo conexo que se removido torna o grafo desconexo sendo que um nó de um grafo ao ser removido faz com que as arestas ligadas a ele e seus nós adjacentes também sejam removidas Articulações não são desejáveis em infraestruturas reais pois representam possíveis falhas de funcionamento e podem ser catastróficas dependendo de quais nós sejam articulações e conhecer os pontos que representam articulações é algo importante 112 em infraestruturas críticas ou saber se determinados pontoschave de uma rede são articulações ou não Em pequenas infraestruturas pode ser uma tarefa simples mas em grandes infraestruturas com tecnologias variadas meios de comunicação distintos e impossibilidade de acesso a todos os nós da rede fisicamente para testes rápidos podese utilizar a teoria dos grafos para auxiliar em verificações diversas da estrutura enxergandoa como um grafo Segundo Gersting 1995 utilizando recursos de busca em grafos podese percorrer todo um grafo sem maiores problemas e um algoritmo pode ser elaborado de forma que arestas vão sendo inseridas em um grafo à medida que o algoritmo de varredura avança e vai encontrando nós ainda não visitados As arestas que são inseridas no grafo gerado e também representam meios de comunicação são chamadas de arestas de árvore e as demais arestas podem ser chamadas de arestas de retorno Observe a imagem 65 para conhecer um possível algoritmo para esta finalidade 113 Imagem 65 ALGORITMO Articulação procedure Articulaçãovar G grafo n vértice var NumÁrvore integer detecta articulações através de uma busca em profundidade a partir de n NumÁrvore 0 na primeira chamada begin marque n como visitado primeira vez que alcança n atribualhe números de árvore e de retorno NumÁrvore NumÁrvore 1 NúmeroDeÁrvoren NumÁrvore NúmeroDeRetornon NúmeroDeÁrvoren for todo vértice x adjacente a n por uma aresta de retorno do if x não foi visitado then begin torne nx uma aresta de árvore ArticulaçãoG x NumÁrvore busca em profundidade está retornando da subárvore de raiz x para o vértice n n é um ponto de articulação a subárvore de raiz x não tem aresta de retorno para algum ancestral de n if NúmeroDeRetornox NúmeroDeÁrvoren then escreva n é uma articulação else ajusta o número de retorno de n NúmeroDeRetornon minNúmeroDeRetornon NúmeroDeRetornox end else aresta nx é uma aresta de retorno ajuste NúmeroDeRetornon NúmeroDeRetornon min NúmeroDeRetornon NúmeroDeÁrvorex end end Fonte Gersting 1995 pág 310 adaptado 114 O algoritmo da imagem 65 traz um mecanismo que a cada vértice n obtido na infraestrutura à medida que a busca em profundidade vai avançando gera um número NumÁrvore que é incrementado em uma unidade a cada novo vértice x descoberto servindo como identificação dos vértices da árvore que vão sendo armazenados em uma estrutura de armazenamento da árvore chamada NúmeroDeÁrvore Outro número NúmeroDeRetorno também é importante na execução do algoritmo que representa um ponto de retorno na árvore que é obtido a partir do menor número de índice de retorno que esteja mais distante partindo do vértice atual n ou dos descendentes do vértice atual na árvore Um chamado fluxo em rede se baseia na teoria dos grafos direcionados onde setas indicam sentidos obrigatórios em arestas que não podem ser desrespeitados e com valores definidos para cada aresta servindo também como recursos para problemas computacionais diversos Esse tipo de estrutura pode ser utilizado em problemas que envolvam limites de capacidade indicados pelos valores das arestas sendo este tipo de problema típico para casos em que se tenha uma capacidade disponível de fluxo por meios representados pelas arestas de um grafo Esta capacidade representa um limite que não pode ser transposto e pode representar por exemplo limites de banda de sinal para internet por meio de comunicação fornecimento de água através de tubulações fornecimento de energia elétrica através de cabeamento etc No caso da internet e da luz é menos comum o direcionamento nos meios pois em geral estes meios permitem transmissão em ambos os sentidos entre os vértices mas no caso da água é mais comum imaginar esta situação de sentido único onde uma tubulação envia água potável e outra tubulação recebe água suja O transporte também é um exemplo de redes capacitadas pois existem vias de mão única com custos associados de consumo de combustível e pedágios sendo ainda possível a elaboração de grafos com parte das arestas direcionadas e parte não direcionada permitindo circulação nos dois sentidos 115 Fonte O autor O controle do fluxo pode ser colocado como um valor junto ao valor padrão da aresta que representa sua capacidade e pode conter uma informação importante sobre proximidade do limite da rede toda parte dela ou pouco fluxo na rede por exemplo Observe a imagem 66 para um exemplo de grafo capacitado e com controle de fluxo Imagem 66 Observando o exemplo da imagem 66 é importante destacar que a capacidade é indicada pelo número à direita nos valores indicados em cada aresta e à esquerda é indicado o valor do fluxo atual que passa pela aresta e por definição o valor do fluxo deve ser sempre menor ou igual ao valor da capacidade Partindo do conceito de rede capacitada é possível imaginar soluções matemáticas e computacionais para problemas como o de fluxo máximo procurando encontrar para cada problema específico a melhor forma de maximizar os fluxos nas arestas respeitando suas capacidades Outro conceito associado aos conceitos de grafos direcionados se refere a emparelhamentos em grafos que representam subconjuntos desses grafos onde qualquer vértice de um grafo G seja ponto de apenas uma aresta em um subconjunto de G Diante desse conceito existe um problema clássico chamado de emparelhamento bipartido onde seja B um grafo bipartido é desejada a obtenção de um emparelhamento 116 Imagem 67 Fonte O autor Grafos bipartidos são aqueles cujos vértices podem ser divididos em dois conjuntos disjuntos V e V tais que toda aresta conecta um vértice em V a um vértice em V e não haja duas arestas quaisquer com vértices em comum Observe o grafo da imagem 67 para um exemplo de emparelhamento para esse tipo de problema Para resolver este problema é preciso que um algoritmo seja implementado de forma que um vértice do grafo G seja escolhido e marcado como já usado e pertencente a um grafo V Em seguida outro vértice não usado do grafo G é escolhido e também indicado como usado mas como pertencente a um conjunto de vértices de um grafo V Assim sucessivamente vão sendo escolhidos vértices do grafo G marcados como usados e associados a um dos grafos V ou V até que não restem mais pares de vértices não escolhidos estando então os vértices separados entre o grafo V e V Nem sempre ocorrerá a situação indicada na imagem 67 em que todos os vértices acabam sendo utilizados na geração dos grafos V e V pois caso haja número ímpar de vértices não haverá possibilidade de que todos os vértices sejam atendidos 117 Parâmetros representam a comunicação entre partes de um algoritmo divididas em subrotinas Esta comunicação é muito importante para que o fluxo de dados que transita entre as subrotinas permita que algoritmos possam dividir o processamento de seus dados em partes Situações como cálculos a serem realizados podem estar em subrotinas diferentes num algoritmo em relação à obtenção dos dados e com a passagem de parâmetros por valor esses dados podem ser enviados a uma subrotina que efetue os cálculos necessários e exiba resultados por exemplo Acesse o link Disponível aqui Os parâmetros se referem a dados esperados por subrotinas para seu processamento mas existe um termo chamado argumento que se confunde com o termo parâmetro Na verdade parâmetro representa o valor esperado pela subrotina e argumento é o dado passado como parâmetro para a subrotina 118 Um exemplo prático de uso da técnica seria a situação em que haja um determinado número de cadeiras fixas para serem utilizados em um local mas por motivos ignorados para tal atividade duas pessoas não possam sentarse sem que haja uma cadeira de intervalo entre duas pessoas para evitar contato visual das atividades desenvolvidas pelas duas pessoas Assim podese imaginar que um grafo contenha as cadeiras utilizadas e outro as que não podem ser utilizadas para distanciamento entre as pessoas obtendose assim dois grafos independentes a partir de um grafo bipartido 119 Probabilidade A estatística é um dos ramos matemáticos mais importantes para a tecnologia da informação nos tempos atuais mas sempre foi uma área de interesse da humanidade estudar números e compreender quais informações poderiam ser obtidas a partir de sua análise A análise combinatória teoria dos números somatório e produtório são assuntos matemáticos relacionados e relevantes que servem de complemento aos estudos da análise de números proporcionados para esta aula O estudo probabilístico com o passar dos tempos foi cada vez mais se tornando relevante e capaz de auxiliar em inúmeras situações do cotidiano humano desde avaliação de riscos em geral associados diretamente ou não à sobrevivência das pessoas como também pode contribuir em tomadas de decisões e estudos que permitiram avanços em diversas áreas com maior segurança a partir da análise de dados e obtenção de probabilidades que trouxessem maior segurança A incerteza é um dos grandes medos do homem na tomada de decisões e os estudos sobre probabilidade podem reduzir esse medo que atrasa ou até impede avanços significativos da humanidade em diversas áreas do conhecimento Desde experimentos aleatórios de resultados não previsíveis a resultados previstos e com boa margem de acerto a partir da avaliação de probabilidades o estudo de dados com o intuito de realizar previsões é antigo e sempre se mostrou uma ferramenta para tentar minimizar dúvidas Segundo Macedo 2012 um experimento aleatório pertence ao conjunto de todos os resultados possíveis chamado de espaço amostral e qualquer subconjunto de um espaço amostral é dito evento Como exemplo temos o caso de um dado que possui um espaço amostral de um a seis faces e como evento podemos ter casos como a probabilidade de um número maior que quatro sair em uma jogada igual a três ou entre um e três Também é possível avaliar em um jogo de par ou ímpar entre duas pessoas a possibilidade de o resultado de uma rodada ser par ou ímpar em um espaço amostral de 10 números que seria por exemplo a contagem dos dedos somados de uma das mãos de cada jogador 121 Estes dois exemplos são ditos escaláveis e podem ser tranquilamente ampliados para mais dados ou mais pessoas jogando par ou ímpar e mesmo assim é possível realizar cálculos e avaliar probabilidades Assim como na teoria de conjuntos os operadores e U são utilizados como intersecção e união entre eventos sendo que a intersecção significa que sendo A e B eventos o evento B ocorrerá apenas se A ocorrer e viceversa tornandoos dependentes um do outro para que possam ocorrer simultaneamente ao passo que na união um evento resultante ocorrerá se ao menos A ocorrer B ocorrer ou ambos Existem casos nos quais as chances de cada elemento ocorrer são iguais mas existem aquelas em que as probabilidades variam A primeira opção chamada de equiprovável seria em casos como o do dado onde todos os seis lados podem ficar virados para cima com a mesma chance ao ser atirado um dado Por outro lado em um estabelecimento comercial como um supermercado as chances de cada cliente ir ao caixa primeiro são variadas pois dependem de variáveis que influenciam o tempo que leva para cada um se dirigir a um caixa e ser atendido Esses tipos de eventos aleatórios são difíceis de prever com exatidão pois não seguem exatamente regras bem definidas para ocorrerem mas existem fenômenos ditos determinísticos que são possíveis de se prever ou até podem ter determinados resultados esperados aumentando muito as chances de um resultado específico acontecer Macedo 2012 cita um conceito elementar da probabilidade em que sendo U um espaço amostral finito e equiprovável e A um evento dentro deste espaço amostral U a chamada probabilidade PA do evento A ocorrer pode ser calculada dividindose o número de elementos de A pelo número de elementos do espaço amostral Assim por mais que seja simples a fórmula a obtenção dos valores do número de elementos de um espaço amostral e do evento podem depender de interpretação e cálculo pois pode ser necessário calcular todas as possibilidades de ocorrências pois podem ser combinações Quando se usam dois dados por exemplo não temos mais 6 alternativas de resultados possíveis ao jogar pois números iguais ou diferentes podem sair em cada dado aumentando as chances de diferentes ocorrências acontecerem 122 Para cada número que saia num dado é preciso pensar que no segundo pode sair qualquer um dos seis números dele como resultado assim já seriam seis opções possíveis de resultados mas este cálculo tem que ser refeito para cada outra face do primeiro dado Desse modo temos que são seis opções do segundo dado para cada face que saia do primeiro dado resultando em 36 combinações distintas de números possíveis Dessa maneira se fosse desejado saber a probabilidade nos dois dados de o resultado ser seis e seis o cálculo se basearia em nU 36 e nA 1 e PA nA NU 136 de chances de ocorrer o resultado seis e seis nos dois dados quando jogados Após a exemplificação de um caso em que não se obtém diretamente os valores para nU e NA é preciso se preparar para quando houver casos assim e uma das teorias mais utilizadas é a da análise combinatória aplicada a problemas de contagem Um dos métodos utilizados na contagem de números para o cálculo de probabilidades é a de definição de arranjos de números onde sendo n e p números naturais e p n o cálculo da quantidade de arranjos ou seja sequências de p elementos distintos em conjuntos de n elementos pode ser calculado com a fórmula para um arranjo Anp n np 123 Um bom exemplo utilizado por Cunha 2017 é a de medalhistas em uma prova de atletismo na qual 8 corredores disputam medalhas de ouro prata e bronze sabendo que em todas as possibilidades 3 corredores ganharam medalhas e 5 não além de que um mesmo atleta não pode ganhar mais de uma medalha Utilizando o princípio de arranjo pois o número de medalhas p é menor que o de corredores n e estes são organizados em grupos de três ganhadores cada um com sua respectiva medalha sem repetições de medalhas ou corredores Aplicando a fórmula temos que p 3 e n 8 calculase Anp 8 8 3 8 5 Simplificando 5 Em 8 temos como restante do cálculo a ser feito 876 336 possibilidades de pódio para a prova Outro conceito importante é o de combinação simples na qual n elementos de um conjunto são organizados de uma maneira diferente dos arranjos pois nos arranjos a ordem e a mudança dos elementos influencia o resultado mas na combinação apenas a mudança de elementos influencia e a ordem não Imagine como exemplo letras utilizadas em placas de carros Mudando a ordem de um mesmo conjunto em uma placa gera outra placa que deve pertencer a outro veículo mas se numa lista de chamada de alunos de uma turma alunos formarem equipes de trabalho a ordem dos nomes dos integrantes de cada equipe não muda a equipe Para o cálculo de combinações utilizase uma nova fórmula Cnp n n p p usando os mesmos termos n e p números naturais da fórmula do arranjo onde p n obtémse a quantidade de subconjuntos de p elementos contidos em um conjunto com n elementos Um exemplo seria a utilização de uma matriz de pontos com 9 pontos em linhas por 9 pontos em colunas para que fossem interligados de 3 em 3 para formar triângulos Neste caso um mesmo subconjunto de 3 pontos em um arranjo formaria três exemplos diferentes de resultados mas triângulos não possuem diferença por qual vértice inicia o mesmo e por isso usase a fórmula da análise combinatória neste caso Neste exemplo teríamos então de acordo com a matriz 9x9 resultando em um total de 81 pontos possíveis para uso na matriz lembrando que destes 3 podem ser utilizados na formação de cada opção de triângulo possível 124 Temos então n 81 e p 3 para serem aplicados na fórmula para combinações Cnp n n p p 81 81 3 3 81 78 3 818079 321 511920 6 85320 possibilidades de elaboração de triângulos neste caso Segundo Macedo 2012 existem algumas propriedades importantes como a probabilidade de um evento impossível ser nula e em um evento certo NA NU A probabilidade de um evento qualquer é um número real entre zero que significa que não há chances de que o evento ocorra até 1 que é a certeza de que este evento ocorrerá Outra propriedade importante é de que uma soma de probabilidades de um evento e seu evento complementar ocorrerem é igual a uma unidade ou seja 1 U e outra propriedade relevante é a e PAB PAPA B sendo A e B conjuntos de elementos distintos Um exemplo seria descobrir dentro de grupos formados por alunos de uma sala de aula a probabilidade de dois alunos X e Y estarem num mesmo grupo Supondo que a turma completa tenha 30 alunos e para uma a atividade imaginada serão formados grupos de 5 alunos exatamente aproveitando que nenhum deles faltou à aula naquele dia Assim temos que n 30 e p 5 com estes dados podemos calcular quantos grupos podem ser formados ao todo independentemente dos alunos X e Y estarem juntos ou não Como os alunos em cada grupo não possuem diferenciação de ordem para gerar novos grupos calculamos pela fórmula da análise combinatória Cnp n n p p 30 305 5 30 25 5 3029282726 54321 142506 possibilidades mas como são 6 grupos no total e este valor seria para o primeiro grupo podemos continuar calculando as probabilidades para os grupos restantes ajustando o raciocínio para cada um dos demais grupos Neste exemplo especificamente é adicionada uma condição de que 2 dos alunos devem estar em um mesmo grupo em cada uma das formações que devam ser consideradas válidas desse jeito mudase a forma de estruturar os dados para o cálculo pois se em cada opção em um dos grupos é preciso que os alunos X e Y estejam juntos como poderíamos então definir os valores de n e p Poderseia pensar que uma resposta teria sido encontrada mas existe a possibilidade da variação de alunos para completarem o grupo dos alunos X e Y assim sendo temos que imaginar as possibilidades para distribuir todos os 28 alunos 125 restantes nas 3 vagas do grupo de X e Y tendo assim n 28 e p 3 Cnp n n p p 28 283 3 282726 321 3276 possibilidades Portanto temos as duas informações necessárias para aplicação da fórmula da proporção nU 142506 e nA 3276 e assim PA nA NU 3276 142506 00229 aproximadamente Este valor é equivalente a cerca de 23 de probabilidade de os dois alunos X e Y estarem juntos em um mesmo grupo dentro do espaço amostral de todas as possibilidades de formação de grupos Acesse o link Disponível aqui Após a apresentação do conceito de recursividade é importante que se exercitem exemplos de código modifiquese cada um para que se obtenham novas alternativas de funções recursivas e assim possa ser compreendido este conceito O chamado aninhamento ou encadeamento de estruturas de controle é um recurso muito útil e acrescenta muitos recursos no desenvolvimento de algoritmos mas também traz um aumento na complexidade de algoritmos que pode confundir iniciantes É importante praticar o desenvolvimento de pequenos algoritmos contendo estruturas de controle variadas para compreender a mecânica dos aninhamentos e como uma estrutura possui influência sobre a outra além de compreender melhor os motivos de ser necessário aninhar estruturas e como definir quais tipos são adequados a cada situação 126 AULA 16 Álgebra Booleana Após ter estudado importantes assuntos como a teoria dos números e a lógica proposicional estes servirão em parte como base nos estudos da álgebra booleana que se propõe a indicar modelos matemáticos envolvendo estas duas áreas da matemática O termo em si já traz uma referência aos valores verdadeiro e falso e a base da teoria envolvendo este tema a ser trabalhado se baseia em tabelaverdade expressões e funções envolvendo valores booleanos tendo forte influência em toda a área de tecnologia da informação que se fundamenta fortemente no trabalho baseado em apenas dois valores como verdadeiro e falso ou ligado e desligado ou 1 e 0 que representam os estados da própria energia elétrica base de todo o funcionamento da TI Assim como foi estudado que existem operações matemáticas como soma e multiplicação que podem ser aplicados a quaisquer números naturais ou reais por exemplo existem operações aplicáveis a conjuntos como união e intersecção que possuem propriedades válidas comuns com as operações matemáticas A comutatividade a associatividade e a distributividade são exemplos de propriedades comuns a essas operações de formas específicas e podem ser empregadas em outras operações aplicáveis a valores booleanos Os operadores conjunção e v disjunção também podem se valer de propriedades como as citadas e alguns exemplos dessas propriedades podem ser observados na imagem 70 que exibe a aplicação de propriedades em proposições baseadas em sentenças bem formadas A B e C 128 Imagem 70 Fonte Gersting 1995 adaptado A v B B v A propriedade comutativa A v B v C A v B v C propriedade associativa A v B C A v B A v C propriedade distributiva A v 0 A propriedade de identidade A v A 1 propriedade complementativa Partindo das propriedades citadas na imagem 70 temos algumas conhecidas de estudos anteriores na disciplina mas temos duas ainda não utilizadas chamadas de identidade que basicamente mostram que um valor conjunto ou sentença aplicado com o número zero ou um conjunto ou sentença vazios respectivamente resultam nos próprios números conjuntos ou sentenças Outra propriedade interessante se chama complementativa que números conjuntos ou sentenças aplicados aos seus valores negativos conjuntos inversos ou negações das sentenças resultam em consequências que se complementam de forma a se tornarem maiores ou nulos dependendo da operação Semelhanças assim permitem que modelos matemáticos ou abstrações possam organizar essas características comuns a mais de uma forma de representação de elementos reais segundo Gersting 1995 Abstrair significa utilizar apenas as características mais relevantes ou comuns a um conjunto de elementos que se deseja modelar ou trazer para a tecnologia da informação tendo assim a possibilidade de criar uma simulação de elementos reais de forma que sejam representados em suas características essenciais mas o mais próximo possível da compreensão de como é o elemento real 129 A modelagem se baseia na lógica de predicados para suas definições formais assim como relações de equivalência e o uso de grafos para modelagem de certos casos e a modelagem feita pela álgebra booleana segue alguns dos princípios de modelagens feitas nesses outros temas estudados Partindo das propriedades listadas na imagem 70 é possível elaborar um exemplo semelhante fundamentandose nas operações básicas que representam a chamada álgebra booleana de soma e subtração segundo Gersting 1995 Examine a imagem 71 para observar a versão alternativa da imagem 70 voltada à exemplificação das mesmas propriedades com base na álgebra booleana Imagem 71 Fonte Gersting 1995 adaptado A B B A propriedade comutativa A B C A B C propriedade associativa A B C A B A C propriedade distributiva A 0 A propriedade de identidade A A 1 propriedade complementativa Importante observar que tanto nos exemplos da imagem 70 quanto nos da imagem 71 alguns operadores podem ser invertidos sem alteração da propriedade como no caso da comutatividade que pode ser representada por A B B A e a associatividade por A B C A B C 130 Outro detalhe relevante que deve ser observado pelo exemplo é o uso de A para representar o complemento de A que com o uso do operador retorna 1 e com o uso do operador retorna 0 por definição As operações base com a álgebra booleana podem ser representadas como tabelas verdade pois envolvem apenas valores 0 e 1 similares ao uso dos valores lógicos falso e verdadeiro respectivamente Dessa maneira observe a imagem 72 para poder avaliar exemplos de uso de tabelasverdade para exemplificar o uso dos operadores de álgebra booleana a serem estudados nesta aula Imagem 72 Fonte Gersting 1995 adaptado 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 0 Por estas tabelasverdade da imagem 72 é possível observar as semelhanças com outros operadores binários já estudados em outras aulas e a forma como os operadores agem sobre os números 0 e 1 funcionam como em outros tipos de elementos já avaliados anteriormente no caso de sentenças e conjuntos Um detalhe importante a ser observado é que os valores 0 e 1 não representam exatamente os números mas sim valores de um conjunto menor que contém apenas 0 e 1 como elementos e as propriedades acabam tendo um comportamento um pouco diferente do que ocorre no conjunto dos inteiros por exemplo 131 Combinando propriedades é possível explicar de que forma 1 1 1 numa álgebra booleana observando a propriedade colocada por Gersting 1995 na imagem 73 onde é explicada a origem do valor 1 obtido pela operação 1 1 Imagem 73 Fonte Gersting 1995 adaptado x x x x 1 propriedade identidade x xx x propriedade complementativa x x x propriedade distributiva x 0 propriedade complementativa x propriedade identidade Para as propriedades da álgebra booleana é possível sem problemas trocar o operador por e 1 por 0 sem perda de validade da propriedade e isto é bastante relevante para a álgebra booleana simplificando a prova de definições com base em uma álgebra booleana Gersting 1995 coloca que um conceito importante é o de isomorfismo em álgebra booleana que se baseia na ideia de que exista uma bijeção que garanta que elementos aplicados a determinadas relações estejam associados a outros elementos mantendo as propriedades fundamentais inalteradas Uma aplicação da álgebra booleana é na teoria de lógica de circuitos em conjunto com a lógica proposicional estudada por Claude Shannon 19162001 chamado de pai da Teoria da Informação 132 Imagem 74 Fonte Gersting 1995 adaptado Ele elaborou uma tese que demonstrava aplicações em lógica de circuitos que tinham como base a álgebra booleana podendo construir relacionamentos numéricos lógicos de todo tipo Nesta lógica a base para aplicações é a energia elétrica e os valores 1 e 0 representam a existência de corrente elétrica fluindo ou não por um meio e esses valores são chamados comumente de alto e baixa respectivamente A transmissão de energia por um meio que pode ser interrompido é a que permite a aplicação desta teoria e fios ligados a chaves que possam interromper a condução de energia servem aos propósitos dos estudos deste tema nesta aula Usando a tabelaverdade da imagem 3 que define operações de álgebra booleana é possível observar o comportamento dos operadores sobre os valores mas também é possível adaptálas para circuitos imaginando chamadas portas lógicas como operadores que resultam nos mesmos valores Observe a imagem 74 para se ter uma ideia de como seriam os circuitos com base em tabelasverdade A porta OR ou representa a soma de fluxos de energia que passam pelo meio e sua lógica funciona de forma que se em pelo menos um dos meios estiver passando corrente a porta energiza o meio adiante dando sequência ao sinal A porta AND também recebe os dois sinais e apenas se as duas entradas forem energizadas permite que a energia siga adiante senão corta o fluxo impedindo que a energia siga pelo meio adiante da porta lógica Por fim a porta lógica de negação NOT apenas inverte o sinal de entrada ou seja se estiver energizada sua entrada impede que a energia siga adiante e caso contrário energiza o meio adiante 133 Os operadores representam portas lógicas que controlam a passagem do fluxo de energia pelo meio de acordo com as combinações de sinais que entram nas portas e a forma como elas funcionam Um detalhe importante é que as portas aceitam que mais de dois sinais cheguem nas portas lógicas dependendo de limites de projeto apenas que servem de base para o desenvolvimento de equipamentos reais normalmente Expressões booleanas são expressões do tipo P Q P Q ou P sendo P e Q expressões booleanas também desse modo expressões combinando estas possibilidades também são expressões booleanas Um exemplo seria P Q P Q que pode ter um circuito desenhado para ilustrar seu funcionamento usando os símbolos utilizados na imagem 74 Para se resolver expressões mais complexas utilizandose de tabelasverdade imagine que cada coluna se refere a uma das expressões base ou expressões com operadores lembrando que existem regras de precedência e símbolos como parênteses que geram prioridades na ordem das operações Observe a imagem 75 para visualizar uma tabelaverdade que serve como solução para a expressão citada como exemplo Imagem 75 Fonte Gersting 1995 adaptado P Q Q P Q PQ P PQP Q 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 A partir da imagem 75 é possível observar que as cores definem etapas do desenvolvimento da tabelaverdade que parte da definição dos valores base para P e Q para em seguida na faixa de colunas de tom azulado desenvolver as operações 134 em ordem de precedência iniciando pela negação ou inversão de Q depois pela operação PQ que utiliza seu resultado para ser operado com P logo em seguida Por fim tendo todas as operações parciais da expressão resolvidas resta realizar a última operação de toda a coluna de valores obtidos até então com Q obtendose o valor final para a expressão na coluna de tom mais escuro de amarelo Acesse o link Disponível aqui É importante ter em mente que os arquivos geralmente possuem nome e extensão sendo que a extensão auxilia na identificação do software que utiliza cada arquivo e assim é interessante que se conheçam extensões mais comuns para que não sejam utilizadas na criação de arquivos de dados para algoritmos criados Imaginar aplicações desenvolvidas para manipular estruturas de dados heterogêneas em quantidade não préestabelecida é um bom tipo de utilidade para o uso de arquivos de texto Estes arquivos podem conter grandes quantidades de linhas e cada linha pode conter os dados de uma estrutura heterogênea organizados de forma a um separador destacar o início e fim de cada dado na linha 135 A manipulação de arquivos de texto é bastante útil e pode agregar uma grande quantidade de outros conceitos estudados ao longo do material como estruturas de controle de fluxo de execução e por isso uma boa forma de se praticar é elaborar algoritmos que gerem dados de tipos variados e que sejam depois armazenados em disco O exemplo da imagem 65 é um exemplo de dados onde estão guardados em um arquivo indicado pela variável AGENDA e que através de uma estrutura de repetição REPITA busca dados em sequência do arquivo para uma estrutura de dados homogênea vetor declarada com um tipo de dados heterogêneos registro Um detalhe a ser observado é que a estrutura de repetição é controlada pelo avanço nas linhas do arquivo com o comando AVANCE e encerra as iterações quando o final do arquivo é atingido com a palavra reservada FDA no comando ATÉ Imagem 65 Exemplo para leitura de dados em arquivos TIPO DADOS VETOR 1100 DE CADASTRO DADOS LISTA INTEIRO I ABRA AGENDA REPITA AVANCE AGENDA COPIE AGENDA LISTA I I I 1 ATÉ FDA AGENDA Fonte O autor 136 Conclusão Após o término dos estudos em diversas áreas matemáticas tendo algumas aplicações diretas na computação e outras nem tanto aparentemente é importante compreender o grau de relação entre as duas áreas A matemática sempre foi a base para o desenvolvimento da área da computação pois sendo uma ciência exata a base da computação se baseia em conceitos matemáticos da física e das demais outras áreas do conhecimento para suas inúmeras aplicações A computação se transformou na mola impulsionadora de evoluções em praticamente todas as áreas do conhecimento humano a partir de suas ferramentas para análise de dados algoritmos de solução de problemas de todo tipo e a otimização dos processos em várias das atividades humanas Seu estudo deve ser mantido pois toda a evolução que ainda ocorrerá na computação provavelmente continuará tendo base nas demais áreas exatas e possuir conhecimentos em áreas afins como a matemática contribui para os melhores profissionais da área da computaçãoSucesso sempre 137 Material Complementar Livro Matemática Discreta para Ciência da Computação Autores Clifford Stein Robert L Drysdale e Kenneth Bogart Editora Pearson Universidades Sinopse Material de base para a matemática discreta contendo temas como árvores de recursão teoria da probabilidade indução contagem criptografia teoria dos números grafos etc Filme PI Ano 1998 Sinopse Max um gênio da computação e matemática vive isolado por problemas com a luz do sol Sem ajuda constrói um supercomputador que permite uma grande descoberta A partir de sua descoberta chega a certas conclusões muito relevantes ao mercado e isto desperta o interesse de grandes investidores Comentário O ponto de interesse do filme é a união dos conhecimentos do personagem em matemática e computação Web Como funciona a Biometria Facial e quais são os usos dessa tecnologia A partir da análise do problema de reconhecimento facial determinamse 80 pontos na face para identificação tendo relação com os conceitos de grafos Acesse o link 138 BERTONE Ana Maria Amarillo Introdução à Teoria dos Números Uberlândia MG UFU 2014 BURTON de David M Elementary Number Theory Revised Printing University of New Hampshire Allyn and Bacon Inc 1980 COPI Irving Marmer Introdução à Lógica Tradução de Álvaro Cabral 2ª ed São Paulo Mestre Jou 1978 CUNHA Francisco Gêvane Muniz Matemática discreta Jânio Kléo de Sousa Castro Fortaleza UABIFCE 2017 GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação LTC Livros Técnicos e Científicos Editora SA Rio de Janeiro 1995 MACEDO Marcos Antônio de Matemática Discreta Coordenação Cassandra Ribeiro Joye Fortaleza UABIFCE 2012 SALMON Wesley C Lógica Tradução de Leonidas Hegenberg Octanny Silveira da Mota 4ª ed Rio de Janeiro Zahar 1978 MENEZES Paulo Blauth Matemática discreta para computação e informática 4ª ed Porto Alegre Bookman 2013 Referências 139