กลับไปหน้าบทความ

อ่าน 12 นาที

ตรรกะเชิงเวลาเมตริก

ตรรกศาสตร์เชิงเวลาแบบเมตริก ( MTL ) เป็นกรณีพิเศษของ ตรรกศาสตร์เชิงเวลา มันเป็นการขยายของตรรกศาสตร์เชิงเวลาโดยที่ตัวดำเนินการเชิงเวลาถูกแทนที่ด้วยตัวดำเนินการที่จำกัดเวลา เช่น...

ตรรกะเชิงเวลาเมตริก

ตรรกศาสตร์เชิงเวลาแบบเมตริก ( MTL ) เป็นกรณีพิเศษของตรรกศาสตร์เชิงเวลามันเป็นการขยายของตรรกศาสตร์เชิงเวลาโดยที่ตัวดำเนินการเชิงเวลาถูกแทนที่ด้วยตัวดำเนินการที่จำกัดเวลา เช่น ตัวดำเนินการ until , next , sinceและpreviousมันเป็นตรรกศาสตร์เชิงเส้นที่สมมติทั้งการสลับลำดับและการใช้แนวคิดนาฬิกาเสมือน โดยนิยามอยู่บนความหมายเชิงเวลาแบบจำนวนเต็มที่อ่อนแอและอิงตามจุด

MTL ได้รับการอธิบายว่าเป็นรูปแบบการกำหนดคุณสมบัติที่โดดเด่นสำหรับระบบเรียลไทม์[ 1 ] MTL เต็มรูปแบบเหนือคำที่มีเวลาไม่จำกัดนั้นไม่สามารถตัดสินได้[ 2 ]

ไวยากรณ์

ตรรกะเชิงเวลาเมตริกแบบสมบูรณ์ (Full Metric Temporal Logic: MTL) ถูกกำหนดในลักษณะเดียวกับตรรกะเชิงเวลาเชิงเส้น (Linear Temporal Logic: LILOG ) โดยที่เซตของจำนวนจริงที่ไม่เป็นลบจะถูกเพิ่มเข้าไปในตัวดำเนินการเชิงเวลา แบบโมดอล UและSในทางทฤษฎีแล้ว MTL สร้างขึ้นจาก:

เมื่อละเว้นตัวห้อย จะถือว่าเท่ากับโดยปริยาย[0,){\displaystyle [0,\infty )}.

โปรดทราบว่าตัวดำเนินการถัดไปNไม่ถือว่าเป็นส่วนหนึ่งของไวยากรณ์ MTL แต่จะถูกกำหนดจากตัวดำเนินการอื่นๆ แทน

อดีตและอนาคต

ส่วนย่อยของตรรกะเชิงเวลาแบบเมตริกในอดีตซึ่งใช้สัญลักษณ์แทนด้วยpast-MTLนั้น ถูกกำหนดให้เป็นการจำกัดตรรกะเชิงเวลาแบบเมตริกฉบับเต็ม โดยไม่รวม ตัวดำเนินการ until ในทำนองเดียวกันส่วนย่อยของตรรกะเชิงเวลาแบบเมตริกในอนาคตซึ่งใช้สัญลักษณ์แทนด้วยfuture-MTLนั้น ถูกกำหนดให้เป็นการจำกัดตรรกะเชิงเวลาแบบเมตริกฉบับเต็ม โดยไม่รวมตัวดำเนินการsince

ขึ้นอยู่กับผู้เขียนMTL อาจถูกกำหนดให้เป็นส่วนของ MTL ในอนาคต ซึ่งในกรณีนี้ MTL เต็มรูปแบบเรียกว่า MTL+Past [ 1 ] [ 3 ]หรือMTLอาจถูกกำหนดให้เป็น MTL เต็มรูปแบบ

เพื่อหลีกเลี่ยงความกำกวม บทความนี้จึงใช้ชื่อ full-MTL, past-MTL และ future-MTL เมื่อเงื่อนไขของตรรกะทั้งสามเป็นจริง จะใช้คำว่า MTL เพียงอย่างเดียว

แบบอย่าง

อนุญาตทีอาร์+{\displaystyle T\subseteq \mathbb {R} _{+}}โดยสัญชาตญาณแล้ว แสดงถึงชุดของจุดเวลาต่างๆ ให้γ:ทีเอ{\displaystyle \gamma :T\to A}ฟังก์ชันที่เชื่อมโยงตัวอักษรกับแต่ละช่วงเวลาทีที{\displaystyle t\in T}แบบจำลองของสูตร MTL ​​คือฟังก์ชันดังกล่าวγ{\displaystyle \gamma }. โดยปกติ,γ{\displaystyle \gamma }เป็นได้ทั้งคำที่กำหนดเวลาไว้หรือสัญญาณในกรณีเหล่านั้นที{\displaystyle T}เป็นได้ทั้งเซตย่อยที่ไม่ต่อเนื่อง หรือช่วงที่ประกอบด้วย 0

ความหมาย

อนุญาตที{\displaystyle T}และγ{\displaystyle \gamma }ตามที่กล่าวมาข้างต้น และปล่อยให้ทีที{\displaystyle t\in T}เวลาที่กำหนดไว้ เราจะมาอธิบายความหมายของสูตร MTL ​​กันต่อไปϕ{\displaystyle \phi }ถือครอง ณ เวลาที{\displaystyle t}ซึ่งแสดงด้วยสัญลักษณ์γ,ทีϕ{\displaystyle \gamma ,t\models \phi }.

อนุญาตฉันอาร์+{\displaystyle I\subseteq \mathbb {R} _{+}}และϕ,ψเอ็มทีแอล{\displaystyle \phi ,\psi \in MTL}เราจะพิจารณาสูตรนี้เป็นอันดับแรกϕยูฉันψ{\displaystyle \phi {\คณิตศาสตร์ {U}__{I}\psi }เรากล่าวว่าγ,ทีϕยูฉันψ{\displaystyle \gamma ,t\models \phi {\mathcal {U}}_{I}\psi }ก็ต่อเมื่อมีเวลาอยู่บ้างเท่านั้นทีที+ฉัน{\displaystyle t'\in t+I}โดยที่:

  • γ,ทีψ{\displaystyle \gamma ,t'\models \psi }และ
  • สำหรับแต่ละคนที"ที{\displaystyle t''\in T}กับที<ที"<ที{\displaystyle t<t''<t'},γ,ที"ϕ{\displaystyle \gamma ,t''\models \phi }.

ต่อไปนี้เราจะพิจารณาสูตรดังกล่าวϕเอสฉันψ{\displaystyle \phi {\คณิตศาสตร์ {S}__{I}\psi }(ออกเสียงว่า "ϕ{\displaystyle \phi }เนื่องจาก ในฉัน{\displaystyle I}ψ{\displaystyle \psi }เรากล่าวว่าγ,ทีϕเอสฉันψ{\displaystyle \gamma ,t\models \phi {\mathcal {S}}_{I}\psi }ก็ต่อเมื่อมีเวลาอยู่บ้างเท่านั้นทีทีฉัน{\displaystyle t'\in t-I}โดยที่:

  • γ,ทีψ{\displaystyle \gamma ,t'\models \psi }และ
  • สำหรับแต่ละคนที"ที{\displaystyle t''\in T}กับที<ที"<ที{\displaystyle t'<t''<t},γ,ที"ϕ{\displaystyle \gamma ,t''\models \phi }.

คำจำกัดความของ γ,ทีϕ{\displaystyle \gamma ,t\models \phi }สำหรับค่าของϕ{\displaystyle \phi }คำว่า "ไม่ได้พิจารณาข้างต้น" มีความหมายคล้ายกับคำจำกัดความในกรณี ของ LTL

ตัวดำเนินการที่กำหนดจากตัวดำเนินการ MTL ​​พื้นฐาน

สูตรบางสูตรถูกใช้บ่อยมากจนต้องมีการเพิ่มตัวดำเนินการใหม่เข้าไป ตัวดำเนินการเหล่านี้มักไม่ถือว่าเป็นส่วนหนึ่งของคำจำกัดความของ MTL แต่เป็นเพียงรูปแบบการเขียนที่บ่งบอกถึงสูตร MTL ​​ที่ซับซ้อนกว่า เราจะพิจารณาตัวดำเนินการที่มีอยู่ใน LTL ก่อน ในส่วนนี้ เราจะกำหนดϕ,ψ{\displaystyle \phi ,\psi } สูตร MTL ​​และฉันอาร์+{\displaystyle I\subseteq \mathbb {R} _{+}}.

ผู้ประกอบการที่คล้ายกับผู้ประกอบการขนส่งสินค้าแบบไม่เต็มคันรถ (LTL)

ปล่อยและกลับไปที่

เราใช้สัญลักษณ์ แทนด้วยϕอาร์ฉันψ{\displaystyle \phi {\mathcal {R}}_{I}\psi } (ออกเสียงว่า "ϕ{\displaystyle \phi }เผยแพร่ในฉัน{\displaystyle I},ψ{\displaystyle \psi }") สูตร¬(¬ϕยูฉัน¬ψ){\displaystyle \neg (\neg \phi {\mathcal {U}}_{I}\neg \psi )}สูตรนี้ใช้ได้ ณ เวลา .ที{\displaystyle t}หากเป็นกรณีใดกรณีหนึ่งต่อไปนี้:

  • มีเวลาอยู่บ้างทีที+ฉัน{\displaystyle t'\in t+I}โดยที่ϕ{\displaystyle \phi }ถือครอง และψ{\displaystyle \psi }ถือไว้ในช่วงเวลา(ที,ที)(ที+ฉัน){\displaystyle (t,t')\cap (t+I)}.
  • ในแต่ละครั้งทีที+ฉัน{\displaystyle t'\in t+I},ψ{\displaystyle \psi }ถือครอง

ชื่อ "release" มาจากกรณี LTL ซึ่งสูตรนี้หมายความง่ายๆ ว่าψ{\displaystyle \psi }ควรยึดถือเสมอ เว้นแต่ϕ{\displaystyle \phi }ปล่อยออกมา

คำที่เทียบเท่ากับคำว่า "ปล่อย" ในอดีตนั้นแสดงด้วยϕบีฉันψ{\displaystyle \phi {\mathcal {B}}_{I}\psi } (ออกเสียงว่า "ϕ{\displaystyle \phi }กลับไปที่ฉัน{\displaystyle I},ψ{\displaystyle \psi }") และเท่ากับสูตร¬(¬ϕเอสฉัน¬ψ){\displaystyle \neg (\neg \phi {\mathcal {S}}_{I}\neg \psi )}.

ในที่สุดและในที่สุด

เราใช้สัญลักษณ์ แทนด้วยฉันϕ{\displaystyle \Diamond _{I}\phi }หรือเอฟฉันϕ{\displaystyle {\mathcal {F}}_{I}\phi }(ออกเสียงว่า "ในที่สุด" ใน)ฉัน{\displaystyle I},ϕ{\displaystyle \phi }หรือ "ในที่สุด"ฉัน{\displaystyle I},ϕ{\displaystyle \phi }") สูตรยูฉันϕ{\displaystyle \top {\mathcal {U}}_{I}\phi }โดยสัญชาตญาณแล้ว สูตรนี้ใช้ได้ผล ณ เวลาที{\displaystyle t} ถ้ามีเวลาบ้างทีที+ฉัน{\displaystyle t'\in t+I}โดยที่ϕ{\displaystyle \phi }ถือครอง

เราใช้สัญลักษณ์ แทนด้วยฉันϕ{\displaystyle \Box _{I}\phi }หรือจีฉันϕ{\displaystyle {\mathcal {G}}_{I}\phi }(ออกเสียงว่า "โกลบอลลี่ อิน)ฉัน{\displaystyle I},ϕ{\displaystyle \phi }",) สูตร¬ฉัน¬ϕ{\displaystyle \neg \Diamond _{I}\neg \phi }โดยสัญชาตญาณแล้ว สูตรนี้ใช้ได้ผล ณ เวลาที{\displaystyle t}ถ้าเป็นตลอดกาลทีที+ฉัน{\displaystyle t'\in t+I},ϕ{\displaystyle \phi }ถือครอง

เราใช้สัญลักษณ์ แทนด้วยฉันϕ{\displaystyle {\overleftarrow {\Box }}_{I}\phi } และฉันϕ{\displaystyle {\overleftarrow {\Diamond }}_{I}\phi }สูตรที่คล้ายกับฉันϕ{\displaystyle \Box _{I}\phi }และฉันϕ{\displaystyle \Diamond _{I}\phi }, ที่ไหนยู{\displaystyle {\mathcal {U}}}ถูกแทนที่ด้วยเอส{\displaystyle {\mathcal {S}}}ทั้งสองสูตรมีความหมายเหมือนกันโดยพื้นฐาน แต่จะแตกต่างกันเมื่อเราพิจารณาจากอดีตแทนที่จะเป็นอนาคต

ถัดไปและก่อนหน้า

กรณีนี้แตกต่างจากกรณีที่ผ่านมาเล็กน้อย เนื่องจากความหมายโดยนัยของสูตร "ถัดไป" และ "ก่อนหน้า" แตกต่างกันไปตามประเภทของฟังก์ชันγ{\displaystyle \gamma }ที่พิจารณา.

เราใช้สัญลักษณ์ แทนด้วยฉันϕ{\displaystyle \bigcirc _{I}\phi }หรือเอ็นฉันϕ{\displaystyle {\mathcal {N}}_{I}\phi } (ออกเสียงว่า "เน็กซ์ อิน)ฉัน{\displaystyle I},ϕ{\displaystyle \phi }") สูตรยูฉันϕ{\displaystyle \bot {\mathcal {U}}_{I}\phi }ในทำนองเดียวกัน เราใช้สัญลักษณ์ แทนฉันϕ{\displaystyle \ominus _{I}\phi }[ 4 ] (ออกเสียงว่า "ก่อนหน้านี้ในฉัน{\displaystyle I},ϕ{\displaystyle \phi }) สูตรเอสฉันϕ{\displaystyle \bot {\mathcal {S}}_{I}\phi }การอธิบายเกี่ยวกับตัวดำเนินการ Next ต่อไปนี้ยังใช้ได้กับตัวดำเนินการ Previously ด้วยการสลับลำดับอดีตและอนาคต

เมื่อประเมินสูตรนี้กับคำที่กำหนดเวลาไว้γ:ทีเอ{\displaystyle \gamma :T\to A}สูตรนี้หมายความว่าทั้งสองอย่าง:

  • ในครั้งต่อไปในขอบเขตของคำจำกัดความที{\displaystyle T}สูตรϕ{\displaystyle \phi }จะคงอยู่
  • นอกจากนี้ ระยะห่างระหว่างเวลาครั้งถัดไปกับเวลาปัจจุบันอยู่ในช่วงเวลาดังกล่าวฉัน{\displaystyle I}.
  • โดยเฉพาะอย่างยิ่ง ครั้งถัดไปนี้ยังคงใช้ได้ ดังนั้น เวลาปัจจุบันจึงไม่ใช่จุดจบของโลก

เมื่อประเมินสูตรนี้กับสัญญาณγ{\displaystyle \gamma }แนวคิดเรื่อง "ครั้งหน้า" นั้นไม่สมเหตุสมผล เพราะ "ครั้งหน้า" หมายถึง "ทันทีหลังจากนั้น" พูดให้ชัดเจนยิ่งขึ้นก็คือ...γ,ทีϕ{\displaystyle \gamma ,t\models \circ \phi }วิธี:

  • ฉัน{\displaystyle I}ประกอบด้วยช่วงเวลาในรูปแบบ(0,ϵ){\displaystyle (0,\epsilon )}และ
  • สำหรับแต่ละคนที(ที,ที+ϵ){\displaystyle t'\in (t,t+\epsilon )},γ,ทีϕ{\displaystyle \gamma ,t'\models \phi }.

ผู้ประกอบการรายอื่น

ต่อไปนี้เราจะพิจารณาผู้ประกอบการที่ไม่เหมือนกับผู้ประกอบการ LTL มาตรฐานทั่วไป

ล้มแล้วลุกขึ้น

เราใช้สัญลักษณ์ แทนด้วยϕ{\displaystyle \uparrow \phi }(ออกเสียงว่า "ไรส์")ϕ{\displaystyle \phi }") สูตรที่ใช้ได้เมื่อϕ{\displaystyle \phi }กลายเป็นความจริง กล่าวให้แม่นยำยิ่งขึ้นคือ อย่างใดอย่างหนึ่งϕ{\displaystyle \phi }ไม่เป็นจริงในอดีตอันใกล้ แต่ไม่เป็นจริงในขณะนี้ หรือไม่เป็นจริงแต่จะเป็นจริงในอนาคตอันใกล้ อย่างเป็นทางการϕ{\displaystyle \uparrow \phi }ถูกกำหนดให้เป็น(ϕ(¬ϕเอส))(¬ϕ(ϕยู)){\displaystyle (\phi \land (\neg \phi {\mathcal {S}}\top ))\lor (\neg \phi \land (\phi {\mathcal {U}}\top ))}[ 5 ]

สูตรนี้ใช้ได้ผลเสมอเมื่อพูดถึงคำพูดที่ใช้เวลาพิจารณา แน่นอนϕยู{\displaystyle \phi {\mathcal {U}}\top }และ¬ϕเอส{\displaystyle \neg \phi {\mathcal {S}}\top }เป็นจริงเสมอ ดังนั้นสูตรจึงเทียบเท่ากับϕ¬ϕ{\displaystyle \phi \lor \neg \phi }ดังนั้นจึงเป็นความจริง

เนื่องจากสมมาตร เราจึงใช้สัญลักษณ์ แทนด้วยϕ{\displaystyle \downarrow \phi }(ออกเสียงว่า "ฟอลล์")ϕ{\displaystyle \phi }) สูตรที่ใช้ได้เมื่อϕ{\displaystyle \phi }กลายเป็นเท็จ ดังนั้นจึงนิยามได้ดังนี้(¬ϕ(ϕเอส))(ϕ(¬ϕยู)){\displaystyle (\neg \phi \land (\phi {\mathcal {S}}\top ))\land (\phi \land (\neg \phi {\mathcal {U}}\top ))}.

ประวัติศาสตร์และคำพยากรณ์

ต่อไปนี้เราจะแนะนำ ตัวดำเนิน การทำนายซึ่งใช้สัญลักษณ์ แทนด้วย{\displaystyle \triangleright }เราใช้สัญลักษณ์ แทนฉันϕ{\displaystyle \triangleright _{I}\phi }[ 6 ]สูตร¬ϕยูฉันϕ{\displaystyle \neg \phi {\mathcal {U}}_{I}\phi }สูตรนี้ยืนยันว่ามีช่วงเวลาแรกในอนาคตอยู่ช่วงหนึ่งซึ่งเป็นไปตามเงื่อนไขที่ว่าϕ{\displaystyle \phi }และเวลาที่จะรอคอยช่วงเวลาแรกนี้เป็นของฉัน{\displaystyle I}.

ต่อไปนี้เราจะพิจารณาสูตรนี้กับคำที่มีเวลาและสัญญาณ โดยเราจะพิจารณาคำที่มีเวลาก่อน สมมติว่าฉัน=∣เอ,{\displaystyle I=\mid a,b\mid '}ที่ไหน{\displaystyle \mid }และ{\displaystyle \mid '}แสดงถึงขอบเขตเปิดหรือขอบเขตปิด ให้γ{\displaystyle \gamma }คำที่กำหนดเวลาและที{\displaystyle t}ในขอบเขตของคำจำกัดความ เมื่อเวลาผ่านไป สูตรดังกล่าวγ,ทีฉันϕ{\displaystyle \gamma ,t\models \triangleright _{I}\phi }เป็นจริงก็ต่อเมื่อγ,ที]0,[ฉัน¬ϕฉันϕ{\displaystyle \gamma ,t\models \Box _{]0,b[\setminus I}\neg \phi \land \Diamond _{I}\phi }สูตรนี้ก็ใช้ได้เช่นกัน กล่าวคือ สูตรนี้เพียงแค่ยืนยันว่า ในอนาคต จนกว่าจะถึงช่วงเวลาดังกล่าวที+ฉัน{\displaystyle t+I}ตรงตามเกณฑ์ที่กำหนดϕ{\displaystyle \phi }ไม่ควรยึดถือ นอกจากนี้ϕ{\displaystyle \phi }ควรคงไว้ในช่วงเวลาใดเวลาหนึ่งที+ฉัน{\displaystyle t+I}อันที่จริง หากมีเวลาเหลือเฟือที"ที+ฉัน{\displaystyle t''\in t+I}โดยที่γ,ที"ϕ{\displaystyle \gamma ,t''\models \phi }จำไว้ว่า เวลาที่มีอยู่นั้นมีจำนวนจำกัดเท่านั้นทีที+ฉัน{\displaystyle t'\in t+I}กับที<ที"{\displaystyle t'<t''}และγ,ทีϕ{\displaystyle \gamma ,t'\models \phi }ดังนั้น จึงจำเป็นต้องมีขนาดที่เล็กกว่านั้นอยู่ด้วยที"{\displaystyle t''}.

ต่อไปนี้เรามาพิจารณาสัญญาณกัน ความเท่าเทียมกันที่กล่าวถึงข้างต้นใช้ไม่ได้อีกต่อไปกับสัญญาณ เนื่องจากข้อเท็จจริงที่ว่า เมื่อใช้ตัวแปรที่แนะนำข้างต้น อาจมีค่าที่ถูกต้องเป็นจำนวนอนันต์สำหรับที{\displaystyle t'}เนื่องจากโดเมนการนิยามของสัญญาณมีความต่อเนื่อง ดังนั้นสูตรจึงเป็นดังนี้ฉันϕ{\displaystyle \triangleright _{I}\phi }นอกจากนี้ยังช่วยให้มั่นใจได้ว่าช่วงเวลาแรกที่ϕ{\displaystyle \phi }ช่องเก็บของด้านซ้ายปิดสนิทแล้ว

ด้วยสมมาตรเชิงเวลา เราจึงกำหนด ตัวดำเนิน การประวัติศาสตร์ซึ่งแสดงด้วยสัญลักษณ์{\displaystyle \triangleleft }เรากำหนดฉันϕ{\displaystyle \triangleleft _{I}\phi }เช่น¬ϕเอสฉันϕ{\displaystyle \neg \phi {\mathcal {S}}_{I}\phi }สูตรนี้ยืนยันว่ามีช่วงเวลาสุดท้ายในอดีตอยู่ช่วงหนึ่งซึ่งเป็นไปตามเงื่อนไขที่ว่าϕ{\displaystyle \phi }จับไว้ และเวลาตั้งแต่วินาทีแรกนั้นเป็นของฉัน{\displaystyle I}.

ตัวดำเนินการที่ไม่เข้มงวด

ความหมายของตัวดำเนินการuntilและsinceที่นำเสนอมานั้นไม่ได้คำนึงถึงเวลาปัจจุบัน กล่าวคือ เพื่อให้ϕ1ยูϕ2{\displaystyle \phi _{1}{\mathcal {U}}\phi _{2}}ถือครองไว้ในบางช่วงเวลาที{\displaystyle t}, ไม่ใช่ทั้งสองอย่างϕ1{\displaystyle \phi _{1}}ก็ไม่เช่นกันϕ2{\displaystyle \phi _{2}}ต้องถือไว้ ณ เวลานั้นที{\displaystyle t}นี่ไม่ใช่สิ่งที่ต้องการเสมอไป ตัวอย่างเช่น ในประโยค "จะไม่มีข้อผิดพลาดจนกว่าระบบจะปิด" ความจริงแล้วอาจต้องการให้ไม่มีข้อผิดพลาดในขณะนี้ ดังนั้น เราจึงแนะนำ ตัวดำเนินการ until อีกตัวหนึ่ง เรียกว่าuntil แบบไม่เข้มงวดซึ่งใช้สัญลักษณ์ แทนด้วยยู¯{\displaystyle {\overline {\mathcal {U}}}}ซึ่งคำนึงถึงเวลาปัจจุบันด้วย

เราใช้สัญลักษณ์ แทนด้วยϕ1ยู¯ฉันϕ2{\displaystyle \phi _{1}{\overline {\mathcal {U}}}_{I}\phi _{2}}และϕ1เอส¯ฉันϕ2{\displaystyle \phi _{1}{\overline {\mathcal {S}}}_{I}\phi _{2}}ทั้ง:

  • สูตรต่างๆϕ2(ϕ1(ϕ1ยูฉันϕ2)){\displaystyle \phi _{2}\lor (\phi _{1}\land (\phi _{1}{\mathcal {U}}_{I}\phi _{2}))}และϕ2(ϕ1(ϕ1เอสฉันϕ2)){\displaystyle \phi _{2}\lor (\phi _{1}\land (\phi _{1}{\mathcal {S}}_{I}\phi _{2}))}ถ้า0ฉัน{\displaystyle 0\in I}, และ
  • สูตรต่างๆϕ1(ϕ1ยูฉันϕ2){\displaystyle \phi _{1}\land (\phi _{1}{\mathcal {U}}_{I}\phi _{2})}และϕ1(ϕ1เอสฉันϕ2){\displaystyle \phi _{1}\land (\phi _{1}{\mathcal {S}}_{I}\phi _{2})}มิฉะนั้น.

สำหรับผู้ให้บริการรายใดก็ตามโอ{\displaystyle {\mathcal {O}}}ตามที่ได้กล่าวไว้ข้างต้น เราจะใช้สัญลักษณ์ แทนโอ¯{\displaystyle {\overline {\mathcal {O}}}}สูตรที่ใช้เงื่อนไขแบบไม่เข้มงวดจนกระทั่ง s และsince ตัวอย่างเช่น¯พี{\displaystyle {\overline {\Diamond }}p}เป็นคำย่อของยู¯พี{\displaystyle \top {\overline {\mathcal {U}}}p}.

ตัวดำเนินการแบบเข้มงวดไม่สามารถกำหนดได้โดยใช้ตัวดำเนินการแบบไม่เข้มงวด กล่าวคือ ไม่มีสูตรใดที่เทียบเท่ากับฉันพี{\displaystyle \bigcirc _{I}p}ซึ่งใช้ตัวดำเนินการแบบไม่เข้มงวดเท่านั้น สูตรนี้กำหนดไว้ดังนี้ยูฉันพี{\displaystyle \bot {\mathcal {U}}_{I}p}สูตรนี้ไม่สามารถใช้ได้ผลในแต่ละครั้งที{\displaystyle t}หากมีความจำเป็นต้อง{\displaystyle \bot }ถือครอง ณ เวลาที{\displaystyle t}.

ตัวอย่าง

ต่อไปนี้เราจะยกตัวอย่างสูตร MTL ​​สามารถดูตัวอย่างเพิ่มเติมได้ในบทความเกี่ยวกับส่วนประกอบย่อยของ MITL เช่น ตรรกะเชิงเวลาแบบช่วงเมตริก (metric interval temporal logic )

  • (พี{1}q){\displaystyle \Box (p\implies \Diamond _{\{1\}}q)}ระบุว่าตัวอักษรแต่ละตัวพี{\displaystyle p}ตามมาด้วยตัวอักษรในอีกหนึ่งหน่วยเวลาต่อมาพอดีq{\displaystyle q}.
  • (พี¬{1}พี){\displaystyle \Box (p\implies \neg \Diamond _{\{1\}}p)}ระบุว่าไม่มีเหตุการณ์สองครั้งติดต่อกันของพี{\displaystyle p}เหตุการณ์ต่างๆ สามารถเกิดขึ้นได้โดยห่างกันเพียงหนึ่งหน่วยเวลาพอดี

การเปรียบเทียบกับ LTL

คำอนันต์มาตรฐาน (ไม่จำกัดเวลา)=เอ0,เอ1,,{\displaystyle w=a_{0},a_{1},\dots ,}เป็นฟังก์ชันจากเอ็น{\displaystyle \mathbb {N} }ถึงเอ{\displaystyle A}เราสามารถพิจารณาคำดังกล่าวโดยใช้เซตของเวลาได้ที=เอ็น{\displaystyle T=\mathbb {N} }และฟังก์ชันγ(ฉัน)=เอฉัน{\displaystyle \gamma (i)=a_{i}}ในกรณีนี้ สำหรับϕ{\displaystyle \phi }สูตร LTL ที่กำหนดขึ้นเอง,ฉันϕ{\displaystyle w,i\models \phi }ก็ต่อเมื่อγ,ฉันϕ{\displaystyle \gamma ,i\models \phi }, ที่ไหนϕ{\displaystyle \phi }ถือว่าเป็นสูตร MTL ​​ที่มีตัวดำเนินการแบบไม่เข้มงวด และ[0,){\displaystyle [0,\infty )}ตัวห้อย ในแง่นี้ MTL จึงเป็นส่วนขยายของ LTL

ด้วยเหตุนี้ สูตรที่ใช้เฉพาะตัวดำเนินการที่ไม่เข้มงวดจึง...[0,){\displaystyle [0,\infty )}ตัวห้อยเรียกว่าสูตร LTL

ความซับซ้อนของอัลกอริทึม

ความพึงพอใจ ของ ECL เหนือสัญญาณคือEXPSPACE - สมบูรณ์[ 6 ]

ชิ้นส่วนของ MTL

ต่อไปนี้เราจะพิจารณาส่วนย่อยบางส่วนของ MTL

มิตล

ส่วนย่อยที่สำคัญของ MTL คือตรรกะเชิงเวลาแบบช่วงเมตริก ( MITL ) ซึ่งมีการนิยามคล้ายกับ MTL โดยมีข้อจำกัดว่าเซตต่างๆ นั้นฉัน{\displaystyle I}ใช้ในยู{\displaystyle {\mathcal {U}}}และเอส{\displaystyle {\mathcal {S}}}ช่วงเหล่านี้ไม่ใช่ช่วงที่มีสมาชิกเพียงตัวเดียว และมีขอบเขตเป็นจำนวนธรรมชาติหรืออนันต์

กลุ่มย่อยอื่นๆ ของ MITL ได้รับการนิยามไว้ในบทความMITLแล้ว

เศษเสี้ยวแห่งอนาคต

Future-MTL ได้รับการแนะนำไว้ข้างต้นแล้ว ทั้ง ในส่วนของคำที่กำหนดเวลาและสัญญาณต่างๆ นั้นมีการแสดงออกน้อยกว่า Full-MTL [ 3 ] : 3

ตรรกะเชิงเวลาของนาฬิกาเหตุการณ์

ตรรกะเชิงเวลาของนาฬิกาเหตุการณ์[ 6 ]ของ MTL ซึ่งเรียกว่าEventClockTLหรือECLอนุญาตให้ใช้ตัวดำเนินการต่อไปนี้เท่านั้น:

  • ตัวดำเนินการบูลีน ได้แก่ และ หรือ และ ไม่
  • ตัวดำเนินการuntilและsinceที่ไม่ได้กำหนดเวลา
  • ตัวดำเนินการทำนายและประวัติศาสตร์ตามเวลาที่กำหนด

เมื่อใช้สัญญาณ ECL จะมีความสามารถในการแสดงออกได้เทียบเท่ากับ MITL และMITL ความเท่าเทียมกันระหว่างตรรกะสองตัวหลังนี้ได้อธิบายไว้ในบทความMITL แล้ว เราจะกล่าวถึงความเท่าเทียมกันของตรรกะเหล่านั้นกับ ECL โดยสังเขป

ถ้าฉัน{\displaystyle I}ไม่ใช่สิ่งเดียวและϕ{\displaystyle \phi }เป็นสูตร MITLฉันϕ{\displaystyle \triangleright _{I}\phi }ถูกกำหนดให้เป็นสูตร MITL ถ้าฉัน={ฉัน}{\displaystyle I=\{i\}}ถ้าเป็นจำนวนเดี่ยว แสดงว่าฉันϕ{\displaystyle \triangleright _{I}\phi }เทียบเท่ากับ]0,ฉัน[¬ϕ]0,ฉัน]ϕ{\displaystyle \Box _{]0,i[}\neg \phi \land \Diamond _{]0,i]}\phi }ซึ่งเป็นสูตร MITL ในทางกลับกัน สำหรับψ{\displaystyle \psi }สูตร ECL และฉัน{\displaystyle I}ช่วงที่มีขอบล่างเป็น 0ฉันψ{\displaystyle \Box _{I}\psi }เทียบเท่ากับสูตร ECL¬ฉัน¬ψ{\displaystyle \neg \triangleright _{I}\neg \psi }.

ความสามารถในการตอบสนองของ ECL เหนือสัญญาณนั้น สมบูรณ์ แบบPSPACE [ 6 ]

รูปแบบปกติเชิงบวก

สูตร MTL ​​ในรูปแบบปกติเชิงบวกนั้น นิยามได้เกือบเหมือนกับสูตร MTL ​​อื่นๆ โดยมีการเปลี่ยนแปลงสองประการดังต่อไปนี้:

  • ตัวดำเนินการReleaseและBackถูกนำมาใช้ในภาษาตรรกะ และไม่ได้ถูกพิจารณาว่าเป็นสัญลักษณ์แทนสูตรอื่นๆ อีกต่อไป
  • การปฏิเสธสามารถใช้ได้กับตัวอักษรเท่านั้น

สูตร MTL ​​ใดๆ ก็ตามเทียบเท่ากับสูตรในรูปแบบปกติ สามารถแสดงได้โดยการอุปมานอย่างง่ายเกี่ยวกับสูตร ตัวอย่างเช่น สูตร¬(ϕยูเอสψ){\displaystyle \neg (\phi {\mathcal {U}}_{S}\psi )}เทียบเท่ากับสูตร(¬ϕ)อาร์เอส(¬ψ){\displaystyle (\neg \phi ){\mathcal {R}}_{S}(\neg \psi )}ในทำนองเดียวกัน การเชื่อมและการแยกสามารถพิจารณาได้โดยใช้กฎของเดอ มอร์แกน

กล่าวโดยเคร่งครัดแล้ว ชุดสูตรในรูปแบบปกติเชิงบวกไม่ได้เป็นส่วนหนึ่งของ MTL

ดูเพิ่มเติม

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ ตรรกะเชิงเวลาเมตริก

ตรรกศาสตร์เชิงเวลาแบบเมตริก ( MTL ) เป็นกรณีพิเศษของ ตรรกศาสตร์เชิงเวลา มันเป็นการขยายของตรรกศาสตร์เชิงเวลาโดยที่ตัวดำเนินการเชิงเวลาถูกแทนที่ด้วยตัวดำเนินการที่จำกัดเวลา เช่น...

ไวยากรณ์

ตรรกะ เชิงเวลาเมตริกแบบสมบูรณ์ (Full Metric Temporal Logic: MTL) ถูกกำหนดในลักษณะเดียวกับ ตรรกะเชิงเวลาเชิงเส้น (Linear Temporal Logic: LILOG ) โดยที่เซตของจำนวนจริงที่ไม่เป็นลบจะถูกเพิ่มเข้าไปใน ตัวดำเนินการเชิง เวลา แบบโมดอล U และ S ในทางทฤษฎีแล้ว MTL...

อดีตและอนาคต

ส่วน ย่อยของตรรกะเชิงเวลาแบบเมตริกในอดีต ซึ่งใช้สัญลักษณ์แทนด้วย past-MTL นั้น ถูกกำหนดให้เป็นการจำกัดตรรกะเชิงเวลาแบบเมตริกฉบับเต็ม โดยไม่รวม ตัวดำเนินการ until ใน ทำนองเดียวกัน ส่วนย่อยของตรรกะเชิงเวลาแบบเมตริกในอนาคต ซึ่งใช้สัญลักษณ์แทนด้วย future-MTL นั้น...

แบบอย่าง

อนุญาต ที ⊆ อาร์ + {\displaystyle T\subseteq \mathbb {R} _{+}} โดยสัญชาตญาณแล้ว แสดงถึงชุดของจุดเวลาต่างๆ ให้ γ : ที → เอ {\displaystyle \gamma :T\to A} ฟังก์ชันที่เชื่อมโยงตัวอักษรกับแต่ละช่วงเวลา ที ∈ ที {\displaystyle t\in T} แบบจำลองของสูตร MTL...