Baixe o app para aproveitar ainda mais
Prévia do material em texto
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/>.
Compartilhar