Capıtulo 3Logica de Primeira Ordem

Logica para ProgramacaoLEIC - Tagus Park

1o Semestre, Ano Lectivo 2007/08

c©Ines Lynce and Luısa Coheur

Bibliografia

• Martins J.P., Logica para Programacao, Capıtulo 3.

• Ben-Ari M., Mathematical Logic for Computer Science,Springer-Verlag, 2003, Capıtulos 5 e 7.

• Huth M. e Ryan M., Logic in Computer Science, CambridgeUniversity Press, 2004, Capıtulo 2.

Programa

• Apresentacao

• Conceitos Basicos

• Logica Proposicional ou Calculo Proposicional

• Logica de 1a ordem ou Logica de Predicados

• Programacao em Logica

• Prolog

Programa

• Apresentacao

• Conceitos Basicos

• Logica Proposicional ou Calculo Proposicional

• Logica de 1a ordem ou Logica de Predicados

• Programacao em Logica

• Prolog

Logica de 1a ordem – programa de festas

• Motivacao

• Componentes de uma Logica

1. Linguagem (+ representacao em logica)2. Sistema dedutivo3. Sistema semantico

Logica de 1a ordem – programa de festas

• Motivacao

• Componentes de uma Logica

1. Linguagem (+ representacao em logica)2. Sistema dedutivo3. Sistema semantico

Logica de Primeira Ordem – Motivacao

• Em logica classica existem duas alternativas para a definicaode uma linguagem

– Logica Proposicional– Logica de Primeira Ordem

Como ja tınhamos visto...

• Logica Proposicional e baseada em proposicoes, isto e, frasesdeclarativas que fazem afirmacoes sobre qualquer coisa.

Limitacoes da Logica Proposicional

• Como representar “Todos os alunos tem exactamente umnumero” em Logica Proposicional?

– Conjuncao de sımbolos proposicionais: Aluno Joao ∧Numero 53118 ∧ TemNumero Joao 53118

– Como referir “todos” e “exactamente um”?– Como generalizar para todos os alunos e qualquer numero?

Ora a Logica de 1a ordem...

• ... permite criar frases com estrutura interna:

Exemplo

• “Todos os alunos tem exactamente um numero”

• ∀x(aluno(x)→ ∃y(numero(x , y) ∧ ∀z(numero(x , z)→ y =z))))

Logica de 1a ordem – programa de festas

• Motivacao

• Componentes de uma Logica

1. Linguagem (+ representacao em logica)2. Sistema dedutivo3. Sistema semantico

Linguagem da Logica de Primeira Ordem (LLPO)

• Como ja se percebeu, e necessario introduzir novos sımbolos,uma nova definicao de fbf e novas regras de formacao.

Alfabeto basico

• Sımbolos de pontuacao: , ( ) [ ]

• Sımbolos logicos: ¬,∧,∨,→, ∀, ∃– O sımbolo ¬ le-se “nao” e corresponde ao operador de negacao– O sımbolo ∧ le-se “e” e corresponde ao operador de conjuncao– O sımbolo ∨ le-se “ou” e corresponde ao operador de disjuncao– O sımbolo → le-se “implica” e corresponde ao operador de

implicacao– O sımbolo ∀ le-se “para todo” e corresponde ao operador de

quantificacao universal– O sımbolo ∃ le-se “existe” e corresponde ao operador de

quantificacao existencial

Alfabeto basico (cont.)

• Letras de funcao com n argumentos (aridade n), para n ≥ 0 ei ≥ 1: f n

i

– Representam funcoes sobre os elementos da linguagem– f 0

i corresponde a funcoes de aridade zero que representamconstantes

– Indice i fornece uma capacidade ilimitada para criar novosnomes

• Letras de predicado com aridade n, para n ≥ 0 e i ≥ 1: Pni

– Representam operadores sobre elementos da linguagem,produzindo valores logicos

• Variaveis individuais para i ≥ 1: xi

– Tem como domınio os objectos da conceptualizacao

Notacao

• Se nao for confuso, usamos a, b, c , . . . para representarconstantes e f , g , h, . . . para representar variaveis;

• Se nao for confuso, usamos P,Q,R, . . . para representar asletras de predicado;

• Se nao for confuso, usamos x , y , z , . . . para representar asvariaveis.

Exemplos

• Funcoes

– capital(x) = capital de x;{(Portugal,Lisboa),(Franca,Paris),(Espanha,Madrid),. . .}

– soma(x , y) = x + y ; {(1, 1, 2), (1, 2, 3), (2, 1, 3), . . .}• Predicados

– Fronteira(x , y) = x tem fronteira com y;{(Portugal,Espanha),(Espanha,Franca),(Franca,Belgica),. . .}

Termos

• Termos representam objectos; correspondem a sintagmasnominais em linguagem natural

• Sao definidos recursivamente

– Cada letra de funcao com aridade zero (letra de constante) eum termo

– Cada variavel e um termo– Se t1, t2, . . . , tn sao termos, entao f n

i (t1, t2, . . . , tn) e um termo– Nada mais e um termo

Exemplos

• capital(Portugal)

• pai(Augustus De Morgan)

• pai(pai(pai(Augustus De Morgan)))

• x

• capital(x)

• pai(x)

Conceito – Termo chao

• Termo sem variaveis e chamdo um termo chao (do Inglesground term)

Exemplos

• capital(Portugal)

• pai(Augustus De Morgan)

• pai(pai(pai(Augustus De Morgan)))

Formulas bem formadas (fbfs)

• Se t1, t2, . . . , tn sao termos, entao Pni (t1, t2, . . . , tn) e uma fbf

(atomica)

• Se α e uma fbf entao (¬α) e uma fbf

• Se α e β sao fbfs entao (α ∨ β), (α ∧ β) e (α→ β) sao fbfs

• Se α e uma fbf contendo zero ou mais ocorrencias da variavelx entao ∀x [α] e ∃x [α] sao fbfs

• Nada mais e uma fbf

Exemplo

• Consideremos

– P letra de predicado com aridade 2– Q letra de predicado com aridade 1– A e B letras de predicado com aridade 0– f letra de funcao com aridade 1– g letra de funcao com aridade 3– a, b, c constantes– x variavel

• Entao sao fbfs

– (¬P(a, g(a, b, c)))– (P(a, b)→ ∀x [(¬Q(f (x)))])– (A ∧ B)

• Parentesis redundantes podem ser eliminados

Quantificadores

• Nas expressoes ∀x [α] e ∃x [α] a fbf α e chamada domınio doquantificador (∀ ou ∃)

• α nao tem de conter a variavel x ; nesse caso ∀x [α] e ∃x [α]sao equivalentes a α

Conceitos – variavel livre e variavel ligada

• x e variavel livre em α se nao for quantificada; caso contrarioe variavel ligada

Exemplo

• ∀x [A(x)] contem a variavel ligada x

• A(x)→ ∃x [B(x)] contem uma ocorrencia de x livre (emA(x)) e outra ligada (em B(x))

Conceitos – fbf fechada (ou cha)

• fbf sem variaveis livres diz-se fechada (ou cha)

Vamos agora trabalhar a representacao em logica

Logica de 1a ordem – programa de festas

• Motivacao

• Componentes de uma Logica

1. Linguagem (+ representacao em logica)2. Sistema dedutivo3. Sistema semantico

Sistema dedutivo – programa de festas

• Sistema de deducao natural

– Conceito de substituicao– Novas regras de inferencia

• Resolucao

– Conversao para a forma clausal– Conceitos de unificacao– Aplicacao da regra de resolucao

• Propriedades do sistema dedutivo

Sistema dedutivo – programa de festas

• Sistema de deducao natural

– Conceito de substituicao– Novas regras de inferencia

• Resolucao

– Conversao para a forma clausal– Conceitos de unificacao– Aplicacao da regra de resolucao

• Propriedades do sistema dedutivo

E la vamos nos ao sistema dedutivo da Logica de 1a

ordem, mas antes...

• ... temos que introduzir um conceito fundamental: o desubstituicao.

Conceito – Substituicao

• Conjunto finito de pares ordenados {t1/x1, . . . , tn/xn}– xi (1 ≤ i ≤ n) e uma variavel– ti (1 ≤ i ≤ n) e um termo

• Aplicacao da substituicao s a fbf α (α ◦ s) corresponde a fbfobtida a partir de α substituindo todas as ocorrencias davariavel livre xi por ti (1 ≤ i ≤ n)

– P(x , f (a, y)) ◦ {a/x , f (a, b)/y} = P(a, f (a, f (a, b)))– P(x , f (a, y)) ◦ {a/x , f (a, b)/y , c/z} = P(a, f (a, f (a, b)))– A(x)→ ∀x [B(x)] ◦ {a/x , f (a, b)/y , c/z} = A(a)→ ∀x [B(x)]

Substituicao – duas restricoes a reter

• Nenhuma das variaveis pode ser igual ao termocorrespondente

– Sejam x , y , z variaveis e f funcao de um argumento– OK: {f (x)/x , z/y}– KO: {x/x , z/y}

• Numa substituicao todas as variaveis tem de ser diferentes

– Sejam x , y , z variaveis e f , g , h funcoes de um argumento– OK: {a/x , g(y)/y , f (g(h(b)))/c}– KO: {a/x , g(y)/y , b/x , f (g(h(b)))/c}

Substituicao: problema

• ∀xP(x , f (a, y)) ◦ {a/x , x/y} = ∀xP(x , f (a, x)))– Efeito colateral indesejavel

I Variavel ligada x foi introduzida como argumento de PI Alteracao do significado da fbf: y era variavel livre e o termo

que a substitui inclui a variavel x que nao e livre

• Novo conceito: termo livre para uma variavel numa fbf

• Nova abordagem: nem todas as substituicoes de variaveislivres fazem sentido

Notacao

• α(x1, . . . , xn) indica que a fbf α tem (pelo menos) x1, . . . , xn

como variaveis livres (pode ter outras alem destas)

Conceito – termo livre para uma variavel numa fbf

• Um termo sem variaveis e sempre livre para qualquer variavel

• Seja α uma fbf e t um termo: t e livre para xi em α senenhuma ocorrencia livre de xi em α ocorrer dentro dodomınio do quantificador ∀/∃xj em que xj e uma variavel emt.

Ou seja...

• Se ocorrencias de xi foram substituıdas por t entao nenhumaocorrencia de uma variavel em t deixa de ser livre em α(t)

– α(x1, . . . , xn) ◦ {t1/x1, . . . , tn/xn} = α(t1, . . . , tn)

Exemplo

• O termo g(y , f (b))

– E livre para x na fbf P(x , y)– Nao e livre para x na fbf ∀y [P(x , y)]

Vamos entao agora ao sistema dedutivo da Logica de 1a

ordem, nomeadamente...

• ... ao sistema de deducao natural.