Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
parte-03-logica-predicados.pdf EDUARDO F R E I R E NAKAMURA I n s / t u t o d e C o m p u t a ç ã o U n i v e r s i d a d e F e d e r a l d o A m a z o n a s n a k a m u r a @ i c o m p . u f a m . e d u . b r Lógica de Predicados Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 1 1Este material baseia-se no material da professora Eulanda Miranda dos Santos (emsantos@icomp.ufam.edu.br) e no livro GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação: um Tratamento Moderno de Matemática Discreta, 5a ed. Livros Técnicos e Científicos, 2004. Todo ser humano é mortal Luiz Inácio é humano ∴ Luiz Inácio é mortal Recapitulando Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 2 Ícone: h>p://www.equiCpz.com/wp-‐content/uploads/2010/06/Warning-‐sign.png Cálculo Proposicional Área que trata da análise de proposições compostas, ligadas por conecCvos (¬, ∧, ∨, →, ↔). Cálculo de predicados Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 3 Ícone: h>p://online.lbcc.edu/pluginfile.php/34778/block_html/content/helpicon.png Cálculo de predicados Área que trata da análise simbólica de predicados e de proposições quanCficadas. O que é um predicado? Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 4 Predicado (dicionário) 1. Qualidade caracterísCca. 2. Atributo, prenda, virtude. 3. Aquilo que se diz do sujeito (gramáCca). Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 5 Predicado (lógica) Um predicado é uma declaração (propriedade) que deve ser verdadeira ou falsa dependendo do valor de suas variáveis. Exemplo Isaac Newton Silva está matriculado em MatemáCca Discreta. Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 6 Sujeito Predicado Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 7 Em lógica de predicados, o predicado transforma-‐se em uma função, que retorna verdadeiro ou falso. Exemplo Isaac Newton Silva está matriculado em MatemáCca Discreta. Ícone: h>p://www.equiCpz.com/wp-‐content/uploads/2010/06/Warning-‐sign.png Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 8 P(x): “x está matriculado em MatemáCca Discreta” Exemplo Isaac Newton Silva está matriculado em MatemáCca Discreta. Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 9 P(x): “x está matriculado em MatemáCca Discreta” x é variável do predicado Predicado Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 10 P(x,y): “ x está matriculado em y ” Um predicado pode ter múlCplas variáveis. Conjunto universo ou domínio de interpretação Os valores das variáveis de predicados são definidos por conjuntos chamados de conjunto universo ou domínio de interpretação. Conjunto universo Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 11 Conjunto verdade Se P(x) é um predicado e x tem domínio D, o conjunto verdade de P(x) é o conjunto de todos elementos de D que tornam P(x) verdadeiro quando subsCtuído por x. O conjunto verdade de P(x) é denotado por { x ∈ D | P(x) } Conjunto verdade Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 12 Conjunto verdade Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 13 Exemplo 1 P(x) : x < 7 e x > 3, e o domínio de x é Z+ Conjunto verdade de P(x): {4,5,6} Exemplo 2 P(x) : x divide 8, e o domínio de x é Z+ Conjunto verdade de P(x): {1,2,4,8} QuanCficadores Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 14 Definição QuanCficadores são palavras/expressões que referem a quanCdades tais como “todos” e “alguns” e indicam para quantos elementos do domínio um dado predicado é verdadeiro. QuanCficadores Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 15 QuanCficador Universal -‐ ∀ u “para todo”, “para cada” e “para qualquer” u ∀x ∈ S, x é mortal, S é o conjunto de todos seres humanos QuanCficador Existencial -‐ ∃ u “existe”, “há pelo menos um”, “existe algum” e “para algum” u ∃x ∈ S, x é estudande de MD, S é o conjunto de todos seres humanos Proposição universal Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 16 Definição Seja Q(x) um predicado e D o domínio de x. Uma proposição universal é uma proposição da forma “(∀x ∈ D), Q(x)” ü A proposição universal é verdadeira sse Q(x) é verdadeiro para todo x em D. ü A proposição universal é falsa sse Q(x) é falso para pelo menos um x em D. ü O valor de x para o qual Q(x) é falso é chamado de contra-‐ exemplo para a proposição universal. Proposição universal Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 17 A proposição ∀x ∈ D, x2 ≥ x, tal que D = {1,2,3} é verdadeira? u SIM! u 12 ≥ 1 u 22 ≥ 2 u 32 ≥ 3 A proposição ∀x ∈ R, x2 ≥ x, é verdadeira? u NÃO u 0,52 = 0,25 < 0,5 Proposição existencial Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 18 Definição Seja Q(x) um predicado e D o domínio de x. Uma proposição existencial é uma proposição da forma “(∃x ∈ D), Q(x)” ü A proposição existencial é verdadeira sse Q(x) é verdadeiro para pelo menos um x em D. ü A proposição existencialé falsa sse Q(x) é falso para todo x em D. Proposição existencial Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 19 A proposição ∃x ∈ Z, x2 = x é verdadeira? u SIM! u 12 = 1 A proposição ∃x ∈ D, x2 = x, tal que D = {5,6,7,8} é verdadeira? u NÃO u 52 = 25 ≠ 5 u 62 = 36 ≠ 6 u 72 = 49 ≠ 7 u 82 = 64 ≠ 8 Proposição condicional universal Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 20 Definição Sejam P(x) e Q(x) predicados. Uma proposição condicional universal tem a forma “∀x, P(x) → Q(x)”. Para todas combinações de valores verdade das variáveis de uma sentença se as premissas são todas verdadeiras então a conclusão também é verdadeira. Tradução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 21 Todo aluno de Computação faz MD Dado alguém, se ele é aluno de Computação, então ele faz MD u P(x): x é um aluno de Computação u Q(x): x faz MD ∀x, P(x) → Q(x) E se disséssemos ∀x, P(x) ∧ Q(x)? O que significa? u Todo mundo é aluno de Computação e faz MD Tradução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 22 Existem algum aluno que faz MD Existe alguém que ele é aluno de Computação e faz MD u P(x): x é um aluno de Computação u Q(x): x faz MD ∃x, P(x) ∧ Q(x) E se disséssemos ∃x, P(x) → Q(x)? u Seria verdadeira se não houvesse aluno de Computação no mundo (universo de discurso) Dados Represente Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta P(x): “x é uma pessoa na sala” I(x): “x fala inglês” F(x): “x fala francês” 1. Todos na sala falam inglês ou francês ∀x, P(x) → [I(x) ∨ F(x)] 2. Alguém na sala ou fala inglês ou francês ∃x, P(x) ∧ (I(x) ∨ F(x))] 23 Tradução Dados Represente Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta A(x): “x é um alunos” I(x): “x é inteligente” M(x): “x gosta de música” 1. Todos alunos são inteligentes ∀x, A(x) → I(x) 2. Existem alunos inteligentes que gostam de música ∃x, A(x) ∧ I(x) ∧ M(x) 24 Tradução Dados Represente Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta F(x): “x é uma fruta” L(y): “y é um legume” D(x,y): “x é mais doce do que y” 1. Alguns legumes são mais doces do que todas as frutas 2. Todas as frutas são mais doces do que todos os legumes 3. Todas as frutas são mais doces do que alguns legumes 25 Tradução Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 26 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Todo engenheiro usa óculos Como negar esta proposição? Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 27 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Nenhum engenheiro usa óculos Ícones obCdos em: 1h>p://www.cliparthut.com/clip-‐arts/127/right-‐or-‐wrong-‐127879.jpg 2h>p://www.clipartbest.com/cliparts/9cp/b8g/9cpb8geKi.png Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 28 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Nenhum engenheiro usa óculos Icones obCdos em: 1h>ps://openclipart.org/image/2400px/svg_to_png/109/molumen-‐red-‐round-‐error-‐ warning-‐icon.png Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 29 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Alguns engenheiros não usam óculos Icones obCdos em: 1h>p://www.cliparthut.com/clip-‐arts/127/right-‐or-‐wrong-‐127879.jpg 2h>p://www.clipartbest.com/cliparts/9cp/b8g/9cpb8geKi.png Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 30 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Alguns engenheiros não usam óculos Icones obCdos em: 1h>ps://openclipart.org/image/2400px/svg_to_png/109/molumen-‐red-‐round-‐error-‐ warning-‐icon.png Negando proposições quanCficadas Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 31 Icones obCdos em: 1h>ps://cdn4.iconfinder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png 2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png Existe pelo menos um engenheiro que não usa óculos Icones obCdos em: 1h>p://www.eatyourcareer.com/wp-‐content/uploads/2013/06/ok-‐256x256.png Teorema Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 32 ¬( ∀x, P(x) ) ≡ ∃x, ¬P(x) ¬( ∃x, P(x) ) ≡ ∀x, ¬P(x) Validade Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 33 O valor verdade de {fs em lógica de predicados depende de sua interpretação, que consiste em u Um conjunto universo não vazio; u A especificação de uma propriedade dos objetos do domínio para cada predicado na expressão; u A atribuição de objetos do domínio para cada variável na expressão Existem infinitas interpretações possíveis para uma dada {f Validade Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 34 Uma {f é dita válida se for verdadeira para todas as interpretações possíveis Não existe um algoritmo para determinar a validade de uma sentença predicaCva u Solução: raciocínio Se encontrarmos pelo menos uma interpretação que torne a sentença falsa, esta não será válida Fbfs válidas? Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 35 SIM SIM NÃO, ex. P(x): x é par ∀x, P(x) → ∃x P(x) ∀x, [P(x) ∧ Q(x)] ↔ ∀x, P(x) ∧ ∀x, Q(x) ∃x, P(x) → ∀y, P(y) Exercícios “The Flash” Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 36 Qual o valor lógico de cada uma das {fs abaixo? O conjunto universo é Z 1. (∀x) (∃y) (x + y = x) 2. (∃y) (∀x) (x + y = x) 3. (∀x) (∃y) (x + y = 0) 4. (∃y) (∀x) (x + y = 0) http://cdn.screenrant.com/wp-content/uploads/The-Flash-Premiere-Questions-Answers.jpg Regras de dedução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 37 As regras de equivalência e de inferência da lógica proposicional ainda são válidas na lógica de predicados Abordagem geral 1. ReCrar os quanCficadores 2. Manipular as {fs sem os quanCficadores 3. Colocar os quanCficadores no lugar Regras de dedução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 38 De Podemos deduzir Lei (∀x) P(x) P(t) onde t é uma variável ou um símbolo constante ParCcularização Universal (∃x) P(x) P(a), onde a é um símbolo constante não uClizado até então ParCcularização Existencial P(x) (∀x) P(x) Generalização Universal P(x) ou P(a), a é constante (∃x) P(x) Generalização Existencial Exemplo 01 Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 39 (∀x) [ P(x) → R(x) ] ∧ ¬R(a) → ¬P(a) 1. ∀x, P(x) → R(x) 2. ¬R(a) 3. P(a) → R(a) 4. ¬P(a) Hipótese 1 Hipótese 2 ParCcularização universal Modus tollens de (2) e (3) Regras de dedução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 40 De Podemos deduzir Lei (∀x) P(x) P(t) onde t é uma variável ou um símbolo constante ParCcularização Universal (∃x) P(x) P(a), onde a é um símbolo constante não uClizado até então ParCcularização Existencial P(x) (∀x) P(x) Generalização Universal P(x) ou P(a), a é constante (∃x) P(x) Generalização Existencial Exemplo 02 Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 41 ∀x, P(x) → ∃x, P(x) 1. ∀x, P(x) 2. P(a) 3. ∃x, P(x) Hipótese 1 ParCcularização universal Generalização existencial Regras de dedução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 42 De Podemos deduzir Lei (∀x) P(x) P(t) onde t é uma variável ou um símbolo constante ParCcularização Universal (∃x) P(x) P(a), onde a é um símbolo constante não uClizado até então ParCcularização Existencial P(x) (∀x) P(x) Generalização Universal P(x) ou P(a), a é constante (∃x) P(x) Generalização Existencial Exemplo 03 Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 43 ∀x, [ P(x) ∧ Q(x) ] → ∀x, P(x) ∧ ∀x, Q(x) 1. ∀x, P(x) ∧ Q(x) 2. P(x) ∧ Q(x) 3. P(x) 4. Q(x) 5. ∀x, P(x) 6. ∀x, Q(x) 7. ∀x, P(x) ∧ ∀x, Q(x) Hipótese 1 ParCcularização universal Conjunção Generalização Universal de (3) Generalização Universal de (4) Conjunção (5) e (6) Prove que cada {fs abaixo é um argumento válido 1. ∀x, P(x) → ∀x, P(x) ∨ Q(x) 2. ∀x, P(x) ∧ ∃x, Q(x) → ∃x, P(x) ∧ Q(x) 3. ∀x, P(x) ∧ ∃x, ¬P(x) → ∃x, Q(x) 4. ∃x, (P(x) → Q(x)) ∧ ∀y, (Q(y) → R(y)) ∧ ∀x, P(x) → ∃x, R(x) Exercícios “The Hulk” Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 44 http://media.ignimgs.com/media/ign/imgs/minisites/topN/comic-book-heroes/9_Hulk.jpg Regras de dedução Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 45 De Podemos deduzir Lei (∀x) P(x) P(t) onde t é uma variável ou um símbolo constante ParCcularização Universal (∃x) P(x) P(a), onde a é um símbolo constante não uClizado até então ParCcularização Existencial P(x) (∀x) P(x) Generalização Universal P(x) ou P(a), a é constante (∃x) P(x) Generalização Existencial __MACOSX/._parte-03-logica-predicados.pdf
Compartilhar