Lógica Computacional 1
Turma B

Considere um ilha onde moram apenas dois tipos de pessoas:

1. Honestas: que sempre falam a verdade;
2. Desonestas: que sempre mentem.

Um viajante, ao passar por esta ilha, encontra três moradores chamados \(A\), \(B\) e \(C\). O viajante então pergunta para o morador \(A\): "Você é honesto ou desonesto?" \(A\) responde algo incompreensível, e o viajante pergunta para \(B\): "O que ele disse?" \(B\) então responde: "Ele disse que é desonesto". Neste momento \(C\) se manifesta: "Não acredite nisto! Isto é uma mentira!"

Questão: \(C\) é honesto ou desonesto?

O curso de Lógica Computacional visa proporcionar ao estudante os fundamentos da lógica matemática, mas com foco na resolução de problemas relevantes para a Ciência da Computação. Neste sentido, a abordagem será na dedução lógica, ou seja, na construção de provas a serem exploradas via dois sistemas dedutivos: a Dedução Natural (DN) e o Cálculo de Sequentes (CS).

Em linhas gerais, um sistema dedutivo nos permite inferir novas informações a partir de informações já existentes. Por exemplo, suponha que tenhamos as seguintes informações:

• Se \(\phi\) então \(\psi\), que podemos representar simbolicamente por \(\phi \to \psi\).
• \(\phi\)

Então podemos inferir \(\psi\).

Neste caso, o conhecimento existente é composto de duas informações, a saber: \(\phi\) e \(\phi \to \psi\); e a nova informação obtida é \(\psi\).

O processo utilizado para inferir \(\psi\) a partir de \(\phi\) e \(\phi \to \psi\) é conhecido como modus ponens (MP). Esquematicamente, podemos representar este processo da seguite forma:

\[\inferrule*[Right=(MP)]{\phi\to \psi \and \phi}{\psi}\]

A representação acima é conhecida como regra de inferência. Uma regra de inferência é um esquema utilizado para representar argumentos válidos, e é composta de duas partes separadas por uma linha horizontal. Em cima da linha são colocados os fatos já conhecidos, que chamamos de hipóteses, e abaixo da linha colocamos a nova informação inferida a partir das hipóteses. Esta nova informação é chamada de conclusão. Como veremos, as regras de inferência serão utilizadas de forma sistemática neste curso. Por exemplo, no esquena a seguir, a regra de inferência \(R\) tem \(h_1, h_2, \ldots, h_n\) como hipóteses, e \(c\) como conclusão:

\[\inferrule*[Right=(R)]{h_1\ h_2\ \ldots\ h_n}{c}\]

Agora precisamos dizer como podemos representar as nossas hipóteses e nossa conclusão. A utilização de linguagem natural para isto (como o Português, por exemplo) não é conveniente porque linguagens naturais são ambíguas. Iniciaremos então com uma linguagem bem simples baseada na noção de proposição. Uma proposição é simplesmente um fato que pode ser qualificado como verdadeiro ou falso.

A lógica proposicional é baseada na noção de proposição, i.e. uma afirmação que pode ser qualificada como verdadeira ou falsa. Assim, são proposições as afirmações:

• \(2 \leq 3\);
• \(0 =1\);
• João tem 23 anos;
• A soma de dois números ímpares é um número par.

No entanto, existem afirmações que não são proposições:

• Qual é o seu nome?
• Feche a porta!

Utilizaremos as letras \(p\), \(q\) e \(r\) (com ou sem subíndices) para denotar proposições arbitrárias. Novas proposições podem ser construídas por meio dos conectivos lógicos: