Lógica Proposicional

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