Baixe Lógica proposicional e outras Slides em PDF para Engenharia Elétrica, somente na Docsity! PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 1 PCS2214 — Fundamentos de Engenharia de Computação I Lógica Professores: Anarosa Alves Franco Brandão, Anna Helena Reali Costa, Ricardo Luís de Azevedo da Rocha, Ricardo Nakamura PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 2 Sumário 1 Introdução 2 Lógica proposicional Proposições Operadores ¬, ∧, ∨ e Tabela Verdade Operadores→,↔ e Equivalência Propriedades dos operadores 3 Lógica de predicados Predicados e relações Quantificadores 4 Provas e Inferência Prova de teoremas Regras de inferência Indução matemática PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 5 Introdução Aplicações e limitações Exemplo: p : Todos engenheiros usam óculos. q : Pessoas de óculos gostam de computadores. ∴ Todos engenheiros gostam de computadores. A lógica nos garante que se p e q forem verdadeiras, a última declaração também o será. Observe que a conclusão é correta, mas as premissas não são verdadeiras, e nem dizem tudo: Nem todos engenheiros usam óculos. Há pessoas que usam óculos e que não gostam de computadores. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 6 Lógica Proposicional Proposições Uma das lógicas formais mais simples é a lógica proposicional, ou cálculo proposicional. Ela lida com declarações, que são sentenças com valor verdadeiro ou falso, nomeadas por variáveis representadas com letras minúsculas, como: s : Sócrates era mortal. p : Leila matou Odete Roitman. q : 2 + 2 = 5 r : 2 é um número par e primo. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 7 Lógica Proposicional Proposições Na lógica proposicional, apenas o valor verdade das proposições importa, e não o significado. s, p, q e r são chamados símbolos de proposição, variáveis proposicionais, ou simplesmente átomos, e podem assumir os valores verdade V (verdadeiro) ou F (falso). PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 10 Lógica Proposicional Operadores ∧ e ∨ Sejam p e q proposições. A conjunção de p e q, denotada por p ∧ q, é a proposição p e q (“and”). A disjunção de p e q, denotada por p ∨ q, é a proposição p ou q (“or”). Um operador binário sobre um conjunto X associa cada par de elementos em X a um elemento de X. O operador ∧ associa o par de proposições p e q à proposição p ∧ q. Então, ∧ é um operador binário sobre proposições. O operador ∨ também é um operador binário sobre proposições. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 11 Lógica Proposicional Tabela verdade Os valores verdade possíveis de uma proposição podem ser listados exaustivamente em uma tabela verdade. Cada linha é uma combinação de valores verdade dos átomos que compõem cada proposição. As colunas correspondem às proposições e seus valores verdade resultantes. (V é verdadeiro, F é falso.) A tabela verdade define formalmente as proposições p ∧ q e p ∨ q: p q p ∧ q p ∨ q F F F F F V F V V F F V V V V V PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 12 Lógica Proposicional Operador de Negação A negação de p, denotada por ¬p, é a proposição não p. Um operador unário sobre um conjunto X associa cada elemento em X a um elemento de X. O operador ¬ associa a proposição p à proposição ¬p. Então, ¬ é um operador unário sobre proposições. A tabela verdade define formalmente as proposições ¬p: p ¬p F V V F PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 15 Lógica Proposicional Operador de Implicação A tabela verdade define o valor verdade da proposição condicional: p q p → q F F V F V V V F F V V V O operador de implicação→ é um operador binário. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 16 Lógica Proposicional Operador de Implicação Justificativa para p → q ser V quando p é F : Considere a proposição: ∀x ∈ R, se x > 0, então x2 > 0. Todos concordam que ela é verdadeira, certo? Isto é, para qualquer número real que se atribua a x , p → q é V , com p denotando x > 0 e q denotando x2 > 0. Verifique: a proposição é verdadeira para quando, por ex., (i) x = 3, quando então p é V e q também é V ; ou quando (ii) x = −2, quando então p é F (pois −2 > 0 é falso) e q é V (pois (−2)2 > 0 é verdade), ou ainda quando (iii) x = 0, quando então p é F (pois 0 > 0 é falso) e q é F (pois (0)2 > 0 é falso). PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 17 Lógica Proposicional Condição Necessária e Condição Suficiente Uma condição necessária precisa ser verdadeira para que a condicionada também o seja. Ela não garante o outro termo, mas se não for verdadeira, este outro termo também não poderá ser verdadeiro. u : Maria necessita ir à Itália para visitar a Torre de Pisa. Uma condição suficiente basta para garantir uma consequência. Se a condição não for verdadeira, a proposição consequente pode não vir a sê-lo, ou ainda pode se tornar verdadeira por outros meios. v : Se Maria está na Torre Eiffel, então ela está em Paris. (Isto não equivale a “Se Maria está em Paris, então ela está na Torre Eiffel.”) p︸︷︷︸ suficiente para q → q︸︷︷︸ necessária para p PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 20 Lógica Proposicional Ordem dos Operadores É necessário ainda definir a ordem de aplicação, ou precedência dos operadores. A ordem de aplicação dos operadores é (da maior para a menor precedência): ¬, ∧, ∨, →, ↔ Parênteses: “(” e “)”, são utilizados para determinar uma ordem específica de aplicação das operações em uma expressão (como em aritmética). PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 21 Lógica Proposicional Exercícios Considere a seguinte proposição: α : p → q ∧ ¬r ∨ s ↔ t Para p =F, q =V, r =F, s =F e t =V, indique o valor verdade de α. Considere as seguintes frases: Uma condição suficiente para que João faça o biênio da Poli é que ele tenha passado no vestibular. Um código é legível e corresponde a um algoritmo somente se ele estiver bem estruturado e for finito. Defina símbolos para proposições e traduza as frases para sentenças proposicionais. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 22 Lógica Proposicional Equivalência A equivalência, ≡ (ou também⇔), entre duas proposições significa que elas possuem o mesmo valor verdade para cada possível combinação dos seus átomos constituintes. Exemplos: ¬ (a ∨ b) ≡ ¬a ∧ ¬b (lei de De Morgan) a → b ≡ ¬b → ¬a (negação do consequente) a⊕ b ≡ (¬a ∧ b) ∨ (a ∧ ¬b) ≡ (a ∨ b) ∧ (¬a ∨ ¬b) r : s : t : r ′ : s ′ : t ′ : a b ¬a ∧ b a ∧ ¬b r ∨ s a ∨ b ¬a ∨ ¬b r ′ ∧ s ′ F F F F F F V F F V V F V V V V V F F V V V V V V V F F F V F F PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 25 Lógica Proposicional Propriedade de operadores Propriedades distributivas: a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c) Propriedades de absorção: a ∨ (a ∧ b) ≡ a a ∧ (a ∨ b) ≡ a Propriedade de negação: ¬(¬a) ≡ a PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 26 Lógica Proposicional Propriedade de operadores Propriedades de De Morgan: ¬(a ∧ b) ≡ ¬a ∨ ¬b ¬(a ∨ b) ≡ ¬a ∧ ¬b Propriedade da implicação: a → b ≡ ¬a ∨ b PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 27 Lógica Proposicional Exercícios Prove, usando tabela verdade, a equivalência de: (1) ¬(a ∨ b) ≡ ¬a ∧ ¬b (DE MORGAN) (2) a → b ≡ ¬a ∨ b (IMPLICAÇÃO) (3) Usando as propriedades dos operadores, prove a equivalência lógica para a⊕ b: (¬a ∧ b) ∨ (a ∧ ¬b) ≡ (a ∨ b) ∧ (¬a ∨ ¬b) PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 30 Lógica Proposicional Resposta dos exercícios (3) Usando as propriedades dos operadores, prove a equivalência lógica para a⊕ b: (¬a ∧ b) ∨ (a ∧ ¬b) ≡ (a ∨ b) ∧ (¬a ∨ ¬b) Uma prova: (¬a ∧ b) ∨ (a ∧ ¬b) ≡ ¬ (¬ ((¬a ∧ b) ∨ (a ∧ ¬b))) ≡ (negação) ¬ (¬ (¬a ∧ b) ∧ ¬ (a ∧ ¬b)) ≡ (De Morgan ∨) ¬ ((a ∨ ¬b) ∧ (¬a ∨ b)) ≡ (De Morgan ∧) ¬ ((a ∧ ¬a) ∨ (a ∧ b) ∨ (¬b ∧ ¬a) ∨ (¬b ∧ b)) ≡ (distributiva ∧) ¬ (F ∨ (a ∧ b) ∨ (¬b ∧ ¬a) ∨ F) ≡ (conjunção) ¬ ((a ∧ b) ∨ (¬b ∧ ¬a)) ≡ (disjunção – identidade) ¬ (a ∧ b) ∧ ¬ (¬b ∧ ¬a) ≡ (De Morgan ∨) (¬a ∨ ¬b) ∧ (b ∨ a) ≡ (De Morgan ∧) (b ∨ a) ∧ (¬a ∨ ¬b) ≡ (conjunção – comutação) (a ∨ b) ∧ (¬a ∨ ¬b) ≡ (disjunção – comutação) C.Q.D. PCS 2214 LÓGICA PROFESSORES: A. A. F. BRANDÃO A. H. R. COSTA R. L. A. ROCHA R. NAKAMURA VERSÃO 3 JAN/2011 AUTORES: A. H. R. COSTA N. L. WERNECK 31 Referência Bibliográfica Referência Bibliográfica da Aula: Johnsonbaugh, Richard. Discrete mathematics. 6th. ed., Pearson Prentice Hall. Chapter 1: pp.1 – 75.