Lógica para Computação - lógica simbólica, sintaxe e semântica, conjunto das expressões legítimas, conjunto indutivos, expressões bem formadas - aula3 log cin

Prévia do material em texto

Lógica Matemática 
Para Computação 
Lógica Simbólica 
Sintaxe e Semântica 
 
 Sintaxe: é preciso definir as regras ``sintáticas´´ 
de representação de sentenças. 
 
 Semântica: é preciso definir um método de 
``voltar´´ do símbolo para o seu significado. 
 
 
 
 
Lógica Simbólica 
Sintaxe 
 
 Qual é o alfabeto da aritmética? 
 
 
 
 
 
Variáveis (x,y,z,...) 
Operadores (,,,) 
Parênteses ((),[],{}) 
Constantes (0,1,2,...) 
Σ = 
Lógica Simbólica 
Sintaxe 
 
 Qual é o alfabeto da lógica? 
 
 
 
 
 
Variáveis (x,y,z,...) 
Operadores (,,,) 
Parênteses (``(´´,``)´´) 
Constantes (0,1) 
Σ = 
Como definir o conjunto de todas as palavras 
sobre Σ que são expressões legítimas? 
Sintaxe 
Conjunto das expressões legítimas da aritmética 
 Definição indutiva 
 
 
Seja V= {x0, x1, ...} um conjunto enumerável de variáveis, 
X = V  {0,1,2,...} e seja + e * dois símbolos de funções binárias. Além 
disso, “(“ denota o parêntese da esquerda e “)” o da direita. O conjunto 
EXPR das expressões aritméticas definidas usando as variáveis de V, as 
constantes {0,1,2,...} e os operadores + e * é frequentemente definido 
como: 
(1) Toda variável em V e constante em {0,1,2..} é uma expressão 
aritmética; 
(2) Se E1 e E2 são expressões aritméticas, então (E1+E2) e (E1*E2) 
também são expressões aritméticas. 
Lógica Simbólica 
Conjunto das expressões legítimas 
1. Toda constante é uma expressão legítima; 
2. toda variável é uma expressão legítima; 
3. se w for uma expressão legítima, então (w) é uma expressão legítima; 
4. se w1 e w2 forem expressões legítimas então (w1w2) é uma expressão 
legítima; 
5. se w1 e w2 forem expressões legítimas então (w1w2) é uma expressão 
legítima; 
6. se w1 e w2 forem expressões legítimas então (w1w2) é uma expressão 
legítima. 
Lógica Simbólica 
Sintaxe 
 Qual o problema com essas definições? 
 
 Não está claro que as cláusulas definem o menor 
conjunto com as propriedades dadas. 
 
 O universo de todas as possíveis expressões não é 
definido. 
 
 Os operadores não estão claramente definidos. 
 
Lógica Simbólica 
Sintaxe 
 
 
 Como definir o conjunto de todas as expressões 
legítimas da lógica simbólica (fórmulas bem 
formadas)? 
Lógica Simbólica 
Sintaxe 
 Buscando uma nova definição 
 Seja Σ o alfabeto V  {0,1, ,,,,(,)}; 
 Seja A = Σ* o conjunto de todas cadeias sobre Σ. 
 O conjunto A é o universo de todas as expressões 
 Observe que A possui muitas cadeias que não são 
expressões legítimas. 
 A proposta é definir EXPR  Σ* . 
 
 
 
Lógica Simbólica 
Sintaxe 
 Buscando uma nova definição 
 Seja Σ o alfabeto V  {0,1, ,,,,(,)}; 
 Seja A = Σ* o conjunto de todas cadeias sobre Σ. 
 O conjunto A é o universo de todas as expressões 
 Observe que A possui muitas cadeias que não são 
expressões legítimas. 
 A proposta é definir EXPR  Σ* . 
 
 
 
Lógica Simbólica 
Sintaxe 
Σ* = conjunto de todas as palavras 
(cadeias) 
 
<expr> = conjunto das expressões 
legítimas 
 
X = conjunto das variáveis e 
constantes 
X 
<expr> 
A=Σ* 
Lógica Proposicional 
Sintaxe 
Definimos o conjunto F de funções como a seguir: 
 Definimos o conjunto F de funções como a seguir: 
 
 
 Observe que essas funções são definidas sobre todas 
as cadeias em A=Σ* , podendo dessa forma produzir 
expressões que não são legítimas. 
 
 
Lógica Proposicional 
Conjunto das expressões legítimas 
1. Toda constante é uma expressão legítima; 
2. toda variável é uma expressão legítima; 
3. se w for uma expressão legítima, então (w) 
 é uma expressão legítima; 
4. se w1 e w2 forem expressões legítimas então 
 (w1w2) é uma expressão legítima; 
5. se w1 e w2 forem expressões legítimas então 
 (w1w2) é uma expressão legítima; 
6. se w1 e w2 forem expressões legítimas então 
 (w1w2) é uma expressão legítima. 
 É o menor conjunto de palavras sobre Σ tais que: 
 
Lógica Proposicional 
Conjunto das expressões legítimas 
 Matematicamente, <expr> (o conjunto das 
expressões legítmas da lógica simbólica) é o fecho 
indutivo do conjunto base X = variáveis  
constantes sob conjunto das funções F = {f1,f2,f3,f4}. 
 
 
 
 
Conjuntos Indutivos 
 Suponha que temos um conjunto A e um 
subconjunto próprio X de A 
 
 
 
F 
X 
A 
f  F 
 
f: An  A 
 Imagine também que nos é dado um conjunto de 
funções sobre A, cada uma com sua aridade. 
 
 
 
 
Conjuntos Indutivos 
F 
X 
A 
f  F 
 
f: An  A 
 Um dado subconjunto Y de A é indutivo sobre X e F 
se: 
 
1. Y contem X; 
2. Y é fechado sob as funções de F (se w1,...,wn  Y, f  
F e aridade de f=n  f(w1,...,wn)  Y (os argumentos e 
o resultado pertencem ao mesmo conjunto) 
 
 
 
Sintaxe da Lógica Proposicional 
Fecho Indutivo 
X 
<expr> 
A=Σ* F F 
 O fecho indutivo de X sob F é o menor conjunto 
que contem X e é fechado sob as funções de F 
 
 
 
 
 
 EXPR é definido como o menor subconjunto de A 
que contem X e é fechado sob as funções de F. 
 
 
 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 Desejamos caracterizar matematicamente o conjunto 
das palavras sobre o alfabeto: 
 Σ  variáveis  constantes  (,)  ,,,, 
 que são de fato expressões da lógica proposicional. 
 
 
 Por quê não basta defini-lo como um conjunto 
indutivo sobre X = variáveis  constantes e F = 
{f1,f2,f3,f4} ? 
 
 
 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 Por quê não basta defini-lo como um conjunto 
indutivo sobre X = variáveis  constantes e F = 
{f1,f2,f3,f4} ? 
 
 Pois é preciso garantir que somente as palavras 
geradas por F a partir de X serão consideradas. Daí 
precisamos tomar o menor dos conjuntos indutivos 
sobre X e F. Ou seja, o fecho indutivo de X sob F. 
 
 
 
 
 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 De cima para baixo: tome a família F de todos os 
subconjuntos indutivos Y de Σ* que contem X e são 
fechados sob F. 
 Claro que o nosso conjunto Σ* é um desses 
conjuntos de F . 
 Daí a família F não é vazia. Logo, ∩F não é problema. 
 Portanto, podemos obter o menor dos conjuntos 
indutivos tomando a interseção da família F . 
 
 Vamos chamar esse menor conjunto de X+. 
 
 
 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 De baixo para cima: desejamos obter o menor dos 
conjuntos indutivos de uma forma mais 
computacional. 
 
 Vamos definir um processo indutivo, passo a passo, 
para obtenção desse menor conjunto indutivo sobre 
X e F. 
 
 
 
 
 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 De baixo para cima: 
 Seja X0 = X 
 X1 = X0  {f(w1,..,wn)  f F, aridade de f =n, w1,...,wn  X0} 
 X2 = X1  {f(w1,..,wn)  f F, aridade de f =n,w1,...,wn  X1} 
 ... 
 Xj = Xj-1  {f(w1,..,wn)  f F, aridade de f =n,w1,...,wn  Xj-1} 
 
 Agora tome Xi = X+. 
 
 
 
 
 
  
i=0 
Lógica Proposicional 
Conjunto das expressões bem formadas 
 LEMA: X+ = X+ 
 Prova: 
 (i) X+  X+ 
 Como X+ é menor dos conjuntos indutivos sobre X e 
F, basta mostrar que X+ é um conjunto indutivo 
sobre X e F. Para isso, precisamos mostrar: 
 
 a) X+ contem X; Trivial peladefinição; 
 b) X+ é fechado sob F; 
 
 
 
 
Lógica Proposicional 
LEMA: X+ = X+ 
(i) X+  X+ 
b) X+ é fechado sob F; 
 
Para cada  (de aridade n>0)  F e para todos x1,...,xn  
X+, pela definição de X+, existe algum i, de forma que 
x1,...,xn  Xi e desde que f(x1,...,xn) Xi+1 (por definição), 
f(x1,...,xn) X+. 
 
 
 
 
 
Lógica Proposicional 
LEMA: X+ = X+ 
(ii) X+  X
+ 
 
Basta mostrar que para todo i, Xi  X
+. 
Prova por indução sobre i: 
Caso base (i=0): X0  X
+ : trivial pelo fato de que X+ é 
indutivo. 
Hipótese Indutiva (i=k): Xk  X
+. 
 
Tese: Xk+1  X
+ ? 
 
 
Lógica Proposicional 
LEMA: X+ = X+ 
(ii) X+  X
+ 
 
Tese: Xk+1  X
+ ? 
 
Pela definição, 
Xk+1 = Xk  {f(w1,..,wn)  f F, aridade de f =n,w1,...,wn  Xk} 
 
Pela H.I. XK  X
+. Como X+ é indutivo, logo é fechado 
sob F, consequentemente a segunda parcela também 
está contida em X+.  
Lógica Proposicional - Sintaxe 
Revisão 
1. Quais são as abordagens para verificar se um 
conjunto é o fecho indutivo de um conjunto X sob 
um conjunto de funções F? 
2. Como seria uma abordagem para definir o maior 
conjunto indutivo sobre uma base X e sob um 
conjunto F de funções? 
3. Considere C como o conjunto de cadeias de 
tamanho ímpar sobre o alfabeto binário. 
 (i) Dê uma definição indutiva para C e 
identifique o conjunto base (i.e. X) da geração 
indutiva e o conjunto de funções geradoras (i.e. F). 
 (ii) Descreva em poucas palavras quais são o 
menor e o maior conjunto indutivo sobre X e F. 
 
 
Lógica Proposicional - Sintaxe 
Revisão 
 
4. Defina indutivamente o conjunto de todas as 
cadeias binárias que têm o formato 1k+10k (k>0), 
identificando: 
 
 (i) a base da indução; 
 (ii) a(s) função(ões) geradora(s); 
 (iii) o maior conjunto indutivo.