Bul funksiyaları çoxluğunun (sisteminin) qapanması. Bul funksiyalarının qapalı sistemi

1)
;
2)	;
3)	;
4)	;
5)	;
6)	;
7)	;
8)	;
9)	;
10)	.

Verilmış funksiyasının , çoxluqla­rından hansına daxil olduğunu təyin edin.

1)	;
2)	;
3)	;
4)	;
5)	;
6)	;
7)	;
8)	;
9)	;
10)	.

Verilmış funksiyasının çoxluğuna daxil olub-olmadığını göstərin.

1)	;
2)	;
3)	;
4)	;
5)	;
6)	;
7)	;
8)	;
9)	;
10)	.

Aşağıdakı funksiyalardan hansı monotondur?

1)	;
2)	;
3)	;
4)	;
5)	;
6)	;
7)	;
8)	;
9)	;
10)	.

Aşağıdakı funksiyalardan hansı xəttidir?

1)	;
2)	;
3)	;
4)	;
5)	;
6)	;
7)	;
8)	;
9)	;
10)	;
11)	;
12)	;
13)	;
14)	;
15)	;
16)	;
17)	;
18)	;
19)	;
20)	.

13. Bul funksiyalarının dolu (tam) sistemi. Bazis bul funksiyaları sistemi
13.1. Bul funksiyalarının dolu (tam) sistemi. Məntiq cəbrinin əsas teoremi
Tutaq ki, bul funksiyalarının hər hansı sistemi verlir.

Tərif 13.1.  Əgər istənilən bul funksiyası sisteminin , , funksiyaları vasitəsilə müəyyən bir düstur şəklində göstərilə bilirsə, onda bul funksiyaları sistemi funksional dolu (tam) sistem adlanır.

Tərif 13.2.  Əgər -dirsə və olarsa, onda sistemi funksional dolu sistem adlanır.

Məsələn, sistemi funksional dolu (tam) sistemdir, çünki istənilən bul funksiyasını inkar, konyunksiya və dizyunksiya funksiyalarının iştirak etdiyi mükəmməl DNF və mükəmməl KNF şəklində göstərə bilərik.

Hər hansı bul funksiyasının funksional dolu olub-olmamasını müəyyən edən belə bir köməkçi təklif vardır.

Teorem 13.1. (köməkçi təklif). Tutaq ki, iki

(13.1)

və

(13.2)

sistemləri verilir. Əgər (13.1) dolu sistemdirsə və onun hər bir funksiyası (13.2) sisteminin funksiyaları vasitəsilə

(13.3)

düsturu şəklində göstərilə bilirsə, onda (13.2) sistemi də funksional dolu sistemdir.

Misal 13.1. , sistemləri do­lu­­dur, çünki sistemi dolu­­dur və de Morqan qaydasına görə və .

Misal 13.2. sistemi do­lu­­dur, çünki götürsək, bu sistemin hər bir funksiyası Seffer ştrixi ilə ifadə olunur:

və .

Misal 13.3. sistemi do­lu­­dur, çünki sistemi do­lu­­dur və

, .

Əsas teorem (Post E). Bul funksiyalarının

sisteminin funksional tam (dolu) olması üçün zəruri və kafi şərt bu sistemin beş mühüm qapalı ,  ,  ,  ,  sistemlərindən heç birinə tama­milə daxil olmamasıdır.

Qeyd. Bul funksiyaları sistemi verilirsə, onda bu sistemin dolu olub-olmamasını Post cədvəli ilə təyin etmək olur. Bunun üçün cədvəlin sütunlarının adları Post sinifləri ,  ,  ,  ,  ilə adlanır, sətirlərin adları isə verilən sisteminin funksiyaları olur. Sətir və sütunun kəsişdiyı xanada sisteminin funksiyası qapalı ,  , , , siniflərindən birinə daxildirsə, onda  işarəsi yazılır, əks halda  işarəsi yazılır. Post teoreminə görə sistemin dolu olması üçün zəruri və kafi şərt hər bir sütunda ən azı bir  işarəsi olmalıdır.

Misal 13.4. sisteminin dolu olub-olma­masını Post cədvəli ilə yoxlayın.

Həlli.

					
					
1					

Cədvəldən göründüyü kimi, sistemi dolu sistemdir, çünki hər bir sütunda  işarəsi vardır, yəni qapalı siniflərin ixtiyari birisinə tamamilə daxil deyildir.

Post teoremini aşağıdakı teoremlər şəklində də vermək olar.

Post teoremi (güclü). Bul funksiyalarının funksi­onal dolu olması üçün zəruri və kafi şərt bu sistemdə qapalı beş , , , və siniflərindən heç birinə daxil olmayan bir funksiyanın olmasıdır.

Post teoremi (zəif). Məntiqi 0 və 1 sabitlərinin daxil olduğu bul funksiyaları sisteminin dolu olması üçün zəruri və kafi şərt bu sistemdə heç olmazsa bir xətti və monoton olmayan funksiyanın olmasıdır.
13.2. Bazis bul funksiyaları sistemi. Asılı

olma­yan bul funksiyaları sistemi

Tərif 13.3.  Əgər sisteminin ixtiyari bir , , funksiyası yerdə qalan , funksiyalarının superpozisiyaları kimi göstərilə bilmirsə, onda sistemi asılıolma­yan bul funksiyaları sistemi adlanır.

Misal 13.5. sistemi asılı funksiyalar sistemdir, çünki və ya .

Misal 13.6. , sistemləri asılı ­olma­yan sistemlərdir, çünki nə , nə də  funksiyaları tək inkar funksiyası ilə düstur kimi göstərilmir.

Misal 13.7. sistemi asılı sistemdir, çünki . Əlavə qeyd edək ki, , , , , , , , , , , .

Tutaq ki, müəyyən qapalı sinifdir.

Tərif 13.4.  Əgər çoxluğunun istənilən məxsusi altçoxluğunun qapanması şərtini ödəyirsə, yəni , onda funksiyalar çoxluğu gətirilə bilməyən (sadələşməyən) adlanır.

Tərif 13.5.  Əgər sistemi dolu­dursa və bu sistemdən hər hansı bir funksiyasını atdıqda sistemi dolu olmazsa, onda bu sistem bazis adlanır.

Deməli, bazis asılı ­olma­yan funksiyaların dolu sistemidir.

Tərif 13.6.  Əgər sinifinin hər bir funksiyası asılı ­olma­yan funksiyalar sisteminin funksiyalarının superpozisiyası şəklində göstərilə bilər­sə, onda sistemi sinifinin bazisi adlanır.

Teorem 13.2. Hər bir bazis olan sistem dörd bul funksiyasından çox deyildir.