5 bilet To’plamga tegishlilik tushunchasi. To’plamlarning tengligi. Tа’rif Ikkita to’plam teng

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 maksima 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.


35


1) Turmushda ikki inson, aytaylik Barno va Nargizaning qarindoshligi haqida gapirganda shuni nazarda tutiladiki, shunday ikkita oila mavjud, Barno va Nargizaning shu oilalarga qandaydir aloqasi bor. Tartiblangan (Barno, Nargiza) juftligi boshqa tartiblangan kishilar juftligidan shunisi bilan farq qiladiki, ularning orasida opa-singillik yoki ona-qizlik, jiyanlik kabi munosabatlar bo’lishi mumkin.
Diskret matematikada ham dekart ko’paytmaning barcha tartiblangan juftliklari orasidan o’zaro qandaydir “qarindoshlik” munosabatlariga ega bo’lgan juftliklarni ajratib ko’rsatish mumkin. Ixtiyoriy ikki to’plamning elementlari orasidagi munosabatlar uchun binar munosabat tushunchasini kiritamiz. Bu tushuncha matematika kabi informatikada ham ko’p uchraydi. Bir nechta to’plam elementlari orasidagi munosabat ma’lumotlar jadvali shaklida beriladi. Ushbu bob tadbiqini ma’lumotlar bazasini boshqarish tizimini tasvirlashda ishlatiladigan n – ar munosabatlarda ko’rish mumkin.
Tа’rif . Agar n o‘rinli munosаbаtda n=1 bo`lsa, munosаbаt А<sub>1</sub> to‘plаmning qism to‘plаmi bo‘lаdi vа unаr munosаbаt (bir o`rinli munosabat) yoki xossа deyilаdi
Ba’zan n -ar munosabat iborasi o'rniga n o'rinli munosabat iborasi qo'llaniladi. Agar munosabat bir o'rinli bo'lsa, u holda u unar munosabat, ikki o'rinli bo'lganda esa binar munosabat deb ataladi. Unar munosabat xossa (xususiyat) deb ham yuritiladi. Adabiyotda, ko'pincha, 3-ar munosabat ternar munosabat deb nomlanadi.
2) 3.8.2. Asosiy mantiqiy amallarning chinlik to‘plamlari. Chinlik to‘plamlari mos ravishda va bo‘lgan va formulalar berilgan bo‘lsin.
Kon’yunksiyaning chinlik to‘plami. va formulalar kon’yunksiyasining chinlik to‘plami bo‘ladi. Haqiqatdan ham, kon’yunksiya ta’rifiga asosan, formula va formulalarning ikkalasi ham chin bo‘lgandagina chindir. Shuning uchun, formulaning chinlik to‘plami va to‘plamlarning umumiy elementlaridan tuzilgan kesishmasidan iborat bo‘ladi. Demak, mulohazalar mantiqidagi kon’yunksiya amaliga ( belgiga) to‘plamlar nazariyasidagi kesishma amali ( belgi) mos keladi (I bobning 2- paragrafidagi 2- shaklga qarang).
4- misol. va formulalarning chinlik to‘plamlari, mos
ravishda, va bo‘lgani uchun (2- va 3- misollarga qarang) kon’yunksiyaning chinlik to‘plami bo‘ladi. ■
Diz’yunksiyaning chinlik to‘plami. va formulalar diz’yunksiyasining chinlik to‘plami bo‘ladi. Haqiqatdan ham, diz’yunksiya ta’rifiga asosan, formula va formulalarning kamida bittasi chin bo‘lgandagina chindir. Demak, to‘plamda formula chindir. Shunday qilib, formulaning chinlik to‘plami va to‘plamlarning barcha elementlaridan, ularni takrorlamasdan, tuzilgan birlashmasidan iborat bo‘ladi. Demak, mulohazalar mantiqidagi diz’yunksiya ( ) amaliga to‘plamlar nazariyasidagi birlashma ( ) amali mos keladi
Implikasiyaning chinlik to‘plami. va formulalar implikasiyaning chinlik to‘plamini topamiz. formulaning chinlik to‘plami va formulaning chinlik to‘plami bo‘lgani uchun, teng kuchlilikka ko‘ra, formulaning chinlik to‘plami bo‘ladi. 1- shaklda tasvirlangan to‘plamning bo‘yalmagan qismi implikasiyaning chinlik to‘plamiga mos keladi.