Lógica para Computação
Aula 1: Introdução
DAINF-UTFPR
1.1
Prof. Ricardo Dutra da Silva
Noções Iniciais
A Lógica analisa estruturas e métodos de raciocı́nio. Podemos pensar na Lógica como uma
ciência de raciocinar. Nós, humanos, somos bastante hábeis em representar e manipular
informações lógicas. Com tais manipulações, somos capazes de inferir novas informações ou
verificar a veracidade de outras.
Exemplo 1.1
Considere um jogo no qual temos cinco cubos coloridos empilhados sobre uma mesa.
Ignoramos a disposição como os cubos estão empilhados (estamos vendados, quem sabe?).
No entanto, alguns fatos sobre como os cubos estão arranjados na pilha são fornecidos.
Nossa tarefa é determinar a ordem em que os cubos estão dispostos.
As premissas são as seguintes.
1. O bloco vermelho está sobre o bloco verde.
2. O bloco verde está em algum lugar acima do bloco azul.
3. O bloco verde não está sobre o bloco azul.
4. O bloco amarelo está sobre o bloco verde ou sobre o bloco azul.
5. Há algum bloco sobre o bloco preto.
6. O bloco preto não está sobre o bloco amarelo.
Somos capazes de derivar conclusões a partir das premissas.
• O bloco vermelho está sobre o bloco verde.
• O bloco verde está sobre o bloco amarelo.
1
2
Aula 1: Introdução
• O bloco amarelo está sobre o bloco azul
• O bloco azul está sobre o bloco preto.
• O bloco preto está diretamente sobre a mesa.
Nem sempre é simples alcançar conclusões ou, quando são dadas, entender o porquê de
certas conclusões. Por isso, é útil que uma prova seja fornecida.
Exemplo 1.2
No Exemplo 1.1, podemos provar informalmente que o bloco amarelo está sobre o bloco
azul.
Nos é dito que o bloco amarelo está sobre o bloco verde ou sobre o bloco azul, mas
também que o bloco vermelho está sobre o bloco verde. Assumindo que pode haver apenas
um bloco sobre outro, podemos concluir que o bloco amarelo não pode estar sobre o bloco
verde. Por eliminação, o bloco amarelo deve estar sobre o bloco azul.
Em uma prova precisamos reconhecer certos passos como imediatamente óbvios. Esses
passos e as conclusões obtidas devem também ser independentes do conteúdo expresso. Na
Lógica, a forma sobrepõe o conteúdo. O que importa é a estrutura (forma) e não sobre o
que estamos falando (blocos, carros, pessoas, etc.).
Exemplo 1.3
Suponha os fatos a seguir.
1. Todos os Civics são Hondas.
2. Todos os Hondas são Japoneses.
Facilmente podemos concluir:
3. Portanto, todos os Civics são Japoneses.
Concluı́mos a partir do Exemplo 1.3 que todos os Civics são Japoneses. Analise agora o
Exemplo 1.4.
Exemplo 1.4
Dado que:
1.1. NOÇÕES INICIAIS
3
1. Todos os Cartos são Lordos.
2. Todos os Lordos são Misus.
Concluı́mos:
3. Portanto, todos os Cartos são Misus.
Mesmo sem saber o que são Cartos, Lordos ou Misus, conseguimos chegar à conclusão de
que todos os Cartos são Misus. Os Exemplos 1.3 e 1.4 compartilham uma mesma estrutura,
uma mesma forma ou regra de raciocı́nio:
1. Todos os x são y.
2. Todos os y são z.
3. Portanto, todos os x são z.
É importante saber as regras que nos levam a conclusões corretas.
Exemplo 1.5
Considere o padrão abaixo:
1. Todos os x são y.
2. Alguns y são z.
3. Portanto, alguns x são z.
Vamos substituir x por “Volkswagen”, y por “carros” e z por “produzidos no Brasil”.
Chegamos a uma conclusão correta.
1. Todos os Volkswagen são carros.
2. Alguns carros são produzidos no Brasil.
3. Portanto, alguns Volkswagen são produzidos no Brasil.
Agora, vamos substituir x por “Volkswagen”, y por “carros” e z por “Palios”. Chegamos a uma conclusão incorreta.
4
Aula 1: Introdução
1. Todos os Volkswagen são carros.
2. Alguns carros são Palios.
3. Portanto, alguns Volkswagen são Palios.
O Exemplo 1.5 apresenta uma regra que leva a conclusões incorretas. Não poderı́amos
assumir, portanto, tal regra em um sistema para provas. Uma regra deve sempre levar a
conclusões corretas.
1.2
Lógica para Computação
Nosso interesse é formalizar linguagens e regras que permitam automatizar o raciocı́nio.
Queremos saber quais regras podem ser computadas e também quais podem ser computadas
de forma eficiente. Estudaremos no curso duas dessas linguagens e diferentes conjuntos de
regras.
Em geral, estaremos interessados em especificar uma linguagem para expressar conhecimentos e estudar métodos que verifiquem fórmulas ou que possibilitem deduzir novas
fórmulas.
A lógica para computação tem aplicações em diferentes áreas.
Matemática Programas são usados para conferir ou mesmo produzir provas matemáticas.
Sistemas de Banco de Dados Restrições lógicas são definidas para testar a integridade
de bancos de dados.
Análise de Software Expressões lógicas são produzidas para verificar propriedades de
programas, tais como corretude e complexidade.
Engenharia de Hardware A Lógica formal é usada, por exemplo, para validar projetos
de hardware e diagnosticar falhas.