ALGORITMUL TRANSFORMARII FORMULELOR IN FORME NORMALE [615605]

1
ALGORITMUL TRANSFORMARII FORMULELOR IN FORME NORMALE
FOAIA DE TITLU

2
CUPRINS

INTRODUCERE ………………………….. ………………………….. ………………………….. ………………………….. 3
CAPITOLUL I. FO RME NORMALE ȘI CONSECINȚE LOGICE ………………………….. ………… 4
1.1. Noțiuni generale privind formele normale. Clasificări. ………………………….. ……………………….. 4
1.1.1. Forma normală booleană, ………………………….. ………………………….. ………………………….. ….. 5
1.1.2. Forma normală de negație, ………………………….. ………………………….. ………………………….. 12
1.1.3. Forma normală conjunctiva ………………………….. ………………………….. …………………………. 15
1.1.4. Forma normală prenex, ………………………….. ………………………….. ………………………….. ….. 16
1.1.5. Forma normală skolem. ………………………….. ………………………….. ………………………….. ….. 16
1.2. Forme normale (2NF, 3NF, BCNF) ………………………….. ………………………….. ……………………. 17
СAPITOLUL II. LOGICĂ PROPOZIȚIONALĂ ȘI FORMELE NORMALE …………………… 21
2.1. Logica propozițională și formele normale ………………………….. ………………………….. …………… 21
2.2. Forme normale pentru logica predicatului de primul nivel ………………………….. ………………… 26
2.3. Transformarea în formă normală conjunctiva ………………………….. ………………………….. ………. 32
III. IMPL EMENTAREA ALGORITMULUI TRANSFORMARII FORMULELOR IN
FORME NORMALE. APLICAȚIE ………………………….. ………………………….. …………………………. 37
3.1. Metode de tranformare a ecuațiilor generale în forma normal ………………………….. ……………. 37
3.2. Tipologia algoritmilor pentru transformarea formulelor în forme normale ………………………. 40
3.3. Exemple de aplicații ………………………….. ………………………….. ………………………….. …………….. 54
CONCLUZ IE ………………………….. ………………………….. ………………………….. ………………………….. …. 65
BIBLIOGRAFIE ………………………….. ………………………….. ………………………….. ………………………… 67

3
INTRODUCERE

Actualitatea temei. Aceeași stare de fapt poate fi exprimată în moduri diferite. Deci există
diferite moduri de a fo rmula același lucru. Cu alte cuvinte, lucrurile pot fi spuse în orice fel. Aceasta
înseamnă că afirmațiile pot fi întoarse și întoarse fără a le schimba. În special, nu este adevărat că
există un singur mod de a spune ceva. Aceasta înseamnă că există difer ite moduri de a spune același
lucru. Exprima t diferit, există o ofertă nesfârșită de formulări diferite pentru o singură gândire. ..
Fără capacitatea de a exprima lucrurile în moduri diferite, literatura ar fi cu adevărat blandă și
plictisitoare. Limbajul trăiește din faptul că te joci cu el, că stabilești accente cu fraze și formulări
inteligente, care inspiră viața în lucruri. Însă, c eea ce este bun pentru poezie nu trebuie neapărat să fie
benefic pentru informatică și logică.
În cazul formulelor logice, este foarte adesea să ne întrebăm dacă nu pu tem găsi o formulare
mai simplă pentru o formulă dată. Un exemplu clasic este dubla negație, pe care pu tem să o omi tem
pur și simplu: în loc de „Nu este cazul să nu fie cazul în care se aplică”, de asemenea, este mai ușor
să spui „se aplică”. Scris matematic: ¬¬a ≡ a. Dar există și cazuri mai complexe care nu sunt atât de
evidente: „Nu este cazul ca a și b nu se aplică” pot fi scrise și ca „a sau b”, matematic ¬ (¬a ∧ ¬b) ≡
a∨b.
Din aceste motive, formulele sunt limitate în anumite contexte în ceea ce privește natura lor
sintactică. De exemplu, l uăm în considerare formulele în formă normală conjunctivă da că, pe de o
parte, dor im să contin uăm modelarea bine, dar, în același timp, sun tem interesat și de teste de
satisfacție care sunt puternic bazate pe sintaxa formulei, cum este cazul, de exemplu, în algoritmul
DPLL. Un alt exemplu sunt formulele în forma n ormală Skolem, pentru care modelele sunt ușor de
construit (dacă pot fi îndeplinite).
Scopul lucrării este de a define algoritmii transformării formulelor în formule normale din
perspectiva logicii propoziționale.
Din acest punct de vedere s -au stabilit un șir de obiective:
1. Să se definească noțiunile generale privind formele normale și clasificarea acestora.
2. Să se definească formele normale 2NF, 3NF și BCNF
3. Să se arate transformările în forme normale în loigica propozițională
4. Să se implementeze practice alg oritmi de transformare a formulelor în forme normale
Metoda de cercetare. Metodele de cercetare utilizate se referă la analiza materialului teoretic
(în limba română, engleză și germană), structurarea logică a informațiilor (analiza sistemică).

4
CAPITOLUL I. FORME NORMALE ȘI CONSECINȚE LOGICE

1.1. Noțiuni generale privind formele normale. Clasificări.

O formă normală (formă canonică ) este o reprezentare matematică cu anumite proprietăți care
sunt predeterminate de tipul formei normale. Dacă este definită o fo rmă normală, aceasta poate fi
obținută din orice reprezentare folosind o relație de echivalență. Dacă mai multe reprezentări duc la
aceeași formă normală, ele sunt echivalente în ceea ce privește tipul de formă normală și, prin urmare,
pot fi comparate și clasificate. Multe forme normale sunt unice, deci există o singură formă normală
pentru fiecare reprezentare.
Formal, o formă normală este un ultim element dintr -un lanț al unei relații bine stabilite . Relația
este definită de transformările permise. Solid itatea relațiilor rezultă din finețea numărului de
manipulări.
Formele normale importante sunt:
1. În matematică, o reprezentare a unui obiect care are anumite proprietăți pre definite și care poate
fi determinată în mod unic pentru toate obiectele de acest ti p. În special:
o Forma normală hessian a unui avion
o Forma normală de pas a unui sistem liniar de ecuații ( metoda de eliminare gaussiană )
o Forma normală jordanian o matrice pătrată
o Forma normală frobenius , de asemenea, forma rațională normală a unei matrice pă tratică
o Forma normală smith a unei matrice cu intrările dintr – un inel principal ideală
o Forma normală a unei matrici ortogonale,
o Forma normală a unei funcții liniare
o Forma normală a unei ecuații pătratice
o Forma normală a unui cvadru ,
o fracție complet trunchiată pentru un număr rațional
2. În teoria jocului o formă de reprezentare a unui joc, vezi forma normală a unui joc
3. În informatică teoretică o simplă f ormă de gramatică fără context ( ierarhia lui chomsky ). În
special :
o Forma normală chomsky
o Forma normală greibach
o Forma normală gentzen,

5
4. În informatică practică pentru baze de date relaționale, structura de date care rezultă din
eliminarea treptată a concedierilor .
5. În logică, o formă de reprezentare a unei formule logice , în special sunt definite prin:
o Forma normală shannon
o Forma normală de negație
o Formule sub formă normală canonică , în special : forma normală conjunctiva; forma normală
disjunctivă ; forma totală normală
6. În logica predicatelor
o Forma normală ajustată
o Forma normală de negație
o Forma normală pränex
o Skolemform
o Forma normală a c lauzei
7. În cazul sistemelor de reducere abstractă, formele normale sunt applicate pentru un obiect care
nu mai poate fi redus
8. În tehnologia digitală cu filtre digitale în formă formală, numărul minim de elemente ale
acestora ținând cont de proprietățile de filtrare dorite, prin aplicarea filtrul ui digital .

1.1.1. Forma normală booleană,

Printre funcțiile booleane cu n = 1 și n = 2, funcțiile AND, OR și NU ocupă o poziție
excepțională, motiv pentru care proprietățile lor vor fi discutate:
Funcția OR corespunde funcției „ uniune ” sau funcției „ disjuncție ” din teoria seturilor .
Setul de u nire este setul care conține toate elementele seturilor individuale A și B, care poate fi
arătat grafic sub forma unei diagrame Venn:

Fig. 1.1: Diagrama Venn a funcției OR.

6
Dacă, cercul Venn cuprinde valoarea argumentului "1", operația logică a + b retur nează "1" dacă
și numai dacă cel puțin un argument are valoarea "1".
Această „uniune de zonă” corespunde funcției SAU disjuncție .
Tehnologia digitală este extinsă la n> 2 fără a modifica definiția de bază a funcției booleane.
Aceasta are ca rezultat funcți a N-fold OR:
 f (x1, x2, …, xn) = x1 x2 … xn = x1 + x2 + … + xn,
 f (x1, x2, …, xn) = 1, dacă xi = 1 se aplică la cel puțin un argument,
sau (cu aceeași valoare informativă)
 f (x1, x2, …, xn) = 0 dacă xi = 0 se aplică tuturor argumentelor.
Acest fapt po ate fi rezumat și sub forma unui tabel de adevăr pentru n argumente:

Tab.1. 1: Tabelul Adevărului funcției OR.
xn … x2 x1 f (x1, x2, …, xn)
0 … 0 0 0 <- marchează BFkt „OR”
: : : : 1
1 … 1 0 1
1 … 1 1 1

Simbolul de comutare al funcției N -fold OR este, de asemenea, adoptat într -o manieră
corespunzătoare de către OR de două ori:

Fig. 1. 2: Simbolul circuitului funcției OR.
În ceea ce privește implementarea tehnică, funcția de comutare implementată în acest mod este
denumită " poartă SAU ".
Funcția booleană "ȘI" . Funcția AND („ȘI”) corespunde în teoria seturilor „cantității medii ”
sau funcției „ conjuncție ”. Suma medie DIN este ansamblul format din elementele care sunt conținute
atât în setul unic A, cât și în setul unic B, care poate fi arătat grafic și în acest caz sub forma unei
diagrame Venn:

7

Fig.1. 3: Diagrama Venn a funcției AND.
Prin urmare, operația logică a · b are drept rezultat un „1” dacă și numai dacă ambele argumente
au valoarea „1”. Această „suprapunere de zonă” corespund e funcției AND sau conjuncție .
Tranziția la funcția N -fold AND asigură:
 f (x1, x2, …, xn) = x1 x2 … xn = x1 · x2 · … · xn,
 f (x1, x2, …, xn) = 0, dacă xi = 0 se aplică la cel puțin un argument, sau (cu aceeași valoare
informativă)
 f (x1, x2, …, xn) = 1 dacă xi = 1 se aplică tuturor argumentelor.
Acest fapt poate fi rezumat aici sub forma unui tabel de adevăr pentru n argumente:
Tab. 1.2 : Tabelul Adevărului funcției AND.
xn … x2 x1 f (x1, x2, …, xn)
0 … 0 0 0
0 … 0 1 0
: : : : 0
1 … 1 0 0 <- distinge BFkt „ȘI”
1 … 1 1 1

Simbolul de comutare al funcției AND -n-fold este de asemenea adoptat într -o manieră
corespunzătoare de către AND -ul de două ori:

Fig. 1. 4: Simbolul circuitului funcției OR (conform DIN).
În ceea ce privește imple mentarea tehnică, funcția de comutare implementată în acest mod este
denumită " poartă ȘI ".

8
Funcția booleană „NU” . Funcția booleană „NU” (negație, funcția INVERS). În teoria seturilor,
funcția NOT corespunde funcției „ set de complement ” sau „ complement are ”.
Tab. 1. 2: Tabelul Adevărului funcției de URGENȚĂ
A fa)
0 1
1 0
Această funcție reprezintă o operație pur unară, a cărei extindere la n variabile de intrare în
această formă nu are sens. În combinație cu funcțiile N sau fold OR sau OR, această fun cție are și o
poziție specială .
Termenul funcție inversă poate fi introdus într -o formă extinsă:
Definiție : Două funcții booleane f (x1, x2, …, xn) și g (x1, x2, …, xn) sunt invers una față de alta
dacă pentru toate argumentele -n-tuples (x1, x2, …, xn ) se aplică:
(1.4),
Așa cum s -a arătat, orice funcție booleană poate fi reprezentată prin combinații cu un pas de
termeni min sau termeni max. Această formă de descriere funcțională conduce direct la definirea așa –
numitelor forme normale.
Definiție: Forma disjunctivă canonică normală (kDNF) : În forma normală disjunctivă canonică,
o funcție booleană este disociată (funcția SA) minterme sale mam arătat.
Forma normală conjunctivă canonică (kKNF) : În forma normală conjunctivă canonică, o funcție
booleană est e reprezentată de o conjuncție (funcția AND) a maxtermelor sale M i.
Termenul "canonic" indică faptul că BFkt este descris aici în forma sa cea mai simplă (și cea
mai complexă). Simplificările (vezi mai jos) sunt adesea posibile în descrierea funcțiilor, a stfel încât
termenii descriptivi nu vor mai fi neapărat disjuncții complete sau conjuncții complete.
Atât un kDNF cât și un kKNF sunt implementate ca circuite în două etape. Dacă, datorită
simplificărilor, nu toate variabilele sunt legate în stadiul de int rare, o astfel de soluție nu mai este
numită "canonică".
Formele normale corespunzătoare sunt apoi definite ca: Forma normală disjunctivă (DNF) sau
Forma normală conjunctivă (KNF) .
Într-o formă prescurtată, ambele sunt denumite și forme disjun ctive sau co njunctive. Experiența
a arătat că este dificilă abordarea formei conjunctive canonice normale (kKNF). Prin urmare,
principiul de bază ar trebui să fie ilustrat din nou folosind un exemplu:
Diagrama KV a unui exemplu dat BFkt:

9

Fig.1.5: Funcție de exempl u.
Funcția booleană este, prin urmare, descrisă de șase 1 câmpuri și două câmpuri 0.
Cu toate acestea, având în vedere că un termen maxim a fost definit printr -un singur câmp 0 și
este, prin urmare, descris ca o disjuncție completă (unirea setată) în acest caz de șapte 1 câmpuri, doi
termeni maximi trebuie folos im pentru a descrie funcția de mai sus:
Acești doi termeni maximi sunt următorii termeni M2 și M7:

Fig.1.6: Maxterms pentru a descrie funcția din Fig. 1.5.

Suprapunerea acestor doi termeni maxim ar ată clar BFkt. Evident, termenii max trebuie
conectați conjunctiv, adică trebuie formată cantitatea medie.
Exemplu de funcție . Folosind definițiile introduse mai sus, kDNF și kKNF pot fi determinate
direct folosind un tabel de adevăr (tabel de valori).
Funcția booleană f (a, b, c) este dată de următorul tabel de valori:

A b c f (a, b, c)
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Fig. 1.7: Funcția booleană descrisă de tabelul de valori și diagrama KV.

10
a) Formarea formei di sjunctive normale canonice (kDNF): În forma normală disjunctivă
canonică f D, toate conjuncțiile complete (ȘI operațiile) ale variabilelor de intrare a, b, c, care rezultă
în valoarea funcției f D = 1, sunt conectate într -un mod disjunctiv (cu OR); deci a ici:
. (1.1)
Aparent, au fost luate în considerare doar acele linii pentru care variabila de ieșire ia valoarea
1. În nota lui Minterm, Eq. 1.1 cu:
. (1.2)
b) Formarea formei conjunctive canonice normale (kKNF):
În forma normală conjunctivă canonică fK, toate disjuncțiile complete (operații OR) ale
variabilelor de intrare a, b, c, care au ca rezultat valoarea funcției fK = 0, sunt legate împreună (cu
AND);
. (1.3)
În acest caz, au fost luate în considerare doar acele linii pentru care variabila de ieșire ia valoarea
0. În notația Maxterm, ec. 1.3 deci:
. (1.4)
Rezumat: Orice funcție booleană f (x1, …, xn) poate fi întotdeauna descrisă ca kDNF (forma
normală disjunctivă canonică) :
(1.5)
sau ca kKNF (formă normală conjunctivă canonică) :
, (1.6)
Unde:
cu: m i = Minterm ( conjuncție completă ), M i = Maxterm ( afișare completă ).
 Un minterm leagă conjunctiv toate variabilele împreună,
 un maxterm leagă disjunctiv toate variabilele.
 Un kDNF devine un DNF (forma normală disjunctivă) dacă cel puțin un termen conjunctiv nu
este un termen.
 Un kKNF devine KNF (forma normală conjunctivă) dacă cel puțin un termen disjunctiv nu este
un termen maxim.

11
Dacă funcțiile booleane sunt implementate sub forma unei forme normale canonice (kDNF sau
kKNF), de ob icei este necesar un număr mare de porți cu un număr mare de intrări de poartă.
Prin urmare, este necesară simplificarea implementării circuitului. Următoarele considerente
arată cum poate fi realizată o reducere a circuitelor:
 Câmpurile alăturate ale unei diagrame KV diferă într -o singură valoare de argument, de
exemplu, x i = 0 și x i = 1.
 Dacă valoarea funcției (conținutul câmpului) este aceeași pentru aceste două câmpuri,
argumentul x i este irelevant (adică valoarea acestor două câmpuri nu depinde de x i ). În descrierea
funcțională, aceste două câmpuri individuale pot fi înlocuite cu o rețea de câmpuri care include ambele
câmpuri. Acest grup de câmpuri este descris fără argumentul xi; parametrul x i este eliminat.
 Rețelele de câmp de acest tip po t fi acum combinate în rețele mai mari (2 -> 4, 4 -> 8 etc.). De
fiecare dată când rețeaua de câmp este dublată, un alt argument este eliminat. Prin combinarea a
2n Astfel, câmpurile unui grup sunt eliminate n argumente. Desigur, acest lucru înseamnă, de
asemenea, că pot fi conectate doar un număr de câmpuri care corespunde unei puteri întregi a
numărului 2 (locul 2)n = 2,4,8, …).
Privită din partea algebrei booleane, formarea conexiunilor de câmp nu înseamnă altceva decât
aplicarea repetată a relației
. (1.7)
O funcție booleană, a cărei descriere conține astfel de grupuri de câmp, este, desigur, nu mai
este o formă normală canonică, ci o formă conjunctivă (KNF) sau o formă normală disjunctivă (DNF).
De exemplu: Următorul exemplu arată clar formarea unor astfel de rețele de câmp pe diagrama
KV:

Fig. 1.8: Formarea conexiunilor de câmp.
Următoarele rețele de câmp sunt posibile în acest exemplu:
 Câmp de patru m 0, m 1, m 4, m 5
 Câmp de doi m 1, m 3

12
 Câmp de doi m 4, m 6
Luând în considerare aceste rețele de câmp, următoarele rezultate pentru implementarea funcției:
(2 niveluri). (1.8)
sau cu introducerea funcției XOR:
(trei niveluri). (1.9)
În acest exemplu, în mod evident, nu sunt posibile rețele de câmp 0, astfel încât doar o implementare
sub form a kKNF este posibilă:
(1.10)

1.1.2. Forma normală de negație,

Negarea unei subformule este adevărată dacă subformula este falsă, iar negația unei subformule
este falsă dacă subformula este adevărată. Simbolul pe care îl folosim pentru negație este ¬.
Tabelul Adevărului . Tabelul de adevăr de mai jos arată toate combinațiile posibile pentru o
negație. Aici tînseamnă adevărat și fînseamnă fals.
A ¬A
f t
t f

O formulă logică este în formă normală de negație (NNF) dacă operatorii de negație apar direct
în ea doar prin enunțuri atomice. O formulă în formă normală negativă poate fi adusă în
forma conjunctivă (KNF) sau în forma normală disjunctivă (DNF) prin aplicarea legilor distributive .
În general, există mai mult de o formă normală de negație pentru fi ecare formulă logică
propozițională. Acest lucru poate fi ilustrat considerând că fiecare formă normală conjunctivă și
fiecare disjunctivă este, de asemenea, o formă normală de negație.
Forma normală de negație nu este o formă canonică: de exemplu, și sunt echivalente și ambele
sunt într -o formă normală de negație.
În logica clasică , orice formulă poate fi adusă în această formă făcând următo arele: Implicațiile
materiale și bicondițiile care apar în ea sunt rezolvate prin legile de echiva lență care le sun t aplicabile;
Legile lui De Morgan sunt utilizate pentru a schimba negațiile spre interior și, în același timp, pentru
a elimina orice negare dublă care ar putea apărea

13
În logica clasică și în multe logici modale , orice formulă poate fi adusă în această formă prin
înlocuirea implicațiilor și echivalențelor cu definițiile sale, prin înlocuirea legilor lu i De Morgan
prin împingerea negației spre interior și prin eliminarea dublei negații. Acest proces poate fi ilustrat
folosind următoarele reguli de rescriere (Handbook of Automated Reasoning 1, p. 204). :
Exemplu :
x2 x1 x0 y DNF y ¬y DNF ¬ y
0 0 0 0
1 (¬x2∧¬x1∧¬x0)
0 0 1 1 (¬x2∧¬x1∧x0) 0
0 1 0 1 ∨(¬x2∧x1∧¬x0) 0
0 1 1 0
1 ∨(¬x2∧x1∧x0)
1 0 0 1 ∨(x2∧¬x1∧¬x0) 0
1 0 1 0
1 ∨(x2∧¬x1∧x0)
1 1 0 1 ∨(x2∧x1∧¬x0) 0
1 1 1 1 ∨(x2∧x1∧x0) 0

Remode lăm funcția negată cu De Morgan. Forma normală disjunctivă (exemplu din
diapozitiv înainte) : y¯ = x¯2x¯1x¯0 ∨x¯2x1x0∨x2x¯1×0
Cu Legea lui De Morgan: ¬y¯y = ¬ (x¯2x¯1x¯0 ∨x¯2x1x0∨x2x¯1×0) = (x2 ∨x1∨x0) ∧
(x2∨x¯1∨x¯0) ∧ (x¯2∨x1 ∨x¯0)
Forma normală conjunctiva: y¯ = (x2∨x¯1∨x0∨x3) ∧ (x¯2∨x¯1∨x¯0∨x¯3)
Cu Legea lui De Morgan : ¬y¯y = ¬ ((x2 ∨x¯1∨x0∨x3) ∧ (x¯2∨x¯1∨x¯0∨x¯3)) =
x¯2x1x¯0x¯3 ∨x2x1x0x 3
Convert im DNF în KNF . Utilizarea Maxterme Mi care nu este inclusă în extensia Minterme
mi
Exemplu: f (x2, x1, x0) = ⋁i∈ {1,3,5,6,7} mi = ⋀i∈ {0,2,4} Mi
Convert im KNF în DNF . Procedura inversă: Utilizați acele Minterme mi care nu sunt incluse
în extensia Maxterme Mi.
Relația dintre formele normale . Număr de variabile (3): Generați un exemplu aleatoriu . Funcția
booleană poate fi modificată făcând clic pe elementele gri
x2 x1 x0 y DNF KNF
0 0 0 0
(x2∨x1∨x0)
0 0 1 0
∧(x2∨x1∨¬x0)
0 1 0 0
∧(x2∨¬x1∨x0)
0 1 1 0
∧(x2∨¬x1∨¬x0)
1 0 0 0
∧(¬x2∨x1∨x0)
1 0 1 0
∧(¬x2∨x1∨¬x0)
1 1 0 0
∧(¬x2∨¬x1∨x0)

14
1 1 1 0
∧(¬x2∨¬x1∨¬x0)

Relația dintre formele normale . Conversia DNF de la f în DNF de la ¬f . Pentru ¬f, folos im acei
termeni care nu sunt cuprinși în f .
Exem plu: f (x2, x1, x0) ⇔¬f (x2, x1, x0) = ⋁i∈ {1,3,5,6,7} mi = ⋁i∈ {0,2,4} mi
Conversia KNF de la f în KNF de la ¬f . Utilizați pentru ¬f acele maxterme Mi care nu sunt conținute
la f.
Exemplu: f (x2, x1, x0) ⇔¬f (x2, x1, x0) = ⋀i∈ {0.2.4} Mi = ⋀i∈ {1,3,5,6,7 } Mi
Realizarea prin porți logice . Fiecare funcție booleană f = (xn – 1,…, x1, x0) din poziția n poate fi
implementată folosind un circuit standard care corespunde DNF sau KNF . În cazul DNF, minterme –
ul se realizează prin porți AND cu n intrări . Extensia M interme la DNF se face printr -o poartă OR .
Exemplu:

y=f(a,b,c)=ab∨c
a b c y
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Realizarea prin porți logice . În cazul KNF, termenii maximi sunt realizați de porți OR cu n intrări .
Extensia termenilor maxima la KNF se face printr -o poartă AND .

15
Exemplu:

y=f(a,b,c)=ab∨c
a b c y
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

1.1.3. Forma normală conjunctiva
CNF (forma normal conjunctiva) este o combinație de disjunctii de literali . Principalul avantaj
al variantei definitorii a CNF e ste că transformarea nu oferă o creștere exponențială a dimensiunii
formulelor în cel mai rău caz. Cu toate acestea, spre deosebire de CNF, transformarea nu este garantată
să producă o formă echivalentă. În schimb, produce o formă echisatisfăcabilă, adică transformarea
este satisfăcătoare dacă și numai dacă originalul este satisfăcător. În multe cazuri, acest lucru este
suficient.
Ideea cheie cu această transformare este că putem înlocui o subformulă cu o nouă variabilă,
echivalentă cu această formulă. De exemplu, dat fiind a ∧ b ∧ ccă definim p1a fi subformula a ∧ bcare
dă:
(p1 ⇔ a ∧ b) ∧ p1 ∧ c
Putem continua apoi cu definirea p2a fi p1 ∧ cceea ce dă:

16
(p2 ⇔ p1 ∧ c) ∧ (p1 ⇔ a ∧ b) ∧ p2

Conectivul ⇔este echivalent cu o conjuncție a două disjuncții a două subformule. Prin urmare,
o transformare finală în CNF nu ar trebui să conducă la o creștere exponențială a dimensiunii formulei
care este posibilă cu procedura de transformare CNF.
1.1.4. Forma normală prenex,

Forma predex este posibilă o formă norma lă, în care declarațiile de logica predicatelor pot fi
afișate. Printre altele, este necesar ca etapă preliminară a formei Skolem .
O afirmație în logica predicatului de primul nivel este sub formă prenexă dacă
toți cuantificatorii (descrierile domeniului d e aplicare) sunt în afara sau în fața formulei reale. Dacă
forma prenex conține, de asemenea, doar conjuncție , disjuncție și negație (imediat în fața atomilor)
ca joncțiuni , este denumită și forma negativă normală .
În logica predicatului clasic, există o formulă logic echivalentă în formă prenex pentru fiecare
formulă . Acest lucru nu este neapărat cazul în logica intuiționistă .
O formulă în formă de prenex ajustată poate fi îndeplinită dacă forma Skolem poate
fi îndeplinită.
1.1.5. Forma normală skolem.
Skolem este una dintre reprezentările matematice ale logicii predicatelor de argumente pentru
oficializarea și pentru a verifica validitatea. Această formă a primit numele matematicianului
norvegian Albert Thoralf Skolem (1887 -1963).
Algoritmii pentru verific area fiabilității folosesc adesea forma Skolem, deoarece fiecare
formulă poate fi îndeplinită dacă și numai dacă forma Skolem poate fi îndeplinită.
În logica matematică , o formulă a logicii de prim ordin este în forma normală Skolem dacă este
în formă norm ală prenex, cu doar cuantificatori universali de prim ordin .
Reducerea la forma normală a lui Skolem este o metodă pentru eliminarea cuantificatorilor
existențiali din enunțurile logice formale , adesea efectuate ca primul pas într -un proveror automat al
teoremei .

17
1.2. Forme normale (2NF, 3NF, BCNF)

Forma normală 1NF . O relație este în prima formă normală, dacă este bidimensională, adică o
structură de rânduri și coloane există înregistrare de date care aparține unui obiect din lumea reală și
fiecare în registrare de date apare o singură data, există doar date în fiecare coloană care corespunde
unui atribut și atributul apare o singură dată în relație . Se introduce o singură valoare (fără cantitate!)
pentru fiecare atribut
Forma normală 2NF . O relație se află în a doua formă normală dacă fiecare atribut care nu este
cheie este dependent de întreaga cheie primară (care poate consta, de asemenea, din mai multe
câmpuri). Este important ca câmpurile de date să depindă nu numai de o cheie parțială, ci de întrea ga
cheie. Dacă o cheie primară constă din mai multe atribute, v erificăm dacă există atribute care depind
de fapt doar de o parte a cheii primare. Dacă este cazul, această parte a cheii primare și a atributelor
asociate trebuie aduse într -o nouă relație.
Forma normală 3NF . O relație se află la a treia formă normală dacă fiecare atribut non -cheie
depinde doar de întreaga cheie primară (care poate fi constituită și din mai multe câmpuri) și nu apar
interdependențe. De îndată ce un atribut non -cheie poate fi i dentificat doar printr -un alt atribut non –
cheie, se vorbește de dependență tranzitorie. Dependențele tranzitive determină, de asemenea,
redundanța și inconsistența datelor.
Alte forme normale . Există și alte forme normale, dar în practică au un sens redus. Următorul
nivel creează noi relații, => acest lucru este adesea asociat cu o pierdere de viteză în anchete și
tranzacții.
Boyce Codd formă normală (BCNF) . Dependențele (tranzitive) dintre cheile individuale sau
atributele cheie între ele nu sunt luate în considerare în 3NF. Sunt eliminate în BCNF. O relație este
în BCNF dacă niciun atribut cheie nu depinde funcțional de un grup de atribute fără o proprietate
cheie.
PROFESOR {student, curs, lector}
În 3NF, dar nu în BCNF , există
FA1: { student, curs } => le ctor
FA2: lector => curs
Împărțirea în două scheme nu este banală, deoarece ar putea fi împărțită în una dintre cele
trei perechi posibile :
{ Student, lector } și { student, curs }
{Curs, lector } și { student, curs }

18
{ Curs, lector } și { student, lec tor } <=
Dependența funcțională FA1 se pierde în toate cele trei descompuneri. A treia descompunere
este de dorit, deoarece nu creează tupeuri înfiorătoare după o operație de îmbinare și, pe de altă parte,
este fără pierderi.
Reprezentarea informațiilor „ relații încrucișate” prin cheie străină . Atribut care este definit
în raport cu cheia primară a unei alte relații (sau același) (același domeniu) . Relațiile sunt reprezentate
de chei st răine și cheia primară asociată.
Exemplu: model ER <=> schemă relațion ală

Figura 1.8. Model ER <=> schemă relațională
Invariante relaționale ю constrângerile inerente ale modelului relației (condițiile modelului)
1. Condiția cheie primară (integritatea entității)
Unicitatea cheii primare fara valori zero ю
2. Condiție de che ie străină (integritate referențială): cheia primară asociată trebuie să existe,
adică pentru fiecare valoare (nu egală cu zero) a unui atribut de cheie străină a unei relații R2, trebuie
să existe o valoare egală a cheii primare în orice tuple al relației R1.
Specificație DDL: CREATE TABLE FAK (FNR CHAR (4), …), PRIMAR KEY (FNR)
CREATE TABLE STUDENT (MATNR CHAR (9), …, FNR CHAR (4), …) ,. PRIMAR KEY
(MATNR), FOREIGN KEY (FNR) REFERENCES FAK

19
Cheile externe și cheia primară asociată poartă informații importante interrelaționale (uneori și
intra-relaționale)
 ele sunt definite pe același interval de valori
 ele permit legarea relațiilor cu ajutorul operațiunilor de relații
 Tastele externe pot avea valori nule dacă nu fac parte dintr -o cheie primară.
 cheie străină este compusă dacă se compune cheia primară asociată. (Valoarea FS = „zero”
înseamnă că toate componentele sunt setate pe „zero”)
 relație poate avea mai multe chei străine care se referă la relații identice sau diferite
Ciclurile sunt posibile (cal ea referențială închisă) ю O relație poate fi o referință și o relație
de referință („tabel autoreferențial”).
Exemplu de Invariante

Termenii modelului relației
termen sens formal
atribut Coloana unei mese
Gama de valori valori posibile ale unui atribut (domeniu de asemenea)
Valoarea atributului Element al unei serii de valori
Schema de relații Set de atribute
relație Set de rânduri într -un tabel
tuplu Rândul unei mese
Schema bazei de date Set de scheme de relații
cheie set minim de atribute ale că ror valori identifică în mod unic un tuple
al unui tabel
Cheia principala o cheie la proiectarea unei baze de date
Cheie externă Set de atribute care este cheie într -o altă relație
Condiție cheie străină toate valorile atributului cheii străine apar în cealaltă relație ca valori
ale cheii
Formarea schemelor de relații

20
metodă conținut
M1 Definiția euristică a „fișierelor plate”
M2 Normalizarea euristică
1NF => 2NF => 3NF => BCNF
M3 Modelarea relațiilor de entitate și transferul la RS
M4 Schița sub forma unei diagrame de clasă UML și transferul la RS
M5 Proiectarea DB justificată teoretic folosind algoritmul
DECOMPUNERE

Ilustrație ERM => RM

Criterii
 Conservarea informațiilor
 Reducerea redundanței
 Minimizarea efortului de legătură
Deasemene a:
 Naturalitatea imaginii
 Fără amestec de obiecte
 Inteligibilitate

21
СAPITOLUL II. LOGICĂ PROPOZIȚIONALĂ ȘI FORMELE NORMALE
2.1. Logica propozițională și formele normale

Logica propozițională tratează:
conectivitățile ¬( negația ), ∧( conjuncția ), ∨( disjuncția ), ⇒( implicația ) și ⇔( echivalența ).
Limbajul logicii propoziționale conține următoarele simboluri:
 Infinit de multe variabile,
 De conectivele ¬, ∧, ∨, ⇒, ⇔, și
 Paranteze (.).
Ansamblul de formule logice propoziționale, F, este cea mai mică
 Pentru toate Xacestea, care Xeste o variabilă, atunci X∈ F,
 Pentru toți φși ψ, dacă φși ψ∈ F, atunci ¬φ∈ F, φ∧ψ∈ F, φ∨ψ∈ F, φ⇒ψ∈ F și φ⇔ψ∈ F,
 Pentru toate, φastfel încât φ∈ F apoi (φ)∈ F.
Putem folosi, de asemenea, constantele t, sau ⊤, pentru adevăra t, și f, sau ⊥, pentru false și le
avem ca formule propoziționale, dar nu toți autorii le folosesc.
Semantică . Sensul unui conectiv este dat de tabelul său de adevăr . Aceste tabele de adevăr în
combinație cu o atribuire de adevăr ne permit să atribuim o valoare de adevăr ( t sau f) unei formule.
 Atribuire de adevăr, γ satisface o formulă φ, scrisă γ⊨φ, dacă φevaluează t utilizarea γ. O
formulă φeste satisfiable dacă există o anumită misiune d e adevăr γ astfel încât γ⊨φ.
 Atribuire de adevăr, γ satisface un set de formule γ, scrise γ⊨γ, dacă γsatisface fiecare membru
al γ.
 Formulă φeste logic validă , scrisă ⊨φ, dacă φ este satisfăcută de fiecare misiune de adevăr.
 Formulă φeste o consecință logi că a setului de formule γ, scrise γ⊨φ, dacă φeste satisfăcută de
fiecare misiune de adevăr care satisf ace γ.
Formulele φși ψsunt echivalente , scrise φ≡ψdacă sunt satisfăcute de aceleași misiuni.
Operatorii propoziționali transformă formulele predicative si mple în formulei predicative
compuse și, prin aceasta, logica propozițională își lărgește considerabil sfera de aplicabilitate în
procesul formalizării judecăților naturale .
Dacă în formula predicativă P (x 1, x2,…¸ x n), în care P este constantă predicativă , iar x1, x2,…¸
xn – variabile individuale, vom înlocui variabilele individuale cu constante individuale, vom obține o
propoziție atomară P (a1, a 2,…¸ a n) – adevărată sau falsă. Atunci când fiece element al

22
universului U posedă însușirea P, obținem formule cuantificate de tipul „x P(x) . Dacă doar unele
elemente ale acestui univers posedă însușirea P, obținem formule predicative cuantificate, tip $x P(x) .
Cuantorii universali și existențiali pot fi tratați ca generalizări, respectiv,
ale conjuncției și disju ncției neexclusive (inclusive ):
„(x) ș P(a 1)ÙP(a 2)Ù…ÙP(a n);
$(x) ș P(a 1)ÚP(a 2)Ú…ÚP(a n);
Dacă formulele predicative conțin variabile ce aparțin mulțimilor infinite , atunci acești cuantori
exprimă conjuncții și disjuncții infinite .
Pentru a transforma un pre dicat poliadic într -o propoziție, e necesar a cuantifica („lega”) fiecare
variabilă individuală. Cuantificând o formulă predicativă diadică, tip R(x, y) , obținem 8 combinații:
1. „x„y(R(x, y)) – pentru orice x și orice y R(x, y) ;
2. „y„x(R(x, y)) – pentru orice y și orice x R(x, y) ;
3. $x$y(R(x, y)) – există x și y, astfel că R(x, y) ;
4. $y$ x(R(x, y)) – există y și x, astfel că R(x, y) ;
5. „y$x(R(x, y)) – pentru orice y există x, astfel că R(x, y) ;
6. $x„y(R(x, y)) – există x, astfel că pentru orice y R(x, y);
7. „x$y(R(x ,y)) – pentru orice x există y, astfel că R(x ,y) ;
8. $y„x(R(x, y)) – există y, astfel că pentru orice x R(x, y) .
Enunțurile 1) și 2), de asemenea 3) și 4), au același sens logic și deci aceeași valoare de adevăr.
Dacă este adevărat 6), at unci este adevărat și 5) (dar nu și reciproc). Dacă este adevărat 8), atunci este
adevărat și 7) (dar nu și reciproc).
Prin urmare, cuantorii omogeni (de același fel) sunt comutativi, iar cuantorii eterogeni sunt
necomutativi:
„x„y(R(x, y)) ș „y„x (R(x, y) );
$ x$ y(R(x ,y)) ș $ y$ x (R(x, y));
$ x„y(R(x, y)) ® „y$ x (R(x, y));
$ y„x(R(x, y)) ® „x$ y (R(x, y));
Logica de ordinul întâi extinde logica propozițională în mai multe moduri. Alături de
conjunctivele propoziționale ¬ (negație), ∧ (conjuncție), ∨ (disjuncție), ⇒ (implicație) și ⇔
(echivalență), găsim = (identitate), ∀ (cuantificare universală) și ∃ (cuantificare existențială) . În timp
ce logica propozițională are un singur tip de expresie: formula, logica de prim ordin are două tipuri:

23
termenul și for mula. Un termen descrie un obiect din universul discursului, iar o formulă este o
afirmație cu privire la astfel de obiecte.
Limbajul logicii de ordinal întâi conține următoarele simboluri:
 Infinit de multe variabile,
 Conexiunile ¬, ∧, ∨, ⇒, ⇔ și cuantific atorii ∀ și ∃,
 Paranteze (,) și virgule,
 Simbolul identității =,
 Simboluri constante,
 Simbolu ri de funcții,
 Simboluri de relație (a.k.a. Simboluri predicate).
Fiecare simbol și funcție are o proprietate arity care ne spune câte argumente are funcția sau
relația. Se presupune că diferite seturi de simboluri sunt disjuncte în perechi, astfel încât, de exemplu,
nu există niciun simbol care să fie atât o constantă cât și o relație. Unii autori simplifică lucrurile
considerând constantele ca fiind funcții cu ari tate zero. Rețineți că limbajele de prim ordin diferă
numai în seturile de simboluri constante, funcționale și de relație (de exemplu, simbolurile non –
logice).
Setul de termeni logici de prim ordin, T, este cel mai mic
 Pentru toate x astfel încât x este o variabilă, apoi x ∈ T,
 Pentru toate c astfel încât c este un simbol constant, atunci c ∈ T,
 Pentru toate f astfel încât f este un simbol al funcției cu arity n (n -ary) și t1, …, tn ∈ T, apoi f
(t1,…, tn) ∈ T.
Setul de formule logice de prim ordin, F, es te cel mai mic
 Pentru toate r astfel încât r este un simbol de relație cu arity n (n -ary) și t1,…, tn ∈ t, apoi r (t1, …,
tn) ∈ f.
 Pentru toți φ și ψ, dacă φ și ψ ∈ f, atunci ¬φ ∈ f, φ∧ψ ∈ f, φ∨ψ ∈ f, φ⇒ψ ∈ f și φ⇔ψ ∈ f,
 Pentru toate φ astfel încât φ ∈ f atunci (φ) ∈ f,
 Pentru toate x, φ astfel încât φ ∈ f și x o variabilă, apoi ∀xφ ∈ f, ∃xφ ∈ f,
 Pentru toți t1, t2 astfel încât t1 și t2 ∈ t, apoi t1 = t2 ∈ f.
Pentru a oferi semnificație pentru un limbaj de primă ordine, avem nevoie de interpretări pentru
simbolurile non -logice. Dacă avem un limbaj L care are constante din mulțimea C, funcții din
mulțimea F și relații din mulțimea R, atunci putem scrie L = C ∪F∪R. Un model pentru limbajul L
este o structură cuprinzând un univers de discurs și interpretări pe ntru toate constanțele, funcțiile și

24
relațiile. Putem scrie M = (M, …, r,…, f,…, c,…) unde M este universul discursului pentru M și pentru
fiecare c∈C avem un c ∈M, pentru fiecare f ∈F cu arie n, avem un f: Mn → M, pentru fiecare r ∈R cu
arity n, avem un r∈Mn. Aici c, f, r sunt interpretările c, f, r, respectiv. Ca convenție vom scrie M pentru
universul discursului modelului M și c, f, r pentru interpretările lui c, f, r.
Exemplu: L uăm în considerare axiomele pentru o relație de echivalență r
∀x rxx (re flexivitate)
∀x∀y rxy ⇒ ryx (simetrie)
∀x∀y∀z (rxy ∧ ryz) ⇒ rxz (tranzitivitate)
Să luăm acum setul de numere naturale, N, să fie universul discursului și dacă luăm ≤ la
interpretarea lui r, atunci avem un model (N, ≤) pentru limbajul acestor axiome.
Adevă rul este definit pentru propozițiile unei limbi date, așa că trebuie să ne ocupăm de variabile
libere. Există două moduri de a face acest lucru:
extinde limbajul cu o constantă nouă pentru fiecare memeber al universului discursului și
înlocuiește variabile le cu noile constante sau
alocăm elemente ale universului discursului la variabile cu ajutorul mapării.
Prima opțiune este dată în Doets, iar a doua în Deransart și Maluszynski.
Metoda Doets
Dacă M este un model pentru limbajul L, atunci limbajul M LM est e o extensie a lui L adăugând
elementele universului discursului ca simboluri constante. Aceste simboluri noi sunt interpretate ca
ele însele. Termenii, formulele și propoziția LM se numesc M -termeni, formule M și propoziții M.
Dacă M este un model și t es te un termen M de bază, atunci valoarea t, scrisă tM, este dată de
următoarele reguli:
dacă t = c (un simbol constant) atunci tM = c,
dacă t = c (un simbol constant adăugat recent) atunci tM = c,
dacă t = f (t1, …, tn) (o aplicație funcțională) atunci tM = f (t1M, …, tnM).
Dacă M este un model și φ este o propoziție M, atunci adevărul lui φ în M, scris M is, este dat
de următoarele reguli:
dacă φ = r (t1, …, tn), atunci M ⊨φ iff r (t1M, …, tnM)
dacă φ = t1 = t2, atunci M ⊨φ iff t1M = t2M
dacă φ = ¬ψ, atun ci M⊨φ iff M⊯ψ
dacă φ = ψ1 ∧ψ2, atunci M ⊨φ iff M⊨ψ1 și M⊨ψ2. În mod similar pentru celelalte conective
logice (∨, ⇒, ⇔)

25
dacă φ = ∀xψ, atunci M ⊨ψ iff pentru toate v ∈M, M⊨ψ {x / v}
dacă φ = ∃xψ, atunci M ⊨ψ iff pentru unele v ∈M, M⊨ψ {x / v}
Aici ψ {x / v} înse amnă că toate ocurențele libere ale variabilei x sunt înlocuite de noua
constantă v.
Pentru a transforma o formulă a limbajului LM într -o frază M avem nevoie de o misiune M care
este doar o mapare de la setul de variabile la setul de simboluri constante. S etul de variabile libere din
formulă trebuie să fie un subset al domeniului alocării M. Când aplicăm o misiune M, înlocuim fiecare
variabilă gratuită prin imaginea ei. Dacă α este o misiune M și formula o formulă LM, φα este o
propoziție M.
Asignarea M α s atisface forumla φ în modelul M dacă M ⊨φα. Se spune că o formulă este
satisfăcătoare dacă poate fi satisfăcută printr -o misiune într -un anumit model.
Formula φ este valabilă sau adevărată în M, scrisă, M dacă M ⊨φ, dacă este satisfăcută de fiecare
misiune M din M.
Dacă Φ este un set de formule, atunci M este un model de Φ dacă pentru toate φ ∈Φ, M⊨φ.
Formula φ este validă logic, scrisă ⊨φ, dacă este valabilă în fiecare model.
Dacă Φ este un set de formule, atunci φ este o consecință logică a lui Φ, sau φ urme ază logic de
la Φ, scris written, dacă φ este valabil în fiecare model de of.
Dacă φ și ψ sunt formule, atunci φ este logic echivalent cu ψ, scris φ ~ ψ dacă ⊨φ⇔ψ
Metoda Deransart și Maluszynski
Aici atribuim elemente ale universului discursului variabilel or cu ajutorul unor mapări numite
evaluări.
Dacă M este un model pentru limba L, t este un termen și ν este o evaluare pentru variabilele
din t, atunci valoarea lui t, scrisă tM, ν, este dată de următoarele reguli:
dacă t = c (un simbol constant) atunci tM , ν = c,
dacă t = v (un simbol variabil) atunci tM, ν = ν (v),
dacă t = f (t1, …, tn) (o aplicație funcțională) atunci tM, ν = f (t1M, ν, …, tnM, ν).
Dacă M este un model și φ este o formulă și ν este o evaluare pentru variabilele din φ, atunci
adevărul lui φ în M și ν, scris M, ν ⊨φ, este dat de următoarele reguli:
dacă φ = r (t1, …, tn), atunci M, ν ⊨φ iff r (t1M, ν, …, tnM, ν)
dacă φ = t1 = t2, atunci M, ν ⊨φ iff t1M, ν = t2M, ν
dacă φ = ¬ψ, atunci M, ν ⊨φ iff M, ν ⊯ψ

26
dacă φ = ψ1 ∧ψ2, atunci M, ν ⊨φ iff M, ν⊨ψ1 și M, ν ⊨ψ2. În mod similar pentru celelalte
conective logice ( ∨, ⇒, ⇔)
dacă φ = ∀xψ, atunci M, ν ⊨ψ iff pentru toate v ∈M, M, {x / v} ν ⊨ψ
dacă φ = ∃xψ, atunci M ⊨ψ iff pentru unele v someM, M, {x / v} ν ⊨ψ
Aici {x / v} ν semnifică funcția ν 'definită ca ν ' (y) = x dacă x = y, altfel ν (y).
Evaluarea ν satisface forumla φ în modelul M dacă M, ν ⊨φ. Se spune că o formulă este
satisfăcătoare dacă poate fi satisfăcută printr -o evaluare într -un anumit model.
Formula φ este valabilă sau adevărată în M, scrisă, M dacă M⊨φ, dacă este satisfăcută de fiecare
evaluare din M.
Dacă Φ este un set de formule, atunci M este un model de Φ dacă pentru toate φ ∈Φ, M⊨φ.
Formula φ este validă logic, scrisă ⊨φ, dacă este valabilă în fiecare model.
Dacă Φ este un set de formule, at unci φ este o consecință logică a lui Φ, sau φ urmează logic de
la Φ, scris written, dacă φ este valabil în fiecare model de of.
Dacă φ și ψ sunt formule, atunci φ este logic echivalent cu ψ, scris φ ~ ψ dacă ⊨φ⇔ψ
Variabilă gratuită . Într-un limbaj de prim ordin, o variabilă care nu este legată de un
cuantificator universal sau existențial se numește variabilă liberă.
Conceptul de formulă adevărată, tautologia, în logica predicatelor , este mult mai puțin banal
decât conceptul corespunzător de logică de enun ț. Deoarece cu formula logică propozițională, toate
interpretările posibile trebuie să fie acoperite de combinația finită a metodei tabelului adevărului, în
timp ce cu formula logică cuantificatoare, de ex. variabilele se referă la orice zonă de obiect, de ci,
atunci când se evaluează generalitatea unei formule, trebuie verificată aplicabilitatea pentru fiecare
arie de obiect imaginabil.

2.2. Forme normale pentru logica predicatului de primul nivel

În logica propozițională , formula ψ este o consecință logi că sau urmează logic din setul de
formule Φ dacă fiecare atribuire de adevăr care Φ satisface ψ.
În logica de prim ordin , formula ψeste o consecință logică sau urmează logic din setul de
formule, Φdacă ψeste adevărat în fiecare model de Φ.
Dacă este un set de formule, o formulă și atunci putem scrieΦ={φ 0,…,φ n-1}ψΦ⊨ψφ0∧…∧φn-1⊨ψ
Teorema 1 dacă și numai dacă . Dovadă: ( ) Să presupunem că . Pentru fiecare misiune
de adevăr , astfel încât , atunci avem , așa. Fiecare atribuire de adevăr, astfel încât atunci prin

27
definiția implicației . De aici . ( ) Presupunem . Dacă este o misiune de adevăr, atunci . Deci, în cazul în
care apoi prin definiția de implicare. Prin urmare .
φ0∧…∧φn-1⊨ψ⊨φ0∧…∧φn-1⇒ψ⇒φ0∧…∧φn-1⊨ψγγ⊨φ0∧…∧φn-1γ⊨ψγ⊨φ0∧…∧φn-
1⇒ψγγ⊭φ0∧…∧φn-1γ⊨φ0∧…∧φn-1⇒ψ⊨φ0∧…∧φn-1⇒ψ⇒⊨φ0∧…∧φn-1⇒ψγγ⊨φ0∧…∧φn-
1⇒ψγ⊨φ0∧…∧φn-1γ⊨ψφ0∧…∧φn-1⊨ψ
Teorema 2 dacă și numai dacă . Dovadă Dacă atunci . Acum = = =φ0∧…∧φn-1⊨ψ⊭φ0∧…∧φn-
1∧¬ψ⊨φ0∧…∧φn-1⇒ψ⊭¬(φ 0∧…∧φn-1⇒ψ)¬(φ 0∧…∧φn-1⇒ψ)
¬(¬(φ 0∧…∧φn-1)∨ψ)
¬¬(φ 0∧…∧φn-1)∧¬ψ)
φ0∧…∧φn-1∧¬ψ
Conform celor două teoreme date, consecința logică poate fi demonstrată printr -o dovadă
de validitate sau de insatisfacție .
Exemplu . Demonstrăm că aceasta P∧Qeste o consecință logică a formulei
propoziționale P∧(P⇒Q):
1) putem folosi un tabel de adevăr pentru a arăta că fiecare misiune de adevăr care este
satisfăcătoare P∧(P⇒Q)satisface P∧Q:
P Q P⇒Q P∧(P⇒Q) P∧Q
f f t f f
f t t f f
t f f f f
t t t t t
2) putem folosi un tabel de adevăr pentru a arăta că (P∧(P⇒Q))⇒(P∧Q)este o tau tologie:
P Q P⇒Q P∧(P⇒Q) P∧Q (P∧(P⇒Q))⇒(P∧Q)
f f t f f t
f t t f f t
t f f f f t
t t t t t t
3) putem folosi un tabel de adevăr pentru a arăta că (P∧(P⇒Q))∧¬(P∧Q)este o contradicție:
P Q P⇒Q P∧(P⇒Q) ¬(P∧Q) (P∧(P⇒Q))∧¬(P∧Q)
f f t f t f
f t t f t f
t f f f t f
t t t t f f
4) ne putem transforma (P∧(P⇒Q))⇒(P∧Q)într – o formă normală conjunctivă pentru a arăta că este o
tautologie: (P ∧(P⇒Q))⇒(P∧Q)

28
= ¬(P∧¬(P∨Q))∨(P∧Q)
= (¬P∨¬¬(P∨Q))∨(P∧Q)
= (¬P∨P∨Q)∨(P∧Q)
= (⊤∨Q)∨(P∧Q)
= ⊤∨(P∧Q)
= ⊤
5) ne putem transforma (P∧(P⇒Q))∧¬(P∧Q)într – o formă normală disjunctivă pentru a arăta că este o
contradicție:
(P∧(P⇒Q))∧¬(P∧Q)
= (P∧(¬P∨Q))∧¬(P∧Q)
= (P∧(¬P∨Q))∧(¬P∨¬Q)
= (P∧¬P)∨(P∧Q)∧(¬P∨¬Q)
= ⊥∨(P∧Q)∧(¬P∨¬Q)
= (P∧Q)∧(¬P∨¬Q)
= (P∧Q∧¬P)∨(¬P∧¬Q∧Q)
= (⊥∧Q)∨(⊥∧¬P)
= ⊥
Exemplul 2 . Demonstrăm că aceasta mortal(barry)este o consecință logică a formulei de prim
ordin man(barry) ∧(∀X man(X) ⇒mortal(X)). Luăm în considerare un model arbitrar, Mastfel
încât M⊨man(barry) ∧(∀Xman(X) ⇒mortal(X))și M⊭mortal(barry). Avem M⊨man(barry) ∧(man(bar
ry)⇒mortal(barry))și de când man(barry) ⇒mortal(barry)
Este echiv alent cu ¬man(barry) ∨mortal(barry))avem o contradicție. Prin
urmare M⊨mortal(barry).
Logica de ordinul întâi extinde logica propozițională în mai multe moduri. Alături de
conectivitățile propoziționale ¬( negație ), ∧( conjuncție ), ∨( disjuncție ), ⇒( implicație )
și ⇔( echivalență ), găsim =( identitate ), ∀( cuantificare universală ) și ∃( cuantificare
existențială ). În timp ce logica propozițională are un singur tip de expresie: formula , logica de prim
ordin are două tipuri: termenul și formula. Un termen descrie un obiect din universul discursului și o
formulă este o afirmație c u privire la astfel de obiecte.
Sintaxă . Limbajul logicii de prim ordin conține următoarele simboluri:
 Infinit de multe variabile,
 De conectivele ¬, ∧, ∨, ⇒, ⇔, și cuantificatorii ∀, și ∃,

29
 Paranteze (, )și virgulă ,,
 Simbolul identității =,
 Simboluri constante,
 Simboluri de funcții,
 Simboluri de relație (aka simboluri de predicat).
Fiecare simbol și funcție are o proprietate arity care ne spune câte argumente are funcția sau
relația. Se presupune că diferite seturi de simboluri sunt disjuncte în perechi, astfel încât, de exemplu,
nu există niciun simbol care să fie atât o constantă cât și o relație. Unii autori simplifică lucrurile
considerând constantele ca fiind funcții cu aritate zero. Rețineți că limbajele de prim ordin diferă
numai în seturile de simboluri constante, funcționale și de relație (numite simbolurile non -logice).
Setul de termeni logici de prim ordin, T, este cel mai mic
 Pentru toate xacestea, care xeste o variabilă, atunci x∈ T,
 Pentru tot ceea cce ceste un simbol constant atunci c∈ T,
 Pentru toate facestea feste un simbol al funcț iei cu arity n (n -ary) și ∈ T, apoi ∈ T.t1,…, t nf(t1,…,
tn)
Setul de formule logice de prim ordin, F, este cel mai mic
 Pentru tot ceea rce reste un simbol al relației cu arity n (n -ary) și ∈ T, apoi ∈ F.t1,…, t nr(t1,…, t n)
 Pentru toți φși ψ, dacă φși ψ∈ F, atunci ¬φ∈ F, φ∧ψ∈ F, φ∨ψ∈ F, φ⇒ψ∈ F și φ⇔ψ∈ F,
 Pentru toate, φastfel încât φ∈ F apoi (φ)∈ F,
 Pentru toți x, φastfel încât φ∈ F și xo variabilă, apoi ∀xφ∈ F, ∃xφ∈ F,
 Pentru toți, astfel încât și ∈ T, apoi ∈ F.t1t2t1t2t1=t2
Semantică . Pentru a ofer i semnificație pentru un limbaj de primă ordine, avem nevoie de
interpretări pentru simbolurile non -logice. Dacă avem un limbaj Lcare are constante din set C, funcții
din set Fși relații din set R, atunci putem scrie L=C∪F∪R. Un model pentru limbaj Leste o structură
cuprinzând un univers de discurs și interpretări pentru toate constantele, funcțiile și relațiile. Putem
scrie M=(M,…,r,…,f,…,c,…) unde Meste universul discursului Mși
 pentru fiecare c∈Cavem c∈M,
 pentru fiecare f∈Fcu arie n, avem un , f:Mn→M
 pentru fiecare r∈Rcu arie n, avem un , r∈Mn
Iată, c,f,rrespectiv, interpretările c,f,r. Ca o convenție vom scrie Mpentru universul discursului
modelului Mși c,f,rpentru interpretările lui c,f,r.
Exemplu: L uăm în considerare axiomele pentru o relație de echivalență r

30
 ∀x rxx (Reflexivitate)
 ∀x∀y rxy ⇒ ryx (simetrie)
 ∀x∀y∀z (rxy ∧ ryz) ⇒ rxz (Tranzitivitate)
Acum luăm setul de numere naturale N, pentru a fi universul discursului, și dacă luăm ≤la
interpretarea lui r, atunci avem un model (N, ≤)pentru limbajul acestor axiome.
Adevărul este definit pentru propozițiile unei limbi date, așa că trebuie să ne ocupăm de variabile
libere. Există două moduri de a face acest lucru: extinde m limbajul cu o consta ntă nouă pentru fiecare
mem bru al universului discursului și înlocui m variabilele cu noile constante sau alocăm elemente ale
universului discursului la variabile cu ajutorul mapării.
Prima opțiune este dată în Doets, iar a do ua în Deransart și Maluszynski .
Metoda Doets . Dacă M este un model pentru limbaj L, atunci limbajul M este o extensie
a adăugării elementelor universului discursului ca simboluri constante. Aceste simboluri noi sunt
interpretate ca ele însele. Termenii, formulele și propoziția sunt num im termeni M, formule M și
propoziții M. LMLLM
Dacă Meste un model și teste un termen M de bază, atunci valoarea t, scrisă , este dată de
următoarele reguli: tM
1. if (un simbol constant) atunci , t=ctM=c
2. if t=c(un nou simbol constant adăugat) atunci , tM=c
3. if (o aplicație funcțională) atunci . t=f(t1,…,t n)tM=f(t 1M,…,t nM)
În cazul în care M este un model și φeste un M -teză, atunci adevărul φîn M, în scris M⊨φ, este
dată de următoarele reguli:
1. dacă, atunci iffφ= r(t1,…,t n)M⊨φr(t 1M,…,t nM)
2. dacă, atunci iffφ=t 1=t2M⊨φt1M=t2M
3. dacă φ=¬ψ, atunci M⊨φ iffM⊯ψ
4. dacă, atunci iff și. În mod similar pentru celelalte conective logice
( ) φ=ψ 1∧ψ2M⊨φM⊨ψ1M⊨ψ2∨, ⇒, ⇔
5. dacă φ=∀xψ, atunci, M⊨ψ pentru toate v∈M,M⊨ψ{x/v}
6. dacă φ=∃xψ, atunci M⊨ψ pentru unii v∈M,M⊨ψ{x/v}
Aici ψ{x/v}însea mnă că toate ocurențele libere ale variabilei xsunt înlocuite de noua
constantă v.
Pentru a transforma o formulă a limbii într-o frază M avem nevoie de o misiune M care este
doar o mapare de la setul de variabile la setul de simboluri constante. Setul de v ariabile libere din

31
formulă trebuie să fie un subset al domeniului alocării M. Când aplicăm o misiune M, înlocuim fiecare
variabilă gratuită prin imaginea ei. Dacă este o misiune M și o formulă, este o propoziție
M. LMαφLMφα
Sarcina M α satisface forumla φdin model Mdacă M⊨φα. Se spune că o formulă
este satisfăcătoare dacă poate fi satisfăcută printr -o misiune într -un anumit model.
Formula φeste valabilă sau adevărată în M, scrisă, Mdacă M⊨φeste satisfăcută de fiecare
misiune M din M.
Dacă Φeste un set de f ormule, atunci Meste un model de Φ dacă pentru toate . φ∈Φ, M⊨φ
Formula φeste validă logic , scrisă ⊨φ, dacă este valabilă în fiecare model.
Dacă Φeste un set de formule, atunci φeste o consecință logică a Φ, sau φeste urmată logic de
la Φ, scris Φ⊨φ, dacă φeste valabil în fiecare model de Φ.
Dacă φși ψsunt formule, atunci φeste logic echivalent cu ψ, scris φ~ψdacă⊨φ⇔ψ
Metoda Deransart și Maluszynski
Aici atribuim elemente ale universului discursului variabilelor cu ajutorul unor mapări numite
evaluări.
Dacă M este un model pentru limbă L, teste un termen și νeste o evaluare pentru variabilele
din t, atunci valoarea t, scrisă , este dată de următoarele reguli: tM,ν
1. if (un simbol constant) atunci , t=ctM,ν=c
2. if t=v(un simbol variabil) atunci , tM,ν=ν(v)
3. if (o apli cație funcțională) atunci . t=f(t1,…,t n)tM,ν=f(t 1M,ν,…,t nM,ν)
În cazul în care Meste un model și φeste o formulă și νeste o evaluare pentru variabilele din φ, atunci
adevărul φîn Mși ν, în scris M,ν⊨φ, este dată de regulile următoarele:
1. dacă, atunci iffφ=r(t1,…,t n)M,ν⊨φr(t 1M,ν,…,t nM,ν)
2. dacă, atunci iffφ=t 1=t2M,ν⊨φt1M,ν=t2M,ν
3. dacă φ=¬ψ, atunci M,ν⊨φ iffM,ν⊯ψ
4. dacă, atunci iff și. În mod similar pentru celelalte conective logice
( ) φ=ψ 1∧ψ2M,ν⊨φM,ν⊨ψ1M,ν⊨ψ2∨, ⇒, ⇔
5. dacă φ=∀xψ, atunci, M,ν⊨ψ pentru toate v∈M,M,{x/v}ν⊨ψ
6. dacă φ=∃xψ, atunci M⊨ψ pentru unii v∈M,M,{x/v}ν⊨ψ
Aici se {x/v}νreferă la funcția ν' definită ca ν'(y)=x if x=y, otherwise ν(y).
Evaluarea ν satisface forumla φdin model Mdacă M,ν⊨φ. Se spune că o formulă
este satisfăcătoare dacă poate fi sa tisfăcută printr -o evaluare într -un anumit model.

32
Formula φeste valabilă sau adevărată în M, scrisă, Mdacă M⊨φeste satisfăcută de fiecare
evaluare din M.
Dacă Φeste un set de formule, atunci Meste un model de Φ dacă pentru toate . φ∈Φ, M⊨φ
Formula φeste validă logic , scrisă ⊨φ, dacă este valabilă în fiecare model.
Dacă Φeste un set de formule, atunci φeste o consecință logică a Φ, sau φeste urmată logic de
la Φ, scris Φ⊨φ, dacă φeste valabil în fiecare model de Φ.
Dacă φși ψsunt formule, atunci φeste logic e chivalent cu ψ, scris φ~ψdacă⊨φ⇔ψ

2.3. Transformarea în formă normală conjunctiva

Întrucât conjuncția și disjuncția sunt atât comutative cât și asociative și idempotente, elementele
conjunctive și disjunctive nu depind de ordinea lor sau dacă apar o dată sau de mai multe ori. Aceasta
este exprimată în următoarea propoziție:
Lema 1
Sunt φ0,…, φm – 1φ0…..φm-1și ψ0,…, ψn – 1ψ0…..ψn-1formule propoziționale astfel
încât {φ0,…, φm – 1} = { ψ0,…, ψn – 1}{φ0…..φm-1}={ ψ0…..ψn-1} se aplică, apoi se aplică și
∧ ( φ0,…, φm – 1) ≡ ∧ ( ψ0,…, ψn – 1).∨ ( φ0,…, φm – 1) ≡ ∨ ( ψ0,…, ψn – 1).
Propoziția de mai sus justifică ortografii precum
⋀φ ∈ Φφși⋁φ ∈ Φφ⋀φ∈Φφși⋁φ∈Φφ
Precum
⋀ Φși⋁ Φ⋀Φși⋁Φ
pentru seturi de formule finite ΦΦ. Dacă dor im să vă imagi năm o formulă concretă mai jos,
putem defini o secvență a tuturor formulelor propozi ționale. Dacă aceasta este φ0, φ1,…φ0.φ1…. ,
atunci se înțelege de ex. ⋀φ ∈ Φφ⋀φ∈Φφformula ⋀y < nφeuj⋀j<nφeuj , cu indicațiile ijeujfii ales
astfel încât i0< ⋯ < in – 1eu0<⋯<eun -1și φ={φeu0,…, φeun – 1}φ={φeu0…..φeun -1} sa fie valabil.
Se poate alege o abordare complet diferită a expresiilor formei ⋀φ ∈ Φφ⋀φ∈Φφsă se integreze
în logica enunțului. Pentru a face acest lucru, defin im funcțiile booleane care funcționează pe seturi
de valori ale adevărului și utilizează arbori ușor difer im decât cei folos im aici. Gândiți -vă la detalii.
Considerațiile preliminare conduc la următoarele determinări și ortografii. Un set finit de literale
se numește clauză , în special setul gol în acest context se mai numește clauză goală . Un set finit de
clauze este stabilit c lauza . Este MMun set de clauze, este sensul lui ⋀⋁M⋀⋁M dat de
⋀ ⋁ M= ⋀K∈ M⋁L ∈ KL.

33
Unele legi logice propoziționale iau o formă diferită dacă se folosește notația de clauză introdusă
mai sus.
Lema 2
⋀ { }⋀ ⋁ { { } }≡ ⊤.≡ ⊥.⋀{}≡⊤.⋀⋁{{}}≡⊥.
Este MMun set de clauze și KK o clauză așa se aplică
⋀ ⋁ M∧ ⋁ K⋀ ⋁ M∨ ⋁ K≡ ⋀ ⋁ ( M∪ { K} ).≡ ⋀ ⋁ { K'∪ K∣ K'∈ M}.⋀⋁M∧⋁K≡⋀⋁(M∪{K}
).⋀⋁M∨⋁K≡⋀⋁{K'∪K|K'∈M}.
Sunt MMși M'M' Se aplică seturi de clauze
⋀ ⋁ M∧ ⋀ ⋁ M'⋀ ⋁ M∨ ⋀ ⋁ M'≡ ⋀ ⋁ ( M∪ M').≡ ⋀ ⋁ { K∪ K'∣ K∈ M, K'∈ M'}.⋀⋁M∧⋀⋁ M'
≡⋀⋁(M∪M').⋀⋁M∨⋀⋁ M'≡⋀⋁{K∪K'|K∈M.K'∈M'}.
Este MMun set de clauze și Xeu∈ VALXeu∈VAL o variabilă statement, se aplică
( ⋀ ⋁ M) {Xeu↦ ⊥ }( ⋀ ⋁ M) {Xeu↦ ⊤ }≡ ⋀ ⋁ { K∖ { X} ∣ ¬ X∉ K∈ M}.≡ ⋀ ⋁ { K∖ { ¬ X}
∣ X∉ K∈ M}.
A treia și a patra regulă din lema de mai sus motivează următoarele definiții.
Sunt MMși M'M'Seturi de clauze, cea cu M⋓ M'M⋓M'uniune
distributivă desemnată sau uniune interioară a MMși M'M' definit de
M⋓ M'= { K∪ K'∣ K∈ M, K'∈ M'}.M⋓M'={K∪K'|K∈M.K'∈M'}.
Este MMun set de clauze și X∈ VALX∈VAL , atunci constrângerile literale
sunt M|XM|Xși M|¬ XM|¬X sau de asemenea M| XM|Xsau M| ¬ XM|¬X definit de:
M| ¬ XM| X= { K∖ { X} ∣ ¬ X∉ K∈ M}.= { K∖ { ¬ X} ∣ X∉ K∈ M}.
Exemplu
X este0↔ ¬ X1X0↔¬X1echivalent cu (¬X0∨ ¬ X1) ∧ ( X0∨ X1)(¬X0∨¬X1)∧(X0∨X1), care
este o formulă în formă normală conjunctivă. Notarea clauzei în acest caz
este ⋀⋁{{X0, X1}, { ¬ X0, ¬ X1} }⋀⋁{{X0.X1}.{¬X0.¬X1}}.
Pentru a demonstra propoziția de mai sus, este suficient să specificăm un algoritm care
transformă fiecare formulă logică propozițională în formă de negație normală într -o formulă
echivalentă în KNF.
NNF2KNF (φ)(φ)
Condiție: φ∈NNFAL φ∈NNFAL.
caz φφdin ⊥
⊥: return {{}}{{}}
⊤⊤: return {}{}

34
XeuXeu: return {{Xeu} }{{Xeu}}
¬ Xeu¬Xe u: return {{¬Xeu} }{{¬Xeu}} ψ ∨ ψ'ψ∨ψ':
lasa M= NNF2KNF ( ψ )M=NNF2KNF( ψ)și M'= NNF2KNF ( ψ')M'=NNF2KNF( ψ') întoarce
M⋓ M'M⋓M'
ψ ∧ ψ'ψ∧ψ':
lasa M= NNF2KNF ( ψ )M=NNF2KNF( ψ)și M'= NNF2KNF ( ψ')M'=NNF2KNF( ψ') întoarce
M∪ M'M∪M'
Postcondition: return este un set declauze și ⋀⋁return≡ φ
O formulă de logică propozițională este în formă normală disjunctivă (DNF) dacă este
o disjuncție a termenilor de conjuncție. Un termen de conjuncție este format exclusiv
din legătura conjunctivă a literelor.
De exemplu: A \ sau B \ sau C \ sau DA ∨ B ∨ C ∨ D
Elementele individuale ale legăturii OR ( AA,BB,C.C,DD ) Variabile, negația lor sauexpresiile
obținute din eleprintr -o operație AND ( conjuncție ).
De exemplu: (a \ și b) \ sau (a \ și \ not b \ și c) \ sau \ not a( a ∧ b ) ∨ ( a ∧ ¬ b ∧ c ) ∨ ¬ a
Fiecare formulă a logicii enunțului poate fi transformată în forma nor mală disjunctivă, deoarece
fiecare funcție booleană poate fi reprezentată și cu un DNF. Pentru a face acest lucru, porn im de la
tabelul lor de adevăr. Pentru fiecare linie care returnează 1, se formează o conjuncție care leagă toate
variabilele funcției (linia). Variabile le care sunt atribuite 1 în linie nu sunt negate și variabilele care
sunt atribuite 0 sunt anulate. Acești termeni se mai numesc minterme . Forma normală disjunctivă este
obținută în final prin legare a disjunctivă a termenilor.
Exemplu. În următorul tabel cu valori de adevăr sunt date doar liniile în
care funcția noastră are valoarea 11 presupune.
AA bb cc
0 0 1
1 0 0
1 0 1

Cu această metodă, cu cât mai multe linii din tabelul adevărului cu atât expresia este mai lungă.
În general, diagramele Karnaugh -Veitch sau metoda Quine -McCluskey sunt utilizate pentru a
determina o formulă minimă (cu cât mai puțini termeni).

35
O formă normală disjunctivă (DNF) este reprezentarea funcțiilor booleane care este
standardizată într -un mod special în algebra booleană.
O formulă de logică propozițională este în formă normală disju nctivă dacă este o disjuncție a
termenilor de conjuncție. În plus față de cerința menționată mai sus, că expresia logică la nivelul
superior constă exclusiv din operațiuni OR/SAU (nivel OR), nu trebuie să mai existe operații OR în
niveluri inferioare între paranteze. Doar două niveluri sunt permise: nivelul superior al operațiunilor
OR (nivel OR) și nivelul inferior al operațiilor AND (nivel AND). Numai negația poate fi folosită în
continuare pentru elementele nivelului AND.
Astfel de forme normale sunt de folos practic în sistemele cu enunțuri mari – de exemplu în
descrierea logică a aparatelor electrice aeronave cu 50 de parametri de intrare și sute de combinații
posibile. Sistemul este transformat pentru prima dată din descrierea literală în formule logic e – de
ex. "Dacă senzorul de aterizare raportează aterizarea, inversorul de tracțiune poate fi activat". Această
colecție de expresii logice este apoi convertită în DNF. Expresia logică este de obicei mai lungă. Într-
o etapă suplimentară, expresia logică este simplificată folosind diagrama Karnaugh –
Veitch . Duplicările logice sunt eliminate și suprapunerile sunt luate în considerare. Expresia logică
calculată în cele din urmă este apoi integrată în software -ul de control sau implementată în hardware
în elec tronica de control.
Fiecare formulă a logicii enunțului poate fi transformată în forma normală disjunctivă, deoarece
fiecare funcție booleană poate fi reprezentată și cu un DNF. Nu trebuie decât să citești rândurile din
tabelul tău de adevăr. Pentru fiecar e linie care returnează 1, se formează o conjuncție care leagă toate
variabilele funcției (linia). Variabilele care sunt atribuite 1 în linie nu sunt negate și variabilele care
sunt atribuite 0 sunt anulate. Aceste clauze se mai numesc minterme. Forma norm ală disjunctivă este
obținută în final prin legarea disjunctivă a termenilor.
O formă normală disjunctivă canonică (KDNF), numită și o formă normală completă
disjunctivă , este un DNF care conține doar termeni în care sunt prezente toate variabilele, fiecar e
variabilă apare exact o dată și ai căror termeni sunt difer im unul de celălalt. Fiecare funcție booleană
are exact un KDNF.
În KDNF, acele alocări variabile pentru care funcția ia valoarea 1 sunt exprimate de Minterme.
În plus față de forma normală disju nctivă, există și alte forme normale în logica enunțului, cum
ar fi forma normală conjunctivă și forma normală de negație.
O formă disjunctivă normală se numește o formă disjunctivă minimă , dacă

36
 fiecare reprezentare echivalentă a aceleiași funcții de ieșir e are cel puțin la fel de mulți termeni
de produs
 pentru fiecare reprezentare echivalentă a aceleiași funcții de ieșire cu același număr de termeni
de produs, numărul de intrări la termenii produsului este cel puțin la fel de mare ca numărul de intrări
la termenii produsului din f.
Exemplu forma normal disjunctivă
x2 x1 x0 y DNF
0 0 0 0
0 0 1 1 (¬x2∧¬x1∧x0)
0 1 0 1 ∨(¬x2∧x1∧¬x0)
0 1 1 0
1 0 0 1 ∨(x2∧¬x1∧¬x0)
1 0 1 0
1 1 0 1 ∨(x2∧x1∧¬x0)
1 1 1 1 ∨(x2∧x1∧x0)
Exemplu: forma normal conjunctiva
x2 x1 x0 y KNF
0 0 0 0 (x2∨x1∨x0)
0 0 1 1
0 1 0 1
0 1 1 0 ∧(x2∨¬x1∨¬x0)
1 0 0 1
1 0 1 0 ∧(¬x2∨x1∨¬x0)
1 1 0 1
1 1 1 1

Anzahl der Variablen: 3 = die boolesche Funktion verändert werden
x2 x1 x0 y KNF
0 0 0 0 (x2∨x1∨x0)
0 0 1 0 ∧(x2∨x1∨¬x0)
0 1 0 0 ∧(x2∨¬x1∨x0)
0 1 1 0 ∧(x2∨¬x1∨¬x0)
1 0 0 0 ∧(¬x2∨x1∨x0)
1 0 1 0 ∧(¬x2∨x1∨¬x0)
1 1 0 0 ∧(¬x2∨¬x1∨x0)
1 1 1 0 ∧(¬x2∨¬x1∨¬x0)

37
III. IMPLEMENTAREA ALGORITMULUI TRANSFORMARII FORMULELOR IN
FORME NORMALE. APLICAȚIE
3.1. Metode de tranformare a ecuațiilor generale în forma normal

Forma normală este dată după cum urmează:
f (x) = x2 + p ⋅q + c
Pe lângă forma normală în matematică, există și așa -numita formă generală. Înainte de x2, acesta
are un coeficient (diferit de zero), de obicei nu este egal cu 1. Această formă este, prin urmare, dată
astfel:
f (x) = a⋅x2 + p⋅x + q
a, p, q ∈R, a ≠ 0
Putem citi interceptarea y direct din forma normală, precum și din forma generală. Aceasta
corespunde valorii fără x, deci aici q. Acest număr q este de obicei l a sfârșitul funcției.
Formarea de la forma normală la forma vertexului
Avem opțiunea de a modela forma normală la forma vertexului. Pu tem face acest lucru, de
exemplu, dacă dor im să găs im vertexul, dar forma normală este dată.
f (x) = x2 + p ⋅x + q → f (x ) = (x – d) 2 + e
Iată un ghid despre cum se face:
Metodă
1) Cu forma normală începeți cu adăugarea pătrată:
Numărul înainte de x, aici b, este împărțit la 2 și rezultatul este apoi pătrat. Această valoare este
adăugată o dată și apoi scăzută din nou; mate matic vorbind, nu schimbăm nimic.
f (x) = x2 + p ⋅x + (p: 2) 2− (p: 2) 2 + q
2) Calcu lăm valoarea negativă cu ultima valoare:
Valoarea negativă este acum compensată față de ultima valoare, q, adică rezumată.
f (x) = x2 + p ⋅x + (p: 2) 2− (p: 2) 2 + q
3) Apli căm formula binomială:
Pe termen lung la început (în verde) poate fi acum simplificată folosind formula 1 binomială.
Noi obținem:
f (x) = (x + (p: 2)) 2 + q− (p: 2) 2
Facem toate acestea pentru ca la final să obțineți forma vertexului și să pu tem citi v ertexul.
Forma vertexului arată astfel: f (x) = (x – d) 2 + e

38
Cele trei formule binomiale sunt rezumate aici dintr -o privire.
Bine de știut
Pentru orice numere reale pozitive a și b:
1. Formula binomială:
(a + b) 2 = a2 + 2 ⋅a⋅b + b2
2. Formula binomială:
(a – b) 2 = a2−2 ⋅a⋅b + b2
3. Formula binomială:
(a + b) ⋅ (a – b) = a2 – b2
Exemplu cu soluție – transforma forma normală în forma vertexului
Funcția f este dată de ecuația f (x) = x2 + 4 ⋅x – 2. Ecuația trebuie convertită în forma vertexului.
Încercăm mai întâi să transformi funcția în forma vertexului!
Soluție
1) adaos pătrat:
f (x) = x2 + 4 ⋅x – 2
f (x) = x2 + 4 ⋅x + (42) 2− (42) 2−2
f (x) = x2 + 4 ⋅x + 4−4−2
2) Calcu lăm valoarea negativă cu ultima valoare:
f (x) = x2 + 4 ⋅x + 4−4−2
f (x) = (x2 + 4 ⋅x + 4) −6
3) Apli căm formula binomială:
f (x) = (x2 + 4 ⋅x + 4) −6
f (x) = (x + 2) 2−6
Astfel, forma vertexului este: f (x) = (x + 2) 2−6 și vertexul: S (−2 / −6)
Această remodelare pare de obicei destul de complicată la început. Dar de fapt trebuie să vă
amintim doar trei pași. După ce calcul ăm câteva sarcini, îți va fi mai ușor.
Formarea de la forma vertexului la forma normală
Putem schimba forma vertexului în forma normală, de exemplu, pentru a afla interceptarea y.
f (x) = (x – d) 2 + e → f (x) = x2 + b ⋅x + c
Metodă de rezolvare:

39
1) Apli căm formula binomială: Mai întâi trebuie să aplic ăm formula binomială. Dacă există un
plus între paranteze, trebuie să folo sim formula 1 binomială și dacă există un minus între paranteze,
ca aici, trebuie să folo sim a doua formulă binomială.
f (x) = (x – d) 2 + e
f (x) = (x2−2 ⋅x⋅d + d2) + e
2) Adău găm ultimele valori:
Pentru a afla interceptarea y, trebuie adăugate ultimele două valori, adică numerele fără x.
f (x) = x2−2 ⋅x⋅d + d2 + e
f (x) = x2− 2⋅x⋅d + (d2 + e)
Interceptarea y este apoi suma lui d2 și e.
Acum am adus forma vertexului în forma normală. Acest lucru este puțin mai ușor decât invers.
În cele ce urmează, dorim să arătăm un exemplu de calcul al modului în care pu tem utiliza
formularul general.
Exemplu cu soluție – convert im forma vertexului la forma generală
f (x) = 3⋅ (x – 5) 2 + 4
Încer căm să convert im această fo rmă de vertex în formă generală.
Adâncire
1) Apli căm formula binomială:
f (x) = 3⋅ (x – 5) 2 + 4
f (x) = 3⋅ (x2−2⋅x⋅5 + 52) +4
f (x) = 3⋅ (x2−10⋅x + 25) +4
2) Scoa tem paranteza:
f (x) = 3⋅ (x2−10⋅x + 25) +4
f (x) = 3⋅x2−3⋅10⋅x⋅ + 3⋅25 + 4
3) Adău găm ultimele valori:
f (x) = 3⋅x2−3⋅10⋅x⋅ + (3⋅25 + 4)
f (x) = 3⋅x2-3030 x + (75 + 4)
f (x) = 3⋅x2-30⋅x + 79
De exemplu: Dat fiind o funcție f cu cele trei variabile A, B, C. Rezultă un tabel de adevăr cu
2n
23
8Linii.
Următorul tabel prezintă termenii minim i și maximi aparținând respectivei atribuții de intrare.
Dacă, pe de altă parte, toate variabilele de intrare sau negația lor sunt legate între ele într -un mod

40
disjunctiv, rezultă o disjuncție completă, care se numește termenul maxim. Cu n variabile binare există
2n termeni max diferiți.
A B C Minterme, m k Maxterme, M k
0 0 0
A
B
C A
B
C
0 0 I
A
B
C
A
B
C
0 I 0
A
B
C
A
B
C
0 I I
A
B
C
A
B
C
I 0 0
A
B
C
A
B
C
I 0 I
A
B
C
A
B
C
I I 0
A
B
C
A
B
C
I I I A
B
C
A
B
C

3.2. Tipologia algoritmilor pentru transformarea formulelor în forme normale

Forma normală conjunctivă (CNF) este o combinație de disjunctii de literal e. Fiecare formulă
are un echivalent în CNF.
Exemple
A
A ∨ ¬A
A ∧ (B ∨ ¬C) ∧ D
Algoritmul de transformare . Există mai multe metode diferite pentru transformarea unei
formule arbitrare în CNF. Următoarea este una dintre cele mai simple. Aceasta este în esență metoda
prezentată în Doets. Are trei pași:
Elimi năm conectivitățile pentru implicare ( ⇒) și echivalență ( ⇔) prin rescrierea folosind
următoarele echivalențe:
A ⇒ B este echivalent cu ¬A ∨ B
A ⇔ B este echivalent cu (¬A ∨ B) ∧ (A ∨ ¬B)
Împin gem negațiile ( ¬) în interiorul subformulel or, pe cât posibil, aplicând legea lui De
Morgan acolo unde este posibil și elimi năm negațiile duble. De asemenea, ne ocupăm de negația
constantelor propoziționale. Facem acest lucru prin rescrierea cu următoarele echivalențe:

41
¬(¬A) este echivalent cu A
¬(A ∧ B) este echivalent cu ¬A ∨ ¬B
¬(A ∨ B) este echivalent cu ¬A ∧ ¬B
¬t este echivalent cu f
¬f este echivalent cu t
Distribuie disjuncțiile ( ∨) pe conjuncții ( ∧). Rescriem toate subtermurile aplicabile ale
formulei folosind una dintre următoarele două echivalențe:
A ∨ (B ∧ C) este echivalent cu (A ∨ B) ∧ (A ∨ C)
(A ∧ B) ∨ C este echivalent cu (A ∨ C) ∧ (B ∨ C)
Punerea în aplicare . Următorul cod poate fi găsit în directorul de exemple al distribuției Barry's
Prolog . Următorul cod Prolog din această secț iune implementează algoritmul dat mai sus.
Mai întâi fixăm un set de operatori de care va trebui să reprezentăm formulele logicii
propoziționale.
:-op(200, fy, ~). – Negation
:-op(0, yfx, (/ \)).
:-op(400, xfy, (/ \)). -Conjunction (not ISO associativity wh ich is yfx)
:-op(0, yfx, ( \/)).
:-op(500, xfy, ( \/)).- Disjunction (not ISO associativity which is yfx)
:-op(600, xfy, =>). – Implication
:-op(700, xfy, <=>). – Equivalence
Pasul 1 . Elimi năm toate implicațiile și echivalențele.
cnf_rewrite_connectives(~A0, ~A1) :-
cnf_rewrite_connectives(A0, A1).
cnf_rewrite_connectives(A0 / \ B0, A1 / \ B1):-
cnf_rewrite_connectives(A0, A1),
cnf_rewrite_connectives(B0, B1).
cnf_rewrite_connectives(A0 \/ B0, A1 \/ B1) :-
cnf_rewrite_connectives(A0, A1),
cnf_rewrite_connectives (B0, B1).
cnf_rewrite_connectives(A0 => B0, ~A1 \/ B1) :-
cnf_rewrite_connectives(A0, A1),
cnf_rewrite_connectives(B0, B1).

42
cnf_rewrite_connectives(A0 <=> B0, (~A1 \/ B1) / \ (A1 \/ ~B1)) :-
cnf_rewrite_connectives(A0, A1),
cnf_rewrite_connectives(B0, B1).
cnf_rewrite_connectives(A, A).
Pasul 2 . Împin gem negativ recursiv, apli căm legea lui De Morgan acolo unde este posibil și
elimi năm toate dublele negații. În acest moment nu există implicații sau echivalențe, doar conjuncții,
disjuncții și negații.
cnf_pus h_negation(~(~A0), A1) :-
cnf_push_negation(A0, A1).
cnf_push_negation(~(A0 / \ B0), A1 \/ B1) :-
cnf_push_negation(~A0, A1),
cnf_push_negation(~B0, B1).
cnf_push_negation(~(A0 \/ B0), A1 / \ B1):-
cnf_push_negation(~A0, A1),
cnf_push_negation(~B0, B1).
cnf_p ush_negation(A0 / \ B0, A1 / \ B1):-
cnf_push_negation(A0, A1),
cnf_push_negation(B0, B1).
cnf_push_negation(A0 \/ B0, A1 \/ B1) :-
cnf_push_negation(A0, A1),
cnf_push_negation(B0, B1).
cnf_push_negation(~ true, false).
cnf_push_negation(~ false, true).
cnf_p ush_negation(A, A).
Pasul 3 . Distribuie o disjuncție pe conjuncții, atunci când este
posibil. Procedura cnf_distribute/2realizează o astfel de rescriere. Procedura cnf_distribute_loop/2ne
oferă cât mai multe rescrieri.
cnf_distribute(A \/ (B / \ C), (A \/ B) /\ (A \/ C)):- !.
cnf_distribute((A / \ B) \/ C, (A \/ C) / \ (B \/ C)):- !.
cnf_distribute(A0 / \ B, (A1 / \ B)):-
cnf_distribute(A0, A1).
cnf_distribute(A / \ B0, (A / \ B1)):-

43
cnf_distribute(B0, B1).
cnf_distribute(A0 \/ B, (A1 \/ B)):-
cnf_distribute(A0, A 1).
cnf_distribute(A \/ B0, (A \/ B1)) :-
cnf_distribute(B0, B1).
cnf_distribute_loop(A, C) :-
cnf_distribute(A, B),
cnf_distribute_loop(B, C).
cnf_distribute_loop(A, A).
Procedura cnf_transform/2este punctul de intrare.
cnf_transform(A, D) :-
cnf_rewrite_con nectives(A, B),
cnf_push_negation(B, C),
cnf_distribute_loop(C, D).
Forma normală disjunctivă (DNF) . Forma normală disjunctivă (DNF) este
o disjuncție a conjuncțiilor de literale . Fiecare formulă are un echivalent în DNF.
Exemple
A
A ∨ ¬A
A ∨ (B ∧ ¬C) ∨ D
Algoritmul de transformare . Există mai multe metode diferite pentru transformarea unei
formule arbitrare în DNF. Următorul este unul dintre cele mai simple cu trei pași:
1. Elimi năm conectivitățile pentru implicare ( ⇒) și echivalență ( ⇔) prin rescrierea f olosind
următoarele echivalențe:
o A ⇒ B este echivalent cu ¬A ∨ B
o A ⇔ B este echivalent cu (¬A ∨ B) ∧ (A ∨ ¬B)
2. Împin gem negațiile ( ¬) în interiorul subformulelor, pe cât posibil, aplicând legea lui De
Morgan acolo unde este posibil și elimi năm negațiile duble. De asemenea, ne ocupăm de
negația constantelor propoziționale. Facem acest lucru prin rescrierea cu următoarele
echivalențe:
o ¬(¬A) este echivalent cu A
o ¬(A ∧ B) este echivalent cu ¬A ∨ ¬B

44
o ¬(A ∨ B) este echivalent cu ¬A ∧ ¬B
o ¬t este echivalent cu f
o ¬f este echivalent cu t
3. Distribuie conjuncțiile ( ∧) peste disjuncții ( ∨). Rescriem toate subtermurile aplicabile ale
formulei folosind una dintre următoarele două echivalențe:
o A ∧ (B ∨ C) este echivalent cu (A ∧ B) ∨ (A ∧ C)
o (A ∨ B) ∧ C este echivalent cu (A ∧ C) ∨ (B ∧ C)
Punerea în aplicare . Următorul cod poate fi găsit în directorul de exemple al distribuției Barry's
Prolog . Următorul cod Prolog din această secțiune implementează algoritmul d at mai sus. Mai întâi
fixăm un set de operatori de care va trebui să reprezentăm formulele logicii propoziționale.
:-op(200, fy, ~). Negation
:-op(0, yfx, (/ \)).
:-op(400, xfy, (/ \)). Conjunction (not ISO associativity whi ch is yfx)
:-op(0, yfx, ( \/)).
:-op(500, xfy, ( \/)). Disjunction (not ISO associativity which is yfx)
:-op(600, xfy, =>). Implication
:-op(700, xf y, <=>). Equivalence
Pasul 1 . Elimi năm toate implicațiile și ech ivalențele.
dnf_rewrite_connectives(~A0, ~A1) :-
dnf_rewrite_connectives(A0, A1).
dnf_rewrite_connectives(A0 / \ B0, A1 / \ B1):-
dnf_rewrite_connectives(A0, A1),
dnf_rewrite_connectives(B0, B1).
dnf_rewrite_connectives(A0 \/ B0, A1 \/ B1) :-
dnf_rewrite_conn ectives(A0, A1),
dnf_rewrite_connectives(B0, B1).
dnf_rewrite_connectives(A0 => B0, ~A1 \/ B1) :-
dnf_rewrite_connectives(A0, A1),
dnf_rewrite_connectives(B0, B1).
dnf_rewrite_connectives(A0 <=> B0, (~A1 \/ B1) / \ (A1 \/ ~B1)) :-
dnf_rewrite_connectives(A0, A1),
dnf_rewrite_connectives(B0, B1).

45
dnf_rewrite_connectives(A, A).
Pasul 2 . Aplicăm legea lui De Morgan acolo unde este posibil și elimi năm toate dublele negații. În
acest moment nu există implicații sau echivalențe, doar conjuncții, disjuncții și negaț ii.
dnf_push_negation(~(~A0), A1) :-
dnf_push_negation(A0, A1).
dnf_push_negation(~(A0 / \ B0), A1 \/ B1) :-
dnf_push_negation(~A0, A1),
dnf_push_negation(~B0, B1).
dnf_push_negation(~(A0 \/ B0), A1 / \ B1):-
dnf_push_negation(~A0, A1),
dnf_push_negation(~B0, B1).
dnf_push_negation(A0 / \ B0, A1 / \ B1):-
dnf_push_negation(A0, A1),
dnf_push_negation(B0, B1).
dnf_push_negation(A0 \/ B0, A1 \/ B1) :-
dnf_push_negation(A0, A1),
dnf_push_negation(B0, B1).
dnf_push_negation(~ true, false).
dnf_push_negation(~ false, t rue).
dnf_push_negation(A, A).
Pasul 3 . Distribuie o conjuncție pe disjuncții, atunci când este
posibil. Procedura dnf_distribute/2realizează o astfel de rescriere. Procedura dnf_distribute_loop/2ne
oferă cât mai multe rescrieri.
dnf_distribute(A / \ (B \/ C), (A / \ B) \/ (A / \ C)):- !.
dnf_distribute((A \/ B) / \ C, (A / \ C) \/ (B / \ C)):- !.
dnf_distribute(A0 / \ B, (A1 / \ B)):-
dnf_distribute(A0, A1).
dnf_distribute(A / \ B0, (A / \ B1)):-
dnf_distribute(B0, B1).
dnf_distribute(A0 \/ B, (A1 \/ B)):-
dnf_distr ibute(A0, A1).
dnf_distribute(A \/ B0, (A \/ B1)) :-

46
dnf_distribute(B0, B1).
dnf_distribute_loop(A, C) :-
dnf_distribute(A, B),
dnf_distribute_loop(B, C).
dnf_distribute_loop(A, A).
Procedura dnf_transform/2este punctul de intrare.
dnf_transform(A, D) :-
dnf_rewrite_connectives(A, B),
dnf_push_negation(B, C),
dnf_distribute_loop(C, D).
O formulă de primă ordine în Formularul normal de prenex (PNF) poate fi pusă într -o formă
Skolem care este satsfiable dacă ș i numai dacă este originală. O formă Skolem este o propoziție
universală . Toate cantificatoarele existențiale din PNF sunt înlocuite de funcțiile Skolem . ∀x0…∀xn-
1φ
Dacă avem un PNF unde poate conține cantificatori – am scris prefixul doar la primul
cuan tificator existențial – atunci vom crea funcția Skolem care este o nouă funcție a arității . Acum
înlocuim în cu scris. Dacă atunci funcția Skolem este o constantă. ∀x0…∀xn-1∃y φφfnyφf(x 0,…, x n-
1)φ{y/f(x 0,…, x n-1)}n=0
Lema. Formula este satisfăcătoare dacă și numai dacă este satisfăcătoare. ∀x0…∀xn-1∃y
φ∀x0…∀xn-1 φ{y/f(x 0,…, x n-1)}
Dovada.
(⇒) Să presupunem că acesta Meste un model astfel încât . Pentru fiecare există un astfel de
lucru care este adevărat. Putem lăsa să fim și să creștem să avem . Acest model mărit
satisface . M⊨∀x0…∀xn-1∃y φx 0…xn-1yφf(x 0,…,xn-1)yMf∀x0…∀xn-1 φ{y/f(x 0,…, x n-1)}
(⇐) Fiecare model al lui este un model de . ∀x0…∀xn-1 φ{y/f(x 0,…, x n-1)}∀x0…∀xn-1∃y φ
Exemple
 Formula ∀x.a(x) devine ∀x.a(x) întrucât nu conține cantificatori existențiali.
 Formula ∃x.∀y.∃z.foo(x,y,z) devine ∀y.foo(f,y,g(y))
Algoritmul de transformare . Lema de mai sus se aplică până când toate cantificatoarele
existențiale au fost eliminate.
Punerea în aplicare . Următorul cod poate fi găsit în dir ectorul de exemple al distribuției Barry's
Prolog .

47
Mai întâi fixăm un set de operatori, care va trebui să reprezinte formulele logicii de prim ordin.
:-op(200, fy, ~). Negatio n
:-op(400, xfy, (/ \)). Conjunction (not ISO associativity which is yfx)
:-op(500, xfy, ( \/)). Disjunction (not ISO associativity which is yfx)
:-op(600, xfy, =>). Implication
:-op(700, xfy, <=>). Equiv alence

Predicatul skolem_prefix( -Prefix)ne ajută să construim nume de funcții unice
Skolem. Prefixeste un atom folosit pentru a construi principiul funcțiilor Skolem.
skolem_prefix('$skolem').
În apelul la skolem_index( -I) Ieste un contor de inde x utilizat pentru a face funcții Skolem unice.
:- dynamic(skolem_index/1).
skolem_index(0).
Predicatul fresh_skolem_atom( -Atom) ne oferă un atom de principiu al funcției Skolem
unic. Aici Atomeste construit din indexul Skolem și prefixul Skolem.
fresh_skol em_atom(Atom) :-
skolem_prefix(Prefix),
name(Prefix, PrefixCodes),
retract(skolem_index(Index)),
NewIndex is Index+1,
assert(skolem_index(NewIndex)),
name(Index, IndexCodes),
append(PrefixCodes, IndexCodes, AtomCodes),
name(Atom, AtomCodes).
Predica tul skolem_function(+Args, -Function)creează o funcție Skolem. Iată Functiono funcție
Skolem care ia Args.
skolem_function(Args, Function) :-
fresh_skolem_atom(Atom),
Function =.. [Atom|Args].

În predicat skolem_rewrite_variable (+Phi, +V, +W, -Psi), forumula Phiare toate aparițiile
variabilei Vrescrise pentru a Wda Psica formula rezultată.

48
skolem_rewrite_variable (F, V, W, W) :-
var (F),
F == V,
skolem_rewrite_variable(F, _, _, F) :-
var (F),
F \== V,
skolem_rewrite_variable(~A0, V, W, ~A1) :-
skolem_rewri te_variable(A0, V, W, A1).
skolem_rewrite_variable(A0 / \ B0, V, W, A1 / \ B1):-
skolem_rewrite_variable(A0, V, W, A1),
skolem_rewrite_variable(B0, V, W, B1).
skolem_rewrite_variable(A0 \/ B0, V, W, A1 \/ B1) :-
skolem_rewrite_variable(A0, V, W, A1),
skolem_r ewrite_variable(B0, V, W, B1).
skolem_rewrite_variable(exists(X, F), V, _, exists(X, F)) :-
X == V,
skolem_rewrite_variable(exists(X, F0), V, W, exists(X, F1)) :-
X \== V,
skolem_rewrite_variable(F0, V, W, F1).
skolem_rewrite_variable(forall(X, F), V, _, for all(X, F)) :-
X == V,
skolem_rewrite_variable(forall(X, F0), V, W, forall(X, F1)) :-
X \== V,
skolem_rewrite_variable(F0, V, W, F1).
skolem_rewrite_variable(Predicate0, V, W, Predicate1) :- % processes functions and predicates
Predicate0 =.. [F|Args0],
skole m_rewrite_variable_in_args(Args0, V, W, Args1),
Predicate1 =.. [F|Args1].
Un predicat ajutător de cel de mai sus este skolem_rewrite_variable_in_args(+Args, +V, +W, –
Result). Fiecare variabilă Vdin Argseste rescrisă Wcare dă lista Result.
skolem_rewrite_ variable_in_args([], _, _, []) :- !.
skolem_rewrite_variable_in_args([H0|T0], V, W, [H1|T1]) :-

49
skolem_rewrite_variable(H0, V, W, H1),
skolem_rewrite_variable_in_args(T0, V, W, T1).
Predicatul skolem_transform(+Phi, +Vars, -Psi) organizează transformarea în forma
Skolem. Phieste o subformulă care este transformată în forma Skolem Psi. Argumentul Varseste o
listă de variabile cuantificate universal, care au fost procesate până acum în superformulă.
skolem_transform(forall(X, Phi), Vars, forall(X, Psi)) :-
skolem_transform(Phi, [X|Vars], Psi).
skolem_transform(exists(X, Phi0), Vars, Psi) :-
reverse(Vars, ReversedVars),
skolem_function(ReversedVars, SkolemFunction),
skolem_rewrite_variable(Phi0, X, SkolemFunction, Phi1),
skolem_transform(Phi1, Vars, Psi).
skolem _transform(Phi, _, Phi).
Punctul de intrare este predicat skolem_transform(+Phi, -Psi) Aici forma Skolem Phieste Psi.
skolem_transform(Phi, Psi) :- skolem_transform(Phi, [], Psi).
Formația normală de negare (NENF)
Algoritmul de transformare
Algoritmul are d oi pași:
1. Elimi năm conectivul implicit ( ⇒) prin rescriere folosind următoarea echivalență:
o A ⇒ B este echivalent cu ¬A ∨ B
2. Împin gem negațiile ( ¬) în interiorul subformulelor, pe cât posibil, aplicând legea lui De
Morgan acolo unde este posibil și elimi năm negațiile duble. De asemenea, ne ocupăm de
negația constantelor propoziționale. Facem acest lucru prin rescrierea cu următoarele
echivalențe:
o ¬(¬A) este echivalent cu A
o ¬(A ∧ B) este echival ent cu ¬A ∨ ¬B
o ¬(A ∨ B) este echivalent cu ¬A ∧ ¬B
o ¬(A ⇔ B) este echivalent cu A ⇔ ¬B
o ¬t este echivalent cu f
o ¬f este echivalent cu t
Punerea în aplicare
Următorul cod poate fi găsit în directorul de exemple al distribuției Barry's Prolog .

50
Următorul cod Prolog din această secțiune implementează algoritmul dat mai sus. Mai întâi
fixăm un set de operatori de care va trebui să reprezentăm formulele logicii propoziționale.
:-op(200, fy, ~). Negation
:-op(0, yfx, (/ \)).
:-op(400, xfy, (/ \)). Conjunction (not ISO associativity which is yfx)
:-op(0, yfx, ( \/)).
:-op(500, xfy, ( \/)). Disjunction (not ISO associativity which is yfx)
:-op(600, xfy, =>). Implication
:-op(700, xfy, <=>). Equivalence
Pasul 1
Elimi năm toate implicațiile.
nenf_rewrite_connectives(~A0, ~A1) :-
nenf_rewrite_connectives(A0, A1).
nenf_rewrite_connectives(A0 / \ B0, A1 / \ B1):-
nenf_rewrite_connectives(A0, A1),
nenf_rewrite_connectives(B0, B1).
nenf_rewrite_connectives(A0 \/ B0, A1 \/ B1) :-
nenf_rewrite_connectives(A0, A1),
nenf_rewrite_connectives(B0, B1).
nenf_rewrite_connectives(A0 => B0, ~A1 \/ B1) :-
nenf_rewrite_connectives(A0, A1),
nenf_rewrite_connectives(B0, B1).
nenf_rewrite_connectives(A0 <=> B0, A1 <=> B1) :-
nenf_rewrite_connectives(A0, A1),
nenf_rewrite_connectives(B0, B1).
nenf_rewrite_connectives(A, A).
Pasul 2
Împin gem negativ recursiv, apli căm legea lui De Morgan acolo unde este posibil și elimi năm toate
dublele negații. În acest moment nu există implicații decât echivalențe, conjuncții, disjuncții și negații.
nenf_push_negation(~(~A0), A1) :-
nenf_push_negation(A0, A1).
nenf_push_negation(~(A0 / \ B0), A1 \/ B1) :-

51
nenf_push_negation(~A0, A1),
nenf_p ush_negation(~B0, B1).
nenf_push_negation(~(A0 \/ B0), A1 / \ B1):-
nenf_push_negation(~A0, A1),
nenf_push_negation(~B0, B1).
nenf_push_negation(~(A0 <=> B0), A1 <=> B1) :-
nenf_push_negation(A0, A1),
nenf_push_negation(~B0, B1).
nenf_push_negation(A0 / \ B0, A1 /\ B1):-
nenf_push_negation(A0, A1),
nenf_push_negation(B0, B1).
nenf_push_negation(A0 \/ B0, A1 \/ B1) :-
nenf_push_negation(A0, A1),
nenf_push_negation(B0, B1).
nenf_push_negation(A0 <=> B0, A1 <=> B1) :-
nenf_push_negation(A0, A1),
nenf_push_negation( B0, B1).
nenf_push_negation(~ true, false).
nenf_push_negation(~ false, true).
nenf_push_negation(A, A).
Procedura nenf_transform/2este punctul de intrare.
nenf_transform(A, C) :-
nenf_rewrite_connectives(A, B),
nenf_push_negation(B, C).
Forma normală de ne gare (NNF)
Algoritmul de transformare
Algoritmul are doi pași:
1. Elimi năm conectivitățile pentru implicare ( ⇒) și echivalență ( ⇔) prin rescrierea folosind
următoarele echivalențe:
o A ⇒ B este echivalent cu ¬A ∨ B
o A ⇔ B este echivalent cu (¬A ∨ B) ∧ (A ∨ ¬B)

52
2. Împin gem negațiile ( ¬) în interiorul subformulelor, pe cât posibil, aplicând legea lui De
Morgan acolo unde este posibil și elimi năm negațiile duble. De asemenea, ne ocupăm de
negația const antelor propoziționale. Facem acest lucru prin rescrierea cu următoarele
echivalențe:
o ¬(¬A) este echivalent cu A
o ¬(A ∧ B) este echivalent cu ¬A ∨ ¬B
o ¬(A ∨ B) este echivalent cu ¬A ∧ ¬B
o ¬t este echivalent cu f
o ¬f este echivalent cu t
Punerea în aplicare
Următorul cod poate fi găsit în directorul de exemple al distribuției Barry's Prolog .
Următorul cod Prolog din această secțiune implementează algoritmul dat mai sus. Mai întâi fixăm un
set de oper atori de care va trebui să reprezentăm formulele logicii propoziționale.
:-op(200, fy, ~). Negation
:-op(0, yfx, (/ \)).
:-op(400, xfy, (/ \)). Conjunction (not ISO associativity which is yfx)
:-op(0, yfx, ( \/)).
:-op(500, xfy, (\/)). Disjunction (not ISO associativity which is yfx)
:-op(600, xfy, =>). Implication
:-op(700, xfy, <=>). Equivalence
Pasul 1
Elimi năm toate implicațiile și echivalențele.
nnf_rewrite_connectives(~A0, ~A1) :-
nnf_rewrite_connectives(A0, A1).
nnf_rewrite_connectives(A0 / \ B0, A1 / \ B1):-
nnf_rewrite_connectives(A0, A1),
nnf_rewrite_connectives(B0, B1).
nnf_rewrite_connectives(A0 \/ B0, A1 \/ B1) :-
nnf_rewrite_connectives(A0, A1),
nnf_rewrite_connectives(B0, B1).
nnf_rewrite_connectives(A0 => B0, ~A1 \/ B1) :-
nnf_rewrite_connectives(A0, A1),

53
nnf_rewrite_connectives(B0, B1).
nnf_rewrite_connectives(A0 <=> B0, (~A1 \/ B1) / \ (A1 \/ ~B1)) :-
nnf_rewrite_connectives(A0, A1),
nnf_rewrite_connectives(B0, B1).
nnf_rewrite_co nnectives(A, A).
Pasul 2 . Împin gem negativ recursiv, apli căm legea lui De Morgan acolo unde este posibil și elimi năm
toate dublele negații. În acest moment nu există implicații sau echivalențe, doar conjuncții, disjuncții
și negații.
nnf_push_negation(~ (~A0), A1) :-
nnf_push_negation(A0, A1).
nnf_push_negation(~(A0 / \ B0), A1 \/ B1) :-
nnf_push_negation(~A0, A1),
nnf_push_negation(~B0, B1).
nnf_push_negation(~(A0 \/ B0), A1 / \ B1):-
nnf_push_negation(~A0, A1),
nnf_push_negation(~B0, B1).
nnf_push_negation (A0 / \ B0, A1 / \ B1):-
nnf_push_negation(A0, A1),
nnf_push_negation(B0, B1).
nnf_push_negation(A0 \/ B0, A1 \/ B1) :-
nnf_push_negation(A0, A1),
nnf_push_negation(B0, B1).
nnf_push_negation(~ true, false).
nnf_push_negation(~ false, true).
nnf_push_negation (A, A).
Procedura nnf_transform/2este punctul de intrare.
nnf_transform(A, C) :-
nnf_rewrite_connectives(A, B),
nnf_push_negation(B, C).

54
3.3. Exemple de aplicații

Transformarea în forma normal. Folosind un exemplu concret de hiperboloid cu o singură
coajă:
3×2−2y2 + 3z2 + 4xz + 4y – 12 = 03×2 -2y2 + 3z2 + 4xz + 4y -12 = 0
trebuie înțeles cum ecuația unei suprafețe de ordinul doi poate fi transformată în forma normală.
Forma normală a acestui hiperboloid cu o singură coajă este
5x′′2 + y′′2−2z′′2−10 = 0,5x′′ 2 + y′2 -2z′2-10 = 0.
Transformarea constă într -o rotire în jurul axelor principale ale suprafeței și deplasarea
ulterioară a suprafeței în originea coordonatelor. Operațiile geometrice asociate transformărilor în
spațiul tridimensional pot fi descrise într -o formă deosebit de potrivită folosind calculul matricei. În
acest scop, este introdusă pentru prima dată o notare matricială a ecuației de zonă.
Ecuația zonei unei zone de ordinul doi poate fi scrisă și sub formă de matrice. Această notare
permite transf erul și aplicarea calculului matricei pe suprafețele de ordinul doi, în special în ceea ce
privește observarea matricilor ortogonale ca expresie a mișcărilor geometrice în spațiul
tridimensional.
În exemplul concret al hiperboloidului cu o singură coajă în considerare cu ecuația generală
3×2−2y2 + 3z2 + 4xz + 4y – 12 = 03×2 -2y2 + 3z2 + 4xz + 4y -12 = 0
această ecuație poate fi scrisă sub formă de matrice după cum urmează:

Trecem spre centrul zonei . În ecuația de suprafață transformată obținută prin rotație , un termen
liniar arată că centrul suprafeței hiperboloidului cu o singură coajă nu se află în originea coordonate.
5x′2 + y′2−2z′2 + 4z ′ – 12 = 05x′2 + y′2 -2z′2 + 4z′ -12 = 0
Prin schimbarea sistemului de coordonate în așa fel încât originea noului siste m de coordonate
să se afle în centrul zonei (în centrul simetriei), se creează în final forma normală a suprafeței de
ordinul doi.
Schimbarea poate fi implementată matematic în ecuația zonei prin adăugarea unui pătrat.
5x′2 + y′2−2 (z ′ – 1) 2−10 = 05x′2 + y′2-2z′-12-10 = 0

55
Rezultă o transformare a coordonatelor coordonatelor (x ′ | y ′ | z ′) x′y′z ′ în noile coordonate (x
′ ′ | y ′ ′ | z ′ ′) x ′ y ′ ′ ′ ′ ′:
x′=x′′x′=x′′ y′=y′′y′=y′′ z′=z′′+1z′=z′′+1
Ecuația de suprafață a hiperboliodei cu cochilie urme ază în forma normală:
5x′′2+y′′2−2z′′2−10=0.
Următoarele secțiuni vor arăta cum să rezolvăm o problemă de optimizare liniară folosind
metoda simplex. În primul rând, însă, problema de optimizare liniară trebuie să existe într -o formă
normală. Forma normală poate fi derivată cu ușurință din forma standard (vezi capitolul precedent).
Forma normală este definită după cum urmează:
Metodă
maximizați f (x1, x2, …, xn) = cx1 + cx2 + … cxn = ∑nj = 1cjxj
u.d.N (în condiții secundare)
aijxj + … + ainxn = bi i = 1, …, m și j = 1, …, n
xi≥0 j = 1, …, n
Forma normală poate fi scrisă mai compact folosind notație matricială:
Metodă
maximizați f (x) = cTx
u.d.N.
Ax = b
x≥0
Diferența la forma standard este condiția de egalitate = în loc de condiția de inegalitate ≤.
Metodă
Pentru a putea folosi metoda simplex, trebuie să fie disponibilă forma normală. Acest lucru este
obținut din formularul standard. Procedura este următoarea:
1. Convert im problema de optimizare liniară în formă standard (vezi capitolul precedent).
2. Co nvert im forma standard în formă normală:
Pentru aceasta, condiția de inegalitate ≤ forma standard trebuie transformată într -o condiție de
egalitate =. În acest scop, sunt introduse variabilele de alunecare xn + 1, …, xN. Acestea sunt clasificate
0 în cadr ul funcției țintă. Ca multe variabile de alunecare trebuie adăugate, deoarece inegalitățile
trebuie convertite în ecuații.
Exemplu: Convert im forma standard în formă normală
Având în vedere următoarea problemă de optimizare liniară în formă standard:

56
f (x1 , x2) = 5×1 −10×2 + 10×3 → max!
u.d.N
x1 + x2 – x3≤8
−x1− x2 + x3≤ – 8
x1−2×2 + 2×3≤4
x1, x2, x3≥0
Introdu cem forma normală!
Problema de optimizare liniară de mai sus, care este dată în formularul standard, poate fi acum
transformată în forma normală prin introducerea unor variabile de alunecare cărora li se dă valoarea
zero în funcția obiectivă (adică nu sunt luate în considerare). Acum sunt introduse trei variabile de
alunecare pentru cele trei inegalități:
f (x1, x2) = 5×1 −10×2 + 10×3 + 0x4 + 0x5 + 0x6 → max!
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Deoarece variabilele de alunecare sunt incluse în funcția țintă cu valoarea zero, ele pot fi de
asemenea neglijate:
f (x1, x2) = 5×1 −10×2 + 10×3 → ma x!
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Pentru a rezolva această problemă de optimizare liniară poate fi utilizată o metodă simplex
(metoda Big -M, metodă dual simplex). Următoarele secțiuni expli că în detaliu modul în care
funcționează aceste metode.
Forma normală poate fi derivată cu ușurință din formularul standard (vezi capitolul precedent)
și este necesară, de exemplu, pentru aplicarea algoritmilor simplex.
Forma normală este definită după cum urmează:
Metodă

57
maximizați f (x1, x2, …, xn) = cx1 + cx2 + … cxn = ∑nj = 1cjxj
u.d.N (în condiții secundare)
aijxj + … + ainxn = bi i = 1, …, m și j = 1, …, n
xi≥0 j = 1, …, n
Forma normală poate fi scrisă mai compact folosind notație matricială:
Metodă
maximizați f (x) = cTx
u.d.N.
Ax = b
x≥0
Diferența la forma standard este condiția de egalitate = în loc de condiția de inegalitate ≤.
Metodă
Pentru a putea folosi metoda simplex, trebuie să fie disponibilă forma normală. Acest lucru este
obținut din formularul standard. Procedura este următoarea:
1. Convert im problema de optimizare liniară în formă standard (vezi capitolul precedent).
2. Convert im forma standard în formă normală:
Pentru aceasta, condiția de inegalitate ≤ forma standard trebuie transfo rmată într -o condiție de
egalitate =. În acest scop, sunt introduse variabilele de alunecare xn + 1, …, xN. Acestea sunt clasificate
0 în cadrul funcției țintă. Ca multe variabile de alunecare trebuie adăugate, deoarece inegalitățile
trebuie convertite în ecuații.
Următorul exemplu arată cum se poate converti formularul standard în forma normală.
Exemplu: Convert im forma standard în formă normală
Având în vedere următoarea problemă de optimizare liniară în formă standard:
f (x1, x2) = 5×1 −10×2 + 10×3 → ma x!
u.d.N
x1 + x2 – x3≤8
−x1− x2 + x3≤ – 8
x1−2×2 + 2×3≤4
x1, x2, x3≥0
Introdu cem forma normală!
Problema de optimizare liniară de mai sus, care este dată în formularul standard, poate fi acum
transformată în forma normală prin introducerea unor variabile de alunecare cărora li se dă valoarea

58
zero în funcția obiectivă (adică nu sunt luate în considerare). Acum sunt introduse trei variabile de
alunecare pentru cele trei inegalități:
f (x1, x2) = 5×1 −10×2 + 10×3 + 0x4 + 0x5 + 0x6 → max!
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Deoarece variabilele de alunecare sunt incluse în funcția țintă cu valoarea zero, ele pot fi de
asemenea neglijate:
f (x1, x2) = 5×1 −10×2 + 10×3 → max!
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Următoarele secțiuni vor arăta cum să rezolvi o problemă de optimizare liniară folosind metoda
simplex. În primul rând, însă, problema de optimizare liniară trebuie să existe într -o formă normală.
Forma normală poate fi derivată cu ușurință din forma standard (vezi capitolul precedent).
Forma normală este definită după cum urmează:
Metodă
maximizați f (x1, x2, …, xn) = cx1 + cx2 + … cxn = ∑nj = 1cjxj
u.d.N (în condiții secundare)
aijxj +… + ainxn = bi i = 1, …, m și j = 1, …, n
xi≥0 j = 1, …, n
Forma normală poate fi scrisă mai compact folosind notație matricială:
Metodă
maximizați f (x) = cTx
u.d.N.
Ax = b
x≥0
Diferența la forma standard este condiția de egalitate = în loc de con diția de inegalitate ≤.

59
Metodă
Pentru a putea folosi metoda simplex, trebuie să fie disponibilă forma normală. Acest lucru este
obținut din formularul standard. Procedura este următoarea:
1. Convert im problema de optimizare liniară în formă standard (vezi capitolul precedent).
2. Convert im forma standard în formă normală:
Pentru aceasta, condiția de inegalitate ≤ forma standard trebuie transformată într -o condiție de
egalitate =. În acest scop, sunt introduse variabilele de alunecare xn + 1, …, xN. Acestea sunt clasificate
0 în cadrul funcției țintă. Ca multe variabile de alunecare trebuie adăugate, deoarece inegalitățile
trebuie convertite în ecuații.
Următorul exemplu arată cum se poate converti formularul standard în forma normală.
Exemplu: Convert im forma standard în formă normală
Având în vedere următoarea problemă de optimizare liniară în formă standard:
f (x1, x2) = 5×1 −10×2 + 10×3 → max!
u.d.N
x1 + x2 – x3≤8
−x1− x2 + x3≤ – 8
x1−2×2 + 2×3≤4
x1,x2,x3≥0
Problema de optimizare liniară de mai sus, care este dată în formularul standard, poate fi acum
transformată în forma normală prin introducerea unor variabile de alunecare cărora li se dă valoarea
zero în funcția obiectivă (adică nu sunt luate în considerare). Acum sunt introduse trei variabile de
alune care pentru cele trei inegalități:
f (x1, x2) = 5×1 −10×2 + 10×3 + 0x4 + 0x5 + 0x6 → max!
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Deoarece variabilele de alunecare sunt incluse în funcția țintă cu v aloarea zero, ele pot fi de
asemenea neglijate:
f (x1, x2) = 5×1 −10×2 + 10×3 → max!

60
u.d.N
x1 + x2 – x3 + x4 = 8
−x1− x2 + x3 + x5 = −8
x1−2×2 + 2×3 + x6 = 4
x1, x2, x3, x4, x5, x6≥0
Pentru a rezolva această problemă de optimizare liniară poate fi utiliza tă o metodă simplex
(metoda Big -M, metodă dual simplex). Următoarele secțiuni explică în detaliu modul în care
funcționează aceste metode.
Forma vertexului
Forma vertexului funcției cvadratice este:
y = (x – xS) 2 + ySy = x -xS2 + yS
XS și yS sunt coordonat ele x și y ale vertexului parabolei. Vârful indică minimul sau maximul
funcției, în funcție de dacă parabola este deschisă în sus sau în jos.
Forma normală
În forma normală, coeficientul înainte de x2 este 1.
Forma normală a funcției cvadratice cu coeficie nții constanți p și q:
y = x2 + px + qy = x2 + px + q
Dacă funcția cvadratică este în formă normală, vertexul este dat de:
xS = −p2xS = -p2
yS = – (p2) 2 + qyS = -p22 + q
Transformarea de la forma normală la forma vertexului cu o adăugare pătrată și aplica rea
primului binom:
x2 + px + q = x2 + px + q =
x2 + px + (p2) 2− (p2) 2 + q = x2 + px + p22 -p22 + q =
(x + p2) 2− (p2) 2 + q = x + p22 -p22 + q =
(x −− p2) 2− (p2) 2 + qx – p22-p22 + q
Introdu cem coeficienții p și q ai ecuației cvadratice:
p = 3
q = 5
Funcția introdusă este:
y = x2 + 3x + 5y = x2 + 3x + 5
Formarea cu un plus pătrat

61
x2 + 3x + 5 = x2 + 3x + 5 =
x2 + 3xx2 + 3x + (32) 2− (32) 2 + 322 -322 + 5 = + 5 =
|| + (p2) 2 + p22− (p2) 2 -p22 = 0 = 0
(x + 32) 2− (32) 2 + 5 = x + 322 -322 + 5 =
|| a2 + 2aba2 + 2ab + b2 = (a + b) 2 + b2 = a + b2
Forma vertexului:
(x −− 32) 2− (32) 2 + 5 = x – 322-322 + 5 =
|| −1⋅ – 1 = + 1 -1⋅-1 = + 1
(x −− 32) 2 + ( – (32) 2 + 5) = x – 322 + -322 + 5 =
(x −− 1,5) 2 + 2,75x – 1,52 + 2,75
cu
xS = −32 = −1.5xS = -32 = -1,5
yS = – (32) 2 + 5 = 2,75 yS = -322 + 5 = 2,75
Forma generală
Forma generală a funcției cvadratice cu coeficienții constanți a, b și c:
y = ax2 + bx + cy = ax2 + bx + c
Dacă funcția cvadratică este în forma sa generală, vertexul este dat de:
xS = −b2axS = -b2a
yS = −b24a + cyS = -b24a + c
Transformarea de la forma generală la forma vertexului cu adăugarea pătrată și aplicarea
primului binom:
ax2 + bx + c = ax2 + bx + c =
a (x2 + bax) + c = ax2 + bax + c =
a (x2 + bax + (b2a) 2− (b2a) 2) + c = ax2 + bax + b2a2 -b2a2 + c =
a (x2 + bax + (b2a) 2) −b24a + c = ax2 + bax + b2a2 -b24a + c =
a (x + b2a) 2 – b24a + c = ax + b2a2 -b24a + c =
a (x −− b2a) 2 – b24a + cax – b2a2 -b24a + c
Calculator pentru conversia de la forma generală la forma vertical
Exemplu: Introdu cem coeficie nții a, b și c ai funcției cvadratice:
a = 2
b = 5

62
c = 12
Ecuația introdusă este:
2×2 + 5x + 12 = 02×2 + 5x + 12 = 0
Formarea cu un plus pătrat
2×2 + 5x + 12 = 2×2 + 5x + 12 =
2 (x2 + 52x) + 12 = 2×2 + 52x + 12 =
|| un (…) un …
2 (x2 + 52x + (52 ⋅2) 2− (52⋅2) 2) + 12 = 2×2 + 52x + 52 ⋅22-52⋅22 + 12 =
|| + (b2a) 2− (b2a) 2 = 0 + b2a2 -b2a2 = 0
2 (x2 + 52x + (52 ⋅2) 2) −524 ⋅2 + 12 = 2×2 + 52x + 52 ⋅22-524⋅2 + 12 =
|| a (…) + a ⋅a… + a⋅
2 (x + 52⋅2) 2−524⋅2 + 12 = 2x + 52 ⋅22-524⋅2 + 12 =
|| a2 + 2aba2 + 2ab + b2 = (a + b) 2 + b2 = a + b2
Forma vertexului:
2 (x −− 52 ⋅2) 2−524⋅2 + 12 = 2x – 52⋅22-524⋅2 + 12 =
2 (x −− 1,25) 2 + 8.8752x – 1.252 + 8.875
|| −1⋅ – 1 = + 1 -1⋅-1 = + 1
cu
xS = −52⋅2 = −1.25xS = -52⋅2 = -1.25
yS = −524 ⋅2 + 12 = 8.875
Convert im forma ver texului la forma normal. Dacă există o funcție patratică în forma
vertexului și dor im să o convert im la forma normală, fa cem următoarele:
1. O funcție cvadratică este dată în forma vertexului f (x) = a ⋅ (x – w) 2 + sf (x) = a ⋅ (x – w) 2 +
s.
2. Cit im parametrii a, wa, w și ss. Atenție la semnul ww!
3. Calcu lăm p = −2⋅wp = −2⋅w.
4. Calcu lăm q = a⋅w2 + saq = a ⋅w2 + sa.
5. Scrieți forma normală: f (x) = a ⋅ (x2 + p⋅x + q) f (x) = a ⋅ (x2 + p⋅x + q).
Care este forma normală a funcției f (x) = 2 ⋅ (x – 1) 2 + 3f ( x) = 2⋅ (x – 1) 2 + 3?
Este a = 2a = 2, w = 1w = 1 și s = 3s = 3.
Cu aceasta putem calcula p = −2w = −2 ⋅1 = −2p = −2w = −2 ⋅1 = −2 și q = w2 + sa = 12 + 32 =
2q = w2 + sa = 12 + 32 = 2.

63
Forma normală este f (x) = 2 ⋅ (x – 2⋅x + 2) f (x) = 2 ⋅ (x – 2⋅x + 2).
Există, de asemenea, o formă de vertex interactivă în calculatorul de formă normală.
Derivarea formării
f (x) = a⋅ (x – w) 2 + sf (x) = a ⋅ (x – w) 2 + s
f (x) = a⋅ (x2−2xw + w2) + sf (x) = a ⋅ (x2−2xw + w2) + s
f (x) = ax2−2axw + aw2 + sf (x) = ax2−2axw + aw 2 + s
f(x)=a⋅x2+(−2aw) ⋅x+(aw2+s)f(x)=a ⋅x2+(−2aw) ⋅x+(aw2+s)
f(x)=a⋅x2+(−2aw) ⋅x+(aw2+s) ⋅aaf(x)=a⋅x2+(−2aw) ⋅x+(aw2+s) ⋅aa
f(x)=a⋅x2+(−2aw) ⋅x+(aw2+s) ⋅aaf(x)=a⋅x2+(−2aw) ⋅x+(aw2+s) ⋅aa
f(x)=a⋅(x2+(−2w) ⋅x+(aw2+s)/a)f(x)=a ⋅(x2+(−2w) ⋅x+(aw2+s)/a)
f(x)=a⋅(x2+p⋅x+q)f(x )=a⋅(x2+p⋅x+q)
Damit gilt:
p=−2wp=−2w
und
q=(aw2+s)/a
Convert im forma normală în forma vertexului
Dacă există o funcție patratică în forma normală și dor im să o convert im la forma vertexului,
facem următoarele:
1. O funcție patratică este dată în forma no rmală f (x) = a ⋅ (x2 + p⋅x + q) f (x) = a ⋅ (x2 + p⋅x +
q).
2. Cit im parametrii a, pa, p și qq.
3. Calcu lăm w = −p2w = −p2.
4. Calcu lăm s = a⋅q – a⋅p24s = a⋅q – a⋅p24.
5. Scrieți forma vertexului: f (x) = a ⋅ (x – w) 2 + sf (x) = a ⋅ (x – w) 2 + s
Care este f orma de vertex a funcției f (x) = – 4⋅ (x2−2x) f (x) = – 4⋅ (x2−2x)?
Este a = −4a = −4, p = −2p = −2 și q = 0q = 0.
Cu aceasta putem face w = −p2 = −− 22 = 1w = −p2 = −− 22 = 1 și s = a ⋅q – a⋅p24 = −− 4 ⋅ (−2)
24 = 4s = a ⋅q – a Calcu lăm ⋅p24 = −− 4 ⋅ (−2) 24 = 4.
Forma apexului este f (x) = – 4⋅ (x – 1) 2 + 4f (x) = – 4⋅ (x – 1) 2 + 4.
Există, de asemenea, o formă normală interactivă în calculatorul formei vertexului.
Derivarea formării
Pornim de la forma vertexului pe care o căutăm și o transformăm în forma normală.

64
f (x) = a⋅ (x – w) 2 + sf (x) = a ⋅ (x – w) 2 + s
f (x) = a⋅ (x2−2xw + w2) + sf (x) = a ⋅ (x2−2xw + w2) + s
f (x) = ax2−2axw + aw2 + sf (x) = ax2−2axw + aw2 + s
f (x) = a⋅x2 + ( – 2aw) ⋅x + (aw2 + s) f (x) = a ⋅x2 + ( – 2aw) ⋅x + (aw2 + s)
f (x) = a⋅x2 + (- 2aw) ⋅x + (aw2 + s) ⋅aaf (x) = a ⋅x2 + ( – 2aw) ⋅x + (aw2 + s) ⋅aa
f (x) = a⋅x2 + ( – 2aw) ⋅x + (aw2 + s) ⋅aaf (x) = a ⋅x2 + ( – 2aw) ⋅x + (aw2 + s) ⋅aa
f (x) = a⋅ (x2 + ( – 2w) ⋅x + (aw2 + s) / a) f (x) = a ⋅ (x2 + ( – 2w) ⋅x + (aw2 + s) / a)
f (x) = a⋅ (x2 + p⋅x + q) f (x) = a ⋅ (x2 + p⋅x + q)
Se aplică următoarele:
p = −2wp = −2w
și
q = (aw2 + s) / aq = (aw2 + s) / a
Prin remodelarea p = −2wp = −2w se obține
w = −p2w = −p2
Prin introducerea și remodelarea obțineți
s = aq – ap24

65
CONCLUZIE

Formele normale sunt „forme de formule” care au ajuns la o astfel de stare de simplificare
maximă. Inițial, există două tipuri de forme normale pentru formule propoziționale: forma normală
disjunctivă și forma normală conjunctivă.
Studierea formelor norma le produce uneori rezultate oarecum caudate.
Atunci când defin im formule, nu se fac restricții sintactice. Libertatea sintactică este un avantaj:
mai ales atunci când dor im să mode lăm fapte specifice. Pe de altă parte, are dezavantajul că este dificil
de vizualizat proprietățile semantice ale oricărei formule și că orice formulă este destul de dificil de
accesat la întrebări algoritmice. Din aceste motive, formulele sunt limitate în anumite contexte în ceea
ce privește natura lor sintactică. În general, o formă normală este un set de formule care au o anumită
structură sintactică și sunt reprezentative pentru toate formulele.
Aceasta din urmă înseamnă adesea că există un echivalent pentru fiecare formulă din subsetul
analizat. Acesta este cazul, de exemplu, cu forma normală conjunctivă . Totuși, poate însemna, de
exemplu, că există o singură formulă satisfăcătoare pentru fiecare formulă, așa cum este cazul formei
normale Skolem .
Formele normale importante sunt:
 forma normală boolean ,
 forma normală de negație ,
 forma normală conjunctivă ,
 forma normală prenex ,
 forma normală Skolem .
Tabelul adevărului este o definiție clară a unei funcții booleane
Cu toate acestea, există un număr infinit de realizări diferite folosind porți sau descrieri logi ce
sub forma unei expresii booleane
Formele normale sunt deosebit de importante în informatică, în care pe de o parte pu tem modela
faptele rezonabil de bine, dar pe de altă parte pu tem urma o abordare sintactică și în testele de
satisfacție. Aceasta duce la formule în formă normală conjunctivă.
Din simplitate, multe metode de probă sunt definite numai pentru formule cu formă sintactică
limitată. Formulele de altă formă trebuie mai întâi să fie „normalizate”, adică să fie transformate în
forma sintactică corespunzătoare.

66
În informatică, expresiile logic e și sistemele logice stau la baza circuitelor elementare, precum
și a limbajelor de programare superioare. Sunt făcute declarații care sunt examinate pentru
veridicitatea lor (afirmație adevărată sau falsă). Aceste afirmații elementare pot fi apoi combina te într –
un sistem complex folosind reguli și legi specifice. Algebra enunțurilor poate fi identificată filosofului
grec Aristotel (384 -322 î.Hr.). Aristotel a introdus calculul logic cu două valori, care este încă utilizat
astăzi. Doar cele două valori de adevăr „adevărate” sau „false” sunt atribuite enunțurilor și legăturilor
lor. Prin această logică formală, multe afirmații ale matematicii și informaticii, dar și din viața de zi
cu zi, pot fi identificate la aceste două valori ale adevărului, fără a le re stricționa. „O afirmație este o
structură lingvistică, din care are sens să spunem că este adevărată sau falsă.” (Aristotel)
De exemplu, decizia de a traversa o stradă este simplificată prin declarațiile „nici o mașină nu
vine din stânga” și „nici o mașin ă nu vine din dreapta”. Dacă ambele afirmații sunt adevărate,
rezultatul „drumul poate fi străbătut” este, de asemenea, adevărat. Aceasta înseamnă că afirmațiile
sunt legate: „Drumul poate fi străbătut dacă nu vine nici o mașină din stânga și dacă nici o m așină nu
vine din dreapta”.
Alocarea valorilor adevărului unui enunț formulat lingvistic este adesea subiectivă, dar poate fi
formulată și ca o afirmație dacă există îndoieli cu privire la corectitudinea alocării valorii adevărului
fără a încălca calculul logic. Pe de altă parte, fără îndoială, nu este o afirmație dacă forma de enunțare
a acesteia este contradictorie, având în vedere condițiile limită date.
O declarație logică poate fi reprezentată în diferite moduri. Poate fi formulat verbal sau descris
folosind anumite formalisme (algebra booleană). Dar chiar și într -o formă de descriere definită, există
de obicei mai multe opțiuni de afișare, toate fiind echivalente între ele. Prin urmare, o declarație poate
fi descrisă prin mai multe forme de enunț recip roc echivalente. Declarațiile cu caracter textual sunt
confuze și predispuse la erori. Prin urmare, matematicianul englez George Boole (1815 -1864) a
încercat să exprime formal această logică și în 1847 și a dezvoltat algebra logicii, care a fost numită
apoi algebră booleană.
De obicei, nu există restricții sintactice la definirea formulelor, de ex. noi formule apar dintr -o
formulă (indiferent dacă este o formulă a logicii enunțului sau a logicii predicatului) dacă aparițiile
individuale ale articulației ∧∧ sunt înlocuite de articulația ∨∨.
Pe de o parte, libertatea sintactică este un avantaj: mai ales atunci când d orim să mode lăm fapte
specifice. Pe de altă parte, are dezavantajul că este dificil de vizualizat proprietățile semantice ale
oricărei formule și că orice formulă este destul de dificil de accesat la întrebări algoritmice.

67
BIBLIOGRAFIE

1. An Expansion -based QBF Solver For Negation Normal Form, http://fmv.jku.at/master/Lonsing –
MasterThesis -2007.pdf
2. Boolesche Algebra und digitale Lo gik, http://dispert.international –
university.eu/Digital_Design_Website_German/digital1/dig001_5.htm
3. Efficient Parallelizations of Hermite and Smi th Normal Form Algorithms,
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.544.2465&rep=rep1&type=pdf
4. Erste Normalform
5. Forme normale in calcul prop ozițiilor bivalente (Formes normales dans le calcul des
propositions bivalentes). Roumanian, with Russian and French summaries. Buletin științific, Secția
de științe matematice și fizice, vol. 8 (1956), pp. 297 –327.,
https://www.cambridge.org/core/journals/journal -of-symbolic -logic/article/mihailescu -eugen -forme –
normale -in-calcul -propozitiilor -bivalente -formes -normales -dans-le-calcul -des-propositions –
bivalentes -roumanian -with-russian -and-french -summa ries-buletin -stiintific -sectia -de-stiinte –
matematice -si-fizice -vol-8-1956 -pp-297327
6. Grundlagen der technischen Informatik, https://ti.uni –
due.de/ti/de/education/ teaching/ws1718/gti/GTI_Kap01_WS1718.pdf
7. https://de.wikipedia.org/wiki/Skolemform
8. https://sites.google.com/site/dieleico/programmierung/datenbankanwendung/grundlagen –
relationenmodell#TOC -1.-Normalform -1NF
9. https ://www.academia.edu/36775506/Teodor_Stihi_ -_Introducere_in_logica_simbolica.pdf
10. https://www.ibm.com/support/knowledgecenter/de/SSGU8G_12.1.0/com.ib m.ddi.doc/ids_ddi
_188.htm
11. Konjunktive und disjunktive Normalformen, http://www.inf.fu -berlin.de/lehre/WS09/infa/dnf –
knf.pdf
12. Logică computațională O introducere practică pentru studenț i la informatică Note de curs,
https://staff.fmi.uvt.ro/~adrian.craciun/lectures/logica/pdf/noteDeCursLogica.pdf
13. LOGICA PENTRU INFORMATICĂ, https://profs.info.uaic.ro/~masalagiu/pub/LOGICA –
R_2016.pdf
14. Normal Form, a Representation Theorem, and a Regular Approximation for Context -Free
Languages,

68
https://www.researchgate.net/publication/320036093_A_Normal_Form_a_Representation_Theorem
_and_a_Regular_Approximation_for_Context -Free_Lang uages
15. Normalformen aussagenlogischer Formeln und die Darstellbarkeit Boolescher Funktionen
durch aussagenlogische Formeln, https://www.math.uni -heidelberg.de/logic/md/lehre/fo lien_1.3.pdf
16. Normalformen boolescher Funktionen, http://wwwmayr.in.tum.de/lehre/2010WS/ds/2010 -11-
02.pdf
17. Normalformen von Matrizen Jordansche Normalform, http://reh.math.uni –
duesseldorf.de/~bogopolski/Lehrveranstaltungen/PS_LinAlgebra09/Bojda.pdf
18. Normalformen von Schaltfunktionen, https://schuelerunterlagen.de/wp –
content/uploads/2017/11/Normalformen -von-Schaltfunktionen.pdf
19. Pradikatenlogik – kurzgefasst, https://link.springer.com/content/pdf/bbm%3A978 -3-540-
33994 -6%2F1.pdf
20. Propositional Analysis, http://intrologic.stanford.edu/notes/chapter_03.html
21. Relationenmodell – Normalisieren
22. UMFORMUNG IN DIE NORMALFORM (MAXIMIERUNGSPROBLEM),
https://www.ingenieurkurs e.de/unternehmensforschung/grundlagen -des-operations -research –
1/standardform -maximierungsproblem/dualer -simplexalgorithmus.html