ตรรกะเชิงเวลาเมตริก
ตรรกศาสตร์เชิงเวลาแบบเมตริก ( MTL ) เป็นกรณีพิเศษของตรรกศาสตร์เชิงเวลามันเป็นการขยายของตรรกศาสตร์เชิงเวลาโดยที่ตัวดำเนินการเชิงเวลาถูกแทนที่ด้วยตัวดำเนินการที่จำกัดเวลา เช่น ตัวดำเนินการ until , next , sinceและpreviousมันเป็นตรรกศาสตร์เชิงเส้นที่สมมติทั้งการสลับลำดับและการใช้แนวคิดนาฬิกาเสมือน โดยนิยามอยู่บนความหมายเชิงเวลาแบบจำนวนเต็มที่อ่อนแอและอิงตามจุด
MTL ได้รับการอธิบายว่าเป็นรูปแบบการกำหนดคุณสมบัติที่โดดเด่นสำหรับระบบเรียลไทม์[ 1 ] MTL เต็มรูปแบบเหนือคำที่มีเวลาไม่จำกัดนั้นไม่สามารถตัดสินได้[ 2 ]
ไวยากรณ์
ตรรกะเชิงเวลาเมตริกแบบสมบูรณ์ (Full Metric Temporal Logic: MTL) ถูกกำหนดในลักษณะเดียวกับตรรกะเชิงเวลาเชิงเส้น (Linear Temporal Logic: LILOG ) โดยที่เซตของจำนวนจริงที่ไม่เป็นลบจะถูกเพิ่มเข้าไปในตัวดำเนินการเชิงเวลา แบบโมดอล UและSในทางทฤษฎีแล้ว MTL สร้างขึ้นจาก:
- เซตจำกัดของตัวแปรเชิงประพจน์AP
- ตัวดำเนินการตรรกะ ¬ และ ∨ และ
- ตัวดำเนินการเชิงโมดอลเชิงเวลาU (อ่านว่า " φ until in I ψ .") โดยที่Iคือช่วงของจำนวนที่ไม่เป็นลบ
- ตัวดำเนินการโมดอลเชิงเวลาS (ออกเสียงว่า " φ since in I ψ .") โดยที่Iเป็นไปตามที่กล่าวมาข้างต้น
เมื่อละเว้นตัวห้อย จะถือว่าเท่ากับโดยปริยาย.
โปรดทราบว่าตัวดำเนินการถัดไปNไม่ถือว่าเป็นส่วนหนึ่งของไวยากรณ์ MTL แต่จะถูกกำหนดจากตัวดำเนินการอื่นๆ แทน
อดีตและอนาคต
ส่วนย่อยของตรรกะเชิงเวลาแบบเมตริกในอดีตซึ่งใช้สัญลักษณ์แทนด้วยpast-MTLนั้น ถูกกำหนดให้เป็นการจำกัดตรรกะเชิงเวลาแบบเมตริกฉบับเต็ม โดยไม่รวม ตัวดำเนินการ until ในทำนองเดียวกันส่วนย่อยของตรรกะเชิงเวลาแบบเมตริกในอนาคตซึ่งใช้สัญลักษณ์แทนด้วยfuture-MTLนั้น ถูกกำหนดให้เป็นการจำกัดตรรกะเชิงเวลาแบบเมตริกฉบับเต็ม โดยไม่รวมตัวดำเนินการsince
ขึ้นอยู่กับผู้เขียนMTL อาจถูกกำหนดให้เป็นส่วนของ MTL ในอนาคต ซึ่งในกรณีนี้ MTL เต็มรูปแบบเรียกว่า MTL+Past [ 1 ] [ 3 ]หรือMTLอาจถูกกำหนดให้เป็น MTL เต็มรูปแบบ
เพื่อหลีกเลี่ยงความกำกวม บทความนี้จึงใช้ชื่อ full-MTL, past-MTL และ future-MTL เมื่อเงื่อนไขของตรรกะทั้งสามเป็นจริง จะใช้คำว่า MTL เพียงอย่างเดียว
แบบอย่าง
อนุญาตโดยสัญชาตญาณแล้ว แสดงถึงชุดของจุดเวลาต่างๆ ให้ฟังก์ชันที่เชื่อมโยงตัวอักษรกับแต่ละช่วงเวลาแบบจำลองของสูตร MTL คือฟังก์ชันดังกล่าว. โดยปกติ,เป็นได้ทั้งคำที่กำหนดเวลาไว้หรือสัญญาณในกรณีเหล่านั้นเป็นได้ทั้งเซตย่อยที่ไม่ต่อเนื่อง หรือช่วงที่ประกอบด้วย 0
ความหมาย
อนุญาตและตามที่กล่าวมาข้างต้น และปล่อยให้เวลาที่กำหนดไว้ เราจะมาอธิบายความหมายของสูตร MTL กันต่อไปถือครอง ณ เวลาซึ่งแสดงด้วยสัญลักษณ์.
อนุญาตและเราจะพิจารณาสูตรนี้เป็นอันดับแรกเรากล่าวว่าก็ต่อเมื่อมีเวลาอยู่บ้างเท่านั้นโดยที่:
- และ
- สำหรับแต่ละคนกับ,.
ต่อไปนี้เราจะพิจารณาสูตรดังกล่าว(ออกเสียงว่า "เนื่องจาก ในเรากล่าวว่าก็ต่อเมื่อมีเวลาอยู่บ้างเท่านั้นโดยที่:
- และ
- สำหรับแต่ละคนกับ,.
คำจำกัดความของ สำหรับค่าของคำว่า "ไม่ได้พิจารณาข้างต้น" มีความหมายคล้ายกับคำจำกัดความในกรณี ของ LTL
ตัวดำเนินการที่กำหนดจากตัวดำเนินการ MTL พื้นฐาน
สูตรบางสูตรถูกใช้บ่อยมากจนต้องมีการเพิ่มตัวดำเนินการใหม่เข้าไป ตัวดำเนินการเหล่านี้มักไม่ถือว่าเป็นส่วนหนึ่งของคำจำกัดความของ MTL แต่เป็นเพียงรูปแบบการเขียนที่บ่งบอกถึงสูตร MTL ที่ซับซ้อนกว่า เราจะพิจารณาตัวดำเนินการที่มีอยู่ใน LTL ก่อน ในส่วนนี้ เราจะกำหนด สูตร MTL และ.
ผู้ประกอบการที่คล้ายกับผู้ประกอบการขนส่งสินค้าแบบไม่เต็มคันรถ (LTL)
ปล่อยและกลับไปที่
เราใช้สัญลักษณ์ แทนด้วย (ออกเสียงว่า "เผยแพร่ใน,") สูตรสูตรนี้ใช้ได้ ณ เวลา .หากเป็นกรณีใดกรณีหนึ่งต่อไปนี้:
- มีเวลาอยู่บ้างโดยที่ถือครอง และถือไว้ในช่วงเวลา.
- ในแต่ละครั้ง,ถือครอง
ชื่อ "release" มาจากกรณี LTL ซึ่งสูตรนี้หมายความง่ายๆ ว่าควรยึดถือเสมอ เว้นแต่ปล่อยออกมา
คำที่เทียบเท่ากับคำว่า "ปล่อย" ในอดีตนั้นแสดงด้วย (ออกเสียงว่า "กลับไปที่,") และเท่ากับสูตร.
ในที่สุดและในที่สุด
เราใช้สัญลักษณ์ แทนด้วยหรือ(ออกเสียงว่า "ในที่สุด" ใน),หรือ "ในที่สุด",") สูตรโดยสัญชาตญาณแล้ว สูตรนี้ใช้ได้ผล ณ เวลา ถ้ามีเวลาบ้างโดยที่ถือครอง
เราใช้สัญลักษณ์ แทนด้วยหรือ(ออกเสียงว่า "โกลบอลลี่ อิน),",) สูตรโดยสัญชาตญาณแล้ว สูตรนี้ใช้ได้ผล ณ เวลาถ้าเป็นตลอดกาล,ถือครอง
เราใช้สัญลักษณ์ แทนด้วย และสูตรที่คล้ายกับและ, ที่ไหนถูกแทนที่ด้วยทั้งสองสูตรมีความหมายเหมือนกันโดยพื้นฐาน แต่จะแตกต่างกันเมื่อเราพิจารณาจากอดีตแทนที่จะเป็นอนาคต
ถัดไปและก่อนหน้า
กรณีนี้แตกต่างจากกรณีที่ผ่านมาเล็กน้อย เนื่องจากความหมายโดยนัยของสูตร "ถัดไป" และ "ก่อนหน้า" แตกต่างกันไปตามประเภทของฟังก์ชันที่พิจารณา.
เราใช้สัญลักษณ์ แทนด้วยหรือ (ออกเสียงว่า "เน็กซ์ อิน),") สูตรในทำนองเดียวกัน เราใช้สัญลักษณ์ แทน[ 4 ] (ออกเสียงว่า "ก่อนหน้านี้ใน,) สูตรการอธิบายเกี่ยวกับตัวดำเนินการ Next ต่อไปนี้ยังใช้ได้กับตัวดำเนินการ Previously ด้วยการสลับลำดับอดีตและอนาคต
เมื่อประเมินสูตรนี้กับคำที่กำหนดเวลาไว้สูตรนี้หมายความว่าทั้งสองอย่าง:
- ในครั้งต่อไปในขอบเขตของคำจำกัดความสูตรจะคงอยู่
- นอกจากนี้ ระยะห่างระหว่างเวลาครั้งถัดไปกับเวลาปัจจุบันอยู่ในช่วงเวลาดังกล่าว.
- โดยเฉพาะอย่างยิ่ง ครั้งถัดไปนี้ยังคงใช้ได้ ดังนั้น เวลาปัจจุบันจึงไม่ใช่จุดจบของโลก
เมื่อประเมินสูตรนี้กับสัญญาณแนวคิดเรื่อง "ครั้งหน้า" นั้นไม่สมเหตุสมผล เพราะ "ครั้งหน้า" หมายถึง "ทันทีหลังจากนั้น" พูดให้ชัดเจนยิ่งขึ้นก็คือ...วิธี:
- ประกอบด้วยช่วงเวลาในรูปแบบและ
- สำหรับแต่ละคน,.
ผู้ประกอบการรายอื่น
ต่อไปนี้เราจะพิจารณาผู้ประกอบการที่ไม่เหมือนกับผู้ประกอบการ LTL มาตรฐานทั่วไป
ล้มแล้วลุกขึ้น
เราใช้สัญลักษณ์ แทนด้วย(ออกเสียงว่า "ไรส์")") สูตรที่ใช้ได้เมื่อกลายเป็นความจริง กล่าวให้แม่นยำยิ่งขึ้นคือ อย่างใดอย่างหนึ่งไม่เป็นจริงในอดีตอันใกล้ แต่ไม่เป็นจริงในขณะนี้ หรือไม่เป็นจริงแต่จะเป็นจริงในอนาคตอันใกล้ อย่างเป็นทางการถูกกำหนดให้เป็น[ 5 ]
สูตรนี้ใช้ได้ผลเสมอเมื่อพูดถึงคำพูดที่ใช้เวลาพิจารณา แน่นอนและเป็นจริงเสมอ ดังนั้นสูตรจึงเทียบเท่ากับดังนั้นจึงเป็นความจริง
เนื่องจากสมมาตร เราจึงใช้สัญลักษณ์ แทนด้วย(ออกเสียงว่า "ฟอลล์")) สูตรที่ใช้ได้เมื่อกลายเป็นเท็จ ดังนั้นจึงนิยามได้ดังนี้.
ประวัติศาสตร์และคำพยากรณ์
ต่อไปนี้เราจะแนะนำ ตัวดำเนิน การทำนายซึ่งใช้สัญลักษณ์ แทนด้วยเราใช้สัญลักษณ์ แทน[ 6 ]สูตรสูตรนี้ยืนยันว่ามีช่วงเวลาแรกในอนาคตอยู่ช่วงหนึ่งซึ่งเป็นไปตามเงื่อนไขที่ว่าและเวลาที่จะรอคอยช่วงเวลาแรกนี้เป็นของ.
ต่อไปนี้เราจะพิจารณาสูตรนี้กับคำที่มีเวลาและสัญญาณ โดยเราจะพิจารณาคำที่มีเวลาก่อน สมมติว่าที่ไหนและแสดงถึงขอบเขตเปิดหรือขอบเขตปิด ให้คำที่กำหนดเวลาและในขอบเขตของคำจำกัดความ เมื่อเวลาผ่านไป สูตรดังกล่าวเป็นจริงก็ต่อเมื่อสูตรนี้ก็ใช้ได้เช่นกัน กล่าวคือ สูตรนี้เพียงแค่ยืนยันว่า ในอนาคต จนกว่าจะถึงช่วงเวลาดังกล่าวตรงตามเกณฑ์ที่กำหนดไม่ควรยึดถือ นอกจากนี้ควรคงไว้ในช่วงเวลาใดเวลาหนึ่งอันที่จริง หากมีเวลาเหลือเฟือโดยที่จำไว้ว่า เวลาที่มีอยู่นั้นมีจำนวนจำกัดเท่านั้นกับและดังนั้น จึงจำเป็นต้องมีขนาดที่เล็กกว่านั้นอยู่ด้วย.
ต่อไปนี้เรามาพิจารณาสัญญาณกัน ความเท่าเทียมกันที่กล่าวถึงข้างต้นใช้ไม่ได้อีกต่อไปกับสัญญาณ เนื่องจากข้อเท็จจริงที่ว่า เมื่อใช้ตัวแปรที่แนะนำข้างต้น อาจมีค่าที่ถูกต้องเป็นจำนวนอนันต์สำหรับเนื่องจากโดเมนการนิยามของสัญญาณมีความต่อเนื่อง ดังนั้นสูตรจึงเป็นดังนี้นอกจากนี้ยังช่วยให้มั่นใจได้ว่าช่วงเวลาแรกที่ช่องเก็บของด้านซ้ายปิดสนิทแล้ว
ด้วยสมมาตรเชิงเวลา เราจึงกำหนด ตัวดำเนิน การประวัติศาสตร์ซึ่งแสดงด้วยสัญลักษณ์เรากำหนดเช่นสูตรนี้ยืนยันว่ามีช่วงเวลาสุดท้ายในอดีตอยู่ช่วงหนึ่งซึ่งเป็นไปตามเงื่อนไขที่ว่าจับไว้ และเวลาตั้งแต่วินาทีแรกนั้นเป็นของ.
ตัวดำเนินการที่ไม่เข้มงวด
ความหมายของตัวดำเนินการuntilและsinceที่นำเสนอมานั้นไม่ได้คำนึงถึงเวลาปัจจุบัน กล่าวคือ เพื่อให้ถือครองไว้ในบางช่วงเวลา, ไม่ใช่ทั้งสองอย่างก็ไม่เช่นกันต้องถือไว้ ณ เวลานั้นนี่ไม่ใช่สิ่งที่ต้องการเสมอไป ตัวอย่างเช่น ในประโยค "จะไม่มีข้อผิดพลาดจนกว่าระบบจะปิด" ความจริงแล้วอาจต้องการให้ไม่มีข้อผิดพลาดในขณะนี้ ดังนั้น เราจึงแนะนำ ตัวดำเนินการ until อีกตัวหนึ่ง เรียกว่าuntil แบบไม่เข้มงวดซึ่งใช้สัญลักษณ์ แทนด้วยซึ่งคำนึงถึงเวลาปัจจุบันด้วย
เราใช้สัญลักษณ์ แทนด้วยและทั้ง:
- สูตรต่างๆและถ้า, และ
- สูตรต่างๆและมิฉะนั้น.
สำหรับผู้ให้บริการรายใดก็ตามตามที่ได้กล่าวไว้ข้างต้น เราจะใช้สัญลักษณ์ แทนสูตรที่ใช้เงื่อนไขแบบไม่เข้มงวดจนกระทั่ง s และsince ตัวอย่างเช่นเป็นคำย่อของ.
ตัวดำเนินการแบบเข้มงวดไม่สามารถกำหนดได้โดยใช้ตัวดำเนินการแบบไม่เข้มงวด กล่าวคือ ไม่มีสูตรใดที่เทียบเท่ากับซึ่งใช้ตัวดำเนินการแบบไม่เข้มงวดเท่านั้น สูตรนี้กำหนดไว้ดังนี้สูตรนี้ไม่สามารถใช้ได้ผลในแต่ละครั้งหากมีความจำเป็นต้องถือครอง ณ เวลา.
ตัวอย่าง
ต่อไปนี้เราจะยกตัวอย่างสูตร MTL สามารถดูตัวอย่างเพิ่มเติมได้ในบทความเกี่ยวกับส่วนประกอบย่อยของ MITL เช่น ตรรกะเชิงเวลาแบบช่วงเมตริก (metric interval temporal logic )
- ระบุว่าตัวอักษรแต่ละตัวตามมาด้วยตัวอักษรในอีกหนึ่งหน่วยเวลาต่อมาพอดี.
- ระบุว่าไม่มีเหตุการณ์สองครั้งติดต่อกันของเหตุการณ์ต่างๆ สามารถเกิดขึ้นได้โดยห่างกันเพียงหนึ่งหน่วยเวลาพอดี
การเปรียบเทียบกับ LTL
คำอนันต์มาตรฐาน (ไม่จำกัดเวลา)เป็นฟังก์ชันจากถึงเราสามารถพิจารณาคำดังกล่าวโดยใช้เซตของเวลาได้และฟังก์ชันในกรณีนี้ สำหรับสูตร LTL ที่กำหนดขึ้นเองก็ต่อเมื่อ, ที่ไหนถือว่าเป็นสูตร MTL ที่มีตัวดำเนินการแบบไม่เข้มงวด และตัวห้อย ในแง่นี้ MTL จึงเป็นส่วนขยายของ LTL
ด้วยเหตุนี้ สูตรที่ใช้เฉพาะตัวดำเนินการที่ไม่เข้มงวดจึง...ตัวห้อยเรียกว่าสูตร LTL
ความซับซ้อนของอัลกอริทึม
ชิ้นส่วนของ MTL
ต่อไปนี้เราจะพิจารณาส่วนย่อยบางส่วนของ MTL
มิตล
ส่วนย่อยที่สำคัญของ MTL คือตรรกะเชิงเวลาแบบช่วงเมตริก ( MITL ) ซึ่งมีการนิยามคล้ายกับ MTL โดยมีข้อจำกัดว่าเซตต่างๆ นั้นใช้ในและช่วงเหล่านี้ไม่ใช่ช่วงที่มีสมาชิกเพียงตัวเดียว และมีขอบเขตเป็นจำนวนธรรมชาติหรืออนันต์
กลุ่มย่อยอื่นๆ ของ MITL ได้รับการนิยามไว้ในบทความMITLแล้ว
เศษเสี้ยวแห่งอนาคต
Future-MTL ได้รับการแนะนำไว้ข้างต้นแล้ว ทั้ง ในส่วนของคำที่กำหนดเวลาและสัญญาณต่างๆ นั้นมีการแสดงออกน้อยกว่า Full-MTL [ 3 ] : 3
ตรรกะเชิงเวลาของนาฬิกาเหตุการณ์
ตรรกะเชิงเวลาของนาฬิกาเหตุการณ์[ 6 ]ของ MTL ซึ่งเรียกว่าEventClockTLหรือECLอนุญาตให้ใช้ตัวดำเนินการต่อไปนี้เท่านั้น:
- ตัวดำเนินการบูลีน ได้แก่ และ หรือ และ ไม่
- ตัวดำเนินการuntilและsinceที่ไม่ได้กำหนดเวลา
- ตัวดำเนินการทำนายและประวัติศาสตร์ตามเวลาที่กำหนด
เมื่อใช้สัญญาณ ECL จะมีความสามารถในการแสดงออกได้เทียบเท่ากับ MITL และMITL ความเท่าเทียมกันระหว่างตรรกะสองตัวหลังนี้ได้อธิบายไว้ในบทความMITL แล้ว เราจะกล่าวถึงความเท่าเทียมกันของตรรกะเหล่านั้นกับ ECL โดยสังเขป
ถ้าไม่ใช่สิ่งเดียวและเป็นสูตร MITLถูกกำหนดให้เป็นสูตร MITL ถ้าถ้าเป็นจำนวนเดี่ยว แสดงว่าเทียบเท่ากับซึ่งเป็นสูตร MITL ในทางกลับกัน สำหรับสูตร ECL และช่วงที่มีขอบล่างเป็น 0เทียบเท่ากับสูตร ECL.
ความสามารถในการตอบสนองของ ECL เหนือสัญญาณนั้น สมบูรณ์ แบบPSPACE [ 6 ]
รูปแบบปกติเชิงบวก
สูตร MTL ในรูปแบบปกติเชิงบวกนั้น นิยามได้เกือบเหมือนกับสูตร MTL อื่นๆ โดยมีการเปลี่ยนแปลงสองประการดังต่อไปนี้:
- ตัวดำเนินการReleaseและBackถูกนำมาใช้ในภาษาตรรกะ และไม่ได้ถูกพิจารณาว่าเป็นสัญลักษณ์แทนสูตรอื่นๆ อีกต่อไป
- การปฏิเสธสามารถใช้ได้กับตัวอักษรเท่านั้น
สูตร MTL ใดๆ ก็ตามเทียบเท่ากับสูตรในรูปแบบปกติ สามารถแสดงได้โดยการอุปมานอย่างง่ายเกี่ยวกับสูตร ตัวอย่างเช่น สูตรเทียบเท่ากับสูตรในทำนองเดียวกัน การเชื่อมและการแยกสามารถพิจารณาได้โดยใช้กฎของเดอ มอร์แกน
กล่าวโดยเคร่งครัดแล้ว ชุดสูตรในรูปแบบปกติเชิงบวกไม่ได้เป็นส่วนหนึ่งของ MTL
ดูเพิ่มเติม
- ตรรกศาสตร์เชิงเวลาแบบประพจน์ที่มีเวลา (Timed Propositional Temporal Logic หรือ LTL) เป็นส่วนขยายอีกรูปแบบหนึ่งของ LTL ที่สามารถวัดเวลาได้