CATEGORII DOCUMENTE |
Elemente de logica formala
ca teorie de ordinul intai
s1. Introducere
Desi logica formala a fost conceputa pentru a modela rationamentul uman, ea este deosebit de utila si pentru reprezentarea si manipularea cunostintelor. Formalismul logic este lipsit de ambiguitate si permite descrierea realitatii inconjuratoare prin formulari concise si clare.
Deducerea de noi fapte in logica formala se bazeaza pe reguli de inferenta, care pot fi tratate si implementate in calculator prin tehnici de unificare si filtraj.
Ideea ca logica de ordinul intai poate fi utilizata ca limbaj de programare
este o idee revolutionara, deoarece, pana in 1972 logica n-a fost utilizata in
informatica decat ca limbaj declarativ. In cele ce urmeaza vom arata ca logica
are o interpretare procedurala, ceea ce-i permite sa fie folosita in mod
eficient ca limbaj de programare. Mai exact spus, o clauza de program de forma
Una din ideile principale ale programarii logice este ca un algoritm se constituie din doua componente distincte si anume logica si controlul. Logica formuleaza problema de rezolvat iar controlul formuleaza modul cum aceasta va fi rezolvata.
Limbajele actuale de programare logica sunt clasificate in doua mari categorii distincte. Prima categorie este formata din asa-zisele limbaje sistem, iar cea de a doua, din limbaje aplicatie.
Limbajele sistem pun mai mult accent pe paralelismul }I.
In aceste limbaje un scop de forma
Limbajele aplicatie sunt considerate ca limbaje de programare cu scop general avand un domeniu extins de aplicabilitate. Accentul in aceste limbaje este pus pe paralelismul SAU. Din aceasta categorie de limbaje citam: Quintus PROLOG, micro-PROLOG si NU-PROLOG.
Logica furnizeaza un formalism unic pentru diferite componente ale informaticii. Ea ne furnizeaza, ca un scop general, limbaje de rezolvare a problemelor, dar in acelasi timp ne furnizeaza si limbaje convenabile sistemelor de operare si fundamente pentru sisteme de baze de date deductive si sisteme expert sau de suport decizional. Aceasta varietate de aplicatii, ca si eleganta si simplitatea unificarii, din programarea logica, ii asigura acesteia, un viitor important si influent. Inferenta logica va deveni elementul fundamental al informaticii.
ss Concepte de baza
Logica formala este o teorie de ordinul intai si ea cuprinde doua aspecte: cel sintactic si cel semantic.
Aspectul sintactic se refera la formulele bine definite admise de gramatica unui limbaj formal cat si la problemele profunde ale teoriei demonstratiei.
Aspectul semantic priveste semnificatia data formulelor si simbolurilor continute in ele.
Logica formala consta dintr-un alfabet, un limbaj de ordinul intai, o multime de axiome si o multime de reguli de inferenta. Aceste elemente sunt cele care careacterizeaza orice teorie de ordinul intai.
Limbajul de ordinul intai este format din formulele bine definite ale teoriei de ordinul intai, iar axiomele sunt submultimi de formule bine definite. Axiomele si regulile de inferenta sunt utilizate pentru deducerea teoremelor teoriei. In continuare vom defini alfabetul si limbajul teoriei de ordinul intai.
Definitia s1. Un alfabet este constituit din urmatoarele categorii de elemente: variabile, constante, functii, proceduri (predicate), conectori, cuantificatori si semne de punctuatie.
Conectorii, cuantificatorii si semnele de punctuatie sunt aceleasi pentru toate alfabetele, in timp ce variabilele, constantele, functiile si predicatele variaza de la un alfabet la altul.
Daca intr-o teorie nu putem lucra decat cu mrimi constante, atunci teoria
respectiva este de ordinul
Daca intr-o teorie putem sa lucram cu marimi variabile siacestea pot fi chiar si predicate ale teoriei respective, atunci acea teorie spunem ca este de ordinul II.
Obiectul logicii il constituie identificarea si folosirea legilor rationamentului uman.
Logica formala utilizeaza simboluri pentru unitatile gandirii si pentru
operatiile efectuate asupra lor. Variabilele vor fi notate, in mod obisnuit,
prin literele
In logica propozitiilor, acestea sunt unitati nedecompozabile, orice
consideratie asupra structurii lor este irelevanta. In logica formal, care se
ocupa cu studiul validitatii, in sensul corectitudinii unei formule, numai pe
baza formei sau sintaxei ei, nu se recurge la interpretari. Simbolurile
Atata timp cat acceptam referirea la
Pentru inceput ne propunem sa vedem ce se intelege prin propozitie, in cadrul logicii propozitiei si totodata vom incerca sa transformam propzitiile din vorbirea curenta in simboluri ce vor putea fi utilizate in cadrul general al logicii formale.
Definitia ss O propozitie este o asertiune declarativa care poate fi considerata adevarata sau falsa intr-un context dat.
Din aceasta definitie se poate constata ca propozitia logica are doua caracteristici esntiale. Prima dintre acestea este ca propozitia este o asertiune declarativa. Bineanteles ca aceasta caracteristica nu o au nici interogarile si nici indemnurile. A doua caracteristica este ca propozitia logica poate fi adevarata sau falsa intr-un anumit context dat. De exemplu, propozitia Senatorul doreste sa fie reales, poate fi adevarata sau falsa. Precizand contextul in care se face aceasta declaratie se poate stabili cu exactitate daca propozitia este adevarata sau falsa. Contextul impune precizarea datelor problemei, adica stabilirea numelui senatorului si a datei la care vor avea loc alegerile la care acesta doreste sa fie reales.
In logica formala vom utiliza simboluri pentru desemnarea propozitiilor si aceasta din doua motive.
Primul dintre ele fiind acela de a furniza o teorie universal valabila, iar cel de al doilea, de a scrie cat mai putin posibil.
Urmatoarele doua asertiuni sunt propozitii in sensul logicii propozitiilor:
p: Materii prime este un cont de pasiv
q: O actiune are o valoare nominala
Prima din aceste propozitii este falsa, iar a douaeste adevarata.
Notatia p: arata ca propozitia Materii prime este un cont de pasiv, se va reprezenta prin simbolul p. Ea poate fi citita astfel: 'p este: Materii prime este un cont de pasiv'.
Cele doua propozitii de mai sus sunt propozitii simple.
Definitia s3. Numim propozitie simpla, o asertiune in care nu apar conectorii logici.
s3. Traducerea conectorilor din vorbirea curenta
in logica formala
Propozitiile simple sau atomii (cum mai sunt ele numite), sunt unitati compozabile. Ele se combina si dau nastere la noi propozitii care, la randul lor, sunt adevarate sau false.
Asocierea sau combinarea atomilor (propozitiilor) din vorbire sau rationament se precizeaza in logica formala prin conectorii logici.
A. Traducerea negatiei
De exemplu pentru a
spune ca nu este adevarat ca o actiune are
o valoare nominala vom folosi conectorul
Prin urmare, nu din vorbirea curenta se traduce in
logica propozitiilor prin conectorul
Sa consideram asertiunea: 401 este cont de decontare cu furnizorii si 13 este cont de casa.
si
q: 13 este cont de casa.
Deci, ea se mai poate scrie si sub forma
Conjunctia
din vorbirea curenta s-a tradus aici prin conectorul
In alte cazuri, pentru a gasii propozitiile care se compun, trebuie sa prelucram expresia din vorbirea curenta. In acest sens, sa consideram urmatoarea asertiune: Grupul social al muncitorilor este mare si este foarte unit.
p: Grupul social al muncitorilor este mare
si
q: Grupul social al muncitorilor este foarte unit.
Sa observam ca, pentru a putea formula cea de a doua propozitie, am fost
nevoiti sa luam in considerare contextul in care o formulam. Acest context era
subinteles in asertiunea initiala. Fara acest context, a doua propozitie,
Cu aceste notatii, asertiune initiala se poate scrie mai pe scurt si sub
forma
Dar de ce am descompus aceasta propozitie in doua propozitii mai simple? Putea oare aceasta formulare sa reprezinte o propozitie simpla? Vom incepe cu precizarea raspunsului la cea de a doua intrebare si anume: asertiunea de mai sus putea reprezenta o propozitie simpla. Totul depinde cum vom interpreta cele doua caracteristici ale unui lucru oarecare: mare si foarte unit. Daca contextul in care ne gasim cu aceasta asertiune nu impune considerarea celor doua caracteristici ca fiind distincte, atunci asertiunea de mai sus poate fi o propozitie simpla. Deci raspunsul la prima intrebare este foarte simplu. Am considerat ca, contextul general in care ne gasim, cere separarea celor doua caracteristici.
C. Traducerea particulei sau
Sa consideram acum asertiunea: |aranimea sau muncitorimea este grupul social care va schimba starea economica a Romaniei.
Din punctul de vedere al logicii formale aceasta asertiune se poate
reprezenta sub forma
Semnificatia celor doua simboluri se poate deduce imediat si ea este:
p: |aranimea este grupul social care va schimba starea economica a Romaniei
iar
q:Muncitorimea este grupul social care va schimba starea economica a Romaniei.
Se constata ca si in acest exemplu a trebuit sa intervenim in formularea asertiunii initiale pentru a pune in evidenta cei doi atomi ai sai.
In general particula sau, din
vorbirea curenta, se traduce in logica propozitiilor prin
Acest lucru depinde de contextul enuntului.
De exemplu, in asertiunea: Un numar intreg nenul este mai mare decat zero sau mai mic decat zero, particula sau are un caracter exclusivist, un numar intreg nenul nu poate fi decat mai mare or mai mic decat zero.
In asertiunea:
Un numar par este un numar care se divide
cu doi sau a carui cifra finala apartine multimii
D. Traducerea implicatiei
Pentru exemplificarea folosirii conectorului logic
Acest exemplu este foarte simplu si se constata ca se poate scrie sub forma
p: O tara incalca drepturile omului,
iar
q: Romania refuza sa aiba relatii comerciale cu ea.
In legatura cu acest conector facem observatia ca, in vorbirea curenta noi am putea avea exprimari si de forma: NATO va desfasura forte de interventie in Bosnia daca ONU va aproba acest lucru.
Se constata ca
aceasta fraza s-ar putea formaliza sub forma
unde
p: ONU va aproba interventia NATO in Bosnia,
iar
q: NATO va desfasura forte de interventie in Bosnia,
care bineinteles ca se
poate reprezenta si sub forma
E. Traducerea dublei implicatii
Pentru
a ilustra folosirea conectorului logic al dublei implicatii,
Se constata fara nici o dificultate ca aceasta asertiune se poate scrie sub
forma
p: Bugetul de stat creste
iar
q: Se inceteaza subventionarea firmelor nerentabile.
Observatie. In locul notatiei cu litere mici am fi putut folosi mnemonici de una sau
mai multe litere mari care sa ne reaminteasca continutul propozitiilor. Astfel
asertiunea de la dubla implicatie se poate scrie si sub forma:
F. Traducerea cuantificatorilor
Sa exemplificam acum folosirea cuantificatorilor. Sa consideram urmatoarea
asertiune: Orice student este absolvent
de liceu. Aceasta asertiune se poate scriesub forma:
Dar sa consideram
urmatoarea asertiune: Nu toti studentii
sunt absolventi de liceu. Aceasta asertiune poate fi interpretata in cel putin
doua moduri diferite si anume: ca Exista
unii studenti care nu sunt absolventi de liceu si Exista studenti care sunt
absolventi de liceu. Desi cele doua interpretari sunt perfect valabile totusI
ele sugereaza lucruri total diferite sI anume, prima interpretare sugereaza
faptul ca marea majoritate a studentilor sunt absolventi de liceu, iar cea de a
doua, ca marea majoritate a studentilor nu sunt absolventi de liceu. Prima interpretare se poate scrie sub un aspect formalizat astfel:
Este clar de aici ca, pentru a exprima sub un aspect mai formalizat aceste lucruri, avem nevoie de notiunea de multime.
In general, cand vrem sa spunem ca toate elementele unei multimi au o
anumita proprietate, atunci folosim cuantificatorul universal,
De exemplu pentru a spune ca orice numar
natural este pozitiv, folosim o expresie de forma:
Daca vrem sa spunem
ca numai anumite numere naturale sunt
pare putem folosi o expresie de forma:
In aceste exemple nu numai ca am aratat cum se introduc in logica propozitiilor cuantificatorii, dar, in acelasi timp am vazut cum se introduc variabilele in vorbirea curenta. De regula prin inlocuirea variabilelor intr-o propozitie, cu diverse valori din domeniul lor de interpretare, se obtine o noua propozitie care poate fi falsa sau adevarata.
Definitia s4. Numim domeniul de interpretare al unei variabile, acea multime introdusa de context, in care respectivei variabile i se pot atribui valori.
Sa mai observam ca in loc de
Desigur, domeniul de interpretare are o mare importanta @n stabilirea
valorii de adevar a unei formule. De exemplu, daca in formula
Propoztiile din logica propozitiilor se pot compune, asa cum am vazut mai sus si dau nastere la noi propozitii logice. Sa observam insa ca in acest fel putem obtine propozitii care nu au nici o semnificatie in vorbirea curenta.
De exemplu, considerand
si
atunci, in logica
propozitiilor are sens compunerea
s4. Formule
In logica propozitiilor, prin combinarea propozitiilor simple se obtin
propozitii care in logica formala se numesc formule. Deci
Observatie. Scrierea corecta a unei formule incepe cu o paranteza stanga si se termina cu o paranteza dreapta. Dar in cele ce urmeaza vom omite aceste paranteze cand nu exista pericolul unei ambiguitati si vom tine seama in acest sens si de ordinea de executie a conectorilor, ordine data mai jos.
Pentru a evita o incarcare excesiva a formulelor cu paranteze vom adopta urmatoarele prioritati pentru conectori:
prioritatea 0 pentru conectorul negatiei, deci
pentru
prioritatea 1 pentru
conectorul conjunctiei, deci pentru
prioritatea 2 pentru
conectorul disjunctiei, deci pentru
prioritatea 3 pentru conectorii
La acestea mai trebuie sa adaugam faptul ca cei doi cuantificatori au prioritatea 0.
Aceste prioritati sI ordinea de executie a conectorilor pot fi schimbate si precizate mai bine prin folosirea parantezelor.
Formulele
se vor nota cu litere mari ale alfabetului latin:
De exemplu,
In cele ce urmeaza vom avea nevoie de notiunea de termen (atom). Vom defini aceasta notiune inductiv.
Definitia s5
1) O constanta este un termen;
2) O variabila este un termen
3) Daca
4) Orice termen este de una din formele de mai sus.
Cu acestea spuse putem da o definitie recurenta pentru o formula bine definita.
Definitia s6. Daca p este un predicat cu aritatea n si daca t1, , tn sunt termeni, atunci p(t1, , tn) este o formula, numita formula atomica sau pur si simplu atom.
Definitia s7.
1) un atom este o formula bine definita;
2) daca P este o formula bine definita, atunci ( P) este o formula bine definita;
3) daca P si Q sunt doua formule bine definite , atunci (P Q), (P Q), (P Q), (P Q) sunt de asemenea formule bine definite;
4) daca F este o formula bine definita si x este o variabila, atunci ( x F(x)) si ( x F(x)) sunt formule bine definite;
5) orice formula (bine definita) se obtineprin aplicarea regulilor 1) la 4).
Uneori este mai comod sa notam formula F G prin G F.
Definitia s8. Domeniul de recunoastere a cuantificatorului x (respectiv a lui x) in x (F) (respectiv x (F)), este intreaga formula F.
Acest domeniu de recunoastere mai este numit si domeniu de portabilitate.
Definitia s9. Aparitia unei variabile, precedata de un cuantificator, in domeniul de portabilitate al acestuia, vom spune ca este legata, orice alta aparitie a variabilei respective, vom spune ca este libera.
Conform acestei definitii pot exista formule in care aparitia unei variabile poate fi legata, dar aceleasi variabile pot fi si cu aparitii libere.
Exemplu. In formula x p(x, x) q(x), primele aparitii ale variabilei x sunt legate, pe cand ultima aparitie este libera. Acest lucru se explica prin aceea ca domeniul de portabilitate a lui x este format doar din formula p(x,x). In formula x (p(x, y) q(x)) ambele aparitii ale lui x sunt legate, deoarece portabilitatea lui x este p(x, y) q(x).
Definitia s10. Daca intr-o formula, o variabila are numai aparitii legate atunci variabila @nsasi este legata @n acea formula.
Definitia s11. Daca @ntr-o formula o variabila are numai aparitii libere, atunci variabila @nsasi este libera @n acea formula
Definitia s1s Daca @ntr-o formula o variabila are atat aparitii libere cat si aparitii legate, atunci variabila @nsasi este semilegata @n acea formula.
Definitia s Spunem ca o formula este inchisa, daca in ea nu exista aparitii de variabile libere.
Exemplu. Formula y x (p(x, y) q(x)) este o formula inchisa, pe cand formula x p(x, y) q(x) nu este inchisa, deoarece ea contine, pe langa variabila libera y si o variabila semi-legata x.
Definitia s14. Daca toate variabilele dintr-o formula sunt libere, atunci formula @nsasi este libera.
Formulele libere vor fi notate cu F, G, H s.a.m.d.
Definitia s15. Daca F este o formula, atunci prin (F) vom reprezenta inchiderea universala a lui F
Inchiderea universala a unei formule libere se obtine prin introducerea unui cuantificator universal pentru toate variabilele care au aparitii libere. Daca formula F are si variabile semi-legate, atunci aparitiile de variabile libere se vor redenumi prin alte variabile distincte intre ele si distincte fata de cele existente.
In mod analog se defineste inchiderea existentialista a lui F, pe care o notam cu (F) si care se obtine prin introducerea unui cuantificator existential pentru toate variabilele din F.
Exemplu. Daca F este p(x, y) q(x) atunci (F)este x y (p(x,y) q(x)), iar (F) este x y (p(x,y) q(x))
s5. Clauze definite de program
Acum vom introduce o categorie importanta de formule si anume clauzele. Pentru aceasta vom introduce mai intai notiunea de literal.
Defnitia s16. Un literal este un atom sau negatia unui atom. Un literal pozitiv este un atom iar un literal negativ este negatia unui atom.
Definitia s17. O clauza este o formula care are aspectul x1, . . . xn (L1, L2 Lm), unde fiecare Li este un literal, iar x1,, xn sunt toate variabilele care apar in formula L1, L2 Lm.
Deci o clauza este inchiderea universala a unei formule.
Exemplu Formulele urmatoare sunt clauze:
x y z (p(x,z) q(x,y) r(y,z))
x y ( p(x,y) r ((f(x,y),a))
Clauzele sunt cele mai utilizate elemente in programarea logica si este foarte comod sa folosim o notatie cauzala. Astfel clauza x1 xs (A1 A2 Ak B1 Bn), unde A1, , Ak, B1 , Bn sunt atomi, iar x1,, xs sunt toate variabilele care apar in acesti atomi, o vom nota prin
A1 ,Ak B1,,Bn.
In aceasta notatie, cauzala B1,,Bn se numeste antecedent, sau premisa, iar A1 ,Ak consecvent sau concluzie. #ntr-o notatie cauzala toate variabilele sunt presupuse a fi universal cuantificate, virgulele in antecedentul B1,,Bn desemneaza conjunctia, iar in consecventul A1 , ,Ak desemneaza disjunctia.
Aceste conventii se justifica prin faptul ca formula
x1 xs (A1 A2 Ak B1 Bn)
este echivalenta cu
x1 xs (A1 A2 Ak) (B1 Bn)
Aceasta echivalenta se obtine foarte usor pe baza tablelor de adevar si este redata @n tabla din Figura s2, din care se observa imediat ca A B si B A au aceeasi tabla de adevar. Aici A reprezinta A1 A2 Akiar B reprezinta B1 Bn.
Pentru a ilustra aplicabilitatea acestor notiuni in programarea logica vom defini conceptele de program definit si scop defnit.
Definitia s18. O clauza de forma
A B1, , Bn
o numim clauza definta de program. Ea contine un singur atom in consecvent.
Intr-o clauza definita de program consecventul il mai numim si cap sau antet iar antecedentul corp.
Definitia s19. O clauza de forma
o numim clauza unitate
Clauza unitate este deci o clauza definita de program care nu are corp.
Semantica neformala a clauzei definite de forma A B1, , Bn este urmatoarea: pentru orice valori atribuite variabilelor din clauza, daca B1, , Bn sunt toate adevarate, atunci A este adevarat. Deci, daca n>0, orice clauza definita este conditionala, pe cand clauza unitate A este neconditionala iar semanitica ei este: pentru orice valori atribuite variabilelor, A este adevarata.
Definitia s20. O multime finita de clauze definite de program constituie un program definit.
Intr-un program definit, multimea clauzelor avand acelasi simbol, p, in antet, constituie descrierea predicatului p.
Definitia s21. Un scop definiteste o clauza definita de forma B1, , Bn, adica o clauza fara antet. Fiecare Bi al unui scop este denumit subscop
Semantica unui scop este urmatoarea: exista cel putin o asignare de valori data variabilelor care satisface acest scop.
Daca y1, , ys sunt toate variabilele care apar in scopul B1, , Bn, atunci aceasta scriere reprezinta o prescurtare a lui
y1 ys ( B1 Bn)
sau intr-o forma echivalenta
y1 , y2 , . , yr (B1 Bn).
Definitia s2s O clauza fara antecedent si fara consecvent o vom numi clauza vida, ea trebuie inteleasa ca o contradictie.
Definitia s23. O clauza defnita de program sau un scop definit constituie o clauza Horn.
s6. Interpretari si modele
in cadrul teoriei de ordinul intai
Una din problemele la care trebuie sa raspunda logica formala este urmatoarea: care este valoarea de adevar a unei formule oarecare P, daca se cunosc valorile de adevar ale atomilor constituenti.
Abordarea intuitiva presupune ca raspunsul la aceasta intrebare se obtine prin evaluari si interpretari (cercetarea valorii de adevar a formulelor).
Pentru a fi capabili sa spunem ca o formula este adevarata sau falsa este necesar sa dam mai intai o semnificatie fiecarui simbol din formula. Cuantificatorii si conectorii au semnificatie prefixata, pe cand constantele, simbolurile de functii si de predicate, pot avea semnificatii diferite, de la o formula la alta.
O interpretare presupune gasirea unui domeniu de studiu care contine constantele si in care se asigneaza fiecarei variabile cate o valoare. De asemenea interpretare a presupune atribuirea de aplicatii pe domeniul respectiv pentru fiecare functie si, in acelasi timp, atribuirea de relatii pe domeniul repectiv pentru fiecare predicat din formula.
Cele mai interesante interpretari sunt cele care traduc formulele in expresii cu valoare de adevar adevarat. O astfel de interpretare este numita model al formulei.
Logica de ordinul intai ofera metode pentru deducerea teoremelor oricarei teorii. Acestea, la randul lor, pot fi caracterizate ca formule care sunt consecinte logice ale axiomelor teoriei respective, adica ele sunt adevarate in orice interpretare care este un model pentru axiomele teoriei.
Sistemele de programare logica care ne intereseazautilizeaza ca regula de inferenta, regula rezolutiei, care consta in urmatoarele. Sa presupunem ca vrem sa demonstram ca formula
y1, , yr (B1 Bn)
este o consecinta logica a unui program P.
Sistemele resolutive actuale sunt sisteme de refutatie: adica se bazeaza pe adaugarea negatiei formulei care vrem s-o demonstram, la axiomele teoriei si se incearca obtinerea unei contradictii.
Daca vom nega formula scop care vrem s-o demonstram, vom obtine forma sa cauzala:
B1 Bn.
Lucrand de sus in jos si de la stanga la dreapta, plecand de la acest scop, sistemul va trece printr-o succesiune de subscopuri. Daca se obtine clauza vida, atunci am obtinut o contradictie si deci y1, , yr (B1 Bn) este o consecinta logica a lui P.
#n continuare ne propunem sa definim notiunile de pre-interpretare, interpretare si model, in cadrul general al unei teorii de ordinul intai.
Definitia s24. O pre-interpretare @ntr-un un limbaj L de ordinul @ntai este constituita din urmatoarele elemente:
multime nevida D, numita domeniul de pre-intgerpretare;
Asocierea fiecarei constantine b din L cu cate un element din D;
Asocierea fiecarei functi n-are din L cu cate o aplicatie a lui Dn in D.
Definitia s25. O interpretare I consta dintr-o pre-interpretare J, ca si din elementele urmatoare:
Asocierea fiecarui predicat n-ar din L cu cate o aplicatie a lui Dn in , adica definirea unei relatii n-are pe D.
Despre interpretarea I, definita in aceasta maniera, vom spune ca este bazata pe J.
Definitia s26. Fie J o pre-interpretare @ntr-un limbaj de ordinul intai L. O asignare de variabile, relativa la J, @nseamna asocierea fiecarei variabile din L cu cate un element din domeniul de pre-interpretare.
Definitia s27. Fie J o pre-interpretare de domeniu D @ntr-un limbaj de ordinul intai L si fie A o asignare de variabile. O asignare de termeni ai lui L, relativa la J si A, se defineste dupa cum urmeaza:
a) Operatia de asignare a unei variabile si asignata sa dupa A;
b) Operatia de asignare a unei constante si asignata sa dupa J;
c) Daca t1', , tn'sunt asignatele termenilor t1, , tnsi f' este asignata functiei n-are f, atunci elementul f'(t1', , tn') din D este asignata lui f(t1, , tn).
Definitia s28. Fie I, o interpretare de domeniu D @ntr-un limbaj de ordinul intai L si fie A o asignare de variabile. Unei formule din L ii putem asocia o valoare logica de adevar, adevarat sau fals, relativ la I si A, adica vom defini o functie, numita functie de adevar, pe multimea formulelor cu valori in multimea in felul urmator:
a) Daca formula este un atom
p(t1,,tn) atunci valoarea de adevar se obtine calculand
valoarea lui
b) Daca formula este de forma x P, atunci valoarea de adevar a formulei este adevarat daca exista d I D astfel incat P are valoarea de adevar adevarat relativ, la I si la A(x/d), daca nu exista un astfel de d, atunci valoarea lui P este fals. Aici A(x/d) este A in care x a fost inlocuit cu d.
c) Daca formula este de forma x P, atunci valoarea de adevar a formulei este adevarat daca pentru orice d I D, P are valoarea de adevar adevarat, relativ la I si la A(x/d), altfel valoarea lui P este fals.
d) Pentru negatie, conjunctie, disjunctie, implicatie, dubla implicatie, identificand valoarea de adevar adevarat cu 1 si pe cea de fals cu 0, definim functia de adevar dupa cum urmeaza.
1) daca P: Q, atunci V(P) =
2) V(P Q)=
3) V(P Q)=
4) V(P Q)=
5) V(P Q)=
Desi noi am folosit aceeasi notatie pentru functia de adevar asociata acestor cuantificatori, totusi este clar ca acestea sunt diferite. Aceasta notatie ne fereste de folosirea superscript-ilor. De exemplu pentru functia asociata conjunctiei ar fi ttrebuit sa folosim o notatie de forma f
In cuvinte regulile de mai sus se exprima astfel:
1 ) Negatia unei formule este adevarata cand formula este falsa si este falsa cand formula este adevarata.
2) Conjunctia a doua formule este adevarata cand ambele formule sunt adevarate, in rest este falsa.
3) Disjunctia a doua formule este adevarata cand cel putin una din formule este adevarata si este falsa cand ambele formule sunt false.
4) Implicatia a doua formule este falsa cand antecedentul este adevarat si concluzia falsa si este adevarata @n toate celelalte cazuri.
5) Dubla implicatie dintre doua formule este adevarata cand ambele formule au aceeasi valoare logica de adevar si este falsa in rest.
Reprezentarea grafica a functiei de adevar este tabla de adevar si pentru cele cinci functii defnite mai sus avem tabla de adevar din Figura s
P |
Q |
P |
P Q |
P Q |
P Q |
P Q |
Fig. s1. Tablele de adevar ale celor 5 functii de baza
Acum suntem @n masura sa demonstram si echivalenta dintre formulele
x1 xs (A1 A2 Ak B1 Bn)
si
x1 xs (A1 A2 Ak) (B1 Bn).
Pentru usurinta calculelor vom nota A1 A2 Akcu A, iar B1 Bn cu B.
Cu aceste notatii avem:
A |
B |
B |
A B |
B A |
Fig. ss Echivalenta formulei A B cu formula B A.
|inand seama de notatiile noastre si de legile lui de Morgen, care vor fi expuse mai tarziu, deducem ca B = B1 Bn. Cu acestea zise, echivalenta de mai sus este complet demonstrata.
Este clar ca valoarea de adevar a unei formule inchise nu depinde deasignarea facuta variabilelor sale.
n consecinta, se poate vorbi fara ambiguitate de valoarea de adevar a unei formule inchise relativ la o interpretare.
Daca valoarea de adevar a uneiformule inchise,relativ la o interpretare, este adevarat (respectiv fals), atunci vom spune ca formula respectiva este adevarata (respectiv falsa) relativ la acea interpretare.
Definitia s29. Fie I o interpretare @ntr-un un limbaj de ordinul intai L si fie F o formula in L.
Daca inchiderea existentialista a lui F este adevarata in I, atunci vom spune ca F este satisfacuta
Daca inchiderea existentialista a lui F este falsa in I, atunci vom spune ca F este nesatisfacuta in I.
Daca inchiderea universala a lui F este adevarata in I, atunci vom spune ca F este valida, in I.
Daca inchiderea universala a lui F este falsa in I, atunci vom spune ca F este nevalida in I.
#n locul terminologiei demai susputem folosi urmatoarele exprimari.
O formula valida este o tautologie.
O formula satisfacuta este consistenta sau realizabila. O formula nesatisfacuta este inconsistenta sau nerealizabila sau chiar contradictie
Terminologia introdusa justifica urmatoarele exprimari:
O formula este valida daca si numai daca negatia ei este inconsistenta.
O formula este inconsistenta daca si numai daca negatia ei este valida.
O formula este nevalida daca si numai daca @n orice interpretare este falsa.
O formula este consistenta daca si numai daca exista o interpretare @n care este adevarata.
O formula valida este consistenta.
O formula consistenta nu este neaparat valida.
O formula inconsistenta este nevalida.
O formula nevalida nu este neaparat inconsistenta.
Grafic, cele precizate mai sus am putea avea urmatoarea repreyentare:
Definitia s30. Fie I o interpretare intr-un limbaj de ordinul intai L si F o formula inchisa. Daca F este adevarata in I atunci vom spune ca I este un model al lui F.
Exemplu. Sa consideram formula x y p(x , y) si interpretarea I urmatoare. Domeniul D sa fie multimea angajatilor unei societati comerciale, iar p sa fie o relatie de subordonare si sa fie interpretat ca 'este subordonat lui'.
In interpretarea de mai sus formula noastra exprima faptul adevarat ca 'Pentru orice angajat x al unei societati comerciale exista un alt angajat y al societatii comerciale, astfel incat x este subordonat lui y'.
O alta interpretare care se poate da acestei formule ar fi urmatoarea: D sa fie multimea numerelor intregi pozitive, iar p sa fie interpretat ca fiind relatia <.
In aceasta interpretare formula noastra exprima faptul adevarat ca 'Pentru orice numar intreg si pozitiv x, exista un alt numar intreg pozitiv y, astfel incat x < y'.
Axiomele unei teorii de ordinul intai formeaza o submultime specifica de formule inchise ale limbajului teoriei.
De exemplu, teoriile de ordinul inti de care noi suntem foarte interesati au clauzele unui program drept axiome.
Conceptul de model al unei formule inchise se poate generaliza imediat la cel al unei multimi de formule inchise.
Definitia s31. Fie S o multime finita de formule inchise dintr-un limbaj de ordinul intai L si I o interpretare in L. Vom spune ca I este un model pentru S, daca I este un model pentru fiecare formula din S.
Deci sa observam ca daca S = este o multime finita de formule inchise, atunci I este un model pentru S daca ea este un model pentru F1 F2 Fq.
Definitia s3s Fie S o multime finita de formule inchise intr-un limbaj de ordinul intai L.
Daca in L se poate gasi o interpretare I care sa fie un model pentru S, atunci vom spune despre S ca este satisfcuta (realizabila, consistenta) in L. Daca toate interpretarile din L sunt modele pentru S, atunci vom spune despre S ca este valida (tautologie) in L.
Daca in L nu gasim nici o interpretare care sa fie un model pentru S, atunci vom spune despre S ca este inconsistenta in L.
Daca in L se poate concepe o interpretare care sa nu fie un model pentru S, atunci vom spune despreSca este nevalida in L.
s7. Substitutii. Unificare
In acest paragraf vom prezenta conceptul de unificare si vom da un algoritm pentru realizarea unificarii. Pentru aceasta avem nevoie de cateva notiuni pregatitoare. Precizam inca de la inceput ca ne situam tot in cadrul general al teoriei de ordinul intai. Mai intai vom defini substitutia.
Definitia s33. O multime finita de elemente de forma , in care fiecare vi este o variabila, iar fiecare ti este un termen distinct de vi si in care variabilele vi sunt distincte doua cate doua, o numim substitutie
Fiecare vi / ti este numita legatura pentru variabila vi. De obicei substitutiile se noteaza cu litere mici ale alfabetului grec. O substitutie in care toti termenii ti sunt inchisi vom spune ca este ea insasi inchisa. Daca toti termenii ti sunt variabile, atunci vom spune despre substitutia respectiva ca este o substitutie de variabile.
Definitia. s34. Se numeste expresie o conjunctie, sau o disjunctie de literale, sau un termen sau chiar literal.
Definitia. s35. Un atom sau un termen este o expresie simpla.
Definitia. s36. Fie o substitutie oarecare q si fie E o expresie. Definim instanta Eq a lui E prin q ca fiind expresia obtinuta din E prin inlocuirea simultana a tuturor aparitiilor variabilelor vi prin termenii lor corespunzatori ti.
Daca Eq este inchisa atunci ea se numeste instanta inchisa a lui E.
Observatie. Eq nu poate fi inchisa decat daca substitutia q este inchisa.
Exemplu. Fie E = p(x, y, f(a)) si fie substitutia q . Instanta lui E prin substitutia q, Eq, este p(b, x, f(a)).
Instanta, prin substitutia q, a unei multimi finite de expresii S = o notam cu Sq si este data de
Definitia. s37. Definim compunerea a doua substitutii q si s ca fiind submultimea qs in care se suprima orice legatura ui/sis pentru care ui=sis si orice legatura vj/tj pentru care vjI Aici sis este instanta lui si prin s
Exemplu. Fie q si s doua substitutii. In aceste conditii qs
Definitias38. Substitutia data de multimea vida o numim substitutie identitate si o notam cu e
Substitutiile au o serie de proprietati din care mai importante sunt:
qe e
2) (E)s = E();
s g sg
si le admitem fara demonstratie
Exemplu. Fie si s doua substitutii si fie expresia E = p(x, y, g(z)). In aceste conditii se poate verifica usor ca s si ca E = p(f(y),z, g(z)), (E = p(f(y), b, g(b)). De asemenea se poate arata ca E(qs) = p(f(y),b, g(b)) = (E
Definitia s39. Spunem ca expresia F este o varianta a expresiei E, daca exista o substitutie astfel incat E = F
Daca exista o substitutie a astfel incat F = E , atunci spunem ca E este o varianta a lui F.
Observatie. Doua expresii E si F reprezinta acceasi varianta daca exista doua substitutii si astfel incat F sa fie o varianta a lui E si E o varianta a lui F, adica E = F si F = Es
Exemplu. Fie E = p(f(x, y), g(z), a) si F = p(f(y, x), g(u), a) doua expresii. Sa demonstram ca cele doua expresii reprezinta variante ale aceleasi expresii. Pentru aceasta sa observam ca substitutia face ca F sa reprezinte o varianta a lui E, iar substitutia face ca E sa reprezinte o varianta a lui F.
Cu acestea spuse putem defini notiunea de unificator.
Definitia s40. Fie S o multime finita de expresii. Spunem ca o substitutie este un unificator al expresiilor lui S, daca si numai daca S se reduce la o singura expresie, (adica este un singleton, @n Franceza).
Cu alte cuvinte, daca presupunem ca multimea S este , atunci substitutia este un unificator daca si numai daca F1 = F2 = Fn Sau chiar mai mult, este un unificator pentru formulele F1, , Fn daca si numai daca acestea reprezinta variante ale aceleeasi expresii.
Definitia s41. Spunem ca un unificator este unificatorul cel mai general al lui S, daca orice alt unificator se poate scrie ca o compunere a lui cu o substitutie oarecare.
Definitia s4s Despre o multime care admite un unificator vom spune ca este unifiabila, iar unificatorul sau cel mai general il vom nota cu Umg.
#n engleza Umg se noteaza cu MGU (Most General Unifier).
Exemple
1) Fie S = . Aceasta multime de expresii nu este unifiabila.
2) Fie S = p(f(x),z), p(y, a) . S este unifiabila si un unificator al ei este a = y/f(a), x/a, z/a . Unificatorul cel mai general al acestei multimi este = Umg = y/f(x), z/a . Sa observam ca x/a
In continuare vom prezenta algoritmul de unificare. Intrarea acestui algoritm este nonstituita din multimea finita de expresii care se doreste sa se demonstreze ca este unifiabila. Iesirea acestui algoritm este formata din unificatorul general al expresiilor, daca multimea respectiva este unifiabila, iar daca multimea nu este unifiabila atunci algoritmul sesizeaza printr-un mesaj acest lucru.
Ideea pe baza careia lucreaza acest algoritm este urmatoarea. Sa presupunem ca dorim sa unificam doua expresii luate la intamplare. Sa ne imaginam doi pointeri, fiecare punctand catre simbolul cel mai din stanga al fiecarei expresii. Sa deplasam acum simultan cei doi pointeri catre dreapta pana cand ei vor puncta pe simboluri diferite. In aceasta situatie se incearca unificarea subexpresiilor, care incep cu cele doua simboluri diferite, printr-o substitutie. Daca exista o astfel de substitutie, procesul de unificare continua cu cele doua expresii obtinute prin aplicarea substitutiei. Daca nu exista o astfel de substitutie cele doua expresii initiale nu sunt unifiabile si procesul de unificare se opreste. Daca pointerii vor puncta pe sfarsitul celor doua expresii atunci acestea sunt unifiabile, iar compunerea tuturor substitutiilor facute pe parcursul unificarii da unificatorul general al celor doua expresii.
Pentru a prezenta algoritmul de unificare mai avem nevoie de un concept si anume de conceptul de multimea de diferente a unei multimi de expresii.
Definitia s43. Fie S o multime finita de expresii. Se numeste multimea de diferente a lui S multimea construita astfel:
Se repereaza simbolul cel mai din stanga al expresiilor din S care nu apare in toate expresiile acestea;
Se extrag din toate expresiile din S subexpresiile din pozitia corespunzatoare simbolului reperat la pasul 1.
Exemplu. Fie S = p(f(x), h(y), a), p(f(x), z, a), p(f(x), h(y), b) . Multimea diferentelor acestei multimi este h(y), z . Acum suntem in masura sa prezentam si algoritmul de unificare.
Pasul l. Se face k = 0 si sk e
Pasul s Daca S este o expresie simpla, atunci S este unifiabila, iar este un Umg al sau. Daca nu, determina multimea de diferente Dk a lui Ssk
Pasul 3. Daca exista v si t, doi termeni in Dk, astfel incat v sa fie o variabila caresanuaparaint,atuncideterminamsk+1 k v/t , incrementam k si reluam de la pasul s Daca nu exista v si t care sa indeplineasca conditiile de mai sus, atunci inseamna ca S nu este unifiabila.
Acest algoritm de unificare este nedeterminist, in sensul ca la pasul 3 se pot face mai multe alegeri pentru v si t. Prin urmare, pentru o problema data exista mai multe solutii. Cu toate acestea, odatafacuta o alegere algoritmul se termina intr-un numar finit de pasi, deoarece S nu contine decat un numar finit de variabile si fiecare aplicare a pasului 3, reduce numarul acestora cu cate o unitate.
Exemplu. Fie S = p(f(a), g(x)), p(y, y) . Sa aplicam algoritmul de mai sus sa vedem daca este unifiabila sau nu.
Avem:
a) =s.
b) D0 = f(a), y, s = y/f(a), Ss = p(f(a), g(x)), p(f(a),f(a)).
c) D1 = g(x), f(a) . Se constata ca nu sunt indeplinite conditiile de aplicare de la pasul 3 deci S nu este unifiabila .
Exemplu. Fie S = p(a,x,h(g(z)), p(z, h(y), h(y)) Ne propunem sa vedem daca este unifiabila si in acest caz sa determinam unificatorul sau general.
Avem:
1) k=0,0=s.
2) D0= , k:=k+1, deci s , prin urmare Ss
3) D1 = x, h(y), k:=k+l, deci = x/h(y), z/a, prin urmare S2 = p(a, h(y),h(g(a))), p(a, h(y), h(y)).
DZ = g(a), y, k:= k+l,deci 2 = x/h(y), z/a, y/g(a), iar Ss =p(a, h(g(a)), h(g(a))). Deci S este unifiabila iar unificatorul sau cel mai general este 3.
Exemplu. Fie S = p(x, x), p(y, f(y)) Sa se verifce daca S este unifiabila.
Avem:
1 ) k =0, 0 = s.
2) D0 = x, y, k:= k+1, deci = x/y, prin urmare Ss = p(y,y), p(y,f(y))
3) D1 = y, f(y). Deoarece y apare in formula f deducem caS nu este unifiabila.
s. Consecinte logice.
Acum suntem in masura sa dam citeva definitii mai des folosite in programarea logica si anume consecinta logica si formele normale.
Definitia s44. Fie S o multime de formule inchise si F o formula oarecare inchisa. Spunem ca F este o consecinta logica a lui S daca, orice interpretare care este un model pentru S este un model si pentru F.
Observatie. Daca S = F1 , Fn , este o multime finita de formule inchise, atunci F este o consecinta logica a lui S daca si numai daca formula F1 , Fn F este valida.
Propozitia. s1. Fie S o multime de formule inchise si F o formula oarecare inchisa intr-un limbaj de ordinul intai L. Festeoconsecinta logica a lui S daca si numai daca S F este inconsistenta in L
Demonstratie. Vom demonstra aceasta propozitie, demonstrand ca daca F este o consecinta logica a lui S, atunci S F este inconsistenta, apoi vom demonstra ca dacaS F este inconsistenta, atunci F este o consecinta logica a lui S.
Pentru inceput vom demonstra ca daca F este o consecinta logica a lui S, atunci S F este nerealizabila. Fie deci I, o interpretare oarecare din L, care este un model pentru S. Deoarece F este o consecinta logica a lui S, deducem ca I este un model si pentru F. Prin urmareI este unmodelpentruS F sidecinupoatefiunmodelsipentruS F caci atunci am avea ca F si F sunt ambele valide in aceeasi interpretare I.
Sa demonstram acum ca daca S F nu este realizabila atunci F este o consecinta logica a lui S. Fie I o interpretare in L care este si un model pentru S. Deoarece S F nu este realizabila deducem ca I nu este un model pentru s F, deci este un model pentru F. Prin urmare am demonstrat ca daca interpretarea I este un model pentru S, atunci ea este un model si pentru F, adica F este o consecinta logica a lui S.
Exemplu. Fie S = p(a), t/ x (p(x) q (x)) si fie F = q(a). Sa aratam ca F este consecinta logica a lui S. Fie I un model al lui S. In aceste conditii avem ca p(a) si x (p(x) q (x)) sunt adevarate in interpretarea I. Prin urmare si q(a) este adevarata in interpretarea I. Aceasta concluzie se obtine astfel: deoarece x (p(x) q (x)) este adevarata, atunci inlocuind pe x cu a obtinem ca si p(a) q (a) este adevarata. |inand seama acum ca si p(a) este adevarata, atunci aplicand regula modus ponens care spune ca daca A si A B sunt adevarate atunci si B este adevarata, obtinem ca, q(a) este adevarata. Cu acestea am demonstrat ca F este o consecinta logica a lui S.
s9. Forme normale prenexe
#n continuare ne propunem sa definim un alt concept al teoriei de ordinul intai si anume formele normale prenexe.
Folosind legea asociativitatii, intr-o formula in care expresiile (subformulele) sunt legate numai prin disjunctie, se poate renunta la utilzarea parantezelor in redactarea acesteia. Deci:
P1 ( P2 P3 ) = ( P1 P2 ) P3 =P1 P2 P3.
In general scriem:
Analog, folosind asociativitatea conjunctiei putem elimina parantezele, din redactarea acesteia si in general putem scrie:
care este o formula adevarata daca si numai daca toate subformulele care o compun sunt adevarate.
Definitia s45. Spunem ca o formula P este in forma normala conjunctiva prenexa (FNC) daca ea are forma Qx1, Qx2,,
Qxs (
Definitia s46. Spunem
ca o formula P este in forma normala
disjunctiva prenexa (FND) daca ea
este de forma Qx1, Qx2,, Qxr (
Exemple
Formula
Formula
Definitia s47. Daca inchiderea universala a formulei V W este valida in orice interpretarea I, @ntr-un limbaj de ordinul intai L, atunci vom spune ca cele doua formule V si W sunt logic echivalente
Cu alte cuvinte, doua formule sunt logic echivalente daca si numai daca au aceleasi valori de adevar in toate interpretarile, pentru orice asignare de variabile.
Propozitia ss Pentru orice formula W exista o alta formula V, in forma normala conjuctiva prenexa si o formula, in forma normala prenexa disjunctiva, U, astfel incat cele trei formule sunt logic echivalente.
Demonstratie. Nu vom da o demonstratie propriu-zisa ci vom prezenta un algoritm de transformare a unei formule in forma normala conjuctiva sau didjunctive.Inacestsensse potefectua urmatoarele transformari :
1 ) Eliminarea implicatiei: Orice formula de forma F G se inlocuieste cu formula F G, care este logic echivalenta.
2) Eliminarea dublei implicatii. Orice formula de forma F G se inlocuieste cu formula (F G) F G), logic echivalenta.
3) Mutarea negatiei:
Se fac urmatoarele inlocuiri:
a) Orice formula de forma x F se inlocuieste cu formula logic echivalenta x F
b) Orice formula de forma x F se inlocuieste cu formula logic echivalenta x F.
c) Orice formula de forma (F G ) se inlocuieste cu formula logic echivalenta F G.
d) Orice formula de forma (F G ) se inlocuieste cu formula logic echivalenta F G.
e) Orice formula de forma F se inlocuieste cu formula logic echivalenta F.
Pasul 3 se repeta pana cand fiecare negatie precede imediat un atom.
Observatie. La pasul 3, punctele c) si d) este vorba de cunoscutele formule ale lui Van de Morgen:
4) Mutarea cuantificatorilor: In cadrul acestui pas orice formula, de una din formele din tabla de mai jos, din partea stanga, se inlocuieste cu forma sa echivalenta, din partea dreapta:
x F G |
x (F G) |
F x G |
x (F G) |
x F G |
x (F G) |
F x G |
x (F G) |
x F G |
x (F G) |
F x G |
x (F G) |
x F G |
x (F G) |
F x G |
x (F G) |
Se repeta pasul 4 pana cand toti cuantificatorii se muta la inceputul formulei principale.
5) Mutarea conjunctiei.Se aplica formulele distributivitatii, la stanga si la dreapta, a disjunctiei fata de conjunctie:
Pasul 5 se aplica pana cand formula data ajunge in forma conjuctiva normala prenexa.
Observatie. Daca se doreste obtinerea unei forme normale disjunctive atunci la pasul 5 se foloseste distributivitatea conjunctiei fata de disjunctie, adica se folosesc formulele:
In acest caz pasul 5 se numeste mutarea disjunctiei.
Propozitia s2 afrma ca oricarei functii de adevar (tabela de adevar) ii corepunde o formula restransa, adica o formula in care nu apar decat conectorii
s10. Skolemizarea formulelor
In cele ce urmeaza vom arata cum putem sa asociem unei formule date F, o noua formula G care are aceleasi proprietati de consistenta cu F.
Formula G va avea o forma prenex din care lipsesc cuantificatorii existentialisti. O astfel de forma o vom numi Skolem iar procedeul prin care, dintr-o formula data, F, obtinem una skolem, G, il numim skolemizare.
Skolemizarea unei formule presupune parcurgerea urmatorilor pasi:
Pasul 1. Se aduce formula data la o forma prenex (conjunctiva sau disjunctiva.
Pasul s Se elimina cuantificatorii existentialisti din forma astfel obtinuta.
Eliminarea cuantificatorilor existentialisti din forma prenex se bazeaza pe o idee din matematica care spune ca orice marime precedata de un cuantificator existentialist esteo functie de variabilele din fata ei care sunt precedate de un cuantificator universal. Sau pe scurt, variabilele existentialiste depind implicit de variabilele universale care le preced.
Mai exact se procedeaza astfel: fie Q1 x1 Qnxn prefixul formei prenex obtinuta la pasul 1 prin aplicarea algoritmului de skolemizare.
Fiecare variabila xi precedata de un cuantificator existentialist se inlocuieste in formula cu o functie fi, care are ca argumente variabilele xj cu j < i precedate de cuantificatorul universal.
Deoarece in formula skolemizata prefixul contine doar cuantificatorul universal, convenim ca acestasa nu se mai scrie cand redactam forma skolem.
Exemplu. Sa se aduca la forma skolem formula:
x (P(x,y) y u (Q(y) (R(a,u) z T(z,u))))
Rezolvare. Forma prenex a acestei formule este:
x t u z (P(x,y) Q(t) (R(a,u) T(z,u))).
Variabila y fiind libera, se considera formula:
y x t u z(P(x,y) Q(t) (R(a,u) T(z,u))).
Eliminand cuantificatorii existentialisti se obtine formula:
x t z(
Inlaturand prefixul obtine m forma skolem:
(
s11. Metode pentru demonstrarea validitatii
unei formule
Ca o aplicatie directa a teoriei de ordinul @ntai @n demostrarea validitatii formulelor din logica propozitiilor, vom relua notiunea de functie de adevar pe care am definit-o @n Sectiunea s5.
In procesul de interpretare a formulelor, atomii din care acestea sunt alcatuite primesc valori de adevar. Aceasta activitate convenim s-o numim evaluare. Deoarece atomii primesc valori ei se mai numesc si variabile logice sau propozitionale.
Functia de adevar face ca fiecarei evaluari, a atomilor unei formule, sa-i corespunda una din valorile de adevar adevarat sau fals. Prin identificarea adevarului cu 1 si a falsului cu 0, functia de adevar asociaza oricarei evaluari a atomilor constituienti, una din valorile 0 sau l.
Pentru
negatie functia de adevar este
P |
P |
Pentru
conjunctie, functiade adevar este
P |
Q |
P Q |
Unei formule cu n atomi, priviti ca variabile propozitionale, ii corespunde o functie de adevar de n variabile, iar tabla ei de adevar va avea 2n linii pentru cele 2n evaluari posibile.
Aceste evaluari se obtin in felul urmator.
Daca formula are o singura variabila propozitionala atunci aceasta nu poate primii decat doua valori: fals sau adevarat, adica 0 sau 1 in acceptiunea noastra. Deci exista doua linii in tabla de adevar asociata formulei. Deocamdata nu facem nici o remarca in ceea ce priveste numarul coloanelor tablei de adevar.
Daca formula are doua variabile propozitionale, atunci prima dintre ele are 2 evaluari posibile: 0 si l. In ideea specificarii tuturor combinatiilor posibile, a doua variabila trebuie sa fie si ea falsa si adevarata, cand prima este adevarata si de asemenea falsa si adevarata, cand prima este falsa. Prin urmare vom avea 4 evaluari posibile ale formulei date. Deci tabla de adevar asociata acesteia va avea 4 = 22 linii.
Conform metodei inductiei matematice presupunem acum ca daca formula are k variabile propozitionale, atunci ea are 2k evaluari posibile si deci tabla ei de adevar va avea 2k linii.
Sa demonstram acum ca daca formula are k +1 variabile propozitionale atunci ea va avea 2k+1 evaluari posibile.
Deoarece formula are k + 1 variabile propozitionale, considerand ca prima variabila are o valoare fixata, de exemplu pe l, atunci in formula mai raman k variabile propozitionale. Conform metodei inductiei matematice deducem ca pentru aceata valoare fixata a primei variabile formula noastra va avea 2k evaluari posibile corespuzatoare celorlalte k variabile.
Considerand acum si cea de-a doua valoare fixata, pentru prima variabila, vom obtinealte 2k evaluari posibile ale formulei. Deci in total vom avea 2k + 2k = 2k+1 evaluari posibile pentru formula data.
Cu acestea am demonstrat ca daca o formula are n atomi atunci ea va avea 2nevaluari. Fiecare linie din tabla de adevar asociata formulei corespunde cate unei evaluari a atomilor sai si ea se mai numeste si interpretare a formulei.
Tot din
aceasta demonstratie se poate deduce ca, pentru o formula cu n variabile
propozitionale exista
In cazul formulelor cu n = 2, deci al formulelor cu doi atomi, exista 16 moduri distincte de aranjare a lui 0 si 1 in ultima coloana, deci exista 16 functii de adevar distincte. Din acestea, noi am selectat doar patru: conjunctia, disjunctia, implicatia si dubla implicatie. Numarul formulelor care se pot face cu doua variabile propozitionale este infinit. Rezulta ca aceeasi tabla de adevar corespunde la mai multe formule.
Exemplu
Sa se scrie tabla de adevar a formulei (P Q) (R S)
Tabla de adevar a formulei noastre are 16 linii, deoarece are 4 variabile logice si este redata mai jos.
P |
Q |
R |
S |
S |
P Q |
R S |
formula |
Ca tehnica de lucru este mai simplu sa reprezentamtabla de adevar, scriind formula pe linia de sus a tabloului, evaluarea atomilor pe coloana in dreptul fecareispsrstii a lor si apoi in dreptul conectorilor logici, valoarea de adevar a rezultatului evaluarii lor.
Pentru exemplificare sa consideram formula (p q) p. Avem:
p q p |
|
||||
Completam apoi coloana de sub conjunctie
p q p |
||||
si in sfarsit, sub implicatie
p q p |
||||
Tabla de adevar da o procedura mecanica de stabilire a validitatii unei formule si acest lucru constituie un avantaj in rezolvarea problemelor de validitate a propozitiilor. Se constata insa ca numarul liniilor din tabla de adevar creste exponential cu numarul variabilelor propozitionale din formula ceea ce duce la formarea unor table de adevar greu de manevrat. Din aceste motive s-au cautat alte metode de demonstrare a validitatii unei formule, metode care sa nu recurga la tabla de adevar.
Dintre aceste metode mai cunoscute sunt: metoda lui Quine si metoda reducerii. Mai tarziu, in cadrul paragrafului Reguli de inferenta, vom prezenta si o alta metoda pentru demonstrarea realizabilitatii unei formule care nu foloseste tabla de adevar si anume metoda deductiilor succesive.
Metoda Quine
Metoda lui Quine de demonstrare a realizabilitatii unei formule consta in urmatorii pasi.
1) Se inlocuieste atomul cu cea mai mare frecventa de aparitie in formula, o data cu V (adevarat) si a doua oara cu F (fals), obtinandu-se doua formule.
2) In fiecare din aceste formule se aplica regulile de mai jos:
a) Se suprima V ca element al conjunctiei (V x=x).
b) Se suprima F ca element al disjunctiei (F+x=x).
c) Se inlocuieste conjunctia in care apare F cu F (F x=F).
d) Se inlocuieste disjunctia in care apare V cu V (V+x=V).
e) O implicatie care contine pe V se inlocuieste cu consecventul.
f) O implicatie care contine pe F se inlocuieste cu negatia antecedentului (F x = V; x F = x).
g) Se suprima V ca membru ai unei duble implicatii (x V=x ; V x=x).
h) O dubla implicatie care contine F se inlocuieste cu negatul celuilalt membru al ei (F x = x; x F = x).
3) Se aplica regulile 1 si 2 pentru urmatorul atom cu cea mai mare frecventa de aparitie, pana la epuizarea atomilor.
4) Daca rezultatul final este F peste tot, atunci formula este nerealizabila; daca rezultatul este V peste tot, atunci ea este tautologie, iar daca se obtine atat F, cat si V, formula este realizabila sau nevalida.
Toate regulile de la pasul 2 se bazeaza pe tablele de adevar ce definesc conectorii logici. Astfel:
- regula a) exprima faptul ca adevar si orice este orice;
- regula b) exprima faptul ca fals sau orice este orice;
- regula c) exprima faptul ca fals si orice este fals;
- regula d) exprima faptul ca adevar sau orice este adevar;
- regula e) se deduce din tabla de adevar a implicatiei din se observa ca adevar implica orice este orice si orice implica adevar este adevar;
- regula f) se deduce tot din tabla de adevar a implicatiei din care se observa ca fals implica orice este adevar si orice implica fals este negatul premisei;
- regula g) se deduce din tabla de adevar a dublei implicatii din care se observa ca: adevar daca si numai daca orice, este orice sau, orice daca si numai daca adevar, este orice.
- regula h) se deduce tot din tabla de adevar a dublei implicatii, din care se observa ca fals daca si numai daca orice, este not orice sau, orice daca si numai daca fals, este not orice.
Exemplu. Fie formula ((p q) p r)) (q r).
Sa vedem caracterul (tautologie, contradictie sau realizabilitate) acestei formule. Aplicam metoda Quine. Aici toti atomii apar de cate doua ori; alegem unul din ei, fie acesta p. Se inlocuieste acesta cu V si apoi cu F si obtinem arborele infologic de mai jos:
((p
q) p
r)) (q r) ((V
q)
(F r)) (q r) ((F
q)
(V r)) (q r) (F r) (q r) (q
F) (q r) q (q r) F (F r) V (V r) V r V F r V r (q r) V (q F) F (q V) q F V q F V
Deoarece am obtinut atat rezultate de F, cat si de V, deducem ca formula nu este nici o tautologie, nici o contradictie, cieste realizabila.
Metoda reducerii
Oaltametodafolositapentrudemonstrareacaracteruluiunei formule, care nu foloseste tabla de adevar, este metoda reducerii. Ea se bazeaza pe falsifcarea formulei date. Deci, se presupune ca exista o interpretare a formulei in care aceasta este falsa (0). Inscriem aceasta valoare sub conectorul principal al formulei, iar deasupra lui numarul pasului efectuat.
Daca formula este de forma P Q, atunci pasul 1 este:
P Q
Dar P Q este falsa numai cand P este adevarat si Q este fals. Deci vom scrie sub conectorul principal din P valoarea 1 si deasupra sa valoarea 2 si vom scrie sub conectorul principal din Q valoarea 0 si deasupra sa valoarea s Continuam in acest fel pana cand obtinem:
a) o evaluare consistenta pentru toate variabilele propozitionale, sau
b) nu gasim o astfel de evaluare.
In primul caz, ipoteza este corecta si deci formula este falsa; in al doilea caz falsificarea esueaza si deci formula este valida.
Daca formula este de forma P Q, atunci primul pas este1
P Q
Dar conjunctia este falsa in mai multe cazuri si deci trebuie analizate pe rand acestea. Daca in toate cazurile se obtin evaluari necontradictorii, atunci formula poate fi falsificata, deci este inconsistenta. Daca unele evaluari sunt contradictorii si altele nu, atunci ea este realizabila. Daca toate cazurile conduc la evaluari contradictorii, atunciformula nu poatefi falsificata si deci este o tautologie.
Tot la o discutie pe cazuri conduc si ceilalti conectori , care se trateaza intocmai ca la conjunctie.
Exemplu. Fie formula ((p q) r) r p) q).
2 3 1 3 2 3
((p q) r) r p) q)
1 1 1 0 1 0 0
Aici am obtinut V(r)=l, deci V( r)=0.
Deci, din r p deducem p = l, dar p q pentru p = 1 implica q=l, ori tot la pasul 3 avem q=0. Prin urmare, am obtinut o contradictie, deci formula nu se poate falsifica. Ca atare, este o tautologie.
s1s Traducerea tablelor de adevar in formule
Panaacumne-amocupatdeconstruireatabelelordeadevar (functiilor de adevar) ale formulelor. Dar, se poate pune si problema inversa, 'Ce formula corespunde unei tabele de adevar date? '. Rezolvarea acestei probleme are doua solutii si anume una FNC si una FND.
A. Construirea formulei FND
Pentru a obtine forma FND procedam astfel:
Sa presupunem ca toate valorile de adevar ale formulei cautate (valorile din ultima coloana a tabelei de adevar) sunt l. Daca formula are n atomisievaluarilelorsuntdeformal,1,1,atunciformula ( p1 p2 pn ) este formula cautata, care corespunde tuturor cerintelor tabelei de adevar si are avantajul ca este sub forma FNC.
Presupunem acum ca cel putin
pentru una din cele 2n evaluari ale atomilor, formula pe care o cautam
are valoarea l, dar evaluarile lor sunt de forma 1, 0, 0, , 0, atunci vom cauta
o formula (o expresie continand atomi) care sa fie adevarata in acea evaluare si
falsa in celelalte. Metoda consta in scrierea unei conjunctii de atomi, care sa
aiba valoarea indicata de linia din tabela de adevar. Astfel, pentru evaluarea
de forma 1, 0, , 0, avem conjunctia
In
general, pentru o evaluare data atomilor p1, p2,,pn,
in care citim 1 pe ultima coloana a tabelei de adevar, construim o conjunctie
de atomi, punand pi daca pi are evaloarea V(pi)
= 1 si
Presupunem acum ca tabela de adevar da in mai multe locuri valoarea l, pentru formula care o cautam. In acest caz, procedam pentru fiecare linie ca mai sus, construind cate o conjunctie de baza pentru fiecare interpretare, apoi facem o disjunctie a acestor conjunctii. Rezultatul obtinut este o formula FND in care fecare conjunctie va transmite valoarea 1 pentru interpretarea pentru care a fost construita, pentru celelalte interpretari conjunctiile vor avea valoarea 0. Deci, in acest fel, am obtinut o formula FND care raspunde cerintelor tabelei noastre de adevar.
B. Construirea formulei FNC
Sa construim acum o formula
FNC care sa raspunda aceleiasi table de adevar.Un rationament asemanator celui
de mai sus ne duce la concluzia ca, pentru fecare linie din tabela de adevar,
in care formula are valoarea 0, exista o disjunctie care ia, ca si formula data,
valoarea 0 numai pe acea linie. Daca formula are n atomi si evaluarea lor este
de forma 1, l, l, atunci
Conjunctiile sau disjunctiile care au proprietatea ca iau aceeasi valoare de adevar ca si formula, in cate o interpretare a ei, se numesc minitermeni, respectiv maxitermeni. Minitermenii se mai numesc si clauze conjunctive, iar maxitermenii, clauze disjunctive. Formarea lor este precizata in rationamentul indicat.
Minitermenii
se formeaza scriind in dreptul fiecarei interpretari o conjunctie, in care
apare pi, daca V(pi) = 1 si
Pentru exemplifcare vom scrie clauzele conjunctive si disjunctive ce corespund unei tabele de adevar a unei formule cu trei atomi.
p1 |
p2 |
p3 |
P |
Minitermeni |
Maxitermeni |
|
|
||||
|
|
||||
|
|
||||
|
|
||||
|
|
||||
|
|
||||
|
|
||||
|
|
Formula ce corespunde acestei tabele de adevar este disjunctia minitermenilorcecorespundlui1incoloanaP,sauconjunctia maxitermenilor ce corespund lui 0 in coloana P.
Fie tabela de adevar.
p |
q |
r |
P |
|
Care este formula restransa ce corespunde acestei table de adevar?
Cele trei conjunctii corespunzatoare valorilor 1 ale formulei sunt:
deci formula cautata este disjunctia celor trei clauze conjunctive, adica:
P: (
Cele cinci clauze disjunctive ce corespund valorilor 0 ale formulei sunt:
Deci formula FNC corespunzatoare tablei de adevar date este:
P: (
Prin urmare am obtinut urmatoarele doua propozitii:
1. Orice formula necontradictorie este echivalenta logic cu o formula restransa sub forma FND.
s Orice formula care nu este tautologie este echivalenta logic cu o formula restransa sub forma FNC.
Utilizand tabla de adevar, orice formula se poate scrie sub o forma restransa de tip FNC sau FND.
Exercitii.
Stabiliti forma normala pentru formulele:
1) P: ((p q) (q p)) ((r s) (q
2) Q: (p (q r)) s
3) Daca
P:creste cursa inarmarilor
Q: sentimentul de securitate scade
R: protestul pacifistilor se inteteste
Sa se arate ca din P Q, Q R si P rezulta R .
s13. Reguli de inferenta
Regulile de inferenta sunt acele reguli care ne permit efectuarea unui rationament riguros, pe baza caruia putem trage concluzii asupra validitatii unor formule, plecand de la alte formule.
Inainte insa de a prezenta regulile de inferenta vom introduce notiunile de forma (formula) argument si argument valid.
Definitia s48. O forma argument este o succesiune de declaratii simbolizate prin P1,,Pn urmate de o concluzie Q.
Definitia s49. O forma argument este valida daca si numai daca concluzia ei, Q, poate fi dedusa logic din conjunctia declaratiilor sale. Cu alte cuvinte o forma argumenteste valida daca si numai daca implicatia P1 Pn Q este adevarata.
Daca o forma argument este valida atunci orice argument al sau este valid.
Din definitia formei argument deducem ca o succesiune de declaratii, ca cea de mai jos, este o forma argument:
p q
p
atunci, q.
O alta forma argument ar fi
p q
q
atunci, p.
Bineinteles ca se pot imagina si altfel de forme argument, dar cele doua de mai sus se bazeaza pe definitia argumentului valid.
Pentru a testa validitatea unui argument al, unei formule argument de una din formulele de mai sus rescriem formulele
p q
p
atunci, q.
rescriem formula dandu-i aspectul: ((p q) p) q, dupa care se poateaplica orice metoda pentru demonstrarea validitatii acestei formule. De exemplu, utilizand tabla de adevar, obtinem imediat:
p |
q |
p q |
(p q) p |
(p q) p q |
Deoarece in tabla de adevar, in ultima coloana, cea corespunzatoare formulei, toate valorile sunt l, deducem ca forma resectiva este o forma argument valida si deci orice argument al sau este un argument valid. Spre deosebire de aceasta forma argument cea de a doua forma argument din cele de mai sus nu este valida.
Acum suntem in niasura sa enuntam inca o metoda de de3nonstrare a validitatii unei formule, care nu se bazeaza pe tabla de adevar. Este vorba de metoda deductiilor succesive. Principiul de demonstratie, care nu foloseste tabla de adevar, este urmatorul: O demonstratie, in care un argument dat este valid, este o secventa de instructiuni in care fiecare instructiune este o premisa a unei forme, sau este dedusa dintr-o instructiune anterioara a secventei, pe baza unei forme argument valide, iar ultima instructiune din secventa este concluzia unei forme argument.
In continuare ne propunem sa dam o scurta ilustrare aacestui principiu. Sa consideram urmatoarele asertiuni:
1) Daca exploatarea excesiva a minelor de carbune are efecte nocive asupra mediului, atunci guvernul va lua masuri de reducere a acestor efecte.
2) Exploatarea excesiva a minelor de carbune are efecte nocive asupra mediului.
3) De aceea guvernul ia masuri de reducere a acestor efecte.
Sa notam cu EEMCEN propozitia Exploatarea excesiva a minelor de carbune are efecte negative asupra mediului si cu GMR propozitia Guvernul ia masuri de reducere a acestor efecte. Forma argument asociata asertiunilor 1-3 va capata aspectul:
l')EEMCEN GMR
2') EEMCEN
/GMR
O demonstratie a validitatii acestei forme trebuie sa fie o secventa de instructiuni. Fiecare instructiune este o premisa sau trebuie sa fie dedusa din instructiunile anterioare printr-o forma argument valida. Folosind regula modus ponens, se poate vedea ca deducerea lui GMR, se face rintr-o singura instructiune:
l')EEMCEN GMR
2') EEMCEN
/GMR
3') GMR obtinuta din l', 2' pe baza regulii modus ponens.
Regulile de inferenta, pe baza carora se pod deduce noi argumente valide sunt urmatoarele:
1. Modus ponens (MP) p q q /q |
s Modus Tollens (MT) p q q q |
3. Silogismul ipotetic (SI) p q q r /p r |
4. Silogismul disjunctiv (SD) p q p /q |
5. Dilema constructiva (DC) (p q) (r s) p r /q s |
6. Absobtia (Abs) p q /p (p q) |
7. Simplificarea (S) p q /p |
8. Conjunctia (C) p q /p q |
9. Adunarea (Ad) p /p q |
Alte reguli care nu au denumiri ar fi urmatoarele:
p dandu-se p atunci, orice implica p
/q
p (q r) daca o implicatie urmeaza lui p, atunci atat
/(p q) (p r) antecedentul cat si consecventul acesteia urmeaza lui p
q p daca q implica p atunci p implica q.
/p q
Pe langa aceste reguli inferenta logica se mai bazeaza si pe alte lucruri (fapte) cunoscute. De exemplu ea se poate baza pe echivalente logice. Cateva din cele mai cunoscute echivalente logice sunt:
l. (p q)=(q p) comutativitatea conjunctiei
s (p q)=(q p) comutativitatea disjunctiei
4. p (q r)=(p q) (p r) distributivitatea disjunctiei fata de conjunctie
5. p (q r) = (p q) (p r) distributivitatea conjunctiei fata de disjunctie
. p=
7.
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1835
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved