Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

Mantiq algebrasidagi ikki taraflama qonun

Ikki taraflama funksiya. Endi ikki taraflama (qo‘shma) funksiya tushunchasini kiritamiz. funksiyaga ikki taraflama bo‘lgan funksiyani topish uchun funksiyaning chinlik jadvalida hamma o‘zgaruvchilarni ularning inkoriga almashtirish kerak, ya’ni hamma joyda 1ni 0ga va 0ni 1ga almashtirish kerak.

1- ta’rif. Quyidagicha aniqlangan

1- jadval
Berilgan funksiya	Ikki taraflama funksiya

funksiyaga funksiyaning ikki taraflama funksiyasi deb aytiladi.

2- ta’rif. Agar



munosabat bajarilsa, u holda o‘z-o‘ziga ikki taraflama funksiya deb ataladi.

Ta’rifga asosan, ikki taraflama funksiya va qiymatlar satrida qarama-qarshi qiymatlar qabul qiladi.

1- misol. Mulohazalar algebrasining asosiy elementar funksiyalariga ikki taraflama bo‘lgan funksiyalarni topamiz (1- jadvalga qarang). Demak, ta’rifga asosan, va funksiyalar o‘z-o‘ziga ikki taraflama funksiya bo‘ladi. ■

2- misol. funksiyaning o‘z-o‘ziga ikki taraflama funksiya ekanligini isbot qilamiz. Haqiqatdan ham

Demak, ekanligi uchun o‘z-o‘ziga ikki taraflama funksiyadir. ■

Teorema. Agar



bo‘lsa, u holda



bo‘ladi.

Isboti.







. ■

Ikki taraflama qonun. 1- teoremaning isbotidan ikki taraflama qonun kelib chiqadi.

Ikki taraflama qonun. funksiyalarning superpozisiyasiga ikki

taraflama bo‘lgan funksiya mos ravishda ikki taraflama funksiyalar superpozisiyasiga teng kuchlidir, ya’ni agar formula funksiyani realizasiya etsa, u holda formula funksiyani realizasiya etadi.

Bu formula formulaga ikki taraflama bo‘lgan formula deb aytiladi va u

deb belgilanadi. Demak, .

Ushbu qonundan o‘z-o‘ziga ikki taraflama bo‘lgan funksiyalarning superpozisiyasi yana o‘z-o‘ziga ikki taraflama funksiya bo‘lishligi kelib chiqadi, ya’ni agar o‘z-o‘ziga ikki taraflama funksiya bo‘lsa, u holda funksiya ham o‘z-o‘ziga ikki taraflama bo‘ladi. Haqiqatan ham,

.

Agar funksiya formula orqali ifodalangan va bu formula o‘z navbatida , , mantiq amallari orqali ifodalangan bo‘lsa, u holda bu funksiyaga (formulaga) ikki taraflama bo‘lgan funksiyani (formulani) topish uchun belgini belgiga, ni ga, 1ni 0ga va 0ni 1ga almashtirish kifoya. Bu prinsipni teng kuchli formulalarga nisbatan ishlatganda, yana teng kuchli formulalar hosil qilamiz, ya’ni bo‘lsa, u holda .

Ushbu prinsipga tayanib mantiq algebrasining bir formulasidan boshqa formulasini, bir teoremasidan boshqa teoremasini, bir ta’rifidan esa boshqa ta’rifini hosil qilish mumkin.

3- misol. Ushbu bobning 9- paragrafida keltirilgan (2), (3), (6), (8), (10), (12) teng kuchli formulalarga ushbu prinsipni qo‘llasak, (4), (5), (7), (9), (11), (13) teng kuchli formulalar kelib chiqadi. ■

Mantiq algebrasida elementlari ta argumentli o‘z-o‘ziga ikki taraflama funksiyalardan iborat bo‘lgan to‘plamni bilan belgilaymiz, uning elementlari soni ga tengdir.

Endi o‘z-o‘ziga ikki taraflama bo‘lmagan funksiyalar haqidagi lemmani ko‘rib chiqaylik.

Lemma. Agar bo‘lsa, u holda undan argumentlarining

o‘rniga va funksiyalarni qo‘yish usuli bilan bir argumentli o‘z-o‘ziga ikki taraflama bo‘lmagan funksiya, ya’ni konstantani hosil qilish mumkin.

Isboti. bo‘lgani uchun, shunday qiymatlar satri topiladiki, bo‘ladi.

() funksiyani kiritamiz va deb

belgilab olamiz. U holda quyidagi natijaga ega bo‘lamiz:

. ■

Mantiq algebrasidagi arifmetik amallar.

Mantiq algebrasidagi arifmetik amallar. {0,1} Bul algebrasidagi kon’yunksiya amali oddiy arifmetikadagi 0 va 1 sonlar ustidagi ko‘paytma amaliga mos keladi. Ammo 0 va 1 sonlarini qo‘shish natijasi {0,1} to‘plam doirasidan chetga chiqadi. Shuning uchun I.I.Jegalkin¹ 2 moduliga asosan qo‘shish amalini kiritdi. va mulohazalarni 2 moduli bo‘yicha qo‘shishni deb belgilaymiz. 2 moduli bo‘yicha qo‘shish, odatda, chinlik jadvali bilan beriladi (1- jadvalga qarang).

1- jadval
0	0	0
0	1	1
1	0	1
1	1	0

Chinlik jadvalidan ko‘rinib turibdiki, bo‘ladi. Mantiq algebrasidagi ko‘paytma va 2 moduli bo‘yicha qo‘shish mantiq amallari uchun kommutativlik, assotsiativlik va distributivlik qonunlari o‘z kuchini saqlaydi.

Bul algebrasidagi asosiy mantiqiy amallarni kiritilgan arifmetik amallar orqali quyidagicha ifodalash mumkin:

; ; ;

; .

2 moduli bo‘yicha qo‘shish amalining ta’rifiga asosan va ().

1 Jegalkin Ivan Ivanovich (Жегалкин Иван Иванович 1869-1947) – sovet matematigi. I. I. Jegalkin XX asrning 30- yillari boshida MDUda birinchi bo‘lib matematik mantiq bo‘yicha ilmiy seminar tashkil etgan.