ความสัมพันธ์แบบไบนารี ความสัมพันธ์ที่เท่าเทียมกัน เซตผลหาร

ทฤษฎีเซต แนวคิดพื้นฐาน

ทฤษฎีเซตเป็นคำจำกัดความพื้นฐานของคณิตศาสตร์สมัยใหม่ สร้างขึ้นโดย Georg Cantor ในปี 1860 เขาเขียนว่า: “หลายอันก็คือหลาย ๆ อันรวมกันเป็นอันเดียว” แนวคิดเรื่องเซตเป็นหนึ่งในแนวคิดพื้นฐานทางคณิตศาสตร์ที่ไม่ได้นิยามไว้ ไม่สามารถลดทอนเป็นแนวคิดอื่นที่ง่ายกว่าได้ ดังนั้นจึงไม่สามารถกำหนดได้แต่สามารถอธิบายได้เท่านั้น ดังนั้นเซตคือการรวมกันเป็นวัตถุเดียวที่สามารถแยกแยะได้อย่างชัดเจนด้วยสัญชาตญาณหรือความคิดของเรา ชุดของวัตถุบางอย่างที่กำหนดโดยลักษณะทั่วไป

ตัวอย่างเช่น,

1. ชาวเมือง Voronezh จำนวนมาก

2. ชุดจุดบนเครื่องบิน

3. เซตของจำนวนธรรมชาติ ℕฯลฯ

ชุดมักจะแสดงด้วยอักษรละตินตัวพิมพ์ใหญ่ ( ก, บี, ซีฯลฯ) วัตถุที่ประกอบเป็นเซตหนึ่งๆ เรียกว่า องค์ประกอบของเซตนั้น องค์ประกอบของเซตจะแสดงด้วยอักษรละตินตัวเล็ก ( ก ข คฯลฯ) ถ้า เอ็กซ์– ตั้งค่าแล้วบันทึก x∈Xหมายความว่าอย่างนั้น เอ็กซ์เป็นองค์ประกอบของชุด เอ็กซ์หรืออะไร เอ็กซ์เป็นของชุด เอ็กซ์และรายการ x∉Xองค์ประกอบนั้น เอ็กซ์ไม่ได้อยู่ในชุด เอ็กซ์- ตัวอย่างเช่น ให้ ℕ เป็นเซตของจำนวนธรรมชาติ แล้ว 5 ℕ , ก 0,5∉ℕ .

ถ้าเป็นชุด ยประกอบด้วยองค์ประกอบของชุด เอ็กซ์แล้วพวกเขาก็พูดอย่างนั้น ยเป็นสับเซตของเซต เอ็กซ์และแสดงถึง Y⊂H(หรือ ย⊆ฮ- เช่น ชุดของจำนวนเต็ม ℤ เป็นสับเซตของจำนวนตรรกยะ ℚ .

ถ้าเป็นสองชุด เอ็กซ์และ ยการรวมสองรายการเกิดขึ้นพร้อมกัน เอ็กซ์วายและ ใช่ เอ็กซ์, เช่น. เอ็กซ์เป็นสับเซตของเซต ยและ ยเป็นสับเซตของเซต เอ็กซ์แล้วก็ชุด เอ็กซ์และ ยประกอบด้วยองค์ประกอบเดียวกัน ชุดดังกล่าว เอ็กซ์และ ยถูกเรียกว่าเท่ากันและเขียน: X=ย.

คำว่าเซตว่างมักใช้- Ø - ชุดที่ไม่มีองค์ประกอบเดียว มันเป็นสับเซตของเซตใดๆ

วิธีการต่อไปนี้สามารถใช้เพื่ออธิบายชุดต่างๆ

วิธีการระบุชุด

1. การแจงนับวัตถุ ใช้สำหรับเซตจำกัดเท่านั้น

ตัวอย่างเช่น, X=(x1, x2, x3… xn)- บันทึก Y ={1, 4, 7, 5} หมายความว่าชุดประกอบด้วยตัวเลขสี่ตัว 1, 4, 7, 5 .

2. การบ่งชี้คุณสมบัติเฉพาะขององค์ประกอบของชุด

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

X=(x: ป(x))

(ชุด เอ็กซ์ประกอบด้วยองค์ประกอบดังกล่าว เอ็กซ์ซึ่งทรัพย์สินนั้นถืออยู่ พี(เอ็กซ์)).

ชุดว่างสามารถระบุได้โดยการระบุคุณสมบัติ: Ø=(x: x≠x)

คุณสามารถสร้างชุดใหม่โดยใช้ชุดที่กำหนดไว้แล้วโดยใช้การดำเนินการกับชุด

ตั้งค่าการดำเนินการ

1. ยูเนี่ยน (ผลรวม) คือเซตที่ประกอบด้วยองค์ประกอบเหล่านั้นทั้งหมด ซึ่งแต่ละองค์ประกอบอยู่ในเซตอย่างน้อยหนึ่งเซต กหรือ ใน.

A∪B=(x: x A หรือ x B)

2. จุดตัด (ผลิตภัณฑ์) คือเซตที่ประกอบด้วยองค์ประกอบทั้งหมด ซึ่งแต่ละองค์ประกอบเป็นของเซตพร้อมกัน กและอีกมากมาย ใน.

A∩B=(x: x A และ x B)

3. กำหนดความแตกต่าง กและ ในเป็นเซตที่ประกอบด้วยองค์ประกอบทั้งหมดที่อยู่ในเซต กและไม่ได้อยู่ในฝูงชน ใน.

A\B=(x: x A และ x B)

4. ถ้า ก– สับเซตของเซต ใน- นั่นเป็นจำนวนมาก บี\เอเรียกว่าส่วนเติมเต็มของเซต กถึงหลาย ๆ คน ในและแสดงถึง เอ'.

5. ผลต่างสมมาตรของสองชุดคือเซต A∆B=(A\B) (บี\เอ)

เอ็น- เซตของจำนวนธรรมชาติทั้งหมด
ซี- เซตของจำนวนเต็มทั้งหมด
ถาม- เซตของจำนวนตรรกยะทั้งหมด
ร- เซตของจำนวนจริงทั้งหมด
ค- เซตของจำนวนเชิงซ้อนทั้งหมด
ซี 0- เซตของจำนวนเต็มที่ไม่เป็นลบทั้งหมด

คุณสมบัติของการดำเนินการในชุด:

1. ก บี=บี A (การสับเปลี่ยนของสหภาพ)

2. ก บี=บี A (การสับเปลี่ยนของทางแยก)

3. เอ(บี ค)=(ก ใน) C (สมาคมสหภาพแรงงาน)

4. ก (ใน ค)=(ก ใน) C (การเชื่อมโยงทางแยก)

5. ก (ใน ค)=(ก ใน) (ก C) (กฎข้อที่ 1 ของการกระจาย)

6. ก (ใน ค)=(ก ใน) (ก C) (กฎข้อที่ 2 ของการกระจาย)

7. ก Ø=ก

8. ก ยู = ยู

9. ก Ø= Ø

10. ก ยู=ก

11. (อ ข)'=ก' B' (กฎของมอร์แกน)

12. (อ ข)'=ก' B' (กฎของมอร์แกน)

13. ก (ก B)=A (กฎการดูดซึม)

14. ก (ก B)=A (กฎการดูดซึม)

มาพิสูจน์ทรัพย์สินหมายเลข 11 กันดีกว่า (ก ข)'=ก' ใน'

ตามคำจำกัดความของเซตที่เท่ากัน เราต้องพิสูจน์การรวมสองรายการเข้าด้วยกัน 1) (ก ข)’ ⊂เอ’ ใน';

2) เอ' บี⊂(อ ใน)'.

เพื่อพิสูจน์การรวมครั้งแรก ให้พิจารณาองค์ประกอบที่กำหนดเอง x∈(อ B)’=X\(A∪B)นี่หมายความว่า x∈X, x∉ A∪B- มันเป็นไปตามนั้น x∉Aและ x∉Bนั่นเป็นเหตุผลว่าทำไม x∈X\Aและ x∈X\Bซึ่งหมายความว่า x∈A'∩B'- ดังนั้น, (ก ข)’⊂เอ’ ใน'

กลับถ้า x∈A’ ใน', ที่ เอ็กซ์พร้อมกันเป็นของชุด เอ' บี'ซึ่งหมายความว่า x∉Aและ x∉B- สืบต่อจากนี้ไปว่า x∉ อ ในนั่นเป็นเหตุผลว่าทำไม x∈(อ ใน)'- เพราะฉะนั้น, เอ' บี⊂(อ ใน)'.

ดังนั้น, (ก ข)'=ก' ใน'

ชุดที่ประกอบด้วยสององค์ประกอบซึ่งมีการกำหนดลำดับขององค์ประกอบ เรียกว่าคู่อันดับ หากต้องการเขียนให้ใช้วงเล็บ (x1,x2)– เซตที่มีสององค์ประกอบ โดย x 1 ถือเป็นองค์ประกอบแรก และ x 2 ถือเป็นองค์ประกอบที่สอง คู่รัก (x1,x2)และ (x2,x1)ที่ไหน x 1 ≠ x 2ถือว่าแตกต่าง.

ชุดที่ประกอบด้วยองค์ประกอบ n ซึ่งกำหนดลำดับขององค์ประกอบ เรียกว่าชุดลำดับขององค์ประกอบ n ตัว

สินค้าคาร์ทีเซียนเป็นเซตที่กำหนดขึ้นเอง X 1, X 2,…,X นสั่งชุดขององค์ประกอบ n โดยที่ x1 เอ็กซ์ 1 , x 2 X 2 ,…, xn เอ็กซ์ เอ็น

เอ็กซ์ 1 Xn

ถ้าเป็นชุด X 1, X 2,…,X นจับคู่ (X 1 = X 2 =…=X น)จากนั้นผลิตภัณฑ์ของพวกเขาจะแสดงแทน Xn.

ตัวอย่างเช่น, ℝ 2 – ชุดคู่ลำดับของจำนวนจริง

ความสัมพันธ์ที่เท่าเทียมกัน ชุดปัจจัย

ขึ้นอยู่กับเซตที่กำหนด สามารถสร้างเซตใหม่ได้โดยพิจารณาจากเซตของเซตย่อยบางเซต ในกรณีนี้ เรามักจะไม่พูดถึงเซตย่อย แต่พูดถึงตระกูลหรือคลาสของเซตย่อย

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

อนุญาต เอ็กซ์ไม่ใช่เซตว่าง แล้วก็เป็นเซตย่อยใดๆ รจากการทำงาน เอ็กซ์ เอ็กซ์เรียกว่าความสัมพันธ์ไบนารีบนเซต เอ็กซ์- ถ้าเป็นคู่. (x,y)รวมอยู่ใน อาร์พวกเขาบอกว่าองค์ประกอบ x มีความสัมพันธ์กัน รกับ ที่.

ตัวอย่างเช่นความสัมพันธ์ x=y, x≥yเป็นความสัมพันธ์แบบไบนารี่บนเซต ℝ.

ความสัมพันธ์แบบไบนารี รบนชุด เอ็กซ์เรียกว่าความสัมพันธ์ที่เท่าเทียมกันถ้า:

1. (ก,ก) ร; เอ็กซ์ X (คุณสมบัติการสะท้อนแสง)

2. (ค,ย) R => (ใช่,x) R (คุณสมบัติสมมาตร)

3. (ค,ย) อาร์, (ใช่, z) R จากนั้น (x,z) R (คุณสมบัติการถ่ายทอด)

ถ้าเป็นคู่. (x,y)เข้าสู่ความสัมพันธ์ที่เท่าเทียมกัน จากนั้น x และ y จึงเรียกว่าเทียบเท่า (เอ็กซ์~ป)

1.ให้ ℤ – ชุดของจำนวนเต็ม ม≥1– จำนวนเต็ม ให้เรานิยามความสัมพันธ์ที่เท่าเทียมกัน รบน ℤ อย่างนั้น เปล่า~เค, ถ้า นะเคหารด้วย ม- ตรวจสอบว่าคุณสมบัติเป็นไปตามความสัมพันธ์นี้หรือไม่

1. การสะท้อนกลับ

สำหรับใครก็ตาม n∈ℤ ℤ เช่นนั้น (หน้า,พี)∈R

ร-ร=0- เพราะ 0∈ ℤ , ที่ (น,พี)∈ℤ.

2. สมมาตร

จาก (น,เค) ∈Rเป็นไปตามนั้นว่ามีสิ่งนั้นอยู่ р∈ℤ, อะไร nk=mp;

k-n =m(-p), -p∈ ℤ, เพราะฉะนั้น (k,n) ∈R.

3. การเคลื่อนย้าย

จากอะไร (น,เค) ∈R, (k,q) ∈Rตามมาว่ามีเช่นนั้น หน้า 1และ ร 2 ∈ ℤ, อะไร nk=mp 1และ k-q=mp 2- เมื่อเพิ่มนิพจน์เหล่านี้เข้าไป เราก็จะได้สิ่งนั้น n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ- นั่นเป็นเหตุผล (n,q) ∈ ℤ.

2. พิจารณาชุด เอ็กซ์ทุกส่วนของอวกาศหรือเครื่องบิน . =(ก, ข)- ให้เราแนะนำความสัมพันธ์ที่เท่าเทียมกัน รบน เอ็กซ์.

(นั่นคือ ซึ่งมีคุณสมบัติดังต่อไปนี้: แต่ละองค์ประกอบของชุดจะเทียบเท่ากับตัวมันเอง ถ้า xเทียบเท่า ย, ที่ ยเทียบเท่า x- ถ้า xเทียบเท่า ย, ก ยเทียบเท่า z, ที่ xเทียบเท่า z ).

จากนั้นจึงเรียกเซตของคลาสที่เทียบเท่าทั้งหมด ชุดปัจจัยและถูกกำหนดไว้ การแบ่งเซตออกเป็นคลาสขององค์ประกอบที่เทียบเท่ากันเรียกว่า การแยกตัวประกอบ.

แสดงจาก เอ็กซ์เข้าไปในเซตของคลาสที่เทียบเท่ากันเรียกว่า การทำแผนที่ปัจจัย.

ตัวอย่าง

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

ถ้าหากต้องการแยกตัวประกอบปริภูมิเชิงเส้น จะมีการใส่สเปซย่อยบางตัวเข้าไป และสันนิษฐานว่าถ้าผลต่างของสององค์ประกอบของปริภูมิเดิมเป็นของสเปซย่อยนี้ องค์ประกอบเหล่านี้จะเท่ากัน ดังนั้นชุดตัวประกอบจะเป็นปริภูมิเชิงเส้นและเรียกว่า พื้นที่ปัจจัย

ตัวอย่าง

ดูเพิ่มเติม

มูลนิธิวิกิมีเดีย

2010.

ดูว่า "ชุดปัจจัย" ในพจนานุกรมอื่นคืออะไร:

หลักการเชิงตรรกะที่เป็นรากฐานของคำจำกัดความผ่านนามธรรม (ดูคำจำกัดความผ่านนามธรรม): ความสัมพันธ์ใดๆ ของประเภทของความเท่าเทียมกัน ที่กำหนดบนชุดองค์ประกอบเริ่มต้นบางชุด แยก (แบ่ง จำแนก) ต้นฉบับ... ... รูปแบบการคิดที่สะท้อนถึงคุณสมบัติสำคัญ ความเชื่อมโยง และความสัมพันธ์ของวัตถุและปรากฏการณ์ในความขัดแย้งและการพัฒนา ความคิดหรือระบบความคิดที่มีลักษณะทั่วไป แยกแยะวัตถุบางประเภทตามลักษณะทั่วไปบางอย่างและโดยรวม... ...

สารานุกรมผู้ยิ่งใหญ่แห่งสหภาพโซเวียต โคโฮโมวิทยาของกลุ่มกาลัวส์ ถ้า M เป็นกลุ่มอาบีเลียนและกลุ่ม Galois ของส่วนขยายที่กระทำกับ M ดังนั้นกลุ่ม cohomology ของ Galois คือกลุ่ม cohomology ที่กำหนดโดยกลุ่มเชิงซ้อนที่ประกอบด้วยแผนที่ทั้งหมด และ d เป็นตัวดำเนินการขอบเขตร่วม (ดู Cohomology ของกลุ่ม).... ..

สารานุกรมคณิตศาสตร์ โคโฮโมวิทยาของกลุ่มกาลัวส์ ถ้า M เป็นกลุ่มอาบีเลียนและกลุ่ม Galois ของส่วนขยายที่กระทำกับ M ดังนั้นกลุ่ม cohomology ของ Galois คือกลุ่ม cohomology ที่กำหนดโดยกลุ่มเชิงซ้อนที่ประกอบด้วยแผนที่ทั้งหมด และ d เป็นตัวดำเนินการขอบเขตร่วม (ดู Cohomology ของกลุ่ม).... ..

โครงสร้างสู่สรวงสวรรค์ ปรากฏครั้งแรกในทฤษฎีเซต และจากนั้นก็ถูกนำมาใช้กันอย่างแพร่หลายในพีชคณิต โทโพโลยี และสาขาอื่นๆ ของคณิตศาสตร์ กรณีพิเศษที่สำคัญของ I. p. คือกลุ่มที่มีโครงสร้างทางคณิตศาสตร์ประเภทเดียวกัน อนุญาต... โคโฮโมวิทยาของกลุ่มกาลัวส์ ถ้า M เป็นกลุ่มอาบีเลียนและกลุ่ม Galois ของส่วนขยายที่กระทำกับ M ดังนั้นกลุ่ม cohomology ของ Galois คือกลุ่ม cohomology ที่กำหนดโดยกลุ่มเชิงซ้อนที่ประกอบด้วยแผนที่ทั้งหมด และ d เป็นตัวดำเนินการขอบเขตร่วม (ดู Cohomology ของกลุ่ม).... ..

บทความนี้มีการแนะนำสั้นเกินไป โปรดเพิ่มส่วนเกริ่นนำที่แนะนำหัวข้อของบทความโดยย่อและสรุปเนื้อหา... Wikipedia

บทความนี้เกี่ยวกับระบบพีชคณิต สำหรับสาขาตรรกะทางคณิตศาสตร์ที่ศึกษาข้อความและการดำเนินการ โปรดดูพีชคณิตของลอจิก พีชคณิตแบบบูลเป็นเซต A ที่ไม่ว่างเปล่าซึ่งมีการดำเนินการไบนารี่สองครั้ง (คล้ายกับการร่วม) ... ... Wikipedia

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

ในเรขาคณิต ส่วนที่มีทิศทางถูกเข้าใจว่าเป็นคู่ของจุดที่ได้รับคำสั่ง โดยจุดแรกเรียกว่าจุดเริ่มต้น และจุดที่สอง B คือจุดสิ้นสุด สารบัญ 1 คำจำกัดความ ... Wikipedia

ในสาขาวิชาคณิตศาสตร์แขนงต่างๆ เคอร์เนลของการแม็ปคือเซตเคอร์ฟ ซึ่งในแง่หนึ่งแสดงถึงความแตกต่างระหว่าง f และการแม็ปแบบฉีด คำจำกัดความเฉพาะอาจแตกต่างกันไป แต่สำหรับการทำแผนที่แบบฉีด f... ... Wikipedia

ตั้งค่าปัจจัย

ฝูงชน.

ความสัมพันธ์ลำดับบางส่วนบนเซต x คือความสัมพันธ์แบบไบนารีที่มีลักษณะต้านสมมาตร การสะท้อนกลับ และสกรรมกริยา และเขียนแทนด้วย
เป็นคู่:

ความสัมพันธ์แบบไบนารีเรียกว่าความอดทนหากเป็นแบบสะท้อนกลับและสมมาตร

ความสัมพันธ์แบบไบนารี่เรียกว่า quasi-order ถ้าเป็นแบบสะท้อนกลับ ไม่สมมาตร และสกรรมกริยา (สั่งล่วงหน้า)

ความสัมพันธ์แบบไบนารี่เรียกว่าลำดับที่เข้มงวดหากเป็นแบบสะท้อนกลับและสกรรมกริยา

การดำเนินการพีชคณิตแบบเอนารีบนเซต M คือฟังก์ชัน

– การดำเนินการแบบเอกเทศ

– การดำเนินการแบบไบนารี

– การดำเนินการไตรภาคี

การดำเนินการพีชคณิตไบนารี –

– การดำเนินการที่กำหนดองค์ประกอบบางส่วนของเซต M ให้กับคู่อันดับแต่ละคู่จากเซต M

คุณสมบัติ:

1) การเปลี่ยนแปลง:

2) การเชื่อมโยง:

องค์ประกอบที่เป็นกลาง

ตั้งค่า M สำหรับการดำเนินการพีชคณิตไบนารี

องค์ประกอบนี้มีชื่อว่า:

• 
  ปัจจัย ชุด– ชุดของคลาสที่เทียบเท่าของสิ่งนี้ ชุด- ความสัมพันธ์คำสั่งซื้อบางส่วนเปิดอยู่ มากมาย x เรียกว่าความสัมพันธ์แบบไบนารี่...


• 
  คำถามต่อไป” ปัจจัย ชุด. ปัจจัย ชุด– จำนวนทั้งสิ้น รูปแบบการคูณและการบวก


• 
  ปัจจัย ชุด– จำนวนทั้งสิ้น
  มากมาย- ชุดของวัตถุที่กำหนดและแตกต่างซึ่งเป็นไปได้โดยรวม


• 
  ฟังก์ชันการคูณคือ... มีต่อ » ปัจจัย ชุด. ปัจจัย ชุด– ชุดของคลาสที่เทียบเท่าของสิ่งนี้ ชุด.


• 
  ในความเป็นจริงแล้วกระบวนการผลิตมีความซับซ้อนมากขึ้น และผลิตภัณฑ์ก็เป็นผลมาจากการใช้งาน ชุด ปัจจัย.


• 
  คุณภาพของการตัดสินใจของฝ่ายบริหารขึ้นอยู่กับ ชุด ปัจจัยที่สำคัญที่สุดคือ n


• 
  การเพิ่มประสิทธิภาพการตัดสินใจระดมทุนเป็นกระบวนการวิจัย ชุด ปัจจัยส่งผลต่อผลลัพธ์ที่คาดหวัง...

ให้ R เป็นความสัมพันธ์แบบไบนารีบนเซต X เรียกว่าความสัมพันธ์ R สะท้อนแสง , ถ้า (x, x) О R สำหรับ x О X ทั้งหมด; สมมาตร – ถ้าจาก (x, y) О R ตามมาด้วย (y, x) О R; หมายเลขสกรรมกริยา 23 สอดคล้องกับตัวเลือก 24 ถ้า (x, y) О R และ (y, z) О R หมายถึง (x, z) О R

ตัวอย่างที่ 1

เราจะบอกว่า x О X มีเหมือนกัน ที่มีองค์ประกอบ y О X ถ้าเป็นเซต
x ç y ไม่ว่างเปล่า ความสัมพันธ์ที่มีเหมือนกันจะเป็นความสัมพันธ์แบบสะท้อนกลับและสมมาตร แต่ไม่ใช่แบบสกรรมกริยา

ความสัมพันธ์ที่เท่าเทียมกันบน X คือความสัมพันธ์แบบสะท้อน สกรรมกริยา และสมมาตร เป็นเรื่องง่ายที่จะเห็นว่า R Í X ´ X จะเป็นความสัมพันธ์ที่เท่าเทียมกัน ถ้าหากการรวมเข้าไว้:

Id X Í R (การสะท้อนกลับ)

R -1 Í R (สมมาตร)

R ° R Í R (สกรรมกริยา)

ในความเป็นจริง เงื่อนไขทั้งสามนี้เทียบเท่ากับสิ่งต่อไปนี้:

รหัส X Í R, R -1 = R, R ° R = R.

โดยการแยกของเซต X คือเซต A ของเซตย่อยที่แยกจากกันแบบคู่ a Í X โดยที่ UA = X ในแต่ละพาร์ติชัน A เราสามารถเชื่อมโยงความสัมพันธ์สมมูล ~ บน X โดยใส่ x ~ y ถ้า x และ y เป็นองค์ประกอบของ Î A .

ความสัมพันธ์ที่เท่าเทียมกันแต่ละรายการ ~ บน X สอดคล้องกับพาร์ติชัน A ซึ่งองค์ประกอบนั้นเป็นเซตย่อย ซึ่งแต่ละองค์ประกอบประกอบด้วยองค์ประกอบที่อยู่ในความสัมพันธ์ ~ เซตย่อยเหล่านี้เรียกว่า คลาสที่เท่าเทียมกัน - พาร์ติชั่น A นี้เรียกว่าชุดตัวประกอบของเซต X เทียบกับ ~ และเขียนแทนด้วย: X/~

ให้เรานิยามความสัมพันธ์ ~ บนเซต w ของจำนวนธรรมชาติ โดยใส่ x ~ y ถ้าเศษที่เหลือจากการหาร x และ y ด้วย 3 เท่ากัน จากนั้น w/~ ประกอบด้วยคลาสความเท่าเทียมกันสามคลาสที่สอดคล้องกับเศษ 0, 1 และ 2

ความสัมพันธ์การสั่งซื้อ

ความสัมพันธ์ไบนารี่ R บนเซต X เรียกว่า ต่อต้านสมมาตร ถ้าจาก x R y และ y R x จะได้ดังนี้: x = y ความสัมพันธ์ไบนารี่ R บนเซต X เรียกว่า ความสัมพันธ์ในการสั่งซื้อ ถ้าเป็นการสะท้อนกลับ ต่อต้านสมมาตร และสกรรมกริยา จะเห็นได้ง่ายว่าสิ่งนี้เทียบเท่ากับเงื่อนไขต่อไปนี้:

1) Id X Í R (การสะท้อนกลับ)

2) R ç R -1 (ต่อต้านสมมาตร)

3) R ° R Í R (การถ่ายทอด)

คู่ลำดับ (X, R) ซึ่งประกอบด้วยเซต X และความสัมพันธ์ลำดับ R บน X เรียกว่า ชุดที่สั่งบางส่วน .

ตัวอย่างที่ 1

ให้ X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3))

เนื่องจาก R เป็นไปตามเงื่อนไข 1 – 3 ดังนั้น (X, R) จึงเป็นเซตที่มีการเรียงลำดับบางส่วน สำหรับองค์ประกอบ x = 2, y = 3, ทั้ง x R y และ y R x ไม่เป็นความจริง องค์ประกอบดังกล่าวเรียกว่า หาที่เปรียบมิได้ - โดยปกติแล้วความสัมพันธ์ของคำสั่งซื้อจะแสดงด้วย £ ในตัวอย่างที่ให้มา 0 £ 1 และ 2 £ 2 แต่มันไม่จริงที่ 2 £ 3

ตัวอย่างที่ 2

อนุญาต< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

องค์ประกอบ x, y О X ของชุดที่เรียงลำดับบางส่วน (X, £) ถูกเรียก เทียบเคียงได้ ถ้า x £ y หรือ y £ x

เรียกว่าชุดที่สั่งบางส่วน (X, £) สั่งเป็นเส้นตรง หรือ โซ่ ถ้ามีองค์ประกอบสองอย่างที่สามารถเทียบเคียงได้ ชุดจากตัวอย่างที่ 2 จะถูกเรียงลำดับเชิงเส้น แต่ชุดจากตัวอย่างที่ 1 จะไม่เรียงลำดับ

เรียกสับเซต A Í X ของเซตที่เรียงลำดับบางส่วน (X, £) ขอบเขตด้านบน หากมีองค์ประกอบ x О X โดยที่ £ x สำหรับ О A ทั้งหมด องค์ประกอบ x О X เรียกว่า ใหญ่ที่สุด ใน X ถ้า y £ x สำหรับ y ทั้งหมด О X องค์ประกอบ x О X เรียกว่าสูงสุดหากไม่มีองค์ประกอบ y О X แตกต่างจาก x ซึ่ง x £ y ในตัวอย่างที่ 1 องค์ประกอบที่ 2 และ 3 จะเป็นค่าสูงสุด แต่ไม่ใช่ค่าที่ใหญ่ที่สุด กำหนดไว้เช่นเดียวกัน ขีดจำกัดล่าง เซตย่อย องค์ประกอบที่เล็กที่สุดและน้อยที่สุด ในตัวอย่างที่ 1 องค์ประกอบ 0 จะเป็นทั้งค่าน้อยที่สุดและค่าต่ำสุด ในตัวอย่างที่ 2 นั้น 0 ก็มีคุณสมบัติเหล่านี้เช่นกัน แต่ (w, £) ไม่มีทั้งองค์ประกอบที่ใหญ่ที่สุดหรือสูงสุด

ถ้าทัศนคติ ร มีคุณสมบัติดังต่อไปนี้: สะท้อนกลับ สมมาตร สกรรมกริยา เช่น คือความสัมพันธ์ที่เท่าเทียมกัน (~ หรือ ≡ หรือ E) บนเซต ม จากนั้นเซตของคลาสความเท่าเทียมกันเรียกว่าเซตตัวประกอบของเซต ม เกี่ยวกับความเท่าเทียมกัน ร และถูกกำหนดไว้ นาย

มีสับเซตขององค์ประกอบของเซต ม เทียบเท่า x , เรียกว่า คลาสที่เท่าเทียมกัน.

จากคำจำกัดความของชุดตัวประกอบ จะเป็นไปตามว่าเป็นเซตย่อยของบูลีน: .

ฟังก์ชันนี้เรียกว่า บัตรประจำตัวและกำหนดไว้ดังต่อไปนี้:

ทฤษฎีบท.พีชคณิตตัวประกอบ เอฟ n /~ เป็น isomorphic ของพีชคณิตของฟังก์ชันบูลีน บี n

การพิสูจน์.

มอร์ฟิซึ่มที่ต้องการ ξ : เอฟ n / ~ → บี n ถูกกำหนดโดยกฎต่อไปนี้: คลาสที่เทียบเท่า ~(φ) ฟังก์ชั่นตรงกัน ฉ φ , มีตารางความจริงสำหรับสูตรใดก็ได้จากชุด ~(φ) - เนื่องจากคลาสความเท่าเทียมกันที่แตกต่างกันจะสอดคล้องกับตารางความจริงที่ต่างกัน การทำแผนที่ ξ injective และเนื่องจากสำหรับฟังก์ชันบูลีนใดๆ ฉ จาก ในพี มีสูตรแทนฟังก์ชัน ฉ จากนั้นทำแผนที่ ξ การผ่าตัด การดำเนินการของร้านค้า 0, 1 เมื่อแสดง ξ ได้รับการตรวจสอบโดยตรง ซีทีดี.

โดยทฤษฎีบทความสมบูรณ์ของฟังก์ชันของทุกฟังก์ชันที่ไม่คงที่ 0 สอดคล้องกับ SDNF บางส่วน ψ อยู่ในชั้นเรียน ~(φ) = ξ -1 (ฉ) สูตรที่แสดงถึงฟังก์ชัน ฉ - ปัญหาการอยู่ในห้องเรียนก็เกิดขึ้น ~(φ) รูปแบบปกติที่ไม่ต่อเนื่องซึ่งมีโครงสร้างที่ง่ายที่สุด

สิ้นสุดการทำงาน -

หัวข้อนี้เป็นของส่วน:

หลักสูตรการบรรยายเรื่องวินัยคณิตศาสตร์แบบไม่ต่อเนื่อง

มหาวิทยาลัยแห่งรัฐมอสโกแห่งวิศวกรรมโยธา.. สถาบันเศรษฐศาสตร์การจัดการและระบบสารสนเทศในการก่อสร้าง.. IEEE..

หากคุณต้องการเนื้อหาเพิ่มเติมในหัวข้อนี้ หรือคุณไม่พบสิ่งที่คุณกำลังมองหา เราขอแนะนำให้ใช้การค้นหาในฐานข้อมูลผลงานของเรา:

เราจะทำอย่างไรกับเนื้อหาที่ได้รับ:

หากเนื้อหานี้มีประโยชน์สำหรับคุณ คุณสามารถบันทึกลงในเพจของคุณบนโซเชียลเน็ตเวิร์ก:

ทวีต

หัวข้อทั้งหมดในส่วนนี้:

วิชาคณิตศาสตร์ไม่ต่อเนื่อง
วิชาคณิตศาสตร์แบบไม่ต่อเนื่อง (จำกัด, จำกัด) เป็นสาขาหนึ่งของคณิตศาสตร์ที่ศึกษาคุณสมบัติของโครงสร้างที่ไม่ต่อเนื่อง ในขณะที่คณิตศาสตร์คลาสสิก (ต่อเนื่อง) ศึกษาคุณสมบัติของวัตถุ

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

แบบฝึกหัด
1. พิสูจน์ว่าการทำแผนที่ไอโซมอร์ฟิกนั้นเป็นไอโซโทนเสมอ และสิ่งที่ตรงกันข้ามไม่เป็นความจริง

2. เขียนกลุ่มของคุณเป็นภาษาชุด
3. เขียนเป็นภาษาชุดของวัตถุนั้นๆ

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

เซตจำกัดและเซตอนันต์
สิ่งที่ในชุดประกอบด้วยคือ วัตถุที่ประกอบเป็นเซตเรียกว่าองค์ประกอบ องค์ประกอบของชุดมีความแตกต่างและแตกต่างออกไป

ดังที่เห็นได้จากตัวอย่างที่ให้มา
พลังของชุด

ภาวะเชิงการนับของเซตจำกัดจะเท่ากับจำนวนสมาชิกของเซตนั้น ตัวอย่างเช่น ภาวะเชิงการนับของเอกภพ B(A) ของเซต A ของภาวะเชิงการนับ n
A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…อัน|

เซตจำกัด A มีภาวะเชิงการนับ k ถ้ามันเท่ากับส่วน 1.. k;:
เซตย่อย, เซตย่อยของตัวเอง

หลังจากที่แนวคิดของเซตถูกนำเสนอ งานก็จะเกิดขึ้นในการสร้างเซตใหม่จากเซตที่มีอยู่ นั่นคือ การกำหนดการดำเนินการของเซต
ชุดเอ็ม",

การเพิ่มและการลบรายการ
ถ้า A เป็นเซต และ x เป็นองค์ประกอบ แล้วก็เป็นองค์ประกอบ

ชุดมีขอบเขต กำหนดขอบเขต
ให้ฟังก์ชันตัวเลข f(x) ถูกกำหนดให้กับเซต X บางชุด

ขอบเขตบน (ขอบเขต) ของฟังก์ชัน f(x) คือตัวเลขดังกล่าว
ขีดจำกัดบน (ล่าง) ที่แน่นอน

เซตของขอบเขตบนทั้งหมด E เขียนแทนด้วย Es และเซตของขอบเขตล่างทั้งหมดเขียนด้วย Ei ในกรณีที่
ขอบเขตบน (ล่าง) ที่แน่นอนของเซต

หากองค์ประกอบ z อยู่ในจุดตัดของเซต E และเซตของขอบเขตบนทั้งหมด Es (ตามลำดับ r ที่ต่ำกว่า
คุณสมบัติพื้นฐานของขอบเขตบนและล่าง

ให้ X เป็นเซตที่เรียงลำดับบางส่วน
1. ถ้าอย่างนั้น

กำหนดจากมุมมองที่เป็นองค์ประกอบ
มุมมองโดยรวม ซึ่งแตกต่างจากมุมมองที่แสดงที่มา ไม่สามารถป้องกันได้ในเชิงตรรกะในแง่ที่ว่าจะนำไปสู่ความขัดแย้งประเภทรัสเซลล์และคันทอร์ (ดูด้านล่าง)

ภายในกรอบของคุณสมบัติ t
โครงสร้าง

เซต X ที่เรียงลำดับเพียงบางส่วนจะเรียกว่าโครงสร้างหากมีเซตที่มีสององค์ประกอบอยู่ด้วย
ชุดปิดและแบ่งพาร์ติชัน

ฉากกั้นของเซต A คือ ตระกูล Ai
ความสัมพันธ์แบบไบนารี

ลำดับความยาว n ซึ่งมีเงื่อนไขคือ a1, .... an จะแสดงโดย (a1, .... a
คุณสมบัติของความสัมพันธ์แบบไบนารี

ความสัมพันธ์แบบไบนารี่ R บนเซต Ho มีคุณสมบัติดังต่อไปนี้: (a) สะท้อนกลับถ้า xRx
ความสัมพันธ์แบบไตรภาค

สินค้าคาร์ทีเซียน XY
ความสัมพันธ์แบบ N-ary

โดยการเปรียบเทียบกับผลคูณคาร์ทีเซียนของชุด X,Y สองชุด เราสามารถสร้างผลคูณคาร์ทีเซียน X ได้
จอแสดงผล

การแมปคือการเชื่อมต่อบางอย่างระหว่างองค์ประกอบของเซต ตัวอย่างความสัมพันธ์ที่ง่ายที่สุดคือความสัมพันธ์ของการเป็นสมาชิก x
การโต้ตอบ

เซตย่อย S ของผลิตภัณฑ์คาร์ทีเซียนเรียกว่าการติดต่อกันแบบ n-ary ขององค์ประกอบของเซต Mi
อย่างเป็นทางการ

การทำงาน
คณิตศาสตร์แยกทุกสาขามีพื้นฐานอยู่บนแนวคิดเรื่องฟังก์ชัน

ให้เอ็กซ์ -
เป็นตัวแทนของฟังก์ชันในแง่ของความสัมพันธ์

ความสัมพันธ์แบบไบนารี่ f เรียกว่าฟังก์ชันถ้าจากและ
การฉีด การผ่าตัด การไบเจ็คชัน

เมื่อใช้คำว่า "การแมป" จะมีการสร้างความแตกต่างระหว่างการแมป XbY และการแมป X ไปยัง Y
ฟังก์ชันผกผัน

สำหรับคนตามอำเภอใจเรากำหนด
ชุดที่สั่งบางส่วน

การเรียงสับเปลี่ยนด้วยการทำซ้ำ
ให้เซต A มีองค์ประกอบที่เหมือนกัน (ซ้ำกัน) การเรียงสับเปลี่ยนด้วยการทำซ้ำองค์ประกอบ (n1, n2, … ,nk

ตำแหน่ง
สิ่งอันดับความยาว k (1≤k≤n) ประกอบด้วยองค์ประกอบที่แตกต่างกันของเซต n องค์ประกอบ A (สิ่งอันดับต่างกันใน

ตำแหน่งที่มีการทำซ้ำ
ให้เซต A มีองค์ประกอบที่เหมือนกัน (ซ้ำกัน) ตำแหน่งที่มีการซ้ำซ้อนขององค์ประกอบ n รายการของชื่อ k

การจัดวางอย่างเป็นระเบียบ
ให้เราวางวัตถุ n รายการลงในกล่อง m เพื่อให้แต่ละกล่องมีลำดับ และไม่ใช่ชุดของวัตถุที่วางอยู่ในนั้นเหมือนเมื่อก่อน สอง

การรวมกัน
จากชุดองค์ประกอบ m A เราสร้างชุดลำดับความยาว n ซึ่งองค์ประกอบต่างๆ จะถูกจัดเรียงด้วยธีมเดียวกัน

การรวมกันกับการทำซ้ำ
สูตรผลลัพธ์จะใช้ได้ก็ต่อเมื่อไม่มีองค์ประกอบที่เหมือนกันในชุด A ให้มีองค์ประกอบของ n ประเภทและจากนั้นก็มี tuple ของ

วิธีการสร้างฟังก์ชัน
วิธีการนี้ใช้ในการแจกแจงตัวเลขเชิงรวมกันและสร้างอัตลักษณ์เชิงรวมกัน

จุดเริ่มต้นคือตัวรวมลำดับ (ai)
ระบบพีชคณิต

ระบบพีชคณิต A คือกลุ่ม ‹M,O,R› องค์ประกอบแรกที่ M เป็นเซตที่ไม่ว่างเปล่า องค์ประกอบที่สอง O คือเซต
การปิดและพีชคณิตย่อย

เซตย่อยถูกปิดภายใต้การดำเนินการ φ ถ้า
พีชคณิตที่มีการดำเนินการแบบไบนารี่หนึ่งครั้ง

ให้ดำเนินการไบนารีหนึ่งรายการบนเซต M ให้เราพิจารณาพีชคณิตที่มันสร้างขึ้น แต่ก่อนอื่นเราจะพิจารณาคุณสมบัติบางอย่างของการดำเนินการไบนารี่
ไบนารี่<М, f2>กรุ๊ปออยด์

พีชคณิตของแบบฟอร์ม
เรียกว่ากรุ๊ปออยด์ ถ้า f2 เป็นการดำเนินการเหมือนกับการคูณ (<М,

จำนวนเต็มโมดูโล m
ให้วงแหวนของจำนวนเต็ม - ให้เราเตือนคุณ พีชคณิต

ความสอดคล้อง
ความสอดคล้องของพีชคณิต A =

(Σ – ลายเซ็นพีชคณิตประกอบด้วยสัญลักษณ์ฟังก์ชันเท่านั้น) เรียกว่าความสัมพันธ์ที่เท่าเทียมกัน
องค์ประกอบของทฤษฎีกราฟ , อะไร

โดยการเปรียบเทียบกับผลคูณคาร์ทีเซียนของชุด X,Y สองชุด เราสามารถสร้างผลคูณคาร์ทีเซียน X ได้
กราฟเป็นวัตถุทางคณิตศาสตร์

ทฤษฎีกราฟใช้ในด้านต่างๆ เช่น ฟิสิกส์ เคมี ทฤษฎีการสื่อสาร การออกแบบคอมพิวเตอร์ วิศวกรรมไฟฟ้า วิศวกรรมเครื่องกล สถาปัตยกรรม การวิจัยเกี่ยวกับ
กราฟ จุดยอด ขอบ

โดยกราฟที่ไม่มีทิศทาง (หรือเรียกสั้น ๆ ว่ากราฟ) เราหมายถึงคู่ที่กำหนด G =
คำอธิบายอีกประการหนึ่งที่ใช้บ่อยกว่าของกราฟกำกับ G ประกอบด้วยการระบุชุดของจุดยอด X และการติดต่อ Г<и, v>แล้วเราจะบอกว่าขอบ e เป็นเหตุการณ์ที่เกิดขึ้น

การแข่งขันแบบย้อนกลับ
เนื่องจากมันแสดงถึงชุดของจุดยอดดังกล่าว

กราฟมอร์ฟิซึม
สองกราฟ G1 = และ G2 = เป็นไอโซมอร์ฟิก (G

เส้นทางที่มุ่งเน้นเส้นทาง
เส้นทาง (หรือเส้นทางที่กำหนด) ของกราฟกำหนดทิศทางคือลำดับของส่วนโค้งซึ่ง

ส่วนโค้งที่อยู่ติดกัน จุดยอดที่อยู่ติดกัน ระดับจุดยอด
ส่วนโค้ง a = (xi, xj), xi ≠ xj, มีจุดยอดร่วม, n

การเชื่อมต่อ
จุดยอดสองจุดในกราฟจะถูกเรียกว่าเชื่อมต่อกันหากมีเส้นทางง่ายๆ เชื่อมต่อกัน กราฟจะเรียกว่าเชื่อมต่อกันหากจุดยอดทั้งหมดเชื่อมต่อกัน

ทฤษฎีบท.
กราฟส่วนโค้งถ่วงน้ำหนัก

กราฟ G = (N, A) เรียกว่าถ่วงน้ำหนักหากมีการกำหนดฟังก์ชัน l: A → R บนเซตของส่วนโค้ง A ซึ่ง
เมทริกซ์การเชื่อมต่อที่แข็งแกร่ง

เมทริกซ์การเชื่อมต่อที่แข็งแกร่ง: ใส่ 1 ตามแนวทแยง กรอกบรรทัด X1 - หากจุดยอดสามารถเข้าถึงได้จาก X1 และ X1 d
ต้นไม้

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

หลักฐาน พิจารณาต้นไม้ G(V, E) ต้นไม้จึงเป็นกราฟที่เชื่อมโยงกัน
ทฤษฎีบท

จุดศูนย์กลางของต้นไม้อิสระประกอบด้วยจุดยอดหนึ่งหรือสองจุดที่อยู่ติดกัน: Z(G) = 0&k(G) = 1 → C(G) = K1
กำกับสั่งและต้นไม้ไบนารี

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

1. แต่ละส่วนโค้งเข้าสู่บางโหนด จากข้อ 2 ของคำจำกัดความ 9.2.1 เรามี:
สั่งต้นไม้

เซต T1,..., Tk ในคำจำกัดความที่เทียบเท่าของ orderev คือแผนผังย่อย ถ้าลำดับสัมพัทธ์ของทรีย่อย T1,...,
ต้นไม้ไบนารี

ต้นไม้ไบนารี่ (หรือไบนารี่) คือชุดโหนดที่มีขอบเขตจำกัดซึ่งว่างเปล่าหรือประกอบด้วยรากและต้นไม้ไบนารีสองต้นที่แยกจากกัน - ซ้ายและขวา
ต้นไม้ไบนารีไม่ได้อยู่ในจาวา

เป็นตัวแทนต้นไม้ฟรี
ในการแสดงต้นไม้ คุณสามารถใช้เทคนิคเดียวกับการแสดงกราฟทั่วไป - เมทริกซ์ที่อยู่ติดกันและอุบัติการณ์ รายการที่อยู่ติดกัน และอื่นๆ แต่ใช้คุณสมบัติพิเศษของ

จบเพื่อ
ทรีอิสระใดๆ สามารถกำหนดทิศทางได้โดยการกำหนดโหนดใดโหนดหนึ่งให้เป็นรูท คำสั่งซื้อใด ๆ สามารถสั่งซื้อได้ตามอำเภอใจ สำหรับผู้สืบทอดของโหนดเดียว (พี่น้อง) ของลำดับที่ได้รับคำสั่ง จะมีการกำหนดความสัมพันธ์

ฟังก์ชันลอจิกพื้นฐาน
ให้เราแทนด้วย E2 = (0, 1) ชุดที่ประกอบด้วยตัวเลขสองตัว ตัวเลข 0 และ 1 เป็นตัวเลขพื้นฐานในแผ่นรองแยก

ฟังก์ชันบูลีน
ฟังก์ชันบูลีนของอาร์กิวเมนต์ n x1, x2, … ,xn คือฟังก์ชัน f จากกำลัง n ของเซต

พีชคณิตบูลีนสององค์ประกอบ
ลองพิจารณาเซต Во = (0,1) และกำหนดการดำเนินการกับมันตามตารางแหล่งที่มา

ตารางฟังก์ชันบูลีน
ฟังก์ชันบูลีนของตัวแปร n ตัวสามารถระบุได้ด้วยตารางที่ประกอบด้วย 2 คอลัมน์และ 2n แถว คอลัมน์แรกแสดงรายการชุดทั้งหมดจาก B

F5 – ทำซ้ำใน y
f6 – รวมโมดูโล 2 f7

ลำดับการดำเนินงาน
หากไม่มีวงเล็บในนิพจน์ที่ซับซ้อน การดำเนินการจะต้องดำเนินการตามลำดับต่อไปนี้: การร่วม การแตกแยก การนัย ความเท่าเทียมกัน การปฏิเสธ
แบบแผนเกี่ยวกับการจัดเรียงทฤษฎีบทแรกของแชนนอน

เพื่อแก้ปัญหาในการค้นหา SDNF และ SCNF ที่เทียบเท่ากับสูตรดั้งเดิม φ ก่อนอื่นเราจะพิจารณาการขยายของฟังก์ชันบูลีน f(x1, x2
ทฤษฎีบทที่สองของแชนนอน

โดยอาศัยหลักการของความเป็นคู่ ทฤษฎีบท 6.4.3 (ทฤษฎีบทที่สองของแชนนอน) ถือเป็นพีชคณิตแบบบูลีน ฟังก์ชันบูลีนใดๆ f(x1, x2,...
ความสมบูรณ์ของฟังก์ชั่น

ทฤษฎีบท (เกี่ยวกับความสมบูรณ์ของฟังก์ชัน) สำหรับฟังก์ชันบูลีน f จะมีสูตร φ แทนฟังก์ชัน f
อัลกอริทึมสำหรับการค้นหา sdnf

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

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

รูปแบบมาตรฐานของฟังก์ชันลอจิคัล (สูตร) ​​คือนิพจน์ที่มีรูปแบบมาตรฐานของสูตรบูลีน โดยที่ฟังก์ชันดังกล่าวแสดงถึงฟังก์ชันลอจิคัลโดยเฉพาะ
ในพีชคณิต

ระบบฟังก์ชันบูลีน
ให้ฟังก์ชันบูลีน f(g1, g2, …, gm) และ g1(x1, x2, …, xn), g2(x1

พื้นฐาน Zhegalkin
เรามาลองดูระบบกัน เสร็จสมบูรณ์แล้ว เนื่องจากฟังก์ชันใดๆ จากพื้นฐานมาตรฐานจะแสดงเป็นเทอม

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

พีชคณิตเจกัลคิน
ผลรวมโมดูโล 2 การเชื่อมและค่าคงที่ 0 และ 1 ก่อให้เกิดระบบที่สมบูรณ์ตามหน้าที่ กล่าวคือ สร้างพีชคณิต - พีชคณิต Zhegalkin

ก=
ตรรกะเชิงประพจน์

ตรรกะทางคณิตศาสตร์ศึกษาแนวคิดพื้นฐานของไวยากรณ์ (รูปแบบ) และความหมาย (เนื้อหา) ของภาษาธรรมชาติ ลองพิจารณาการวิจัยหลักสามประการในตรรกะทางคณิตศาสตร์ - ตรรกะ
ความหมายของภาคแสดง

ให้ X1, X2, ..., Xn เป็นตัวแปรตามใจชอบ เราจะเรียกตัวแปรเหล่านี้ว่าตัวแปรเรื่อง ให้ตัวแปรกำหนดคุณ
การประยุกต์ภาคแสดงในพีชคณิต

ลองพิจารณาภาคแสดงที่มีตัวแปรเพียงตัวเดียวว่าง ซึ่งเราแสดงด้วย x และหารือเกี่ยวกับการใช้ภาคแสดงในพีชคณิต
ตัวอย่างทั่วไป

พีชคณิตภาคแสดงบูลีน
เนื่องจากการดำเนินการเชิงตรรกะสามารถนำไปใช้กับเพรดิเคตได้ กฎพื้นฐานของพีชคณิตแบบบูลจึงใช้ได้สำหรับการดำเนินการเหล่านี้

ทฤษฎีบท. (คุณสมบัติของการดำเนินการเชิงตรรกะสำหรับเพรดิเคต)
มน

F↔G=(F→G)(G→F), F→G=ไม่ใช่ FG
2. ใช้กฎหมายไม่ใช่ F=F กฎของมอร์แกน: ไม่ใช่ (F

ภาคแสดงแคลคูลัส
แคลคูลัสภาคแสดงเรียกอีกอย่างว่าทฤษฎีอันดับหนึ่ง

ในแคลคูลัสภาคแสดง เช่นเดียวกับในแคลคูลัสเชิงประพจน์ จุดที่สำคัญที่สุดอันดับแรกคือปัญหาความสามารถในการแก้ไข
การติดตามและความเท่าเทียมกัน