อ่าน 5 นาที
ตรรกะเชิงเวลาแบบประพจน์ที่กำหนดเวลาไว้
ข้อผิดพลาด CS1: ละเว้นเป็นระยะๆ/การตรวจสอบโมเดล/ตรรกะชั่วคราว
ในด้านการตรวจสอบแบบจำลองซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ตรรกะเชิงเวลาแบบประพจน์ที่มีเวลา ( TPTL ) เป็นส่วนขยายของตรรกะเชิงเวลาเชิงเส้นแบบ ประพจน์ (LTL)...
ตรรกะเชิงเวลาแบบประพจน์ที่กำหนดเวลาไว้
ในด้านการตรวจสอบแบบจำลองซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ตรรกะเชิงเวลาแบบประพจน์ที่มีเวลา ( TPTL ) เป็นส่วนขยายของตรรกะเชิงเวลาเชิงเส้นแบบ ประพจน์ (LTL) โดยมีการนำตัวแปรมาใช้ในการวัดช่วงเวลาระหว่างสองเหตุการณ์ ตัวอย่างเช่น ในขณะที่ LTL อนุญาตให้ระบุว่าแต่ละเหตุการณ์pจะตามมาด้วยเหตุการณ์q ในที่สุด TPTL ยังอนุญาตให้กำหนดขีดจำกัดเวลาสำหรับการเกิดขึ้นของ q ได้อีกด้วย
ไวยากรณ์
ส่วนประกอบในอนาคตของ TPTLถูกกำหนดในลักษณะเดียวกับตรรกะเชิงเวลาเชิงเส้นซึ่งนอกจากนี้ ยัง สามารถแนะนำตัวแปร นาฬิกา และเปรียบเทียบกับค่าคงที่ได้ ในทางทฤษฎีแล้ว MTLสร้างขึ้นจาก ชุดของนาฬิกา :
- เซตจำกัดของ ตัวแปร เชิงประพจน์AP
- ตัวดำเนินการตรรกะ ¬ และ ∨ และ
- ตัวดำเนินการโมดอลเชิงเวลาU ,
- การเปรียบเทียบนาฬิกาโดยใช้ตัวเลขและตัวดำเนินการเปรียบเทียบ เช่น <, ≤, =, ≥ หรือ >
- ตัวดำเนินการหาปริมาณแบบแช่แข็งสำหรับสูตร TPTL ที่มีชุดนาฬิกา
นอกจากนี้ สำหรับช่วงเวลาหนึ่งๆถือว่าเป็นตัวย่อของ; และในทำนองเดียวกันสำหรับช่วงเวลาประเภทอื่นๆ ทุกประเภท
ตรรกะTPTL+Past [ 1 ]ถูกสร้างขึ้นเป็นเศษส่วนในอนาคตของTLSและยังประกอบด้วย
- ตัวดำเนินการโมดอลเชิงเวลาS
ตัวดำเนินการถัดไปNไม่ถือว่าเป็นส่วนหนึ่งของ ไวยากรณ์ MTLแต่จะถูกกำหนดจากตัวดำเนินการอื่นๆ แทน
สูตรปิดคือสูตรบนเซตนาฬิกา ที่ว่างเปล่า [ 2 ]
นางแบบ
ให้แทนเซตของเวลาโดยสัญชาตญาณ ให้ เป็นฟังก์ชันที่เชื่อมโยงแต่ละช่วงเวลากับเซตของข้อความจากAPแบบจำลองของสูตร TPTL คือฟังก์ชันดังกล่าวโดยปกติจะเป็นคำหรือสัญญาณ ที่มีเวลา ในกรณีเหล่านั้นจะเป็นเซตย่อยแบบไม่ต่อเนื่องหรือช่วงที่มีค่า 0 อยู่
ความหมาย
ให้และเป็นไปตามที่กล่าวมาข้างต้น ให้เป็นเซตของนาฬิกาให้( การประเมินค่านาฬิกาเหนือ)
ต่อไปนี้เราจะอธิบายว่าสูตร TPTL เป็นจริง ณ เวลาใดเวลาหนึ่งสำหรับการประเมินค่า หมายความว่าอย่างไร ซึ่งเราจะ ใช้สัญลักษณ์ แทนด้วยให้และเป็นสองสูตรบนเซตของนาฬิกาเป็นสูตรบนเซตของนาฬิกา, , , เป็นตัวเลข และเป็นตัวดำเนินการเปรียบเทียบ เช่น <, ≤, =, ≥ หรือ >: เราจะพิจารณาสูตรที่มีตัวดำเนินการหลักอยู่ใน LTL ก่อน:
- เป็นจริงถ้า,
- ถือไว้หาก
- เป็นจริงหากเงื่อนไขใดเงื่อนไขหนึ่งหรือทั้งสอง เงื่อนไขเป็นจริง
- เป็นจริงก็ต่อเมื่อมีอยู่ซึ่งและและสำหรับแต่ละโดยที่, ,
- เป็นจริงก็ต่อเมื่อมีอยู่ซึ่งและและสำหรับแต่ละโดยที่ , ,
- เป็นจริงถ้า,
- คงอยู่ถ้าคงอยู่
ตรรกะเชิงเวลาเมตริก
ตรรกะเชิงเวลาแบบเมตริก เป็นส่วนขยายอีกอย่างหนึ่งของ LTL ที่ช่วยให้สามารถวัดเวลา ได้แทนที่จะบวกตัวแปร มันจะบวกตัวดำเนินการจำนวนอนันต์สำหรับช่วงของจำนวนที่ไม่เป็นลบ ความหมายของสูตรณ เวลาใดเวลาหนึ่งนั้นโดยพื้นฐานแล้วเหมือนกับความหมายของสูตรโดยมีข้อจำกัดว่าเวลาที่ สูตรนี้ต้องเป็นจริงนั้นเกิด ขึ้น ในช่วง
TPTL มีความสามารถในการแสดงออกอย่างน้อยเท่ากับ MTL อันที่จริง สูตร MTL เทียบเท่ากับสูตร TPTL โดยที่เป็นตัวแปรใหม่[ 2 ]
ดังนั้น ตัวดำเนินการอื่นๆ ที่แนะนำในหน้าMTLเช่นและก็สามารถกำหนดให้เป็นสูตร TPTL ได้เช่นกัน
TPTL มีความสามารถในการแสดงออกมากกว่า MTL อย่างชัดเจน[ 1 ] : 2 ทั้งในส่วนของคำที่กำหนดเวลาและสัญญาณ ในส่วนของคำที่กำหนดเวลา ไม่มีสูตร MTL ใดเทียบเท่ากับในส่วนของสัญญาณ ไม่มีสูตร MTL ใดเทียบเท่ากับซึ่งระบุว่าข้อเสนออะตอมสุดท้ายก่อนจุดเวลา 1 คือ
การเปรียบเทียบกับ LTL
คำอนันต์มาตรฐาน (ไม่จำกัดเวลา) คือฟังก์ชันจากไปยังเราสามารถพิจารณาคำดังกล่าวโดยใช้เซตของเวลาและฟังก์ชันในกรณีนี้ สำหรับสูตร LTL ใดๆ ก็ต่อเมื่อโดยที่ถือเป็นสูตร TPTL ที่มีตัวดำเนินการแบบไม่เข้มงวด และเป็นฟังก์ชันเดียวที่กำหนดบนเซตว่าง
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ตรรกะเชิงเวลาแบบประพจน์ที่กำหนดเวลาไว้
ในด้านการตรวจสอบแบบจำลองซึ่งเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ตรรกะเชิงเวลาแบบประพจน์ที่มีเวลา ( TPTL ) เป็นส่วนขยายของตรรกะเชิงเวลาเชิงเส้นแบบ ประพจน์ (LTL)...
ไวยากรณ์
ส่วนประกอบ ในอนาคตของ TPTL ถูกกำหนดในลักษณะเดียวกับ ตรรกะเชิงเวลาเชิงเส้น ซึ่งนอกจากนี้ ยัง สามารถแนะนำตัวแปร นาฬิกา และเปรียบเทียบกับค่าคงที่ได้ ในทางทฤษฎีแล้ว MTL สร้างขึ้นจาก ชุดของนาฬิกา : X {\displaystyle X}
นางแบบ
ให้แทนเซตของเวลาโดยสัญชาตญาณ ให้ เป็นฟังก์ชันที่เชื่อมโยงแต่ละช่วงเวลากับเซตของข้อความจาก AP แบบจำลองของสูตร TPTL คือฟังก์ชันดังกล่าวโดยปกติจะเป็น คำ หรือ สัญญาณ ที่มีเวลา ในกรณีเหล่านั้นจะเป็นเซตย่อยแบบไม่ต่อเนื่องหรือช่วงที่มีค่า 0 อยู่ ที ⊆ อาร์ +...
ความหมาย
ให้และเป็นไปตามที่กล่าวมาข้างต้น ให้เป็นเซตของ นาฬิกา ให้( การประเมินค่านาฬิกา เหนือ) ที {\displaystyle T} γ {\displaystyle \gamma } X {\displaystyle X} ν : X → อาร์ ≥ 0 {\displaystyle \nu :X\to \mathbb {R} _{\geq 0}} X {\displaystyle X}