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ışdır 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.

Elementar disjunksiya anlayışını təqdim edək.

Elementar disjunksiya formanın ifadəsidir

Məntiqi funksiyanın konyunktiv normal forması (CNF) cüt-cüt fərqli elementar disjunksiyaların hər hansı sonlu çoxluğunun birləşməsidir. Məsələn, məntiqi funksiyalar

elementar disjunksiyaların birləşmələridir. Buna görə də onlar konyunktiv normal formada yazılır.

Analitik ifadə ilə verilən ixtiyari məntiqi funksiyanı aşağıdakı əməliyyatları yerinə yetirməklə CNF-ə endirmək olar:

Məntiqi ifadəyə inkar əməliyyatı tətbiq edilərsə, inversiya qaydasından istifadə;

Bölmə aksiomunun vurma ilə bağlı istifadəsi:

Absorbsiya əməliyyatından istifadə:

Təkrarlanan dəyişənlərin disjunksiyalarında və ya onların inkarlarında istisnalar;

Bir istisna olmaqla, bütün eyni elementar disjunksiyaların aradan qaldırılması;

Eyni zamanda dəyişəni və onun inkarını daxil edən bütün disjunksiyaların silinməsi.

Sadalanan əməliyyatların etibarlılığı məntiq cəbrinin əsas aksiomlarından və eynilik əlaqələrindən irəli gəlir.

Konyunktiv normal forma o zaman mükəmməl adlanır ki, ona daxil olan hər bir elementar disjunksiya birbaşa və ya tərs formada funksiyanın asılı olduğu bütün dəyişənləri ehtiva edir.

CNF-nin mükəmməl CNF-ə çevrilməsi aşağıdakı əməliyyatları yerinə yetirməklə həyata keçirilir:

Dəyişənlərin bağlayıcılarının hər bir elementar diszyunksiyasına əlavələr və bu elementar diszyunsiyaya daxil deyilsə, onların inkarları;

Paylanma aksiomundan istifadə;

Bir istisna olmaqla, bütün eyni elementar disjunksiyaların çıxarılması.

İstənilən məntiqi funksiya istisna olmaqla mükəmməl CNF-də təmsil oluna bilər

eyni şəkildə birinə () bərabərdir. Mükəmməl CNF-nin fərqləndirici xüsusiyyəti ondadır ki, məntiqi funksiyanın orada təsviri unikaldır.

Mükəmməl CNF funksiyasına daxil olan elementar disjunksiyalar sıfır tərkib hissəsi adlanır. Mükəmməl CNF-də hər bir sıfır komponent funksiyanın sıfır dəsti olan dəyişən dəyərlərinin yeganə dəstində yox olur. Nəticə etibarilə, məntiqi funksiyanın sıfır dəstlərinin sayı onun mükəmməl CNF-ə daxil olan sıfır tərkib hissələrinin sayı ilə üst-üstə düşür.

Mükəmməl CNF-də sıfır sabiti məntiqi funksiyası sıfırın tərkib hissəsi olan 2n birləşməsi ilə təmsil olunur. Uyğunluq cədvəlinə uyğun olaraq məntiqi funksiyanın SKNF-ni tərtib etmək qaydasını tərtib edək.

Funksiyasının sıfıra bərabər olduğu uyğunluq cədvəlinin hər sətri üçün bütün dəyişənlərin elementar diszyunsiyası tərtib edilir. Dəyəri sıfıra bərabərdirsə, disjunksiya dəyişənin özünü və ya dəyəri birə bərabərdirsə, inkarı ehtiva edir. Yaranan elementar diszyunksiyalar bağlayıcı işarə ilə birləşir.

Misal 3.4. Axtarış cədvəli 2.2 ilə verilmiş z(x) məntiqi funksiyası üçün mükəmməl konyunktiv formanı təyin edirik.

Sıfır funksiya dəstinə 000 uyğun gələn cədvəlin birinci sırası üçün null komponentini tapırıq. İkinci, üçüncü və beşinci sıralar üçün oxşar əməliyyatları yerinə yetirərək, istədiyiniz mükəmməl CNF funksiyasını təyin edirik:

Qeyd etmək lazımdır ki, vahid çoxluqların sayı sıfır çoxluqların sayından çox olan funksiyalar üçün onları SKNF şəklində və əksinə yazmaq daha yığcamdır.

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, unikal şə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ə tələb 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) ;

Sadə disjunksiya(ing. inclusive disjunction) və ya disyunktom(İngilis dili disjunktı) bir və ya bir neçə dəyişənin və ya onların inkarlarının diszyunksiyası adlanır və hər dəyişən bir dəfədən çox baş vermir.

Sadə disjunksiya

• tam, əgər hər bir dəyişən (və ya onun inkarı) ona tam olaraq bir dəfə daxil olarsa;
• monoton, onda dəyişənlərin inkarları yoxdursa.

Konyunktiv normal forma, CNF(İngiliscə konjunktiv normal forma, CNF) Boolean funksiyasının bir neçə sadə bənddən ibarət birləşmə formasına malik olduğu normal formadır.

CNF nümunəsi:$f(x,y) = (x \lor y) \torpaq (y \lor \neg ( z ))$

SKNF

Mükəmməl konyunktiv normal forma, SKNF(İngilis dili mükəmməl konyunktiv normal forma, PCNF) şərtləri ödəyən CNF-dir:

• onun eyni sadə disjunksiyaları yoxdur
• hər sadə ayırma tamamlandı

SKNF nümunəsi:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z ))$

Teorem: Eyni vahidə bərabər olmayan hər hansı $f(\vec ( x ))$ Boolean funksiyası üçün onu müəyyən edən SKNF var.

Sübut:$\neg ( f ) (\vec x)$ funksiyasının tərsi $f(\vec x)$-nın sıfıra bərabər olduğu çubuqlarda birinə bərabər olduğundan, $\neg ( f ) üçün SDNF (\vec x)$ bunu belə yaza bilər:

$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n) ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \paz x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \paz ... \paz x_ ( n ) ^ ( \sigma_ ( n) ) )) $, burada $ \sigma_ ( i ) $ $ x_ ( i ) $-da inkarın varlığını və ya olmamasını bildirir

İfadənin sol və sağ tərəflərinin inversiyasını tapın:

$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n) ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \paz x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \paz ... \paz x_ ( n ) ^ ( \sigma_ ( n) ))) ))) $

Sağ tərəfdə alınan ifadəyə de Morqan qaydasını iki dəfə tətbiq edərək, əldə edirik: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots , x^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \nöqtələr \vee \neg ( x_n^ ( \sigma_n ) )) $

Son ifadə SKNF-dir. SKNF eyni sıfır olmayan istənilən funksiya üçün qurula bilən SDNF-dən alındığı üçün teorem isbat edilir.

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

• Həqiqət cədvəlində funksiyanın dəyəri $0$-a bərabər olan dəyişənlər dəstini qeyd edirik.
• Hər bir işarələnmiş çoxluq üçün bütün dəyişənlərin diszyunksiyasını aşağıdakı qaydaya uyğun olaraq yazırıq: əgər hansısa dəyişənin qiyməti $0$-dırsa, onda dəyişənin özünü disjunksiyaya daxil edirik, əks halda isə onun inkarı.
• Alınan bütün disjunksiyaları birləşmə əməliyyatları ilə birləşdiririk.

Median üçün SKNF-nin qurulmasına bir nümunə

bir). Həqiqət cədvəlində funksiyanın dəyəri $0$-a bərabər olan dəyişənlər dəstini qeyd edirik.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). Hər bir işarələnmiş çoxluq üçün bütün dəyişənlərin birləşməsini aşağıdakı qaydaya uyğun olaraq yazırıq: əgər hansısa dəyişənin qiyməti $0$-dırsa, onda biz dəyişənin özünü disjunksiyaya, əks halda isə inkarına daxil edirik.

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0	$(x \lor y \lor z)$
0	0	1	0	$(x \lor y \lor \neg ( z ))$
0	1	0	0	$(x \lor \neg ( y ) \lor z)$
0	1	1	1
1	0	0	0	$(\neg ( x ) \lor y \lor z)$
1	0	1	1
1	1	0	1
1	1	1	1

3). Alınan bütün disjunksiyaları birləşmə əməliyyatları ilə birləşdiririk.

$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg ( x ) \lor y \lor z) \land (x \lor \neg ( y ) \lor z) \torpaq (x \lor y \lor \neg ( z ))$

Bəzi funksiyalar üçün SKNF nümunələri

Pirs oxu: $ x \downarrow y = (\neg ( x ) \lor ( y )) \land (( x ) \lor \neg ( y )) \land (\neg ( x ) \lor \neg ( y ) ) $

Eksklüziv və ya: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$

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 prime işinə 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.