1. Mantiqiy funksiyalarni berilish usullari. Bul algebrasining asoslari. Mantiqiy elementlar

A (B + C) = (A B) + (A C)

A + (B C) = (A + B) (A + C)

Duallik qonuni (de-Morgan teoremasi)
Yutish qonuni	A + A B = A A (A + B) = A

2.2 jadvaldagi aksioma va qonunlarni tatbiq etish mantiqiy funksiyalarni soddalashtirishni amalga oshirishga imkon beradi, yaʻni ular uchun eng sodda kо‘rinishdagi ifodalarni topishga imkon beradi. Masalan,

1) ;

2) .

Assotsiativlik qonunini ishlatish orqali har qanday kо‘p о‘zgaruvchili (K ) mantiqiy funksiyani ikki о‘zgaruvchi funksiya kо‘rinishida ifodalash mumkin.

Ikki о‘zgaruvchili 2² = 16 mantiqiy funksiyalarning tо‘liq tо‘plami 2.3 jadvalda berilgan.

2.3 jadval

A	0	0	1	1	Shartli belgilanishi va algebraik ifodasi	Funksiyaning nomi
V	0	1	0	1
F0	0	0	0	0	F0= 0	Doim 0
F1	0	0	0	1	F1 = AB	Konyunksiya
F2	0	0	1	0		Taqiq
F3	0	0	1	1	F3 = A	A Aynan bir xil
F4	0	1	0	0		Taqiq
F5	0	1	0	1	F5 = B	V Aynan bir xil
F6	0	1	1	0		Faqat YOKI
F7	0	1	1	1	F7 = A + B	Dezyunksiya
F8	1	0	0	0		Pirs strelkasi (YOKI-YО‘Q)
F9	1	0	0	1		Tenglik (ekvivalentlik)
F10	1	0	1	0	F10 =	V teskarisi
F11	1	0	1	1	F11 = B A = A +	V dan A ga implekatsiya
F12	1	1	0	0	F12 =	A teskarisi
F13	1	1	0	1	F13 = A B = + B	A dan V ga implekatsiya
F14	1	1	1	0	F14 = A/B =	Sheffer shtrixi (VA-YО‘Q)
F15	1	1	1	1	F15 = 1	Doimiy 1

2.3 jadvalga tatbiqan har bir funksiya A va V ikki о‘zgaruvchi ustidagi mumkun bо‘lgan 16 tadan bitta mantiqiy operatsiyani belgilaydi va о‘zining nomiga ega hamda shartli belgilanishi mavjud.

Masalan “Faqat YOKI” ikki о‘zgaruvchining teng emaslik signali ishlab chiqariladi: A B bо‘lganda F₆=1 ; A = V bо‘lganda F₆ = 0. 1.3 jadvalda ancha murakkab funksiyalar uchun – taqiq, ekvivalentlik, implikatsiya va boshqalar. – ularni inkor etish, dezyunksiya, konyunksiya operatsiyalari yordamida ifodalanishlari berilgan.

Mantiqiy funksiyalarni ifodalanishi quyidagilarga bо‘linadi: sо‘z bilan, jadvalliy, algebraik, grafik. Masalan, F₉ = f (A, B) funksiyani sо‘z bilan bayoni quyidagicha F₉ = 1 bо‘ladi A = B va F₉ = 0 bо‘lganda , qachonki A B bо‘lsa, chinlik jadvali kо‘rinishida ham ifodalash mumkin (1.4 jadval) yoki algebraik shaklda (1.3 jadvalga qaralsin). Chinlik jadvali barcha 2^K bо‘lishi mumkun bо‘lgan mantiqiy о‘zgaruvchilarning qiymatlar tо‘plami va funksiya qiymatini о‘z ichiga oladi.

2.4 jadval

A	V	F9
0	0	1
0	1	0
1	0	0
1	1	1

Funksiyani jadval kо‘rinishidan ifodalanishidan algebraik kо‘rinishga о‘tish uchun о‘zgaruvchilarning har bir tо‘plamiga minitermga mos (m_i) (birning konstituentasi) о‘zgaruvchilar konyunksiyasi qо‘yiladi, ular agarda ushbu о‘zgaruvchining qiymati tо‘plamda 1 ga teng bо‘lsa, yoki teskari kо‘rinishda, agarda о‘zgaruvchining qiymati 0 ga teng bо‘lsa. K о‘zgaruvchi uchun g = 2^K minitermlar tuziladi: m₀ , m₁ , m _{g – 1}. 2.5 jadvalda ikki о‘zgaruvchili barcha minitermlar keltirilgan. Ushbu i - chi о‘zgaruvchilar tо‘plamiga mos keluvchi F funksiyaning qiymatini f_i kabi belgilab olamiz.

Demak, F₉ funksiyaning algebraik ifodalanishi minitermlar yig‘indisi kabidir, о‘zgaruvchilar tо‘plamiga mos bо‘lgan, ular uchun f_i = 1:

F₉ = f₀ m₀ + f₁ m₁ + f₂ m₂ + f₃ m₃ = 1 ( ) + 0 ( ) + 0 ( ) + (AB) = + AB.
Umumiy holda har qanday mantiqiy funksiyaning algebraik ifodasini quyidagi kо‘rinishda ifodalash mumkin

bu yerda f_i , m₀ – funksiyaning (0 yoki 1) va minitermning qiymati, i – chi о‘zgaruvchi tо‘plamiga mos keluvchi.

2.5 jadval

A	V	mi	Mi	F9
0 0 1 1	0 1 0 1	m0 = m1 = m2 = m3 = AB	M0 = M1 = M2 = M3 = A + B	f0 = 1 f1 = 0 f2 = 0 f3 = 1

Mantiqiy bazis minimal deb ataladi, agarda unga kiruvchi funksiyalardan loaqal bittasini olib tashlanganda uni funksional tо‘liq bо‘lmagan holatga о‘zgartirsa. VA, YOKI, YО‘Q mantiqiy bazis minimal emas, chunki duallik qonuni yordamida mantiqiy ifodalardan yoki VA funksiyasini olib tashlash mumkin, yoki YOKI funksiyasini olib tashlash mumkin. Natijada minimal bazislarni olamiz: VA, YО‘Q va YOKI, YО‘Q.

“Sheffer shtrixi” (VA-YО‘Q) hamda “Pirs strelkasi” (YOKI-YО‘Q) kabi minimal mantiqiy bazislar faqat bitta funksiyadan tashkil topgan (2.3 jadvalga qaralsin). Bu funksiyalar tо‘plamini funksional tо‘liqligi ular yordamida mantiqiy bazisning barcha funksiyalarini quyida keltirilgan ifodalarga mos ravishda joriy etish mumkinligidan kelib chiqadi:

Oddiy mantiqiy operatsiyalarni bajaruvchi elektron sxemalarni mantiqiy elementlar deb ataladi. Kompyuterda turli mantiqiy funksiyalarni joriy etish uchun u yoki bu minimal bazisli operatsiyalarni joriy etuvchi mantiqiy elementning bо‘lishi yetarlidir. Mantiqiy elementlarning bu tо‘plami minimal element asosi (yoki asos) deb ataladi. Zamonaviy kompyuterlarning bloklari va qurilmalarida bunday asos bо‘lib kо‘pincha VA-YО‘Q, YOKI-YО‘Q elementlari xizmat qiladi.

Kompyuter qurilmalarini faqat minimal bazis elementlaridan foydalanib joriy etish kо‘pincha qurilmalarning murakkablashishiga olib keladi va ularning foydalanishdagi kо‘rsatgichlarini yomonlashtiradi. Shuning uchun qurilmalarning kо‘rsatgichlarini joriy etilishida yaxshilash maqsadida kengaytirilgan element bazasini ishlatish maqsadga muvofiq bо‘ladi, ularga VA-YО‘Q, YOKI-YО‘Q elementlaridan tashqari, VA-YOKI-YО‘Q, VA, YOKI va hokazo funksiyalarni bajaruvchi sxemalar kiradi.

Konyuktor – ikkilik mantiqiy elemen bо‘lib, u “mantiqiy kо‘paytiruv” (VA) operatsiyasini bajaradi. Uch krishli konyuktorning ishlash mantiqi 2.6 jadvalda keltirilgan va uni holatlar jadvali (chinlik jadvali) deb ataladi.

2.6 jadval

x1	x2	x3	u		x1	x2	x3	u
0	0	0	0		1	0	0	0
0	0	1	0		1	0	1	0
0	1	0	0		1	1	0	0
0	1	1	0		1	1	1	1

2.6 jadval asosida tuzilgan konyuktor ishlashining mantiqiy tenglamasi quyidagi kо‘rinishda yoziladi

u = x₁ x₂ x₃ yoki u = x₁ x₂ x₃ .

Keltirilgan tenglama konyuktorning x₁, x₂, x₃ kirishlari va u chiqishining holatini xarakterlaydi.

Dezyunktor - ikkilik mantiqiy element bо‘lib, u “mantiqiy qо‘shish” (YOKI) operatsiyasini bajaradi. Uch krishli dezyunktorning ishlash mantiqi 2.7 jadvalda keltirilgan va uni holatlar jadvali (chinlik) deb ataladi.

2.7 jadval

x1	x2	x3	u		x1	x2	x3	u
0	0	0	0		1	0	0	1
0	0	1	1		1	0	1	1
0	1	0	1		1	1	0	1
0	1	1	1		1	1	1	1

2.7 jadval asosida tuzilgan dezyunktor ishlashining mantiqiy tenglamasi quyidagi kо‘rinishda yoziladi

u = x₁ x₂ x₃ yoki u = x₁ x₂ x₃ .

Keltirilgan tenglama dezyunktorning x₁, x₂, x₃ kirishlari va u chiqishining holatini xarakterlaydi.

Invertor - ikkilik mantiqiy element bо‘lib, u “mantiqiy inkor” (YО‘Q) operatsiyasini bajaradi. Invertorning ishlash mantiqi 1.8 jadvalda keltirilgan va uni holatlar jadvali (chinlik jadvali) deb nomlanadi.

2.8 jadval

x	u
0	1
1	0

2.8 jadval asosida tuzilgan invertor ishlashining mantiqiy tenglamasi quyidagi kо‘rinishda yozilad .

Sheffer elementi - ikkilik mantiqiy elemen bо‘lib, u “inkor etishli mantiqiy kо‘paytirish” (VA-YО‘Q) operatsiyasini bajaradi. Sheffer elementining ishlash mantiqi 2.9 jadvalda keltirilgan va uni holatlar jadvali (chinlik jadvali) deb yuritiladi.

2.9 jadval

x1	x2	x3	u		x1	x2	x3	u
0	0	0	1		0	1	1	1
0	0	1	1		1	0	1	1
0	1	0	1		1	1	0	1
1	0	0	1		1	1	1	0

2.9 jadval asosida tuzilgan konyuktor ishlashining mantiqiy tenglamasi quyidagi kо‘rinishda bо‘ladi .

Pirs elementi - ikkilik mantiqiy element bо‘lib, u “inkor etishli mantiqiy qо‘shish” (YOKI-YО‘Q) operatsiyasini bajaradi. Pirs elementining ishlash mantiqi 2.10 jadvalda keltirilgan va uni holatlar jadvali (chinlik jadvali) deb ataladi.

2.10 jadval

x1	x2	x3	u		x1	x2	x3	u
0	0	0	1		0	1	1	0
0	0	1	0		1	0	1	0
0	1	0	0		1	1	0	0
1	0	0	0		1	1	1	0

2.10 jadval asosida tuzilgan Pirs elementini ishlashining mantiqiy tenglamasi quyidagi kо‘rinishga ega y .

VA-YOKI-YО‘Q mantiqiy elementining chinlik jadvali 2.11 jadvalda keltirilgan va uning 2.11 jadval asosida tuzilgan ishlashining mantiqiy tenglamasi quyidagi kо‘rinishda yoziladi .
2.11 jadval

x1 x2 x3 u4	u
1 1 0 1 1 0 0 0	0 0 0 1

Nazorat uchun savollar

1. 
   Asosiy mantiqiy operatsiyalarni sanab bering.
   
2. 
   Mantiqiy operatsiyalarning aksioma va qonunlarini jadval ko‘rinishida bayon qiling.
   
3. 
   Ikki o‘zgaruvchili 2² = 16 mantiqiy funksiyalarning to‘liq to‘plamini jadval ko‘rinishida bering.
   
4. 
   Mantiqiy funksiyalarni ifodalanish usullarini sanab bering va misol keltiring.
   
5. 
   Mantiqiy elementlarni sanab bering, ularni chinlik jadvali va shartli belgilanishi orqali tushuntiring.