I-bob. Asosiy qism

O‘nlik sonlar
Ikkilik son
8	4	2	1
0	0	0	0	0
1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1

12	1	1	0	0
13	1	1	0	1
14	1	1	1	0
15	1	1	1	1

15 soni quyidagi yig‘indi ko‘rinishda ifodalanadi: 15=8+4+2+1=2³+2²+2¹+2⁰ ,

shuning uchun ikkilik ekvivalentnig barcha razryadlarida “1” turibdi, ya’ni o‘nlik 15 soni ikkilik hisob tizimida 1111 son bilan ifodalanadi.
Ikkilik sonni o‘nlikka o‘zgartirish uchun pozitsiyalarida “1” turgan salmog‘lar yig‘indisi topilish kerak. Masalan, 0111 o‘nlik sanoq tizimida 4+2+1=7 teng.
Inkor funksiyasi Ϝ(x)= x eng oddiy ko‘rinishga ega 1.2 jadval.

2. 
   jadval
   

x	F
0	1
1	0

Bu erda x argumentning qiymati “1” haqiqat bo‘lsa, undu funksiya F yolg‘on “0” bo‘ladi.

^{Ikki o‘zgaruvchanlarning m}antiqiy qo‘shish funksiyasi (diz’yunksiya)
^{F (x1, x2 ) = x1 + x2} 1.3 jadvalda keltirilgan.

3. 
   jadval.
   

^x1	^x2	F
0	0	0
0	1	1
1	0	1
1	1	1

Diz’yunksiya funksiyasi haqiqiydir, agar argumentlarning birontasi haqiqiy bo‘lsa.
Ikki o‘zgaruvchanlarning mantiqiy ko‘paytirish (kon’yuksiya) funksiyasi

F (x₁, x₂ ) = x₁

jadval 1.4. da keltirilgan.

3. 
   jadval.
   

x1	x2	F
0	0	0
0	1	0
1	0	0
1	1	1

Kon’yuksiya operatsiyasi natijasida yangi murakkab mulohaza haqiqiydir agar tashkil etuvchi barcha o‘zgaruvchanlar haqiqiy “1” bo‘lsa. Barcha boshqa holarda esa yolg‘on “0” qiymatga egadir.

Har qanday funksiya uchun naborlarning to‘liq soni 2ⁿ ( bu erda n – o‘zgaruvchanlarning soni) teng, 2ⁿ esa – funksiyalarning maksimal soni. SHunday qilib, ikki o‘zgaruvchanlar funksiyasi uchun naborlarning to‘liq soni 2² =4 teng, funksiya 2⁴ = 16 teng, ya’ni ikki o‘zgaruvchanlar uchun 16 turli funksiyalar berilishi mumkin. n =3 teng bo‘lganida naborlar soni 2³ =8 teng, funksiyalar soni esa 2⁶= 32, n =4 teng bo‘lganida naborlar soni 2⁴ =16, funksiyalar soni 2⁸=256 teng, va h.k.
Uchta o‘zgaruvchanlar uchun 1.5. jadvalda ixtiyoriy ko‘rinishdagi F funksiya berilgan. Haqiqiylik jadvalini tuzish tartibi quyidagicha: Mantiqiy funksiyaning haqiqiylik jadvali o‘zgaruvchanlarning kombinatsiyasi ikkilik son 000 lardan iborat bo‘lgan nollik nabordan boshlanadi. Keyingi nabor (birinchi) esa (o‘nlik sanok tizimidagi 1 sonning ekvivalenti) 001 ikkilik sondan, ya’ni x₃ =0, x₂
=0, x₁ =1, ikkinchi nabor – ikkilik son 010 (o‘nlik sanoq tizimidagi 2 ekvivalenti) va h.k. 1.5.jadvalning oxirgi satri 111 larga teng bo‘lgan x₃, x₂, x₁ to‘plami (nabori)dan iborat bo‘lib o‘nlik sanoq tizimida 7 sonning ekvivalentidir. Xuddi shu

tartibda har qanday mantiqiy funksiyani haqiqiylik jadvalini tuzish mumkin. Jadvalning o‘ng ustunida F funksiyaning qiymatlari yoziladi.
1.5.jadval.

to‘plam nomeri	x3	x2	x1	F
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

Funksiyani jadval usulidagi ko‘rinishidan algebraikka o‘tish oson. Bunday shaklda mantiqiy funksiyani miniumlashtirish maqsadida turli o‘zgartirishlar engil amalga oshiriladi. Algebraik ko‘rinishdagi bul funksiyalari ikkita shaklga ega: mukammal diz’yunktiv normal shakl (MDNSH) va mukammal kon’yunktiv normal shakl (MKNSH).

Bul funksiyalarini MDNSH ko‘rinishda tasavvur etish uchun minterma tushunchasi bilan tanishish kerak bo‘ladi. Minterma deb, inversi yoki u siz olingan har qanday o‘zgaruvchanlarning ko‘paytmasini tashkil etuvchi har qanday mantiqiy kombinatsiya nomlanadi. Masalan, ikki o‘zgaruvchanli funksiya uchun 4ta minterma yozish mumkin:

- -
^{mo = x}2 ^{× x1} _,
-
^{m1 = x}2 ^{× x1}
-
_, ^{m2 = x}2 ^{× x1} _,
^{mo = x}2 ^{× x1} _.

Uchta o‘zgaruvchan uchun 8 ta minterma yozish mumkin.
Shunday qilib, ushbu mantiqiy funksiyani mintermalarining maksimal soni uning to‘plammga bog‘liq. Jadval ko‘rinishida berilgan har qanday mantiqiy funksiyaning to‘plamini (nabor) minterma ko‘rinishida inversiyasiz agar 1 teng

bo‘lsa va inversiyali agar u 0 teng bo‘lsa yozilishi mumkin. Mintrema indeksi jadval dagi to‘plam nomeridir. 1.5. jadvalga qaytib berilgan F funksiya uchun
- - - - - - -
m = x × x × x m = x × x × x m = x × x × x

barcha mintermalarni yozamiz:
^{o 3} 2 ¹ _, 1 ³ 2 ¹ _, 2 ³ 2 ¹ _,

^- - - - ^-

3 ³ 2 ¹ _,

7 ³ 2 ¹ _.
^{m = x × x × x} m₄ = x₃ × x₂× x_{1 ,} m₅ = x₃ × x₂× x_{1 ,} ^m₆ ^{= x}₃ ^{× x}₂ ^{× x1} _,
m = x × x × x

Mantiqiy funksiyani MDNSHda tasavvur etish uchun quyidagi amalarni bajarish kerak:

1. 
   Haqiqiylik jadvalidan F=1 bo‘lgan mintermalarni yozib olish.
   
2. 
   Yozib olingan mintermalarni diz’yunksiya operatsiyasi bilan birlashtirish natijasini F ga tenglashtirish.
   

1.5. jadvaldan ko‘rinib turibdiki 3,5,6,7 to‘plamlariga quyidagi mintermalar to‘g‘ri keladi:

-

3 ³ 2 ¹ _,
m = x × x × x
-

5 ³ 2 ¹ _,
m = x × x × x
-

m = x × x × x
6 ³ 2 ¹ _,
m = x × x × x

7 ³ 2 ¹ _.
Ushbu funksiya uchun MDNSH quyidagicha yoziladi: F= m₃ +m₅ + m₆ + m₇ yoki
- - -

F(x x x ) = x × x × x + x × x × x + x × x × x + x
× x × x

3 2 1
³ 2 ^1
3 2 ^1
3 2 ^1
3 2 ¹

Funksiyani MDNSH ko‘rinishda yozish jarayoni birlar bo‘yicha strukturaviy formulani tuzish deb ham nomlanadi.
MKNSH shakli maksetrma tushunchasi bilan bog‘liq. Maksetrma deb inversiyali yoki u siz olingan barcha o‘zgaruchanlarni mantiqiy qo‘shish bilan olingan har qanday diz’yunksiya nomlanadi.
Ikkita o‘zgaruvchanli mantiqiy funksiya uchun maksterma quyidagicha yoziladi:

M₀ = x₂ + x_{1 ,}


^{M1 = x2 + x}1 _,
-
^{M 2 = x}2 ^{+ x1} _,
- -
^{M3 = x}2 ^{+ x}1

Uchta o‘zgaruvchanli mantiqiy funksiya uchun makstermalar soni 8 teng:

M ₀ = x₃ + x₂ + x_{1 ,}


M₁ = x₃ + x₂ + x_{1 ,}

-
M ₂ = x₃ + x₂ + x_{1 ,}

- -
M₃ = x₃ + x₂ + x_{1 ,}

-
M ₄ =