Mantiqiy algebra Hasse diagrammasi Bo'linuvchilarning mantiqiy algebrasi. Misollar yechish

Mavzu: Mantiqiy algebradan foydalanish
Reja:

1. 
   Mantiqiy algebra
   
2. 
   Hasse diagrammasi Bo'linuvchilarning mantiqiy algebrasi.
   
3. 
   Misollar yechish
   

Mantiqiy algebra (tuzilishi) - Boolean algebra (structure)

Mavzu bilan tanishish uchun qarang Mantiqiy algebra. Muqobil taqdimot uchun qarang Mantiqiy algebralar kanonik ravishda aniqlangan.
Ushbu maqola umumiy ro'yxatini o'z ichiga oladi ma'lumotnomalar, lekin bu asosan tasdiqlanmagan bo'lib qolmoqda, chunki unga mos keladigan etishmayapti satrda keltirilgan. Iltimos yordam bering takomillashtirish tomonidan ushbu maqola tanishtirish aniqroq iqtiboslar. (2013 yil iyul) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)
Yilda mavhum algebra, a Mantiqiy algebra yoki Mantiq panjarasi a to'ldirildi tarqatish panjarasi. Ushbu turdagi algebraik tuzilish ikkalasining ham muhim xususiyatlarini aks ettiradi o'rnatilgan operatsiyalar va mantiq operatsiyalar. Mantiqiy algebra $ a $ ning umumlashtirilishi sifatida qaralishi mumkin quvvat o'rnatilgan algebra yoki a to'plamlar maydoniyoki uning elementlarini umumlashtirilgan deb ko'rish mumkin haqiqat qadriyatlari. Bu shuningdek, a De Morgan algebra va a Kleen algebra (involyatsiya bilan).
Mantiqiy algebra paydo bo'lishiga olib keladi a Mantiq uzuk, va aksincha, mos keladigan halqalarni ko'paytirish bilan birikma yoki uchrashmoq ∧ va qo'ng'iroq qo'shilishi eksklyuziv disjunktsiya yoki nosimmetrik farq (emas ajratish ∨). Biroq, mantiqiy halqalar nazariyasi ikki operator o'rtasida o'ziga xos assimetriyaga ega, aks holda mantiqiy algebra aksiomalari va teoremalari nazariya simmetriyasini ifodalaydi. ikkilik tamoyili.[1]
Pastki guruhlarning mantiqiy panjarasi
Tarix
"Boolean algebra" atamasi sharaflanadi Jorj Bul (1815–1864), ingliz matematikasi. U tanishtirdi algebraik tizim dastlab kichik risolada, Mantiqning matematik tahlili, 1847 yilda davom etgan jamoatchilik o'rtasidagi tortishuvlarga javoban nashr etilgan Augustus De Morgan va Uilyam Xemiltonva keyinchalik muhimroq kitob sifatida, Fikrlash qonunlari, 1854 yilda nashr etilgan. Boole formulasi yuqorida tavsiflanganidan ba'zi muhim jihatlari bilan farq qiladi. Masalan, Boole-dagi konyunksiya va disjunksiya ikki tomonlama amal emas edi. Boolean algebra 1860-yillarda, yozgan qog'ozlarda paydo bo'ldi Uilyam Jevons va Charlz Sanders Peirs. Mantiq algebrasining birinchi sistematik taqdimoti va tarqatuvchi panjaralar 1890 yilga qarzdor Vorlesungen ning Ernst Shreder. Mantiq algebrasini ingliz tilida birinchi keng qamrovli davolash A. N. Uaytxed1898 yil Umumjahon algebra. Boolean algebra zamonaviy aksiomatik ma'noda aksiomatik algebraik tuzilish sifatida 1904 yildagi qog'ozdan boshlanadi. Edvard V. Xantington. Mantiqiy algebra jiddiy matematikaga aylandi Marshall Stoun 1930-yillarda va Garret Birxof1940 yil Panjara nazariyasi. 1960-yillarda, Pol Koen, Dana Skottva boshqalar chuqur yangi natijalarni topdilar matematik mantiq va aksiomatik to'plam nazariyasi mantiqiy algebra filiallaridan foydalangan holda, ya'ni majburlash va Mantiqiy qiymatga ega modellar.
Ta'rif
A Mantiqiy algebra oltipanjara dan iborat o'rnatilgan A, ikkitasi bilan jihozlangan ikkilik operatsiyalar ∧ ("uchrashish" yoki "va" deb nomlanadi), ∨ ("qo'shilish" yoki "yoki" deb nomlanadi), a bir martalik operatsiya ¬ ("komplement" yoki "not" deb nomlanadi) va ikkita element 0 va 1 in A ("pastki" va "yuqori" yoki "eng kichik" va "eng katta" elementlar deb nomlanadi, shuningdek, mos ravishda ⊥ va ⊤ belgilar bilan belgilanadi), barcha elementlar uchun shunday a, b va v ning A, quyidagi aksiomalar tutmoq:[2]
a ∨ (b ∨ v) = (a ∨ b) ∨ v a ∧ (b ∧ v) = (a ∧ b) ∧ v assotsiativlik
a ∨ b = b ∨ a a ∧ b = b ∧ a kommutativlik
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a singdirish
a ∨ 0 = a a ∧ 1 = a shaxsiyat
a ∨ (b ∧ v) = (a ∨ b) ∧ (a ∨ v) a ∧ (b ∨ v) = (a ∧ b) ∨ (a ∧ v) tarqatish
a ∨ ¬a = 1 a ∧ ¬a = 0 qo'shimchalar
Ammo, absorbsiya qonuni va hatto assotsiativlik qonuni aksiomalar to'plamidan chiqarilishi mumkinligiga e'tibor bering, chunki ular boshqa aksiomalardan kelib chiqishi mumkin (qarang. Tasdiqlangan xususiyatlar).
Faqat bitta elementi bo'lgan mantiqiy algebra a deb ataladi mantiqsiz mantiqiy algebra yoki a mantiqiy algebra degeneratsiyasi. (Eski asarlarda ba'zi mualliflar 0 va 1 bo'lishi shart edi aniq Ushbu holatni istisno qilish uchun elementlar.)[iqtibos kerak]
Yuqoridagi so'nggi uchta juft aksiomalardan (identifikatsiya, taqsimot va qo'shimchalar) yoki yutilish aksiomasidan kelib chiqadigan narsa
a = b ∧ a agar va faqat agar a ∨ b = b.
Munosabati The bilan belgilanadi a ≤ b agar bu teng shartlar bajarilsa, a qisman buyurtma eng kichik element 0 va eng katta element 1. Uchrashuv a ∧ b va qo'shilish a ∨ b ikkita elementning elementlari ularga to'g'ri keladi cheksiz va supremumnavbati bilan ≤ ga nisbatan.
Birinchi to'rtta aksiomalar jufti a ta'rifini tashkil qiladi cheklangan panjara.
Birinchi beshta juft aksiomalardan kelib chiqadiki, har qanday to'ldiruvchi noyobdir.
Aksiomalar to'plami o'z-o'zini dual agar aksiomada ∨ ∧ bilan 0 ni 1 ga almashtirsa, natija yana aksioma bo'ladi degan ma'noda. Shuning uchun, bu amalni mantiq algebrasiga (yoki mantiya panjarasiga) qo'llash orqali, bir xil elementlarga ega bo'lgan boshqa mantiq algebrasini oladi; unga deyiladi ikkilamchi.[3]
Misollar
Mantiqiy bo'lmagan eng oddiy mantiqiy algebra, mantiqiy algebra ikki elementli, faqat ikkita elementga ega, 0 va 1 va qoidalar bilan belgilanadi:
∧ 0 1
0 0 0
1 0 1
∨ 0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
Uning dasturlari mavjud mantiq, 0 ni talqin qilish yolg'on, 1 sifatida to'g'ri, ∧ kabi va, ∨ kabi yokiva ¬ kabi emas. Mantiqiy va mantiqiy operatsiyalarni o'z ichiga olgan iboralar bayon shakllarini ifodalaydi va yuqoridagi aksiomalar yordamida ikkita shunday ifoda tengligini ko'rsatishi mumkin, agar faqat tegishli bayonot shakllari bo'lsa. mantiqiy ekvivalent.
Ikki elementli Boolean algebra, shuningdek, elektronni loyihalash uchun ishlatiladi elektrotexnika;[4] bu erda 0 va 1 bittadan ikki xil holatni anglatadi bit a raqamli elektron, odatda yuqori va past Kuchlanish. Sxemalar o'zgaruvchini o'z ichiga olgan iboralar bilan tavsiflanadi va agar ikkita mos keladigan sxemalar kirish-chiqarish xatti-harakatlari bir xil bo'lsa, shunday ikkita ifoda o'zgaruvchilarning barcha qiymatlari uchun teng bo'ladi. Bundan tashqari, har qanday mumkin bo'lgan kirish-chiqish xatti-harakatlari mos mantiqiy ifoda bilan modellashtirilishi mumkin.
Mantiq algebralarining umumiy nazariyasida ham ikki elementli mantiq algebrasi muhim ahamiyatga ega, chunki bir nechta o'zgaruvchini o'z ichiga olgan tenglama odatda barcha mantiq algebralarida to'g'ri bo'ladi va agar u faqat ikki elementli mantiq algebrasida (agar buni tekshirish mumkin bo'lsa) ahamiyatsiz qo'pol kuch kichik sonli o'zgaruvchilar algoritmi). Masalan, quyidagi qonunlar (Konsensus teoremalari) odatda barcha mantiq algebralarida amal qiladi:
(a ∨ b) ∧ (¬a ∨ v) ∧ (b ∨ v) ≡ (a ∨ b) ∧ (¬a ∨ v)
(a ∧ b) ∨ (¬a ∧ v) ∨ (b ∧ v) ≡ (a ∧ b) ∨ (¬a ∧ v)
The quvvat o'rnatilgan (barcha kichik to'plamlar to'plami) har qanday berilgan bo'sh bo'lmagan to'plam S mantiqiy algebra hosil qiladi, an to'plamlar algebrasi, ikkita operatsiya bilan ∨: = ∪ (birlashma) va ∧: = ∩ (kesishish). Eng kichik element 0 bu bo'sh to'plam va eng katta element 1 to'plamdir S o'zi.
Hasse diagrammasi Bo'linuvchilarning mantiqiy algebrasi.
Har qanday kishi uchun tabiiy son n, barchasi ijobiy bo'linuvchilar ning n, belgilaydigan a≤b agar a ajratadi b, hosil qiladi a tarqatish panjarasi. Ushbu panjara mantiqiy algebradir, agar shunday bo'lsa n bu kvadratsiz. Ushbu mantiq algebrasining pastki va yuqori elementi tabiiy son 1 va nnavbati bilan. Ning to'ldiruvchisi a tomonidan berilgan n/a. Uchrashuv va qo'shilish a va b tomonidan berilgan eng katta umumiy bo'luvchi (gcd) va eng kichik umumiy ko'plik (lcm) ning a va bnavbati bilan. Uzuk qo'shilishi a+b lcm bilan berilgan (a,b) / gcd (a,b). Rasmda misol keltirilgan n = 30. Qarama-qarshi misol sifatida kvadratsizlarni hisobga olgan holda n= 60, 30 ning eng katta umumiy bo'luvchisi va uni to'ldiruvchi 2 2 bo'ladi, pastki element esa 1 bo'lishi kerak.
Mantiq algebralarining boshqa misollari kelib chiqadi topologik bo'shliqlar: agar X topologik makon, keyin barcha kichik to'plamlar to'plami X qaysiki ham ochiq, ham yopiq ∨: = ∪ (birlashma) va ∧: = ∩ (kesishma) amallari bilan mantiqiy algebra hosil qiladi.
Agar R o'zboshimchalik bilan uzuk va biz to'plamini aniqlaymiz markaziy idempotentlar tomonidan
A = { e ∈ R : e2 = e, sobiq = xe, ∀x ∈ R }
keyin to'plam A amallari bilan mantiqiy algebraga aylanadi e ∨ f := e + f - ef va e ∧ f := ef.
Gomomorfizmlar va izomorfizmlar
A homomorfizm ikki mantiya algebrasi o'rtasida A va B a funktsiya f : A → B hamma uchun shunday a, b yilda A:
f(a ∨ b) = f(a) ∨ f(b),
f(a ∧ b) = f(a) ∧ f(b),
f(0) = 0,
f(1) = 1.
Shundan kelib chiqadiki f(¬a) = ¬f(a) Barcha uchun a yilda A. The sinf barcha mantiya algebralaridan ushbu morfizm tushunchasi bilan birgalikda a to'liq pastki toifa ning toifasi panjaralardan.

An izomorfizm ikki mantiya algebrasi o'rtasida A va B gomomorfizmdir f : A → B teskari homomorfizm bilan, ya'ni homomorfizm bilan g : B → A shunday tarkibi g ∘ f: A → A bo'ladi identifikatsiya qilish funktsiyasi kuni Ava tarkibi f ∘ g: B → B identifikatsiya qilish funktsiyasi yoqilgan B. Boolean algebralarining homomorfizmi, agar shunday bo'lsa, izomorfizmdir ikki tomonlama.

Mantiq uzuklar
Asosiy maqola: Mantiq uzuk
Har bir mantiqiy algebra (A, ∧, ∨) a ga olib keladi uzuk (A, +, ·) Belgilash orqali a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (bu operatsiya deyiladi nosimmetrik farq to'plamlarda va XOR mantiqqa nisbatan) va a · b := a ∧ b. Ushbu halqaning nol elementi mantiq algebrasining 0 ga to'g'ri keladi; halqaning multiplikativ identifikatsiya elementi bu mantiq algebrasining 1-qismidir. Ushbu uzuk shunday xususiyatga ega a · a = a Barcha uchun a yilda A; ushbu xususiyatga ega uzuklar chaqiriladi Mantiq uzuklar.
Aksincha, agar mantiqiy uzuk bo'lsa A berilgan, uni aniqlab mantiqiy algebraga aylantirishimiz mumkin x ∨ y := x + y + (x · y) va x ∧ y := x · y.[5][6]Ushbu ikkita qurilish bir-biriga teskari bo'lganligi sababli, har bir mantiqiy uzuk mantiq algebrasidan kelib chiqadi va aksincha deb ayta olamiz. Bundan tashqari, xarita f : A → B mantiqiy algebralarning gomomorfizmi, agar bu mantiqiy uzuklarning gomomorfizmi bo'lsa. The toifalar mantiqiy halqalar va mantiq algebralari tengdir.[7]
Ssiang (1985) a berdi qoidalarga asoslangan algoritm ga tekshirish ikkala ixtiyoriy ibora har bir mantiqiy uzukda bir xil qiymatni bildiradimi, umuman ko'proq, Boudet, Jouanna, va Shmidt-Schauß (1989) algoritmini bergan tenglamalarni echish mantiqiy uzuklar va mantiqiy algebralarning o'xshashligini qo'llagan holda, ikkala algoritmda dastur mavjud avtomatlashtirilgan teorema.