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 este considerata ca o definitie de procedura. Daca este un scop, atunci fiecare este considerat ca un apel de procedura. Deci una din etapele de stabilire a scopului initial o constituie unificarea fiecarui cu capatul al unei unei clauze de program. In acest fel, scopul initial este inlocuit cu scopul intermediar , unde este substitutia care a permis realizarea unificarii. Unificarea devine in acest fel un mecanism, atat pentru transferul parametrilor, cat si pentru alegerea si construirea datelor.

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 este considerat ca un sistem de procese paralele, iar o etapa de rezolvare o constituie aducerea unui proces la un sistem de procese (cele care apar in corpul clauzei care satisface apelul). Variabilele partajate intre procese sunt considerate ca niste cai de comunicatie intre sisteme. Din aceasta categorie de limbaje citam: PARLOG, PROLOG si GHC.

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 sau

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 , adica literele mici de la sfarsitul alfabetului latin. Constantele vor fi notate prin literele adica literele mici de la inceputul alfabetului latin. Functiile, de diverse aritati, vor fi notate prin literele . Predicatele, de diferite aritati, vor fi notate prin literele Literele prin care desemnam diversele elemente ale teoriei de ordinul intai pot fi indiciate. Conectorii folositi in logica formala sunt: , iar cuantificatorii sunt: In fine, semnele de punctuatie sunt: , si "virgula".

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 , si operatiile efectuate asupra lor vor fi abstractii, susceptibile desigur de interpretare ca propozitii, dar asta nu in cadrul demonstratiei, ci ulterior.

Atata timp cat acceptam referirea la ca fiind propozitii (si eventual le exemplificam) spunem ca lucram 'intuitiv', in contrast cu stilul formal. In cele ce urmeaza, cele doua puncte de vedere coexista.

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 , si vom reprezentare aceasta propozitie sub forma (Nu este adevarat ca o actiune are o valoare nominala), care este echivalenta cu asertiunea: o actiune nu are o valoare nominala. Alteori, negatia unei propozitii p o vom nota si prin .

Prin urmare, nu din vorbirea curenta se traduce in logica propozitiilor prin conectorul (sau ). #n vorbirea curenta, negarea unui fapt se poate face si altfel: unele cuvinte sunt negatele altora. De exemplu calificativul tare reprezinta negatia lui moale, bun reprezinta negatia lui rau s.a.m.d. Economia unei tari poate fi caracterizata ca fiind in crestere sau in recesiune. Recesiune reprezinta negatia lui crestere, adica o economie care nu este in crestere, neaparat este in recesiune. De asemenea climatul social dintr-o tara poate fi stabil sau instabil.

B. Traducerea conjunctiei si

Sa consideram asertiunea: 401 este cont de decontare cu furnizorii si 13 este cont de casa.

Se constata cu usurinta ca aceasta asertiune se compune din doua propozitii simple

p: 401 este cont de decontare cu furnizorii

si

q: 13 este cont de casa.

Deci, ea se mai poate scrie si sub forma sau folosind conectorul , sub forma

Conjunctia din vorbirea curenta s-a tradus aici prin conectorul . Dar nu intodeauna conjunctia si se poate traduce prin acest conector. De exemplu, in expresia: Romania si SUA sunt aliate, conjunctia si nu indica o compunere de doua propozitii. Alteori, conjunctia din logica propozitiilor este introdusa in vorbirea curenta prin particula iar. De exemplu, in asertiunea: 401 este cont de decontare cu furnizori, iar 13 este cont de casa, particula iar se traduce in logica propozitiilor cu ajutorul conectorului

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.

Se constata ca, de fapt, aceasta asertiune se compune din doua propozitii mai simple:

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, , nu ar fi avut nici o semnificatie nici din punct de vedere al vorbirii, deoarece, nu ar fi avut subiect.

Cu aceste notatii, asertiune initiala se poate scrie mai pe scurt si sub forma , sau, utilizand conectorul , 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 , folosind conectorul logic

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 , dar nu se poate pune semnul egal intre cei doi conectori datorita caracterului ambiguu al particulei sau. Uneori aceasta particula presupune realizarea unuia din cei doi atomi care-i leaga, neexcluzand insa realizarea ambilor atomi, alteori este exclusa realizarea ambilor atomi.

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 , particula sau, nu are caracter exclusivist, ea permite realizarea ambelor evenimente.

D. Traducerea implicatiei

Pentru exemplificarea folosirii conectorului logic sa consideram asertiunea: Daca o tara incalca drepturile omului, atunci Romania refuza sa aiba relatii comerciale cu ea.

Acest exemplu este foarte simplu si se constata ca se poate scrie sub forma , care se citeste Daca , atunci . Deci simbolul este folosit pentru a traduce implicatia logica, iar si au semnificatiile urmatoare.

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 , care se citeste

E. Traducerea dublei implicatii

Pentru a ilustra folosirea conectorului logic al dublei implicatii, sa consideram urmatoarea asertiune: Bugetul de stat creste daca si numai daca se inceteaza subventionarea firmelor nerentabile.

Se constata fara nici o dificultate ca aceasta asertiune se poate scrie sub forma , care se citeste , unde si au semnificatiile de mai jos:

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: , unde reprezinta propozitia Bugetul de stat creste, iar reprezinta propozitia Se inceteaza subventionarea firmelor nerentabile.

F. Traducerea cuantificatorilor

Sa exemplificam acum folosirea cuantificatorilor. Sa consideram urmatoarea asertiune: Orice student este absolvent de liceu. Aceasta asertiune se poate scriesub forma: student, este absolvent de liceu. Notand acum cu propozitia este student, in care apare variabila , obtinem o alta exprimare a asertiunii initiale si anume: , student, .

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: student, , unde este: nu este absolvent de liceu, iar cea de a doua sub forma: student, unde este: este absolvent de liceu. Vom adopta una sau alta din interpretarile care putem sa le dam functie de mesajul pe care dorim sa-1 transmitem.

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, , iar atunci cand vrem sa spunem ca numai anumite elemente ale unei multimi au o proprietate, folosim cuantificatorul existential,

De exemplu pentru a spune ca orice numar natural este pozitiv, folosim o expresie de forma: Daca am vrea sa spunem ca Orice om are o data de nastere, atunci am putea folosi o expresie de forma: are o data de nastere, unde prin am notat multimea oamenilor.

Daca vrem sa spunem ca numai anumite numere naturale sunt pare putem folosi o expresie de forma: este numar par.

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 este numar par, am putea folosi o scriere de forma , iar in loc de este numar pozitiv , s.a.m.d. Iar sub aceasta forma defintiile si conceptele pe care le vom introduce ulterior vor avea un caracter de generalitate mai mare, ceea ce constituie un avantaj din punctul de vedere al teoriei noastre.

Desigur, domeniul de interpretare are o mare importanta @n stabilirea valorii de adevar a unei formule. De exemplu, daca in formula , care o interpretam sub forma este un numar pozitiv, consideram domeniul de interpretare ca fiind multimea numerelor naturale, atunci orice valoare am da lui am obtine o propozitie adevarata. Daca vom considera ca domeniul de interpretare este multimea numerelor intregi, atunci propozitia respectiva este falsa pentru anumite valori ale variabilei anume pentru valori negative. Daca interpretam sub forma este cetatean roman, sigur ca putem stabili diverse domenii de interpretare in care aceasta propozitie este intotdeauna adevarata, sau numai uneori, sau intotdeauna falsa.

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

: Numerele pare se divid cu 2

si

: Recolta de grau de anul acesta este bogata,

atunci, in logica propozitiilor are sens compunerea , care in vorbirea curenta ar insemna Numerele pare se divid cu 2 daca si numai daca recolta de grau de anul acesta este bogata. Or, intre cele doua fenomene nu exista nici o legatura. In vorbirea curenta astfel de exprimari nu pot sa apara pentru ca propozitiile care se formeaza au intotdeauna acelasi context.

s4. Formule

In logica propozitiilor, prin combinarea propozitiilor simple se obtin propozitii care in logica formala se numesc formule. Deci , , , in logica propozitiilor sunt propozitii, iar in logica formala sunt formule.

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 este o functie n-ara si sunt termeni, atunci este un termen

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 t₁, , t_n sunt termeni, atunci p(t₁, , t_n) 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 x₁, . . . x_n (L₁, L₂ L_m), unde fiecare L_i este un literal, iar x₁,, x_n sunt toate variabilele care apar in formula L₁, L₂ L_m.

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 x₁ x_s (A₁ A₂ A_k B₁ B_n), unde A₁, , A_k, B₁ , B_n sunt atomi, iar x₁,, x_s sunt toate variabilele care apar in acesti atomi, o vom nota prin

A₁ ,A_k B₁,,B_n.

In aceasta notatie, cauzala B₁,,B_n se numeste antecedent, sau premisa, iar A₁ ,A_k consecvent sau concluzie. #ntr-o notatie cauzala toate variabilele sunt presupuse a fi universal cuantificate, virgulele in antecedentul B₁,,B_n desemneaza conjunctia, iar in consecventul A₁ , ,A_k desemneaza disjunctia.

Aceste conventii se justifica prin faptul ca formula

x₁ x_s (A₁ A₂ A_k B₁ B_n)

este echivalenta cu

x₁ x_s (A₁ A₂ A_k) (B₁ B_n)

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 A₁ A₂ A_kiar B reprezinta B₁ B_n.

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 B₁, , B_n

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

A

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 B₁, , B_n este urmatoarea: pentru orice valori atribuite variabilelor din clauza, daca B₁, , B_n 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 B₁, , B_n, adica o clauza fara antet. Fiecare B_i 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 y₁, , y_s sunt toate variabilele care apar in scopul B₁, , B_n, atunci aceasta scriere reprezinta o prescurtare a lui

y₁ y_s ( B₁ B_n)

sau intr-o forma echivalenta

y₁ , y₂ , . , y_r (B₁ B_n).

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

y₁, , y_r (B₁ B_n)

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:

B₁ B_n.

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 y₁, , y_r (B₁ B_n) 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 Dⁿ 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 Dⁿ 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 t₁', , t_n'sunt asignatele termenilor t₁, , t_nsi f' este asignata functiei n-are f, atunci elementul f'(t₁', , t_n') din D este asignata lui f(t₁, , t_n).

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(t₁,,t_n) atunci valoarea de adevar se obtine calculand valoarea lui unde este aplicatia asociata lui p de I, iar sunt asignatele, relative la I si A, corespunzatoare termenilor t₁,,t_n.

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

Fig. s1. Tablele de adevar ale celor 5 functii de baza

Acum suntem @n masura sa demonstram si echivalenta dintre formulele

x₁ x_s (A₁ A₂ A_k B₁ B_n)

si

x₁ x_s (A₁ A₂ A_k) (B₁ B_n).

Pentru usurinta calculelor vom nota A₁ A₂ A_kcu A, iar B₁ B_n cu B.

Cu aceste notatii avem:

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 = B₁ B_n. 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 F₁ F₂ F_q.

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 v_i este o variabila, iar fiecare t_i este un termen distinct de v_i si in care variabilele v_i sunt distincte doua cate doua, o numim substitutie

Fiecare v_i / t_i este numita legatura pentru variabila v_i. De obicei substitutiile se noteaza cu litere mici ale alfabetului grec. O substitutie in care toti termenii t_i sunt inchisi vom spune ca este ea insasi inchisa. Daca toti termenii t_i 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 v_i prin termenii lor corespunzatori t_i.

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 u_i/s_is pentru care u_i=s_is si orice legatura v_j/t_j pentru care v_jI Aici s_is 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 F₁ = F₂ = F_n Sau chiar mai mult, este un unificator pentru formulele F₁, , F_n 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 s_k 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 D_k a lui Ss_k

Pasul 3. Daca exista v si t, doi termeni in D_k, astfel incat v sa fie o variabila caresanuaparaint,atuncideterminams_{k+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) D₀ = f(a), y, s = y/f(a), Ss = p(f(a), g(x)), p(f(a),f(a)).

c) D₁ = 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,₀=s.

2) D₀= , k:=k+1, deci s , prin urmare Ss

3) D₁ = x, h(y), k:=k+l, deci _ = x/h(y), z/a, prin urmare S₂ = p(a, h(y),h(g(a))), p(a, h(y), h(y)).

DZ = g(a), y, k:= k+l,deci ₂ = 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 ₃.

Exemplu. Fie S = p(x, x), p(y, f(y)) Sa se verifce daca S este unifiabila.

Avem:

1 ) k =0, ₀ = s.

2) D₀ = x, y, k:= k+1, deci _ = x/y, prin urmare Ss = p(y,y), p(y,f(y))

3) D₁ = 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 = F₁ , F_n , este o multime finita de formule inchise, atunci F este o consecinta logica a lui S daca si numai daca formula F₁ , F_n 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:

P₁ ( P₂ P₃ ) = ( P₁ P₂ ) P₃ =P₁ P₂ P₃.

In general scriem: , pentru disjunctia subformulelor P_i, care prezinta proprietatea ca este adevarata daca cel putin una din subformule este adevarata.

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 Qx₁, Qx₂,, Qx_s ( ) unde P_i, este o disjunctie de literale, iar Q este un cuantificator existentialist sau universal, iar x₁, , x_r sunt toate variabilele din P.

Definitia s46. Spunem ca o formula P este in forma normala disjunctiva prenexa (FND) daca ea este de forma Qx₁, Qx₂,, Qx_r ( ), unde P₁, P₂, , P_n sunt conjunctii de literale iar Q este cuantificatorul existentialist sau universal, iar x₁, , x_n sunt toate variabilele din P.

Exemple

Formula este sub forma normala conjunctiva.

Formula este sub forma normala disjunctiva.

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:

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 Q₁ x₁ Q_nx_n prefixul formei prenex obtinuta la pasul 1 prin aplicarea algoritmului de skolemizare.

Fiecare variabila x_i precedata de un cuantificator existentialist se inlocuieste in formula cu o functie f_i, care are ca argumente variabilele x_j 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( (x, b) Q(t) (R(a, f(x, t)) T(z , f(x, t)))).

Inlaturand prefixul obtine m forma skolem:

( (x, b) Q(t) (R(a, f(x, t)) T(z , f(x, t)))).

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 si avem (1) = 0 si (0) =1. Functia de adevar se reprezinta grafic prin tabla de adevar.

Pentru conjunctie, functiade adevar este (0,0) = 0, care se reprezinta prin tabla de adevar de mai j os:

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 2ⁿ linii pentru cele 2ⁿ 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 = 2² linii.

Conform metodei inductiei matematice presupunem acum ca daca formula are k variabile propozitionale, atunci ea are 2^k evaluari posibile si deci tabla ei de adevar va avea 2^k linii.

Sa demonstram acum ca daca formula are k +1 variabile propozitionale atunci ea va avea 2^k+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 2^k 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 2^k + 2^k = 2^k+1 evaluari posibile pentru formula data.

Cu acestea am demonstrat ca daca o formula are n atomi atunci ea va avea 2ⁿevaluari. 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 functii de adevar, deoarece exista moduri de aranjare a lui 0 sau 1 in ultima coloana a unei table de adevar cu 2ⁿ linii.

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.

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:

Completam apoi coloana de sub conjunctie

si in sfarsit, sub implicatie

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:

((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 ( p₁ p₂ p_n ) 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 2ⁿ 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 , care este adevarata numai in aceasta evaluare, inrest fiind falsa. De exemplu, pentru o evaluare de forma 0 0 1 0, formula FNC, care corespunde celor 4 atomi, este

In general, pentru o evaluare data atomilor p₁, p₂,,p_n, in care citim 1 pe ultima coloana a tabelei de adevar, construim o conjunctie de atomi, punand p_i daca p_i are evaloarea V(p_i) = 1 si daca V(p_i) are valoarea 0, in evaluarea respectiva. Pentru interpretarea data, conjunctia intreaga va avea valoarea 1, iar pentru celelalte interpretari va avea valoarea 0, deoarece cel putin unul din atomii constituienti va avea valoarea 0.

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 este formula FND care raspunde cerintelor tabelei de adevar. Daca evaluarea este de forma: 0, 1, l, , 1, atunci formula FND care corespunde acestei evaluari este: si are proprietatea ca ia ca si formula, valoarea 0. Daca exista mai multe valori de 0 ale formulei date, atunci scriem pentru fiecare dintre ele cate o forma FND, ca mai sus, iar @n final facem conjunctia acestor formule. Conjunctia disjunctiilor pentru care formula este 0, va fi 0, si 1 pentru celelalte.

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 p_i, daca V(p_i) = 1 si , daca V(p_i) = 0, iar maxitermenii se formeaza scriind in dreptul fiecarei interpretari o disjunctie in care apare p_i, daca V(p_i) = 0 si daca, V(p_i) =1.

Pentru exemplifcare vom scrie clauzele conjunctive si disjunctive ce corespund unei tabele de adevar a unei formule cu trei atomi.

Formula ce corespunde acestei tabele de adevar este disjunctia minitermenilorcecorespundlui1incoloanaP,sauconjunctia maxitermenilor ce corespund lui 0 in coloana P.

Fie tabela de adevar.

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 P₁,,P_n 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 P₁ P_n 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:

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:

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

legile lui De Morgan

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= dubla negatie

7. inlocuirea disjunctiei

inlocuirea conjunctiei