การสั่งซื้อแบบครอบคลุม

Q: ข้อมูลสำคัญเกี่ยวกับ การสั่งซื้อแบบครอบคลุม

ในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีโดยเฉพาะอย่างยิ่งใน การ พิสูจน์ทฤษฎีบทอัตโนมัติและการเขียนเทอมใหม่การบรรจุ หรือการครอบคลุมลำดับก่อน (≤) บนเซตของเทอมถูกกำหนดโดย

ในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีโดยเฉพาะอย่างยิ่งใน การ ^{พิสูจน์}ทฤษฎีบทอัตโนมัติและการเขียนเทอมใหม่การบรรจุ [ ¹^]หรือการครอบคลุมลำดับก่อน (≤) บนเซตของเทอมถูกกำหนดโดย^[²^]

s ≤ tถ้าพจน์ย่อยของtเป็นตัวอย่างการแทนที่ของs

ตัวอย่างเช่น มันถูกใช้ใน อั ลก อริทึมการเติมเต็มของ Knuth–Bendix

คุณสมบัติ

การครอบคลุมเป็นการเรียงลำดับล่วงหน้า กล่าวคือสะท้อนและถ่ายทอดได้แต่ไม่ใช่สมมาตรผกผัน [ ^{หมายเหตุ 1 ]}และไม่ใช่ทั้งหมด^{[หมายเหตุ 2 ]}
ความสัมพันธ์สมมูลที่สอดคล้องกันซึ่งกำหนดโดยs ~ tถ้าs ≤ t ≤ s นั้นคือความเท่าเทียมกันแบบโมดูลัสการเปลี่ยนชื่อ
s ≤ tเมื่อใดก็ตามที่s เป็นพจน์ย่อยของt
s ≤ tเมื่อใดก็ตามที่t เป็นตัวอย่างทดแทนของs
การรวมกันของลำดับการเขียนใหม่ ที่มีพื้นฐานดี R ^{[หมายเหตุ 3 ]}กับ (<) มีพื้นฐานดีโดยที่ (<) หมายถึงเคอร์เนลที่ไม่สะท้อนของ (≤) ^{[ 3 ]}โดยเฉพาะอย่างยิ่ง (<) เองก็มีพื้นฐานดี

หมายเหตุ

เนื่องจากทั้ง f ( x ) ≤ f ( y ) และ f ( y ) ≤ f ( x ) สำหรับสัญลักษณ์ตัวแปรx , yและสัญลักษณ์ฟังก์ชันf
เนื่องจากทั้ง a และ b ไม่เท่ากัน สำหรับ สัญลักษณ์ค่าคงที่ที่แตกต่างกันaและ b
^เช่น ความสัมพันธ์ทวิภาคที่ไม่สะท้อนกลับ ถ่ายทอดได้ และมีรากฐานที่ดี Rซึ่ง sRtบ่งชี้ว่า u [ s σ ]_p R u [ t σ]_pสำหรับทุกเทอม s , t , uทุกเส้นทาง pของ uและทุกการแทนที่ σ

[3] เนื่องจากทั้ง f ( x ) ≤ f ( y ) และ f ( y ) ≤ f ( x ) สำหรับสัญลักษณ์ตัวแปรx , yและสัญลักษณ์ฟังก์ชันf

[4] เนื่องจากทั้ง a และ b ไม่เท่ากัน สำหรับ สัญลักษณ์ค่าคงที่ที่แตกต่างกันaและ b

[5] เช่น ความสัมพันธ์ทวิภาคที่ไม่สะท้อนกลับ ถ่ายทอดได้ และมีรากฐานที่ดี Rซึ่ง sRtบ่งชี้ว่า u [ s σ ]_p R u [ t σ]_pสำหรับทุกเทอม s , t , uทุกเส้นทาง pของ uและทุกการแทนที่ σ

พิสูจน์

[

หมายเหตุ 1 ]

[หมายเหตุ 2 ]

[หมายเหตุ 3 ]

[ 3 ]

การสั่งซื้อแบบครอบคลุม

คุณสมบัติ

หมายเหตุ

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