|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi buxoro viloyati buxoro davlat universiteti
|
| bet | 4/10 | | Sana | 28.01.2024 | | Hajmi | 226,5 Kb. | | #147720 |
Bog'liq 1 Mulohazalar algebrasi funksiyalari Funksiyalarning teng kuchTo'liqlik mezoni
Endi biz funktsiyalar tizimining to'liqligi uchun zarur va etarli shartlarni aniqlaydigan to'liqlik mezonini (Post teoremasi) shakllantirish va isbotlash imkoniyatiga egamiz. Biz to'liqlik mezonini shakllantirish va isbotlashdan oldin bir nechta mustaqil manfaatdor lemmalar bilan murojaat qilamiz.
Lemma 2.7. O'z-o'zidan ikkilamchi bo'lmagan funksiya haqida lemma.
Agar f (x 1, ..., x n) Ï S bo'lsa, undan x va `x funksiyalarni qo'yish orqali doimiyni olish mumkin.
Isbot... fÏS dan boshlab, o'zgaruvchilarning qiymatlari to'plami mavjud
= (a 1, ..., a n) shunday
f (`a 1, ...,` a n) = f (a 1, ..., a n)
f funksiyadagi argumentlarni almashtiramiz:
x i bilan almashtiriladi ,
ya'ni funktsiyani qo'yamiz va ko'rib chiqamiz
Shunday qilib, biz doimiyga ega bo'ldik (ammo uning qaysi doimiy ekanligi ma'lum emas: 0 yoki 1). ð
Lemma 2.8. Monotonik bo'lmagan funksiya bo'yicha lemma.
Agar f (x 1, ..., xn) funksiya monoton bo'lmagan f (x 1, ..., xn) Ï M bo'lsa, u holda o'zgaruvchilarni o'zgartirish va 0 konstantalarini almashtirish orqali undan inkor olish mumkin. va 1.
Isbot... f (x 1, ..., x n) Ï M bo'lgani uchun uning o'zgaruvchilari to'plamlari va qiymatlari mavjud, , shundayki, bundan tashqari, i ning kamida bitta qiymati uchun a i< b i . Выполним следующую замену переменных функции f:
x i bilan almashtiriladi
Bunday almashtirishdan so'ng biz bitta j (x) o'zgaruvchining funktsiyasini olamiz, buning uchun bizda mavjud:
Bu j (x) = `x ekanligini bildiradi. Lemma isbotlangan. ð
Lemma 2.9. Chiziqli bo'lmagan funksiya bo'yicha lemma.
Agar f (x 1, ..., x n) Ï L bo‘lsa, undan 0, 1 konstantalarini o‘rniga qo‘yib, `x funksiyasidan foydalanib, x 1 & x 2 funksiyasini olishimiz mumkin.
Isbot... Biz f ni DNF (masalan, mukammal DNF) shaklida ifodalaymiz va quyidagi munosabatlardan foydalanamiz:
Misol... Keling, ushbu o'zgarishlarni qo'llashga ikkita misol keltiramiz.
Shunday qilib, disjunktiv normal shaklda yozilgan funktsiya, ko'rsatilgan munosabatlar, qavslarni ochish va oddiy algebraik o'zgartirishlar qo'llanilgandan so'ng, mod 2 polinomiga (Jegalkin polinomiga) aylanadi:
Bu erda A 0 doimiy, A i esa x 1, ..., x n, i = 1, 2, ..., r sonidan ba'zi o'zgaruvchilarning birikmasidir.
Har bir A i birikmasi faqat bitta o‘zgaruvchidan iborat bo‘lsa, f chiziqli funksiya bo‘lib, lemma shartiga zid keladi.
Binobarin, f funksiyasi uchun Jegalkin polinomi kamida ikkita omilni o'z ichiga olgan atamani o'z ichiga oladi. Umumiylikni yo'qotmasdan, biz ushbu omillar orasida x 1 va x 2 o'zgaruvchilari borligini taxmin qilishimiz mumkin. Keyin ko'phadni quyidagicha o'zgartirish mumkin:
f = x 1 x 2 f 1 (x 3, ..., xn) + x 1 f 2 (x 3, ..., xn) + x 2 f 3 (x 3, ..., xn) + f 4 (x 3, ..., xn),
Bu erda f 1 (x 3, ..., x n) ¹ 0 (aks holda ko'phadga x 1 x 2 bog'lovchisi bo'lgan birikma kirmaydi).
(a 3, ..., a n) f 1 (a 3, ..., a n) = 1 bo‘lsin.
j (x 1, x 2) = f (x 1, x 2, a 3, ..., a n) = x 1 x 2 + ax 1 + bx 2 + g,
bu yerda a, b, g doimiylar 0 yoki 1 ga teng.
Bizda mavjud bo'lgan inkor amalidan foydalanamiz va j (x 1, x 2) dan olingan y (x 1, x 2) funksiyani quyidagicha ko'rib chiqamiz:
y (x 1, x 2) = j (x 1 + b, x 2 + a) + ab + g.
Bu aniq
y (x 1, x 2) = (x 1 + b) (x 2 + a) + a (x 1 + b) + b (x 2 + a) + g + ab + g = x 1 x 2.
Demak,
y (x 1, x 2) = x 1 x 2.
Lemma to'liq isbotlangan. ð
|
| |
