Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Logica inferencia-corrigido, Notas de estudo de Engenharia Elétrica

Mesmo que o arquivo Logica de inferencia, porem, corrigido.

Tipologia: Notas de estudo

2011

Compartilhado em 10/03/2011

leandro-caboatan-10
leandro-caboatan-10 🇧🇷

4.4

(12)

37 documentos

Pré-visualização parcial do texto

Baixe Logica inferencia-corrigido e outras Notas de estudo 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 Provas e Inferência Prova e argumento Prova é um argumento que estabelece a verdade de um teorema. Lógica é usada na análise da validade ou não de um argumento. Um argumento é uma sequência de proposições que pode ser descrito por: p1, p2, . . . , pn / ∴ q onde p1, p2, . . . , pn constituem a hipótese e q é a conclusão. Argumento válido: se p1, p2, . . . , pn são todos V , então q tem também que ser V . Caso contrário, o argumento é inválido ou uma falácia. 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 Provas e Inferência Prova direta Prova Direta: assume-se que a hipótese (p1, p2, . . . , pn) é V , e busca-se validar a conclusão q. Exemplo: provar, por prova direta, que: Para todos inteiros m e n, se m é impar e n é par, então m + n é ímpar. Prova: Por definição de ímpar, existe k1 tal que: m = 2k1 + 1. Por definição de par, existe k2 tal que: n = 2k2. Assim, m + n = 2k1 + 1 + 2k2 = 2(k1 + k2) + 1. Fazendo k = k1 + k2, vem que m + n = 2k + 1 que, por definição, indica que m + n é ímpar. 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 7 Provas e Inferência Prova por contradição Prova por Contradição ou por Refutação: assume-se que a hipótese p é V e que a conclusão q é F . Então, usando p, ¬q e outros axiomas, definições e teoremas provados, deriva-se uma contradição. Contradição é uma proposição na forma (r ∧ ¬r), com r sendo qualquer proposição. Justificativa de equivalência entre a prova direta, p → q, e da prova por contradição, (p ∧ ¬q) → (r ∧ ¬r), pode ser dada por uma tabela verdade. Faça isso como um exercício, mostrando a equivalência: (p → q) ≡ ((p ∧ ¬q) → (r ∧ ¬r)) 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 Provas e Inferência Regras de inferência Regras de inferência são argumentos válidos que são curtos e simples e que podem ser usados na prova de argumentos mais complexos. Modus Ponens: (p → q), p / ∴ q Modus Tollens: (p → q),¬q / ∴ ¬p Adição: p / ∴ p ∨ q Simplificação: p ∧ q / ∴ p , p ∧ q / ∴ q Conjunção: p, q / ∴ p ∧ q Silogismo Hipotético: (p → q), (q → r) / ∴ (p → r) Silogismo Disjuntivo: (p ∨ q),¬p / ∴ q Resolução: (p ∨ q), (¬p ∨ r) / ∴ (q ∨ r) 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 Provas e Inferência Cláusula e Resolução Cláusula é uma sentença proposicional formada pela disjunção de termos que são ou átomos ou negação de átomos. p ∨ ¬q ∨ r ∨ s é uma cláusula (p ∧ t) ∨ ¬q ∨ r ∨ s não é uma cláusula Para o uso da regra de inferência resolução, as sentenças devem ser descritas como cláusulas. 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 Provas e Inferência Uso de Resolução Prove o argumento abaixo, usando a regra de inferência resolução: (a ∨ ¬b ∧ c), ¬(a ∨ d) / ∴ ¬b Prova: primeiro devemos transformar, usando equivalência lógica, o argumento em cláusulas. (a ∨ ¬b ∧ c) ≡ (a ∨ ¬b) ∧ (a ∨ c) (distributiva) ≡ (a ∨ ¬b), (a ∨ c) (simplificação) ¬(a ∨ d) ≡ ¬a ∧ ¬d (De Morgan) ≡ ¬a, ¬d (simplificação) Novo argumento, usando somente cláusulas: (a ∨ ¬b), (a ∨ c), ¬a, ¬d / ∴ ¬b Aplicando resolução em ((a ∨ ¬b), ¬a), derivamos ¬b. CQD 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 Provas e Inferência Exemplo: solução (1) ∀x ,∀y ,∀z Pai(x , y) ∧ (Pai(y , z) ∨ Mae(y , z)) → Avo(x , z) – PREMISSA (2) Pai(Kronos, Zeus) – PREMISSA (3) Pai(Uranus, Kronos) – PREMISSA (4) Pai(Kronos, Zeus) ∨ Mae(Kronos, Zeus) – AD 2 (5) Pai(Uranus, Kronos) ∧ (Pai(Kronos, Zeus) ∨ Mae(Kronos, Zeus)) – CJ 3, 4 (6) Pai(Uranus, Kronos) ∧ (Pai(Kronos, Zeus) ∨ Mae(Kronos, Zeus)) → Avo(Uranus, Zeus) – UN 1, x/Uranus, y/Kronos, z/Zeus (7) Avo(Uranus, Zeus) – MP 5, 6 – CONCLUSÃO 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 Provas e Inferência Indução Matemática Princípio da Indução Matemática: Dada uma função proposicional S(n) e respectivo domínio D de inteiros positivos. Suponha que: (1) S(1) é V. (2) ∀n > 1, se S(n) é V, então S(n + 1) é V. Então, S(n) é V, ∀n ∈ D. Forma Forte da Indução Matemática: Dada uma função proposicional S(n) e domínio D ′ de inteiros positivos > n0. Suponha que: (1) S(n0) é V. (2) ∀n > n0, se S(k) é V, ∀k , n0 6 k < n, então S(n) é V. Então, S(n) é V, ∀n > n0, n, n0 ∈ 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 17 Provas e Inferência Indução Matemática: exemplo Exemplo: suponha que inserimos parênteses e então multiplicamos os n números a1a2 . . . an. Se n = 4, poderíamos colocar parênteses como: (a1a2)(a3a4). Então, multiplicaríamos a1 por a2 e a3 por a4 e, depois, (a1a2) por (a3a4). Note que o número de multiplicações é 3. Prove que se inserirmos parênteses, de qualquer forma possível, e multiplicarmos os n números a1a2 . . . an, efetuaremos n − 1 multiplicações.
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved