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

Mavzu: Funksional yopiq sinflar. Post teoremasi
Reja:
1.Funksional yopiq sinflar.
2.Post teoremasi
Funksional yopiq sinflar.Mantiq algebrasining   {φ₁,...,φ _n } funksiyalar sistemasi berilgan bo‘lsin.
1.Ta`rif. Agar mantiq algebrasining istalgan funksiyasini   {φ₁,...,φ _n } sistemadagi funksiyalar superpozitsiyasi orqali ifodalash mumkin bo‘lsa, u holda Ф sistema to‘liq funksiyalar sistemasi deb ataladi.
Istalgan funksiyani MKNSh yoki MDNSh ko‘rinishida ifodalash mumkinligidan

{xy, x  y, x}
funksiyalar sistemasining to‘liqligi kelib chiqadi.
{xy, x  y, 1}
funksiyalar sistemasi

ham to‘liq bo‘ladi, chunki istalgan funksiyani Jegalkin ko‘phadi ko‘rinishiga keltirish mumkin.
1- m i s o l . Quyidagilar to‘liq funksiyalar sistemasi ekanligini isbotlaymiz:

a) xy, x ; b)
x  y, x ; d)
xy, x  y, 1;

e) x  y ; f) xy ; g) x  y, x  y, 1 ;

h) x  y  z, xy, 0, 1 ; i)
x  y, x ; j)
x  y, 0 .

1. 
   x  y  x y , ya’ni diz’yunksiya amalini kon’yunksiya va inkor amallari
   

orqali ifodalash mumkin. Demak, {xy, x} funksiyalar sistemasi to‘liqdir;

2. 
   xy  x  y
   

ekanligi ma’lum. Demak, istalgan mantiqiy funksiyani diz’yunksiya va inkor

amallari orqali ifodalasa bo‘ladi. Shuning uchun {x  y, x} funksiyalar sistemasi to‘liqdir;

4. 
   mantiq algebrasining ixtiyoriy funksiyasini yagona Jegalkin ko‘phadi ko‘rinishiga keltirish mumkin bo‘lgani uchun {xy, x  y, 1} funksiyalar sistemasi
   

to‘liqdir.

4. 
   va f) mantiq algebrasidagi istalgan funksiyani
   

ψ ( x, y)  xy

va φ(x, y)  x  y

Sheffer

funksiyalari orqali ifodalash mumkin. Haqiqatan ham,
x  φ(x, x) ,

x  y  x  y  φ(x, y)  φ (φ(x, y),φ(x, y))
va
xy  φ (x, y)  φ(φ (x, x),φ( y, y))

asosiy mantiqiy amallarni Sheffer funksiyasi orqali ifodalash mumkin. Demak, funksiyalar sistemalari to‘liqdir.

{x  y}

va {xy}

g) x  y  xy  x  y
bo‘lgani uchun
x  y (x  y)  xy bo‘ladi.
{xy, x  y, 1}
to‘liq sistema ekanligi

4. 
   bandda isbot qilingan edi, demak, {x  y, x  y, 1} sistema to‘liqdir.
   

Xuddi shunday qolgan h), i) va j) funksiyalar sistemalarining to‘liqligini ham isbot qilish mumkin. Bu ish o‘quvchiga havola qilinadi. ■

1. 
   t e o r e m a . Agar
   

  {φ₁,...,φ_n }
funksiyalar sistemasi to‘liq bo‘lsa, u holda unga ikki

taraflama bo‘lgan ^*  {φ^*,...,φ ^*} funksiyalar sistemasi ham to‘liq bo‘ladi.
1 n

I s b o t i . ^*
sistemaning to‘liqligini isbotlash uchun istalgan
f (x₁,..., x_n )
funksiyani ^*

sistemasidagi funksiyalar superpozitsiyasi orqali ifodalash mumkinligini ko‘rsatish kerak. Buning

uchun avval
f ^* funksiyani
  {φ₁,...,φ _n }
sistemadagi funksiyalar orqali ifodalaymiz (  sistema

to‘liq bo‘lgani uchun bu protsedurani bajarish mumkin). Keyin ikki taraflama qonunga asosan ikki taraflama funksiyalar superpozitsiyasi orqali f funksiyani hosil qilamiz. ■

2. 
   m i s o l . Quyidagilar to‘liq funksiyalar sistemasi emasligini isbotlaymiz:
   

a) x, 1 ; b)
e) xy  yz  xz, x ; f) xy, x  y ; d) xy  yz  xz, 0, 1.

1. 
   x  x  1 bo‘lgani uchun {x, 1} sistemadagi funksiyalar bir argumentli funksiyalar bo‘ladi.
   

Bizga ma’lumki, bir argumentli funksiyalarning superpozitsiyasi natijasida hosil qilingan funksiya ham bir argumentli funksiya bo‘ladi. Natijada, bu sistemadagi funksiyalar orqali ko‘p argumentli funksiyalarni ifodalab bo‘lmaydi. Shuning uchun {x, 1} – to‘liq funksiyalar sistemasi emas.

2. 
   {xy, x  y}
   

sistemadagi funksiyalarning ikkalasi ham monotondir. Monoton

funksiyalarning superpozitsiyasi orqali hosil qilingan funksiya ham monoton bo‘lishi isbotlangan edi. Demak, bu ikkala funksiyaning superpozitsiyasi orqali monoton bo‘lmagan funksiyalarni ifodalash mumkin emas va natijada, {xy, x  y} – to‘liq funksiyalar sistemasi emas.

4. 
   {x  y, x}
   

sistemadagi funksiyalar chiziqli funksiyalardir. Shuning uchun bu funksiyalar

orqali chiziqlimas funksiyalarni ifodalab bo‘lmaydi. Demak, {x  y,

emas.
x} – to‘liq funksiyalar sistemasi rqali ifodalash mumkin. Demak, {xy, x} funksiyalar sistemasi to‘liqdir;

3. 
   xy  x  y
   

ekanligi ma’lum. Demak, istalgan mantiqiy funksiyani diz’yunksiya va inkor

amallari orqali ifodalasa bo‘ladi. Shuning uchun {x  y, x} funksiyalar sistemasi to‘liqdir;

4. 
   mantiq algebrasining ixtiyoriy funksiyasini yagona Jegalkin ko‘phadi ko‘rinishiga keltirish mumkin bo‘lgani uchun {xy, x  y, 1} funksiyalar sistemasi
   

to‘liqdir.

4. 
   va f) mantiq algebrasidagi istalgan funksiyani
   

ψ ( x, y)  xy

va φ(x, y)  x  y

Sheffer

funksiyalari orqali ifodalash mumkin. Haqiqatan ham,
x  φ(x, x) ,

x  y  x  y  φ(x, y)  φ (φ(x, y),φ(x, y))
va
xy  φ (x, y)  φ(φ (x, x),φ( y, y))

asosiy mantiqiy amallarni Sheffer funksiyasi orqali ifodalash mumkin. Demak, funksiyalar sistemalari to‘liqdir.

{x  y}

va {xy}

g) x  y  xy  x  y
bo‘lgani uchun
x  y (x  y)  xy bo‘ladi.
{xy, x  y, 1}
to‘liq sistema ekanligi

4. 
   bandda isbot qilingan edi, demak, {x  y, x  y, 1} sistema to‘liqdir.
   

Xuddi shunday qolgan h), i) va j) funksiyalar sistemalarining to‘liqligini ham isbot qilish mumkin. Bu ish o‘quvchiga havola qilinadi. ■

1.