A Cartilha da Lógica, Maria Nicoletti - Lista5 respostas

Prévia do material em texto

BCC/ENC Introduc¸a˜o a Lo´gica
5a Lista de Exerc´ıcios
1. Considere o alfabeto definido por:
Constantes: a, b, c
Variveis: X, Y, Z
Smbolos funcionais: f/3, g/2, h/1
Simbolos predicados: p/3, q/2
Quantificadores: ∀, ∃
Conectivos: ¬, ∧, ∨, →, ↔
Simbolos de pontuao: ( ) ,
Verifique quais da expresso˜es lo´gicas a seguir sa˜o fo´rmulas bem-formadas. Justifique sua resposta
com base na definic¸a˜o de fo´rmula bem-formada.
Definic¸a˜o 3.9: Uma formula bem-formada - wff - e´ definida recursivamente como (Cartilha da lo´gica
pg. 148):
1. os s´ımbolos especias verdade, falso e s´ımbolos predicados de aridade 0 sa˜o fo´rmulas;
2. um a´tomo e´ uma fo´mula;
3. se α e β forem fo´mulas, enta˜o sa˜o fo´rmulas:
α
¬α
α ∧ β
α ∨ β
α→ β
α↔ β
4. se α for uma fo´rmula e X for uma varia´vel livre em α, enta˜o (∀Xα) e (∃Xα) sa˜o fo´mulas;
5. fo´rmulas sa˜o geradas apenas por meio de um nu´mero finito de aplicac¸o˜es de 1, 2, 3 e 4.
(a) (∃X(∀Xp(X, a, b)))
Sim, pois p e´ um s´ımbolo de predicado com aridade 3 definido no alfabeto e todos os seus argu-
mentos sa˜o termos, logo ele e´ uma fo´rmula e os quantificadores quantificam a varia´vel X que esta´
presente em p.
(b) (∀Y (∀Xp(X,Y, b)))
Sim, pois p e´ um s´ımbolo de predicado com aridade 3 definido no alfabeto e todos os seus argu-
mentos sa˜o termos, logo ele e´ uma fo´rmula e os quantificadores quantificam a varia´vel X que esta´
presente em p.
(c) (∀Y (∃Xp(X, a, b)))
Sim, pois p e´ um s´ımbolo de predicado com aridade 3 definido no alfabeto e todos os seus argu-
mentos sa˜o termos, logo ele e´ uma fo´rmula e os quantificadores quantificam a varia´vel X que esta´
presente em p.
BCC/ENC Introduc¸a˜o a Lo´gica Page 2 of 5
(d) (∀X(∃Y p(X, a, Y ) → q(f(X), g(Y ))))
Na˜o, pois mesmo q sendo um s´ımbolo de predicado com aridade 2 definido no alfabeto, seus ar-
gumentos na˜o sa˜o termos, uma vez que f/1 e g/1 na˜o foram definidos como s´ımbolos funcionais
no alfabeto.
(e) p(X, g(a, b), Y ) ∨ q(h(h(Z)), d) ∧ ¬q(c, d)
Sim, pois p e´ um s´ımbolo de predicado com aridade 3 definido no alfabeto e todos os seus argu-
mentos sa˜o termos e q tambe´m e´ um s´ımbolo de predicado com aridade 2 definido no alfabeto
e todos os seus argumentos sa˜o termos, logo a negac¸a˜o, disjunc¸a˜o e conjunc¸a˜o dessas fo´rmulas
tambe´m e´ fo´rmula.
(f) p(q(X, a), b, Y ) → q(c, d)
Na˜o, pois mesmo p sendo um s´ımbolo de predicado com aridade 3 definido no alfabeto, seus ar-
gumentos na˜o sa˜o termos, uma vez que q/2 foi definido como s´ımbolo de predicado no alfabeto e
s´ımbolo de predicado na˜o e´ termo.
(g) ∀X(∃Z(∀Y (p(a, b,X) → q(g(X,Z), f(a, b, Y ))))))
Sim, pois p e q sa˜o s´ımbolos de predicado com aridade 3 e 2 respectivamente e ambos esta˜o
definidos no alfabeto, e todos os seus argumentos sa˜o termos, logo p e q sa˜o fo´rmulas e os quan-
tificadores quantificam as varia´veis X, Y e Z que esta˜o presentes em p e q.
(h) ¬h(p(a, b, c)) ∨ f(d, d)
Na˜o, devido ha´ va´rios problemas: (1) h e f sa˜o s´ımbolos funcionais; (2) f/2 na˜o foi definido; (3) a
constande d na˜o foi definida no alfabeto; e (4) p/3 e´ um s´ımbolo de predicado, logo na˜o e´ termo.
(i) (∃Y ((∃Z(p(Z,Z,Z) ∨ ¬q(Y, Y ))) ∨ (∀Xq(X,X))))
Sim, pois p e q sa˜o s´ımbolos de predicado com aridade 3 e 2 respectivamente e ambos esta˜o
definidos no alfabeto, e todos os seus argumentos sa˜o termos, logo a negac¸a˜o e disjunc¸a˜o dessas
fo´rmulas tambe´m sa˜o fo´rmulas. Ale´m disso, os quantificadores quantificam as varia´veis X e Y
que esta˜o presentes em p e q.
(j) (∀X(∃Y (p(X,Y, f(a, b, Y )) → (∃Zp(Z,Z, d)))))
Na˜o, pois a constante d no esta´ definida no alfabeto.
(k) (∀X(∃Y (p(f(a, b, c), Y,X))) → (∃Y (∀Xq(h(Y ), g(X,Y ))))
Sim, pois p e q sa˜o s´ımbolos de predicado com aridade 3 e 2 respectivamente e ambos esta˜o
definidos no alfabeto, e todos os seus argumentos sa˜o termos, e os quantificadores quantificam as
varia´veis X e Y que esta˜o presentes em p e q.
(l) (∀X(f(X, b, c) ↔ q(h(X))))
Na˜o, pois f esta´ definido como s´ımbolo funcional no alfabeto.
(m) ((a ∨ b ∨ c) ↔ (b ∨ d))
Na˜o, pois a constante d no esta´ definida no alfabeto.
(n) (∀X(q(X,Y ) ∨ ¬p(f(a, b,X), g(Z,Z,X), h(a))))
Na˜o, pois g/3 na˜o esta´ definido no alfabeto.
2. Considere o alfabeto A com:
Cont.
BCC/ENC Introduc¸a˜o a Lo´gica Page 3 of 5
Conectivos: ¬, ∧, ∨, →, ↔
Quantificadores: ∀, ∃
Simbolos de pontuao: ( ) e ,
Constantes: a, b, c
Variveis: X, Z
Smbolos funcionais: f/2, g/3, h/1
Simbolos predicados: p/3, q/1
(a) Crie pelo menos 10 termos (explique por que sa˜o termos).
Termos sa˜o definidos recursivamente como:
1. uma constante e´ um termo;
2. uma varia´vel e´ um termo;
3. se f e´ um funtor (ou seja, um s´ımbolo funcional com aridade n) e t1, t2, ..., tn sa˜o
termos, enta˜o f(t1, t2, ..., tn) e´ um termo;
4. Todos os termos sa˜o criados usando as regras anteriores.
Com base na descric¸a˜o de termo (A cartilha da lo´gica pg. 144) e no alfabeto dado segue alguns
exemplos poss´ıveis de termos:
a, b e c pois a, b e c sa˜o constantes do alfabeto, logo sa˜o termos
X e Z pois X e Z sa˜o varia´veis do alfabeto, logo sa˜o termos
g(a,b,c) g e´ um s´ımbolo funcional com aridade 3, e seus argumentos
(constantes a, b e c) sa˜o termos
g(g(a,b,c),g(a,b,c),g(a,b,c)) g e´ um s´ımbolo funcional com aridade 3, e seus argumentos
sa˜o termos
f(h(h(a)),g(h(a),h(b),h(c))) f e´ um s´ımbolo funcional com aridade 2, e seus argumentos
sa˜o s´ımbolos funcionais com termos como argumento
h(g(X,Z,a)) h e´ um s´ımbolo funcional com aridade 1, e seu argumento
e´ um s´ımbolo funcional com termos como argumento
(b) Crie pelo menos 10 fo´rmulas bem-formadas (explique por que sa˜o wff ).
Com base na Definic¸a˜o 3.9: definida no exerc´ıcio 1 e no alfabeto dado segue alguns exemplos
poss´ıveis de wff :
p(a,b,c) p e´ um s´ımbolo de predicado com aridade 3, e seus
argumentos (constantes a, b e c) sa˜o termos
p(g(a,b,c),g(a,b,c),g(a,b,c)) p e´ um s´ımbolo de predicado com aridade 3, e seus
argumentos sa˜o termos
q(h(h(a))) q e´ um s´ımbolo de predicado com aridade 1, e seu
argumento e´ um s´ımbolo funcional (termo)
∀Xq(h(h(X))) q e´ um s´ımbolo de predicado com aridade 1, e seu
argumento e´ um s´ımbolo funcional (termo) e o quantificador
universal quantifica uma varia´vel (termo) definida no alfabeto
(c) Crie pelo menos 5 expresso˜es lo´gicas que na˜o sa˜o fo´rmulas e explique por que.
Cont.
BCC/ENC Introduc¸a˜o a Lo´gica Page 4 of 5
Com base na definic¸a˜o 3.9: e na definic¸a˜o de termo definidas em exerc´ıcios anteriores e no al-
fabeto dado segue alguns exemplos (gritantes) poss´ıveis, vale ressaltar que qualquer diversificac¸a˜o
desses exemplos tambe´m na˜o sera˜o fo´rmulas.
g(g(a, b, c), g(a, b, c), g(a, b, c)) ∨ q(b) pois g e´ um s´ımbolo funcional, ou seja, ele retorna coisas logo
na˜o e´ poss´ıvel fazer a disjunc¸a˜o com um predicado
p(q(a), q(b), q(c)) p e´ um s´ımbolo de predicado com aridade 3, contundo seus
argumentos na˜o sa˜o termos
X ∧ Y nesse caso X e Y na˜o sa˜o fo´rmulas
∀Xp(X, a, b) ∧ ∀bq(b) nesse caso b e´ uma constante e quantificadores quantificam
varia´veis
3. Identifique as varia´veis livres e ligadas nas fo´rmulas a seguir, e quais fo´rmulas sa˜o fechadas.
(a) (∀X(p(X,Y ) → (∃Z(q(a, Z,M) ↔ r(Z, T,X)))))
Ligadas: X e Z.
Livres: Y, M e T.
(b) (∀X(∀Y (¬p(a) ∨ q(X,Y )))) ∧ (∀X(p(X))) ∧ (∀Y (q(a, Y ) ∨ ¬p(Y )))
Nesse caso X e Y esta˜o ligadas e na˜o ha´ varia´veis livres, tornando essa fo´rmula uma fo´rmula
fechada.
(c) (∃Z(p(Z, a) ↔ q(Z,Z))) → (∀Y (∃X(p(a,X) ∨ ¬r(X,Y ) ∨ ¬q(Y, b))))
Nesse caso X, Y e Z esta˜o ligadas e na˜o ha´ varia´veis livres, tornando essa fo´rmula uma fo´rmula
fechada.
(d) (∀X(∀Y (∃Z(r(X,Y ) ∧ ¬r(a, Y ))) → (∀Zs(Z, b, Z))))
Nesse caso X, Y e Z esta˜o ligadas e na˜o ha´ varia´veis livres, tornando essa fo´rmula uma fo´rmula
fechada.
(e) (∀X((∀Y (p(X,Y, Z) ∧ ¬r(y,X) ∨ ¬q(X))) ↔ (∀Zq(Z))))
Nessecaso X e Y esta˜o ligadas e Z esta´ livre no primeiro termo antes da implicac¸a˜o e Z esta´ ligada
no segundo termo apo´s a implicac¸a˜o.
4. Construa o fechamento universal e o existencial das fo´rmulas:
(a) (∀X(p(X,Y ))
(∀Y (∀X(p(X,Y ))) - Fechamento universal
(∃Y (∀X(p(X,Y ))) - Fechamento existencial
(b) (∀X(p(X,Y )) ∧ (∃Y (q(Y ))
(∀Y (∀X(p(X,Y ))) ∧ (∃Y (q(Y )) - Fechamento universal
(∃Y (∀X(p(X,Y ))) ∧ (∃Y (q(Y )) - Fechamento existencial
(c) (∀X(∃Y (q(X,Y ) ∨ p(Z))))
(∀Z(∀X(∃Y (q(X,Y ) ∨ p(Z))))) - Fechamento universal
(∃Z(∀X(∃Y (q(X,Y ) ∨ p(Z))))) - Fechamento existencial
Cont.
BCC/ENC Introduc¸a˜o a Lo´gica Page 5 of 5
(d) (∀X(∀Z(p(X,Y, Z, T ) ↔ q(Z,M))))
(∀Y (∀T (∀M(∀X(∀Z(p(X,Y, Z, T ) ↔ q(Z,M))))))) - Fechamento universal
(∃Y (∃T (∃M(∀X(∀Z(p(X,Y, Z, T ) ↔ q(Z,M))))))) - Fechamento existencial
(e) (∃M(∃X(∀Y (p(a, b, Y ) ∨ ¬q(X, b)))))
Esta´ fo´rmula na˜o possu´ı varia´vel livre, ou seja, ela ja´ e´ uma fo´rmula fechada.
The End.