Capitolul 1 Noțiuni introductive de teoria mulțimilor

Cuprins

Capitolul 1 Noțiuni introductive de teoria mulțimilor

Relații între mulțimi

Operații cu mulțimi

Paradoxurile teoriei mulțimilor

Latice și algebre Boole

Alte operații cu mulțimi

Diferența și diferența simetrică

– Funcția lui Sheffer

Capitolul 2 Relații

Definiția relațiilor

Proprietățile relațiilor

Partiția unei mulțimi

Relații de ordine

Produsul relațiilor

Aplicații

Produsul aplicațiilor

Capitolul 3 Logica propozițiilor

Principiile din logica matematică

Formarea propozițiilor

Valoarea propozițiilor

Scheme de construire a unor propoziții din alte propoziții

Construire mulțimii prpozițiilor

Ierarhizarea functorilor logici

Formule propoziționale

Scheme cu contacte

Funcția de lucru a unui dipol cu contacte

Prima problemă de analiză

Inferențe logice

Capitolul 4 Forme normale

Problema deciziei I

Forma normală conjunctivă

Forma normală disjunctivă

Algoritm de aducere a unei funcții logice la forma normală

Forme normale perfecte

Algoritm de aducere a unei funcții logice la formă normală perfectă

Problema deciziei II

Capitolul 5 Logica predicatelor

Cuantificatorii predicatului

Operații cu predicate

Formule predicative

Deductibilitate. Decidabilitate.

Bibliografie

Bibliografie

O. Becker, “Fundamentele matematicii „ , Ed. Științifică, București, 1968.

N. Both, “Elemente de logică matematică și de teoria mulțimilor”, Univ. Babeș-Bolyai, Cluj-Napoca, 1981.

N. Both, “Capitole speciale de logică matemetică”, Univ. Babeș-Bolyai, Cluj-Napoca, 1994.

G. Enescu, “Introducere în logica matematică”, ”, Ed. Științifică, București, 1965.

Al. Froda “Eroare și paradox în matematică”, Ed. Enciclopedică Română, București, 1971.

P.S. Novikov, “Elemente de logică matematică”, Ed. Științifică, București, 1966.

Gr.C. Moisil, “Elemente de logică matematică și de teoria mulțimilor”, Ed. Științifică, București, 1968.

Gr.C. Moisil, „Lecții despre logica raționamentului nuanțat”, Ed. Științifică și Enciclopedică, București, 1975.

Gr.C. Moisil, „Scheme cu comandă directă cu contacte și relee”, Editura Academiei, 1959.

F. Speranza, “Relații și structuri”, Ed. Științifică și Enciclopedică, București, 1975.

=== Capitolul 3 ===

Capitolul 3

Logica propozițiilor

Baza cunoașterii o formează noțiunile. Exemple de noțiuni sunt numărul, operațiile, obiectele.

Relațiile dintre noțiuni sunt judecățile.

Se numește propoziție o expresie verbală a unei judecăți despre care se poate spune dacă este adevărată sau falsă. Pentru a decide dacă o propoziție este adevărată ea trebuie plasată într-un univers U al discursului.

O formă propozițională este o propoziție P(x) în care apare variabila x element al universului U.

Exemple

În universul U al domnitorilor Moldovei, forma propozițională:

„x este fiul predecesorului său”

-este adevărată pentru x = Petru Rareș

-este falsă pentru x = Alexandru Lăpușneanu

2. În universul U al cărților din bibliotecă , forma propozițională:

“ x este o carte scrisă de Mircea Eliade “

-este adevărată pentru x = Istoria religiilor

-este falsă pentru x = Pseudo-Kynegheticos.

Pentru a individualiza o submulțime , este suficient să precizăm o formă propozițională P(x) în U. Acestei forme i se asociază mulțimea elementelor pentru care forma propozițională este adevărată.

3.1. Principiile din logica matematică

Principiul celor două valori. Vom considera că propozițiile pot fi doar adevărate sau false. Acest principiu se stipulează în felul următor:

Principilul terțiului exclus: O propoziție este sau adevărată, sau falsă, altă variantă nu există.

Principiul noncontradicției: O propoziție nu poate fi în același timp și adevărată și falsă.

3.2. Formarea propozițiilor

Propozițiile elementare sunt de forma : “ S este P”. Interpretarea acestei propoziții: subiectul S este numele predicativ P. De exemplu: “Casa este verde”. Aici S = „casa” iar P = “verde”.

Propozițiile elementare se leagă prin conectivele logice care se mai chemă și functori logici sau conectori logici:

Utilizând acești functori obținem propoziții compuse.

Exemplu:

Fie propozițiile p : “casa este verde” q: “ gardul este stricat”. pq este o nouă propoziție : “casa este verde și gardul este stricat”.

3.3. Valoarea unei propoziții

Valoarea unei propoziții asociază numărul 1 propozițiilor adevărate și 0 propozițiilor false.

v(p)=1 , dacă propoziția este adevărată

v(p)=0 , dacă propoziția este falsă.

3.4. Scheme de construire a unor propoziții din alte propoziții

Pornind de la propoziția p se obține propoziția care este adevărată când p este falsă. Celor două propoziții le putem atașa un tabel al valorilor de adevăr:

Tabela de adevăr pentru negație:

Dacă p și q sunt două propziții (sau două forme propoziționale de aceeiași variabilă), atunci

este o nouă propoziție, adevărată atunci când și p și q sunt adevărate

este o nouă propoziție, adevărată atunci când este adevărată cel puțin una dintre cele două propoziții.

Tabela de adevăr pentru conjuncție și disjuncție:

Obsevație.

Să considerăm P(x), o formă propozițională, și A mulțimea elementelor pentru care P(x) este adevărată. Să notăm cu B mulțimea pe care Q(x) este adevărată. Ca în figura 3.1. am reprezentat prin diagrame Venn mulțimile elementelor și valorile de adevăr ale propozițiilor. Se vede imediat că:

este adevărată pe mulțimea

este adevărată pentru

este adevărată pentru

Fig.3.1.

Implicația : este o propoziție falsă când p este adevărată și q este falsă.

Tabela de adevăr pentru implicație și echivalență

Pe de altă parte, propoziția este adevărată indiferent de valorile propozițiilor p și q, așa cum rezultă din ultima coloană a tabelului de mai jos.

3.5. Construirea mulțimii propozițiilor.

Fie o mulțime nevidă de propoziții elementare. Aplicația de valuare este o funcție surjectivă care atașază unei propoziții valoarea sa de adevăr.

Cu ajutorul functorilor se extinde la mulțimea tuturor propozițiilor P , iar funcția de valuare se extinde la .

Putem defini inductiv această extindere. Extinderea lui

(i)

(ii) dacă se dau expresiile , atunci sunt expresii .

Extinderea lui v

(iii) Mulțimea P este formată numai din elementele definite prin (i)și (ii).

Am obținut în acest mod o algebră generată de adică .

Elementele din P se numesc propoziții. sunt propoziții compuse obținute din propozițiile elementare aplicând (ii).

Din cele discutate până acum putem compune tabelul valorilor de adevăr pentru functorii descriși mai sus.

3.6. Ierarhizarea functorilor logici

Functorii logici sunt aplicați pe rând în expresii respectând următoarea ordine de prioritate: . Ordinea aplicării functorilor poate fi modificată cu ajutorul parantezelor.

Funcția de adevăr pentru expresii este, așa cum am spus, . Două expresii sunt semantic echivalente, , dacă .

Se numește tautologie o expresie universal valabilă , adică pentu care .

Exemple de tautologii.

1) este o tautologie.

Demonstrația o vom face construind un tabel al valorilor de adevăr.

Ultima coloană arata ca valoare propoziției este 1 indiferent de valorile propozițiilor elementare.

2) este o tautologie. Într-adevăr, urmărind tabelul vedem că valorile acestei propoziții sunt 1 indiferent de valorile variabilelor.

3.7. Formule propoziționale

Mulțimii propozițiilor elementare , i se adaugă mulțimea variabilelor propoziționale . Astfel, mulțimea și formulele obținute cu functorii alcătuiesc algebra , generată de F. Dacă este o formulă propozițională care depinde de variabilele , notăm formula propozițională cu .

Înlocuind variabilele cu propozițiile se obține o nouă propoziție .

O formulă se numește tautologie, sau lege logică sau formulă identic adevărată, dacă , propoziția este adevărată.

Decidem dacă este o tautologie pe baza tabelului valorilor pe care le poate lua conform cu .

Dacă este o tautologie, atunci este o absurditate.

Dacă nu este nici tautologie, nici absurditate, atunci se numește formulă realizabilă.

Dacă este o tautologie, atunci valoarea sa de adevăr depinde numai de , nu și de .

Exemple de tautologii.

Ca exercițiu, să demonstrăm tautologia . Construim în acest scop tabelul valorilor de adevăr

Demonstrația tautologiei decurge în felul următor

Demonstrația principiului terțiului exclus și respectiv :

Alte tautologii

Exercițiu.

Să se demonstreze tautologia

Rezolvare.

3.8. Scheme cu contacte

Utilizarea logicii matematice în analiza și sinteza circuitelor electrice și electronice datează din primii ani ai proiectării mecanismelor automate și apoi a calculatoarelor. Gr.C.Moisil s-a preocupat de teoria algebrică a mecanismelor automate, publicând în 1959 un curs asupra acestor probleme.

Intr-o schemă distingem elementele de comandă (contacte normal deschise sau normal închise) , elementele intermediare și elementele de execuție (becuri, dispozitive de semnalizare etc).

Vom nota în continuare cu litere mici a,b,…,z, contactele normal închise și cu contactele normal deschise.

Fig. 3.2. Contacte normal închise și normal deschise

Dipoli cu contacte

Circuitul deschis, respectiv circuitul închs formează un dipol cu contacte

Contactele normal închise și normal deschise sunt dipoli cu contacte

c) Dacă sunt dipoli , atunci dipolii obținuți prin montarea în serie sau paralel a dipolilor , sunt dipoli cu contacte

Formulele de structură a unei scheme .

a,b,…,z, contactele normal închise

contactele normal deschise

X,…,Z relee

U,…W lămpi

simbol pentru montarea în serie

simbol pentru montare în paralel

Pentru schema de mai jos

Fig. 3.3.

formula de structură este

3.9. Funcția de lucru a unui dipol cu contacte.

Se consideră o variabilă k indicând starea de funcționare a unui dipol. Dacă k = 1, dipolul conduce, dacă k = 0, dipolul nu conduce.

Conductibilitatea dipolului din figura de mai jos

Fig. 3.4.

Poate fi stabilită utlizând tabelul următor:

Conductibilitatea dipolului din figura 3.5

Fig. 3.5.

Poate fi stabilită din tabelul

Pentru dipolul din figua 3.6

Fig. 3.6.

Formula de structură este

Funcția de lucru a dipolului este dată în tabelul următor

3.10. Prima problemă de analiză

Prima problemă de analiză cere să se determine valoarea funcției de lucru a unui dipol.

Exemplu. Se dă dipolul de mai jos:

Fig. 3.7.

Se pune problema de a stabilii dacă pentru a = b = 1, c = d = 0 dipolul conduce ?

Formula de structură a dipolului este

Funcția de lucru primește pentru a = b = 1, c = d = 0 valoarea

, deci dipolul conduce.

Probleme

Să se scrie formulele de structură pentru schemele de mai jos.

Problema 1. Problema 2. Problema 3.

Problema 4 Problema 5

Soluția problemei 1:

Soluția problemei 2:

Soluția problemei 3:

Soluția problemei 4:

Soluția problemei 5:

3.11. Inferețe logice

Inferența logică este o metodă de a obține noi propoziții adevărate din propoziții despre care s-a stabilit deja că sunt adevărate.

Orice tautologie conduce la o regulă de inferență.

Condițiile de aplicare a unei reguli precizează premisele inferenței și apoi concluzia. Se utilizează notația

Dacă S este un sistem de reguli de inferență se introduce relația

“A poate fi dedus din S”, notată .

Exemple

1)

Inferența corespunzătoare este următoarea:

Explicând cu cuvinte notația de mai sus înseammnă: dacă H poate fi dedus din S și poate fi dedus din S, atunci G poate fi dedus din S.

2)

Această tautologie se poate scrie ca un lanț de inferențe

Citim astfel premisele: , implicația poate fi dedusă din S și la rândul ei, implicația poate fi dedusă din S .

Concluzia este că implicația

poate fi dedusă din S.

Tautologia poate fi scrisă ca regula contrapoziției:

Tautologia poate fi scrisă ca principiul contradicției în felul următor

=== capitolul1 ===

Capitolul 1

Noțiuni introductive de teoria mulțimilor

Noțiunea de mulțime este considerată primară și ea este explicată pe baza exemplelor.

Să dăm câteva exemple de mulțimi.

Mulțimea numerelor naturale: .

Mulțimea numerelor pare : .

Mulțimea numerelor impare: .

Mulțimea numerelor întregi: .

Mulțimea numerelor iraționale I, conține fracțiile zecimale neperiodice , de exemplu.

Alfabetul grecesc , .

Mulțimea punctelor din plan, egal depărtate de un punct fixat din același plan, cercul .

Mulțimea vidă, notată prin . Ca exemplu, mulțimea punctelor de intersecție a două drepte paralele situate în același plan este o mulțime vidă.

Vom utiliza notația cunoscută , pentru elementele ce aparțin mulțimii X, și pentru elementele ce nu aparțin lui X.

Dacă notăm cu p(x) o proprietate a elementului x, mulțimea punctelor care au respectiva proprietate se notează cu .

Dacă rezultă că p(x) este adevărată.

Dacă rezultă că p(x) este falsă.

1.1. Relații între mulțimi

Relația de incluziune notată , însemnă că oricare ar fi , atunci și .

Relația de incluzine strictă însemnă că X este o parte proprie a lui Y.

Relația de egalitate se definește astfel, dacă și în același timp , atunci .

Exemplu:

Dacă, atunci oricare ar fi , rezultă că , ca urmare .

Putem reprezenta cele două mulțimi prin diagrame Euler-Venn.

Fig.1.1.

Proprietățile relației de incluziune:

Reflexivitatea

Tranzitivitatea și implică

Antisimetria și implică

Mulțimea părților mulțimii X se notează cu .

Exemplu: Fie. Mulțimea părților lui A este

1.2. Operții cu mulțimi

Reuniunea

Intersecția

Complementarea

Mulțimi disjuncte

Diferența a două mulțimi

Dacă notăm cu I muțimea universală, atunci

Am utilizat în cele de mai sus simbolurile pentru operații logice.

Simbolul pentru operatorul “și”, simbolul pentru “sau”, iar pentru „implicație”, simbolul .

Vom utiliya de asemenea simbolurile numite cuantificatori:

cuantificatorul universal, notat având semnificația “oricare ar fi”

cuantificatorul existențial, notat cu semnificația “există”.

De exemnplu, propoziția: “ Oricare a r fi x, există y astfel încât y=2x”, se scrie astfel .

Proprietățile mulțimii părților unei mulțimi

Dacă

Dacă

1.3. Paradoxurile teoriei mulțimilor

Să considerăm o mulțime care nu se conține pe sine ca element. De exemplu, dacă .

Fie acum C, mulțimea tuturor mulțimilior care nu se conțin ca element

.

Mulțimea C astfel definită prezintă următoarele situații:

Pe de o parte, dacă înseamnă că C are proprietatea elementeleor sale și deci .

Pe de altă parte, dacă , atunci nu se conține ca element adică .

În ambele situații ajungem la o contradicție.

După modelul acestui exemplu se pot da și alte mulțimi paradoxale . Acest lucru a pus în evidență o slăbiciune a teoriei mulțimilor, așa cum a fost ea dezvoltată de G.Cantor. Pentru a remedia această situație, a fost dezvoltată teoria claselor de către K.Godel și P.Bernays.

O clasă M este mulțime dacă există o altă clasă C astfel încât .

1.4. Latice și algebre Boole

O mulțime înzestrată cu operațiile se numește latice dacă sunt satisfăcute următoarele proprietăți:

1. Comutativitatea

2. Asociativitatea

3. Absorbția

Să notăm laticea ca pe o structură algebrică cu două olerații:.

O latice se numește distributivă dacă sunt îndeplinite proprietățile:

4. Distributivitatea

5. Idempotența

6. Există elementele și I astfel ca

Elementele și I sunt cel mai mic, repectiv cel mai mare element al laticei.

Se numește algebră booleană o latice distributivă , cu prim și ultim element, în care se definește complementul cu proprietățile .

Mulțimea părților , cu două operații binare , o operație unară -, complemetarea , având elementele și I se numește algebră booleană. Notăm cu algebra booleană.

În orice algebră booleană au loc legile lui de Morgan

7.

8. Legea dublei negații .

Pentru familii de mulțimi , se definesc și .

Dacă , o familie oarecare de indici, eventual infinită, se definesc reuniune și intersecția unui număr oarecare, eventual infinit de mulțimi: și .

Vom demonstra câteva proprietăți ale mulțimii părților.

Proprietatea 1. 1. Dacă

Demonstrație

Intr-adevăr, fie . Cum , ca urmare . Deci .

Invers, dacă , și, ca urmare . Deci .

Proprietatea 1.2. Dacă .

Demonstrație.

Din rezultă că .Ca urmare,

Dacă , , ca urmare , deci . În concluzie . c.c.t.d.

Proprietatea 1. 3. .

Demostrație.

Din . Dacă , adică .

Invers, , atunci . Ca urmare, .

Proprietatea 1. 4. Dacă .

Într-adevăr, . Să considetăm , atunci , deci .

1.5. Alte operații cu mulțimi.

Diferența a două mulțimi.

Am definit , sau echivalent, .

Fig. 1.2.

Proprietățile diferenței mulțimilor.

Fig.1.3.

Fig. 1..4.

Se poate demonstra că .

Demonstrație.

Arătăm că . Fie . Atunci . Ca urmare, .

Arătăm că . Fie , rezultă că , adică .

Diferența simetrică

Diferența simetrică notată cu se definește prin relația .

Fig. 1.5.

Proprietățile diferenței simetrice.

Funcția lui Sheffer

Funcția lui Sheffer se definește ca operația “nici…nici”, x nu aparține nici lui A nici lui B, se notează cu . Acest lucru înseamnă:. Iată câteva proprietăți.

.

Fig.1.6.

=== Capitolul2 ===

Capitolul 2

Relații

2.1 Definiția relațiilor

Fie X și Y două mulțimi. Definim produsul cartezian ca mulțimea perechilor:

.

O relație binară este o submulțime a produsului cartezian .

Exemplul 2.1.

Dacă și , să fie respectiv, mulțimea studenților și mulțimea angajatorilor prezenți la un târg de forță de muncă . Perechile de forma reprezintă mulțimea tuturor perechilor student, angajator ce pot negocia. Fie formată doar din acele perechi, student angajator , în care studentul a primit o ofertă fermă. O relație ar putea descrie faptul că un același student a găsit două oferte. Ofertanții din relația K nu pot angaja ambii același student.

Exemplul 2.2.

Fie mulțimea numerelor naturale. Produsul cartezian este mulțimea

Fie R relația care asociază unui număr natural, patratul său, atunci .

O relație se mai notează și cu xRy sau .

Dacă , atunci relația se numește relație totală.

Dacă , relația este vidă.

Se numește domeniul unei relații mulțimea

.

Se numește codomeniul relației, mulțimea

.

Relația definită prin mulțimea

Exemplul 2.3. Pe mulțimea perechilor de numere reale relația “x este mai mic decât y ”, este o relație totală

Exemplul 2.4. Apartenența unui element la o mulțime este tot o relație .

Exemplul 2.5. Relația de incluziune între submulțimile unei mulțimi este o relație în produsul cartezian al părților .

Graful atașat unei relații are drept noduri elementele din cele două mulțimi iar arcul (x,y) apare în graful relației dacă . Dacă în primul exemplu avem studenții și angajatorii , graful din figura 2.1 ilustrează ofertele primate de cei doi studenți.

Fig.2.1.

Produsul cartezian a n mulțimi are ca elemente n-uplurile ordonate .

Se numește relație n-ară pe mulțimea , o submulțime a produsului cartezian

Exemplul 2.6. În mulțimea punctelor din plan se consideră submulțimea formată din vârfurile unui poligon regulat cu k laturi care definește relația corespunzătoare.

2.2. Proprietățile relațiilor

O relație este reflexivă dacă . Acest lucru se mai scrie și . În graful asocuiat relației există câte o buclă în fiecare vârf.

Fig.2.2. Relație reflexivă

O relație este simetrică dacă pentru , . Sau altfel spus,. În graful relației, dacă între două noduri există un arc, atunci arcul este dublu.

Fig.2.3. Relație simetrică

O relație este antisimetrică dacă din .

3. O relație este tranzitivă dacă , din .

Adică din .

Graful unei relații transitive este ca cel din figura de mai jos.

Fig.2.4. Relație tranzitivă

Se numește relație de echivalență o relație reflexivă, simetrică și tranzitivă.

Exemplul 2.7. Fie relația de egalitate a numerelor raționale positive de forma .

În raport cu relația de echivalență dată de egalitatea fracțiilor, mulțimea se împarte în clase de echivalență. Într-o clasă de echivalență se află fracțiile care au aceeași valoare. Obținem. următoarele clase:

Mulțimea formată cu clasele de numere echivalente este o mulțime cât notată .

Clasă de echivalență pentru o relație și un element fixat x este mulțimea .

Se numește mulțime cât, mulțimea claselor de echivalență în raport cu o relație de echivalență.

2.3. Partiția unei mulțimi

Se numește partiție a unei mulțimi X o familie de mulțimi , cu următoarele proprietăți:

Teorema 2.1. Fiind dată o relație de echvalență în X, ,clsele de echivalență constitue o partiție a lui X.

Invers, fiind dată o partiție a lui X, relația R definită de xRy dacă (x,y) aparțin la aceesși submulțime a partiției este o relație de echivalență.

Demonstrație

Fie , două elemente presupuse neechivalente. Ca urmare și , iar . (Altfel ar exista și deci ceea c ear însemna că xRy)

Cum relația de echivalență este definită în X, rezultă că .

Invers, fie X și o partiție a sa. Definim o relație în felul următor:

, dar în acest caz relația este reflexivă și simetrică.

Pe de altă parte, dacă , dacă , atunci acest lucru ar însemnă că și deci că nu este partiție . Rezultă că dacă și , atunci și deci , adică tranzitivitatea relației.

Relația de echivalență R este de indice finit dacă există un număr finit de clase de echivalență. Cu alte cuvinte, mulțimea cât are un număr finit de elemente.

Evient, egaliatea numerelor raționale potizive este de indice infinit.

Exemplul 2.8. Un exemplu de relație de echivalență este congruența. Mulțimea numerelor naturale se împarte în clasa numerelor pare și clasa numerelor impare .

1)

2)

Am împărțit mulțimea numerelor naturale în clase de echivalență modulo 2 :

Să obsevăm că , x împărțit cu 2 dă restul 0, iar faptul că înseamnă că x împărțit cu 2 dă restul 1.

Două numere sunt congruente față de modulul 2 dacă diferența lor este un multiplu de 2.

Relația de congruență este o relație de echivalență. Mulțimea este o mulțime cât în raport cu relația de congruență modulo 2.

Fie două partiții ale aceleiași mulțimi X . este mai puțin fină decât dacă orice submulțime din este conținută în cel puțin una dintre submulțimile lui .

Relația de ordine dintre partiții duce la o relație de ordine între relațiile de echivalență definite pe X.

înseamnă că dacă , atunci și .

2.4. Relații de ordine

O relație , reflexivă, tranzitivă și antisimetrică se numește relație de ordine

O mulțime X dotată cu o relație de ordine se numește mulțime ordonată. Dacă relația este totală, ordonare este totală.

Un exemplu de mulțime total ordonată: mulțimea numerelor naturale cu relația .

Observație. O relație de ordine strictă, de exemplu relația < , este antireflexivă.

2.5. Produsul relațiilor

Fie două relații R și S, și . Relația produs se definește astfel:

dacă există cel puțin un astfel ca .

Operația este necomutativă.

Puterile unei relații pe o mulțime. Dacă definim puterile relației prin:

, cu notăm relația identică

R este simetrică dacă

R este antisimetrică dacă

R este tranzitivă dacă .

Exemplu. Dacă , să considerăm relația

Fig.2.5.

Vom avea atunci, conform definiției puterii unei relații

.

2.6. Aplicații

Se numește aplicație a lui X în Y o relație între X și Y care asociază ficărui element din X un singur element din Y

Aplicația se numește surjecție dacă oricare ar fi există cel puțin un și y este imaginea lui x.

Exemplul 2.9. Fie R o relație de echivalență în I. Aplicația , care asociază clasa lui x este surjectivă.

Aplicația se numește injecție dacă oricare ar fi există cel mult un astfel ca .

Aplicația injectivă și surjectivă se numește bijectivă.

Exemplul 2.10. În mulțimea X relația “egal cu “ = este o bijecție care se numește aplicația identică.

Obsevație Se dă o aplicație și se definește următoarea relație:

. Relația este o echivalență. Într-adevăr,

deci

Din deci

Din deci .

Dacă funcția f este o injecție, relația este egaliatea

Echivalența se numește nucleul lui f și se notează cu ker f.

2.7. Produsul aplicațiilor

Definim produsul aplicațiilor ca produs de relații.

Teorema 2.2. Produsul a două aplicații este o aplicație.

Într-adevăr, fie , atunci , iar prin g lui y i se asociază astfel încât .

În general, .

Teorema 2.3. Produsul a două surjecții este o surjecție, produsul a două injecții este o injecție și produsul a dauă bijecții este o bijecție.

Diagrame

Pentru aplicațiile putem adopta următoarea reprezentare, prin diagrama de mai jos:

Fig.2.6.

Spunem că diagrama este comutativă dacă și numai dacă .

Teorema 2.4. Oricare ar fi aplicația , există o aplicație surjectivă , o aplicație bijectivă și o aplicație injectivă astfel încât diagrama

Fig.2.7.

este comutativă.

Demonstrație

Dacă , unde cu am notat clasa de echivalență căreia îi aparține x în raport cu ker f. Definim .

Stiind că pentru , (din definiția lui ker f ), avem , ceea ce arată că diagrama este comutativă.

Teorema 2.5. Fie două relații de echivalență pe A astfel încât . Există o aplicație unică , între clasele de echivalență , care face comutativă diagrama:

Fig.2.8.

Unde , pentru .

Demonstrație Clasele care îl conțin pe sunt respective .

Definim o aplicație bine definită deoarece și deci , adică și dacă se alege un alt reprezentant al clasei, imaginea prin f rămâne aceeași.

=== Capitolul4 ===

Capitolul 4

Formele normale

4.1. Problema deciziei I

Fiind dată o funcție logică , să se stabilească dacă ea este

o tautologie

o contradicție

o propoziție realizabilă (există cel puțin o alegere a valorilor variabilelor pentru care este adevărată).

Pentru rezolvarea acestei probleme am utilizat așa numita metodă a tabelelor de valori. Dacă, însă, numărul variabilelor este mare, metoda de rezolvare presupune folosire formelor normale a funcțiilor logice.

Se numește formă normală a unei funcții logice o expresie care satisface următoarele condiții

conține numai functorii

negația apare numai peste propoziții elementere

4.2. Forma normală conjunctivă

Intr-o formă normală conjunctivă functorul principal, care leagă factorii aflați în paranteze este .

Însemnă că funcția logică este o conjuncție a disjuncțiilor.

Exemplu

. Uneori această formă poate fi scrisă ca

Să observăm că dacă într-o formă normală conjunctivă apare un termen , el poate fi simplificat deoarece .

Dacă într-o formă normală conjunctivă , unul dintre factori este fals, atunci expresia este o contradicție.

Dacă într-o formă normală conjunctivă toți factorii sunt adevărați, atunci este o tautologie.

4.3. Forma normală disjunctivă

Intr-o formă normală disjunctivă functorul principal, care leagă factorii aflați în paranteze este .

Exemplu

care mai poate fi scrisă ca

Să observăm că dacă într-o formă normală disjunctivă apare un membru , el poate fi redus deoarece .

4.4. Algoritm de aducere a unei funcții logice la forma normală

In formele normale apar numai functorii . Pentru a transforma funcția logică , astfel încât să conțină numai functorii , pot fi utilizate următoarele expresii echivalente:

Algoritmul de aducere a unei funcții logice la forma normală are următorii pași:

Se elimină functorii, alții decât

Se coboară negația pe variabile

Se aplică legile de distributivitate și asociativitate pentru a avea ca functor principal, functorul dorit.

Exemple de expresii normalizate :

Exemplul 1.

, expresia din dreapta este în formă normală disjunctivă

Exemplul 2.

, expresia din dreapta este în formă normală conjunctivă

Exemplul 3.

Expresie adusă la forma normală disjunctivă.

Exemplul 4.

Ultima expresie este în forma normală disjunctivă

Exemplul 5.

Forma normală conjunctivă obținută ne permite să susținem că expresia este o contredicție.

4.5. Probleme de decizie

Așa cum am spus, aducerea la forma normală permite stabilirea valorii de adevăr a funcțiilor logice.

Exemplu. Să se arate că formula este o contradicție.

Demonstrație.

Aducem pe X la forma normală disjunctivă.

Având valoarea 0 pentru orice alegere a variabilelor, formula este o contradicție.

Observație. Dacă se cere echivalența a două formule X și Y, se demonstrează că formula este o tautologie.

4.6. Forme normale perfecte

Să începem prin a preciza câteva noțiuni necesare în cele ce urmează. Mai întâi să observăm că dacă într-o expresie sunt suprimați functorii principali, ceea ce rămîne se vor numi membrii expresiei.

Exemplu. Dacă se dă expresia , membrii expresiei sunt.

Numim temeni primi variabilele și negațiile lor.

De exemplu în expresia termenii primi sunt .

Se numește formă normală perfectă o formă normală care respectă următoarele restricții:

Fiecare membru conține toate literele

Nici un termen prim nu apare mai mult decât o dată într-un membru.

Nici un membru nu apare mai mult decât o dată.

Nici o literă nu poate intra într-un membru împreună cu negația sa.

Exemplu de formă normală conjunctivă perfectă

.

Exemplu de formă normală disjunctivă perfectă

.

4.7. Algoritm de aducere a unei expresii la o formă normală perfectă

Se aduce expresia la o formă normală conjunctivă sau disjunctivă

Se adaugă literele care lipsesc

pentru formele normale disjunctive se adaugă , expresie cu valoarea 0 și deoarece , după cum știm, , termenul nu va schimba valoarea expresiei.

pentru formele normale conjunctive se adaugă , expresie cu valoarea 1.

Deoarece

Se reduc termenii care se repetă, deoarece

În continuare vom nota conjucția prin alăturarea literelor.

Exemple.

1.Să se aducă la forma normală disjunctivă perfectă expresia .

Adăugăm membrii și se obține:

Forma obținută este o formă normală disjunctivă perfectă.

2. Să se aducă la forma normală disjunctivă perfectă expresia

Forma este normală disjunctivă perfectă.

3. Să se aducă la forma normală conjunctivă perfectă expresia

. Adăugând , care nu schimbă valoarea expresiei, obținem:

Aceasta este forma este normală conjunctivă perfectă.

4.8. Problema deciziei II

A doua problemă de decizie poate fi formulată în felul următor:

Să se construiască o formulă propozițională cu n variabile care să fie adevărată pentru anumite valori prescrise ale variabilelor.

Metodă de rezolvare.

– variabila se asociază cu valorile 1

– variabila se asociază cu valorile 0

– membrii se leagă prin conjuncții

– se face disjuncția conjuncțiilor

Exemplu. Să se construiască o expresie astfel încât

, iar restul să fie 0.

Construim expresia, punând în locul valorilor 1 o variabilă, iar în locul valorilor 0, negția variabilei.

Aceasta este o formă normală disjunctivă perfectă. Urmărim acum simplificarea formei, scoțând factorii comuni pe baza distributivității operațiilor și eliminînd apoi membrii inutili.

Se vede imediat că acestă problemă își găsește aplicare în siteza și simplificarea schemelor cu contacte. Iată mai jos rezolvarea unei astfel de probleme.

Să se găsească expresia pentru care valorile sunt date mai jos.

Să se scrie forma normală disjunctivă perfectă, să se simplifice și să se reprezinte schema care realizează funcționarea dorită.

Rezolvare.

Urmărind valorile variabilelor pentru care funcția este 1 pute scrie următoarea funcție

Aceasta este o formă normală disjunctivă.

Pentru a o simplifica procedăm astfel:

Putem deci reprezenta schema a cărei funcționare esre dată de funcția .

Schema este cea din figura de mai jos

Fig. 4.1. Sinteza dipolului

=== Capitolul5 ===

Capitolul 5

Logica predicatelor

Să începem cu un exemnplu:

Propoziția

“x este un număr par”

are ca subiect ceva neprecizat. O putem considera ca P(x), o propoziție deschisă.

Dacă notăm cu o mulțime universală și considerăm o submulțime ,

atunci, după cum se știe, ea poate fi definită cu ajutorul unei proprietăți .

In acest fel, propoziția “x este un număr par” poate fi descrisă ca .O astfel de descriere se numește predicat.

Un predicat este o afirmație relativă la una sau mai multe variabile care pentru valori particulare date variabilelor poate lua valoarea “adevărat” sau “fals”.

În calculul propozițiilor s-au utilizat

-propoziții constante, date

-variabile propoziționale în formule propoziționale.

Predicatul este o funcție propozițională. Calculul predicatelor este o extensie a calculului propozițiilor.

Predicatele care depind de o singură variabilă se numesc predicate unare, mulțimea lor se notează cu . Predicatele care depind de două variabile sunt predicate binare. Mulțimea predicatelor binare este notată cu , predicatele cu n variabile , sunt predicate n-are, din mulțimea .

Dacă P(x) este un predicat și x = a, atunci P(a) este propoziția obținută după înlocuirea variabilei cu o valoare particulară.

Pentru a defini un predicat trebuie precizată mulțimea elementelor în care variabilele iau valori, adică mulțimea de referință, universul discursului .

Mulțimea elementelor din pentru care P(x) este adevărată se numește domeniul predicatului .

Exemple.

Predicatul

Este un predicat unar cu domeniul {-5,-4,…,4,5}.

Fie mulțimea membrilor familiei descrise de arborele din figura 5.1.

Fig.5.1. Arborele familiei

Predicatul

“x este fratele lui y”

Este un predicat binar cu domeniul :

{(Ion, Pertu), {Petru, Ion), (Vlad,Dinu),(Dinu,Vlad)}.

Să facem următoarea obsevație: un predicat multiplu este o relație.

Exemplu.

Fie = {țarile lumii, orașele lumii} și predicatul

“y este cel mai mare oraș din x”

P(x,y) are ca elemente ale domeniului x – “țara”, y – “cel mai mare oraș al țării”

Pentru perechile

x = Austria y = Viena

x = SUA y = New York , propozițiile obținute au valoarea adevărat.

Așa cum am arătat deja, un predicat este o funcție definită pe cu codomeniul mulțimea propozițiilor obținute prin particularizarea variabilelor.

De exemplu, dacă = {-2,-1,0,1,2}, iar , atunci valorile propozițiilor se pot pune într-un tabel, ca mai jos

Domeniul predicatului este mulțimea {-1,0,1}.

5.1. Cuantificatorii predicatului.

Cuantificarea universală

Să luăm predicatul “ x are proprietatea P(x) ”. Unui asemenea predicat i se poate asocia predicatul “ oricare ar fi x are proprietatea P(x) ”, sau

“ toți x au proprietatea P(x) ”. O astfel de asociere se numește cuantificare. Pentru predicatul “ oricare ar fi x are proprietatea P(x) ” utilizăm notația

,

unde semnul este cuantificatorul universal, iar x este variabila legată.

Propoziția este adevărată dacă pentru toți , P(x) sunt adevărate

Predicatul este fals dacă există un pentru care să fie fals.

Pentru un predicat multiplu scriem

,

unde x,y sunt variabile legate.

Cuantificarea existențială

Dacă două mulțimi sunt în relația , atunci predicatului

“dacă ”

i se asociază propoziția “Există cel puțin un x cu propriatetea ”.

Asocierea se numește cuantificare existențială. Cuantificatorul existențial se notează cu . Cuatificarea existențială se notează cu , aici variabila x se numește variabilă legată.

Propoziția existențială este adevărată dacă și numai dacă există cel puțin un element în mulțumea de referință a predicatului pentru care proprietatea este adevărată și este falsă dacă nici un element din mulțimea de referință nu are proprietatea P.

Pentru predicate binare putem scrie propoziția .

Din cele spuse până aici putem constata că unui predicat P(x) i se asociază

a) propoziții particulare P(a), P(b)

O propoziție universală

O propoziție existențială

Unui predicat binar P(x,y) i se asociază

1) propoziții particulare P(a,b), P(c,d)

2) Propoziții particuare universalizate și

3) Propoziții particuare existențiale și

4) O propoziție universală

5) O propoziție existețială

6) Două propoziții existențiale universalizate : “Oricare ar fi x, există cel puițin un y astfel încât P(x,y)”. Aceată propoziție este diferită de care însemnă “Oricare ar fi y există cel puțin un x…”

7) Două propoziții universale existențializate: Prima înseamnă

“Există cel puțin un x, astfel încât oricare ar fi y , P(x,y)”, diferită de care înseamnă “ există cel puțin un y, astfel încât oricare ar fi x, P(x,y) ”.

5.2. Operații cu predicate

Să considerăm două predicate: P(x) cu domeniul și Q(x) cu domeniul .

Dacă P(x) și Q(x) sunt două predicate lor le pute asocia propozițiile:

b) Propoziții universale:

c) Propoziții existențiale :

În concluzie, dacă este o mulțime de propoziții, aplicația le asociază valorile de adevăr. Dacă M este o mulțime de variabile, se numește predicat cu n variabile peste M aplicația . Acest lucru înseamnă că un predicat multivalent P asociază sistemului ordonat de variabile o propoziție

Mulțimea de adevăr a predicatului este

Predicatul este adevărat dacă și fals dacă .

În particular, dacă avem un predicat cu o singură variabilă și-i asociem propoziția , valorile sale vor fi

Negarea propozițiilor cuantificate.

Dacă un predicat este adevărat pentru orice mulțime de variabile, se numește identic adevărat.

5.4. Formule predicative

O definiție inductivă a formulelor predicative:

Orice predicat este o formulă predecativă

Dacă sunt formule predicative, atunci

, sunt formule predicative.

Dacă este o formulă predicativă atunci sunt formule predicative.

Nu există alte formule predicative.

Să obsevăm că dacă un cuantor este în domeniul de acțiune al altui cuantor, atunci variabilele legate trebuie să difere.

Iată câteva formule identic adevărate:

5.5. Deductibilitate. Decidabilitate.

Fie formule predicative. Dacă se spune că este deductibilă semantic din . Aici sunt premisele ,iar este concluzia. Deductibilitatea se notează prin .

Problema decidabilității în logica predicatelor poate fi formulată astfel: există un procedeu finit de a decide dacă o formulă este adevărată sau nu ?

Pentru formulele cu o singură variabilă, problema este decidabilă.

În 1936 Church a demonstrat că nu există un procedeu finit de decizie pentru orice formulă predicativă.