Mantiqiy funksiyalar uchun qiymatlar jadvali. Funksiyalar soni

DNF - dis'yunktiv normal shakl
Elementar mantiqiy mahsulotlarning 
mantiqiy yig'indisi. DNF haqiqat jadvalidan quyidagi algoritm yoki qoida 
bo'yicha olinadi: 
1) jadvalda chiqish funktsiyasi = 1 tanlangan o'zgaruvchilar qatorlari. 
2) o'zgaruvchilarning har bir qatori uchun mantiqiy ko'paytma yoziladi; bu 
erda = 0 o'zgaruvchilar inversiya bilan yoziladi. 
3) hosil bo'lgan mahsulot mantiqiy ravishda umumlashtiriladi. 
Fdnf = X 1 * X 2 * X 3 
∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3 
Agar barcha o'zgaruvchilar bir xil daraja yoki tartibga ega bo'lsa, DNF 
mukammal deb ataladi, ya'ni. har bir ish to'g'ridan-to'g'ri yoki teskari shaklda 
barcha o'zgaruvchilarni o'z ichiga olishi kerak. 
b) 
CNF - kon'yunktiv normal shakl
Elementar mantiqiy summalarning 
mantiqiy mahsulotidir. 
CNF ni quyidagi algoritm yordamida haqiqat jadvalidan olish mumkin: 
1) chiqish funktsiyasi = 0 bo'lgan o'zgaruvchilar to'plamini tanlang 
2) har bir o'zgaruvchilar to'plami uchun elementar mantiqiy yig'indini 
yozamiz va o'zgaruvchilar = 1 inversiya bilan yoziladi. 
3) olingan summalar mantiqiy ravishda ko'paytiriladi. 
Fscnf = (X 1 V X 2 V X 3) 
∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 
1 V X 2 V X 3) 
CNF mukammal deb ataladi
agar barcha o'zgaruvchilar bir xil darajaga 
ega bo'lsa. 

---

Algebraik shaklda siz mantiqiy eshiklar yordamida mantiqiy qurilma sxemasini 
qurishingiz mumkin. 
1-rasm - Mantiqiy qurilma diagrammasi 
Barcha mantiqiy operatsiyalar aniqlangan 
haqiqat jadvallari
qiymatlar. Haqiqat 
jadvali operatsiya natijasini aniqlaydi 
hammasi mumkin
x asl bayonotlarning 
mantiqiy qiymatlari. Amaliyotlarni qo'llash natijasini aks ettiruvchi variantlar soni 
mantiqiy ifodadagi gaplar soniga bog'liq bo'ladi. Agar mantiqiy ifodadagi 
bayonotlar soni N bo'lsa, unda haqiqat jadvali 2 N qatorni o'z ichiga oladi, chunki 
argumentlarning mumkin bo'lgan qiymatlarining 2 N xil kombinatsiyasi mavjud. 
NO operatsiyasi - mantiqiy inkor (inversiya) 
Mantiqiy operatsiya oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin bo'lgan 
bitta argumentga QO'LLANILMAYDI. Operatsiyaning natijasi EMAS: 
• 
agar dastlabki ifoda rost bo'lsa, uni inkor qilish natijasi noto'g'ri bo'ladi; 
• 
agar asl ifoda noto'g'ri bo'lsa, uni inkor qilish natijasi to'g'ri bo'ladi. 
Quyidagi konventsiyalar inkor operatsiyasi uchun QABUL QILMAYDI: 
A emas, Ā, A emas, ¬A,!A 
Rad etish operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanmaydi: 
A 
emas, balki A 
0 
1 
1 
0 
Inkor amalining natijasi asl bayonot noto'g'ri bo'lganda to'g'ri bo'ladi va aksincha. 
OR operatsiya - mantiqiy qo'shish (ajralish, birlashma) 
Mantiqiy OR operatsiyasi oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin 
bo'lgan ikkita bayonotni birlashtirish funktsiyasini bajaradi. Mantiqiy operatsiya 
uchun manba bo'lgan bayonotlar argumentlar deb ataladi. OR operatsiyasining 
natijasi, agar asl iboralardan kamida bittasi to'g'ri bo'lsa, to'g'ri bo'ladigan ifodadir. 
Qo'llaniladigan belgilar: A yoki B, A V B, A yoki B, A || B. 

---

OR operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanadi: 
YOKI amalining natijasi A rost, yoki B rost, yoki A va B bir vaqtning o'zida to'g'ri, 
A va B argumentlari noto'g'ri bo'lsa, noto'g'ri bo'ladi. 
VA operatsiya - mantiqiy ko'paytirish (bo'g'in) 
Mantiqiy AND operatsiyasi oddiy va murakkab mantiqiy ifoda bo'lishi mumkin 
bo'lgan ikkita bayonotni (argumentlarni) kesish funktsiyasini bajaradi. AND 
operatsiyasining natijasi ikkala asl ibora ham to'g'ri bo'lgan taqdirdagina to'g'ri 
bo'ladigan ifodadir. 
Qo'llaniladigan belgilar: A va B, A L B, A va B, A va B. 
AND operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanadi: 
A 
B 
A va B 
0 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
1 
AND operatsiyasining natijasi, agar A va B iboralar bir vaqtning o'zida to'g'ri 
bo'lsa va boshqa barcha holatlarda noto'g'ri bo'lsa, rost bo'ladi. 
"IF-THEN" operatsiyasi - mantiqiy keyingi (ta'sir) 
Bu operatsiya ikkita oddiy mantiqiy ifodani bog'laydi, ulardan birinchisi shart, 
ikkinchisi esa shu shartning natijasidir. 
Amaliy belgilar: 
agar A, keyin B; A B ni o'z ichiga oladi; agar A u holda B; A → B. 
Haqiqat jadvali: 
A 
B 
A → B 

---

0 
0 
1 
0 
1 
1 
1 
0 
0 
1 
1 
1 
Quyidagi amalning natijasi (ma’nosi) faqat A asosi to‘g‘ri, B xulosasi (natija) 
noto‘g‘ri bo‘lgandagina noto‘g‘ri bo‘ladi. 
"A, agar va faqat B" operatsiyasi (ekvivalentlik, ekvivalentlik) 
Amaliy belgi: A ↔ B, A ~ B. 
Haqiqat jadvali: 
A 
B 
A↔B 
0 
0 
1 
0 
1 
0 
1 
0 
0 
1 
1 
1 
"Mod 2 qo'shish" operatsiyasi (XOR, eksklyuziv yoki qat'iy ajratish) 

---

Amaliy belgi: A XOR B, A 
⊕ B. 
Haqiqat jadvali: 
A 
B 
A
⊕B 
0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
0 
Amaliyot ekvivalentligining natijasi faqat A va B bir vaqtning o'zida to'g'ri yoki 
noto'g'ri bo'lsa, to'g'ri bo'ladi. 
Mantiqiy ustuvorlik 
• 
Qavs ichidagi amallar 
• 
Inversiya 
• 
Bog'lovchi (&) 
• 
Disjunction (V), Exclusive OR (XOR), sum mod 2 
• 
Izoh (→) 
• 
Ekvivalentlik (↔) 
Mukammal disjunktiv normal shakl 
Formulaning mukammal dis'yunktiv normal shakli(SDNF) unga ekvivalent 
formula bo'lib, u quyidagi xususiyatlarga ega elementar birikmalarning 
diszyunksiyasidir: 
1. Formulaning har bir mantiqiy atamasi F funktsiyasiga kiritilgan barcha 
o'zgaruvchilarni o'z ichiga oladi (x 1, x 2, ... x n). 
2. Formulaning barcha mantiqiy shartlari boshqacha. 
3. Birorta ham mantiqiy atama o'zgaruvchini va uning inkorini o'z ichiga 
olmaydi. 

---

4. Formuladagi hech qanday mantiqiy atama bir xil o'zgaruvchini ikki marta o'z 
ichiga olmaydi. 
SDNF ni haqiqat jadvallari yordamida yoki ekvivalent transformatsiyalar 
yordamida olish mumkin. 
Har bir funktsiya uchun SDNF va SKNF o'zgartirishgacha noyob tarzda 
aniqlanadi. 
Mukammal kon'yunktiv normal shakl 
Mukammal kon'yunktiv normal shakl formulasi (SKNF) xossalarini 
qanoatlantiradigan elementar ayirmalarning birikmasi bo‘lgan unga ekvivalent 
formuladir: 
1. Barcha elementar bandlar F funktsiyasiga kiritilgan barcha o'zgaruvchilarni 
o'z ichiga oladi (x 1, x 2, ... x n). 
2. Barcha elementar disjunksiyalar har xil. 
3. Har bir elementar dis'yunktsiya bir marta o'zgaruvchini o'z ichiga oladi. 
4. Elementar dis'yunktsiyada o'zgaruvchi va uning inkori mavjud emas. 
Foydalanilgan adabiyotlar 
• 
1. Toʼraev X. Matematik mantiq va diskret matematika. T.: “Oʼqituvchi”, 2003. 
• 
2. Sudoplatov S. V., Ovchinnikova Ye. V. Elementii diskretnoy matematiki – M.: «Infra-
M», 2002 g. 
• 
3. Аseev G.G., Аbramov O.M., Sitnikov D.E. Diskretnaya matematika. – Rostov – na-
Donu, «Feniks», 2003 g. 
• 
4. Kulabuxov S.Yu. Diskretnaya matematika – Taganrogskiy 
radiotexnicheskiy 
universitet
, Taganrog, 2001 g.