Mulohazalar algebrasi funksiyalari. Funksiyalar teng kuchliligi. Superpozitsiya

•  
• Mulohazalar algebrasi  funksiyalari. Funksiyalar teng kuchliligi.
• Funksiyalar superpozisiyasi

Reja:

           1.Mulohazalar algebrasi funksiyalari.

           2.Funksiyalarning teng kuchliligi.

           3.Nol saqlovchi funksiyalar.

           4.Bir saqlovchi funksiyalar.

Tayanch iboralar: Mulohazalar algebrasi funksiyalari, funksiyalarning teng kuchliligi,nol saqlovchi funksiyalar,bir saqlovchi funksiyalar

Ma`lumki,mantiqiy amallar mulohazalar algebrasi  nuqtai nazaridan chinlik jadvallari bilan to`liq tavsiflanadi. Agarda funksiyaning jadval shaklida berilishini esga olsak, u holda mulohazalar algebrasida ham funksiya tushunchasi aniqlash mumkin.

1-tarif.Mulohazalar algebrasining, x1x2,…,xn argumentli f(x1x2,…,xn)  funksiyasi deb, 0 va 1 qiymatlar qabul qiluvchi funksiyaga aytiladi va uning x1x2,…,xn argumentlari ham 0 va 1 qiymatlar qabul qiladi. f(x1x2,…,xn) funksiya o`zining chinlik jadvali bilan berilishi mumkin:

Bu jadvalning har bir satrida avval o`zgaruvchilarning 

(a1, a2, ….,an) qiymatlari va shu qiymatlar satrida  f funksiyaning f(a1, a2, ….,an) qiymati beriladi. Ma`lumki, n ta o`zgaruvchi uchun qiymatlar satrlarining soni 2n va funksiyalar soni    gat eng bo`ladi.

Mulohazalar algebrasida asosiy  elementar funksiyalar quyidagilardan iborat:

Agar f(0,0,0,…,0) = 0  bo`lsa , u holda   f(x1x2,…,xn)  funksiya 0 saqlovchi   funksiya deb ataladi. Agar f(1,1,1,…,1)  = 1 bo`lsa u holda f(x1x2,…,xn)  funksiya 1 saqlovchi funksiya deb ataladi.

n ta argumentli 0 saqlovchi funksiyalarning soni      ga va 1 saqlovchi funksiyalar soni ham  gat eng bo`ladi.

Mulohazalar algebrasidagi n argumentli 0 saqlovchi funksiyalar to`plamini P0 va 1 saqlovchi funksiyalar to`plamini P1 orqali belgilaymiz.

2-ta`rif.Agar x1x2,…,xn argumentlarining barcha qiymatlar satri uchun f  va g  funksiyalarning mos qiymatlari bir xil bo`lsa, u holda f va g funksiyalar teng kuchli funksiyalar deb ataladi va 

f = g deb  begilanadi.

3-ta`rif. Agarda

            f(x1x2,…xi-1,1,xi+1,… xn) = f(x1x2,…xi-1,0,xi+1,… xn)  bo`lsa, u holda xi argument f(x1x2,…, xn) funksiyaning coxta argumenti deyiladi.   

Agarda

            f(x1x2,…xi-1,1,xi+1,… xn) ¹ f(x1x2,…xi-1,0,xi+1,… xn)  bo`lsa, u holda xi argument f(x1x2,…, xn) funksiyaning coxta emas (muhim) argumenti deyiladi. 

Misol. f(x,y) = xÚxy funksiya uchun y argument soxta argument bo`ladi, chunki  f(x,0) = f(x,1) = x.

Funksiyaning argumentlari qatoriga istalgancha soxta argumentlarni yozish mumkin va u qatordan hamma soxta argumentlarni olib tashlash mumkin.

4-ta`rif.   mulohazalar algebrasi funksiyalarining chekli sistemasi bo`lsin.Quyidagi ikkita usulni bittasi bilan hosil qilinadigan y funksiya F sistemadagi    

Funksiyalarning elementar superpozisiyasi yoki bir rangli superpozisiyasi deb ataladi:

1. biror funksiyaning xji argumentini qayta nomlash usuli, ya`ni 

Bu erda o`zgaruvchi , xjk o`zgaruvchilarning birortasi bilan mos tushishi mumkin;

1.  biror funksiyaning biror xji argumenti o`rniga ikkinchi bir  funksiyani qo`yish usuli, ya`ni 

              .

Agar sistema funksiyalarining k rangli superpozisiyalar sinfi berilgan bo`lsa, u holda bo`ladi. 

Funksiyalarning superpozitsiyasi.

To'plamlar orasidagi moslik G A va V kichik to'plam deb ataladi. Agar shunday deyishadi b

ga mos keladi a. Barcha mos keladigan elementlar to'plami

Chaqirildi yo'l element a. Element mos keladigan barcha narsalar to'plami deyiladi

prototip element b.

Ko'p juftliklar (B, a) bunday, bu teskari deb ataladi

munosabati G va tomonidan ko'rsatiladi. Tasvir tushunchasi va uning prototipi

"G va o'zaro teskari.

Misollar. 1) natural songa mos ravishda qo'yaylik P

haqiqiy sonlar to'plami ... 5 raqamining tasviri

yarim oraliq bo'ladi

(bu eng katta butun son, kichik yoki teng X). Ushbu moslik bilan 5 raqamining oldingi tasviri cheksiz to'plamdir: yarim oraliq.

Yopish nuqtai nazaridan, yopiqlik va to'liqlikning boshqa ta'riflarini berish mumkin (asl ta'riflarga teng):

K - yopiq sinf, agar K = [K];

Agar [K] = R 2 bo'lsa, K to'liq sistemadir.

Misollar.

* (0), (1) - yopiq sinflar.

* Bitta o'zgaruvchining ko'p funksiyalari - yopiq sinf.

* - yopiq sinf.

* Sinf (1, x + y) yopiq sinf emas.

Keling, eng muhim yopiq sinflarni ko'rib chiqaylik.

1.T 0- 0 ni saqlaydigan funksiyalar sinfi.

T 0 bilan doimiy 0 ni saqlaydigan f (x 1, x 2, ..., x n) barcha mantiqiy funksiyalar sinfini, ya’ni f (0, ..., 0) = 0 bo‘lgan funksiyalarni belgilaymiz.

T 0 ga tegishli funktsiyalar va bu sinfga kirmaydigan funksiyalar mavjudligini ko'rish oson:

0, x, xy, xÚy, x + y Î T 0;

Ï T 0 ekanligidan, masalan, uni dizyunksiya va qo`shma gaplarda ifodalab bo`lmasligi kelib chiqadi.

Birinchi qatorda T 0 sinfidagi f funktsiyasi uchun jadval 0 qiymatini o'z ichiga olganligi sababli, T 0 dan funktsiyalar uchun ixtiyoriy qiymatlar faqat 2 n - 1 o'zgaruvchilar qiymatlari to'plamida ko'rsatilishi mumkin, ya'ni

,

bu erda 0 ni saqlaydigan va n ta o'zgaruvchiga bog'liq bo'lgan funktsiyalar to'plami.

T 0 yopiq sinf ekanligini ko'rsatamiz. XÎT 0 bo'lgani uchun, yopiqlikni asoslash uchun uning superpozitsiya amaliga nisbatan yopiqligini ko'rsatish kifoya, chunki o'zgaruvchilarni o'zgartirish operatsiyasi x funksiyasi bilan superpozitsiyaning maxsus holatidir.

Mayli. Keyin buni ko'rsatish kifoya. Ikkinchisi tenglik zanjiridan kelib chiqadi

2.T 1- 1 ni saqlaydigan funksiyalar sinfi.

T 1 bilan doimiy 1 ni saqlaydigan f (x 1, x 2, ..., x n) barcha mantiqiy funksiyalar sinfini, ya’ni f (1, ..., 1) = 1 bo‘lgan funksiyalarni belgilaymiz.

T 1 ga tegishli funktsiyalar va bu sinfga kirmaydigan funktsiyalar mavjudligini ko'rish oson:

1, x, xy, xÚy, xºy Î T 1;

0,, x + y Ï T 1.

X + y Ï T 0 ekanligidan, masalan, x + y ni diszyunksiya va konyunksiya yordamida ifodalab bo‘lmaydi.

T 0 sinfiga oid natijalar ahamiyatsiz holda T 1 sinfiga o'tadi. Shunday qilib, bizda:

T 1 - yopiq sinf;

.

3. L- chiziqli funksiyalar sinfi.

L bilan mantiqiy algebraning f (x 1, x 2, ..., x n) chiziqli bo‘lgan barcha funksiyalari sinfi belgilansin:

L ga tegishli bo'lgan va ushbu sinfga kirmaydigan funktsiyalar mavjudligini ko'rish oson:

0, 1, x, x + y, x 1 º x 2 = x 1 + x 2 + 1, = x + 1 Î L;

Masalan, xÚy Ï L ekanligini isbotlaylik.

Buning aksini deylik. XÚy uchun ifodani aniqlanmagan koeffitsientli chiziqli funktsiya shaklida qidiramiz:

x = y = 0 uchun bizda a = 0,

x = 1, y = 0 uchun bizda b = 1,

x = 0, y = 1 uchun, bizda g = 1,

lekin u holda x = 1, y = 1 uchun bizda 1Ú 1 ¹ 1 + 1 bo'ladi, bu esa xÚy funksiyaning chiziqli emasligini isbotlaydi.

Chiziqli funktsiyalar sinfining yopiqligining isboti juda aniq.

Chiziqli funktsiya a 0, ..., an koeffitsientining n + 1 qiymatlarini belgilash orqali yagona aniqlanganligi sababli, n o'zgaruvchiga bog'liq bo'lgan L (n) funktsiyalar sinfidagi chiziqli funktsiyalar soni ga teng. 2 n + 1.

.

4.S- o'z-o'zidan ikkilamchi funktsiyalar sinfi.

O'z-o'zidan ikki tomonlama funktsiyalar sinfining ta'rifi ikkilik va ikki tomonlama funktsiyalar deb ataladigan printsipdan foydalanishga asoslangan.

Tenglik bilan aniqlangan funksiya deyiladi ikki tomonlama ishlaydi .

Shubhasiz, ikkita funktsiya jadvali (o'zgaruvchilar qiymatlari to'plamining standart tartibi bilan) ustunni teskari (ya'ni 0 ni 1 ga va 1 ni 0 ga almashtirish) asl funktsiya jadvalidan olinadi. funktsiya qiymatlari va uni aylantirish.

Buni ko'rish oson

(x 1 Ú x 2) * = x 1 Ù x 2,

(x 1 Ù x 2) * = x 1 Ú x 2.

Ta'rifdan kelib chiqadiki, (f *) * = f, ya'ni f funksiya f * ga dualdir.

Funksiya superpozitsiya yordamida boshqa funksiyalar bilan ifodalansin. Savol shundaki, amalga oshiradigan formulani qanday qurish kerak? To'plamlarda uchraydigan o'zgaruvchilarning barcha turli belgilarini = (x 1, ..., x n) bilan belgilaymiz.

2.6 teorema. Agar j funksiya f, f 1, f 2, ..., f m funksiyalarning superpozitsiyasi sifatida olingan bo‘lsa, ya’ni.

superpozitsiyaga dual funktsiya ikki tomonlama funksiyalarning superpozitsiyasidir.

Isbot.

j * (x 1, ..., x n) = `f (` x 1, ..., `x n) =

Teorema isbotlangan. ð

Ikkilik printsipi teoremadan kelib chiqadi: agar A formulasi f (x 1, ..., xn) funktsiyani amalga oshirsa, unda A dan olingan formulalar unga kiritilgan funktsiyalarni ikki tomonlama funktsiyalari bilan almashtirish orqali f * ikki tomonlama funktsiyani amalga oshiradi. (x 1, ... , xn).

P 2 dan barcha o'z-o'zidan ikkilangan funktsiyalar sinfini S bilan belgilaymiz:

S = (f | f * = f)

S ga tegishli funktsiyalar va bu sinfga kirmaydigan funksiyalar mavjudligini ko'rish oson:

0, 1, xy, xÚy Ï S.

O'z-o'zidan ikkilamchi funktsiyaning kamroq ahamiyatsiz misoli bu funktsiyadir

h (x, y, z) = xy Ú xz Ú yz;

superpozitsiyaga dual funksiya haqidagi teoremadan foydalanib, biz bor

h * (x, y, z) = (x Ú y) Ù (x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h *; h Î S.

O'z-o'zidan ikkilamchi funktsiya uchun identifikatsiya

to'plamlarda shunday va biz qarama-qarshi deb ataydigan o'z-o'zidan ikki tomonlama funktsiya qarama-qarshi ma'nolarni oladi. Bundan kelib chiqadiki, o'z-o'zidan ikkilamchi funktsiya standart jadval satrlarining birinchi yarmidagi qiymatlari bilan to'liq aniqlanadi. Demak, n ta o‘zgaruvchiga bog‘liq bo‘lgan S (n) funksiyalar sinfidagi o‘z-o‘zidan ikkilamchi funksiyalar soni:

.

Keling, S sinfining yopiqligini isbotlaylik. XÎS bo'lgani uchun, yopiqlikni asoslash uchun uning superpozitsiya amaliga nisbatan yopiqligini ko'rsatish kifoya, chunki o'zgaruvchilarni o'zgartirish operatsiyasi x funksiyasi bilan superpozitsiyaning maxsus holatidir. Mayli. Keyin buni ko'rsatish kifoya. Ikkinchisi to'g'ridan-to'g'ri o'rnatiladi:

5.M- monoton funktsiyalar sinfi.

Mantiq algebrasining monoton funksiyasi tushunchasiga ta’rif berishdan oldin uning o‘zgaruvchilari to‘plamlari to‘plamiga tartib munosabatini kiritish zarur.

To'plam to'plamdan oldin aytiladi (yoki “ko‘p emas” yoki “kichik yoki teng”) va yozuvdan foydalaning, agar a i £ b i hammasi uchun i = 1, ..., n. Agar va bo'lsa, biz to'plam to'plamdan qat'iy oldin (yoki to'plamdan "qat'iy kamroq" yoki "kamroq") ekanligini aytamiz va yozuvdan foydalanamiz. va to'plamlari solishtiriladigan deyiladi, agar bo'lsa, yoki.Bu munosabatlarning hech biri bajarilmasa, va to'plamlari solishtirilmaydigan deyiladi. Masalan, (0, 1, 0, 1) £ (1, 1, 0, 1), lekin (0, 1, 1, 0) va (1, 0, 1, 0) toʻplamlarni solishtirib boʻlmaydi. Shunday qilib, £ munosabati (u ko'pincha ustunlik munosabati deb ataladi) V n to'plamdagi qisman tartibdir. Quyida B 2, B 3 va B 4 qisman tartiblangan to'plamlarning diagrammalari keltirilgan.

Kiritilgan qisman tartib munosabati bizning kursimiz doirasidan tashqariga chiqadigan juda muhim tushunchadir.

Endi biz monoton funksiya tushunchasini aniqlay oladigan holatdamiz.

Mantiqiy algebra funksiyasi deyiladi monoton agar har qanday ikkita to'plam uchun va shunga o'xshash tengsizlik ... Mantiqiy algebraning barcha monoton funksiyalar to‘plami M bilan, n ta o‘zgaruvchiga bog‘liq bo‘lgan barcha monoton funksiyalar to‘plami M (n) bilan belgilanadi.

M ga tegishli funktsiyalar va bu sinfga kirmaydigan funksiyalar mavjudligini ko'rish oson:

0, 1, x, xy, xÚy Î M;

x + y, x®y, xºy Ï M.

M monoton funksiyalar sinfi yopiq sinf ekanligini ko'rsatamiz. XÎM bo'lgani uchun, yopiqlikni asoslash uchun uning superpozitsiya amaliga nisbatan yopiqligini ko'rsatish kifoya, chunki o'zgaruvchilarni o'zgartirish operatsiyasi x funktsiyasi bilan superpozitsiyaning maxsus holatidir.

Mayli. Keyin buni ko'rsatish kifoya.

Tegishli ravishda j, f 1, ..., f m funksiyalar o‘zgaruvchilar to‘plami bo‘lsin va j funksiyaning o‘zgaruvchilar to‘plami f 1, ..., f m funksiyalarda uchraydigan o‘sha va faqat shu o‘zgaruvchilardan iborat bo‘lsin. O'zgaruvchan qiymatlarning ikkita to'plami bo'lsin va bo'lsin. Bu to'plamlar to'plamlarni belgilaydi o'zgaruvchan qiymatlar shu kabi ... Chunki f 1, ..., f m funksiyalari

va f funksiyaning monotonligi tufayli

Bundan biz olamiz

n ta o'zgaruvchiga bog'liq monoton funksiyalar soni aniq ma'lum emas. Pastki chegarani osongina olish mumkin:

bu erda - n / 2 ning butun qismi.

Yuqoridan juda yuqori baho olish juda oson:

Ushbu hisob-kitoblarni aniqlashtirish zamonaviy tadqiqotning muhim va qiziqarli vazifasidir.

To'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. ð

Lemma 2.10. To'liqlik mezonining asosiy lemmasi.

Agar mantiqiy funktsiyalarning F = (f) sinfida birlikni saqlamaydigan, 0 ni saqlamaydigan, o'z-o'zidan ikkilamchi va monoton bo'lmagan funktsiyalar mavjud bo'lsa:

u holda bu sistemaning funksiyalaridan superpozitsiya va o'zgaruvchilarni o'zgartirish amallari orqali biz 0, 1 konstantalarni va funksiyani olishimiz mumkin.

Isbot... Funktsiyani ko'rib chiqaylik. Keyin

.

Keyingi mulohazalarning ikkita mumkin bo'lgan holatlari mavjud, bundan keyin 1) va 2) deb nomlanadi.

biri). Birlik to'plamidagi funktsiya 0 qiymatini oladi:

.

Hamma narsani almashtiring funktsiya o'zgaruvchilari o'zgaruvchan x. Keyin funksiya

bor, chunki

va .

O'z-o'zidan ikki tomonlama bo'lmagan funktsiyani oling. Biz funktsiyani allaqachon qo'lga kiritganimiz sababli, o'z-o'zidan ikkilamchi bo'lmagan funktsiya lemmasi bo'yicha (Lemma) 2.7. ) sizdan doimiyni olishingiz mumkin. Ikkinchi doimiyni birinchisidan funksiya yordamida olish mumkin. Demak, birinchi ko'rib chiqilayotgan holatda konstantalar va inkor olinadi. ... Ikkinchi holat va u bilan to'liqlik mezonining asosiy lemmasi to'liq isbotlangan. ð

2.11 teorema. Mantiq algebrasining funksiyalar sistemalarining to`liqligi mezoni (Post teoremasi).

F = (fi) funktsiyalar tizimi to'liq bo'lishi uchun uning beshta yopiq sinf T 0, T 1, L, S, M, ya'ni har biri uchun to'liq bo'lmasligi zarur va etarli. F da T 0, T 1, L, S, M sinflari bu sinfga kirmaydigan kamida bitta funksiya mavjud.

Kerak... F to'liq sistema bo'lsin. Aytaylik, F ko'rsatilgan sinflardan birida mavjud; biz uni K bilan belgilaymiz, ya'ni F Í K. Oxirgi kiritish mumkin emas, chunki K - to'liq tizim bo'lmagan yopiq sinf.

Adekvatlik... F = (f i) funksiyalar tizimi T 0, T 1, L, S, M beshta yopiq sinfning hech biriga toʻliq kiritilmasin. F funksiyalarni qabul qiling:

Keyin, asosiy lemma asosida (Lemma 2.10 ) 0 ni saqlamaydigan funksiyadan, 1 ni saqlamaydigan o‘z-o‘zidan ikkilangan va monoton bo‘lmagan funksiyadan 0, 1 konstantalarini va inkor funksiyasini olishimiz mumkin:

.

Chiziqli bo'lmagan funktsiyaga asoslangan lemma (lemma 2.9 ) konstantalar, inkor va chiziqli bo'lmagan funksiyalardan bog'lanishni olishingiz mumkin:

.

Funktsional tizim - mantiq algebrasining har qanday funktsiyasini mukammal dis'yunktiv normal shakl ko'rinishida ifodalash imkoniyati to'g'risidagi teorema bo'yicha to'liq tizim (dizyunksiyani konyunksiya va inkor ko'rinishida ifodalash mumkinligiga e'tibor bering). ).

Teorema to'liq isbotlangan. ð

Misollar.

1. f (x, y) = x |y funksiya to`liq sistemani tashkil qilishini ko`rsatamiz. X½y funksiya qiymatlari jadvalini tuzamiz:

f (0,0) = 1, shuning uchun x | yÏT 0.

f (1,1) = 0, shuning uchun x | yÏT 1.

f (0,0) = 1, f (1,1) = 0, demak, x | yÏM.

f (0,1) = f (1,0) = 1, - qarama-qarshi to'plamlarda x | y bir xil qiymatlarni oladi, shuning uchun x | yÏS.

Va nihoyat, funktsiyaning chiziqli emasligi nimani anglatadi
x | y.

To'liqlik mezoniga asoslanib, f (x, y) = x | y yaxlit tizimni tashkil qiladi. ð

2. Funktsiyalar sistemasini ko'rsataylik yaxlit tizimni tashkil qiladi.

Haqiqatan ham, .

Shunday qilib, tizimimizning funktsiyalari orasida biz topdik: 0 ni saqlamaydigan funktsiya, 1 ni saqlamaydigan funksiya, o'z-o'zidan ikkilangan, monoton bo'lmagan va chiziqli bo'lmagan funktsiyalar. To'liqlik mezoniga asoslanib, funktsiyalar tizimi ekanligini ta'kidlash mumkin yaxlit tizimni tashkil qiladi. ð

Shunday qilib, biz to'liqlik mezoni konstruktiv va berishiga ishonch hosil qildik samarali usul mantiq algebrasining funksiyalar sistemalarining to`liqligini oydinlashtirish.

Keling, to'liqlik mezonining uchta natijasini shakllantiramiz.

Xulosa 1... Butun mantiqiy funktsiyalar to'plamiga (K¹P 2) to'g'ri kelmaydigan mantiqiy funktsiyalarning har qanday yopiq K sinfi tuzilgan yopiq sinflarning kamida bittasida mavjud.

Ta'rif. Yopiq K sinfi deyiladi oldindan to'la agar K to'liq bo'lmasa va har qanday fÏ K funksiya uchun K È (f) klassi to'liq bo'ladi.

Ta'rifdan kelib chiqadiki, precomplete sinf yopiq.

Xulosa 2. Mantiq algebrasida faqat beshta oldindan to'liq sinflar mavjud, xususan: T 0, T 1, L, M, S.

Natijani isbotlash uchun faqat ushbu sinflarning hech biri ikkinchisida mavjud emasligini tekshirish kerak, bu, masalan, funktsiyalarning turli sinflarga tegishliligi haqidagi quyidagi jadval bilan tasdiqlangan:

Xulosa 3. Har qanday to'liq funktsiyalar tizimidan to'rtta funktsiyadan ko'p bo'lmagan to'liq quyi tizimni ajratish mumkin.

To'liqlik mezonining isbotidan kelib chiqadiki, beshdan ortiq funktsiyani ajratib bo'lmaydi. Asosiy lemmaning isbotidan (lemma 2.10 ) shundan kelib chiqadi o'z-o'zidan ikkilanmaydi yoki birlikni saqlamaydi va monoton emas. Shuning uchun to'rtdan ortiq funktsiya kerak emas.

Qurilish funktsiyasi

Sizning e'tiboringizga barcha huquqlar kompaniyaga tegishli bo'lgan onlayn funktsional diagrammalarni chizish bo'yicha xizmatni taqdim etamiz Desmos... Funktsiyalarni kiritish uchun chap ustundan foydalaning. Siz uni qo'lda yoki oynaning pastki qismidagi virtual klaviatura yordamida kiritishingiz mumkin. Grafik yordamida oynani kattalashtirish uchun siz chap ustunni ham, virtual klaviaturani ham yashirishingiz mumkin.

Onlayn diagrammaning afzalliklari

• Kiritilgan funksiyalarni vizual ko'rsatish
• Juda murakkab grafiklarni yaratish
• Bevosita berilgan grafiklarni yaratish (masalan, ellips x ^ 2/9 + y ^ 2/16 = 1)
• Diagrammalarni saqlash va ularga havolani olish imkoniyati, bu Internetda hamma uchun mavjud bo'ladi
• Masshtabni boshqarish, chiziq rangi
• Konstantalardan foydalanib, nuqtalar bo'yicha grafiklarni chizish imkoniyati
• Bir vaqtning o'zida bir nechta funktsiyalar grafiklarini qurish
• Qutbli koordinatalarda chizish (r va th (\ teta) dan foydalaning)

Biz bilan har xil murakkablikdagi jadvallarni onlayn tarzda qurish oson. Qurilish darhol amalga oshiriladi. Xizmat funktsiyalarning kesishish nuqtalarini topish, ularning keyingi harakatlanishi uchun grafiklarni ko'rsatish uchun talab qilinadi Word hujjati masalalarni yechish, funksiyalar grafiklarining xulq-atvor xususiyatlarini tahlil qilish uchun illyustratsiyalar sifatida. Saytning ushbu sahifasida diagrammalar bilan ishlash uchun optimal brauzer hisoblanadi Gugl xrom... Boshqa brauzerlar bilan ishlash kafolatlanmaydi.

Mavzu: “Funksiya: tushunchasi, topshiriq berish usullari, asosiy xarakteristikalari. Teskari funksiya. Funktsiyalarning superpozitsiyasi."

Dars epigrafi:

“Biror narsani o'rganing va o'ylamang

Bu mutlaqo foydasiz ekanligini bilib oldim.

O'rganmasdan biror narsa haqida o'ylash

Dastlabki fikrlash mavzusi -

Konfutsiy.

Darsning maqsadi va psixologik-pedagogik vazifalari:

1) Umumiy ta'lim (me'yoriy) maqsad: o‘quvchilar bilan funksiyaning ta’rifi va xossalarini takrorlash. Funksiyalarning superpozitsiyasi tushunchasini kiriting.

2) Talabalarning matematik rivojlanishi muammolari: nostandart o'quv va matematik materiallar bo'yicha, talabalarning aqliy tajribasini, ularning matematik intellektning mazmunli kognitiv tuzilishini, shu jumladan mantiqiy-deduktiv va induktiv, analitik va sintetik teskari fikrlash qobiliyatini, algebraik va majoziy- grafik fikrlash, mazmunli umumlashtirish va konkretlashtirish, o'quvchilarning metakognitiv qobiliyati sifatida aks ettirish va mustaqillik uchun; ta'lim va matematik intellektning psixologik mexanizmlari sifatida yozma va og'zaki nutq madaniyatini rivojlantirishni davom ettirish.

3) Tarbiyaviy vazifalar: talabalarda matematikaga kognitiv qiziqish, mas'uliyat, burch tuyg'usi, akademik mustaqillik, guruh, o'qituvchi, guruhdoshlar bilan hamkorlik qilish qobiliyatiga ega shaxsiy ta'limni davom ettirish; raqobatbardosh o'quv va matematik faoliyat uchun avtogogik qobiliyat, yuqori va yuqori natijalarga intilish (akmeik motiv).

Dars turi: yangi materialni o'rganish; yetakchi matematik mazmun mezoniga ko‘ra – amaliy dars; talabalar va o'qituvchi o'rtasidagi axborot o'zaro ta'siri turi mezoniga ko'ra - hamkorlik darsi.

Dars jihozlari:

1. O‘quv adabiyotlari:

1) Kudryavtsev matematik tahlil: Darslik. universitet va universitet talabalari uchun. 3 jildda V. 3. - 2-nashr, Qayta ishlangan. va qo'shing. - M .: Yuqori. shk., 1989 .-- 352 b. : kasal.

2) Matematik analizda Demidovich topshiriqlari va mashqlari. - 9-nashr. - M .: "Fan" nashriyoti, 1977 yil.

2. Rasmlar.

Darslar davomida.

1.Mavzu va darsning asosiy tarbiyaviy maqsadini e’lon qilish; o'quvchilarning mashg'ulotga tayyorgarlik ko'rishda burch, mas'uliyat, kognitiv qiziqish hissini rag'batlantirish.

2. Savollar bo'yicha materialni takrorlash.

a) Funksiyaning ta’rifini bering.

Asosiy matematik tushunchalardan biri funksiya tushunchasidir. Funksiya tushunchasi ikki to‘plam elementlari o‘rtasida bog‘lanishni o‘rnatish bilan bog‘liq.

Ikki bo'sh bo'lmagan to'plam berilsin va. Har bir elementga bitta va faqat bitta element bilan mos keladigan f moslashuvi deyiladi funktsiyasi va y = f (x) yoziladi. Ular f funktsiyani ham aytishadi ko'rsatadi ko'pdan ko'pga.

https://pandia.ru/text/79/018/images/image003_18.gif "width =" 63 "height =" 27 ">. gif" width = "59" balandligi = "26"> chaqirildi ko'p ma'nolar f funksiya va E (f) bilan belgilanadi.

b) Sonli funksiyalar. Funktsiya grafigi. Funksiyalarni sozlash usullari.

Funktsiya berilgan bo'lsin.

Agar va to'plamlarning elementlari haqiqiy sonlar bo'lsa, f funktsiyasi chaqiriladi raqamli funktsiya ... Bunday holda, x o'zgaruvchisi chaqiriladi dalil yoki mustaqil o'zgaruvchi, va y funktsiyasi yoki qaram o'zgaruvchi(x dan). x va y kattaliklarning o'zlari ichida bo'lgan deyiladi funktsional bog'liqlik.

Funktsiya grafigi y = f (x) Oxy tekislikning barcha nuqtalari to'plami deb ataladi, ularning har biri uchun x argumentning qiymati, y esa funktsiyaning mos keladigan qiymatidir.

y = f (x) funktsiyani aniqlash uchun siz x ni bilib, y ning mos keladigan qiymatini topishga imkon beradigan qoidani ko'rsatishingiz kerak.

Ko'pincha funktsiyani aniqlashning uchta usuli mavjud: analitik, jadvalli, grafik.

Analitik usul: Funktsiya bir yoki bir nechta formulalar yoki tenglamalar sifatida ko'rsatilgan.

Masalan:

Agar y = f (x) funktsiyaning sohasi aniqlanmagan bo'lsa, u tegishli formula mantiqiy bo'lgan barcha argument qiymatlari to'plamiga to'g'ri keladi deb taxmin qilinadi.

Funktsiyani aniqlashning analitik usuli eng mukammal hisoblanadi, chunki u y = f (x) funktsiyasini to'liq tekshirish imkonini beradigan matematik tahlil usullari bilan birga keladi.

Grafik usul: Funktsiya grafigini o'rnatadi.

Grafik topshiriqning afzalligi uning ravshanligi, kamchiligi uning noaniqligidir.

Jadval usuli: funktsiya bir qator argument qiymatlari va mos keladigan funktsiya qiymatlari jadvali bilan belgilanadi. Masalan, trigonometrik funktsiyalar qiymatlarining taniqli jadvallari, logarifmik jadvallar.

v) Funksiyaning asosiy xarakteristikalari.

1. D to'plamda aniqlangan y = f (x) funksiya chaqiriladi hatto shartlar bajarilsa va f (-x) = f (x); g'alati shartlar bajarilsa va f (-x) = -f (x).

Juft funktsiyaning grafigi Oy o'qiga nisbatan simmetrik, toq esa koordinatali. Masalan, - juft funktsiyalar; va y = sinx, https://pandia.ru/text/79/018/images/image014_3.gif "width =" 73 "height =" 29 "> - umumiy funktsiyalar, ya'ni toq va toq ...

2. D to'plamda y = f (x) funksiya aniqlansin va bo'lsin. Agar argumentlarning har qanday qiymatlari uchun tengsizlik tengsizlikni nazarda tutsa: , keyin funksiya chaqiriladi ortib boradi to'plamda; agar , keyin funksiya chaqiriladi kamaymaydigan https://pandia.ru/text/79/018/images/image021_1.gif "width =" 117 "height =" 28 src = "> keyin funksiya chaqiriladi. kamayib borayotgan ustida ; - oshmaydigan .

To‘plamdagi ortib boruvchi, o‘smaydigan, kamayuvchi va kamaymaydigan funksiyalar https://pandia.ru/text/79/018/images/image023_0.gif "width =" 13 "height =" 13 "> D qiymati (x + T) D va f (x + T) = f (x) tengligi bajariladi.

T davrining davriy funksiyasining grafigini tuzish uchun uni T uzunlikdagi istalgan segmentga chizish va uni butun ta’rif sohasi bo‘ylab davriy ravishda davom ettirish kifoya.

Davriy funktsiyaning asosiy xossalarini qayd qilaylik.

1) Davriy funksiyalarning algebraik yig‘indisi T davri bir xil bo‘lgan davriy funksiyadir.

2) Agar f (x) funksiya T davriga ega bo'lsa, f (ax) funksiya T / a davriga ega.

d) Teskari funksiya.

D ta'rif sohasi va E..gif "width =" 48 "height =" 22 "> qiymatlar to'plamiga ega y = f (x) funksiya berilsin, keyin x = z (y) funktsiya berilsin. ta'rif sohasi E va qiymatlar to'plami bilan D . Bunday funktsiya z (y) deb ataladi teskari f (x) funksiyasiga va quyidagi shaklda yoziladi: ... y = f (x) va x = z (y) funktsiyalari o'zaro teskari deyiladi. y = f (x) funksiyaga teskari x = z (y) funksiyani topish uchun x uchun f (x) = y tenglamani yechish kifoya.

ga misollar:

1. y = 2x funksiya uchun teskari funksiya x = ½ y funksiyadir;

2. Funktsiya uchun teskari funksiya funktsiyadir.

Teskari funktsiyaning ta'rifidan kelib chiqadiki, y = f (x) funksiya faqat va agar f (x) D va E to'plamlar o'rtasida birma-bir moslikni aniqlasa, teskari funktsiyaga ega. Demak, har qanday qat'iy monoton funksiya teskari funktsiyaga ega ... Bundan tashqari, agar funktsiya oshsa (kamaysa), keyin teskari funktsiya ham ortadi (kamayadi).

3. Yangi materialni o'rganish.

Murakkab funktsiya.

y = f (u) funksiya D to‘plamda, u = z (x) funksiya to‘plamda va mos qiymat uchun aniqlansin. ... Keyin to'plamda u = f (z (x)) funksiya aniqlanadi, u chaqiriladi murakkab funktsiya x dan (yoki superpozitsiya berilgan funksiyalar yoki funktsiya funksiyasi ).

u = z (x) o'zgaruvchisi chaqiriladi oraliq argument murakkab funktsiya.

Masalan, y = sin2x funksiya y = sinu va u = 2x ikkita funksiyaning superpozitsiyasidir. Murakkab funktsiya bir nechta oraliq argumentlarga ega bo'lishi mumkin.

4. Doskada bir nechta misollarni yechish.

5. Darsni yakunlash.

1) amaliy darsning nazariy va amaliy natijalari; talabalarning aqliy tajriba darajasini tabaqalashtirilgan baholash; ularning mavzuni o'zlashtirish darajasi, malakasi, og'zaki va yozma matematik nutqining sifati; namoyon bo'lgan ijodkorlik darajasi; mustaqillik va aks ettirish darajasi; tashabbuskorlik darajasi, matematik fikrlashning ayrim usullariga kognitiv qiziqish; hamkorlik darajalari, intellektual raqobat, o'quv va matematik faoliyatning yuqori ko'rsatkichlariga intilish va boshqalar;

2) asoslantirilgan baholarni, dars ballarini e'lon qilish.

Adabiyotlar:

1. Г. П.Гаврилов, А. А.Сапожников. Задачи и упражнения по дискретной математике: Учебное пособие. М: ФИЗМАТЛИТ, 2005, 416 с.

2. Кайзер Г.Дж. Комбинаторная математика. М.. Мир, 1966

3. 3. Емеличев В.А. и др. Лекции по теории графов. М.. Наука, 1990.

4.  Мендельсон Э. Введение в математическую логику. М., Наука, 1976.

5. Ёқубов Т. Математик логика элементлари. Тошкент, “Ўқитувчи”, 1983.

6. Тўраев Ҳ. Математик мантиқ ва дискрет математика. Самарқанд, 2003.

7. Гаврилов Г.П. и др. Сборник задач по дискретной математики. М.: Наука, 1977.

8. Зыков А.А. Основы теории графов. М., Наука, 1987.

9. Ершов Ю.Л. и др. Математическая логика. М., Наука, 1987