Apostila de Lógica - UTFPR - Aula 1

Lógica para Computação
Aula 1: Introdução
DAINF-UTFPR Prof. Ricardo Dutra da Silva
1.1 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”. Che-
gamos 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 conhe-
cimentos 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.

Apostila de Lógica - UTFPR - Aula 1

Enviado por

Direitos autorais:

Formatos disponíveis

Apostila de Lógica - UTFPR - Aula 1

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Apostila de Lógica - UTFPR - Aula 1

Enviado por

Direitos autorais:

Formatos disponíveis

Lógica para Computação

1.1 Noções Iniciais

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.

• O bloco amarelo está sobre o bloco azul

• O bloco azul está sobre o bloco preto.

• O bloco preto está diretamente sobre a mesa.

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.

1. Todos os Cartos são Lordos.

2. Todos os Lordos são Misus.

3. Portanto, todos os Cartos são Misus.

3. Portanto, todos os x são z.

É importante saber as regras que nos levam a conclusões corretas.

3. Portanto, alguns x são z.

Vamos substituir x por “Volkswagen”, y por “carros” e z por “produzidos no Brasil”.

1. Todos os Volkswagen são carros.

2. Alguns carros são produzidos no Brasil.

3. Portanto, alguns Volkswagen são produzidos no Brasil.

1. Todos os Volkswagen são carros.

2. Alguns carros são Palios.

3. Portanto, alguns Volkswagen são Palios.

1.2 Lógica para Computação

Análise de Software Expressões lógicas são produzidas para verificar propriedades de

Você também pode gostar