Mantiq qonunlari
•
1. ¬¬ A
•
2. A&B
•
3. AVB
•
4. A va (B&C)
•
5. AV (BVC)
•
6.A va (BVC)
•
7. AV (B&C)
•
8. A&A
•
9. AVA
•
10. AV¬A
•
11.A & ¬A
•
12. A&I
•
13. AVI
•
14.A&L
•
15. AVL
•
16. ¬ (A&B)
•
17. ¬ (AVB)
•
18.A => B
Qonunlar asosida siz murakkab mantiqiy ifodalarni soddalashtirishingiz mumkin.
Murakkab mantiqiy funktsiyani oddiyroq, lekin unga ekvivalenti bilan almashtirish
jarayoni funksiyani minimallashtirish deb ataladi.
1-misol.
Olingan formulalarda murakkab ifodalarning inkori bo‘lmasligi uchun
ifodalarni soddalashtiring.
Yechim
2-misol.
Funktsiyani minimallashtirish
Ifodani soddalashtirish uchun yutilish va yopishish formulalaridan foydalanilgan.
3-misol.
Quyidagi gapning inkorini toping: "Agar dars qiziqarli bo'lsa, unda
o'quvchilarning hech biri (Misha, Vika, Sveta) derazadan tashqariga qaramaydi".
Yechim
Keling, bayonotlarni belgilaymiz:
Y- "Dars qiziqarli";
M- "Misha derazadan tashqariga qaraydi";
B- "Vika derazadan tashqariga qaraydi";
C- "Sveta derazadan tashqariga qaraydi."
Ifodani soddalashtirishda amallarni almashtirish formulasi va de Morgan
qonunidan foydalanilgan.
4-misol.
Jinoyat ishtirokchisini ikkita asosga asoslanib aniqlang: mantiqiy
kompyuter jadvali
•
1) "Agar Ivanov qatnashmagan yoki Petrov qatnashgan bo'lsa, unda Sidorov
qatnashgan";
•
2) "Agar Ivanov qatnashmagan bo'lsa, Sidorov qatnashmagan".
Yechim
Keling, iboralarni tuzamiz:
I- "Ivanov jinoyatda ishtirok etgan";
P- "Petrov jinoyatda ishtirok etgan";
S- "Sidorov jinoyatda ishtirok etgan".
Keling, posilkalarni formulalar shaklida yozamiz:
Natijani haqiqat jadvali yordamida tekshiramiz:
Javob: Jinoyatda Ivanov ishtirok etgan.
Uning haqiqat jadvalidan mantiqiy funktsiyani qurish
Mantiqiy funksiya uchun haqiqat jadvalini tuzishni o‘rgandik. Keling, teskari
masalani hal qilishga harakat qilaylik.
Z funksiyaning haqiqat qiymati rost (Z = 1) bo'lgan qatorlarni ko'rib chiqaylik. Bu
haqiqat jadvali uchun funksiyani quyidagicha tuzish mumkin: Z (X, Y) = (¬ X &
¬Y) V (X & ¬Y).
Funktsiya rost (1 ga teng) bo'lgan har bir satr argumentlar birikmasi bo'lgan qavsga
mos keladi va agar argumentning qiymati O bo'lsa, biz uni inkor bilan qabul
qilamiz. Barcha qavslar ajratish operatsiyasi bilan bog'langan. Olingan formulani
mantiq qonunlarini qo'llash orqali soddalashtirish mumkin:
Z (X, Y)<=>((¬X & ¬Y) VX) & ((¬X & Y) V ¬Y)<=>(XV (¬X & ¬Y)) & (¬YV
(¬X & ¬Y))<=>((XV¬X) & (XV ¬Y)) & ((Y¬V ¬X) & (¬YV ¬Y))<=>(1 & (XV
¬Y)) & (¬YV ¬X) & ¬Y)<=>(XV ¬Y) & (¬YV ¬X) & ¬Y).
Olingan formulani tekshiring: Z (X, Y) funksiyasi uchun haqiqat jadvalini tuzing.
Mantiqiy funktsiyani haqiqat jadvaliga ko'ra qurish qoidalarini yozing:
•
1. Haqiqat jadvalida funksiya qiymati 1 ga teng bo'lgan qatorlarni tanlang.
•
2. Kerakli formulani bir nechta mantiqiy elementlarning diszyunksiyasi
shaklida yozing. Ushbu elementlarning soni tanlangan chiziqlar soniga teng.
•
3. Bu diszyunksiyadagi har bir mantiqiy element funksiya argumentlarining
birikmasi sifatida yoziladi.
•
4. Agar jadvalning mos qatoridagi har qanday funktsiya argumentining
qiymati 0 ga teng bo'lsa, u holda bu argumentni inkor bilan qabul qilamiz.
1. Harakatlar tartibini aniqlang.
2. Haqiqat jadvalining o'lchamini aniqlang.
Ustunlar soni mantiqiy o'zgaruvchilar soni (ikkita A, B mavjud) va harakatlar soni
(ulardan ikkitasi ham bor) bilan belgilanadi.
4. Javobni shakllantirish.
Oxirgi ustunda bitta "0" A ga "1" ga, B esa "0" ga teng. Ma’lum bo‘lishicha, bu
funksiya A mantiqiy o‘zgaruvchisi rost, B mantiqiy o‘zgaruvchisi esa noto‘g‘ri
bo‘lgan taqdirdagina noto‘g‘ri bo‘ladi, bu esa NATIJA mantiqiy funksiyasiga mos
keladi.
Demak, bu funktsiya A va B o'zgaruvchilarning mantiqiy natijasiga teng: Agar A
bo'lsa, B bo'lsa.
Mantiqiy funktsiya uchun haqiqat jadvalini yarating:
1. Harakatlar tartibini aniqlang.
2. Haqiqat jadvalining o'lchamini aniqlang.
Jadvalning "sarlavhasi" ikkita qatorni o'z ichiga oladi - harakatlar raqamlari va
harakatlarning mantiqiy operatsiyalari.
Ustunlar soni mantiqiy o'zgaruvchilar soni (ikkita A, B mavjud) va harakatlar soni
(ulardan beshtasi bor) bilan belgilanadi.
Jadvaldagi qatorlar soni mantiqiy o'zgaruvchilar soniga teng bo'lgan quvvatga
ikkitaga teng - ikkita o'zgaruvchi bo'lsa, 4 qator olinadi.
3. Jadval ustunlarini shu ustunning mantiqiy vazifasiga muvofiq birin-ketin
to‘ldiring.
4. Javobni shakllantirish.
Oxirgi ustunda "1" A ga teng B ga, "0" esa - A ga teng bo'lmagan B ga to'g'ri
keladi. Ma'lum bo'lishicha, bu funktsiya A ga B ga teng bo'lganda to'g'ri va A ga
mos bo'lmagan B ga teng bo'lmaganda noto'g'ri bo'ladi. IDENTITY mantiqiy
funksiyasiga.
Demak, bu funktsiya A va B o'zgaruvchilarning mantiqiy IDENTITY ga teng: A B
bilan bir xil.
Kompyuter fanlari: shaxsiy kompyuter texnikasi Yashin Vladimir Nikolaevich
4.3. Mantiqiy funksiyalar va haqiqat jadvallari
Mantiq algebrasida mantiqiy o'zgaruvchilar va mantiqiy funksiyalar o'rtasidagi
bog'lanishlar haqiqat jadvallari deb ataladigan mos jadvallar yordamida ham
ko'rsatilishi mumkin. Haqiqat jadvallari keng qo'llaniladi, chunki ular mantiqiy
funktsiyaning mantiqiy o'zgaruvchilari qiymatlarining barcha kombinatsiyalari
uchun qanday qiymatlarni olishini aniq ko'rsatadi. Haqiqat jadvali ikki qismdan
iborat. Birinchi (chap) qism mantiqiy o'zgaruvchilarga tegishli bo'lib, mantiqiy
o'zgaruvchilarning mumkin bo'lgan kombinatsiyalarining to'liq ro'yxatini o'z ichiga
oladi. A, B, C ... va hokazo. Ushbu jadvalning ikkinchi (o'ng) qismida chiqish
holatlari kirish miqdorlari birikmalarining mantiqiy funktsiyasi sifatida belgilanadi.
Masalan, mantiqiy funktsiya uchun F = A v B v C uchta mantiqiy o'zgaruvchining
(dizyunksiyasi). A, B, va BILAN Haqiqat jadvali rasmda ko'rsatilgan shaklga ega
bo'ladi. 4.1. Mantiqiy o'zgaruvchilar va mantiqiy funktsiyaning qiymatlarini yozish
uchun ushbu haqiqat jadvali 8 qator va 4 ustunni o'z ichiga oladi, ya'ni har qanday
haqiqat jadvalining argumentlari va funktsiyalari qiymatlarini yozish uchun
qatorlar soni teng bo'ladi. 2 n, qayerda P - mantiqiy funktsiyaga argumentlar soni
va ustunlar soni n + 1.
Guruch. 4.1. Mantiqiy funktsiya uchun haqiqat jadvali F = A v V v C
Haqiqat jadvali har qanday mantiqiy funktsiya uchun tuzilishi mumkin, masalan,
rasmda. 4.2 - mantiqiy funktsiyaning haqiqati jadvali F = A? B? C(ekvivalentlar).
Mantiqiy funksiyalar mos ravishda nomlanadi. Ikki ikkilik oʻzgaruvchilar uchun
oʻn oltita mantiqiy funksiya mavjud boʻlib, ularning nomlari quyida keltirilgan.
Shaklda. 4.3 - mantiqiy funktsiyalarni ko'rsatadigan jadval F 1, F 2, F 3, … , F
16 ikkita mantiqiy o'zgaruvchi A va V.
Funktsiya F 1 = 0 va doimiy nol funksiyasi yoki nol generatori deb ataladi.
Yuqorida sanab o'tilgan o'zgaruvchilarning mantiqiy funktsiyalari orasida boshqa
mantiqiy funktsiyalarni ifodalash uchun ishlatilishi mumkin bo'lgan bir nechta
mantiqiy funktsiyalar mavjud. Mantiq algebrasida bir mantiqiy funktsiyani
boshqasiga almashtirish operatsiyasi superpozitsiya operatsiyasi yoki
superpozitsiya usuli deyiladi. Masalan, Sheffer funktsiyasini de Morgan qonuni
yordamida mantiqiy dis'yunktsiya va inkor funktsiyalari yordamida ifodalash
mumkin:
Superpozitsiya usuli yordamida boshqa mantiqiy funktsiyalarni ifodalash uchun
ishlatilishi mumkin bo'lgan mantiqiy funktsiyalar asosiy mantiqiy funktsiyalar deb
ataladi. Bunday asosiy mantiqiy funktsiyalar to'plami mantiqiy funktsiyalarning
funktsional to'liq to'plami deb ataladi. Amalda bunday to'plam sifatida uchta
mantiqiy funktsiya eng ko'p qo'llaniladi: konyunksiya, dis'yunktsiya va inkor. Agar
mantiqiy funktsiya asosiy funktsiyalar yordamida ifodalansa, u holda taqdimotning
bu shakli normal deyiladi. Oldingi misolda asosiy funksiyalar bilan ifodalangan
Sheffer mantiqiy funksiyasi normal shaklda ifodalangan.
Ushbu mantiqiy funktsiyalarni amalga oshiradigan asosiy funktsiyalar to'plami va
ularga mos keladigan texnik qurilmalardan foydalanib, siz har qanday mantiqiy
qurilma yoki tizimni loyihalashingiz va yaratishingiz mumkin.
Ta'rifi:
| 