Tərif 1.Konyunktiv monomial (elementar birləşmə) dəyişənlərdən bu dəyişənlərin birləşməsi və ya onların inkarları adlanır.

Misal üçün, elementar bağlayıcıdır.

Tərif 2.Disjunktiv monomial (elementar disjunksiya) dəyişənlərdən bu dəyişənlərin diszyunksiyası və ya onların inkarları adlanır.

Misal üçün, elementar disjunksiyadır.

Tərif 3. Verilmiş təklif cəbr düsturuna ekvivalent olan və elementar konyunktiv monomiyalların disjunksiyasından ibarət düstur deyilir disjunktiv normal forma(DNF) bu düsturun.

Misal üçün,- DNF.

Tərif 4. Verilmiş təklif cəbri düsturuna ekvivalent olan və elementar disyunktiv monomialların birləşməsindən ibarət olan düstura deyilir. konyunktiv normal forma(CNF) bu düsturun.

Misal üçün, – KNF.

Hər bir təklif cəbr düsturu üçün bir sıra disjunktiv və konyunktiv normal formalar tapmaq olar.

Normal formaların qurulması alqoritmi

Məntiq cəbrinin ekvivalentlərindən istifadə edərək, düsturdakı bütün əməliyyatları əsaslarla əvəz edin: birləşmə, disjunksiya, inkar:

İkiqat mənfi cəhətlərdən qurtulun.

Lazım gələrsə, birləşmə və disjunksiya əməliyyatlarına paylanma və udma düsturlarının xassələrini tətbiq edin.

2.6. Mükəmməl disjunktiv və mükəmməl konyunktiv normal formalar

İstənilən Boolean funksiyası çoxlu DNF və CNF təmsillərinə malik ola bilər. Bu təmsillər arasında mükəmməl DNF (SDNF) və mükəmməl CNF (SKNF) xüsusi yer tutur.

Tərif 1. Mükəmməl disjunktiv normal forma(SDNF) hər bir konyunktiv monomial çoxluqdakı hər dəyişəni tam olaraq bir dəfə ehtiva etdiyi və ya özü və ya inkarının daxil olduğu DNF-dir.

Struktur olaraq, DNF-ə endirilən təklif cəbrinin hər bir düsturu üçün SDNF aşağıdakı kimi müəyyən edilə bilər:

Tərif 2. Mükəmməl disjunktiv normal forma Təklif cəbr düsturunun (SDNF) aşağıdakı xüsusiyyətlərə malik olan DNF adlanır:

Tərif 3. Mükəmməl konyunktiv normal forma(SKNF) hər bir disjunktiv monomial çoxluqdakı hər dəyişəni tam olaraq bir dəfə ehtiva etdiyi və ya özü və ya inkarının daxil olduğu bir CNF-dir.

Struktur olaraq, CNF-ə endirilən təklif cəbrinin hər bir düsturu üçün SKNF aşağıdakı kimi müəyyən edilə bilər.

Tərif 4. Mükəmməl konyunktiv normal forma Verilmiş təklif cəbri düsturunun (SKNF) aşağıdakı xüsusiyyətləri təmin edən CNF-dir.

Teorem 1. Eyni yalan olmayan dəyişənlərin hər bir Boolean funksiyası SDNF-də və üstəlik, unikal şəkildə təmsil oluna bilər.

SDNF tapmaq yolları

1-ci yol

2-ci yol

formulun 1 qiymətini aldığı sətirləri seçin;

bağlayıcıların disjunksiyasını aparırıq, bir şərtlə ki, əgər dəyişən 1 qiyməti ilə birləşməyə daxil edilirsə, onda bu dəyişəni yazırıq, əgər 0 qiyməti ilə onu inkar edirik. SDNF alırıq.

Teorem 2. Eyni dərəcədə doğru olmayan dəyişənlərin hər bir Boolean funksiyası SKNF-də və üstəlik, özünəməxsus şəkildə təmsil oluna bilər.

SKNF tapmaq yolları

1-ci yol– ekvivalent çevrilmələrin köməyi ilə:

2-ci yol- həqiqət cədvəllərindən istifadə etməklə:

formulun 0 qiymətini qəbul etdiyi sətirləri seçin;

disjunksiyaların birləşməsini tərtib edirik, bir şərtlə ki, əgər dəyişən 0 qiyməti ilə disjunksiyaya daxil edilibsə, onda bu dəyişəni, qiyməti 1-dirsə, inkarını yazırıq. SKNF alırıq.

Misal 1 CNF funksiyalarının qrafikini tərtib edin.

Həll

Dəyişənlərin çevrilməsi qanunlarından istifadə edərək "" bağlantısını ləğv edin:

= /de Morqan qanunları və ikiqat inkar/ =

/paylayıcı qanunlar/ =

Misal 2 Düsturu DNF-ə çevirin.

Həll

Məntiqi əməliyyatları aşağıdakılarla ifadə edirik:

= /İnkarı dəyişənlərlə əlaqələndirin və ikiqat inkarları azaldın/ =

= /paylanma qanunu/ .

Misal 3 Düsturu DNF və SDNF-də yazın.

Həll

Məntiq qanunlarından istifadə edərək, biz bu düsturu yalnız elementar birləşmələrin disjunksiyalarını ehtiva edən formaya salırıq. Nəticə düstur istənilən DNF olacaq:

SDNF qurmaq üçün bu düstur üçün həqiqət cədvəlini tərtib edəcəyik:

Cədvəlin düsturunun (sonuncu sütun) 1 qiymətini aldığı sətirləri qeyd edirik. Hər bir belə sətir üçün bu sətirin ,, dəyişənlər çoxluğunda doğru olan düstur yazırıq:

sətir 1: ;

sətir 3: ;

sətir 5: .

Bu üç düsturun ayrılması yalnız 1, 3, 5-ci sətirlərdəki dəyişənlər dəstində 1 qiymətini alacaq və buna görə də tələb olunan mükəmməl disyunktiv normal forma (PDNF) olacaqdır:

Misal 4 Düsturu SKNF-ə iki yolla gətirin:

a) ekvivalent çevrilmələrin köməyi ilə;

b) həqiqət cədvəlindən istifadə etməklə.

Həll:

İkinci elementar disjunksiyanı çeviririk:

Formula belə görünür:

b) bu ​​düstur üçün həqiqət cədvəlini tərtib edin:

Cədvəlin düsturunun (sonuncu sütun) 0 qiymətini aldığı sətirləri qeyd edirik. Hər bir belə sətir üçün bu sətirin ,, dəyişənlər çoxluğunda doğru olan düsturu yazırıq:

sətir 2: ;

sətir 6: .

Bu iki formulun birləşməsi yalnız 2 və 6-cı sətirlərdəki dəyişənlər dəstində 0 qiymətini alacaq və buna görə də arzu olunan mükəmməl konyunktiv normal forma (CKNF) olacaqdır:

Müstəqil həll üçün suallar və tapşırıqlar

1. Ekvivalent çevrilmələrdən istifadə edərək, düsturları DNF-yə gətirin:

2. Ekvivalent çevrilmələrdən istifadə edərək, düsturları CNF-ə gətirin:

3. İkinci paylama qanunundan istifadə edərək DNF-ni CNF-ə çevirin:

a) ;

4. Verilmiş DNF-ləri SDNF-lərə çevirin:

5. Verilmiş CNF-ni SKNF-ə çevirin:

6. Verilmiş məntiqi düsturlar üçün SDNF və SKNF-ni iki üsulla qurun: ekvivalent çevrilmələrdən istifadə etməklə və həqiqət cədvəlindən istifadə etməklə.

b) ;

İstənilən məntiqi düstur üçün eyni çevrilmələrin köməyi ilə ona ekvivalent olan sonsuz sayda düsturlar qurmaq olar. Məntiq cəbrində əsas vəzifələrdən biri kanonik formaların axtarışıdır (yəni, vahid qaydaya görə qurulmuş düsturlar, kanon).

Əgər məntiqi funksiya dəyişənlərin disjunksiya, birləşmə və inkar yolu ilə ifadə edilirsə, onda bu təmsil forması normal adlanır.

Normal formalar arasında mükəmməl normal formalar (funksiyaların özünəməxsus şəkildə yazıldığı formalar) seçilir.

Mükəmməl Disjunktiv Normal Forma (PDNF)

Tərif. Düstur müəyyən sayda dəyişənlərin və ya onların inkarlarının birləşməsindən əmələ gəlirsə, elementar birləşmə adlanır.

Nümunələr: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Tərif. Düstur təkrar olunmayan elementar birləşmələrin disyunksiyasıdırsa, ona disyunktiv normal forma (DNF) deyilir.

DNF aşağıdakı formada yazılır: F 1 ∨ F 2 ∨ ... ∨ F n , burada F i elementar bağlayıcıdır.

Nümunələr: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Tərif. K dəyişənlərində məntiqi düstur mükəmməl disyunktiv normal forma (PDNF) adlanır, əgər:
1) düstur DNF-dir, burada hər bir elementar birləşmə k x 1, x 2, ..., x k və on dəyişənlərin birləşməsidir. i-ci yer bu bağlayıcı ya x i dəyişənidir, ya da onun inkarıdır;
2) belə bir DNF-də bütün elementar birləşmələr cüt-cüt fərqlənir.

Misal: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Mükəmməl konyunktiv normal forma (SKNF)

Tərif. Düstur müəyyən sayda dəyişənlərin və ya onların inkarlarının diszyunksiyasından əmələ gəlirsə, elementar disjunksiya adlanır.

Nümunələr: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Tərif. Düstur təkrar olunmayan elementar disjunksiyaların birləşməsidirsə, konyunktiv normal forma (CNF) adlanır.

CNF aşağıdakı formada yazılır: F 1 ∧ F 2 ∧ ... ∧ F n , burada F i elementar disjunksiyadır.

Nümunələr: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Tərif. K dəyişənlərində məntiqi düstur mükəmməl konyunktiv normal forma (KDNF) adlanır, əgər:
1) düstur CNF-dir, burada hər bir elementar disjunksiya k dəyişənlərinin x 1 , x 2 , …, x k disjunksiyasıdır və bu disyunksiyanın i-ci yeri ya x i dəyişəni, ya da onun inkarıdır;
2) belə CNF-də bütün elementar disjunksiyalar cüt-cüt fərqlənir.

Misal: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

qeyd et ki Eyni şəkildə 0 və ya 1-ə bərabər olmayan istənilən məntiqi funksiya SDNF və ya SKNF kimi təqdim edilə bilər..

Həqiqət cədvəlinə əsasən SDNF-nin qurulması alqoritmi

1. Funksiya dəyərinin birinə bərabər olduğu cədvəlin bütün sətirlərini seçin.
2. Hər bir belə sətir üçün bütün dəyişənlərin birləşməsini aşağıdakı kimi yazın: əgər bu çoxluqda hansısa dəyişənin qiyməti 1-ə bərabərdirsə, onda biz dəyişənin özünü birləşməyə daxil edirik, əks halda isə onun inkarı.
3. Bütün yaranan bağlayıcıları ayırma əməliyyatları ilə əlaqələndiririk.

Həqiqət cədvəlinə əsasən SKNF-nin qurulması alqoritmi

1. Funksiya dəyərinin sıfıra bərabər olduğu cədvəlin bütün sətirlərini seçin.
2. Hər bir belə sıra üçün bütün dəyişənlərin diszyunksiyasını aşağıdakı kimi yazın: əgər bu çoxluqda hansısa dəyişənin qiyməti 0-dırsa, onda biz dəyişənin özünü konjonksiyaya daxil edirik, əks halda isə onun inkarı.
3. Alınan bütün disjunksiyaları birləşmə əməliyyatları ilə birləşdiririk.

Alqoritmlərin təhlili göstərir ki, əgər funksiyanın qiyməti həqiqət cədvəlinin əksər sətirlərində 0-a bərabərdirsə, onun məntiqi düsturunu almaq üçün SDNF, əks halda SKNF qurmaq daha yaxşıdır.

Misal: Üç ​​dəyişənin məntiqi funksiyasının həqiqət cədvəli verilmişdir. Bu funksiyanı həyata keçirən məntiqi düstur qurun.

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Çünki həqiqət cədvəlinin əksər sətirlərində funksiyanın qiyməti 1-ə bərabərdir, onda SKNF-ni qururuq. Nəticədə aşağıdakı məntiqi düsturu alırıq:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Nəticə formulunu yoxlayaq. Bunun üçün funksiyanın həqiqət cədvəlini qururuq.

x	y	z	x	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

Orijinal həqiqət cədvəlini və məntiqi düstur üçün qurulmuş cədvəli müqayisə edərək, funksiya dəyəri sütunlarının eyni olduğunu qeyd edirik. Bu, məntiqi funksiyanın düzgün qurulduğunu bildirir.

standart əsas. Elementar düsturlar hərfidir. Elementar bağlayıcı (dizyunksiya). Disjunktiv (konyunktiv) normal forma və mükəmməl forma. Teorem: 0-dan (1-dən) başqa istənilən Boolean funksiyası SDNF (SKNF) kimi təqdim edilə bilər. Standart bazanın tamlığı. Tam əsasların nümunələri: Zhegalkin əsası, Şeffer vuruşu, Pirs oxu.

Standart əsas üç ilkin Boole cəbri əməliyyatlarının toplusudur: toplama (birləşmə), vurma (kəsişmə) və inkar.

Burada zəng edəcəyik hərfi x dəyişəni və ya onun inkarı x və xˆ işarəsi verin. Müxtəlif dəyişənlərlə müəyyən edilmiş çoxlu literalların məntiqi kəsişməsi, yəni. X = xˆ 1 xˆ 2 formasının ifadəsi. . . xˆ l, adlanır elementar birləşmə . Bütün dəyişənlərin fərqli olması tələbi aşağıdakılarla bağlıdır. Əgər bağlayıcı bir neçə eyni hərfi ehtiva edirsə, onda birləşmənin kommutativliyinə, assosiativliyinə və idempotentliyinə görə ekvivalent düstura keçərək yalnız bir hərfi tərk edə bilərik (məsələn, x 1 x 1 = x 1). Əgər birləşmə dəyişəni və onun inkarını ehtiva edirsə, onda düstur 0 sabitinə ekvivalentdir, çünki x x = 0 və hər hansı Y düsturu üçün bizdə Y x x = 0 var.

Bir neçə elementar birləşmənin diszyunkasiyası deyilir disjunktiv normal forma , və ya DNF . Misal üçün,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

Əgər verilmiş DNF-nin hər elementar birləşməsində dəyişənlərin tərkibi eynidirsə, DNF adlanır. mükəmməl . Verilən nümunə mükəmməl olmayan bir DNF-dir. Əksinə, düstur

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

mükəmməl formasıdır.

Boolean cəbrində toplama və vurma simmetrik əməliyyatlar olduğundan və hər zaman toplamanı vurma, vurmağı isə toplama kimi şərh etmək olar, ikili anlayış da var - konyunktiv normal forma (KNF ), elementar ayırmaların bağlayıcısı olan və mükəmməl bağlayıcı forma (SKNF ). Simmetrik yarım halqalar üçün ikilik prinsipindən belə çıxır ki, DNF haqqında hər hansı müddəa CNF haqqında ikili müddəaya uyğun gəlir ki, bu da toplamanın (dizyunksiyanın) vurma ilə, vurmanın (konyunksiyanın) toplama ilə, sabit 0-ı sabit 1, sabit 1 ilə əvəz etməklə əldə edilir. sabit 0, münasibətləri ikili (tərs) sıra ilə sıralayın. Buna görə də, bundan sonra biz yalnız DNF-nin öyrənilməsinə diqqət yetirəcəyik.

Teorem 1.4. 0 sabitindən başqa istənilən Boolean funksiyası SDNF kimi təqdim edilə bilər.

◀X σ ilə razılaşaq, əgər σ = 1 olarsa x düsturu, σ = 0 olarsa x düsturunu nəzərdə tutaq. f(y 1 , . . . , y n) funksiyası (t 1) üzərində 1 qiymətini götürsün. , . . , t n ) (belə vektor deyilir tərkib vahidi ). Sonra elementar birləşmə də bu çoxluqda 1 qiymətini alır, lakin bütün digər n-ölçülü Boolean vektorlarında yox olur. Formulu nəzərdən keçirin

burada cəmi (birlik) verilmiş funksiyanın 1 qiymətini aldığı arqument dəyərlərinin bütün çoxluqlarına (t 1 , . . . . , t n) yayılır. Qeyd edək ki, belə çoxluqların çoxluğu boş deyil, belə ki, cəmi ən azı bir şərti ehtiva edir.

Φ düsturunun onlar üçün 1-ə çevrildiyini və yalnız nəzərdən keçirilən funksiyanın 1-ə çevrildiyi dəyişənlərin qiymətləri üçün görmək asandır. Deməli, Ψ düsturu f funksiyasını təmsil edir.

Nəticə 1.1. Standart baza tamamlandı.

◀ Həqiqətən, əgər funksiya 0 sabit deyilsə, o, ya standart əsas üzərində düstur olan SDNF kimi təqdim edilə bilər. 0 sabiti, məsələn, f(x 1 , x 2 , . . . , x n) = x 1 x 1 düsturu ilə təmsil oluna bilər.

Misal 1.2.Üç dəyişənli m(x 1 , x 2 , x 3) funksiyasını nəzərdən keçirək (Cədvəl 1.4), adlanan çoxluq funksiyası ̆. Arqumentlərinin yarısından çoxunun 1 dəyəri varsa, bu funksiya 1-ə bərabər qiymətləndirilir. Buna görə də ona çox vaxt səsvermə funksiyası deyilir. Bunun üçün bir SDNF quraq.

Standart bazanın tamlığı digər tam funksiya sistemlərini seçməyə imkan verir. F çoxluğunun tamlığı aşağıdakı mülahizələrdən müəyyən edilə bilər. Tutaq ki, üç standart buzz funksiyasının hər biri F üzərində bir düsturla təmsil olunur. Onda 1.3 teoreminə əsasən F-nin başqalığı tam olacaqdır.

Misal 1.3.Əməliyyatlar toplusuna modul 2 toplama, vurma və sabit 1 deyilir Jegalkin əsası . Modul 2 toplama və vurma Z2 halqasının əsas əməliyyatlarıdır, onların köməyi ilə qurulan ifadələr Z2 halqasının üzərində çoxhədlidir. Sərbəst üzvü yazmaq üçün bu halda sabit 1 lazımdır. xx \u003d x olduğundan, polinomdakı bütün amillər 1 dərəcəyə malikdir. Buna görə də, polinom yazarkən dərəcə anlayışı olmadan edə bilərsiniz. Zhegalkin əsasında düsturların nümunələri:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

İstənilən belə düstur Jeqalkin polinomu adlanır. Əslində, Zhegalkin polinomu Z2 halqası üzərində çoxhədlidir.

Standart bazanın əlavə və inkar əməliyyatlarını təmsil edən Zhegalkin əsasında düsturlar qurmaq asandır (iki bazanın vurulması ümumidir):

x+y=x⊕y⊕xy, x=x⊕1.

Buna görə də, Zhegalkin əsası tam dəstdir.
Göstərilə bilər ki, hər hansı Boolean funksiyası üçün Jeqalkin çoxhədli unikal şəkildə müəyyən edilir

(daha doğrusu, şərtlər sırasına qədər). Az sayda dəyişəni olan Jeqalkin polinomunun əmsallarını qeyri-müəyyən əmsallar üsulu ilə tapmaq olar.

Misal 1.4. Tək bir funksiya dəstini nəzərdən keçirək - Schaeffer vuruşunu*. Aşağıdakı asanlıqla təsdiqlənən şəxsiyyətlərdən irəli gələn bu dəst tamamlandı:

x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).

Misal 1.5. Tək funksiyadan ibarət olan əsas, Pirs oxu da tamamlandı. Bunun yoxlanılması Schaeffer insultunun vəziyyətinə bənzəyir. Bununla belə, bu nəticəni simmetrik yarım halqalar üçün ikilik prinsipi əsasında da çıxarmaq olar.

*Schaffer vuruşu ikili əməliyyatdır, lakin assosiativ deyil. Buna görə də, infiks formasından istifadə edərkən diqqətli olmalısınız: nəticə əməliyyatların yerinə yetirilmə ardıcıllığından asılıdır. Bu halda, mötərizələrdən istifadə edərək əməliyyatların ardıcıllığını açıq şəkildə göstərmək tövsiyə olunur, məsələn, (x | y) | z, x | deyil y | z, baxmayaraq ki, hər iki forma ekvivalentdir.

Təklif cəbrinin disyunktiv və konyunktiv normal formaları. Təklif məntiqinin hər bir funksiyası üçün həqiqət cədvəli tərtib edilə bilər. Tərs problem də həmişə həll edilə bilər. Bir neçə tərif təqdim edək.

Elementar bağlayıcılar (bağlayıcılar) hər bir dəyişənin ən çox baş verdiyi dəyişənlərin birləşmələri və ya onların inkarları adlanır

bir dəfə.

Disjunktiv normal forma(DNF) elementar birləşmələrin disjunksiya formasına malik olan düsturdur.

Elementar disjunksiyalar (bəndlərə görə) inkarlı və ya inkarsız dəyişənlərin disjunksiyaları adlanır.

Konyunktiv normal forma(CNF) elementar disjunksiyaların birləşmə formasına malik olan düsturdur.

Təklif cəbrinin hər bir funksiyası üçün disyunktiv və konyunktiv normal formalar toplusunu tapmaq olar.

DNF tikinti alqoritmi:

1. Ekvivalent çevrilmə düsturlarından istifadə edərək Boolean əməliyyatlarına keçin.

2. Yaxın neqativləri olan düsturlara, yəni neqativlərin dəyişənlərdən yuxarıda yerləşdiyi düstura keçin - de Morqan qanunlarını tətbiq edin.

3. Mötərizələri açın - paylanma qanunlarını tətbiq edin.

4. Bir dəfə almaq üçün təkrarlanan terminlər - idempotensiyanın qanunu.

5. Absorbsiya və yarımabsorbsiya qanunlarını tətbiq edin.

Misal 6 DNF düsturlarını tapın: .

Boole cəbrində, ikilik prinsipi. Bu aşağıdakı kimidir.

Funksiya çağırılır ikili funksiyasına əgər . Bunlar. verilmişə ikili funksiya tapmaq üçün arqumentlərin inkarlarından funksiyanın inkarını qurmaq lazımdır.

Misal 7-ə ikili funksiyanı tapın.

Məntiq cəbrinin elementar funksiyaları arasında 1-in 0-a ikili və əksinə, x-in ikili, x-in ikili, ikili və əksinədir.

Funksiyanı ifadə edən F 1 formulunda bütün bağlayıcılar əvəz olunur

disjunksiya üzrə, disjunksiya konyunksiya üzrə, 0-da 1, 0-da 1, onda * funksiyasını təmsil edən F * düsturu alırıq, dual .

Konyunktiv normal forma (CNF) DNF üçün ikili anlayışdır, ona görə də onu sxemə uyğun olaraq asanlıqla qurmaq olar:

Misal 8 CNF düsturlarını tapın: .

Nümunə 6-nın nəticəsini istifadə edərək, əldə etdik

Mükəmməl disjunktiv və mükəmməl konyunktiv normal formalar. Normal forma növlərinin hər birində (dizyunktiv və konyunktiv) SDNF və SKNF-nin mükəmməl formalarının bir sinfini ayırmaq olar.

Mükəmməl elementar birləşmə inkarlı və ya inkarsız bütün dəyişənlərin məntiqi hasilidir və hər bir dəyişən məhsula yalnız bir dəfə daxil edilir.

İstənilən DNF bütün dəyişənləri ehtiva etməyən bağlayıcıları bölmək yolu ilə SDNF-yə endirilə bilər, yəni. əskik dəyişən x i üçün əlavə paylanma qanunundan istifadə etməklə vurulur

Misal 9 DNF nümunəsi 6 üçün SDNF tapın

Mükəmməl elementar disjunksiya inkarlı və ya inkarsız bütün dəyişənlərin məntiqi cəmi deyilir, üstəlik, hər bir dəyişən cəmi bir dəfə daxil edilir.

İstənilən CNF, birləşmə yolu ilə heç bir X i dəyişəni olmayan birləşmə termini əlavə etməklə və distributiv qanunu tətbiq etməklə SKNF-ə endirilə bilər.

Misal 10. CNF-dən SKNF-ə çevirin:

SKNF qurmaq üçün sxemdən istifadə edə bilərsiniz

Misal 11. Nümunə 6-nın düsturu üçün SKNF tapın.

Hər bir funksiyanın bir SDNF var və üstəlik, yeganə . Hər bir funksiyanın bir SKNF və üstəlik, bir .

Çünki SDNF və SKNF düsturlarla unikal şəkildə müəyyən edilir, onlar düsturun həqiqət cədvəlinə uyğun olaraq qurula bilər.

SDNF qurmaq üçün F-nin 1 qiymətini aldığı sətirləri seçmək və onlar üçün mükəmməl elementar birləşmələri yazmaq lazımdır. Əgər həqiqət cədvəlinin arzu olunan cərgəsində dəyişənin qiyməti birə bərabərdirsə, mükəmməl konyunksiyada inkarsız, sıfırdırsa, inkarla qəbul edilir. Sonra mükəmməl bağlayıcılar (onların sayı cədvəldəki vahidlərin sayına bərabərdir) ayırma işarələri ilə bağlanır.

SKNF-ni həqiqət cədvəlinə əsasən qurmaq üçün orada F=0 olan sətirləri seçmək və mükəmməl elementar disjunksiyaları yazmaq, sonra isə onları bağlayıcı işarələrlə birləşdirmək lazımdır. Əgər həqiqət cədvəlinin tələb olunan sətirində (F=0) dəyişənin qiyməti sıfıra uyğundursa, mükəmməl disyunktda inkarsız, birə bərabərdirsə, inkarla qəbul edilir.

Misal 12. 6-cı misalın düsturu üçün həqiqət cədvəlinə əsasən SDNF və SKNF-ni tapın.

Cədvəl 14 yalnız F=10101101 son qiymətini göstərir. Bu ifadənin etibarlılığı genişləndirilmiş həqiqət cədvəli qurmaqla müstəqil olaraq yoxlanılmalıdır.

Cədvəl 14

x	y	z

Sadə bağlayıcı çağırdı bağlayıcı bir və ya bir neçə dəyişənlər, saat bu hər biri dəyişən görüşür yox daha çox bir dəfə (və ya özü, və ya onun inkar).

Məsələn, sadə birləşmədir,

disjunktiv normal forma(DNF) çağırdı disjunksiya sadə bağlayıcılar.

Məsələn, ifadə DNF-dir.

Mükəmməl disjunktiv normal forma(SDNF) çağırdı bu cür disjunktiv normal forma, saat hansı in hər bağlayıcı daxildir hamısı dəyişənlər verilmişdir siyahı (və ya özləri, və ya onlar inkar), və in bir və həcm eynitamam.

Məsələn, ifadə DNF-dir, lakin SDNF deyil. İfadə SDNF-dir.

Oxşar təriflər (dizyunksiya üçün birləşmənin əvəz edilməsi və əksinə) CNF və SKNF üçün də doğrudur. Dəqiq formulaları təqdim edirik.

Sadə disjunksiya çağırdı disjunksiya bir və ya bir neçə dəyişənlər, saat bu hər biri dəyişən daxildir yox daha çox bir dəfə (və ya özü, və ya onun inkar Məsələn, ifadə sadə diszyunksiyadır,

Konyunktiva normal forma(KNF) çağırdı bağlayıcı sadə disjunksiyalar(məsələn, ifadə - CNF).

Mükəmməl konyunktiv normal forma (CKNF) hər bir sadə disyunksiya verilmiş siyahının bütün dəyişənlərini (ya özləri, ya da onların inkarları) və eyni ardıcıllıqla ehtiva edən CNF-dir.

Məsələn, ifadə SKNF-dir.

Bir formadan digərinə keçid alqoritmlərini təqdim edirik. Təbii ki, konkret hallarda (müəyyən yaradıcı yanaşma ilə) alqoritmlərin istifadəsi verilmiş formanın xüsusi formasını istifadə edən sadə çevrilmələrdən daha zəhmətli ola bilər:

a) DNF-dən CNF-ə keçid

Bu keçidin alqoritmi belədir: biz DNF-nin üzərinə iki inkar qoyuruq və de Morqanın qaydalarından istifadə etməklə (yuxarı inkara toxunmadan) DNF-nin inkarını yenidən DNF-yə gətiririk. Bu halda, udma qaydasından (və ya Bleyk qaydasından) istifadə edərək mötərizələri açmalısınız. Yaranan DNF-nin (yuxarı) inkarı (yenə de Morqanın qaydası ilə) bizə dərhal CNF verir:

Qeyd edək ki, CNF çıxarsaq orijinal ifadədən də əldə edilə bilər saat mötərizələr üçün;

b) CNF-dən DNF-ə keçid

Bu keçid sadəcə mötərizələri açmaqla həyata keçirilir (bu vəziyyətdə yenə udma qaydası istifadə olunur)

Beləliklə, DNF əldə etdik.

Əks keçid (SDNF-dən DNF-ə) DNF-nin minimuma endirilməsi problemi ilə bağlıdır. Bu, təriqətdə daha ətraflı müzakirə olunacaq. 5-də biz Bleyk qaydasına uyğun olaraq DNF-nin (və ya SDNF) necə sadələşdirilməsini göstəririk. Belə bir DNF deyilir qısaldılmış DNF;

c) DNF (və ya SDNF) abbreviaturası ilə qayda Bleyk

Bu qaydanın tətbiqi iki hissədən ibarətdir:

DNF-də ayrı-ayrı terminlər arasında terminlər varsa , sonra termini bütün disjunksiyaya əlavə edirik üçün 1 üçün 2. Bu əməliyyatı bir neçə dəfə (ardıcıl olaraq mümkündür, eyni vaxtda mümkündür) bütün mümkün cüt şərtlər üçün yerinə yetiririk və sonra adi absorbsiyanı tətbiq edirik;

Əlavə edilmiş termin artıq DNF-də var idisə, o, tamamilə ləğv edilə bilər, məsələn,

və ya

Əlbəttə ki, qısaldılmış DNF unikal şəkildə müəyyən edilmir, lakin onların hamısı eyni sayda hərfləri ehtiva edir (məsələn, DNF var. , ona Bleyk qaydasını tətbiq etdikdən sonra verilənə ekvivalent bir DNF əldə etmək olar):

c) DNF-dən SDNF-ə keçid

Bəzi sadə birləşmədə dəyişən yoxdursa, məsələn, z, ifadəni içinə daxil edin, bundan sonra mötərizələri açırıq (təkrarlanan disjunct şərtlərini yazmırıq). Misal üçün:

d) CNF-dən SKNF-ə keçid

Bu keçid əvvəlkinə bənzər şəkildə həyata keçirilir: sadə disjunksiyada hansısa dəyişən yoxdursa (məsələn, z, sonra ona bir ifadə əlavə edirik (bu, disjunksiyanın özünü dəyişmir), bundan sonra paylama qanunundan istifadə edərək mötərizələri açırıq):

Beləliklə, SKNF CNF-dən əldə edilir.

Qeyd edək ki, minimum və ya qısaldılmış CNF adətən müvafiq DNF-dən alınır.