Kurs ishi “Diskeret matematika va matematik mantiq” fanidan Mavzu: Funksiyalar sistemasining yopiqligi va to’liqligi

To’liq funksiyalar sistemasi.

Ikki taraflama funksiyalar sistemasining to’liq bo’lish sharti
Mantiq algebrasining F={ , ….. , } funksiyalar sistemasi berilgan bo’lsin.
1 -Ta’rif. Agar mantiq algebrasining istalgan funksiyasini F={ ₁, …., _n} sistemadagi funksiyalar superpozitsiyasi orqali ifodalash mumkin bo’lsa, u holda F to’liq funksiyalar sistemasi deb ataladi. Istalgan funksiyani MKNSH yoki MDNSH ko’rinishida ifodalash mumkunligidan {xy, x ˅ y, } funksiyalar sistemasining to’liqligi kelib chiqadi. {xy, x+y, 1} funksiyalar sistemasi ham to’liq bo’ladi, chunki istalgan funksiyani Jegalkin ko’pxadi ko’rinishiga keltirish mumkin.
Quyidagi funksiyalar sistemasining to’liqligini isbotlaymiz:
a) xy, ;
b) x ˅ y, ;
v) xy, x + y, 1;
g) ;
d) ;
i) x + y, x ˅ y, 1
j) x + y + z, xy, 0, 1;
k) x y, ;
l) x y, 0.
Isbot. a) x ˅ y = , ya’ni diz’yunksiya amalini kon’yunksiya va inkor amallari orqali ifodalash mumkun. Demak, {xy, } funksiyalar sistemasi to’liq bo’ladi: b)xy = = ekanligi ma’lum. Demak, istalgan mantiqiy funksiyani diz’yunksiya va inkor amallari orqali ifodalasa bo’ladi. Shuning uchun {x ˅ y, } funksiyalar sistemasi to’liqdir; v) mantiq algebrasining ixtiyoriy funksiyasini yagona Jegalkin ko’phadi ko’rinishiga keltirish mumkinligidan {xy, x + y, 1} funksiyalar sistemasining to’liqligi kelib chiqadi; g) va d) mantiq algebrasidagi istalgan funksiyani Ψ(x, y) = va
Sheffer funksiyalari orqali ifodalash mumkin. Xaqiqatan ham, = (x, x), x ˅ y = = = ( xy = ) =
Asosiy mantiqiy amallarni Shefer funksiyasi orqali ifodalash mumkin. Demak, { } va { } funksiyalar sistemasi to’liq bo’ladi. i) x˅y = xy+x+y bo’lganligi uchun x˅y+(x+y)=xy bo’ladi. {xy, x+y, 1} to’liq Sistema ekanligi v) bandda isbot qilingan edi, demak, {x+y, x˅y, 1} sistema to’liqdir. Xuddi shunday boshqa funksiyalar sistemasining to’liqligini isbot qilish mumkun. 1-teorema. Agar F={ ,…., } funksiyalar sistemasi to’liq bo’lsa, u holda ikki taraflama bo’lgan ={ ,…., } funksiyalar sistemasi ham to’liq bo’ladi.
Isbot. sistemaning to’liqligini isbotlash uchun istalgan ,…., ) funksiyani sistemasidagi funksiyalar superpozitsiyasi orqali ifodalash mumkunligini ko’rsatishimiz kerak. Buning uchun avval funksiyani F={ } sistemadagi funksiyalar orqali ifodalaymiz (F sistema to’liq bo’lganligi uchun bu protsedurani bajarish mumkin). Keyin ikki taraflama qonunga asosan ikki taraflama funksiyalar superpozitsiyasi orqali f funksiyani hosil qilamiz.