กลับไปหน้าบทความ

อ่าน 4 นาที

วงแหวนบูลีน

ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2

วงแหวนบูลีน

ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น[ 1 ] [ 2 ] [ 3 ]ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2

วงแหวนบูลีนทุกวงก่อให้เกิดพีชคณิตบูลีนโดยการคูณวงแหวนสอดคล้องกับการเชื่อมหรือพบและการบวกวงแหวนสอดคล้องกับการแยกแบบพิเศษหรือผลต่างสมมาตร (ไม่ใช่การแยก [ 4 ]ซึ่งจะประกอบเป็นเซมิริง ) ในทางกลับกัน พีชคณิตบูลีนทุก วงก่อให้เกิดวงแหวนบูลีน วงแหวนบูลีนตั้งชื่อตามผู้ก่อตั้งพีชคณิตบูลีนจอร์จ บู

สัญกรณ์

มีระบบการเขียนสัญลักษณ์อย่างน้อยสี่ระบบที่แตกต่างกันและเข้ากันไม่ได้สำหรับวงแหวนและพีชคณิตบูลีน:

  • ในพีชคณิตเชิงสลับที่สัญลักษณ์มาตรฐานคือการใช้x + y = ( x ∧ ¬ y ) ∨ (¬ xy )สำหรับผลรวมของริงของxและyและใช้xy = xyสำหรับผลคูณของทั้งสอง
  • ในตรรกศาสตร์สัญลักษณ์ที่นิยมใช้คือxyสำหรับการตัดกัน (เหมือนกับผลคูณของริง) และx y สำหรับการรวม ซึ่งเขียนในรูปสัญลักษณ์ของริง (ดังที่กล่าวไว้ข้างต้น) เป็นx + y + xy
  • ในทฤษฎีเซตและตรรกศาสตร์ มักใช้x · y สำหรับการตัดกัน และx + yสำหรับการรวมxy [ 5 ] การใช้ + นี้แตกต่างจากการใช้ในทฤษฎีวงแหวน
  • ธรรมเนียมปฏิบัติที่พบได้ไม่บ่อยนักคือการใช้xyสำหรับผลคูณ และxy สำหรับผลรวม ของวงแหวน เพื่อหลีกเลี่ยงความกำกวมของเครื่องหมาย+

ในอดีต คำว่า "วงแหวนบูลีน" ถูกใช้เพื่อหมายถึง "วงแหวนบูลีนที่อาจไม่มีเอกลักษณ์" และ "พีชคณิตบูลีน" ถูกใช้เพื่อหมายถึงวงแหวนบูลีนที่มีเอกลักษณ์ การมีอยู่ของเอกลักษณ์เป็นสิ่งจำเป็นในการพิจารณาวงแหวนว่าเป็นพีชคณิตเหนือฟิลด์ของสององค์ประกอบมิฉะนั้นจะไม่มีโฮโมมอร์ฟิซึมของวงแหวน (แบบมีเอกลักษณ์) จากฟิลด์ของสององค์ประกอบไปยังวงแหวนบูลีน (นี่เหมือนกับการใช้คำว่า "วงแหวน" และ "พีชคณิต" ในทฤษฎีการวัดแบบเก่า[ a ] )

ตัวอย่าง

ตัวอย่างหนึ่งของวงแหวนบูลีนคือเซตกำลังของเซตใดๆXซึ่งการบวกในวงแหวนคือการลบสมมาตรและการคูณคือการหาจุดตัดอีกตัวอย่างหนึ่ง เรายังสามารถพิจารณาเซตของ เซต ย่อยจำกัดหรือเซตย่อยร่วมจำกัดทั้งหมดของXซึ่งมีผลต่างสมมาตรและการหาจุดตัดเป็นตัวดำเนินการเช่นกัน โดยทั่วไปแล้ว ด้วยตัวดำเนินการเหล่านี้ฟิลด์ของเซต ใดๆ ก็ เป็นวงแหวนบูลีนได้ ตามทฤษฎีบทการแทนของสโตนวงแหวนบูลีนทุกวงจะสมสัณฐานกับฟิลด์ของเซต (ซึ่งถือว่าเป็นวงแหวนที่มีตัวดำเนินการเหล่านี้)

ความสัมพันธ์กับพีชคณิตบูลีน

แผนภาพเวนน์สำหรับการดำเนินการทางตรรกะบูลีน ได้แก่ การเชื่อม การแยก และการเติมเต็ม

เนื่องจากการดำเนินการร่วมในพีชคณิตบูลีนมักเขียนในรูปการบวก ดังนั้นในบริบทนี้จึงเหมาะสมที่จะใช้สัญลักษณ์ แทนการบวกวงแหวน ซึ่งเป็นสัญลักษณ์ที่มักใช้แทนการดำเนินการแบบเอกซ์คลูซีฟออร์

กำหนดให้ริงบูลีนRสำหรับxและyในRเราสามารถกำหนดได้ดังนี้

xy = xy ,
xy = xyxy ,
¬ x = 1 ⊕ x .

การดำเนินการเหล่านี้จึงเป็นไปตามสัจพจน์ทั้งหมดสำหรับการตัดกัน การรวมกัน และการเติมเต็มในพีชคณิตบูลีนดังนั้นวงแหวนบูลีนทุกวงจึงกลายเป็นพีชคณิตบูลีน ในทำนองเดียวกัน พีชคณิตบูลีนทุกตัวจะกลายเป็นวงแหวนบูลีนได้ดังนี้:

xy = xy ,
xy = ( xy ) ∧ ฌ( xy )

หากแปลงวงแหวนบูลีนเป็นพีชคณิตบูลีนด้วยวิธีนี้ แล้วแปลงพีชคณิตบูลีนเป็นวงแหวนอีกครั้ง ผลลัพธ์ที่ได้ก็คือวงแหวนเดิม ผลลัพธ์ที่คล้ายกันนี้ก็ใช้ได้เช่นกันเมื่อเริ่มต้นจากพีชคณิตบูลีน

ฟังก์ชันระหว่างวงแหวนบูลีนสองวงจะเป็นโฮโมมอร์ฟิซึมของวงแหวนก็ต่อเมื่อมันเป็นโฮโมมอร์ฟิซึมของพีชคณิตบูลีนที่สอดคล้องกันเท่านั้น ยิ่งไปกว่านั้น เซตย่อยของวงแหวนบูลีนจะเป็นไอเดียลของวงแหวน (ไอเดียลวงแหวนเฉพาะ, ไอเดียลวงแหวนสูงสุด) ก็ต่อเมื่อมันเป็นไอเดียลอันดับ (ไอเดียลอันดับเฉพาะ, ไอเดียลอันดับสูงสุด) ของพีชคณิตบูลีนเท่านั้นวงแหวนผลหารของวงแหวนบูลีนมอดูลไอเดียลของวงแหวนจะสอดคล้องกับพีชคณิตแฟกเตอร์ของพีชคณิตบูลีนที่สอดคล้องกันมอดูลไอเดียลอันดับที่สอดคล้องกัน

คุณสมบัติของวงแหวนบูลีน

วงแหวนบูลีนทุกวงRสอดคล้องกับxx = 0สำหรับทุกxในRเพราะเรารู้ว่า

xx = ( xx ) 2 = x 2x 2x 2x 2 = xxxx

และเนื่องจาก( R , ⊕)เป็นกลุ่มอาเบเลียน เราจึงสามารถลบxx ออก จากทั้งสองข้างของสมการนี้ได้ ซึ่งจะได้xx = 0การพิสูจน์ที่คล้ายกันนี้แสดงให้เห็นว่าวงแหวนบูลีนทุกวงเป็นวงแหวนสลับที่ได้ :

xy = ( xy ) 2 = x 2xyyxy 2 = xxyyxyและผลลัพธ์ที่ได้คือ xyyx = 0ซึ่งหมายความว่า xy = yx (โดยใช้คุณสมบัติข้อแรกข้างต้น)

คุณสมบัติxx = 0แสดงให้เห็นว่าวงแหวนบูลีนใดๆ ก็เป็นพีชคณิตแบบเชื่อมโยงบนฟิลด์F 2ที่มีสมาชิกสองตัวได้เพียงวิธีเดียวเท่านั้น โดยเฉพาะอย่างยิ่ง วงแหวนบูลีนจำกัดใดๆ ก็มีจำนวนสมาชิกเป็นกำลังของสอง ไม่ใช่ว่าพีชคณิตแบบเชื่อมโยงที่มี เอกลักษณ์ ทุกตัวบนF 2จะเป็นวงแหวนบูลีนเสมอไป ตัวอย่างเช่น พิจารณาวงแหวนพหุนามF 2 [ X ]

วงแหวนผลหารR / IของวงแหวนบูลีนR ใดๆ มอดูลไอเดียลI ใดๆ ก็เป็นวงแหวนบูลีนเช่นกัน ในทำนองเดียวกันวงแหวนย่อย ใดๆ ของวงแหวนบูลีนก็เป็นวงแหวนบูลีนด้วย

การหาตำแหน่ง เฉพาะที่RS −1ของวงแหวนบูลีนRโดยเซตSR ใดๆ ก็ เป็นวงแหวนบูลีนเช่นกัน เนื่องจากองค์ประกอบทุกตัวในการหาตำแหน่งเฉพาะที่นั้นเป็นตัวผกผันได้

วงแหวนผลหารสูงสุดQ ( R ) (ในความหมายของ Utumi และLambek ) ของวงแหวนบูลีนRเป็นวงแหวนบูลีน เนื่องจากเอนโดมอร์ฟิซึมบางส่วนทุกตัวเป็นไอเดมโพเทนต์[ 6 ]

ไอเดียลเฉพาะตัวPทุก ตัว ในวงแหวนบูลีนRเป็น ไอเดีย ลสูงสุด : วงแหวนผลหารR / Pเป็นโดเมนเชิงอิน ทิก รัลและเป็นวงแหวนบูลีนด้วย ดังนั้นจึงสมมูลกับฟิลด์F₂ ซึ่งแสดงให้เห็น ถึงความเป็นไอเดียลสูงสุดของPเนื่องจากไอเดียลสูงสุดเป็นไอเดียลเฉพาะตัวเสมอ ไอเดียลเฉพาะตัวและไอเดียลสูงสุดจึงตรงกันในวงแหวนบูลีน

ไอเดียลที่สร้างขึ้นอย่างจำกัดทุกตัวของวงแหวนบูลีนเป็นไอเดียลหลัก (อันที่จริง( x , y ) = ( x + y + xy ))ยิ่งไปกว่านั้น เนื่องจากสมาชิกทั้งหมดเป็นตัวผกผัน วงแหวนบูลีนจึงเป็นวงแหวนปกติแบบสลับที่ได้ของฟอน นอยมันน์และด้วยเหตุนี้จึงเป็นวงแหวนแบนราบโดยสมบูรณ์ ซึ่งหมายความว่าโมดูลทุกตัวบนวงแหวนเหล่านี้เป็นโมดูลแบนราบ

การรวมกัน

การรวมกันในวงแหวนบูลีนสามารถตัดสินได้ [ 7 ] นั่นคือ มีอัลกอริทึมเพื่อแก้สมการใดๆ บนวงแหวนบูลีน ทั้งการรวมกันและการจับคู่ในวงแหวนบูลีนอิสระที่สร้างขึ้นอย่างจำกัด นั้นเป็นปัญหา NP-completeและทั้งสองเป็น ปัญหา NP-hardในวงแหวนบูลีนที่นำเสนออย่างจำกัด[ 8 ] (ในความเป็นจริง เนื่องจากปัญหาการรวมกันใดๆf ( X ) = g ( X )ในวงแหวนบูลีนสามารถเขียนใหม่ได้เป็นปัญหาการจับคู่f ( X ) + g ( X ) = 0ดังนั้นปัญหาจึงเทียบเท่ากัน)

การรวมในวงแหวนบูลีนจะเป็นแบบเอกภาพหากสัญลักษณ์ฟังก์ชันที่ไม่ได้ตีความทั้งหมดเป็นแบบศูนย์ และจะเป็นแบบจำกัดในกรณีอื่น ๆ (กล่าวคือ หากสัญลักษณ์ฟังก์ชันที่ไม่ได้ปรากฏในลายเซ็นของวงแหวนบูลีนเป็นค่าคงที่ทั้งหมด จะมีตัวรวมทั่วไปที่สุดและในกรณีอื่น ๆชุดตัวรวมที่สมบูรณ์ขั้นต่ำจะเป็นแบบจำกัด) [ 9 ]

ดูเพิ่มเติม

หมายเหตุ

  1. ^เมื่อวงแหวนบูลีนมีเอกลักษณ์ การดำเนินการส่วนเติมเต็มจะสามารถกำหนดได้บนวงแหวนนั้น และลักษณะสำคัญของคำจำกัดความสมัยใหม่ของทั้งพีชคณิตบูลีนและพีชคณิตซิกมาก็คือ พวกมันมีการดำเนินการส่วนเติมเต็ม

การอ้างอิง

  1. ^ Fraleigh 1976 , หน้า 25, 200
  2. เฮอร์สไตน์ 1975 , หน้า 130, 268
  3. ^แมคคอย 1968หน้า 46
  4. ^ "การแยกส่วนเป็นการดำเนินการบวกในวงแหวนบูลีน "
  5. ^ Koppelberg 1989 , นิยาม 1.1, หน้า 7
  6. ^ Brainerd & Lambek 1959 , บทสรุปที่ 2
  7. ^มาร์ตินและนิปโคว์ 1986
  8. คันดรี-โรดี, คาปูร์ และนเรนดราน 2528
  9. บูเดต์, ฌัวเนาด์ และ ชมิดต์-เชาส์ 1989
  • จอห์น อาร์มสตรอง, วงแหวนบูลีน
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Boolean_ring&oldid=1351899674#Examples "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ วงแหวนบูลีน

ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2

สัญกรณ์

มีระบบการเขียนสัญลักษณ์อย่างน้อยสี่ระบบที่แตกต่างกันและเข้ากันไม่ได้สำหรับวงแหวนและพีชคณิตบูลีน:

ตัวอย่าง

ตัวอย่างหนึ่งของวงแหวนบูลีนคือ เซตกำลัง ของเซตใดๆ X ซึ่งการบวกในวงแหวนคือ การลบสมมาตร และการคูณคือ การหาจุดตัด อีกตัวอย่างหนึ่ง เรายังสามารถพิจารณาเซตของ เซต ย่อยจำกัด หรือเซตย่อยร่วมจำกัดทั้งหมดของ X ซึ่งมีผลต่างสมมาตรและการหาจุดตัดเป็นตัวดำเนินการเช่นกัน...

ความสัมพันธ์กับพีชคณิตบูลีน

เนื่องจากการดำเนินการร่วม ∨ ในพีชคณิตบูลีนมักเขียนในรูปการบวก ดังนั้นในบริบทนี้จึงเหมาะสมที่จะใช้สัญลักษณ์ ⊕ แทนการบวกวงแหวน ซึ่งเป็นสัญลักษณ์ที่มักใช้แทนการดำเนินการ แบบเอกซ์คลูซีฟออ ร์