00 exercicios enunciados

Exercícios de Lógica para Programação
Ana Cardoso-Cachopo
Fevereiro de 2013

CONTEÚDO

1

Conteúdo
1

Argumentos e Validade

3

2

Lógica Proposicional — Sistema de Dedução Natural

4

3

Lógica Proposicional — Tabelas de Verdade

6

4

Lógica Proposicional — Resolução

7

5

Lógica Proposicional — BDDs

8

6

Lógica Proposicional — OBDDs

10

7

Lógica Proposicional — SAT

11

8

Lógica de Primeira Ordem — Representação; Sistema de Dedução Natural

13

9

Lógica de Primeira Ordem — Sistema Semântico

16

10 Lógica de Primeira Ordem — Resolução

20

11 Lógica de Primeira Ordem — Resolução SLD; Árvores SLD

22

12 Prolog — Árvores de Refutação; Listas

24

13 Prolog — Operadores Pré-definidos

26

14 Prolog — Corte; Negação

28

2

CONTEÚDO

Prefácio
Este documento contém uma compilação de exercícios para a disciplina de
Lógica para Programação da LEIC.
A maior parte dos exercícios foi criada por mim especificamente para as aulas práticas ou para as provas de avaliação da disciplina e outros foram tirados de livros ou artigos acerca da matéria em questão.
Existem dois exercícios cujo enunciado foi feito pelo Professor João Pavão
Martins nas aulas sobre os sistemas de dedução natural da lógica proposicional e da lógica de primeira ordem. Esses exercícios estão assinalados com a etiqueta (JPM).
O Professor João Cachopo, para além de discutir comigo algumas das respostas dos exercícios, ajudou-me a fazer em LaTeX as figuras dos vários capítulos, tornando esta compilação (muito) mais apresentável.
Obviamente, a responsabilidade por quaisquer erros ou gralhas que esta compilação de exercícios possa ter é inteiramente minha.

3

1

Argumentos e Validade

Exercício 1.1
Usando apenas a informação que está explícita, diga, justificando, se os seguintes argumentos são válidos ou são inválidos:
1. Peregrino Cinzento é Gandalf
Mithrandir é Gandalf
∴ Peregrino Cinzento é Mithrandir
2. Mithrandir é um feiticeiro
Mithrandir é Gandalf
∴ Gandalf é um feiticeiro
3. Os orcs são