·

Sistemas de Informação ·

Lógica Matemática

Send your question to AI and receive an answer instantly

Ask Question

Preview text

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL ESCOLA POLITÉCNICA Lógica para Computação Prof Michael da Costa Móra Trabalho 1 Lógica Proposicional 20241 Observações o Trabalho deve ser entregue em formato digital word látex ou outro editorprocessador de texto a sua escolha Não serão aceitos trabalhos de manuscritos fotografados Grupos de no máximo 4 alunos 1 Prove as seguintes regras de equivalência utilizando tabelasverdade 𝑝𝑞 𝑝 𝑞 𝐿𝑒𝑖 𝑑𝑒 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛 𝑝 𝑞 𝑝 𝑞 𝐿𝑒𝑖 𝑑𝑒 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 2 Prove as seguintes regras de equivalência utilizando o cálculo de dedução natural Utilize somente as 10 regras elementares apresentadas em aula 𝑝𝑞 𝑝 𝑞 𝐿𝑒𝑖 𝑑𝑒 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛 𝑝 𝑞 𝑝 𝑞 𝐿𝑒𝑖 𝑑𝑒 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝐴𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑖𝑑𝑎𝑑𝑒 3 Formalize as sentenças abaixo usando a lógica sentencial Considere M como Ana é médica P como Bia é médica e G como Carla é médica a Ana Bia e Carla são médicas b Ou Bia e Carla são médicas ou Ana e Carla são médicas c Não é verdade que se Ana é médica e se Carla é médica então Bia não é médica 4 Formalize os seguintes argumentos e prove que os mesmos são válidos usando uma das noções vistas consequência lógica e dedução natural Escolha as sentenças adequadamente indicando o símbolo proposiconal associado a cada sentença a Ou Demócrito acredita na Teoria das Formas ou Platão acredita Platão acredita na Teoria das Formas se e somente se ele não for um atomista e Demócrito é um atomista se e somente se ele não acredita na Teoria das Formas Demócrito é um atomista Portanto Platão não é um atomista b Se eu fumar muito ou beber muito não vou dormir bem e se eu não dormir bem ou não comer bem vou me sentir acabado Se eu me sentir acabado não farei exercícios e não estudarei Eu fumo muito Portanto não estudarei 5 A Dedução Natural é um método de prova semântico ou sintático Justifique sua reposta Pontifícia Universidade Católica do Rio Grande do Sul Escola Politécnica Lógica para a Ciência da Computação P1 Responda TODAS AS QUESTÕES na folha de respostas 1 15 pontos Construa a tabelaverdade para as seguintes fórmulas Indique quais são tautologias contradições ou apenas satisfatíveis a 𝑃 𝑃 𝑄 b 𝑃 𝑃 c 𝑃 𝑄 𝑅 𝑃 𝑅 𝑃 𝑅 2 05 pontos Sabendo que p Cão ladra e q Cão morde qual das fórmulas abaixo representa corretamente em Lógica Proposicional o ditado popular Cão que ladra não morde a 𝑝 𝑞 b 𝑝 𝑞 c 𝑝 𝑞 d 𝑝 𝑞 e Nenhuma das anteriores 3 05 pontos Sabendo que p Há fumaça e q Há fogo qual das fórmulas abaixo representa corretamente em Lógica Proposicional o ditado popular Onde há fumaça há fogo a 𝑝 𝑞 b 𝑞 𝑝 c 𝑝 𝑞 d 𝑝 𝑞 e Nenhuma das anteriores 4 40 pontos Formalize na Lógica Proposicional os seguintes argumentos e prove que os mesmos são válidos usando dedução natural Apresente a definição completa das variáveis proposicionais a Se o tanque é vazio o caro não anda O tanque é vazio Logo o carro não anda b Se o tanque é vazio o caro não anda O caro não anda Logo o tanque é vazio c Se o caro não anda o tanque é vazio ou o motor não funciona O carro não anda O tanque não é vazio Logo o motor não funciona d Não é o caso que o motor não funciona Se o motor funciona o carro anda Logo o carro anda 5 30 ptos Prove que as deduções abaixo são verdadeiras 𝑎 𝑃𝑄 𝑃 𝑄 𝑏 𝑃 𝑄 𝑄 𝑃 6 A Dedução Natural é um método de prova semântico ou sintático Justifique sua reposta 05 ptos Regras Básicas de DN 𝐴 𝐵 𝐴 𝐴 𝐵 𝐵 𝐸 𝐴 B 𝐴 𝐵 𝐼 𝐴 𝐵 𝐴 𝐶 𝐵 𝐶 𝐶 𝐸 𝐴 𝐴 𝐵 𝐴 𝐵 𝐴 𝐼 𝐴 𝐵 𝐴 𝐵 𝐸 𝐴 𝐵 𝐴 𝐵 𝐼 𝐴 𝐵 𝐴 𝐵 𝐴 𝐵 𝐵 𝐴 𝐸 𝐴 𝐵 𝐵 𝐴 𝐴 𝐵 𝐼 𝐴 𝐴 𝐸 𝐴 𝛬 𝐴 𝐼 Trabalho 1 1 a Lei de DeMorgan 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 F F F V V V V V F V F V V F V V V F F V F V V V V V V F F F F V b Lei de DeMorgan 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 𝒑 𝒒 F F F V V V V V F V V F V F F V V F V F F V F V V V V F F F F V c Distributividade 𝑝 𝑞 𝑟 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝑝 𝑞 𝑝 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 F F F F F F F F V F F V V F F F F V F V F V F F F F V F V V V F F F F V V F F F F F F F V V F V V V F V V V V V F V V V F V V V V V V V V V V V d Distributividade 𝑝 𝑞 𝑟 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 𝑝 𝑞 𝑝 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑟 F F F F F F F F V F F V F F F V F V F V F F F V F F V F V V V V V V V V V F F F V V V V V V F V F V V V V V V V F F V V V V V V V V V V V V V V e Associatividade 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑞 𝑟 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 F F F F F F F V F F V F F F F V F V F F F F F V F V V V F V F V V F F F F F F V V F V F F F F V V V F V F F F V V V V V V V V V f Associatividade 𝑝 𝑞 𝑟 𝑝 𝑞 𝑝 𝑞 𝑟 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 𝑝 𝑞 𝑟 F F F F F F F V F F V F V V V V F V F V V V V V F V V V V V V V V F F V V F V V V F V V V V V V V V F V V V V V V V V V V V V V 2 a Lei de DeMorgan Para provar essa equivalência precisamos provar 𝑝 𝑞 𝑝 𝑞 e 𝑝 𝑞 𝑝 𝑞 Vamos começar com a primeira direção 1 𝑝 𝑞 Suposição 2 𝑝 𝑝 Lei do terceiro excluído 3 𝑝 Suposição por redução ao absurdo 4 𝑞 Suposição por redução ao absurdo 5 𝑝 Suposição por redução ao absurdo 6 𝑞 Suposição por redução ao absurdo 7 𝑝 𝑞 Introdução da conjunção de 5 e 6 8 Contradição de 1 e 7 9 𝑞 Conclusão da suposição de 4 10 𝑞 Negativação da conclusão de 9 11 𝑝 𝑞 Introdução da disjunção de 3 e 10 12 𝑝 𝑞 Eliminação da disjunção de 511 Agora vamos para a segunda direção 1 𝑝 𝑞 Suposição 2 𝑝 Suposição por redução ao absurdo 3 𝑝 Suposição por redução ao absurdo 4 𝑞 Suposição por redução ao absurdo 5 𝑝 𝑞 Introdução da conjunção de 2 e 4 6 Contradição de 1 e 5 7 𝑞 Conclusão da suposição de 3 8 𝑞 Dupla negação de 7 9 𝑝 𝑞 Introdução da conjunção de 2 e 8 10 Contradição de 1 e 9 11 𝑝 Conclusão da suposição de 2 12 𝑝 𝑞 Introdução da disjunção de 11 13 𝑝 𝑞 Eliminação da disjunção de 312 Com ambas as direções provadas demonstramos o resultado b Lei de DeMorgan Vamos começar com a primeira direção 1 𝑝 𝑞 Suposição 2 𝑝 Suposição por redução ao absurdo 3 𝑝 𝑞 Introdução da disjunção de 2 4 Contradição de 1 e 3 5 𝑝 Conclusão da suposição de 2 6 𝑞 Suposição por redução ao absurdo 7 𝑝 𝑞 Introdução da disjunção de 6 8 Contradição de 1 e 7 9 𝑞 Conclusão da suposição de 6 10 𝑝 𝑞 Introdução da conjunção de 5 e 9 Agora vamos para a segunda direção 1 𝑝 𝑞 Suposição 2 𝑝 Eliminação da conjunção de 1 3 𝑝 𝑞 Lei da exclusão do terceiro 4 𝑞 Eliminação da conjunção de 1 5 𝑝 𝑞 Lei da exclusão do terceiro 6 Contradição de 2 3 e 4 5 7 𝑝 𝑞 Conclusão da suposição de 1 c Distributividade Começamos com a primeira direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑝 Eliminação da conjunção de 1 3 𝑞 𝑟 Eliminação da conjunção de 1 4 𝑞 Suposição por redução ao absurdo 5 𝑝 𝑞 Introdução da conjunção de 2 e 4 6 𝑝 𝑞 𝑝 𝑟 Introdução da disjunção de 5 7 𝑟 Suposição por redução ao absurdo 8 𝑝 𝑟 Introdução da conjunção de 2 e 7 9 𝑝 𝑞 𝑝 𝑟 Introdução da disjunção de 8 10 𝑝 𝑞 𝑝 𝑟 Eliminação da disjunção de 3 46 79 Agora vamos para a segunda direção 1 𝑝 𝑞 𝑝 𝑟 Suposição 2 𝑝 Suposição por redução ao absurdo 3 𝑞 Suposição por redução ao absurdo 4 𝑝 𝑞 𝑟 Introdução da conjunção de 2 e 3 5 𝑝 Suposição por redução ao absurdo 6 𝑟 Suposição por redução ao absurdo 7 𝑝 𝑞 𝑟 Introdução da conjunção de 5 e 6 8 𝑝 𝑞 𝑟 Eliminação da disjunção de 1 24 57 d Distributividade Vamos começar com a primeira direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑝 Suposição por redução ao absurdo 3 𝑝 𝑞 𝑝 𝑟 Suposição 4 𝑝 𝑞 Eliminação da conjunção de 3 5 𝑝 𝑟 Eliminação da conjunção de 3 6 𝑞 Suposição por redução ao absurdo 7 𝑞 𝑟 Introdução da conjunção de 6 e 7 8 𝑝 𝑞 𝑟 Introdução da disjunção de 2 e 7 9 𝑟 Suposição por redução ao absurdo 10 𝑞 𝑟 Introdução da conjunção de 6 e 9 11 𝑝 𝑞 𝑟 Introdução da disjunção de 2 e 9 12 𝑝 𝑞 𝑟 Eliminação da conjunção de 4 58 911 Agora vamos para a segunda direção 1 𝑝 𝑞 𝑝 𝑟 Suposição 2 𝑝 𝑞 Eliminação da conjunção de 1 3 𝑝 𝑟 Eliminação da conjunção de 1 4 𝑝 Suposição por redução ao absurdo 5 𝑝 𝑞 𝑟 Introdução da disjunção de 4 6 𝑞 𝑟Suposição por redução ao absurdo 7 𝑞 Eliminação da conjunção de 6 8 𝑝 𝑞 Introdução da disjunção de 4 9 𝑟 Eliminação da conjunção de 6 10 𝑝 𝑟 Introdução da disjunção de 4 11 𝑝 𝑞 𝑝 𝑟 Introdução da conjunção de 2 e 3 12 𝑝 𝑞 𝑟 Eliminação da conjunção de 5 68 911 c Associatividade Vamos começar com a primeira direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑝 𝑞 Eliminação da conjunção de 1 3 𝑝 Eliminação da conjunção de 2 4 𝑞 Eliminação da conjunção de 2 5 𝑞 𝑟 Introdução da conjunção de 4 e 1 6 𝑝 𝑞 𝑟 Introdução da conjunção de 3 e 5 Agora vamos para a segunda direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑞 𝑟 Eliminação da conjunção de 1 3 𝑞 Eliminação da conjunção de 2 4 𝑟 Eliminação da conjunção de 2 5 𝑝 𝑞 Introdução da conjunção de 3 e 1 6 𝑝 𝑞 𝑟 Introdução da conjunção de 5 e 4 d Associatividade Vamos começar com a primeira direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑝 𝑞 Eliminação da disjunção de 1 3 𝑝 Suposição por redução ao absurdo 4 𝑝 𝑞 𝑟 Introdução da disjunção de 3 5 𝑞 𝑟 Suposição por redução ao absurdo 6 𝑞 Suposição por redução ao absurdo 7 𝑝 𝑞 𝑟 Introdução da disjunção de 3 8 𝑝 𝑞 𝑟 Eliminação da disjunção de 2 34 57 9 𝑝 𝑞 𝑟 Eliminação da disjunção de 1 28 Agora vamos para a segunda direção 1 𝑝 𝑞 𝑟 Suposição 2 𝑝 Suposição por redução ao absurdo 3 𝑝 𝑞 𝑟 Introdução da disjunção de 2 4 𝑞 𝑟 Suposição por redução ao absurdo 5 𝑞 Suposição por redução ao absurdo 6 𝑝 𝑞 Introdução da disjunção de 2 7 𝑝 𝑞 𝑟 Introdução da disjunção de 6 8 𝑝 𝑞 𝑟 Eliminação da disjunção de 4 57 9 𝑝 𝑞 𝑟 Eliminação da disjunção de 1 23 48 3 a M 𝑃 𝐺 b Ou exclusivo 𝑃 𝐺 𝑀 𝐺 𝑃 𝐺 𝑀 𝐺 c 𝑀 𝑙𝑎𝑛𝑑 𝐺 𝑃 4 a Vamos formalizar o argumento utilizando proposições representadas por letras proposicionais 𝐷 Demócrito acredita na Teoria das Formas 𝑃 Platão acredita na Teoria das Formas 𝐴 Demócrito é um atomista 𝐵 Platão não é um atomista As premissas do argumento são 1 𝐷 𝑃 Ou Demócrito acredita na Teoria das Formas ou Platão acredita 2 𝑃 𝐴 Platão acredita na Teoria das Formas se e somente se ele não for um atomista 3 𝐴 𝐷 Demócrito é um atomista se e somente se ele não acredita na Teoria das Formas 4 𝐴 Demócrito é um atomista E a conclusão é 5 𝐵 Portanto Platão não é um atomista Agora vamos demonstrar que a conclusão é uma consequência lógica das premissas utilizando dedução natural 1 𝐴 𝐷 𝐷 𝐴 da premissa 3 2 𝐴 premissa 3 𝐷 eliminação da implicação de 1 com 2 4 𝑃 𝐴 premissa 5 𝑃 eliminação da biimplicação de 4 com 𝐷D 6 𝐷 𝑃 premissa 7 𝑃 premissa 8 𝐷 eliminação do ou de 6 com 7 9 𝐵 contradição com a premissa 4 Portanto demonstramos que a conclusão 𝐵 é uma consequência lógica das premissas confirmando que o argumento é válido b Vamos formalizar o argumento utilizando proposições representadas por letras proposicionais 𝐹 Eu fumo muito 𝐵 Eu bebo muito 𝐷 Eu não vou dormir bem 𝐸 Eu não como bem 𝐴 Eu me sinto acabado 𝑋 Eu faço exercícios 𝑆 Eu estudo As premissas do argumento são 1 𝐹 𝐵 𝐷 Se eu fumar muito ou beber muito não vou dormir bem 2 𝐷 𝐸 𝐴 Se eu não dormir bem ou não comer bem vou me sentir acabado 3 𝐴 𝑋 𝑆 Se eu me sentir acabado não farei exercícios e não estudarei 4 𝐹 Eu fumo muito E a conclusão é 5 𝑆 Portanto não estudarei Agora vamos demonstrar que a conclusão é uma consequência lógica das premissas utilizando dedução natural 1 𝐹 𝐵 𝐷 premissa 2 𝐹 premissa 3 𝐷 eliminação da implicação de 1 com 2 4 𝐷 𝐸 𝐴 premissa 5 𝐷 premissa 6 𝐸 eliminação da implicação de 4 com 5 7 𝐴 eliminação da implicação de 4 com 5 8 𝐴 𝑋 𝑆 premissa 9 𝑋 𝑆 eliminação da implicação de 7 com 8 10 𝑆 eliminação da conjunção de 9 Portanto demonstramos que a conclusão 𝑆 é uma consequência lógica das premissas confirmando que o argumento é válido 5 A Dedução Natural é um método de prova sintático na lógica Isso significa que ele se baseia na aplicação de regras formais para derivar conclusões a partir de premissas sem depender da interpretação semântica das proposições envolvidas Trabalho 1 1 a Lei de DeMorgan p q pq pq p q pq pq pq F F F V V V V V F V F V V F V V V F F V F V V V V V V F F F F V b Lei de DeMorgan p q pq pq p q pq pq pq F F F V V V V V F V V F V F F V V F V F F V F V V V V F F F F V c Distributividade p q r qr pqr pq pr pq pr pqr pq pr F F F F F F F F V F F V V F F F F V F V F V F F F F V F V V V F F F F V V F F F F F F F V V F V V V F V V V V V F V V V F V V V V V V V V V V V d Distributividade p q r qr pqr pq pr pq pr pqr pq pr F F F F F F F F V F F V F F F V F V F V F F F V F F V F V V V V V V V V V F F F V V V V V V F V F V V V V V V V F F V V V V V V V V V V V V V V The image contains no visible text e Associatividade p q r pq pq r qr pqr pqr pqr F F F F F F F V F F V F F F F V F V F F F F F V F V V V F V F V V F F F F F F V V F V F F F F V V V F V F F F V V V V V V V V V f Associatividade p q r pq pq r qr pqr pqr pqr F F F F F F F V F F V F V V V V F V F V V V V V F V V V V V V V V F F V V F V V V F V V V V V V V V F V V V V V V V V V V V V V 2 a Lei de DeMorgan Para provar essa equivalência precisamos provar pq pq e pq pq Vamos começar com a primeira direção 1 pq Suposição 2 p p Lei do terceiro excluído 3 pSuposição por redução ao absurdo 4 q Suposição por redução ao absurdo 5 p Suposição por redução ao absurdo 6 q Suposição por redução ao absurdo 7 pq Introdução da conjunção de 5 e 6 8 Contradição de 1 e 7 9 q Conclusão da suposição de 4 10q Negativação da conclusão de 9 11 pq Introdução da disjunção de 3 e 10 12 pq Eliminação da disjunção de 511 Agora vamos para a segunda direção 1 pq Suposição 2 p Suposição por redução ao absurdo 3 p Suposição por redução ao absurdo 4 q Suposição por redução ao absurdo 5 pq Introdução da conjunção de 2 e 4 6 Contradição de 1 e 5 7 qConclusão da suposição de 3 8 q Dupla negação de 7 9 pq Introdução da conjunção de 2 e 8 10 Contradição de 1 e 9 11 p Conclusão da suposição de 2 12 pq Introdução da disjunção de 11 13 pq Eliminação da disjunção de 312 Com ambas as direções provadas demonstramos o resultado b Lei de DeMorgan Vamos começar com a primeira direção 1 pq Suposição 2 p Suposição por redução ao absurdo 3 pq Introdução da disjunção de 2 4 Contradição de 1 e 3 5 p Conclusão da suposição de 2 6 q Suposição por redução ao absurdo 7 pq Introdução da disjunção de 6 8 Contradição de 1 e 7 9 q Conclusão da suposição de 6 10 pq Introdução da conjunção de 5 e 9 Agora vamos para a segunda direção 1 pq Suposição 2 p Eliminação da conjunção de 1 3 pq Lei da exclusão do terceiro 4 q Eliminação da conjunção de 1 5 pq Lei da exclusão do terceiro 6 Contradição de 2 3 e 4 5 7 pq Conclusão da suposição de 1 c Distributividade Começamos com a primeira direção 1 pqr Suposição 2 p Eliminação da conjunção de 1 3 qr Eliminação da conjunção de 1 4 q Suposição por redução ao absurdo 5 pq Introdução da conjunção de 2 e 4 6 pq pr Introdução da disjunção de 5 7 r Suposição por redução ao absurdo 8 pr Introdução da conjunção de 2 e 7 9 pq pr Introdução da disjunção de 8 10 pq pr Eliminação da disjunção de 3 46 79 Agora vamos para a segunda direção 1 pq pr Suposição 2 p Suposição por redução ao absurdo 3 q Suposição por redução ao absurdo 4 pqr Introdução da conjunção de 2 e 3 5 p Suposição por redução ao absurdo 6 r Suposição por redução ao absurdo 7 pqr Introdução da conjunção de 5 e 6 8 pqr Eliminação da disjunção de 1 24 57 d Distributividade Vamos começar com a primeira direção 1 pqr Suposição 2 p Suposição por redução ao absurdo 3 pq pr Suposição 4 pq Eliminação da conjunção de 3 5 pr Eliminação da conjunção de 3 6 q Suposição por redução ao absurdo 7 qr Introdução da conjunção de 6 e 7 8 pqr Introdução da disjunção de 2 e 7 9 r Suposição por redução ao absurdo 10qr Introdução da conjunção de 6 e 9 11 pqr Introdução da disjunção de 2 e 9 12 pqr Eliminação da conjunção de 4 58 911 Agora vamos para a segunda direção 1 pq pr Suposição 2 pq Eliminação da conjunção de 1 3 pr Eliminação da conjunção de 1 4 p Suposição por redução ao absurdo 5 pqr Introdução da disjunção de 4 6 qrSuposição por redução ao absurdo 7 q Eliminação da conjunção de 6 8 pqIntrodução da disjunção de 4 9 r Eliminação da conjunção de 6 10 prIntrodução da disjunção de 4 11 pq pr Introdução da conjunção de 2 e 3 12 pqr Eliminação da conjunção de 5 68 911 c Associatividade Vamos começar com a primeira direção 1 pqr Suposição 2 pq Eliminação da conjunção de 1 3 p Eliminação da conjunção de 2 4 q Eliminação da conjunção de 2 5 qr Introdução da conjunção de 4 e 1 6 pqr Introdução da conjunção de 3 e 5 Agora vamos para a segunda direção 1 pqr Suposição 2 qr Eliminação da conjunção de 1 3 q Eliminação da conjunção de 2 4 r Eliminação da conjunção de 2 5 pq Introdução da conjunção de 3 e 1 6 pqr Introdução da conjunção de 5 e 4 d Associatividade Vamos começar com a primeira direção 1 pqr Suposição 2 pq Eliminação da disjunção de 1 3 p Suposição por redução ao absurdo 4 pqr Introdução da disjunção de 3 5 qr Suposição por redução ao absurdo 6 q Suposição por redução ao absurdo 7 pqr Introdução da disjunção de 3 8 pqr Eliminação da disjunção de 2 34 57 9 pqr Eliminação da disjunção de 1 28 Agora vamos para a segunda direção 1 pqr Suposição 2 p Suposição por redução ao absurdo 3 pqr Introdução da disjunção de 2 4 qr Suposição por redução ao absurdo 5 q Suposição por redução ao absurdo 6 pq Introdução da disjunção de 2 7 pqr Introdução da disjunção de 6 8 pqr Eliminação da disjunção de 4 57 9 pqr Eliminação da disjunção de 1 23 48 3 a M PG b Ou exclusivo PG M G PG M G c 4 a Vamos formalizar o argumento utilizando proposições representadas por letras proposicionais 𝐷 Demócrito acredita na Teoria das Formas 𝑃 Platão acredita na Teoria das Formas 𝐴 Demócrito é um atomista 𝐵 Platão não é um atomista As premissas do argumento são 1 D P Ou Demócrito acredita na Teoria das Formas ou Platão acredita 2 P A Platão acredita na Teoria das Formas se e somente se ele não for um atomista 3 A D Demócrito é um atomista se e somente se ele não acredita na Teoria das Formas 4 𝐴 Demócrito é um atomista E a conclusão é 5 B Portanto Platão não é um atomista Agora vamos demonstrar que a conclusão é uma consequência lógica das premissas utilizando dedução natural 1 ADD A da premissa 3 2 𝐴 premissa 3 D eliminação da implicação de 1 com 2 4 P A premissa 5 P eliminação da biimplicação de 4 com 𝐷D 6 D P premissa 7 P premissa 8 D eliminação do ou de 6 com 7 9 B contradição com a premissa 4 Portanto demonstramos que a conclusão B é uma consequência lógica das premissas confirmando que o argumento é válido b Vamos formalizar o argumento utilizando proposições representadas por letras proposicionais 𝐹 Eu fumo muito 𝐵 Eu bebo muito 𝐷 Eu não vou dormir bem 𝐸 Eu não como bem 𝐴 Eu me sinto acabado 𝑋 Eu faço exercícios 𝑆 Eu estudo As premissas do argumento são 1 FB D Se eu fumar muito ou beber muito não vou dormir bem 2 D E A Se eu não dormir bem ou não comer bem vou me sentir acabado 3 A XS Se eu me sentir acabado não farei exercícios e não estudarei 4 F Eu fumo muito E a conclusão é 5 S Portanto não estudarei Agora vamos demonstrar que a conclusão é uma consequência lógica das premissas utilizando dedução natural 1 FB D premissa 2 F premissa 3 D eliminação da implicação de 1 com 2 4 D E A premissa 5 D premissa 6 E eliminação da implicação de 4 com 5 7 A eliminação da implicação de 4 com 5 8 A XS premissa 9 XS eliminação da implicação de 7 com 8 10S eliminação da conjunção de 9 Portanto demonstramos que a conclusão S é uma consequência lógica das premissas confirmando que o argumento é válido 5 A Dedução Natural é um método de prova sintático na lógica Isso significa que ele se baseia na aplicação de regras formais para derivar conclusões a partir de premissas sem depender da interpretação semântica das proposições envolvidas Pontifícia Universidade Católica do Rio Grande do Sul Escola Politécnica Lógica para a Ciência da Computação P1 1 a Considere a tabela verdade abaixo 𝑷 𝑸 𝑷 𝑸 𝑷 𝑷 𝑸 F F F V F V V V V F V V V V V V A tabela possui apenas valores verdadeiros logo 𝑃 𝑃 𝑄 é uma tautologia b Considere a tabela abaixo 𝑷 𝑷 𝑷 𝑷 𝑷 𝑷 F V V F V F V F A tabela possui apenas valores falsos logo 𝑃 𝑃 é uma contradição c Considere a tabela verdade abaixo 𝑷 𝑸 𝑹 𝑷 𝑹 𝑷 𝑹 𝑷 𝑹 𝑸 𝑹 𝑸 𝑹 𝑷 𝑹 𝑷 𝑹 𝑷 𝑸 𝑹 𝑷 𝑹 𝑷 𝑹 F F F V V V V V F F V V V V V V F V F V V F V V F V V V V V V V V F F F V V V V V F V V V V V V V V F F V F V V V V V V V V V V A tabela possui apenas valores verdadeiros então 𝑃 𝑄 𝑅 𝑃 𝑅 𝑃 𝑅 é uma tautologia 2 A expressão Cão que ladra não morde pode ser formulada como 𝑝 𝑞 Resposta Letra C 3 A expressão Onde há fumaça há fogo pode ser formulada como 𝑝 𝑞 Resposta Letra A 4 a Formalização 𝑃 O tanque é vazio 𝑄 O carro não anda Argumento 1 𝑃 𝑄 premissa 2 𝑃 premissa 3 Portanto 𝑄 MP 1 2 b Formalização 𝑃 O tanque é vazio 𝑄 O carro não anda Argumento 1 𝑃 𝑄 premissa 2 𝑄 premissa 3 Portanto 𝑃 MT 1 2 c Formalização 𝑃 O carro não anda 𝑄 O tanque é vazio 𝑅 O motor não funciona Argumento 1 𝑃 𝑄 𝑅 premissa 2 𝑃 premissa 3 𝑄 premissa 4 Portanto 𝑅 DS 1 2 3 d Formalização 𝑃 O motor não funciona 𝑄 O carro anda Argumento 1 𝑃 premissa 2 𝑃 𝑄 premissa 3 Portanto 𝑄 MT 1 2 5 a Vamos provar 𝑃𝑄 𝑃 𝑄 1 𝑃 𝑄𝑃 𝑄𝑃 premissa 2 𝑃 suposição para a introdução da conjunção 3 𝑄 suposição para a introdução da conjunção 4 𝑃 𝑄 introdução da conjunção 2 3 5 Contradição 𝑃 𝑄 e 𝑃 𝑄 contradição 1 4 6 𝑃 introdução da negação 25 7 𝑄 suposição para a introdução da disjunção 8 𝑃 𝑄 introdução da disjunção 6 7 9 𝑃 𝑄 eliminação da conjunção 18 Portanto 𝑃𝑄 𝑃 𝑄 b Vamos provar 𝑃 𝑄 𝑄 𝑃 1 Suponha 𝑃 𝑄 suposição para a introdução da implicação 2 Suponha 𝑄 suposição para a introdução da implicação 3 Suponha 𝑃 suposição para a introdução da implicação 4 𝑄 eliminação da implicação 1 3 5 Contradição 𝑄 e 𝑄 contradição 2 4 6 𝑃 introdução da negação 35 7 𝑄 𝑃 introdução da implicação 26 8 𝑃 𝑄 𝑄 𝑃 introdução da implicação 17 9 𝑃 𝑄 𝑄 𝑃 introdução da implicação 18 Portanto 𝑃 𝑄 𝑄 𝑃 6 A Dedução Natural é um método de prova sintático na lógica Isso significa que ele se baseia na aplicação de regras formais para derivar conclusões a partir de premissas sem depender da interpretação semântica das proposições envolvidas Pontifícia Universidade Católica do Rio Grande do Sul Escola Politécnica Lógica para a Ciência da Computação P1 1 a Considere a tabela verdade abaixo P Q PQ PPQ F F F V F V V V V F V V V V V V A tabela possui apenas valores verdadeiros logo PPQ é uma tautologia b Considere a tabela abaixo P P PP P P F V V F V F V F A tabela possui apenas valores falsos logo P Pé uma contradição c Considere a tabela verdade abaixo P Q R PR PR P R Q R Q R PR P R PQ R PR P R F F F V V V V V F F V V V V V V F V F V V F V V F V V V V V V V V F F F V V V V V F V V V V V V V V F F V F V V V V V V V V V V A tabela possui apenas valores verdadeiros então PQ R P R PR é uma tautologia 2 A expressão Cão que ladra não morde pode ser formulada como pq Resposta Letra C 3 A expressão Onde há fumaça há fogo pode ser formulada como pq Resposta Letra A 4 a Formalização P O tanque é vazio Q O carro não anda Argumento 1 PQ premissa 2 P premissa 3 Portanto Q MP 1 2 b Formalização P O tanque é vazio Q O carro não anda Argumento 1 PQ premissa 2 Q premissa 3 Portanto P MT 1 2 c Formalização P O carro não anda Q O tanque é vazio R O motor não funciona Argumento 1 PQ R premissa 2 P premissa 3 Q premissa 4 Portanto R DS 1 2 3 d Formalização P O motor não funciona Q O carro anda Argumento 1 P premissa 2 PQ premissa 3 Portanto Q MT 1 2 5 a Vamos provar P Q PQ 1 PQPQP premissa 2 P suposição para a introdução da conjunção 3 Q suposição para a introdução da conjunção 4 PQ introdução da conjunção 2 3 5 Contradição PQ e PQ contradição 1 4 6 P introdução da negação 25 7 Q suposição para a introdução da disjunção 8 PQ introdução da disjunção 6 7 9 PQ eliminação da conjunção 18 Portanto P Q PQ b Vamos provar PQQ P 1 Suponha PQ suposição para a introdução da implicação 2 Suponha Q suposição para a introdução da implicação 3 Suponha P suposição para a introdução da implicação 4 𝑄 eliminação da implicação 1 3 5 Contradição Q e Q contradição 2 4 6 P introdução da negação 35 7 Q P introdução da implicação 26 8 PQ Q P introdução da implicação 17 9 PQQ P introdução da implicação 18 Portanto PQQ P 6 A Dedução Natural é um método de prova sintático na lógica Isso significa que ele se baseia na aplicação de regras formais para derivar conclusões a partir de premissas sem depender da interpretação semântica das proposições envolvidas