Andamento da apresenta˘c~aoprofessor.ufabc.edu.br/~jair.donadelli/logica/Slides...Linguagem do c alculo de predicados Andamento da apresenta˘c~ao 1 Linguagem do c alculo de predicados

Linguagem do calculo de predicados

Andamento da apresentacao

1 Linguagem do calculo de predicadosDiscussao informalLinguagem formalAbreviaturasExemplos de linguagens de primeira ordemVariaveis livres e ligadas; substituicao de variaveisTeoremas de unicidade de representacao

Professor : [email protected]

Logica Basica


Discussao informal

O que queremos formalizar?

Todos os passaros tem pena.

Nem todos os passaros voam.

Todos os passaros sao mais leves que algum mamıfero.

Todo aluno e mais novo que algum professor.

Pode ser tratado no calculo sentencial, o qual nao captura todaestrutura da sentenca. Os alvos do discurso (sujeito e ojeto) temqualidade e mantem relacoes.


Logica Basica


Discussao informal

Argumentos nao validados pela logica proposicional

Premissa Todos os felinos sao mamıferosPremissa Alguns felinos sao ferozes

Conclusao Alguns mamıferos sao ferozes


Logica Basica


Discussao informal


Premissa Qualquer amigo de Maria e amigo de JoaoPremissa Pedro nao e amigo de Joao

Conclusao Pedro nao e amigo de Maria


Logica Basica


Discussao informal


Premissa O sucessor de um inteiro par e ımparPremissa 2 e um inteiro par

Conclusao O sucessor de 2 e ımpar


Logica Basica


Discussao informal

O que procuramos

Uma linguagem mais rica que leva em conta a estrutura internadas sentencas

sujeito – predicado – objeto

na qual sujeito e objetos de quem se fala sao elementos de umuniverso do discurso e sao representados por constantes, porobjetos genericos e nao especificados (pronomes) que saorepresentados por variaveis; os predicados e as relacoes saoexplicitados. Incorpora o “para todo” e o “existe” comoprimitivas da linguagem.


Logica Basica


Discussao informal

Exemplos I

Num universo far, far away ....

As constantes a := Armando, d := Daniel, j := Jair

Os predicados P para “e professor”, A para “e aluno”.

As relacoes J para “lecionam juntos” e N para “e mais novo”.


Logica Basica


Discussao informal

Exemplos II

P(a) representa a sentenca “Armando e professor”

¬A(j) representa a sentenca “Jair nao e aluno”

J(a, d) representa a sentenca “Armando e Daniel lecionam juntos”

M(d , a) representa a sentenca “Daniel e mais novo que Armando”


Logica Basica


Discussao informal

Exemplos III

Obervemos que

J(a, d) e J(d , a) tem o mesmo significado

mas

M(a, d) e M(d , a) nao tem o mesmo significado


Logica Basica


Discussao informal

Exemplos IV

Variaveis

P(x) representa “x e professor”

M(x , y) que representa “x e mais novo que y”

Nao sao sentencas. Nao tem valor logico

Sao chamadas de sentencas abertas.

Tornam-se sentencas substituindo as variaveis por constantes ou sequantificamos.


Logica Basica


Discussao informal

Exemplos V

Quantificacao

Os quantificadores ∀ le-se “para todo” e ∃ le-se “existe”

∀x P(x) representa “para todo x , x e professor”

∃x P(x) representa “existe x , x e professor”

Sao sentencas. Tem valor logico


Logica Basica


Discussao informal

Exemplos VI

Notemos que, por exemplo

∀x M(x , y) e uma sentenca aberta

∃y ∀x M(x , y) e ∀x ∃y M(x , y) tem significados diferentes.


Logica Basica


Discussao informal

Exemplos VII

“Todo aluno e mais novo que algum professor”:

∀x ∃y(A(x) ∧ P(y)→ M(x , y))


Logica Basica


Discussao informal

Exemplos VIII

“Todo aluno e mais novo que algum professor”:

∀x ∃y(A(x) ∧ P(y)→ M(x , y))


Logica Basica


Discussao informal

Exemplos IX

“Ha um professor tal que todo aluno aprende algo com ele”

B(x , y , z) representa “y aprende z com x”

H(x) representa “x e um assunto”

∃x(P(x) ∧ ∀y

(A(y)→ ∃z (H(z) ∧ B(x , y , z))

))


Logica Basica


Discussao informal

Exemplos X

“Todos os passaros tem pena.”

∀x (passaro(x)→ pena(x))

“Nem todos os passaros voam.”

∃x (passaro(x) ∧ ¬voa(x))

“Todos os passaros sao mais leves que algum mamıfero.”

∀x (passaro(x)→ ∃y (mamifero(y) ∧Maisleve(x , y)))


Logica Basica


Discussao informal

Exemplos XI

“Todos os homens sao sabios”

∀x (Homem(x)→ Sabio(x))

“Nenhum homem e sabio”

∀x (Homem(x)→ ¬Sabio(x))

“Alguns homens sao sabios”

∃x (Homem(x) ∧ Sabio(x))


Logica Basica


Discussao informal

Exemplos XII

“Se x e inteiro igual a zero ou maior que zero e se todo inteiro edivisıvel por x , entao x e igual a um”

0 e 1 sao constantes.

I (x) representa “x e inteiro”

>(x , y) representa “x e maior que y”

=(x , y) representa “x e igual a y”

d(y , x) representa “y e divisıvel x”

∀x(I (x) ∧

(>(x , 0)∨ =(x , 0)

)∧ ∀y (I (y)→ d(y , x)) →=(x , 1)

)Professor : [email protected]

Logica Basica


Discussao informal

Exemplos XIII

Premissa Qualquer amigo de Maria e amigo de JoaoPremissa Pedro nao e amigo de Joao

Conclusao Pedro nao e amigo de Maria

Premissa ∀x (Amigo(x ,m)→ Amigo(x , j))Premissa ¬Amigo(p, j)

Conclusao ¬Amigo(p,m)


Logica Basica


Discussao informal

Exemplos XIV

Premissa O sucessor de um inteiro par e ımparPremissa 2 e um inteiro par

Conclusao O sucessor de 2 e ımpar

Premissa ∀x (Inteiro(x) ∧ Par(x)→ Impar(s(x))Premissa Inteiro(2) ∧ Par(2)

Conclusao Impar(s(2))


Logica Basica


Linguagem formal

A logica de predicados

A logica de predicados, ou logica de primeira ordem, e constituıdapor:

linguagem que trata dos sımbolos utilizados e da regra deformacao de formulas,

semantica que interpreta a linguagem, dando-lhe umsignificado, e

axiomatizacao ou sistema de axiomas, que dita as regras parademonstracoes de teoremas.

A linguagem da logica de primeira ordem nao e unica.

Ha sımbolos comuns a todas e outros especıficos (e.g., ∈, +).


Logica Basica


Linguagem formal

Constituintes de uma linguagem de primeira ordem

alfabeto sao os sımbolos utilizados,

termos sao as sequencias finitas de sımbolos que representamindivıduos do universo a que se refere a linguagem, e

formulas sao as sequencias finitas de sımbolos querepresentam assercoes sobre os indivıduos.


Logica Basica


Linguagem formal

Alfabeto

Variaveis x1, x2, x3, . . .

Conectivos logicos ¬, ∨, ∧, →, ↔

Quantificadores ∀, ∃

Pontuacao os parenteses ( e ) e a vırgula ,

Sımbolo de igualdade =

Constantes c1, c2, c3, . . .

Sımbolos relacionais n-arios Rn1 ,R

n2 ,R

n3 , . . . para cada inteiro n > 1

Sımbolos funcionais n-arios F n1 ,F

n2 ,F

n3 , . . . para cada inteiro n > 1


Logica Basica


Linguagem formal

Alfabeto

As constantes, os sımbolos relacionais e funcionais sao especıficosde cada linguagem de primeira ordem.

O conjunto das constantes pode ser vazio, o conjuntos dossımbolos relacionais pode ser vazio e o conjunto sımbolosfuncionais pode ser vazio.


Logica Basica


Linguagem formal

Alfabeto — Simplificacoes

Variaveis x , y , z ,w

Constantes a, b, c , d ,

Sımbolos relacionaisP,Q,R, <,6,Amigo,Maisleve,mamifero,passaro

Sımbolos funcionais F ,G ,H,+, ·

Por exemplo, na linguagem da aritmetica

a funcao soma, + , e usada como x + y ao inves de +(x , y).

a relacao menor que < e escrita a < b ao inves de < (a, b).


Logica Basica


Linguagem formal

Expressao

Uma sequencia finita de sımbolos do alfabeto e chamado deexpressao.

Por exemplox1, ∀(c1c100∃p30

1 →

e uma expressao


Logica Basica


Linguagem formal

Termos

Termo e qualquer expressao que respeita as regras

1 Constantes sao termos.

2 Variaveis sao termos.

3 se t1, t2, . . . , tn sao termos e F funcao n-aria, entaoF (t1, t2, . . . , tn) e termo.

4 Todos os termos tem uma das formas acima.

ExemploSao termos: c1, F 1

2 (x1), x101


Logica Basica


Linguagem formal

Formulas

Formula e qualquer expressao obtida a partir das regras

1 Se t e s sao termos, entao (t = s) e uma formula.

2 Se t1, . . . , tn sao termos e R e um sımbolo relacional n-ario,entao R(t1, . . . , tn) e uma formula.

3 Se α e β sao formulas, entao (¬α), (α→ β), (α ∧ β),(α ∨ β), (α↔ β) sao formulas.

4 Se α e formula e x e uma variavel, entao (∀x α) e (∃x α) saoformulas.

5 Todas as formulas tem uma das formas acima.

Exemplo: (R11 (x1) ∨ R3

2 (x4, x2, c1))→ (∀x1(∃x2 R32 (c4, x2, c1)))


Logica Basica


Abreviaturas

Mais simplificacoes I

Abriviaturas

Para resultados teoricos (metamatematicos) e vantajosopossuirmos o mınimo possıvel de sımbolos.

Para expressarmos de maneira clara e sucinta quanto maissımbolos, melhor.

Tratando alguns sımbolos como abreviaturas de outros ganhamosdos dois lados.


Logica Basica


Abreviaturas

Mais simplificacoes II

1 (diferente) t 6= s e abreviatura de ¬(t = s);

2 (nao existe) 6 ∃x α e e abreviatura de ¬∃x α;

3 (ou) α ∨ β e abreviatura de ¬((¬α) ∧ (¬β));

4 (implica) α→ β e abreviatura de ¬(α ∧ ¬β);

5 (sse) α↔ β e abreviatura de (¬(α ∧ ¬β)) ∧ (¬(β ∧ ¬α));

6 (existe) ∃x α e abreviatura de ¬∀x ¬α.


Logica Basica


Abreviaturas

Omissao de parenteses

Omitimos os parenteses externos de uma formula, recolocandoquando a usamos para compor outras formulas. Por exemplo,escrevemos α ∧ β no lugar de (α ∧ β), mas recolocamos osparenteses quando escrevemos, por exemplo, ∀x(α ∧ β).

Em sequencias de conjuncoes e em sequencias de disjuncoes,omitimos o uso sucessivo de parenteses. Isto e, escrevemosα ∧ β ∧ γ no lugar de α ∧ (β ∧ γ), o mesmo valendo para oconectivo ∨.

Quando nao houver riscos de mas interpretacoes, omitimos osparenteses externos em subformulas do tipo ∀xα, ∃xα e ¬α.Por exemplo, escrevemos ¬∀x∃yα, em vez de ¬(∀x(∃yα)).


Logica Basica


Exemplos de linguagens de primeira ordem

Exemplos I

Uma linguagem de primeira ordem tem os sımbolos logicos(comum as linguagens)

x1, x2, x3, . . . ¬ ∧ ∀ ( ) , =

e os sımbolos extralogicos (especıficos de cada linguagem)

Constantes, Sımbolos relacionais e Sımbolos funcionais

Para definir uma linguagem explicitamos so os sımbolosextralogicos.


Logica Basica



Exemplos II

Exemplo 1: A linguagem da igualdade pura, L=:

Nao ha sımbolos extralogicos.

Exemplo 2: Uma linguagem para Corpos LF :

Constantes: 0, 1Sımbolos funcionais binarios: +, ·

Exemplo 3: Uma linguagem para Teoria dos Conjuntos LST :

Sımbolo relacional binario: ∈


Logica Basica

https://en.wikipedia.org/wiki/Theory_of_pure_equality

https://en.wikipedia.org/wiki/Field_(mathematics)



Exemplos III

Exemplo 4: Uma linguagem para Aritmetica LN :

Constante: 0Sımbolo funcional unario: S

Sımbolos funcionais binarios: +, ·, E

A constante 0 pretende representar o numero zero, S a funcaosucessor (isto e, S(n) = n + 1), e E representa a funcaoexponencial (isto e, E(n,m) = nm).


Logica Basica



Exemplos IV

Exemplo 5: Outra linguagem para Aritmetica

Constantes: 0, 1Sımbolos funcionais binarios: +, ·

Sımbolo relacional binario: <, |

Nesse caso, sao termos da linguagem:

0, 1, +(1, 1),+(1,+(1, 1)), +(1,+(1,+(1, 1))),+(1,+(1,+(1,+(1, 1)))), e assim por diante. Representam osnumeros naturais.


Logica Basica



Exemplos V

Sao formulas da linguagem:

< (·(1, 1),+(1, 1))

∀x (+(0, x) = x)

∀x ∀y ((+(1, x) = +(y , 1))→ x = y)

∀x ∀y (|(x , y)→ (<(x , y) ∨ x = y))


Logica Basica


Variaveis livres e ligadas; substituicao de variaveis

Variaveis Livres e Variaveis Ligadas I

Uma formula e atomica se e formada pelas 2 primeiras regras.

A ocorrencia de uma variavel x e livre em uma formula α se, e sose,

1 α e atomica e x ocorre em α;

2 α e da forma (¬β) e x ocorre livre em β;

3 α e da forma (β ∧ γ) e x ocorre livre em β ou γ;

4 α e da forma ∀xkψ e x e diferente de xk e x ocorre livre em ψ.

Uma ocorrencia de x em α que nao e livre e dita ligada.

Uma formula α sem ocorrencia de variaveis livre e dita sentenca.


Logica Basica



Variaveis Livres e Variaveis Ligadas II

O item 4 e a chave: a ocorrencia de uma variavel x e ligada se elaesta no escopo de uma ocorrencia de ∀x .

Por exemplo,

1 Em ∀x7(x5 = x7) a ocorrencia de x5 e livre e a ocorrencia dex7 e ligada.

2 Em ∀x0 ((x0 = F 13 (x6))→ (¬∀x6 R

19 (x6)))a primeira

ocorrencia de x6 e livre e a segunda ocorrencia e ligada.

3 Em ∀z (∀x (P(x)→ R(z)))→ (Q(y)→ P(x)) a variavel x elivre e ligada, y e livre e z e ligada.


Logica Basica



Variaveis Livres e Variaveis Ligadas III

O item 4 e a chave: a ocorrencia de uma variavel x e ligada se elaesta no escopo de uma ocorrencia de ∀x .

Por exemplo,

1 Em ∀x7(x5 = x7) a ocorrencia de x5 e livre e a ocorrencia dex7 e ligada.

2 Em ∀x0 ((x0 = F 13 (x6))→ (¬∀x6 R

19 (x6))) a primeira

ocorrencia de x6 e livre e a segunda ocorrencia e ligada.

3 Em ∀z (∀x (P(x)→ R(z)))→ (Q(y)→ P(x)) a variavel x elivre e ligada, y e livre e z e ligada.


Logica Basica



Substituicao de variaveis I

Se α e uma formula, x e uma variavel e t e um termo, definimos[α]tx a formula obtida substituindo todas as ocorrencias livres davariavel x pelo termo t.

Denotamos por

[α]t1...tnx1...xn

a formula obtida pela substituicao em α de todas as ocorrenciaslivres das variaveis x1, . . . , xn pelos termos t1, . . . , tn,respectivamente.


Logica Basica



Substituicao de variaveis II

Exemplos:

1 [(x = y)]xy e (x = x)

2 [(x = y)]yx e (y = y)

3 [∀x (x = y)]yx e ∀x (x = y),

4 [∀x (x = y)]xy e ∀x (x = x),

5 [∀x P(x)→ P(x)]τx e ∀x P(x)→ P(τ),

6 [∀x (¬∀y (x = y))→ (¬∀y (x = y))]yx e∀x (¬∀y (x = y))→ (¬∀y (y = y)),

7 [∀x (P(x , y)→ (¬Q(y) ∨ ∃y P(x , y)))]F (y ,z)y e

∀x (P(x ,F (y , z))→ (¬Q(F (y , z)) ∨ ∃y P(x , y)))


Logica Basica



Substituicao de variaveis III

Exemplos:

1 [(x = y)]xy e (x = x)

2 [(x = y)]yx e (y = y)

3 [∀x (x = y)]yx e ∀x (x = y),

4 [∀x (x = y)]xy e ∀x (x = x),

5 [∀x P(x)→ P(x)]τx e ∀x P(x)→ P(τ),

6 [∀x (¬∀y (x = y))→ (¬∀y (x = y))]yx e∀x (¬∀y (x = y))→ (¬∀y (y = y)),

7 [∀x (P(x , y)→ (¬Q(y) ∨ ∃y P(x , y)))]F (y ,z)y e

∀x (P(x ,F (y , z))→ (¬Q(F (y , z)) ∨ ∃y P(x , y)))


Logica Basica


Teoremas de unicidade de representacao

Teorema da unicidade de representacao dos termos

Se t e um termo de uma linguagem, entao uma, e apenas uma,das assercoes abaixo e verdadeira:

t e uma variavel;

t e uma constante;

t e da forma F (t1, . . . , tn), onde t1, . . . , tn sao termos e F eum sımbolo funcional n-ario.

Alem disso, se t e da forma F (t1, . . . , tn) e, ao mesmo tempo, e daforma G (s1, . . . , sm) entao:

n = m;

F e G sao o mesmo sımbolo funcional;

ti e o mesmo termo que si , para todo i 6 n.


Logica Basica



Teorema da unicidade de representacao das formulas I

Seja α uma formula de uma linguagem. Entao α satisfaz uma, eapenas uma, das condicoes abaixo

α e uma formula atomica da forma R(t1, . . . , tn), onde R eum sımbolo relacional n-ario e t1, . . . , tn sao termos;

α e uma formula atomica da forma (s = t) onde s e t saotermos;

α e da forma ¬β, para uma unica formula β;

α e da forma β ∧ γ para unicos β e γ formulas;

α e da forma ∀xβ, para uma unica formula β e uma unicavariavel x .


Logica Basica



Teorema da unicidade de representacao das formulas II

Alem disso, valem:

α e e da forma (s = t) e, ao mesmo tempo, e da forma(u = v) entao s e o mesmo que u e t e o mesmo que v ;

se α e da forma R(t1, . . . , tn) e, ao mesmo tempo, e da formaS(s1, . . . , sm) entao:

n = m;

R e S sao o mesmo sımbolo relacional;

ti e o mesmo termo que si , para todo i 6 n.


Logica Basica

Documents

Andamento da apresenta˘c~aoprofessor.ufabc.edu.br/~jair.donadelli/logica/Slides...Linguagem do c alculo de predicados Andamento da apresenta˘c~ao 1 Linguagem do c alculo de predicados