Mavzu: Funksional yopiq sinflar. Post teoremasi Reja: Funksional yopiq sinflar. Post teoremasi

t a ’ r i f . O‘z-o‘zidan va mantiq algebrasining hamma funksiyalari sinfidan ( P₂ dan) farq qiluvchi funksional yopiq sinflarga kirmaydigan xususiy funksional yopiq sinf maksimal funksional yopiq sinf deb ataladi.

Mantiq algebrasida hammasi bo‘lib beshta maksimal funksional yopiq sinf mavjud. Bular

quyidagilardir:
P₀ ,
P₁ , M , S , L .

Post²⁵ teoremasi. E. L. Post tomonidan funksiyalar sistemasi to‘liqligining yetarli va zarur shartlari topilgan.


²⁵ Post (Post Emil Leon, 1897 (Polsha) – 1954) – AQSh matematigi, mantiqchisi.

P o s t t e o r e m a s i .
  {φ₁,...,φ_n }
funksiyalar sistemasi to‘liq bo‘lishi uchun bu

sistemada
P₀ ,
P₁ , M , S , L maksimal funksional yopiq sinflarning har biriga kirmaydigan kamida

bitta funksiya mavjud bo‘lishi yetarli va zarur (ya’ni

  {φ₁,...,φ_n }

funksiyalar sistemasi faqat


P₀ ,


P₁ , M , S , L

maksimal funksional yopiq sinflardan birortasining ham qism to‘plami bo‘lmaganda va faqat shundagina to‘liq sistema bo‘ladi).
Post jadvali

I s b o t i . Zarurligi.
  {φ₁,...,φ_n }
to‘liq sistema (ya’ni

[]  P₂ ) va F maksimal funksional yopiq sinflarning birortasi bo‘lsin deb faraz qilamiz. U vaqtda F sinfning yopiqligini hisobga olib,

P₂[]  [F ]  F
munosabatni yozish mumkin, ya’ni
F  P₂ . Ammo

bunday bo‘lishi mumkin emas. Demak,   F
munosabat bajarilmaydi.

	P0	P1	S	L	M
φ1
φ 2
...	...	...	...	...	...
φn

Yetarliligi isbotini o‘quvchiga havola etamiz. ■
N a t i j a . Mantiq algebrasidagi har qanday funksional yopiq sinf
maksimal funksional yopiq sinflardan birortasining qism to‘plami bo‘ladi.


P₀ ,


P₁ , M , S , L

Amalda berilgan
  {φ₁,...,φ_n }
funksiyalar sistemasining to‘liq yoki to‘liq emasligini

aniqlash uchun Post jadvali deb ataluvchi jadvaldan foydalaniladi. Post jadvali quyida keltirilgan.
Jadvalning xonalariga o‘sha satrdagi funksiya funksional yopiq sinflarning elementi bo‘lsa

“+” ishora, bo‘lmasa “–” ishorasi qo‘yiladi.
 {φ₁,...,φ_n }
sistema to‘liq funksiyalar sistemasi

bo‘lishi uchun, Post teoremasiga asosan, jadvalning har bir ustunida kamida bitta “–” ishorasi bo‘lishi yetarli va zarur.

 {φ₁,...,φ_n }
funksiyalar sistemasi to‘liq bo‘lmasligi uchun
P₀ ,
P₁ , M , S , L maksimal

funksional yopiq sinflardan birortasining qism to‘plami bo‘lishi, ya’ni Post jadvalining biror ustunidagi barcha ishoralar “+” bo‘lishi kerak.
Funksiyalar sistemasining to‘liqligi tushunchasi bilan sinfning (to‘plamning) yopig‘i
tushunchasi o‘zaro bog‘langan.

2. 
   t a ’ r i f . A bilan P₂
   

(nta argumentli mantiq algebrasining hamma

funksiyalarini o‘z ichiga olgan) to‘plamning biror qism to‘plamini belgilaymiz. A to‘plam funksiyalarning superpozitsiyasidan hosil qilingan hamma Bul funksiyalari to‘plami ( A to‘plam funksiyalari orqali ifodalangan hamma bul funksiyalari to‘plami) A to‘plamning yopig‘i deb aytiladi va [A] kabi belgilanadi.

3- m i s o l . 1.
A  P₂
bo‘lsin, u holda [ A]  P₂ bo‘ladi.

2. A {1, x₁  x₂}
bo‘lsin, u holda A to‘plamning yopig‘i barcha chiziqli funksiyalar

to‘plamidan (ya’ni, L to‘plamdan) iborat bo‘ladi. ■
1- jadval

		P0	P1	S	L	M
a)	0	+	–	–	+	+
	xy	+	+	–	–	+
	x  y  z	+	+	+	+	–
b)	1	–	+	–	+	+
	xy	+	+	–	–	+
	x  y  z	+	+	+	+	–
d)	{x y  x z  y z}	–	–	+	–	–
e)	0	+	–	–	+	+
	1	–	+	–	+	+
	x  y	+	–	–	+	–
f)	0	+	–	–	+	+
	1	–	+	–	+	+
	xy	+	+	–	–	+

To‘plam yopig‘i quyidagi xossalarga ega:
1) [ A]  A ; 2) [[A]]  [ A] ;

3) agar
A₁  A₂
bo‘lsa, u holda [ A₁ ]  [ A₂ ] bo‘ladi;

4) [ A₁  A₂ ]  [ A₁ ] [ A₂ ]. ■

7- t a ’ r i f . Agar [ A]  A
bo‘lsa, u holda A to‘plam (sinf) funksional yopiq sinf deb ataladi.

4- m i s o l . 1.
A  P₂
funksional yopiq sinfdir.

2. 
   A {1, x₁  x₂} funksional yopiq sinf emas.
   

2. 
   L funksional yopiq sinfdir. ■
   

Osongina ko‘rish mumkinki, har qanday


[A]

funksional sinf yopiq sinf bo‘ladi. Bu hol

ko‘pgina funksional yopiq sinflarni topishga yordam beradi.
To‘plam yopig‘i va yopiq sinf tilida funksiyalar sistemasining to‘liqligi ta’rifini (avvalgi ta’rifga ekvivalent bo‘lgan ta’rifni) berish mumkin.
8- t a ’ r i f . Agar [ A]  P₂ bo‘lsa, u holda A funksiya-lar sistemasi to‘liq deb ataladi.
5- m i s o l . Quyidagi funksiyalar sistemalarining to‘liq emasligini Post jadvali vositasida isbot qilamiz (1- jadvalga qarang).
a) ₁  {0, xy, x  y  z} ; b) ₂  {1, xy, x  y  z};
d) ₃  {x y  x z  y z}; e) ₄  {0, 1, x  y};
f) ₅  {0, 1, xy}.
Post jadvalidan ko‘rinib turibdiki, yuqorida keltirilgan barcha funksiyalar sistemalari to‘liq emas, chunki har bir sistema uchun jadvalda bitta ustun faqatgina “+” ishoralaridan iborat. Shuni ham ta’kidlash kerakki, har bir sistema uchun bu ustunlar har xil.

Demak, Post teoremasi shartidan
P₀ ,
P₁ , M , S , L maksimal funksional yopiq sinflarning

birortasini ham olib tashlash mumkin emas. Bu xulosadan, o‘z navbatida,
P₀ ,
P₁ , M , S , L

2. 
   t a ’ r i f . Agar A sistemadagi funksiyalar superpozitsiyasidan hosil bo‘lgan funksiya ham shu sistemaning elementi bo‘lsa, u holda bunday sistema superpozitsiyaga nisbatan yopiq sistema deb ataladi.
   
3. 
   t a ’ r i f . Mantiq algebrasining superpozitsiyaga nisbatan yopiq bo‘lgan har qanday funksiyalar sistemasi funksional yopiq sinf deb ataladi.
   

Ravshanki, muayyan xususiyatga ega bo‘lgan funksiyalar sistemasi funksional yopiq sinfni tashkil etadi va, aksincha, ma’lum funksional yopiq sinfga kiruvchi funksiyalar bir xil xususiyatga ega bo‘lgan funksiyalardir. Quyidagi funksiyalar sistemasi funksional yopiq sinflarga misol bo‘la oladi:

3. 
   bir argumentli funksiyalar sinfi;
   
4. 
   mantiq algebrasining hamma funksiyalari sinfi;
   

4. 
   L – chiziqli funksiyalar sinfi;
   
5. 
   S – o‘z-o‘ziga ikki taraflama funksiyalar sinfi;
   
6. 
   M – monoton funksiyalar sinfi;
   

4. 
   P₀
   
5. 
   P₁
   

• 
  nul qiymatni saqlovchi funksiyalar sinfi;
  
• 
  bir qiymatni saqlovchi funksiyalar sinfi.
  

2.