![]() | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
Istorie | Literatura | Matematica | Psihologie |
Logica Predicatelor
1. Alfabetul si sintaxa in logica predicatelor
Vom prezenta logica predicatelor ca un limbaj formal, ca si logica propozitiilor. Reamintim ca un limbaj formal este format, in general, dintr-un alfabet care contine toate simbolurile limbajului, o sintaxa care stabileste modul in care sunt folosite simbolurile limbajului pentru a forma cu ele formule ( aceste formule, in logica propozitiilor, s-au numit propozitii) si o semantica care stabileste interpretarea acestor formule.
Alfabetul. In logica propozitiilor alfabetul este format din trei categorii de simboluri:
a) Simboluri logice:
i) Variabile
care se vor nota cu litere mici de la sfarsitul alfabetului latin,
insotite eventual de indici: ,etc.
ii) Simboluri ale conectorilor logici: .
iii) Un simbol , numit virgula, un simbol ( , numit paranteza deschisa si un simbol, ), numit paranteza inchisa.
iv) Cuantificatori: .
b) Simboluri specifice:
i) Simboluri de predicate care se vor nota cu litere mari ale alfabetului latin de
tipul P, Q, ,, etc.
ii) Simboluri de constante care se vor nota cu litere mici de la inceputul
alfabetului latin: a , b, ,,etc.
iii) Simboluri de functii care se vor nota cu litere mici ale alfabetului latin
de tipul g,
,,etc.
Cuantificatorii si
se numesc respectiv cuantificatorul universal si cuantifcatorul existential.
Mentionam ca
predicatele, ca si funtiile, se disting intre ele prin aritatea lor, aritate care trebue
sa fie un numar intreg pozitiv; respectiv vom avea simboluri de
predicate sau simboluri de functii,
unare, binare, ternare, , are,, etc. Din punct de vedere formal aritatea nu se
defineste ci se mentioneaza la fiecare aparitie a unui
simbol de predicat sau de functie. Din comoditate vom spune in loc de
simboluri de constante sau simboluri de variabile pur si simplu constante,
respectiv variabile.
Sintaxa. Orice secventa de simboluri se numesre expresie. Printre expresii distingem unele care se numesc termeni, formule atomice( atomi), formule, formule inchise( fraze).
Notiunea de termen se defineste inductiv astfel;
i) Orice variabila si orice constanta sunt termeni.
ii) Daca f este un simbol de
functie ara si
sunt termeni atunci
este un termen.
iii) Orice termen se obtine aplicand succesiv, de un numar finit de ori, regulile i) si ii).
Notiunea de formula atomica: O formula atomica este o
expresie de forma unde P este un simbol de predicat
ar si
sunt termeni.
Notiunea de formula se defineste inductiv astfel:
i) Orice formula atomica este o formula.
ii) Daca si
sunt formule atunci
sunt formule.
iii) Daca este o formula
si
este o variabila
atunci
si
sunt formule.
iv) Orice formula se obtine aplicand succesiv, de un numar finit de ori, regulile i) si ii) si iii).
In formula
se numeste scopul cuantificatorului
si, analog, in
formula
se numeste scopul cuantificatorului
. Notam, de asemenea, ca in
sau
variabila
poate sa
lipseasca din expresia lui
; in acest caz, dupa cum vom vedea, din punct de vedere
semantic,
si
, au aceeasi semnificatie ca si
.
Parantezele se poate reduce dupa aceleasi reguli ca si in logica propozitiilor
- mai intai se reduc parantezele
exterioare; astfel devine
,
devine
, etc.
- ordinea de prioritate a
aplicarii conectorilor logici si a cuantificatorilor si
este:
Iar
in cazul aparitiei multiple ale aceluiasi cuantificator acesta, cu
exceptia negatiei, se aplica de la dreapta la stanga.
Astfel devine
.
-
daca avem mai multe aparitii succesive ale cuantificatorilor, acesia
se aplica de la stanga la dreapta fara a mai mentona acest
lucru prin paranteze. Astfel devine
.
Exemple
1. se obtine prin reducerea
parantezelor din
.
2. se obtine prin reducerea
parantezelor din
.
3. se obtine prin reducerea parantezelor
din
.
4.
Pentru a indica un limbaj concret
este suficient sa indicam simbolurile sale specifice. Astfel putem
considera un limbaj care contine
doua constante 0 si 1, doua predicate binare
si
, o functie binara +. In acest limbaj putem
considera urmatorele formule:
,
,
,
,
,
,
,
,
.
Mentionam
ca am notat, pentru orice doi termeni u
si v, in loc de
,
in loc de
si
in loc de
Exercitii.
1. Refaceti parantezele pentru urmatoarele formule
(a) .
;
.
(b) .
;
.
(c) .
;
.
(d) .
;
..
(e) .
.
(f) .
;
.
(g) .
2. Reduceti cat mai multe paranteze posibile in urmatoarele formule.
a) .
.
(b) .
.
(c)
O aparitie a unei variabile x intr-o formula se numeste legata daca aparitia lui x este intr-un cuantificator,
sau
, sau in scopul unui
cuantificator,
sau
din
. In caz contrar aparitia se numeste libera in
. O variabila se numeste legata( respectiv libera)
intr-o formula
daca are cel putin o aparitie legata(
respectiv libera) in
.
Exemple.
1. .
2.
.
3. .
4.
In exemplul 1
singura aparitie a lui x este
libera. In exemplul 2, prima aparitie a lui x este libera dar a doua aparitie a lui x ca si a treia sunt legate. In
exemplul 3, toate aparitiile lui sunt legate. In
exemplul 4, x are o singura
aparitie care este legata. In fiecare dintre exemplele de mai sus
variabila y are o singura
aparitie care este libera. In exemplul 2, variabila
este atat legata
cat si libera
Exercitii
1. Indicati aparitiile libere si legate ale variabilelor in urmatoarele formule:
(a) .
x are doua aparitii legate; y o aparitie libera; z doua aparitii legate.
(b)
Primele doua aparitii ale lui y sunt legate si a treia este libera; prima aparitie a lui z este libera si celelalte doua sunt legate.
(c)
Toate aparitiile lui x sunt legate; y are primele trei aparitii legate si a treia libera.
Pentru orice formula vom scrie
in loc de
pentru a indica
ca
nu are alte variabile
libere in afara de
( ceea ce nu inseamna ca
contine
neaparat aceste variabile libere). Notatia este convenabila
deoarece vom consimti sa scriem
pentru rezultatul substitutiilor variabilelor
cu termenii
in toate
apatitiile libere(daca exista) ale lui
respectiv.
2. Interpretari
Formulele din limbajul logicii predicatelor nu au sens decat daca se da o anumita interpretare simbolurilor limbajului. O interpretare I consta din urmatoarele:
i) O multime D numita domeniul interpretarii.
ii) Pentru fiecare simbol de predicat ar P, o
relatie
ara
intre elementele lui D.
iii) Pentru fiecare simbol de
functie ara f, o
functie
ara
.
iv) Pentru fiecare simbol de
constanta a, un element .
Pentru fiecare simbol de predicat P, simbol de functie f, simbol de constanta a, relatia , functia
si elementul
se numesc interpretarile lui P, f,
a in raport cu interpretarea I a limbajului si daca
interpretarea I este clara din
context nu se mai face distinctie intre simbol si inerpretarea sa.
O formula care nu contine variabile libere se numeste formula inchisa sau fraza. Putem considera ca frazele sunt propozitii care in raport cu o interpretare data sunt adevarate sau false. Formulele in general pot fi( in raport cu o interpretare data) adevarate( satisfacute) pentru anumite valori ale variabilelor libere in domeniu de interpretare si false pentru alte valori ale lor.
Exemple. Consideram urmatoarele formule
1.
.
2.
.
3.
Consideram
o intrepretare I in care domeniul
interpretarii este multimea a numerelor intregi
pozitive iar interpretarea predicatului binar P este relatia de ordine pe
; deci daca
atunci
daca
. Formula 1 reprezinta atunci o expresie in limbajul
cotidian, anume
(
x este mai mic sau
egal ca y
) care este satisfacuta de anumite perechi
de numere intregi
pozitive ( de exemplu avem
si
deci perechile
si
satisfac formula
noastra) si nu este satisfacuta de altele ( de exemplu avem
deci perechea
nu satisface formula. Formula 2 reprezinta expresia
pentru orice numar intrg pozitiv y ,
si este
satisfacuta numai de numarul 1. Formula 3 este insa o
fraza care afirma ca exista un cel mai mic numar
intreg pozitiv si este adevarata in interpretarea noastra.
Daca insa domeniul interpretarii este multimea
a numerelor intregi
atunci fraza noastra nu mai este adevarata.
Exercitiu
Pentru urmatoarele formule si pentru interpretarile indicate stabiliti pentru ce valori ale variabilelor libere aceste formule sunt satisfacute sau, in cazul cand ele sunt fraze, daca ele sunt adevarate
(i) ;
(ii) ;
(iii) .
(a) Domeniul interpretarii este
multimea a numerelor intregi
pozitive, interpretarea predicatului binar P
este relatia de ordine pe
, interpretarea functiei binare f este inmultirea pe
si interpretarea
constantei a este
.
(b) Domeniu interpretarii este
multimea a numerelor intregi,
interpretarea predicatului binar P
este relatia de egalitate pe
si interpretarea
constantei a este
.
(iii) Domeniul inerpretarii este
multimea a tuturor
submultimilor lui
,
inseamna
,
inseamna
iar a inseamna multimea vida
.
Rezolvare
(a) Formula (i) este expresia care este satisfacuta de toate perechile
de numere intregi
pozitive cu
si nu este satisfacuta de perechea
.
Formula (ii) este expresia . O pereche
de numere intregi
pozitive astfel ca
satisface formula
daca si numai daca
.
Formula (iii) este insa o
fraza care afirma ca relatia de ordine pe este tranzitiva
si este evident adevarata.
In continuare vom defini notiunile semantice de adevar sau satisfactie intr-un mod precis.
Fie I
o interpretare.O asociere in interpretarea I este o aplicatie
unde
este multimea tuturor variabilelor si D este domeniul interpretarii. Fie
o asociere in
interpretarea M . Notam cu
multimea tuturor
termenilor si definim o aplicatie
inductiv astfel:
i) Pentru orice constanta c luam .
ii) Pentru orice variabila x luam .
iii) Daca f este o functie ara si
sunt termeni atunci
.
Aplicatia se noteaza cu
aceeasi litera
ca si asocierea
data. Spunem, de asemenea ca
este elementul din D asociat
termenului
.
Exemplu.
Consideram termenul unde f si g sunt functii binare,
si
variabile si a o constanta. Consideram
interpretarea I cu domeniul
multimea
a numerelor intregi,
functia f interpretata ca
inmultirea numerelor intregi, functia g interpretata ca adunarea numerelor intregi si constanta
a interpretata ca numarul
intreg 2. Pentru o pereche
de numere intregi
putem considera o asociere
cu
si
. Atunci asociatul termenului
este numarul
intreg
.
Faptul ca o asociere satisface o formula
se defineste
inductiv astfel
i) Daca este o formula
atomica atunci
unde P este un predicat
ar si
sunt termeni; in acest
satisface
daca
.
ii) Daca si
sunt formule atunci
a) satisface
daca
nu satisface
;
b) satisface
daca
satisface
si
satisface
;
c) satisface
daca
satisface
sau
satisface
;
d) satisface
daca
nu satisface
sau
satisface
;
e) satisface
daca
satisface
si
satisface
sau
nu satisface
sau
nu satisface
si
nu satisface
.
iii) Daca este o formula
si x este o variabila
atunci
a) satisface
daca pentru orice
element
asocierea
definita prin
satisface
.
b) satisface
daca exista
un element
astfel incat asocierea
de mai sus satisface
.
Putem reformula definitia de mai
sus definind pentru fiecare asociere o valorizare
astfel: pentru
luam
daca
satisface
si
daca
nu satisface
. Atunci punctele i), ii) si iii) ale definitiei se
transcriu astfel:
i) Daca este o formula
atomica,
unde P este un predicat
ar si
sunt termeni atunci
daca si
numai daca
.
ii) Daca si
sunt formule atunci
.
iii) Daca este o formula
si x este o variabila
atunci
daca si
numai daca pentru orice
avem
si
daca si
numai daca exista un
astfel incat
.
Fie I
o interpretare. Daca este o fraza(
formula inchisa) atunci, evident, pentru orice doua asocieri
( unde D este
domeniul interpretarii) avem
motiv pentru care
scriem
unde
este o asociere
oarecare. In ceea ce urmeaza vom studia din punct de vedere semantic numai
frazele. Motivul este ca de regula, din punct de vedere semantic,
formulele care nu sunt inchise pot fi inlocuite cu fraze. Astfel avem:
Fie
o formula care nu
este neaparat inchisa. Atunci, evident
si
sunt fraze si
avem
1. Exista o asociere astfel incat
daca si
numai daca
.
2. Pentru orice asociere avem
daca si
numai daca
.
O fraza se numeste
adevarata in interpretarea I daca
; in aceasta situatie spunem, de asemenea, ca
interpretarea I este un model pentru
si notam
. Fraza
se numeste
falsa in interpretarea I
daca
. Fraza
se numeste logic adevarata ( tautologie) daca este adevarata in orice
interpretare, caz in care sctriem
, si logic
falsa ( contradictie) daca este falsa in orice
interpretare).
Exemple(analiza semantica a unor fraze)
Fraza este logic
adevarata. Intr-adevar, In caz contrar ar exista o interpretare I astfel incat
este falsa in
aceasta interpretare adica
este adevarata si
este falsa. Interpretarea predicatului unar
este o submultime
si interpretarea
constantei
este elementul
si, in
particular, faptul ca
este falsa in I
inseamna ca
. Pe de alta parte faptul ca
este adevarata inseamna ca
pentru orice element
. Evident, avem o contradictie.
2.
Consideram fraza. Fie I o
interpretare oarecare. Interpretarea predicatului binar P este o relatie binara
. Faptul ca fraza
este adevarata
in I inseamna ca pentru orice elemente
daca
atunci
. Astfel fraza
este
adevarata intr-o interpretare I
daca si numai daca interpretarea predicatului binar P este o relatie binara
simetrica pe domenul D al
interpretarii.
Analog fraza este
adevarata intr-o interpretare I
daca si numai daca interpretarea predicatului binar P este o relatie binara
reflexiva pe domenul D al
interpretarii, fraza
este
adevarata intr-o interpretare I
daca si numai daca interpretarea predicatului binar P este o relatie binara
tranzitiva pe domenul D al
interpretarii; in fine fraza
este adevarata intr-o interpretare I daca si numai daca interpretarea predicatului binar P este o relatie de echivalenta pe domenul D al interpretarii.
3. Consideram fraza . Fie I o
interpretare oarecare si presupunem ca interpretarea predicatului
binar Q este relatia de
egalitate pe D. Atunci fraza
este
adevarata in I daca
si numai daca interpretarea predicatului binar P este graficul unei aplicatii
.
5.
Consideram fraza . Consideram o interpretare I cu domeniul interpretarii
si interpretarea
predicatului binar relatia de prdine
pe
. Atunci fraza
este
adevarata in I daca
si numai daca interpretarea constantei a este numarul natural 0. Rezulta, de asemenea, ca
fraza
este adevarata in interpretarea de mai sus.
Daca schimbam domeniul interpretarii si anume il luam
atunci fraza
nu este
adevarata pentru orice interpretare a constantei a si, in particular fraza
nu este adevarata.
Echivalenta frazelor se
defineste exact ca si in logica propozitiilor mai precis pentru
orce doua fraze avem
daca
iar echivalenta
ferzelor are aceleasi proprietati ca si echivalenta
propozitiilor.
Tablouri semantice.
Sintaxa frazelor se poate formula independent de sintaxa formulelor in general pe baza urmatoarelor definitii:
Un termen de baza este un termen in expresia caruia nu apar variabile.
O fraza
atomica este o expresie de forma unde P este un simbol de predicat
ar si
sunt termeni de
baza.
Notiunea de fraza se poate defini inductiv astfel:
i) Orice fraza atomica este o fraza.
ii) Daca si
sunt fraze atunci
sunt fraze.
iii) Daca este o formula
unde
este o variabila
atunci
si
sunt fraze.
iv) Orice fraza se obtine aplicand succesiv, de un numar finit de ori, regulile i) si ii) si iii).
Tablourile semantice atomice sunt:
Pentru fiecare
fraza atomica
,
(1) si (2)
;
Pentru fraza
,
(3) si (4)
;
Pentru orice fraze
,
(5)
si (6)
;
(7) si (8)
;
(9) si (10)
;
(11) si (12)
;
Pentru orice formula
,
(13) (14)
;
(15) (16)
.
Acum putem demonstra, cu ajutorul tablourilor semantice( demonstratii Beth), ca anumite fraze din logica propozitiilor sunt logic adevarate , teorema de corectitudine fiind evidenta; insa datorita faptului ca tablourile semantice in logica predicatelor pot sa fie infinite, nu mai functioneaza o teorema de completitudine clara, ca cea din logica propozitiilor.
(1)
( pe scurt
),
(2) ( pe scurt si
),
unde si
.
Pentru afirmatia (1) demonstratia Beth este
Afirmatia (2) rezulta din (1) prin echivalente astfel:
( deoarece
prin legea dublei
negatii)
( deoarece, conform lui (1),
)
( prin legea dublei negatii).
(3)
( pe scurt
),
(4) ( pe scurt
),
unde si
.
(3) si (4) rezulta prin echivalente din (1):
( deoarece, conform lui (1),
)
( deoarece
prin legea dublei
negatii);
( deoarece, conform lui (2),
)
( deoarece
prin legea dublei
negatii).
(5)
(
distributivitatea completa a cuantificatorului universal fata de
conjunctie),
(6)
( distributivitatea
completa a cuantificatorului existential fata de
disjunctie).
Pentru afirmatia (5) vom da mai jos o demonstratie Beth. Afirmatia (6) rezulta prin echivalente astfel:
( deoarece, conform lui (4),
)
( deoarece, conform lui De Morgan,
)
( conform lui (5)
( conform lui De Morgan)
( deoarece, conform lui (4),
).
(7)
(8)
(9) este logic adevarata
(10)
nu este logic
adevarata; aici
.
Pentru (7) urmeaza demonstratie Beth
Pentru (8) procedam prin echivalete astfel:
prin legea dublei
negatii)
( deoarece, conform lui (2),
)
( deoarece, conform lui (2),
)
( conform lui (7))
( deoarece, conform lui (1),
)
( deoarece, conform lui (1),
)
( conform legii dublei negatii).
Pentru (9) urmeaza demonstratie Beth
Pentru a
demonstra (10) consideram formula unde P este un predicat binar si
interpretarea I cu domeniul
multimea
a numerelor naturale
si predicatul P relatia de
egalitate pe
. Atunci, interpretarea formulei
este
, interpretarea formulei
este
si avem, evident,
,
si deci
.
Insa este instructiv de vazut si de ce demonstrata Beth esueaza.
Cuantificatorul universal are o distributivitate partiala fata de disjunctie iar cuantificatorul existential are o distributivitate partiala fata de conjunctie
(11)
este logic
adevarata,
(12) nu este logic
adevarata,
(13) este logic
adevarata,
(14) nu este logic
adevarata.
In (13) si (14) avem si
.
Pentru (11) vom da demonstratie Beth mai jos. Pentru (13) folosim echivalente astfel:
Pentru (13) procedam prin echivalente:
deoarece
)
( conform lui De Morgan )
(deoarece
)
( conform lui De Morgan )
si ultima formula este logic adevarata conform lui (11).
Pentru (12) consideram doua
predicate binare P si Q , o constanta 1 si formulele
si
. Consideram de asemenea o interpretare I in care domeniul este
, interpretarea lui P
este relatia
pe
iar interpretarea lui Q este relatia
pe
iar interpretarea
constantei este cea uzuala. Interpretarea formulei
este
iar a formulei
este
. Avem, evident
,
astfel ca
.
Pentru (14)
consideram un predicat binar P ,
doua constante 0 si 1 si formulele si
. Consideram de asemenea o interpretare I in care domeniul este
, interpretarea lui P
este relatia
pe
iar interpretarea
constantelor este cea uzuala. Interpretarea formulei
este
iar interpretarea
formulei
este
. Avem, evident,
si
astfel ca
.
Pe de alta parte daca si
este o fraza
avem:
(15)
;
(16) .
Pentru (15),
avem ca este logic
adevarata conform lui (11) si ramane de demonstrat ca
este logic
adevarata; dam o
demonstratie Beth.
Pentru (16) procedam prin echivalente|
( conform lui (14)
.
O lista de formule care se pot justifica cu metode asemanatoare cu cele de mai sus este urmatoarea
( pe scurt
).
( pe scurt si
).
(3) ( pe scurt
).
( pe scurt
).
(5) .
.
(7) .
(8) .
(9).
(10) .
(11) .
(12).
(13) .
(14).
15) .
(16).
(17).
(18) .
(19) .
.
(21) .
Copyright © 2025 - Toate drepturile rezervate