Lógica Proposicional: Semântica

Redução ao Absurdo

Fórmula Possível, Contraditória e Válida

Reductio ad absurdum (latim para "redução ao absurdo", provavelmente originário do grego εις άτοπον απαγωγη, transl. e eis átopon apagoge), que significaria algo próximo a "redução ao impossível".

Assume uma ou mais hipóteses e, a partir destas, deriva uma consequência absurda ou ridícula, e então conclui que a suposição original deve estar errada.

O argumento se vale do princípio da não-contradição (uma proposição não pode ser, ao mesmo tempo, verdadeira e falsa) e do princípio do terceiro excluído (uma proposição é verdadeira ou é falsa, não existindo uma terceira possibilidade).

Uma fórmula possível é uma fórmula que pode ser interpretada como verdadeira. É possível encontrar uma forma de atribuir valores de verdade aos símbolos proposicionais que faz com que a fórmula seja interpretada como verdadeira.

ex: p <--> q |= (p --> q) ^ (q --> p)

Fórmula Contraditória que nunca pode ser interpretada como verdadeira. Não é possível encontrar uma interpretação para os símbolos proposicionais que permita interpretar como verdadeira esta fórmula.

ex: |=/= p ^ ¬p

Fórmula válida (ou tautologia) é uma fórmula que é sempre interpretada como verdadeira. qualquer que seja a interpretação para os símbolos proposicionais que se considere, a fórmula é sempre interpretada como verdadeira

ex: |= p v ¬p

Explicando mais um pouco...

Caso assuma que uma dada fórmula lógica não é consequência semântica, então temos G |=/= A. Ao realizar a valoração correta sobre as fórmulas e encontrarmos um absurdo, então o que foi assumido está errado, logo, temos G |= A. Caso contrário, ou seja, não encontramos um absurdo, temos um contra-modelo para a fórmula e de fato temos

G |=/= A.

Ex: {p, p --> q} |= q

• Pela definição de consequência semântica temos: q deve ser verdadeiro para todas as fórmulas contidas em {p, p -->q}.
• Assuma então, {p, p-->q} |=/= q temos então que há alguma fórmula verdadeira em {p, p-->q} verdadeira e q sendo falso, logo temos:
• (1) V({p, p-->q}) = 1
• (2) V(q) = 0
• De (1) temos (3) V(p) = 1
• De (1) temos (4) V(p-->q) = 1
• De (4) e (2) e pela tabela da implicação temos (5) V(p) = 0
• De (5) e (3) temos a redução ao absurdo.
• Portanto {p, p-->q} |= q

Estrutura de interpretação sobre P

Referência Bibliográfica

Cap. Lógica Clássica Proposicional. João Marcos Almeida. Disponível em: http://www.dimap.ufrn.br/%7Ejmarcos/courses/LC/Cap1.pdf

Definição: Uma estrutura de interpretação (ou valoração) sobre o conjunto de símbolos proposicinais P é uma função V : P -> {0, 1}.

Lógica Proposicional: Semântica

Consequência lógica. Disponível em: http://pt.wikipedia.org/wiki/Consequ%C3%AAncia_l%C3%B3gica

Redução ao Absurdo. Disponível em: http://pt.wikipedia.org/wiki/Reductio_ad_absurdum

Thiago Medeiros Barros

Consequência Lógica

Trata-se de uma relação entre um conjunto de sentenças (ou proposições) e uma sentença (proposição), na qual o primeiro acarreta o segundo.

A consequência lógica é a relação entre as premissas e a conclusão de um argumento válido.

G irá representar um conjunto arbitrário de premissas e A uma arbitrária conclusão arbitrária

Uma fórmula A é uma consequência semântica de um conjunto de fórmulas G .

G |= A,

Se e somente se nenhuma interpretação I faz com que todos os membros de G sejam verdadeiros e A seja falso.

Contradição

Se houver qualquer qualquer premissa que seja verdadeira no conjunto G, para uma conclusão falsa em A, temos |=/=

ex: {p, p --> q |= q} e {p, p --> q} |=/= r