|
Лаборатория2
|
| bet | 3/5 | | Sana | 04.01.2024 | | Hajmi | 0,86 Mb. | | #129980 |
Bog'liq mustaqil ish DT (1)1.2 Post teoremasi. funksiyalar sistemasining tulikligi uchun bu sistemada , , , , maksimal funksional yopik sinflarning xar biriga kirmovchi kamida bitta funksiya mavjud bulishi yetarli va zarur (ya’ni shunda va fakat shundagina tulik sistema buladiki, kachonki u , , , , maksimal funksional yopik sinflarning birortasining xam kism tuplami bulmasa).
Isbot. tulik sistema bulsin, ya’ni . Faraz kilamizki, maksimal funksional yopik sinflarning birortasi. U vaktda ning yopikligini xisobga olib, ni yozish mumkin, ya’ni . Ammo bunday bulishi mumkin emas. Demak, munosabat bajarilmaydi.
Teoremaning yetarliligining isbotini ukuvchilarga xavola etamiz.
Natija. Mantik algebrasidagi xar kanday funksional yopik sinf , , , , maksimal funksional yopik sinflarning birortasining kism tuplami buladi.
Amalda birorta sistemaning tulik yoki tulik emasligini aniklash uchun Post jadvalidan foydalanadilar. Post jadvali kuyidagi kurinishda buladi:
Jadvalning xonalariga usha satrdagi funksiya funksional yopik sinflarning elementi bulsa “+” ishora, bulmasa “-” ishorasi kuyiladi.
sistema tulik funksiyalar sistemasi bulishi uchun, teoremaga asosan, jadvalning xar bir ustunida kamida bitta “-” ishorasi bulishi yetarli va zarur.
funksiyalar sistemasi tulik bulmasligi uchun , , , , maksimal funksional yopik sinflarning birortasining kism tuplami bulishi, ya’ni Post jadvalining biror ustuni tulik “+” ishoralaridan iborat bulishi kerak.
Funksiyalar sistemasining tulikligi tushunchasi bilan sinfning (tuplamning) yopigi tushunchasi uzaro boglangan.
6-ta’rif. bilan (n argumentli mantik algebrasining xamma funksiyalarini uz ichiga olgan) tuplamning biror kism tuplamini belgilaymiz. tuplam funksiyalarning superpozitsiyasidan xosil etilgan xamma bul funksiyalari tuplami ( tuplam funksiyalari orkali ifodalangan xamma bul funksiyalari tuplam)ga tuplamning yopigi deb aytiladi va [ ] kabi belgilanadi.
Misol. 1. = bulsin, u xolda [ ]= .
2. ={ } bulsin, u vaktda tuplamning yopigi xamma - chizikli funksiyalar tuplamidan iborat buladi.
Tuplam yopigi kuyidagi xossalarga ega:
1. [ ] Ê ;
2. [[ ]] = [ ];
3. agar 1 Í 2 bulsa, u xolda [ 1] Í [ 2] buladi;
4. [ 1 2] Ê [ 1] [ 2].
7-ta’rif. Agar [ ]= bulsa, u xolda tuplam (sinf)ga funksional yopik sinf deb aytiladi.
Misol. 1. = sinfi yopik sinf buladi.
2. ={ } cinfi yopik sinf bulmaydi.
3. - sinfi yopik sinf buladi.
Osongina kurish mumkinki, xar kanday [ ] sinf yopik sinf buladi. Bu xol kupgina funksional yopik sinflarni topishga yordam beradi.
Tuplam yopigi va yopik sinf tilida funksiyalar sistemasining tulikligi xakidagi ta’rif (avvalgi ta’rifga ekvivalent bulgan ta’rif) ni berish mumkin.
8-ta’rif. Agar [ ]= bulsa, u xolda funksiya-lar sistemasi tulik deb aytiladi.
Misol. Kuyidagi funksiyalar sistemalarining tulik emasligini Post jadvali orkali isbot kilaylik:
a) ; b) ;
v) ; g) ;
d)
|
|
|
|
|
|
|
a)
|
|
+
|
-
|
-
|
+
|
+
|
|
|
+
|
+
|
-
|
-
|
+
|
|
|
+
|
+
|
+
|
+
|
-
|
|
|
|
|
|
|
|
b)
|
|
-
|
+
|
-
|
+
|
+
|
|
|
+
|
+
|
-
|
-
|
+
|
|
|
+
|
+
|
+
|
+
|
-
|
|
|
|
|
|
|
|
v)
|
|
-
|
-
|
+
|
-
|
-
|
|
|
|
|
|
|
|
g)
|
|
+
|
-
|
-
|
+
|
+
|
|
|
-
|
+
|
-
|
+
|
+
|
|
|
+
|
-
|
-
|
+
|
-
|
|
|
|
|
|
|
|
d)
|
|
+
|
-
|
-
|
+
|
+
|
|
|
-
|
+
|
-
|
+
|
+
|
|
|
+
|
+
|
-
|
-
|
+
|
Jadvaldan kurinib turibdiki, yukorida keltirilgan xamma funksiyalar sistemasi tulik emas, chunki xar bir sistema uchun jadvalda bitta ustun fakatgina “+” ishoralaridan iborat. Shuni ta’kidlashimiz kerakki, xar bir sistema uchun bu ustunlar xar xil. Demak, Post teoremasi shartidan , , , , maksimal funksional yopik sinflarning birortasini xam olib tashlash mumkin emas. Bu xulosadan uz navbatida , , , , maksimal funksional yopik sinflarning birortasi ikkinchisining kism tuplami bula olmasligi kelib chikadi.
1.3 Berilgan misol yordamida amaliy ko‘rsatmalar.
F={ } funksiyalar sinfining to‘liqligini Post jadvali yordamida tekshiring.
1-kadam. Post jadvali orqali berilgan funksiyalar sinfini to‘liqligini tekshirish uchun, sistemadagi barcha funksiyalarning chinlik jadvalini tuzamiz
|
|
|
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
2- kadam. Berilgan funksiyalarning P0 , P1, L, S, M funksional yopiq sinflarga tegishliligini yuqoridagi chinlik jadvalidan aniqlaymiz.Funksiyamiz P0 –nol saqlovchi funksiyalar sinfiga kirishi uchun argumentlarning barchasi bir vaqtda yolђon qiymat qabul qilganda funksiya ќam yolђon qiymat qabul qilishi kerak. Chinlik jadvalidan ko‘rinib turibdiki faqat funksiya nol saqlovchi, qolgan funksiyalarimiz nol saqlovchi emas. Post jadvalida mos ustunni to‘ldiramiz.
3- kadam. Funksiya P1 –bir saqlovchi funksiyalar sinfiga kirishi uchun argumentlarning barchasi bir vaqtda chin qiymat qabul qilganda funksiya ќam chin qiymat qabul qilishi kerak. Chinlik jadvalidan ko‘rinib turibdiki faqat funksiya bir saqlovchi emas, qolgan funksiyalarning barchasi bir saqlovchi. Post jadvalida mos ustunni to‘ldiramiz.
|
P0
|
P1
|
L
|
S
|
M
|
|
+
|
+
|
|
|
|
|
-
|
+
|
|
|
|
|
-
|
-
|
|
|
|
1
|
-
|
+
|
|
|
|
4- kadam Endi sistemadagi funksiyalarni L- chiziqli funksiyalar sinfiga tegishli yoki tegishli emasligini tekshiramiz. Buning uchun funksiyalarning Jegalkin ko‘pќadi ko‘rinishini xosil qilamiz. Ko‘pќadda ko‘paytirish amali ishtirok etmasa, bunday funksiya chiziqli bo‘ladi
Ko‘rinib turibdiki va funksiyalar chiziqli emas, va 1 chizikli. Post jadvalida mos ustunni to‘ldiramiz
|
P0
|
P1
|
L
|
S
|
M
|
|
+
|
+
|
-
|
|
|
|
-
|
+
|
-
|
|
|
|
-
|
-
|
+
|
|
|
1
|
-
|
+
|
+
|
|
|
5- kadam. Chinlik jadvali yordamida funksiyalarning S-o‘z –o‘ziga qo‘shma funksiyalar sinfiga kirishini tekshiramiz. Buni 3 xil usulda amalga oshirish mumkin
1-usul. Chinlik jadvalida funksiyalarni qiymatlari satrini chiziq bilan o‘rtasidan ajratib, shu chiziqqa nisbatan qiymatlarning simmetrikligini tekshiramiz
|
|
|
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
2- usul. Chinlik jadvalida funksiya kiymatlirini teskari œgirib, (kushmalik prinsipiga kœra) inkorlarini olganda funksiyaning chinlik kiymati bilan mos tushsa, bu funksiya œz-œziga qœshma bœladi
3-usul. funksiyaga qœshma funksiyani topish uchun funksiyaning barcha œzgaruvchilarini va funksiyani inkorini topish kerak. Agar = bœlsa, funksiya œz-œziga ikkitaraflama yoki œz-œziga qœshma funksiya deyiladi
, demak bu funksiya œz-œziga qœshma emas.
, demak bu funksiya œz-œziga qœshma emas.
bu xolda, bu funksiya œz-œziga qœshma funksiya bœladi.
1 ga qœshma funksiya 0 bœladi
|
P0
|
P1
|
L
|
S
|
M
|
|
+
|
+
|
-
|
-
|
|
|
-
|
+
|
-
|
-
|
|
|
-
|
-
|
+
|
+
|
|
1
|
-
|
+
|
+
|
-
|
|
6- kadam. Funksiyalar sistemasidagi funksiyalarni monotonligini tekshiramiz. Funksiya monoton bœlishi uchun barcha larda shart bajarilishi kerak. Chinlik jadvalidan kœrinib turibdiki monoton, nomonoton, nomonoton, 1 monoton bœladi.
|
P0
|
P1
|
L
|
S
|
M
|
|
+
|
+
|
-
|
-
|
+
|
|
-
|
+
|
-
|
-
|
-
|
|
-
|
-
|
+
|
+
|
-
|
1
|
-
|
+
|
+
|
-
|
+
|
Post jadvalning barcha ustunlarida kamida bittadan «-» ishora qatnashgan, ya’ni maksimal funksionol sinflarga kirmaydigan kamida bittadan funksiya mavjud. Demak kœrilgan funksiyalar sistemasi tœliq.
|
| |
