Teorema Aniq bo'lmagan to'plamlar o'ziga xoslikni qondiradi

De Morgan qonunlari. Mantiq qonunlari va formulalari. Bo'linishga nisbatan disjunksiyaning taqsimlanishi
8-bobda noaniq va tasodifiy to'plamlar kabi sonli bo'lmagan ob'ektlar turlari ko'rib chiqilgan. Bu ilovaning maqsadi noaniq to'plamlarning xususiyatlarini chuqurroq o'rganish va noaniq to'plamlar nazariyasi ma'lum ma'noda tasodifiy to'plamlar nazariyasiga qisqartirilganligini ko'rsatishdir. Bu maqsadga erishish uchun teoremalar zanjiri tuziladi va isbotlanadi. Kelgusida, hamma aniq bo'lmagan to'plamlar bir xil to'plamning kichik to'plamlari deb taxmin qilinadi Y.
P2-1. Aniq bo'lmagan to'plamlar uchun De Morgan qonunlari
Ma'lumki, to'plamlar algebrasining quyidagi identifikatsiyalari Morgan qonunlari deb ataladi
Teorema 1.Aniq bo'lmagan to'plamlar o'ziga xoslikni qondiradi
(3) Teoremaning isboti 8 -bobda berilgan ta'riflar asosida bu munosabatlarda ishtirok etuvchi noaniq to'plamlarning a'zolik funktsiyalarining qiymatlarini hisoblash orqali (2) va (3) munosabatlarning to'g'riligini to'g'ridan -to'g'ri tekshirishdan iborat. Shaxslar (2) va (3) chaqiriladi noaniq to'plamlar uchun de Morgan qonunlari... Klassik munosabatlardan (1) farqli o'laroq, ular to'rtta identifikatsiyadan iborat bo'lib, ularning bir jufti birlashma va kesishish operatsiyalariga, ikkinchisi esa mahsulot va yig'indiga tegishli. To'plamlar algebrasidagi (1) munosabat kabi, noaniq to'plamlar algebrasidagi de Morgan qonunlari inkor operatsiyalari o'z ichiga olgan ifodalar va formulalarni o'zgartirishga imkon beradi. P2-2. Aniq bo'lmagan to'plamlar uchun taqsimot qonuni Aniq bo'lmagan to'plamlar uchun operatsiyalarning ba'zi xususiyatlari bajarilmaydi. Shunday qilib, qachon bo'lgan hollar bundan mustasno A- "aniq" to'siq (ya'ni a'zolik funktsiyasi faqat 0 va 1 qiymatlarini oladi). Aniq bo'lmagan to'plamlar uchun taqsimot qonuni to'g'rimi? Adabiyotda ba'zida noaniq tarzda "har doim ham emas" deb aytiladi. Keling, buni to'liq tushuntiraylik. Teorema 2.A, B va C har qanday noaniq to'plamlar uchun Shu bilan birga, tenglik to'g'ri va agar hamma uchun bo'lsa Isbot... Biz ixtiyoriy elementni tuzatamiz. Belgini qisqartirish uchun biz (4) kimligini isbotlash uchun shuni ko'rsatish kerak Uch raqamning turli tartiblarini ko'rib chiqing a, b, v. Birinchi bo'lsin Keyin (6) munosabatlarning chap tomoni va o'ng tomoni, ya'ni. tenglik (6) to'g'ri. Keling (6) munosabatida chapda va o'ngda a bor, ya'ni. (6) munosabatlar yana tenglikdir. Agar (6) ga nisbatan chapda va o'ngda a bo'lsa, ya'ni. ikkala qism yana mos keladi. Qolgan uchta raqamlar tartibi a, b, v demontaj qilishning hojati yo'q, chunki (6) raqamlarga nisbatan b va v nosimmetrik tarzda kiring. Identifikatsiya (4) isbotlangan. 2 -teoremaning ikkinchi bayoni, noaniq to'plamlar bo'yicha operatsiyalar ta'rifiga muvofiq (8 -bobga qarang). Bu ikkita ibora, agar isbotlanishi kerak bo'lgan narsaga to'g'ri kelsa. Ta'rif 1.A noaniq A to'plamining tashuvchisi barcha nuqtalarning yig'indisidir , kimdan 2 -teorema uchun xulosa.Agar B va C noaniq to'plamlarining tayanchlari Y bilan mos keladigan bo'lsa, unda tenglik (5) A faqat "tiniq" (ya'ni oddiy, klassik, loyqa emas) to'plami bo'lsa amalga oshadi.

Dalil. Shart bo'yicha hammaning oldida. Keyin 2 -teoremadan kelib chiqadi o'sha. yoki, bu degani A- aniq to'plam. P2-3. Aniq bo'lmagan to'plamlar tasodifiy to'plamlarning proektsiyalari sifatida O'tgan asrning 60 -yillarida zamonaviy noaniq nazariya vujudga kelishining boshidanoq uning ehtimollik nazariyasi bilan aloqasi haqida munozaralar boshlandi. Gap shundaki, noaniq to'plamning a'zolik funktsiyasi ehtimollik taqsimotiga o'xshaydi. Faqatgina farq shundaki, tasodifiy o'zgaruvchining barcha mumkin bo'lgan qiymatlari (yoki mumkin bo'lgan qiymatlar to'plami sanab bo'lmaydigan bo'lsa, integral) bo'yicha ehtimolliklar yig'indisi har doim 1 ga teng bo'ladi va yig'indisi S a'zolik funktsiyasining qiymatlari (uzluksiz holatda - a'zolik funktsiyasining ajralmas qismi) har qanday manfiy bo'lmagan raqam bo'lishi mumkin. A'zolik funktsiyasini normallashtirish vasvasasi mavjud, ya'ni. uning barcha qiymatlarini bo'linadi S(da S 0) uni ehtimollik taqsimotiga (yoki ehtimollik zichligiga) kamaytirish. Biroq, noaniqlik bo'yicha mutaxassislar bunday "ibtidoiy" qisqartirishga haqli ravishda e'tiroz bildirishadi, chunki u har bir loyqa (noaniq to'plam) uchun alohida -alohida amalga oshiriladi va noaniq to'plamlar bo'yicha oddiy operatsiyalar ta'riflari bilan kelishib bo'lmaydi. Oxirgi bayonot quyidagilarni bildiradi. Aniq bo'lmagan to'plamlarning a'zolik funktsiyalariga ruxsat bering A va V... Bu holatda a'zolik funktsiyalari qanday o'zgartiriladi? O'rnatish printsipial jihatdan mumkin emas. Oxirgi bayonot a'zolik funktsiyalari qiymatlari bir xil bo'lgan, lekin ulardagi set-teorik operatsiyalarning turli natijalari va tegishli a'zolik funktsiyalari qiymatlari yig'indisiga ega bo'lgan noaniq to'plamlarning bir nechta misollarini ko'rib chiqqandan so'ng aniq bo'ladi. to'plamlar-teorik operatsiyalarining bu natijalari uchun, masalan, to'plamlarning kesishishi uchun ham alohida. Aniq bo'lmagan to'plamlar ustida ishlarda, noaniq nazariya amaliy matematikaning mustaqil bo'lagi va ehtimollik nazariyasi bilan hech qanday aloqasi yo'qligi haqida tez -tez bahs yuritiladi (qarang, masalan, monografiyalardagi adabiyotlarni ko'rib chiqish). Mumkin bo'lmagan nazariya va ehtimollik nazariyasini taqqoslagan mualliflar, odatda, nazariy va bu sohalar o'rtasidagi farqni ta'kidladilar amaliy tadqiqotlar... Odatda, aksiomalar solishtiriladi va qo'llanilish sohalari taqqoslanadi. Darhol ta'kidlash kerakki, ikkinchi turdagi taqqoslash dalillari isbotlovchi kuchga ega emas, chunki ehtimol ilmiy-statistik usullar kabi uzoq vaqtdan beri mavjud bo'lgan ilmiy sohaning qo'llanilish chegaralari to'g'risida har xil fikrlar mavjud. Eslatib o'tamiz, taniqli frantsuz matematiklaridan biri Anri Lebesgning arifmetikaning qo'llanilish chegaralari haqidagi mulohazasining natijasi quyidagicha: "Arifmetika qo'llanilganda qo'llaniladi" (uning monografiyasiga qarang). Aniq bo'lmagan nazariya va ehtimollik nazariyasining turli aksiomatikasini taqqoslaganda, aksiomalar ro'yxati turlicha ekanligini ko'rish oson. Biroq, bu nazariyalar o'rtasida, masalan, evklid geometriyasining tekislikda arifmetikaga (aniqrog'i, sanoq sistemasi nazariyasiga) ma'lum qisqarishi kabi aloqalarni o'rnatish mumkin emas degan xulosaga kelmaydi. - qarang, masalan, monografiya). Eslatib o'tamiz, bu ikki aksiomatika - evklid geometriyasi va arifmetikasi bir qarashda juda farq qiladi. Yangi yo'nalish ixlosmandlarining ilmiy apparatlarining tub yangiligini ta'kidlash istagini tushunish mumkin. Shu bilan birga, yangi yondashuv va ilgari ma'lum bo'lgan munosabatlar o'rtasida aloqa o'rnatish juda muhimdir. Ma'lum bo'lishicha, noaniq to'plamlar nazariyasi tasodifiy to'plamlar nazariyasi bilan chambarchas bog'liq. 1974 yilda, noaniq to'plamlarni tasodifiy to'plamlarning "proektsiyalari" deb hisoblash tabiiy ekanligi maqolada ko'rsatildi. Aniq bo'lmagan to'plamlar nazariyasini tasodifiy to'plamlar nazariyasiga aylantirishning bu usulini ko'rib chiqing. Ta'rif 2.Bo'lsin - cheklangan Y to'plamning tasodifiy to'plami. Y bo'yicha aniqlangan noaniq B to'plam A proektsiyasi deb ataladi va agar Proj A bilan belgilanadi (7) hamma bilan Shubhasiz, har bir tasodifiy to'plam A noaniq to'plam (7) formulasi yordamida bog'lanishi mumkin B = Proj A. Ma'lum bo'lishicha, buning aksi ham haqiqat. Teorema 3. Cheklangan Y to'plamning har qanday loyqa B to'plami uchun, Y to'plamining tasodifiy A to'plami mavjud, shunday qilib B = Proj A. Dalil. Tasodifiy to'plamning taqsimlanishini ko'rsatish kifoya A... Bo'lsin U 1- tashuvchi V(yuqoridagi 1 -ta'rifga qarang). Umumiylikni yo'qotmasdan, biz buni taxmin qilishimiz mumkin ba'zilari bilan m va elementlar U 1 shunday tartibda raqamlangan Biz to'plamlar bilan tanishamiz Boshqa barcha kichik to'plamlar uchun NS ko'pchilik Bor qo'yish P (A = X) = 0... Elementdan beri y t to'plamga kiradi Y (1), Y (2), ..., Y (t) va tarkibiga kirmaydi ko'pchilik Y (t + 1), ..., Y (m), keyin yuqoridagi formulalardan kelib chiqadi Agar aniq bo'lsa, 3 -teorema isbotlangan. 8 -bobning mulohazalaridan kelib chiqqan holda, mustaqil elementlarga ega bo'lgan tasodifiy to'plamning taqsimlanishi uning proektsiyasi bilan to'liq aniqlanadi. Umumiy shaklning cheklangan tasodifiy to'plami uchun bunday emas. Aytilganlarga aniqlik kiritish uchun bizga quyidagi teorema kerak. Teorema 4. $ Y $ sonining tasodifiy kichik to'plami uchun elementlar soni raqamlar to'plami va biri orqali ifodalanadi. Dalil. Ikkinchi to'plam birinchisi orqali quyidagicha ifodalanadi: Birinchi to'plam elementlari ikkinchisida rasmiy mantiqdan qo'shilishlar va istisnolar formulasi yordamida ifodalanishi mumkin. Bu formulada, birinchi summada da to'plamning barcha elementlari orqali o'tadi Y \ X, ikkinchisida summa o'zgaruvchilari 1 da va 2 da mos kelmaydi va bu to'plam orqali ishlaydi va hokazo. Inklyuziya va istisnolar formulasiga havola 4 -teorema isbotini to'ldiradi. 4 -teoremaga muvofiq, tasodifiy A to'plamni nafaqat taqsimot, balki sonlar to'plami bilan ham tavsiflash mumkin. Bu to'plamda tenglik tipidagi boshqa munosabatlar mavjud emas. Bu to'plam raqamlarni o'z ichiga oladi, shuning uchun tasodifiy to'plamning proektsiyasini tuzatish fiksatsiyaga tengdir k = Karta (Y) dan parametrlar (2 k -1) tasodifiy to'plamning taqsimlanishini ko'rsatuvchi parametrlar A umuman. Quyidagi teorema foydali bo'ladi. Teorema 5. Agar Projekt A = B, keyin Tasdiqlash uchun tasodifiy to'plamlar nazariyasidagi identifikatsiyani, 8 -bobdagi ehtimollik formulasini, noaniq to'plamni rad etish ta'rifini va barcha P (A = X) yig'indisi faktini ishlatish kifoya. ) 1 ga teng. P2-4. Aniq bo'lmagan va tasodifiy to'plamlarning kesishishi va mahsulotlari Keling, tasodifiy to'plamlardagi operatsiyalar ularning proektsiyalari bo'yicha operatsiyalar bilan qanday bog'liqligini bilib olaylik. De Morgan qonunlari (1 -teorema) va 5 -teorema tufayli tasodifiy to'plamlarning kesishish jarayonini ko'rib chiqish kifoya. Teorema 6. Agar cheklangan to'plamning tasodifiy kichik to'plamlari A 1 va A 2 bo'lsa U mustaqil, keyin noaniq to'plam mahsulotdir noaniq to'plamlar Proj A 1 va Proj A 2. Dalil. Buni har kimga ko'rsatish kerak Nuqtani tasodifiy to'plam bilan yopish ehtimoli formulasi bo'yicha (8 -bob) Ma'lumki, tasodifiy to'plamlarning kesishishining taqsimlanishi ularning birgalikdagi taqsimlanishi bilan quyidagicha ifodalanishi mumkin: (9) va (10) munosabatlardan kelib chiqadiki, tasodifiy to'plamlarning kesishishini qoplash ehtimoli ikki barobar yig'indida ifodalanishi mumkin. E'tibor bering, formulaning (11) o'ng tomoni quyidagicha qayta yozilishi mumkin: (12) Darhaqiqat, (11) formuladan (12) formuladan farqi shundaki, u yig'indisi o'zgaruvchilarining kesishishi doimiy qiymatga ega bo'lgan shartlarni guruhlaydi. Tasodifiy to'plamlarning mustaqilligi ta'rifidan va yig'indilarni ko'paytirish qoidasidan foydalanib, biz (11) va (12) dan quyidagini olamiz. 6 -teoremaning isbotini to'ldirish uchun nuqtani tasodifiy to'plam bilan qoplash ehtimoli formulasiga yana bir bor murojaat qilish kifoya (8 -bob). Ta'rif 3. Tasodifiy C to'plamining tashuvchisi - bu barcha elementlarning yig'indisi kimdan Teorema 7.Tenglik to'g'ri va agar tasodifiy to'plamlar tayanchlarining kesishishi bo'lsa va bo'sh Dalil. Qaysi sharoitda ekanligini aniqlash kerak Keyin tenglik (13) shartga kamayadi Shubhasizki, (14) munosabatlar bajariladi va agar bo'lsa p 2 p 3 Hamma uchun = 0 bir vaqtning o'zida shunday element yo'q va va bu tasodifiy to'plamlar tayanchlarining bo'sh kesishmasiga teng . 7 -teorema isbotlangan. P2-5. Aniq bo'lmagan to'plamlar bo'yicha operatsiyalar ketma -ketligini kamaytirish tasodifiy to'plamlar bo'yicha operatsiyalar ketma -ketligiga Aniq bo'lmagan va tasodifiy to'plamlar orasidagi ba'zi ulanishlar yuqorida keltirilgan. Shuni ta'kidlash kerakki, ishdagi bu aloqalarni o'rganish (bu ish 1974 yilda qilingan va "Ko'p o'lchovli" seminarida ma'ruza qilingan. statistik tahlil va real jarayonlarni ehtimoliy modellashtirish "1974 yil 18 dekabr - qarang) L. Zade tomonidan noaniq to'plamlar apparatini ishlab chiqish va umumlashtirish maqsadida tasodifiy to'plamlarni kiritish bilan boshlandi. uning yordamida modellashtirilgan tushunchalar (ob'ektlar) o'rtasida etarlicha moslashuvchan emas. Shunday qilib, ikkita noaniq to'plamning "umumiy qismini" ta'riflash uchun faqat ikkita operatsiya mavjud - mahsulot va kesishma. Agar ulardan birinchisi qo'llanilsa, aslida bu to'plamlar mustaqil proyeksiyalar sifatida harakat qiladi deb taxmin qilinadi. tasodifiy to'plamlar (yuqoridagi 6 -teoremaga qarang). Kesishish operatsiyalari to'plamlar orasidagi bog'liqlik shakliga ham aniq cheklovlar qo'yadi (yuqoridagi 7 -teoremaga qarang) va bu holda hatto zarur va etarli shartlar topiladi. (tushunchalar, ob'ektlar). tasodifiy to'plamlarning matematik apparati bunday imkoniyatlarni beradi. Noma'lum to'plamlarni tasodifiy sonlarga qisqartirishdan maqsad, noaniq to'plamlarning har qanday konstruktsiyasi ortida, tasodifiy o'zgaruvchilarning ehtimollik taqsimotining zichligiga qarab, birinchisining xususiyatlarini aniqlaydigan tasodifiy to'plamlar konstruktsiyasini ko'rishdir. Ushbu bo'limda biz noaniq to'plamlar algebrasini tasodifiy to'plamlar algebrasiga qisqartirish bo'yicha natijalarni taqdim etamiz. Ta'rif 4.Ehtimollar maydoni { V, G, P)bo'linadigan deyiladi, agar o'lchanadigan har qanday X G va har qanday musbat sonlar uchun, P (X) dan kichikroq bo'lsa, biz o'lchanadigan to'plamni ko'rsatishimiz mumkin Misol. Cheklangan o'lchovli chiziqli fazoning birlik kubi bo'lsin, G Borel to'plamlarining sigma-algebrasi va P.- Lebesgue chorasi. Keyin { V, G, P)- bo'linadigan ehtimollik maydoni. Shunday qilib, bo'linadigan ehtimollik maydoni ekzotik emas. Oddiy kub bunday bo'shliqqa misol bo'la oladi. Misolda keltirilgan bayonotning isboti standart matematik usullar yordamida amalga oshiriladi, buning natijasida o'lchovli to'plamni o'zboshimchalik bilan ochiq to'plamlar yordamida aniqlab olish mumkin, ikkinchisi ochiq to'plarning eng ko'p hisoblanadigan sonining yig'indisi sifatida ifodalanadi va to'plar uchun bo'linish to'g'ridan -to'g'ri tekshiriladi (X to'pidan mos keladigan tekislik bilan ajratilgan hajm jismi). Teorema 8.Bo'linadigan ehtimollik maydonida tasodifiy A to'plami berilsin (V, G, P) cheklangan sonli elementlarning Y to'plamining barcha kichik to'plamlaridagi qiymatlar bilan va Y da noaniq D to'plami. Keyin tasodifiy S 1 to'plamlar mavjud., C 2, C 3, Xuddi shu ehtimollik maydonida C 4 bu erda B = Proj A. Dalil. De Morgan qonunlarining noaniqligi uchun (yuqoridagi 1 -teoremaga qarang) va tasodifiy to'plamlar uchun, shuningdek yuqoridagi 5 -teorema (inkor qilish bo'yicha) asosliligi tufayli tasodifiy to'plamlar mavjudligini isbotlash kifoya. C 1 va C 2 . To'plamning barcha kichik to'plamlari to'plamida ehtimollik taqsimotini ko'rib chiqing Bor tasodifiy to'plamga mos keladi BILAN shu kabi Projekt C = D(3 -teorema tufayli mavjud). Keling, tasodifiy to'plamni tuzamiz C 2 Biz faqat elementni chiqarib tashlaymiz xuddi shu Y to'plami va bundan tashqari, set-teorik operatsiyalar natijalari shunga o'xshash munosabatlar bilan bog'liq bu erda belgi ko'rib chiqilgan joy tasodifiy to'plamlarning kesishish belgisi bilan band bo'lishini anglatadi, agar B m ta'rifida kesishish belgisi yoki noaniq to'plamlar mahsuloti belgisi bo'lsa va shunga mos ravishda tasodifiy birlashma ramzi bo'lsa to'plamlar, agar B m birlashma belgisini yoki noaniq to'plamlar yig'indisining ramzini o'z ichiga olsa. De Morgan qonunlari mantiqiy qoidalar mantiqiy inkor yordamida juft mantiqiy operatsiyalarni bog'laydigan, Shotlandiya matematikasi Avgust de Morgan tomonidan tashkil etilgan. Avgust de Morgan klassik mantiqda quyidagi munosabatlar to'g'ri ekanligini payqadi: emas (A va B) = (A emas) yoki (B emas) emas (A yoki B) = (A emas) va (B emas) Bizga tanish bo'lgan shaklda, bu nisbatlar quyidagi shaklda yozilishi mumkin: De Morgan qonunlari quyidagicha ifodalanishi mumkin. Men de Morgan qonuni: Ikkita oddiy bayonotning ajralishini inkor etish, bu bayonotlarni inkor etishining birlashmasiga tengdir. II de Morgan qonuni: Ikkita sodda gapni birlashtirilishini inkor etish, bu gaplarni inkor etishning bir -biriga mos kelmasligiga teng. Keling, aniq misollar bilan de Morgan qonunlarining qo'llanilishini ko'rib chiqaylik. Misol 1. Formulani shunday o'zgartiringki, murakkab iboralarni inkor qilmang. Birinchi Morgan qonunidan foydalanib, biz quyidagilarni olamiz: B va C oddiy so'z birikmalarini inkor etish uchun biz ikkinchi de Morgan qonunini qo'llaymiz va quyidagilarni olamiz: , Shunday qilib: . Natijada, biz ekvivalent bayonotga ega bo'ldik, unda murakkab so'zlarni inkor etish yo'q va barcha inkorlar faqat oddiy bayonotlarga tegishli. Siz haqiqat jadvallari yordamida qarorning to'g'riligini tekshirishingiz mumkin. Buning uchun biz asl bayonot uchun haqiqat jadvallarini tuzamiz: va de Morgan qonunlari yordamida amalga oshirilgan o'zgartirishlar natijasida olingan bayonot uchun: . 1 -jadval. B / \ C. A / B / \ C Jadvallardan ko'rinib turibdiki, asl mantiqiy bayon va de Morgan qonunlari yordamida olingan mantiqiy bayon tengdir. Bu haqiqat jadvallarida biz bir xil qiymatlar to'plamini olganligimizdan dalolat beradi. Mantiq qonunlari va formulalari Kirish darsida matematik mantiq asoslari, biz matematikaning ushbu bo'limining asosiy tushunchalari bilan tanishdik va endi mavzu tabiiy ravishda davom ettiriladi. Yangi nazariy, aniqrog'i, nazariy emas, balki umumiy o'quv materialidan tashqari, bizni amaliy vazifalar kutmoqda, shuning uchun agar siz ushbu sahifaga qidiruv tizimidan kirgan bo'lsangiz va / yoki materialni yomon boshqargan bo'lsangiz, iltimos yuqoridagi havolaga o'ting va oldingi maqoladan boshlang. Bundan tashqari, amaliyot uchun bizga 5 kerak haqiqat jadvallari mantiqiy operatsiyalar qaysi i juda tavsiya qilaman qo'l bilan qayta yozish. Eslamang, chop qilmang, ya'ni o'z qo'lingiz bilan qog'ozga qayta yozib yozing - shunda ular sizning ko'z o'ngingizda bo'ladi: - jadval YO'Q; - jadval I; - Yoki jadval; - ta'sir qilish jadvali; - ekvivalentlik jadvali. Bu juda muhim. Asosan, ularni raqamlash qulay bo'lardi. "1 -jadval", "2 -jadval" va boshqalar., lekin men bu yondashuvning kamchiliklarini bir necha bor ta'kidlaganman - ular aytganidek, bir manbada jadval birinchi, ikkinchisida - yuz birinchi bo'ladi. Shuning uchun biz "tabiiy" nomlardan foydalanamiz. Biz davom etamiz: Aslida, siz allaqachon mantiqiy formula tushunchasi bilan tanishsiz. Men sizga standartni beraman, lekin aqlli ta'rif: formulalar bayonotlar algebrasi deyiladi: 1) har qanday elementar (oddiy) bayonotlar; 2) agar va formulalar bo'lsa, formulalar ham shakl ifodasidir . Boshqa formulalar yo'q. Xususan, formula - bu mantiqiy ko'paytirish kabi har qanday mantiqiy operatsiya. Ikkinchi nuqtaga e'tibor bering - bu imkon beradi rekursiv o'zboshimchalik bilan uzun formulani "yaratish" usuli. Qanday bo'lmasin - formulalar, keyin - shuningdek, formulalar; beri va formulalar, demak - shuningdek, formulalar va boshqalar. Har qanday elementar bayonot (yana aniqlanganidek) formulaga bir necha marta kiritilishi mumkin. Formula emas masalan, rekord bor - va bu erda "algebraik axlat" bilan aniq o'xshashlik bor, undan raqamlarni qo'shish yoki ko'paytirish kerakligi aniq emas. Mantiqiy formulani quyidagicha ko'rish mumkin mantiqiy funktsiya... Keling, bir xil birikmani funktsional shaklda yozaylik: Bunda elementar iboralar, shuningdek, klassik mantiqda 2 qiymatni olishi mumkin bo'lgan argumentlar (mustaqil o'zgaruvchilar) rolini o'ynaydi: rost yoki Yolg'on gapirish... Keyinchalik, qulaylik uchun men ba'zida oddiy bayonotlarga murojaat qilaman o'zgaruvchilar. Mantiqiy formulani (funktsiyani) tavsiflovchi jadval e'lon qilinganidek, haqiqat jadvali... Iltimos - tanish rasm: Haqiqat jadvalini shakllantirish printsipi quyidagicha: "kirishda" siz ro'yxatga olishingiz kerak barcha mumkin bo'lgan kombinatsiyalar elementar bayonotlarni (dalillarni) olishi mumkin bo'lgan haqiqatlar va yolg'onlar. Bunday holda, formulada ikkita bayon mavjud va bunday to'rtta kombinatsiya mavjudligini aniqlash oson. "Chiqishda" biz butun formulaning (funktsiyaning) mos keladigan mantiqiy qiymatlarini olamiz. Aytishim kerakki, bu erda "chiqish" "bir qadamda" chiqdi, lekin umumiy holda mantiqiy formula murakkabroq. Va bunday "qiyin vaziyatlarda" siz kuzatishingiz kerak mantiqiy amallarni bajarish tartibi: - inkor qilish birinchi navbatda amalga oshiriladi; - ikkinchidan - birikma; - keyin - ajralish; - keyin ma'no; - va nihoyat, ekvivalentlik eng past ustuvorlikka ega. Shunday qilib, masalan, belgi mantiqiy ko'paytirishni, keyin esa mantiqiy qo'shishni bajarishni anglatadi. Xuddi "oddiy" algebrada bo'lgani kabi - "avval ko'paytiramiz, keyin qo'shamiz". Amallar tartibini odatdagidek o'zgartirish mumkin - qavs yordamida: - bu erda, birinchi navbatda, disjunksiya bajariladi va shundan keyingina "kuchliroq" operatsiya amalga oshiriladi. Ehtimol, hamma tushunadi, lekin har bir o't o'chiruvchi uchun: va bu ikki xil formulalar! (rasmiy va moddiy jihatdan) Keling, formula uchun haqiqat jadvalini tuzaylik. V bu formula ikkita asosiy iborani o'z ichiga oladi va "kirish" da biz mumkin bo'lgan kombinatsiyalar va nollarning ro'yxatini tuzishimiz kerak. Chalkashlik va tushunmovchiliklarga yo'l qo'ymaslik uchun biz kombinatsiyalarni ro'yxatlashga rozilik bildiramiz aniq shu tartibda (men aslida boshidanoq de -fakto ishlataman): Formula ikkita mantiqiy operatsiyani o'z ichiga oladi va ularning ustuvorligiga ko'ra, birinchi navbatda, siz bajarishingiz kerak rad etish bayonotlar. Xo'sh, biz "pe" ustunini inkor qilamiz - biz nollarni nolga, nollarni esa bitta raqamga aylantiramiz: Ikkinchi bosqichda biz ustunlarga qaraymiz va ularga murojaat qilamiz Yoki operatsiya... Bir oz oldinga yugurib, men aytamanki, ajralish o'zgaruvchan. (va ular bir xil) va shuning uchun ustunlar odatdagi tartibda - chapdan o'ngga tahlil qilinishi mumkin. Mantiqiy qo'shimchani bajarishda quyidagi amaliy mulohazalardan foydalanish qulay bo'ladi: "Agar ikkita nol bo'lsa, biz nol qo'yamiz, agar kamida bitta birlik bitta bo'lsa": Haqiqat jadvali tuzilgan. Keling, eski yaxshi xulosani eslaylik: ... diqqat bilan, diqqat bilan ... biz oxirgi ustunlarni ko'rib chiqamiz. Propozitsion algebrada bunday formulalar deyiladi ga teng yoki bir xil: (uchta gorizontal chiziq - identifikator belgisi) Darsning 1 -qismida, men asosiy mantiqiy operatsiyalar orqali mazmunini ifoda etishga va'da berdim va va'daning bajarilishi uzoq kutmadi! Qiziquvchilar mazmunli ma'noga ega bo'lishlari mumkin (masalan, "Agar yomg'ir yog'ayotgan bo'lsa, tashqarida nam bo'ladi") va ekvivalent bayonni mustaqil ravishda tahlil qiling. Formula qilaylik umumiy ta'rif: ikkita formulalar deyiladi teng (bir xil) agar ular bu o'zgaruvchilar formulalariga kiritilgan har qanday qiymatlar to'plami uchun bir xil qiymatlarni olsalar (oddiy iboralar)... Bu ham aytilgan "Haqiqat jadvallari mos keladigan bo'lsa, formulalar tengdir" lekin menga bu ibora unchalik yoqmaydi. 1 -mashq Formulaning haqiqat jadvalini tuzing va siz bilgan shaxsning to'g'riligiga ishonch hosil qiling. Muammoni hal qilish tartibini yana bir bor takrorlaylik: 1) Formula ikkita o'zgaruvchini o'z ichiga olganligi sababli, 4 ta nol va jami bitta to'plam bo'lishi mumkin. Biz ularni yuqorida ko'rsatilgan tartibda yozamiz. 2) Ta'sirlar qo'shilishdan ko'ra "kuchsizroq", lekin ular qavs ichida joylashtirilgan. Biz ustunni to'ldiramiz, shu bilan birga quyidagi mulohazalardan foydalanish qulay: "Agar nol bitta narsadan kelib chiqsa, biz nol qo'yamiz, qolgan barcha hollarda - bitta"... Keyinchalik, biz ustun uchun imzo uchun to'ldiramiz va shu bilan birga Diqqat!- ustunlar va "o'ngdan chapga" tahlil qilinishi kerak! 3) Va oxirgi bosqichda oxirgi ustunni to'ldiring. Va bu erda shunday fikr yuritish qulay: "Agar ustunlarda ikkita birlik bo'lsa, biz bitta, qolgan barcha hollarda - nol qo'yamiz". Nihoyat, biz haqiqat jadvalini tekshiramiz ekvivalentlar . Propozitsion algebraning asosiy ekvivalentlari Biz ulardan faqat ikkitasini uchratdik, lekin, albatta, gap ular bilan cheklanmaydi. Bir nechta identifikatorlar bor va men ularning eng muhimlari va eng mashhurlarini sanab o'taman: Bog'lanishning komutativligi va disunksiyaning komutativligi Kommutativlik O'zgaruvchanlik: Birinchi sinfdan tanish bo'lgan qoidalar: "Mahsulot (summa) omillar (atamalar) almashinishidan o'zgarmaydi"... Biroq, bu xususiyatning hamma elementar ko'rinishiga ko'ra, bu har doim ham to'g'ri kelavermaydi, xususan, bu komutativ emas. matritsani ko'paytirish (umuman, ularni qayta tartibga solish mumkin emas), a vektorlarning hosilasi- antikommutativ (vektorlarning almashinuvi belgining o'zgarishiga olib keladi). Va bundan tashqari, bu erda men yana matematik mantiqning formalizmini ta'kidlamoqchiman. Masalan, iboralar "Talaba imtihonni topshirdi va ichdi" va "Talaba ichdi va imtihondan o'tdi" moddiy nuqtai nazardan farq qiladi, lekin rasmiy haqiqat nuqtai nazaridan farq qilmaydi. ... Har birimiz bunday talabalarni bilamiz va axloqiy sabablarga ko'ra biz aniq ismlarni aytmaymiz =) Mantiqiy ko'paytirish va qo'shishning assotsiativligi Yoki, agar "maktab usulida" - kombinatsiyalangan xususiyat: Tarqatish xususiyatlari E'tibor bering, ikkinchi holatda "ochiladigan qavslar" haqida gapirish noto'g'ri bo'ladi, qaysidir ma'noda bu "fantastika" - axir ularni butunlay olib tashlash mumkin: chunki ko'paytirish - bu kuchliroq operatsiya. Va yana, bu "banal" ko'rinadigan xususiyatlar hamma algebraik tizimlarda ham bajarilmaydi va bundan tashqari, isbot talab qilinadi. (bu haqda tez orada gaplashamiz)... Aytgancha, ikkinchi taqsimot qonuni bizning "odatiy" algebramizda ham amal qilmaydi. Va aslida: Idempotentsiya qonuni Nima qilish kerak, lotincha ... To'g'ridan -to'g'ri sog'lom psixikaning qandaydir printsipi: "Men va men - menman", "Men yoki men ham menman" =) Va keyin bir nechta o'xshash identifikatorlar mavjud: ... hmm, men hatto osib qo'ygan narsam bor ... shuning uchun ertaga falsafa doktori bilan uyg'onishingiz mumkin =) Ikki tomonlama rad etish qonuni Bu erda rus tilidagi misol o'zini ko'rsatmoqda - hamma biladi, ikkita zarracha "ha" degani emas. Va mustahkamlash uchun hissiy rang berish Negativlar ko'pincha uchta "emas" dan foydalanadi: - kichik dalillar bilan ham u ishladi! Absorbsiya qonunlari - "O'g'il bola bo'lganmi?" =) To'g'ri identifikatorda, qavslar qoldirilishi mumkin. De Morgan qonunlari Aytaylik, qattiqqo'l Ustoz (siz uning ismini ham bilasiz :)) imtihon topshiradi, agar - Talaba 1 -savolga javob berdi va – Talaba 2 -savolga javob berdi... Keyin bayonot Talaba emas imtihondan o'tdi, bayonotga teng bo'ladi - Talaba emas birinchi savolga javob berdi yoki 2 -savol bo'yicha. Yuqorida ta'kidlab o'tilganidek, ekvivalentlar isbotlanishi kerak, ular haqiqat jadvallari yordamida standart usulda amalga oshiriladi. Darhaqiqat, biz ekvivalentlik va ekvivalentlikni ifodalaganmiz, endi bu muammoni hal qilish texnikasini birlashtirish vaqti keldi. Keling, kimligini isbotlaylik. U bitta iborani o'z ichiga olganligi sababli, "kirishda" faqat ikkita variant mumkin: bitta yoki nol. Keyinchalik, biz bitta ustunni tayinlaymiz va ularga murojaat qilamiz qoida VA: Natijada, "chiqish paytida" formulasi olinadi, uning haqiqati bayonot haqiqatiga to'g'ri keladi. Ekvivalentligi isbotlangan. Ha, bu dalil ibtidoiy (va kimdir buni "ahmoq" deb aytadi), lekin matematikaning odatiy o'qituvchisi uning qalbini larzaga soladi. Shuning uchun, hatto bunday oddiy narsalarga ham beparvo qaramaslik kerak. Keling, masalan, de Morgan qonunining haqiqiyligiga ishonch hosil qilaylik. Birinchidan, chap tomon uchun haqiqat jadvalini tuzaylik. Ajralish qavs ichida bo'lgani uchun, biz birinchi navbatda uni bajaramiz, shundan so'ng ustunni bekor qilamiz: Keling, o'ng tomon uchun haqiqat jadvalini tuzaylik. Bu erda ham hamma narsa shaffof - birinchi navbatda biz ko'proq "kuchli" rad etishni amalga oshiramiz, keyin ustunlarga murojaat qilamiz qoida VA: Natijalar bir -biriga mos keladi, shuning uchun kimligi isbotlanadi. Har qanday ekvivalentlik sifatida ifodalanishi mumkin haqiqiy formula bilan bir xil... Bu shuni anglatadiki HAR QANDAY asl nol va birliklar to'plami uchun"Chiqishda" qat'iy ravishda bitta olinadi. Va buning juda oddiy izohi bor: haqiqat jadvallari bir xil bo'lgani uchun, albatta, ular ekvivalentdir, masalan, ekvivalent sifatida, biz tasdiqlagan de Morganning kimligini chap va o'ng tomonlarini birlashtiraylik. : Yoki, agar ixchamroq bo'lsa: 2 -topshiriq Quyidagi ekvivalentlarni isbotlang: b) Dars oxirida qisqa yechim. Biz dangasa emasmiz! Faqat haqiqat jadvallarini tuzishga harakat qiling, balki aniq xulosalar tuzish. Yaqinda ta'kidlaganimdek, oddiy narsalarni e'tiborsiz qoldirish juda qimmatga tushishi mumkin! Biz mantiq qonunlari bilan tanishishda davom etamiz! Ha, bu to'g'ri - biz allaqachon ular bilan kuch va kuch bilan ishlayapmiz: To'g'ri da deyiladi haqiqiy formula bilan bir xil yoki mantiq qonuni. Ekvivalentlikdan bir xil haqiqiy formulaga ilgari asosli o'tish natijasida yuqorida sanab o'tilgan barcha identifikatorlar mantiq qonunlari hisoblanadi. Qabul qiladigan formula Yolg'on da unga kiritilgan o'zgaruvchilar qiymatlarining har qanday to'plami deyiladi xuddi shunday noto'g'ri formula bo'yicha yoki qarama -qarshilik. Qadimgi yunonlarning qarama -qarshiliklarining xususiy misoli: - hech qanday bayonot bir vaqtning o'zida to'g'ri va noto'g'ri bo'lishi mumkin emas. Dalil ahamiyatsiz: "Chiqishda" faqat nol qabul qilinadi, shuning uchun formula to'g'ri bir xil yolg'on. Biroq, har qanday qarama -qarshilik mantiq qonunidir, xususan: Bitta maqolada bunday keng mavzuni qamrab olishning iloji yo'q, shuning uchun men faqat bir nechta qonunlar bilan cheklanaman: Uchinchi qonun chiqarildi - klassik mantiqda har qanday gap to'g'ri yoki noto'g'ri, uchinchisi yo'q. "Bo'lish yoki bo'lmaslik" - bu savol. O'zingiz haqiqat plitasini tuzing va uning to'g'riligiga ishonch hosil qiling bir xil haqiqat formula Qarama -qarshilik qonuni Bu qonunning mohiyatini muhokama qilganimizda faol muhokama qilindi zarur shart, eslab qoling: "Agar yomg'ir paytida nam bo'lsa, demak, agar tashqarida quruq bo'lsa, yomg'ir yog'magan.". Bundan tashqari, bu qonundan kelib chiqadiki, agar adolatli bo'lsa Streyt teorema, keyin bayonot, ba'zan deyiladi qarama -qarshi teorema Agar rost bo'lsa teskari teorema, keyin qarama -qarshilik qonuni tufayli, teorema ham amal qiladi, teskari teskari: Va yana, bizning ma'lumotli misollarimizga qaytamiz: bayonotlar uchun - son 4 ga bo'linadi, - son 2 ga bo'linadi adolatli Streyt va qarama -qarshi teoremalar, lekin noto'g'ri teskari va teskari teskari teoremalar. Pifagor teoremasining "kattalar" formulasi uchun barcha 4 "yo'nalish" to'g'ri. Sillogizm qonuni Shuningdek, janr klassikalari: "Hamma emanlar daraxtlar, hamma daraxtlar o'simliklardir, shuning uchun hamma emanlar o'simliklardir.". Xo'sh, bu erda men yana matematik mantiqning formalizmiga e'tibor qaratmoqchiman: agar bizning qattiq o'qituvchimiz ma'lum bir talabani eman daraxti deb hisoblasa, rasmiy nuqtai nazardan bu talaba albatta o'simlik =) ... garchi, agar Siz bu haqda o'ylaysiz, ehtimol norasmiy bilan ham =) Keling, formula uchun haqiqat jadvalini tuzaylik. Mantiqiy operatsiyalarning ustuvorligiga muvofiq, biz quyidagi algoritmga amal qilamiz: 1) biz natijalarni bajaramiz va. Umuman aytganda, siz 3 -chi implikatsiyani darhol bajarishingiz mumkin, lekin bu unga qulayroqdir (va ruxsat berilgan!) buni birozdan keyin aniqlang; 2) ustunlarga qo'llang qoida VA; 3) hozir qilyapmiz; 4) va oxirgi bosqichda biz ustunlarga ta'sir ko'rsatamiz va. Ko'rsatkich va o'rta barmog'ingiz bilan jarayonni boshqarishingiz mumkin :)) Oxirgi ustundan, menimcha, hamma narsa sharhlarsiz aniq: , kerak bo'lganda. Topshiriq 3 Quyidagi formula mantiq qonuni bo'ladimi -yo'qligini bilib oling: Qo'llanma oxirida qisqa yechim. Ha, va men deyarli unutib qo'ydim - keling, nol va boshlang'ich to'plamlarni sillogizm qonunining isboti bilan bir xil tartibda ro'yxatlashga rozi bo'laylik. Albatta, chiziqlarni o'zgartirish mumkin, lekin bu mening yechimim bilan taqqoslashni ancha murakkablashtiradi. Mantiqiy formulalarni konvertatsiya qilish Formulalarni o'zgartirish va soddalashtirish uchun "mantiqiy" maqsadidan tashqari ekvivalentlar keng qo'llaniladi. Qisqacha aytganda, identifikatorning bir qismini boshqasiga almashtirish mumkin. Masalan, agar siz mantiqiy formulada bo'lakka duch kelsangiz, unda idempotentsiya qonuniga ko'ra, siz uni o'rniga yozishingiz mumkin (va yozishingiz kerak). Agar ko'rsangiz, yutilish qonuniga ko'ra, kirishni soddalashtiring. Va boshqalar. Bundan tashqari, yana bir muhim narsa bor: identifikatorlar nafaqat oddiy iboralar uchun, balki ixtiyoriy formulalar uchun ham amal qiladi. Masalan: , qayerda (qanchalik murakkab bo'lmasin) formulalar. Keling, masalan, murakkab ma'noni o'zgartiraylik (Birinchi shaxs): Keyinchalik, biz "murakkab" De Morgan qonunini qavsga qo'llaymiz, shu bilan birga, operatsiyalar ustuvorligi tufayli, bu qonun : Qavslar kabi olib tashlanishi mumkin ichida "kuchliroq" birikma mavjud: Umuman, kommutativlik bilan hamma narsa oddiy - siz hech narsani belgilashingiz shart emas ... sillogizm qonuni qalbimga biror narsa uchun singib ketgan :)) Shunday qilib, qonun yanada murakkab shaklda qayta yozilishi mumkin: "Eman, daraxt, o'simlik" bilan mantiqiy zanjirni baland ovozda gapiring, shunda siz tushunasizki, qonunning mazmuni o'zgarmagan. Agar so'zlar yanada original bo'lib qolmasa. Trening sifatida formulani soddalashtiraylik. Qayerdan boshlash kerak? Avvalo, harakatlar tartibini tushunish uchun: bu erda inkor butun qavsga nisbatan qo'llaniladi, bu bayonotga "biroz zaifroq" birikma bilan "mahkamlanadi". Aslida, bizda ikkita omilning mantiqiy mahsuloti bor:. Qolgan ikkita operatsiyadan, eng past ustuvorlikka ega va shuning uchun butun formula quyidagi tuzilishga ega: Qoida tariqasida, birinchi qadam (lar) ekvivalentlik va ta'sirdan xalos bo'ladi (agar ular bo'lsa) va formulani uchta asosiyga kamaytiring mantiqiy operatsiyalar... Nima deysiz .... Bu mantiqiy. (1) Biz identifikatordan foydalanamiz ... Va bizning holatda. Buning ortidan odatda qavslar bilan "demontaj" qilinadi. Birinchidan, butun yechim, keyin sharhlar. "Sariyog 'yog'ini" olmaslik uchun men "oddiy" tenglik belgilaridan foydalanaman: (2) Biz tashqi qavslarga de Morgan qonunini qo'llaymiz. Uyushma x 1 (x 2 x 3) = (x 1 x 2) x 3; x 1 Ú (x 2 Ú x 3) = (x 1 Ú x 2) Ú x 3. Kommutativlik x 1 x 2 = x 2 x 1 x 1 Ú x 2 = x 2 Ú x 1 Bog'lanishning disjunksiya bo'yicha taqsimlanishi x 1 (x 2 x x 3) = x 1 x 2 x x 1 x 3. Bo'linishga nisbatan disjunksiyaning taqsimlanishi x 1 Ú (x 2 × x 3) = (x 1 Ú x 2) × (x 1 Ú x 3). * Idempotensiya (tautologiya) Ikki marta yo'q Doimiy xususiyatlar x & 1 = x; (universal to'plam qonunlari) x & 0 = 0; (nol o'rnatilgan qonunlar) De Morgan qoidalari (qonunlari) Qarama -qarshilik (bir -birini to'ldiruvchi) qonuni Uchinchi (bir -birini to'ldiruvchi) istisno qilish qonuni Bu formulalarning dalillari arzimasdir. Bir variant - chap va o'ng tomonlar uchun haqiqat jadvallarini tuzish va ularni solishtirish. Bog'lanish qoidalari Elementar birikmalarni yopishtirish qoidasi taqsimot qonuni, bir -birini to'ldirish qonuni va universal to'plam qonunidan kelib chiqadi: ikkita qo'shni qo'shma gapning ajralishi asl birikmalarning umumiy qismi bo'lgan bitta elementar birikma bilan almashtirilishi mumkin. . Boshlang'ich summani yopishtirish qoidasi ikkinchi turdagi taqsimot qonunidan, bir -birini to'ldirish qonunidan va nol to'plamidan kelib chiqadi: ikkita qo'shni gapning birikmasi bitta elementli gap bilan almashtirilishi mumkin, bu asl gaplarning umumiy qismi. . Absorbsiya qoidasi Ikkita elementar mahsulot yig'indisining yutilish qoidasi birinchi turdagi taqsimot qonuni va universal to'plam qonunlaridan kelib chiqadi: biri ikkinchisining ajralmas qismi bo'lgan ikkita elementar birikmaning disjunksiyasini oz sonli operandli birikma bilan almashtirish mumkin. . Boshlang'ich summalar mahsulotining yutilish qoidasi ikkinchi turdagi taqsimot qonuni va nol to'plam qonunlaridan kelib chiqadi: bittasi ikkinchisining ajralmas qismi bo'lgan ikkita elementar disjunksiyaning birikmasi, operandlar soni kamroq bo'lgan elementar disjunksiya bilan almashtirilishi mumkin. Joylashtirish qoidasi Ushbu qoida yopishtirishning teskari harakatini belgilaydi. Boshlang'ich mahsulotni yuqori darajadagi elementar mahsulotlarning mantiqiy yig'indisiga ochish qoidasi (r = n gacha, ya'ni birlik birliklariga qadar, quyida muhokama qilinadi) universal to'plam qonunlari, taqsimotidan kelib chiqadi. Birinchi turdagi qonun va uch bosqichda amalga oshiriladi: R darajali kengaytiriladigan elementar mahsulotga omillar sifatida kiritiladi n-r birliklari, bu erda n - birlik tarkibining unvoni; Har bir birlik dastlabki elementar mahsulotda bo'lmagan va uni inkor etuvchi o'zgaruvchining mantiqiy yig'indisi bilan almashtiriladi: x i v `x i = 1; Barcha qavslar birinchi turdagi taqsimot qonuni asosida ochiladi, bu esa r-darajali dastlabki elementar mahsulotni birlikning 2 n-r komponentining mantiqiy yig'indisiga kengayishiga olib keladi. Boshlang'ich mahsulotni ochish qoidasi Boolean algebra (FAL) funktsiyalarini minimallashtirish uchun ishlatiladi. R darajadagi elementar yig'indini n darajali elementlarning yig'indisiga (nolni tashkil etuvchilar) kengaytirish qoidasi ularning nol to'plami (6) qonunlariga va ikkinchi turdagi taqsimot qonuniga (14) amal qiladi va uchtasida bajariladi. bosqichlar: R darajasining kengaytiriladigan summasida, biz shart sifatida, kiritamiz n-n nol; Har bir nol boshlang'ich yig'indida bo'lmagan va uni inkor etuvchi o'zgaruvchining mantiqiy mahsuloti sifatida ifodalanadi: x i·` x i = 0; Olingan ifoda ikkinchi turdagi taqsimot qonuni (14) asosida o'zgartiriladi, shunda r darajasining boshlang'ich yig'indisi 2 n-r nolli komponentning mantiqiy mahsulotiga aylanadi. 16. To'liq tizim haqida tushuncha. To'liq tizimlarga misollar (isboti bilan) Ta'rif. A mantiqiy funktsiyalar majmui to'liq tizim deb ataladi (P2 da), agar biron bir mantiqiy funktsiyani A ustidagi formula bilan ifodalash mumkin bo'lsa. A = funktsiya tizimi f 1, f 1, ..., f m) tugallangan deb nomlanadi asos. Minimal asos - bu hech bo'lmaganda bitta funktsiyani olib tashlash uchun asosdir f 1 bu asosni shakllantirish funktsiyalar tizimini o'zgartiradi (f 1, f 1, ..., f m) to'liq bo'lmagan Teorema. A = (∨, &,) tizimi tugallangan. Dalil. Agar f mantiq algebrasining vazifasi bir xil noldan farq qiladigan bo'lsa, u holda f faqat disjunksiya, konjunksiya va inkorni o'z ichiga oladigan mukammal disjunktiv normal shakl ko'rinishida ifodalanadi. Agar f ≡ 0 bo'lsa, u holda f = x & x bo'ladi. Teorema isbotlangan. Lemma. Agar A tizimi tugallangan bo'lsa va A tizimining har qanday funktsiyasini boshqa B tizimiga nisbatan formulalar bilan ifodalash mumkin bo'lsa, B ham to'liq tizimdir. Dalil. Ixtiyoriy mantiqiy funktsiyani f (x 1,…, x n) va ikkita funktsiya tizimini ko'rib chiqaylik: A = (g 1, g 2,…) va B = (h 1, h 2,…). A tizimi tugallangach, f funksiyasi uning formulasi sifatida ifodalanishi mumkin: f (x 1,…, x n) = bu erda g i = ℜ i ya'ni f funktsiyasi sifatida ifodalanadi f (x 1,…, x n) = ℑ [ℜ1, ℜ2, ...] Boshqacha qilib aytganda, uni B formulasi bilan ifodalash mumkin. Mantiqiy algebraning barcha funktsiyalarini shu tarzda o'tib, biz B tizimining ham to'liq ekanligini aniqlaymiz. Lemma isbotlangan. Teorema. Quyidagi tizimlar P 2 da to'liq: 4) (&, ⊕, 1) Jegalkin asosi. Dalil. 1) A = (&, V,) tizimi tugallanganligi ma'lum (3 -teorema). Keling, B = (V, sistemasi to'liq ekanligini ko'rsataylik. Darhaqiqat, de Morgan qonunidan (x & y) = (x ∨ y) biz x & y = (x ∨ y) ni olamiz, ya'ni birikma disjunksiya va inkor orqali ifodalanadi va A tizimining barcha funktsiyalari B tizimi ustidagi formulalar bilan ifodalanadi. Lemma bo'yicha, B tizimi tugallangan. 2) 1 -bandga o'xshab: (x ∨ y) = x & y ⇔ x ∨ y = (x & y) va Lemma 2 2 -bandning haqiqatini bildiradi. 3) x | y = (x va y), x | x = x; x & y = (x | y) = (x | y) | (x | y) va Lemma 2 ga binoan tizim tugallangan. 4) x = x ⊕1 va Lemma 2 ga ko'ra tizim tugallangan. Teorema isbotlangan. 17. Jegalkin algebrasi. Operatsion xususiyatlari va to'liqligi Jegalkin S4 = (⊕, &, 1) asosida aniqlangan mantiqiy funktsiyalar to'plami deyiladi Jegalkin algebra. Asosiy xususiyatlar. 1. almashish qobiliyati h1⊕h2 = h2⊕h1 h1 & h2 = h2 & h1 2. assotsiativlik h1⊕ (h2⊕h3) = (h1⊕h2) ⊕h3 h1 & (h2 & h3) = (h1 & h2) & h3 3. tarqatish qobiliyati h1 & (h2⊕h3) = (h1 & h2) ⊕ (h1 & h3) 4. doimiylarning xususiyatlari 5.h⊕h = 0 h & h = h Bayonot... Boshqa barcha mantiqiy funktsiyalarni Jegalkin algebrasi yordamida ifodalash mumkin: x → y = 1⊕x⊕xy x ↓ y = 1⊕x⊕y⊕xy 18. Polinom Jegalkina. Qurilish usullari. Misol. Jegalkin polinomi (2 polinomli modul) n x 1, x 2 ... x n o'zgaruvchilar shakl ifodasi deyiladi: c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n, bu erda C k doimiylari 0 yoki 1 qiymatlarini olishi mumkin. Agar Jegalkin polinomida alohida o'zgaruvchilar mahsuloti bo'lmasa, u chiziqli (chiziqli funktsiya) deb ataladi. Masalan, f = x⊕yz⊕xyz va f 1 = 1⊕x⊕y⊕z polinomlar, ikkinchisi esa chiziqli funksiya. Teorema... Har bir mantiqiy funktsiya o'ziga xos tarzda Jegalkin polinomi sifatida ifodalanadi. Bu erda berilgan funktsiyadagi Jegalkin polinomlarini tuzishning asosiy usullari keltirilgan. 1. Aniqlanmagan koeffitsientlar usuli. P (x 1, x 2 ... x n) berilgan f (x 1, x 2 ... x n) funktsiyani amalga oshiruvchi kerakli Jegalkin polinomi bo'lsin. Keling, uni shaklda yozaylik P = c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n C k koeffitsientlarini toping. Buning uchun biz haqiqat jadvalining har bir satridan x 1, x 2 ... x n o'zgaruvchilarini ketma -ket belgilaymiz. Natijada, biz 2 n noma'lum bo'lgan 2 n tenglama tizimiga ega bo'lamiz, u o'ziga xos echimga ega. Buni hal qilib, biz polinom P (X 1, X 2 ... X n) koeffitsientlarini topamiz. 2. Formulalarni biriktiruvchi (, &) ustidan o'zgartirishga asoslangan usul. Biror formulani tuzing F f (X 1, X 2 ... X n) funktsiyasini bajarib, (, &) birikmalar to'plami ustida. Keyin hamma joyda A shaklidagi subformulalarni A1 ga almashtiring, tarqatish qonunidan foydalanib qavslarni kengaytiring (3 -xususiyatga qarang) va keyin 4 va 5 -xossalarni qo'llang. Misol... F (X, Y) = X → Y funksiyaning Jegalkin polinomini tuzing Yechim. 1. (aniqlanmagan koeffitsientlar usuli). Keling, kerakli polinomni quyidagi shaklda yozamiz: P = c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy Haqiqat jadvalidan foydalanib, biz buni topamiz f (0,0) = P (0,0) = C 0 = 1 f (0,1) = P (0,1) = C 0 ⊕C 2 = 1 f (1,0) = P (1,0) = C 0 ⊕C 1 = 0 f (1,1) = P (1,1) = C 0 ⊕C 1 ⊕C 2 ⊕C 12 = 1 Biz qaerdan topamiz, C 0 = 1, C 1 = 1, C 2 = 0, C 12 = 1 Shuning uchun: x → y = 1⊕X⊕XY. 2. (Formulalarni o'zgartirish usuli.). Bizda: x → y = xvy = (xy) = (x (y⊕1)) ⊕1 = 1⊕x⊕xy E'tibor bering, Jegalkin algebrasining afzalligi (boshqa algebralar bilan taqqoslaganda) mantiq arifmetizatsiyasida yotadi, bu esa mantiqiy funktsiyalarni o'zgartirishga imkon beradi. Mantiqiy algebra bilan solishtirganda uning kamchiligi formulalarning noqulayligidir.