Informatica

´ Logica EI ´ Engenharia Informatica 2012-2013

Notas de apoio ` UC a
(em prepara¸˜o) ca

´ ´ ´ Claudia Mendes Araujo, Jose Carlos Esp´ ırito Santo, Lu´ Pinto ıs ´ Departamento de Matematica e Aplicacoes ¸˜ Universidade do Minho 9 de Maio de 2013

2

Cap´ ıtulo 1

Indu¸˜o e Recurs˜o Estruturais ca a
Exemplo 1: Seja C o menor1 subconjunto de N0 que satisfaz as seguintes condi¸oes: c˜ 1. 0 ∈ C; 2. para todo n ∈ N0 , se n ∈ C, ent˜o n + 2 ∈ C. a Exemplos de elementos de C s˜o: 0, 2, 4. De facto: a
ˆ 0 ´ um elemento de C, por C satisfazer 1.; e ˆ sabendo que 0 ∈ C, por C satisfazer 2., segue 0 + 2 = 2 ∈ C; ˆ sabendo que 2 ∈ C, por C satisfazer 2., segue 2 + 2 = 4 ∈ C.

Adiante (e como ´ f´cil de intuir), mostraremos que C ´ o conjunto dos n´meros pares. e a e u Esta forma de definir o conjunto C ´ um caso particular das chamadas defini¸˜es e co indutivas de conjuntos, um mecanismo muito util para definir conjuntos (e de uso ´ frequente em Ciˆncias de Computa¸ao), que apresentaremos de seguida. e c˜ Defini¸˜o 2: Sejam X um conjunto e B um subconjunto n˜o vazio de X. Seja O ca a um conjunto de opera¸˜es em X (i.e., fun¸oes do tipo X n −→ X, com n ∈ N). Um co c˜ subconjunto I de X tal que i) B ⊆ I e ii) I ´ fechado para as opera¸oes de O (i.e., as opera¸˜es de O quando aplicadas e c˜ co a elementos de I produzem elementos de I ou, por outras palavras, para cada opera¸ao f : X n −→ X de O e para cada (x1 , ..., xn ) ∈ I n , f (x1 , ..., xn ) ∈ I) c˜ ´ chamado um conjunto indutivo, sobre X, de base B e conjunto de opera¸˜es O. e co Observa¸˜o 3: Admitamos as suposi¸oes da defini¸ao anterior. Ent˜o: ca c˜ c˜ a
1

Dizemos que um conjunto A ´ mais pequeno que um conjunto B quando A ⊆ B e

3

4

˜ CAP´ ITULO 1. INDUCAO E RECURSAO ESTRUTURAIS ¸˜

i) X ´ um conjunto indutivo para qualquer O; e ii) B ´ um conjunto indutivo quando O = ∅. e Donde podemos concluir que, em geral, os subconjuntos indutivos de um conjunto, para uma dada base e um dado conjunto de