Baixe o app para aproveitar ainda mais
Prévia do material em texto
Matemática Discreta - AULA01 - Prof. Rafael Matos Bibliografia utilizada: ROSEN, K. H. Matemática Discreta e suas aplicações. Introdução e Capítulo I. Tema: Lógica Formal. Conectivos e valores lógicos: Negação, conjunção, disjunção, implicação e bi-implicação. Tabelas-verdade. Notas: - TODO Diagramas de Venn na parte de conjuntos; Matemática discreta é a parte da matemática voltada para o estudo dos objetos discretos (elementos distintos ou desconexos). A partir deste estudo, pode-se chegar a soluções de problemas tais como: ● Descobrir quantas formas de senhas válidas podem existir em um sistema computacional; ● Calcular probabilidades de se ganhar na loteria; ● Identificar e-mails como spam ; ● Descobrir o menor caminho entre duas cidades (por exemplo, por transporte público); ● Verificar quantos passos são necessários para chegar a uma escolha; ● Provar que algoritmos podem resolver corretamente um problema; A razão principal do crescimento da computação discreta é ser o modo como os computadores trabalham com as informações. Sua utilização em algoritmos e lógica de programação é essencial. Lógica formal Lógica é a base de todo raciocínio matemático e também automatizado, sendo aplicado em inteligência artificial e programação de computadores, entre outros. Baseado na estrutura do raciocínio, a Lógica Formal relaciona conceitos e fornece um meio de compor provas de declarações (significado preciso para sentenças matemáticas). Os conceitos são rigorosamente definidos, e as proposições são transformadas em notações simbólicas precisas e sem ambiguidade. Os elementos mais básicos são as proposições, ou seja, uma sentença que declara um fato, o qual pode ser verdadeiro ou falso (e não ambos ao mesmo tempo). Exemplo de proposições: 1. Brasília é a capital do Brasil (verdadeira); 2. Buenos Aires é a capital do Chile (falsa); 3. 1 + 1 = 2 (verdadeira); 4. 2 + 2 = 5 (falsa); Exemplo de não-proposições: 1. Que horas são? (não declara um fato); 2. x + y = z (não é verdadeiro nem falso); Variáveis proposicionais são as que representam proposições, sendo representadas por letras (por convenção, p, q, r, s, ...). Se uma proposição for verdade, seu valor-verdade é indicado por V. Caso seja falsa, indicado por F. Esta área de lógica proposicional foi desenvolvida por Aristóteles, e métodos para produzir novas proposições a partir das já existentes foram discutidas por George Boole. Conectivos e valores lógicos Tabelas verdade Tipo de tabela matemática usada em Lógica para determinar se uma fórmula é válida ou se um conjunto de proposições está correto. Negação Seja p uma proposição. A negação de p é indicada por e a sentença em questão p ou p¬ deve ser lida como "Não é o caso de p " ou "Não p ". Exemplo: "Hoje é domingo." A negação pode ser "Não é o caso de hoje ser domingo" ⇒ ou "Hoje não é domingo." p p¬ F V V F Tabela-Verdade para a negação de uma proposição Conjunção Sejam p e q proposições. A conjunção de p e q é indicada por e a sentença em p ⋀ q questão deve ser lida como "p e q ". A conjunção será verdadeira apenas se ambas forem verdadeiras. p q p ⋀ q F F F F V F V F F V V V Tabela-Verdade para a conjunção de duas proposições Disjunção Disjunção inclusiva Sejam p e q proposições. A disjunção inclusiva de p e q é indicada por e a p ⋁ q sentença em questão deve ser lida como "p ou q ". A disjunção será falsa apenas se ambas forem falsas. p q p ⋁ q F F F F V V V F V V V V Tabela-Verdade para a disjunção inclusiva de duas proposições Disjunção exclusiva Sejam p e q proposições. A disjunção exclusiva de p e q é indicada por e a p ⊕ q sentença em questão deve ser lida como "p ou q ". A disjunção será verdadeira quando apenas uma, e somente uma, das proposições for verdadeira. p q p ⊕ q F F F F V V V F V V V F Tabela-Verdade para a disjunção exclusiva de duas proposições Implicação (ou condicional) Sejam p e q proposições. A proposição condicional deve ser lida como "se p, p → q então q ". A condicional será falsa quando p for verdadeira e q falsa, e será verdadeira nos outros casos. Neste caso, p é chamada hipótese e q a conclusão. p q p → q F F V F V V V F F V V V Tabela-Verdade para a implicação entre duas proposições Obs.: A implicação, em lógica, é diferente das declarações if p then q utilizadas em programação. Bi-implicação (ou equivalência) Sejam p e q proposições. A proposição bicondicional deve ser lida como "p se e p ↔ q somente se q ". A bicondicional será verdadeira quando ambas forem verdadeiras ou ambas forem falsas. p q p ↔ q F F V F V F V F F V V V Tabela-Verdade para a bi-implicação entre duas proposições Prioridade dos Operadores Operador Prioridade ¬ 1 ⋀ 2 ⋁ 3 → 4 ↔ 5 Prioridade dos operadores Exercícios Construir a tabela-verdade de: a) ;p q) p )( ⋁ ¬ → ( ⋀ q b) ;p¬ c) ;p¬ ⋁ q d) ;pq ↔ ¬
Compartilhar