2.1.4. Forme de reprezentare a declarațiilor
1. Formularul A1ÚA2Ú.ÚAN. unde Ai este o declarație elementară sau negarea unei declarații elementare (literală), se numește o disjuncție elementară.
2. Formularul B1 × B2 × × Bn. unde Bi este literal, se numește conjunct elementar.
3. Formularul D1 × D2 ×. × Dn. unde Dj este disjuncția elementară, se numește forma normală conjunctivă (CNF).
4. Forma K1ÚK2Ú.ÚKn. unde Kj este o conjuncție elementară, se numește o formă normală disjunctivă (DNF).
Întotdeauna adevăratul (pe orice set de valori ale propozițiilor elementare care intră în el) o declarație complexă se numește tautologie.
Întotdeauna fals (pe orice set de valori ale propozițiilor elementare care intră în ea) declarația se numește o contradicție.
Un CNF perfect (SKNF) este un CNF astfel încât fiecare disjuncție elementară care o introduce să conțină toate propozițiile elementare direct sau cu inversiune strict o dată. Nu există disjuncții recurente. Orice declarație complexă, în afară de tautologie, are un SKNF unic.
Un DNP (DNNF) este numit DNF, astfel încât fiecare conjuncție elementară care intră în el conține toate propozițiile elementare direct sau cu inversiune strict o dată. Nu există conjuncții recurente. Orice declarație complexă, altul decât o contradicție, are un singur CDNF.
2.1.5. Transformarea declarațiilor
O declarație complexă, prezentată într-o formă arbitrară prin intermediul echivalențelor 11-16, și folosind legile lui De Morgan poate fi transformată în formă normală.
Conversia CNF în SKNF.
Schematic, ideea de bază a transformării poate fi reprezentată după cum urmează:
Conversia DNP la SDNF.
Schematic, ideea de bază a transformării poate fi reprezentată după cum urmează:
Conversia CDNF la SKNF.
Luați în considerare exemplul:
Luăm funcția logică f (declarație complexă) în SDNF și construim negarea acestei funcții, adică funcția f, prin scrierea tuturor constituenților unității care nu aparțin f.
Să aibă forma
Un dispozitiv mnemonic este de a atribui constituenților numerele care sunt obținute prin privirea la constituenți ca numere binare.
Negarea funcției este obținută prin scrierea elementelor lipsă (numere binare lipsă).
Acum aplicați negația funcției.
Articole similare
Trimiteți-le prietenilor: