อ่าน 4 นาที
วงแหวนบูลีน
ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2
วงแหวนบูลีน
ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น[ 1 ] [ 2 ] [ 3 ]ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2
วงแหวนบูลีนทุกวงก่อให้เกิดพีชคณิตบูลีนโดยการคูณวงแหวนสอดคล้องกับการเชื่อมหรือพบ∧และการบวกวงแหวนสอดคล้องกับการแยกแบบพิเศษหรือผลต่างสมมาตร (ไม่ใช่การแยก∨ [ 4 ]ซึ่งจะประกอบเป็นเซมิริง ) ในทางกลับกัน พีชคณิตบูลีนทุก วงก่อให้เกิดวงแหวนบูลีน วงแหวนบูลีนตั้งชื่อตามผู้ก่อตั้งพีชคณิตบูลีนจอร์จ บูล
สัญกรณ์
มีระบบการเขียนสัญลักษณ์อย่างน้อยสี่ระบบที่แตกต่างกันและเข้ากันไม่ได้สำหรับวงแหวนและพีชคณิตบูลีน:
- ในพีชคณิตเชิงสลับที่สัญลักษณ์มาตรฐานคือการใช้x + y = ( x ∧ ¬ y ) ∨ (¬ x ∧ y )สำหรับผลรวมของริงของxและyและใช้xy = x ∧ yสำหรับผลคูณของทั้งสอง
- ในตรรกศาสตร์สัญลักษณ์ที่นิยมใช้คือx ∧ yสำหรับการตัดกัน (เหมือนกับผลคูณของริง) และx ∨ y สำหรับการรวม ซึ่งเขียนในรูปสัญลักษณ์ของริง (ดังที่กล่าวไว้ข้างต้น) เป็นx + y + xy
- ในทฤษฎีเซตและตรรกศาสตร์ มักใช้x · y สำหรับการตัดกัน และx + yสำหรับการรวมx ∨ y [ 5 ] การใช้ + นี้แตกต่างจากการใช้ในทฤษฎีวงแหวน
- ธรรมเนียมปฏิบัติที่พบได้ไม่บ่อยนักคือการใช้xyสำหรับผลคูณ และx ⊕ y สำหรับผลรวม ของวงแหวน เพื่อหลีกเลี่ยงความกำกวมของเครื่องหมาย+
ในอดีต คำว่า "วงแหวนบูลีน" ถูกใช้เพื่อหมายถึง "วงแหวนบูลีนที่อาจไม่มีเอกลักษณ์" และ "พีชคณิตบูลีน" ถูกใช้เพื่อหมายถึงวงแหวนบูลีนที่มีเอกลักษณ์ การมีอยู่ของเอกลักษณ์เป็นสิ่งจำเป็นในการพิจารณาวงแหวนว่าเป็นพีชคณิตเหนือฟิลด์ของสององค์ประกอบมิฉะนั้นจะไม่มีโฮโมมอร์ฟิซึมของวงแหวน (แบบมีเอกลักษณ์) จากฟิลด์ของสององค์ประกอบไปยังวงแหวนบูลีน (นี่เหมือนกับการใช้คำว่า "วงแหวน" และ "พีชคณิต" ในทฤษฎีการวัดแบบเก่า[ a ] )
ตัวอย่าง
ตัวอย่างหนึ่งของวงแหวนบูลีนคือเซตกำลังของเซตใดๆXซึ่งการบวกในวงแหวนคือการลบสมมาตรและการคูณคือการหาจุดตัดอีกตัวอย่างหนึ่ง เรายังสามารถพิจารณาเซตของ เซต ย่อยจำกัดหรือเซตย่อยร่วมจำกัดทั้งหมดของXซึ่งมีผลต่างสมมาตรและการหาจุดตัดเป็นตัวดำเนินการเช่นกัน โดยทั่วไปแล้ว ด้วยตัวดำเนินการเหล่านี้ฟิลด์ของเซต ใดๆ ก็ เป็นวงแหวนบูลีนได้ ตามทฤษฎีบทการแทนของสโตนวงแหวนบูลีนทุกวงจะสมสัณฐานกับฟิลด์ของเซต (ซึ่งถือว่าเป็นวงแหวนที่มีตัวดำเนินการเหล่านี้)
ความสัมพันธ์กับพีชคณิตบูลีน

เนื่องจากการดำเนินการร่วม∨ในพีชคณิตบูลีนมักเขียนในรูปการบวก ดังนั้นในบริบทนี้จึงเหมาะสมที่จะใช้สัญลักษณ์⊕ แทนการบวกวงแหวน ซึ่งเป็นสัญลักษณ์ที่มักใช้แทนการดำเนินการแบบเอกซ์คลูซีฟออร์
กำหนดให้ริงบูลีนRสำหรับxและyในRเราสามารถกำหนดได้ดังนี้
- x ∧ y = xy ,
- x ∨ y = x ⊕ y ⊕ xy ,
- ¬ x = 1 ⊕ x .
การดำเนินการเหล่านี้จึงเป็นไปตามสัจพจน์ทั้งหมดสำหรับการตัดกัน การรวมกัน และการเติมเต็มในพีชคณิตบูลีนดังนั้นวงแหวนบูลีนทุกวงจึงกลายเป็นพีชคณิตบูลีน ในทำนองเดียวกัน พีชคณิตบูลีนทุกตัวจะกลายเป็นวงแหวนบูลีนได้ดังนี้:
- xy = x ∧ y ,
- x ⊕ y = ( x ∨ y ) ∧ ฌ( x ∧ y )
หากแปลงวงแหวนบูลีนเป็นพีชคณิตบูลีนด้วยวิธีนี้ แล้วแปลงพีชคณิตบูลีนเป็นวงแหวนอีกครั้ง ผลลัพธ์ที่ได้ก็คือวงแหวนเดิม ผลลัพธ์ที่คล้ายกันนี้ก็ใช้ได้เช่นกันเมื่อเริ่มต้นจากพีชคณิตบูลีน
ฟังก์ชันระหว่างวงแหวนบูลีนสองวงจะเป็นโฮโมมอร์ฟิซึมของวงแหวนก็ต่อเมื่อมันเป็นโฮโมมอร์ฟิซึมของพีชคณิตบูลีนที่สอดคล้องกันเท่านั้น ยิ่งไปกว่านั้น เซตย่อยของวงแหวนบูลีนจะเป็นไอเดียลของวงแหวน (ไอเดียลวงแหวนเฉพาะ, ไอเดียลวงแหวนสูงสุด) ก็ต่อเมื่อมันเป็นไอเดียลอันดับ (ไอเดียลอันดับเฉพาะ, ไอเดียลอันดับสูงสุด) ของพีชคณิตบูลีนเท่านั้นวงแหวนผลหารของวงแหวนบูลีนมอดูลไอเดียลของวงแหวนจะสอดคล้องกับพีชคณิตแฟกเตอร์ของพีชคณิตบูลีนที่สอดคล้องกันมอดูลไอเดียลอันดับที่สอดคล้องกัน
คุณสมบัติของวงแหวนบูลีน
วงแหวนบูลีนทุกวงRสอดคล้องกับx ⊕ x = 0สำหรับทุกxในRเพราะเรารู้ว่า
- x ⊕ x = ( x ⊕ x ) 2 = x 2 ⊕ x 2 ⊕ x 2 ⊕ x 2 = x ⊕ x ⊕ x ⊕ x
และเนื่องจาก( R , ⊕)เป็นกลุ่มอาเบเลียน เราจึงสามารถลบx ⊕ x ออก จากทั้งสองข้างของสมการนี้ได้ ซึ่งจะได้x ⊕ x = 0การพิสูจน์ที่คล้ายกันนี้แสดงให้เห็นว่าวงแหวนบูลีนทุกวงเป็นวงแหวนสลับที่ได้ :
- x ⊕ y = ( x ⊕ y ) 2 = x 2 ⊕ xy ⊕ yx ⊕ y 2 = x ⊕ xy ⊕ yx ⊕ yและผลลัพธ์ที่ได้คือ xy ⊕ yx = 0ซึ่งหมายความว่า xy = yx (โดยใช้คุณสมบัติข้อแรกข้างต้น)
คุณสมบัติx ⊕ x = 0แสดงให้เห็นว่าวงแหวนบูลีนใดๆ ก็เป็นพีชคณิตแบบเชื่อมโยงบนฟิลด์F 2ที่มีสมาชิกสองตัวได้เพียงวิธีเดียวเท่านั้น โดยเฉพาะอย่างยิ่ง วงแหวนบูลีนจำกัดใดๆ ก็มีจำนวนสมาชิกเป็นกำลังของสอง ไม่ใช่ว่าพีชคณิตแบบเชื่อมโยงที่มี เอกลักษณ์ ทุกตัวบนF 2จะเป็นวงแหวนบูลีนเสมอไป ตัวอย่างเช่น พิจารณาวงแหวนพหุนามF 2 [ X ]
วงแหวนผลหารR / IของวงแหวนบูลีนR ใดๆ มอดูลไอเดียลI ใดๆ ก็เป็นวงแหวนบูลีนเช่นกัน ในทำนองเดียวกันวงแหวนย่อย ใดๆ ของวงแหวนบูลีนก็เป็นวงแหวนบูลีนด้วย
การหาตำแหน่ง เฉพาะที่RS −1ของวงแหวนบูลีนRโดยเซตS ⊆ R ใดๆ ก็ เป็นวงแหวนบูลีนเช่นกัน เนื่องจากองค์ประกอบทุกตัวในการหาตำแหน่งเฉพาะที่นั้นเป็นตัวผกผันได้
วงแหวนผลหารสูงสุด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 ]
ดูเพิ่มเติม
หมายเหตุ
- ^เมื่อวงแหวนบูลีนมีเอกลักษณ์ การดำเนินการส่วนเติมเต็มจะสามารถกำหนดได้บนวงแหวนนั้น และลักษณะสำคัญของคำจำกัดความสมัยใหม่ของทั้งพีชคณิตบูลีนและพีชคณิตซิกมาก็คือ พวกมันมีการดำเนินการส่วนเติมเต็ม
การอ้างอิง
- ^ Fraleigh 1976 , หน้า 25, 200
- ↑เฮอร์สไตน์ 1975 , หน้า 130, 268
- ^แมคคอย 1968หน้า 46
- ^ "การแยกส่วนเป็นการดำเนินการบวกในวงแหวนบูลีน "
- ^ Koppelberg 1989 , นิยาม 1.1, หน้า 7
- ^ Brainerd & Lambek 1959 , บทสรุปที่ 2
- ^มาร์ตินและนิปโคว์ 1986
- ↑คันดรี-โรดี, คาปูร์ และนเรนดราน 2528
- ↑บูเดต์, ฌัวเนาด์ และ ชมิดต์-เชาส์ 1989
ลิงก์ภายนอก
- จอห์น อาร์มสตรอง, วงแหวนบูลีน
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ วงแหวนบูลีน
ในทางคณิตศาสตร์วงแหวนบูลีนR คือวงแหวนที่ x² = x สำหรับทุกxในRนั่นคือวงแหวนที่ประกอบด้วยสมาชิกที่เป็นตัวประกอบเอกลักษณ์เท่านั้น ตัวอย่างหนึ่งคือวงแหวนของจำนวนเต็มมอดูล 2
สัญกรณ์
มีระบบการเขียนสัญลักษณ์อย่างน้อยสี่ระบบที่แตกต่างกันและเข้ากันไม่ได้สำหรับวงแหวนและพีชคณิตบูลีน:
ตัวอย่าง
ตัวอย่างหนึ่งของวงแหวนบูลีนคือ เซตกำลัง ของเซตใดๆ X ซึ่งการบวกในวงแหวนคือ การลบสมมาตร และการคูณคือ การหาจุดตัด อีกตัวอย่างหนึ่ง เรายังสามารถพิจารณาเซตของ เซต ย่อยจำกัด หรือเซตย่อยร่วมจำกัดทั้งหมดของ X ซึ่งมีผลต่างสมมาตรและการหาจุดตัดเป็นตัวดำเนินการเช่นกัน...
ความสัมพันธ์กับพีชคณิตบูลีน
เนื่องจากการดำเนินการร่วม ∨ ในพีชคณิตบูลีนมักเขียนในรูปการบวก ดังนั้นในบริบทนี้จึงเหมาะสมที่จะใช้สัญลักษณ์ ⊕ แทนการบวกวงแหวน ซึ่งเป็นสัญลักษณ์ที่มักใช้แทนการดำเนินการ แบบเอกซ์คลูซีฟออ ร์