Baixe o app para aproveitar ainda mais
Prévia do material em texto
Raciocínio Lógico Aula 1 Prof. André Roberto Guerra Organização da Disciplina Aula 1 – Fundamentação • Definições preliminares • Proposições e conectivos Aula 2 – Operações • Operações lógicas sobre proposições • Construção de tabelas-verdade Aula 3 – Proposições Compostas • Tautologia, contradições e contingências Aula 4 – Implicação e Equivalência • Implicação lógica • Equivalência lógica Aula 5 – • Álgebra das proposições • Método dedutivo Aula 6 – Regras e Validade • Argumentos e regras de inferência • Validade mediante tabelas-verdade, regras de inferência e equivalências Aula Prática 1 a 4 – Aulas 7 a 10 – • Exercícios de fixação • Solução de problemas FIM Organização da Aula Fundamentação • Definições preliminares • Proposições e conectivos Definições Preliminares • A lógica formal é uma ciência que determina as formas corretas (válidas) de raciocínio (COPI, I.M. Introdução à lógica. São Paulo: 1968) � Estudo dos métodos e princípios usados para distinguir o raciocínio correto do incorreto (DOPP, J. Noções de lógica formal. São Paulo:1970) � O aprendizado da Lógica auxilia os estudantes no raciocínio, na compreensão de conceitos básicos, na verificação formal de programas e os prepara melhor para o entendimento do conteúdo de tópicos mais avançados (CELINA A.A.P. ABAR: 2011 - PUCSP) � Lógica é o estudo de argumentos. Um argumento é uma sequência de enunciados na qual um dos enunciados é a conclusão e os demais são premissas, as quais servem para provar, ou pelo menos fornecer, alguma evidência para a conclusão (NOLT, J.; ROHATYN, D. Lógica. São Paulo:1991) Áreas de Atuação • Ciências Humanas • Filosofia, Direito, Letras • Ciências Exatas/Tecnológicas • Computação/TI/Matemática • Algoritmos • Programação • Argumentos estão tradicionalmente divididos em: • DEDUTIVOS e INDUTIVOS Argumento Dedutivo • É válido quando suas premissas são verdadeiras e a conclusão é também verdadeira � Premissa: "Todo homem é mortal." � Premissa: "João é homem." � Conclusão: "João é mortal." Esses argumentos serão objeto de estudo neste roteiro Argumento Indutivo • A verdade das premissas não basta para assegurar a verdade da conclusão � Premissa: "É comum após a chuva ficar nublado." � Premissa: "Está chovendo." � Conclusão: "Ficará nublado." Não trataremos do estudo desses argumentos neste roteiro � As premissas e a conclusão de um argumento, formuladas em uma linguagem estruturada, permitem que o argumento possa ter uma análise lógica apropriada para a verificação de sua validade Tais técnicas de análise serão objeto de estudo deste conteúdo FIM Uma breve história da Lógica • Vídeo: http://www.youtube.com/watch?v=ozMbmBp3onE Classificação da Lógica • Alguns autores dividem o estudo da Lógica em: • Lógica Indutiva • Lógica Dedutiva Lógica Indutiva •Útil no estudo da teoria da probabilidade (não será abordada neste roteiro) Lógica Dedutiva • Que pode ser dividida em: 1. Lógica clássica 2. Lógicas complementares da clássica 3. Lógicas não - clássicas 1- Lógica Clássica � Considerada como o núcleo da lógica dedutiva. Denominada atualmente de Cálculo de Predicados de 1ª Ordem � “O Cálculo de Predicados, dotado de uma linguagem mais rica, tem várias aplicações importantes não só para matemáticos e filósofos, como também para estudantes de Ciência da Computação.” 2 - Lógicas Complementares da Clássica � Complementam de algum modo a lógica clássica estendendo o seu domínio •Exemplos: lógicas modal, deôntica, epistêmica, etc. 3- Lógicas Não-Clássicas � Caracterizadas assim por derrogarem alguns dos princípios da lógica clássica • Exemplos: paracompletas e intuicionistas; paraconsistentes; não-aléticas; não- reflexivas; probabilísticas, polivalentes, fuzzy-logic etc. FIM Períodos da Lógica • Um “esboço" do desenvolvimento da lógica: • Período Aristotélico: (± 390 a.C. a ± 1840 d.C.) • Período Booleano: (± 1840 a ± 1910) • Período Atual: (1910 - ........) Período Aristotélico (± 390 a.C. a ± 1840 d.C.) • Início com o filósofo grego Aristóteles (384 - 322a.C.), que criou a ciência da Lógica, cuja essência era a teoria do silogismo • Organon ou Instrumento da Ciência Período Booleano (± 1840 a ± 1910) •Inicia-se com George Boole (1815-1864) e Augustus de Morgan (1806-1871) � Publicaram os fundamentos da chamada Álgebra da Lógica, respectivamente com Mathematical Analysis Of Logic e Formal Logic. Período Atual (1910 - ...) •Atualmente, as especialidades se multiplicam e as pesquisas em Lógica englobam muitas áreas do conhecimento FIM Cálculo Proposicional •A primeira e indispensável parte da Lógica é o Cálculo Proposicional ou Cálculo Sentencial ou, ainda, Cálculo das Sentenças � PROPOSIÇÃO: •Sentenças declarativas afirmativas que tenham sentido em afirmar que sejam verdadeiras ou falsas •A lua é quadrada. •A neve é branca. •Matemática é uma ciência. � Sentenças interrogativas ou exclamativas não são estudadas Símbolos da Linguagem • Variáveis Proposicionais: letras latinas minúsculas p,q,r,s,... para indicar as proposições (fórmulas atômicas) • Exemplos: A lua é quadrada: p A neve é branca: q Conectivos Lógicos •As fórmulas atômicas podem ser combinadas entre si e, para representar tais combinações utiliza-se os conectivos lógicos Conectivos lógicos: ^ e v ou → se...então ↔ se e somente se ~ não Exemplos • A lua não é quadrada: ~p • A lua é quadrada e a neve é branca: p ^ q (conjunctos) • A lua é quadrada ou a neve é branca: p v q (disjunctos) � Se a lua é quadrada então: •a neve é branca: p → q (p é o antecedente e q o consequente) � A lua é quadrada se e somente se a neve é branca: p ↔ q Símbolos Auxiliares • ( ), parênteses são utilizados para denotar o "alcance" dos conectivos; • Se a lua é quadrada e a neve é branca, então a lua não é quadrada: ((p ^ q) → ~p) • A lua não é quadrada se e somente se a neve é branca: ((~p) ↔ q)) Definição de Fórmula 1. Toda fórmula atômica é uma fórmula 2. Se A e B são fórmulas, então: (~A), (A v B), (A ^ B), (A → B), (A ↔ B) também são fórmulas 3. São fórmulas apenas as obtidas por 1. e 2. � Fórmulas são constituídas pelos símbolos do alfabeto (variáveis ou átomos, conectivos e símbolos de pontuação) � Todo símbolo de verdade é uma fórmula � Todo símbolo proposicional é uma fórmula � Se A é uma fórmula, então ~A, isto é, negação de A, também é uma fórmula Se A e B são fórmulas... • Negação: ~A ou ~B • Disjunção: A ∧ B • Conjunção: A ∨ B • Implicação: A → B • Bi-implicação: A ↔ B • A: antecedente • B: consequente � Os parênteses são usados segundo a seguinte ordem dos conectivos: ~, ^ , v , → , ↔ � Com o mesmo conectivo adota-se a convenção pela direita Ordem de precedência dos conectivos • Maior precedência: 1. ~ • Precedência intermediária: 2. ∧, 3. ∨ • Menor precedência: 4. →, 5. ↔ Exemplo • A fórmula: p v q ^ ~r → p → ~q • Deve ser entendida como: (((p v q) ^ (~r)) → (p → (~q))) Eliminação de parênteses • Parênteses externos: ((p ∧ ~q)→ ~q) (p ∧ ~q)→ ~q � Conectivos ∨ e ∧ repetidos: alinham-se à esquerda: ((p ∧ q) ∧ ~r) ∧ ~s (p ∧ q ∧ ~r) ∧ ~s p ∧ q ∧ ~r ∧ ~s � Conectivos → e ↔ repetidos: alinham-se à direita: p → (q → (r → s)) p → (q → r → s) p → q → r → s SínteseRaciocínio Lógico • Aula 1 – Fundamentação • Definições preliminares • Proposições e conectivos Referências de Apoio • SANT'ANNA, A. S. O que é um Axioma. Capítulo 3 - Barueri SP: Editora Manoele , 2003. FIM Raciocínio Lógico Aula 2 Prof. André Roberto Guerra Organização da Aula • Operações • Operações lógicas sobre proposições • Construção de tabelas-verdade FIM Operações Lógicas � A lógica clássica é governada por três princípios (entre outros). São eles: • Princípio da Identidade • Princípio da Contradição • Princípio do Terceiro Excluído � Princípio da Identidade: • Todo objeto é idêntico a si mesmo � Princípio da Contradição: • Dadas duas proposições contraditórias (uma é negação da outra), uma delas é falsa � Princípio do Terceiro Excluído: • Dadas duas proposições contraditórias, uma delas é verdadeira � Tendo como base esses princípios, as proposições simples são ou verdadeiras ou falsas - sendo mutuamente exclusivos os dois casos � Daí dizer que a lógica clássica é bivalente Tabela Verdade • Dada uma expressão proposicional, e os valores lógicos das proposições simples que a compõe, utilizando a ordem de precedência é possível calcular o valor lógico da expressão � Para determinar o valor (verdadeiro ou falso) das proposições compostas (moleculares), conhecidos os valores das proposições simples (atômicas) que as compõem são utilizadas tabelas-verdade � Tabela Verdade da proposição composta é uma tabela na qual são apresentados todos os valores verdade possíveis de uma proposição composta, para cada combinação dos valores verdade das proposições componentes � Cada linha da Tabela corresponde a uma possível combinação dos valores lógicos das proposições componentes; como são dois os valores lógicos, existem, para n componentes, 2n combinações possíveis � Possui dois tipos de colunas: • Colunas para as proposições componentes (onde são distribuídos os valores V e F de forma a incluir cada possível combinação) • Colunas para as operações (onde os valores V e F são obtidos pelas operações) � Assim, se a expressão possui n componentes e m operações, a Tabela terá m + n colunas � Para determinar unicamente a Tabela Verdade são estabelecidas algumas convenções para sua construção � Para as colunas: • 1. Dispor as proposições componentes em ordem alfabética • 2. Dispor as operações na ordem de precedência determinada (com parênteses) � Para as linhas: • Alternar V e F para a última coluna • Alternar V V e F F para a penúltima • Alternar V V V V e F F F F para a antepenúltima coluna componente � Prosseguir dessa forma, se houver mais componentes, sempre dobrando o numero de Vs e Fs para cada coluna à esquerda Exemplo: a expressão proposicional (p → q) ∨ ~ ((p ↔ r) → ~ r) � 1. Tabela Verdade da "negação": ~p é Verdadeira se e somente se p é Falsa � 2. Tabela verdade da "conjunção": é Verdadeira se e somente se os conjuntos são Verdadeiros � 3. Tabela verdade da "disjunção": é Falsa se e somente os disjuntos são Falsos � 4. Tabela verdade da "implicação": é Falsa se e somente se o antecedente é Verdadeiro e o consequente é Falso � 5. Tabela verdade "bi implicação": a bi implicação é Verdadeira se, e somente se seus componentes são ou ambos Verdadeiros ou ambos Falsos � 6. Tabela verdade “OU Exclusivo”: É importante observar que "ou" pode ter dois sentidos na linguagem habitual: inclusivo (disjunção) v e exclusivo v onde: p v q significa ((p v q) ^~ (p ^ q)) � 6. Tabela verdade "OU Exclusivo“: � Número de linhas de uma tabela verdade: • Cada proposição simples (atômica) tem dois valores (V ou F) que se excluem. Para n atômicas distintas, há tantas possibilidades quantos são os arranjos com repetição de 2 elementos n a n � Segue-se que o número de linhas da tabela verdade é 2n. Assim: • Para duas proposições são 22 = 4 linhas • Para três proposições são 23 = 8 linhas • Para quatro proposições são 24 = 16 linhas � Exemplo: � A tabela verdade da fórmula ((p v q) → r) terá 8 linhas, como segue: • Variáveis / Proposições: 3 (p q r) 23 = 8 linhas � Exemplo: Construir a tabela verdade da fórmula: ((p v q) → ~p) → (q ^ p) Aplicação � Construir as tabela verdade das fórmulas a seguir •a. (p ∧ q) → (p ∨ q) •b. ~(p ∧ q) ∨ ~(p ↔ p) •c. ~p ∧ ~(p → ~q) 30 � a. (p ∧ q) → (p ∨ q) 31 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V • a. (p ∧ q) → (p ∨ q) 32 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V F F • a. (p ∧ q) → (p ∨ q) 3 3 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V V F F F • a. (p ∧ q) → (p ∨ q) 3 4 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V V F F V F F • a. (p ∧ q) → (p ∨ q) 3 5 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V V V F F F V F F F F • a. (p ∧ q) → (p ∨ q) 3 6 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V V V V F F V F V F V F F F F • a. (p ∧ q) → (p ∨ q) 3 7 p q (p ∧ q) (p ∨ q) (p ∧ q) → (p ∨ q) V V V V V V F F V V F V F V V F F F F V � b. ~(p ∧ q) ∨ ~(p ↔ p) 38 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V F F � b. ~(p ∧ q) ∨ ~(p ↔ p) 3 9 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V V F F V F F � b. ~(p ∧ q) ∨ ~(p ↔ p) 4 0 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V V V F F F V F F F F � b. ~(p ∧ q) ∨ ~(p ↔ p) 4 1 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V F V V F V F F V V F F F V F � b. ~(p ∧ q) ∨ ~(p ↔ p) 4 2 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V F V V F V F F V V F F F V V � b. ~(p ∧ q) ∨ ~(p ↔ p) 4 3 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V F F V V F V V F F V V V F F F V F V � b. ~(p ∧ q) ∨ ~(p ↔ p) 4 4 p q ~(p ∧ q) ~(p ↔ q) ~(p ∧ q) ∨ ~(p ↔ q) V V F F F F F V F V V V V V F V V V V V V F F V F V V F � c. ~p ∧ ~(p → ~q) 45 p q ~p ∧ ~ (p → ~q) V V F V F F F V V F F V � c. ~p ∧ ~(p → ~q) 4 6 p q ~p ∧ ~ (p → ~q) V V F F V F F V F V V F F F V V � c. ~p ∧ ~(p → ~q) 4 7 p q ~p ∧ ~ (p → ~q) V V F V F V F F V V F V V F F F F V F V � c. ~p ∧ ~(p → ~q) 4 8 p q ~p ∧ ~ (p → ~q) V V F V F F V F F V V V F V V F V F F F V F V V � c. ~p ∧ ~(p → ~q) 4 9 p q ~p ∧ ~ (p → ~q) V V F V V F F V F F F V V V F V V F F V F F F V F F V V � c. ~p ∧ ~(p → ~q) 5 0 p q ~p ∧ ~ (p → ~q) V V F F V V F F V F F F F V V V F V V F F F V F F F V F F F V V � Software de apoio didático Truth Table Constructor •www.brian-borowski.com/Software/Truth/ 51 Síntese Raciocínio Lógico • Aula 2 – Operações • Operações lógicas sobre proposições • Construção de tabelas-verdade Referências de Apoio • SANT'ANNA, A. S. O que é um Axioma. Capítulo 3 - Barueri SP: Editora Manoele , 2003. • http://www.pucsp.br/~logica/ FIM Raciocínio Lógico Prof. André Roberto Guerra Aula 3 Organização da Aula Proposições compostas • Tautologia • Contradições • Contingências Propriedades Semânticas • Propriedades semânticas básicas da Lógica Proposicional (LP): • Tautologia • Contradição • Contingência • Tautologia (ou fórmula válida) • Uma fórmula Aé uma tautologia, se, e somente se, para toda interpretação I, I[A] = V Tautologia • Tautologia é toda proposição composta cujo conjunto resposta da tabela- verdade é formado em sua totalidade por V (verdadeiro) � Em outros termos, é toda proposição composta por P (p, q, r, …) cujo valor lógico é sempre V (verdade), quaisquer sejam os valores lógicos das proposições simples componentes p, q, r, … • É imediato que as proposições p → p e p ↔ p são tautológicas (princípio de identidade para as proposições) • Exemplo: A proposição “~(p ^ ~p)” (princípio da não contradição) é tautologia, conforme mostra a sua tabela-verdade: • Portanto, dizer que uma proposição não pode ser simultaneamente verdadeira e falsa é sempre verdadeiro p ~p p ^ ~p ~(p ^ ~p) V F F V F V F V p ~p p v ~p V F V F V V � A proposição “p v ~p” (princípio do terceiro excluído) é tautologia, como comprovado na tabela-verdade • Portanto, o conceito de que uma proposição ou é verdadeira ou é falsa é válido • Uma fórmula A é insatisfazível (insatisfatível) ou uma contradição (contraválida), se, e somente se, para toda interpretação I, I[A] = F Contradição • Contradição é toda proposição composta cujo conjunto resposta da tabela- verdade é formado em sua totalidade por F (falso) � Em outros termos, é toda proposição composta P(p, q, r, …) cujo valor lógico é sempre F (falso), quaisquer sejam os valores lógicos das proposições simples componentes p, q, r, … • Como a tautologia é sempre verdadeira (V), a negação de uma tautologia é sempre falsa (F), ou seja, é uma contradição, e vice-versa • Portanto, dizer que uma proposição pode ser simultaneamente verdadeira e falsa é sempre falso p ~p p ^ ~p V F F F V F � Exemplo: a proposição “p ^ ~p” � A proposição (p^q)^ ~(p v q) é uma contradição como comprovado na tabela-verdade: p q p ^ q p v q ~(p v q) (p ^ q) ^ ~(p v q) V V V V F F V F F V F F F V F V F F F F F F V F � Uma fórmula A é uma contingência se, e somente se, os valores do seu conjunto resposta são diferentes entre si Contingência • Em outros termos, é toda proposição composta P(p, q, r, …) cujo valor lógico é alternado entre V (verdadeiro) e F (falso), quaisquer sejam os valores lógicos das proposições simples componentes p, q, r, … • Simplificando, contingência é toda proposição composta cujo conjunto resposta • não é tautologia e • não é contradição � A proposição ~(p v q) é uma contingência como comprovado na tabela-verdade p q p v q ~(p v q) V V V F V F V F F V V F F F F V � Uma fórmula A é falsificável, se, e somente se, os valores do seu conjunto resposta são F (falsos) • A fórmula sob a condição de contradição também é falsificável Propriedades Semânticas LP � Uma fórmula A é satisfazível, se, e somente se, os valores do seu conjunto resposta são V (verdade) • A fórmula sob a condição de tautologia também é satisfazível Relações entre fórmulas da LP • Toda fórmula válida (tautologia) é satisfazível • Toda fórmula contraditória (insatisfazível) é falsificável • Uma fórmula não pode ser satisfazível e contraditória • Uma fórmula não pode ser uma tautologia e falsificável • Se A é uma tautologia, então ~A é contraditória • Se A é contraditória, então, ~A é uma tautologia • Se A é satisfazível, então ~A é falsificável, e vice-versa • Há fórmulas que são tanto satisfazíveis quanto falsificáveis, i.e., são contingências ou fórmulas indeterminadas • Curiosidade • A classificação de fórmulas extensas não é um processo trivial • Um dos grandes desafios da computação é encontrar métodos (algoritmos) eficientes para decidir se uma fórmula é: • satisfazível — falsificável • contradição — tautologia Classificação de Fórmula LP Falsificável Contradição 0 0 0 0 0 0 0 00 0 0 0 00 00 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0 0 0 000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Satisfazível Tautologia 1 1 111 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 10 0 0 0 0 0 00 0 0 0 00 00 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0 0 0 0 000 0 0 0 0 0 0 1 111 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 0 0 00 0 0 0 0 00 0 0 0 0 0 1 1 1 1 1Contradição Tautologia Falsificável Satisfazível C o n t i n g ê n c i a Síntese Raciocínio Lógico • Propriedades semânticas básicas da Lógica Proposicional (LP) • Tautologia • Contradição • Contingência • Satisfazível • Falsificável Referências de Apoio • SANT'ANNA, A. S. O que é um Axioma. Capítulo 3. Barueri: Editora Manoele, 2003. Site para consulta � Noções de Lógica Matemática — PUC–SP. Disponível em: <http://www.pucsp.br/~logica/>. Raciocínio Lógico Prof. André Roberto Guerra Aula 4 Organização da Aula • Implicação Lógica • Equivalência Lógica 2 Implicação e Equivalência Lógica • Envolve: • Tabela-verdade • Classificação de fórmulas da LP • Tautologia • Contradição • Contingência 3 • Conectivos •→ (implicação / condicional) • (implicação lógica) •↔ (bi-implicação) • (equivalência lógica) 4 Implicação Lógica • Segundo o dicionário Michaelis, “implicar” significa: Originar, produzir como consequência, ser causa de: ...uma filosofia definitiva, ...implicaria a imobilidade do pensamento humano (Antero de Quental) 5 • Definição • A implicação lógica entre P e Q (duas fórmulas proposicionais quaisquer), nesta ordem, ocorre se, e somente se, a implicação (condicional “→”) entre elas gerar uma tautologia 6 • Os símbolos “→” e “ ” são distintos pois, “→” condicional é o resultado de uma operação lógica. Exemplo, considerando as proposições p e q, pode-se obter uma nova proposição expressa por p → q 7 •Já a Implicação Lógica estabelece uma relação. Exemplo: A condicional p^~p → q é tautologia. Logo, p^~p→ q ⇒ T 8 p q ~p p^ ~p p^~p → q V V F F V V F F F V F V V F V F F V F V • Em outras palavras, uma proposição composta P (p, q, r, …) implica numa proposição composta Q (p, q, r, …) se em qualquer linha da tabela verdade de P → Q NÃO ocorrer de P ser V (verdadeiro) e Q se F (Falso). P ⇒ Q sempre que os valores de seus conectivos forem V (Verdade) 9 • Em síntese, a condição necessária e suficiente para que uma implicação lógica qualquer representada por P⇒Q seja válida (verdadeira) é que a proposição condicional P (p, q, r, …)→ Q (p, q, r, …) seja uma tautologia 10 • Exemplo: verificar se p ^ q ⇒ p v q é válida. Para isso, basta construir a tabela verdade da proposição p ^ q → p v q e observar o resultado 11 p q p ^ q p v q p ^ q → p v q V V V V V V F F V VF V F V V F F F F V • O Conjunto resposta da tabela verdade da proposição p ^ q → p v q é uma tautologia. Sendo assim, p ^ q ⇒ p v q é válido (Verdadeiro) 12 • Exemplo: Verificar se p→ q⇒ p↔ q é válida. Para isso, basta construir a tabela verdade da proposição p→ q→ p↔ q e observar o resultado 13 p q p → q p ↔ q p → q → p ↔ q V V V V V V F F V V F V F V F F F F F V • O Conjunto resposta da tabela verdade da proposição p→ q→ p↔ q NÃO é tautologia. Sendo assim, p→ q→ p↔ q NÃO é válido (Falso) 14 Propriedades da Implicação • As Implicações Lógicas admitem certas propriedades que podem ser utilizadas na obtenção de outros resultados • Estão categorizadas em: � Implicações Imediatas � Implicações Notáveis 15 Implicações Imediatas •Propriedade Reflexiva •Qualquer proposição P implica na própria proposição P P⇒P •Propriedade Transitiva •Se P⇒Qe Q⇒R então P⇒R comprovado pela tabela verdade (P→Q ^ Q→R)→ (P→R) 16 Implicações Notáveis • Regras de inferência • Adição • Simplificação • Simplificação Disjuntiva • Absorção • Modus Ponens • Modus Tollens • Silogismo disjuntivo 17 •Adição Ocorre junto ao conectivo OU “v” P⇒P v Q Q⇒P v Q •Simplificação Ocorre junto ao conectivo E “^” P^ Q ⇒ P P^ Q ⇒ Q 18 •Simplificação disjuntiva •Utilizada nos casos em que uma das proposições ocorre de forma contraditória e com um conectivo OU “v” sendo simplificada (P v Q) ^ (P v ~Q) ⇒ P Sou feliz ou me demito e Sou feliz ou não me demito. Logo, sou feliz 19 • Absorção • Uma mesma proposição simples ocorre numa proposição condicional, sendo suficiente então pode ser omitida (absorvida) P → Q ⇒ P → (P ^ Q) Se corro então pulo. Logo, se corro, então corro e pulo 20 • Modus Ponens • Baseada em proposição condicional (P → Q) ^ P ⇒ Q • Modus Tollens • Baseada em proposição contrapositiva de condicional (P → Q) ^ ~Q ⇒ ~P 21 • Silogismo disjuntivo • Ocorre a partir de uma disjunção (conectivo “OU”) em que uma das proposições simples é contrariada validando a outra proposição (P v Q) ^ ~P ⇒ Q (P v Q) ^ ~Q ⇒ P 22 Equivalência Lógica • Segundo o dicionário Michaelis, “equivalência” significa: igualdade de valor, correspondência [DICMAXI – Michaelis Português] 23 • Definição • A equivalência lógica entre P e Q (duas fórmulas proposicionais quaisquer), nesta ordem, ocorre se, e somente se, a bicondicional “↔” entre elas gerar uma tautologia 24 • É importante lembrar que os símbolos “↔” e “⇔” são distintos pois, “↔” bicondicional é o resultado de uma operação lógica. Já a equivalência Lógica, estabelece uma relação 25 • Duas proposições são logicamente equivalentes (ou equivalentes) quando ambas apresentam os mesmos valores lógicos. Ou ainda, são logicamente equivalentes (ou equivalentes) quando o conjunto resposta de suas tabela verdade são iguais 26 • Em síntese, a condição necessária e suficiente para que uma equivalência lógica qualquer representada por P⇔ Q seja válida (verdadeira) é que a proposição bicondicional correspondente P ↔ Q seja uma tautologia 27 • Exemplo: • A bicondicional ~(p^~q)↔ (p→ q) é uma equivalência. Logo, ~(p^~q) ⇔ (p→ q) é tautologia 28 p q ~q p^ ~q ~(p^ ~q) p→q ~(p^ ~q) ⇔ p → q V V F F V V V V F V V F F V F V F F V V V F F V F V V V • Exemplo 2: • A proposição p↔ q⇔ (p→q)^(q→p) é uma equivalência. Logo, p ↔ q⇔ (p→q)^(q→p) é tautologia 29 p q p→q q→p (p→q) ^ (q→p ) p ↔ q V V V V V V V F F V F F F V V F F F F F V V V V Equivalências Imediatas • Propriedade Reflexiva • Qualquer proposição P equivale a própria proposição P P⇔ P • Propriedade Transitiva • Se P⇔ Q e Q⇔ R então P⇔ R Comprovado pela tabela verdade (P→ Q) ^ (Q→ R)↔ (P→ R) 30 Quadro de Equivalências 31 Síntese Raciocínio Lógico • Implicação Lógica • Equivalência Lógica Referências de Apoio • SANT'ANNA, A. S. O que é um Axioma. Capítulo 3. Barueri, SP: Editora Manoele, 2003. Raciocínio Lógico Aula 5 Prof. André Roberto Guerra 5 � Álgebra das proposições �Método Dedutivo Organização da Aula Ferramenta muito importante, pois através dela pode-se operar sobre proposições utilizando-se de implicações e equivalências “notáveis”. Álgebra das Proposições Uma aplicação apresentada como exemplo é a simplificação de códigos computacionais, pois quanto mais simples o código, mais simples será compreendido e poderá ser executado mais rapidamente. Álgebra das Proposições Conceito definido e apresentado no início” da disciplina (Aula 1) “PROPOSIÇÃO: sentenças declarativas afirmativas que tenham sentido em afirmar que sejam verdadeiras ou falsas.” Álgebra das Proposições A álgebra das proposições é utilizada para reduzir/modificar expressões compostas, ou seja, também são conhecidas como propriedades. Álgebra das Proposições Implicações Notáveis �Adição �Simplificação Disjuntiva �Simplificação �Absorção �Modus Ponens �Modus Tollens �Silogismo disjuntivo Álgebra das Proposições Adição Ocorre junto ao conectivo OU “v” P⇒P v Q Q⇒P v Q Simplificação Ocorre junto ao conectivo E “^” P^ Q ⇒ P P^ Q ⇒ Q Implicações Notáveis Simplificação disjuntiva Utilizada nos casos em que uma das proposições ocorre de forma contraditória e com um conectivo OU “v” sendo simplificada (P v Q) ^ (P v ~Q) ⇒ P Sou feliz ou me demito e Sou feliz ou não me demito. Logo, sou feliz. Implicações Notáveis Absorção Uma mesma proposição simples ocorre numa proposição condicional, sendo suficiente então pode ser omitida (absorvida) P → Q ⇒ P → (P ^ Q) Se corro então pulo. Logo, se corro, então corro e pulo. Implicações Notáveis Modus Ponens Baseada em proposição condicional (P → Q) ^ P ⇒ Q Modus Tollens Baseada em proposição contrapositiva de condicional (P → Q) ^ ~Q ⇒ ~P Implicações Notáveis Silogismo disjuntivo Ocorre a partir de uma disjunção (conectivo “OU”) em que uma das proposições simples é contrariada validando a outra proposição (P v Q) ^ ~P ⇒ Q (P v Q) ^ ~Q ⇒ P Implicações Notáveis Quadro de Equivalências Método Dedutivo O Método dedutivo também é um método para demonstração de implicações e equivalências, utilizando das propriedades, leis e regras. Método Dedutivo No método dedutivo, as equivalências relativas desempenham um papel importante nas equivalências lógicas. As proposições (simples ou compostas) podem ser substituídas por P,Q,R,T,C Método Dedutivo Problema: O Número de linhas cresce muito rapidamente, à medida que aumenta o número de proposições simples envolvidas no argumento. Com 10 proposições a tabela terá 1024 linhas e com 11 são 2048. Método Dedutivo O Método Dedutivo utiliza as implicações e equivalência notáveis apresentadas, também chamados de regras de inferência A validade destes pode ser verificada pela construção de tabelas verdade de cada argumento Método Dedutivo Exemplo: Simplificar (p → (~p → q) (p → (~p → q) p → (~~p v q) ~p v (p v q) (~p v p) v (~p v q) T v (~p v q) T Método Dedutivo A implicação do exemplo anterior representa uma tautologia, pois a propriedade distributiva gera (~p v p), ou seja, ela é obrigatoriamente forçada a gerar um valor verdadeiro. Método Dedutivo Ao juntar-se com o operador “v” (OU), ela obriga a proposição formada a gerar um valor verdadeiro na resolução Caso a proposição fosse T^(~p v q) então o valor lógico é (~p v q) pois, o valor mesmo que falso, juntado com (~p v q)será (~p v q). Síntese Raciocínio Lógico � Álgebra das proposições �Método Dedutivo Referências de Apoio � SANT'ANNA, A. S. O que é um Axioma. Capítulo 3 - Barueri SP: Editora Manoele , 2003. 6 Raciocínio Lógico Aula 6 Prof. André Roberto Guerra � Argumentos e regras de inferência �Validade mediante tabelas-verdade, regras de inferência e equivalências Organização da Aula Argumentos Um grupo de proposições iniciais que redunda em outra proposição final, consequente das primeiras! Argumento é a relação que associa um conjunto de proposições (p1, p2,... pn), chamadas premissas do argumento, a uma proposição “c”, chamada de conclusão do argumento. Os termos premissa e conclusão podem ser substituídos pelos correspondentes hipótese e tese. São exemplos de argumentos: p1:Todos cearenses são humoristas p2:Todos humoristas gostam de música. C:Todos os cearenses gostam de música. Argumentos O tipo de argumento ilustrado no exemplo é chamado silogismo. Silogismo é o argumento formado por duas ou mais premissas e a respectiva conclusão. O estudo dos argumentos lógicos verifica se eles são válidos ou inválidos! Argumentos Argumentos Válidos Um argumento é válido (ou ainda legítimo ou bem construído), quando sua conclusão é uma consequência obrigatória do seu conjunto de premissas. As premissas e a conclusão podem ser visivelmente falsas (e até absurdas!), e o argumento, ainda assim, será considerado válido. Isto pode ocorrer porque, na Lógica, o estudo dos argumentos não leva em conta a verdade ou a falsidade das premissas que compõem o argumento, mas tão somente a validade deste. Argumentos Válidos Exemplo: O silogismo... p1: Todos os homens são pássaros. p2: Nenhum pássaro é animal. C: Portanto, nenhum homem é animal. está bem construído, portanto é um argumento válido, muito embora a veracidade das premissas e da conclusão sejam questionáveis. Argumentos Válidos 9 A construção do argumento é analisada e não o seu conteúdo! Se a construção está correta então o argumento é válido, independentemente do conteúdo das premissas ou da conclusão! Argumentos Válidos Em um argumento válido, as premissas são consideradas provas evidentes da verdade da conclusão, caso contrário não é válido. Quando é válido, a conclusão é uma consequência lógica das premissas, ou ainda, a conclusão é uma inferência decorrente das premissas Argumentos Válidos A lógica se preocupa com o relacionamento entre as premissas e a conclusão, ou seja, com a estrutura e a forma do raciocínio. A verdade do conteúdo de cada premissa e da conclusão é estudo das demais ciências. Argumentos Válidos A validade do argumento está diretamente ligada à forma pela qual ele se apresenta. (Lógica Formal – estuda a forma dos argumentos). Argumentos Válidos A Lógica Formal Clássica só estuda Argumentos Dedutivos, verificando se são ou não válidos. Verdade e Falsidade: são propriedades das proposições, nunca dos argumentos. Argumentos Válidos Validade ou Invalidade: são propriedades dos argumentos dedutivos que dizem respeito a inferência ser ou não válida (raciocínio ser ou não correto). Os conceitos de argumento válido ou inválido são independentes da verdade ou falsidade de suas premissas e conclusão. Argumentos Válidos Qualquer combinação de valores verdade entre as premissas e a conclusão é possível, exceto que nenhum argumento dedutivo válido tenha as premissas verdadeiras e a conclusão falsa. Um argumento dedutivo no qual todas as premissas são verdadeiras é dito Argumento Correto, evidentemente sua conclusão também é verdadeira. Argumentos Válidos Inferência é a relação que permite passar das premissas para a conclusão (um “encadeamento lógico”). A palavra inferência vem do latim, Inferre, e significa “conduzir para”. Regras de Inferência O objeto de estudo da lógica é determinar se a conclusão de um argumento é ou não decorrente das premissas (uma inferência). Mecanismos para se obter conclusões sobre outras assertivas, que juntas formam os passos de uma prova. Regras de Inferência Modus Ponens Baseada em proposição condicional (P→Q)^P⇒Q ou (P^P→Q)→Q É a base das regras de inferência e dada pela tautologia indicada. Dada uma implicação, se ela e sua hipótese são verdadeiras então sua consequência também o é. Implicações e Equivalências Notáveis Apresente argumento válido para: ~p ∧ q, r → p, ~r → s, s → t ⊢ t. (1) ~p ∧ q - hipótese (2) ~p - simplificação de (1) (3) r → p - hipótese (4) ~r -modus tollens usando (2 e 3) (5) ~r → s - hipótese (6) s -modus ponens usando (4 e 5) (7) s → t - hipótese (8) t - modus ponens usando (6 e 7) Implicações e Equivalências Notáveis Validade de um Argumento Todo argumento tem um valor lógico, aquí utilizado V se é válido (correto, legítimo) ou F se é um sofisma (incorreto, ilegítimo). Validade de um Argumento As premissas dos argumentos são verdadeiras ou, pelo menos admitidas como tal. Aliás, a lógica só se preocupa com a validade dos argumentos e não com a verdade ou falsidade das premissas e das conclusões. Validade de um Argumento A validade de um argumento depende exclusivamente da relação existente entre as premissas e a conclusão. Portanto, afirmar que um dado argumento é válido significa afirmar que as premissas estão de tal modo relacionadas com a conclusão que não é possível ter a conclusão falsa se as premissas são verdadeiras. Critérios de Validade de um Argumento Teorema – Um argumento P1, P2, …, Pn Q é válido se e somente se a condicional: (P1 ^ P2 ^…^ Pn) →Q é tautológica. Exemplificando, do argumento válido P ⇒ p V q segue-se a validade dos argumentos: (~p ^ r) ⇒ (~p ^ r) V (~s→ r) (p→ r v s) ⇒ (p→ r v s) V (~r→ s) pois ambos têm a mesma forma Critérios de Validade de um Argumento Portanto, a validade ou não de um argumento depende apenas da sua forma e não do seu conteúdo ou da verdade ou falsidade das proposições que o integram. Critérios de Validade de um Argumento Argumentos Válidos Fundamentais Os argumentos válidos abaixo, são conhecidos como argumentos fundamentais: (a) Adição (AD) (i) p ⇒ p ν q (ii) p ⇒ q ν p; (b) Simplificação (SIMP) (i) p Λ q ⇒ p (ii) p Λ q ⇒ q; (c) Conjunção (CONJ) (i) p, q ⇒ p Λ q (ii) p, q ⇒ q Λ p; (d) Absorção (ABS) p → q ⇒ p → (p Λ q); (e) Modus ponens (MP) p → q , p ⇒ q; (f) Modus tollens (MT) p → q , ~q ⇒ ~p; Argumentos Válidos Fundamentais (g) Silogismo disjuntivo (SD) (i) p ν q, ~p ⇒ q (ii) p ν q, ~q ⇒ p; (h) Silogismo hipotético (SH) p → q, q → r ⇒ p → r; (i) Dilema construtivo (DC) p → q, r → s, p ν r ⇒ q ν s; (j) Dilema destrutivo (DD) p→ q, r→ s, ~q ν ~s ⇒~p ν ~r; Argumentos Válidos Fundamentais A validade dos dez argumentos pode ser verificada (faça isso) através da construção das tabelas-verdade de cada argumento. Os dez argumentos válidos fundamentais acima são também chamados de “regras de inferência”. Argumentos Válidos Fundamentais A validade de um argumento pode ser demonstrada através da Construção de tabelas- verdade ou utilizando as regras de inferência. Validade de Argumento Exemplo: Demonstre que os argumentos abaixo são válidos, utilizando tabela- verdade e as regras de inferência: • Se o programa é eficiente, ele executará rapidamente. • O programa é eficiente ou tem um erro. • O programa não executa rapidamente. Portanto o programa tem um erro; Validadede Argumento - Inicialmente, o argumento é traduzido para linguagem simbólica. Consideram-se as proposições simples: p: O programa é eficiente, q: O programa executa rápido e r: O programa tem um erro. Validade de Argumento Obtem-se então, na linguagem simbólica, as premissas p → q, p ∨ r, ~q e a conclusão r, ou seja, (p → q) ∧ (p ν r) ∧ (~q) ⇒ r Validade de Argumento Validade mediante tabela-verdade (p → q) ∧ (p ν r) ∧ (~q) ⇒ r p q r p → q p ∨ r ~q r V V V V V F V V V F V V F F V F V F V V V V F F F V V F F V V V V F V F V F V F F F F F V V V V V F F F V F V F Validade mediante regras de inferência As premissas são (1) p → q (2) p ∨ r (3) ~q (4) ~p modus tollens nas premissas (1) e (3) (5) r silogismo disjuntivo nas premissas (2) e (4); Portanto, é possível concluir a proposição “r” das premissas (1), (2) e (3), ou seja, o argumento é válido. Validade mediante regras de inferência � Se Graham está no campo de golfe, então Harvey está de serviço no hospital e Ives deve ter mudado sua política. � Harvey não está de serviço no hospital. Portanto, Graham não está no campo de golfe; Validade mediante regras de inferência Inicialmente, o argumento é traduzido para linguagem simbólica. Consideram-se as proposições simples: p: Graham está no campo de golfe, q: Harvey está de serviço no hospital, e r: Ives mudou sua política. Validade mediante regras de inferência Obtem-se então, na linguagem simbólica, as premissas p → (q Λ r), ~q e a conclusão ~p, ou seja, (p → (q Λ r) ∧ ~q ⇒ ~p Validade mediante regras de inferência (p → (q Λ r) ∧ ~q ⇒ ~p p q r q Λ r p → (q Λ r) ~q ~p V V V V V F F V V F F F F F V F V F F V F V F F F F V F F V V V V F V F V F F V F V F F V F V V V F F F F V V V Validade mediante tabela-verdade As premissas são (1) p → q Λ R (2) ~q (3) ~q ν ~r adição na premissa (2); (4) ~( q Λ r) lei de De Morgan da disjunção na premissa (3); Validade mediante regras de inferência (5) ~p modus tollens nas premissas (1) e (4) Portanto é possível concluir a proposição “~p” das premissas (1) e (2), ou seja, o argumento é válido Validade mediante regras de inferência Síntese � Argumentos e regras de inferência � Validade mediante tabelas-verdade, regras de inferência e equivalências Referências de Apoio � SANT'ANNA, A. S. O que é um Axioma. Capítulo 3 - Barueri SP: Editora Manoele , 2003. Raciocínio Lógico Aula Prática 1 Prof. André Roberto Guerra Organização da Aula Aula Prática 1 (Aula 7) • Exercícios de fixação • Solução de problemas Exercício de fixação Construção de Tabela Verdade Cálculo Proposicional da fórmula apresentada na Aula Teórica 1: (((p v q) ^ (~r)) (p (~q))) Exercício de fixação (((p v q) ^ (~r)) (p (~q))) Síntese Aula Prática 1 (Aula 7) • Exercícios de fixação • Solução de problemas Referências de Apoio � SANT'ANNA, A. S. O que é um Axioma. Capítulo 3 - Barueri SP: Editora Manoele , 2003.
Compartilhar