Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnalogiyalari

Muhammad al-Xorazmiy nomidagi
Toshkent Axborot Texnalogiyalari
Universiteti Samarqand filiali Kompyuter
injineringi fakulteti

KI 22-01 guruhi talabasi Husan Jurayev ning

Diskret tuzilmalar fanidan
1-mustaqil ish topshirig’i.

Bajardi: Husan Jurayev Mamasharip o’g’li.

Tekshirdi: Saidov.O’.M.

Samarqand 2023

Mavzu: To’plamlar kesishmasi va birlashmasi qonunlari.

To'plamlarning birlashmasi.

Har qanday ikkita to'plamning barcha elementlaridan, ularni A[] B takrorlamasdan, tuzilgan to'plamga shu to'plamlarning birlashmasi (yoki yig'indisi) deb aytiladi.
Bu ta'rifdan ko'rinib turibdiki, to'plamlarning umumiy elementlari shu to'plamlarning birlashmasiga faqat bir martadan
1- kiritiladi. Berilgan to'plamlarning birlashmasidagi har qanday element shu to'plamlarning hech bo'lmaganda bittasiga tegishlidir. A va B to'plamlarning birlashmasi A U B kabi belgilanadi. Bu yerda "A va B to'plamlarga birlashma amalini qo'llab (yoki A va B to'plamlar ustida birlashma amali bajarilib), A U B to'plam hosil qilindi" deyish mumkin. 1-shaklda A va B to'plamlar doiralar ko'rinishida, A U B to'plam esa bo'yab tasvirlangan.
1- misol. A = {a,b}, B = {a,b,c} va C = {e,f,k} bo'lsin. U holda E = A U B = {a, b, c}, E U C = {a, b, c, e, f, k}, C U B = {a, b, c, e, f, k}, A U C = {a, b, e, f, k} bo'ladi. ■
2- misol. O'zbekiston Respublikasining yoshi 16dan 25gacha bo'lgan fuqarolari to'plamini A bilan, yoshi 21dan 30gacha bo'lgan fuqarolari to'plamini esa B bilan belgilasak, A va B to'plamlarning A U B birlashmasi O'zbekiston Respublikasining yoshi 16dan 30gacha bo'lgan fuqarolari to'plamini tashkil etadi. ■
3- misol. N U R = R. ■
Shuni ta'kidlash kerakki, to'plamlar bilan bog'liq tushunchalar va ular ustidagi amallar, mos ravishda, sonlar bilan bog'liq tushunchalar va oddiy arifmetik amallar bilan qiyoslanadi. Jumladan, to'plamlar yig'indisini (birlashmasini) topish amali sonlarni qo'shish amali bilan qiyoslanadi. Bunday qiyoslashlar, ko'pincha, bir-biriga o'xshash natijalarning mavjudligini ko'rsatadi, ba'zan esa ular to'plamlarning farqli xususiyatlarga egaligini namoyon etadi. Masalan, ixtiyoriy A va B to'plamlar uchun A œ B bo'lsa, u holda A U B = B va B U A = B bo'ladi, lekin, ixtiyoriy a va b sonlar uchun a < b bo'lgan holda a+b = b va b+a = b tengliklar bajarilmasligi mumkin, ular faqat a = 0 bo'lsagina o'rinlidir.

To'plamlarning kesishmasi.

Har qanday ikkita to'plamning barcha umumiy elementlaridan tuzilgan to'plamga to'plamlarning kesishmasi (yoki ko'paytmasi) deyiladi.

Berilgan A va B to'plamlarning kesishmasi ARB kabi belgilanadi. Bu yerda "A va B to'plamlarga kesishma amalini qo'llab, ARB to'plam hosil qilindi" deyish mumkin. 2- shaklda A va B to'plamlar doiralar ko'rinishida, ARB to'plam esa bo'yab tasvirlangan. To'plamlar ustidagi A ^j5—amallarning yuqorida ta'kidlangan o'ziga xos xususiyatlari to'plamlar ko'paytmasini (kesishmasini) topishda ham namoyon bo'ladi. Masalan, A œ b bo'lsa, u holda A R B = A
2 h kl va =bo'ladi.
- Bitta ham umumiy elementga ega bo'lmagan ikkita
to'plamlarning kesishmasi bo'sh to'plam bo'lishi tabiiydir. Kesishmasi bo'sh bo'lgan to'plamlar o'zaro kesishmaydigan, kesishmasi bo'sh bo'lmagan to'plamlar esa o'zaro kesishadigan to'plamlar deb ataladi.
4- misol. A = {a,b,c}, B = {a,b,c,d}, C = {e,f,k} bo'lsa, u holda D = A R B = {a, b, c}, D R C = 0 , A R C = 0 , B R C = 0 , D R B = {a, b, c} bo'ladi. ■
5- misol. 2- misolda aniqlangan A va B to'plamlarga kesishma amalini qo'llasak, O'zbekiston Respublikasining yoshi 21dan 25gacha bo'lgan fuqarolari to'plami ( A R B to'plam) hosil bo'ladi. Bu yerda A va B to'plamlar o'zaro kesishadigan to'plamlardir. ■
6- misol. N R R = N . ■
7- misol. Butun dunyoda 2005 yilda tug'ilgan bolalar to'plamini T5 bilan, 2006 yilda tug'ilgan bolalar to'plamini esa T bilan belgilasak, u holda T RT =0 bo'ladi. Demak, T5 va T to'plamlar o'zaro kesishmaydigan to'plamlardir.

Umumiy xolda to’plamlarning birlashmasi va kesishmasini quyidagi rasm orqali kengroq tushunsa ham bo’ladi.

Mavzu: Aynan chin, aynan yolg‘on va bajariluvchi formulalar.

Tarif: (aynan chin). Tavtologiya. Tabiiyki, berilgan formula uning tarkibida qatnashuvchi elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlari uchun turli qiymatlar, jumladan, faqat ch yoki faqat yo qiymat qabul qilishi mumkin. Tarkibida elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlarida faqat ch qiymat qabul qiluvchi formula tavtologiya deb ataladi.
Tavtologiya iborasi o’rnida aynan chin yoki doimo chin formula iborasi ham qo’llanilishi mumkin. Tavtologiya ko’pincha J yoki I bilan belgilanadi. Aynan chin formula, uning tarkibida ishtirok etuvchi o’zgaruvchilarning qiymatlariga bog’liq bo’lmay, faqat bitta (ch) qiymat qabul qiladi.
D  x  (x  y)  y
formula tavtologiyadir. Bu tasdiqning to’g’riligini tekshirish uchun 1-jadvalni (D formulaning qiymatlar jadvalini) tuzamiz. Berilgan D formula uning tarkibida qatnashuvchi x va y elementar mulohazalarning mumkin bo’lgan hamma qiymatlar satrlarida faqat ch qiymat qabul qilgani uchun, u tavtologiyadir, ya’ni
x  (x  y)  y  J.

Tarif: (aynan yolg’on). Tarkibida elementar mulohazalarning mumkin bo’lgan barcha qiymatlar satrlarida faqat yo qiymat qabul qiluvchi formula aynan yolg’on (doimo yolg’on) yoki bajarilmaydigan formula deb ataladi.

A  (x  y)  x  y formula aynan yolg’on formuladir.

Teorema: Agar A va A  B formulalarnig har biri tavtologiya bo’lsa, u holda B formula ham tavtologiya bo’ladi.

Isboti.

A va A  B formulalarning har biri tavtologiya bo’lsin. Teorema tasdig’ining teskarisini, ya’ni A va B formulalar tarkibiga kiruvchi o’zgaruvchilarning hech bo’lmaganda bitta qiymatlar satrida B formula yo qiymat qabul qilsin deb faraz qilamiz. U holda, A formula tavtologiya bo’lganligi uchun, o’zgaruvchilarning o’sha qiymatlar satr(lar)ida A ch qiymat qabul qiladi. Shu sababli A  B formula yo qiymat qabul qiladi. Bu esa A  B formula tavtologiyadir degan tasdiqqa qarama-qarshidir. Demak, B tavtologiyadir.

Bajariluvchi formulalar. Endi berilgan formula uning atrkibida qatnashuvchi elementar mulohazalarning ba’zi qiymatlar satrlari uchun ch, ba’zilari uchun esa yo qiymat qabul qilish holini qaraymiz.