การแนะนำ

เป้าหมาย

เรียนรู้เกี่ยวกับ

  • ความหมายของนกฮูก
  • Logics รายละเอียด
  • เหตุผล Tableau

เงื่อนไข

  • ความรู้พื้นฐานของแคลคูลัสเชิงประพจน์
  • ความรู้พื้นฐานของตรรกะลำดับแรก


ความหมายของนกฮูก

ความหมายของนกฮูกจะขึ้นอยู่กับ Logics คำอธิบายที่มีความหมายอย่างเป็นทางการแบบทฤษฎี

OWL DL สอดคล้องกับ \ (\ mathcal {Shoin} (D) \)

นกฮูก 2 สอดคล้องกับ \ (\ mathcal {SROIQ} (D) \)

ในการบรรยายนี้เราจะอธิบายความหมายของ OWL DL โดยการอธิบายตรรกะคำอธิบาย \ (\ mathcal {Shoin} (D) \)

Logics รายละเอียด

  • ครอบครัวของภาษาแทนความรู้
  • เศษเล็กเศษน้อยมักจะจิกลำดับแรก (FOL)
  • ในกรณีส่วนใหญ่ decidable
  • แสดงออกได้เปรียบโดยเปรียบเทียบ
  • ต้นตอมาจากเครือข่ายความหมาย
  • ไวยากรณ์ใช้งานง่าย
  • ตัวแปรอิสระ


Logics รายละเอียด - องค์ประกอบพื้นฐาน

องค์ประกอบพื้นฐาน:

  • ชื่อแนวคิด (แนวคิดอะตอม), นักศึกษาเช่นหนังสือ, ...
  • ชื่อบทบาทเช่น bornIn, worksFor ...
  • ชื่อบุคคล (บุคคลวัตถุ) เช่นสตีเฟนแมรี่ ...

ชุดของชื่อแนวคิดบทบาทและบุคคลมักจะแสดงเป็นลายเซ็นหรือคำศัพท์

Logics รายละเอียด - ฐานความรู้

มักจะเป็นฐานความรู้ DL ประกอบด้วย:

  • TBox \ (\ mathcal {T} \): ข้อมูลเกี่ยวกับแนวคิด
  • ABox \ (\ mathcal {} \): ข้อมูลเกี่ยวกับบุคคล

นอกจากนี้ใน DLs แสดงออกมากขึ้น:

  • RBox \ (\ mathcal {R} \): ข้อมูลเกี่ยวกับบทบาท

\ (\ mathcal {ALC} \) - แนวคิด

\ (\ mathcal {ALC} \), ภาษาที่แสดงคุณลักษณะที่มีส่วนประกอบเป็นที่ง่ายที่สุด propositionally ปิด DL  

(Complex) \ (\ mathcal {ALC} \) แนวความคิดที่ถูกกำหนด inductively ดังนี้

  • ชื่อแนวคิดทุกแนวคิด
  • \ (\ mathcal {\ บน} \) และ \ (\ mathcal {\ bot} \) เป็นแนวความคิด,
  • ถ้า \ (C \) และ \ (D \) เป็นแนวคิดและ \ (r \) คือบทบาทแล้วต่อไปนี้เป็นแนวความคิด:
    • \ (\ NEG C \) (มักจะเรียกว่าการปฏิเสธหรือส่วนประกอบ)
    • \ (C \ sqcap D \) (ร่วมสี่แยกมักจะเรียกหรือ "และ")
    • \ (C \ sqcup D \) (มักเรียกว่าการหย่าสหภาพหรือ "หรือ")
    • \ (\ exists RC \) (ข้อ จำกัด อัตถิภาวนิยมมักจะเรียกว่า)
    • \ (\ forall RC \) (ข้อ จำกัด มูลค่ามักจะเรียกว่า)

\ (\ mathcal {ALC} \) แนวคิด - ตัวอย่าง

\ (\ text {คน} \ sqcap \ exists \ {ข้อความ} hasChild. บน \ \)

  • คนกับเด็ก

\ (\ ข้อความ {สัตว์} \ sqcap \ forall \ text {กิน}. \ text {ผัก} \)

  • สัตว์เท่านั้นที่กินผัก

\ (\ text {ศาสตราจารย์} \ sqcup \ text {นักศึกษา} \)

  • อาจารย์หรือนักเรียน

\ (\ ข้อความ {บุคคล} \ sqcap \ forall \ {ข้อความ bornIn}. \ ข้อความ NEG \ {EuropeanCountry} \)

  • คนที่ไม่ได้เกิดในประเทศในทวีปยุโรป

\ (\ mathcal {ALC} \) - TBox

TBox (กล่อง terminological) ประกอบด้วยชุด จำกัด ของสัจพจน์ terminological

สัจพจน์ terminological มีพื้น (ทั่วไป) สัจพจน์รวมแนวคิดแนวความคิดที่กำหนดคือ \ (C \) และ \ (D \) GCIs จะแสดงเป็น

\[C \sqsubseteq D\]

ความเท่าเทียมกันแนวคิดสามารถแสดงด้วย

\[C \equiv D\]

ซึ่งเป็นคำย่อของ \ (C \ sqsubseteq D \) และ \ (D \ sqsubseteq C \)

\ (\ mathcal {ALC} \) - ABox

ABox ประกอบด้วยชุด จำกัด ของสัจพจน์ assertional ของรูปแบบต่อไปนี้:

  • \ (C () \) ดังนั้นที่เรียกว่ายืนยันแนวคิด
  • \ (r (b) \) ดังนั้นที่เรียกว่ายืนยันบทบาท

\ (\ mathcal {ALC} \) - ความหมาย (1)

Definiton อย่างเป็นทางการของความหมายรูปแบบทฤษฎี \ (\ mathcal {ALC} \) จะได้รับโดยวิธีการของการตีความ \ (\ mathcal {I} = (\ Delta ^ {\ mathcal {I}} \ cdot ^ { \ mathcal {I}}) \) ประกอบด้วย

  • โดเมนที่ไม่ว่างเปล่า \ (\ Delta ^ {\ mathcal {I}} \)
  • การทำแผนที่ \ (\ cdot ^ {\ mathcal {I}} \) แผนที่ซึ่ง
    • บุคคลทุกคน \ (\) กับองค์ประกอบโดเมน \ (^ {\ mathcal {I}} \ in \ Delta ^ {\ mathcal {I}} \)
    • ชื่อแนวคิดทุก \ (\) เพื่อ subset ของโดเมน \ (^ {\ mathcal {I}} \ subseteq \ Delta ^ {\ mathcal {I}} \)
    • ทุกบทบาท \ (r \) ถึงชุดของคู่ขององค์ประกอบโดเมน \ (r ^ {\ mathcal {I}} \ subseteq \ Delta ^ {\ mathcal {I}} \ times \ Delta ^ {\ mathcal {I}} \)

\ (\ mathcal {ALC} \) - ความหมาย (2)

  • การตีความถูกขยายแนวความคิดที่ซับซ้อนโดย
    • \ (\ ^ บน \ mathcal {I} = \ Delta ^ \ mathcal {I} \)
    • \ (\ bot \ mathcal {I} = \ emptyset \)
    • \ ((\ NEG C) ^ \ mathcal {I} = \ Delta ^ \ mathcal {I} \ setminus C ^ \ mathcal {I} \)
    • \ ((C \ sqcap D) ^ \ mathcal {I} = C ^ \ mathcal {I} \ Cap d ^ \ mathcal {I} \)
    • \ ((C \ sqcup D) ^ \ mathcal {I} = C ^ \ mathcal {I} \ ถ้วย D ^ \ mathcal {I} \)
    • \ ((\ exists RC) ^ \ mathcal {I} = \ {x \ in \ Delta ^ \ mathcal {I} | \ exists y \ in C ^ \ mathcal {I} \ text {เช่นนั้น} (x, y ) \ in R ^ \ mathcal {I} \)
    • \ ((\ forall RC) ^ \ mathcal {I} = \ {x \ in \ Delta ^ \ mathcal {I} | \ forall (x, y) \ in R ^ \ mathcal {I} \ Rightarrow y \ in C ^ \ mathcal {I} \)

\ (\ mathcal {ALC} \) - ความหมาย (3)

  • การตีความจะขยายออกไปตามหลักการ
    • \ (\ mathcal {I} \ รุ่น C \ sqsubseteq D \ text {IFF} C ^ \ mathcal {I} \ subseteq D ^ \ mathcal {I} \)
    • \ (\ mathcal {I} \ รุ่น C \ equiv D \ text {IFF} C ^ \ mathcal {I} = D ^ \ mathcal {I} \)
    • \ (\ mathcal {I} \ รุ่น C () \ text {IFF} ^ \ mathcal {I} \ in C ^ \ mathcal {I} \)
    • \ (\ mathcal {I} \ r รุ่น (b) \ text {} IFF (^ \ mathcal {I}, B ^ \ mathcal {I}) \ in R ^ \ mathcal {I} \)

\ (\ mathcal {ALC} \) ฐานความรู้ - ตัวอย่าง

TBox \ (\ mathcal {T} \):

\ (\ begin {align} \ text {Man} \ equiv \ ข้อความ NEG \ {ผู้หญิง} \ ข้อความ sqcap \ {คน} \ \ \ text {ผู้หญิง} & \ ข้อความ sqsubseteq \ {คน} \ \ \ text {แม่ } \ equiv \ text {ผู้หญิง} \ sqcap \ exists \ text {hasChild}. \ \ top \ \ end {align} \)

ABox \ (\ mathcal {} \):

\ (\ begin {align} \ text {แมน (สตีเฟน)} \ \ \ ข้อความ NEG \ {Man (MONICA)} \ \ \ text {ผู้หญิง (เจสสิก้า)} \ \ \ text {hasChild (สตีเฟน, เจสสิก้า)} \ \ \ end {align} \)

\ (\ mathcal {ALC} \) ในนกฮูก

\ (\ mathcal {ALC} \) ผู้ประกอบการที่สอดคล้องกับการแสดงออกของนกฮูกต่อไปนี้:

\ (\ begin {align} \ บน & \ text {นกฮูก: Thing} \ \ \ bot & \ text {นกฮูก: ไม่มี} \ \ \ NEG & \ text {นกฮูก: complementOf} \ \ \ sqcup & \ text {นกฮูก: unionOf} \ \ \ sqcap & \ text {นกฮูก: intersectionOf} \ \ \ exists & \ text {นกฮูก: someValues​​From} \ \ \ forall & \ text {นกฮูก: allValues​​From} \ \ \ end {align} \)


\ (\ mathcal {ALC} \) + บทบาทผกผัน

การตั้งชื่อ: \ (\ mathcal {ALCI} \)

บทบาทสามารถ

  • ชื่อบทบาท \ (r \) หรือ
  • บทบาทผกผัน \ (r ^ - \)

ความหมายของบทบาทที่ตรงกันข้ามถูกกำหนดโดย

\[ (r^-)^\mathcal{I} = \{(y,x) | (x,y) \in r^\mathcal{I} \}\]

นกฮูกสร้าง: นกฮูก: inverseOf

\ (\ mathcal {ALC} \) Hierarchy บทบาท +

การตั้งชื่อ: \ (\ mathcal {ALCH} \)

สำหรับบทบาทของ \ (R, S \)

  • ความจริงการรวมบทบาท (RIA) ที่ชี้แนะโดย \ (r \ sqsubseteq s \)
  • \ (r \ equiv s \) เป็นคำย่อของ \ (r \ sqsubseteq s \) และ \ (s \ sqsubseteq r \)

การตีความ \ (\ mathcal {I} \) entails \ (r \ sqsubseteq s \) IFF \ (^ r \ mathcal {I} \ subseteq S ^ \ mathcal {I} \)

นกฮูกสร้าง: rdfs: subPropertyOf

\ (\ mathcal {ALC} \) + กริยาบทบาท

การตั้งชื่อ: \ (\ mathcal {ALC} \) + กริยา = \ (\ mathcal {S} \)

สำหรับบทบาท \ (r \)

  • ความจริงกริยาคือแสดงโดย \ (\ text {} ทรานส์ (R) \)

การตีความ \ (\ mathcal {I} \) entails \ (\ text {} ทรานส์ (R) \) IFF

\[(x,y) \in r^\mathcal{I} \wedge (y,z) \in r^\mathcal{I} \rightarrow (x,z) \in r^\mathcal{I}.\]

นกฮูกสร้าง: นกฮูก: TransitiveProperty

\ (\ mathcal {ALC} \) + บทบาทการทำงาน

การตั้งชื่อ: \ (\ mathcal {ALCF} \)

สำหรับบทบาท \ (r \)

  • ความจริงการทำงานคือแสดงโดย \ (\ text {} Func (R) \)

การตีความ \ (\ mathcal {I} \) entails \ (\ text {} Func (R) \) IFF

\[(x,y) \in r^\mathcal{I} \wedge (x,z) \in r^\mathcal{I} \rightarrow y=z.\]

นกฮูกสร้าง: นกฮูก: FunctionalProperty

บทบาทที่เรียบง่ายเมื่อเทียบกับคอมเพล็กซ์

ปล่อย \ (\ mathcal {R} \) เป็นลำดับชั้นของบทบาทและปล่อยให้ \ (\ sqsubseteq ^ {*} _ {\ mathcal {R}} \) จะปิดสะท้อนและ transitive ของ

  • บทบาท \ (r \) มีความซับซ้อน WRT \ (\ mathcal {R} \) ถ้ามีบทบาท \ (s \) นั้น \ (\ text {} ทรานส์ (s) \ in \ mathcal {R} \ ) และ \ (s \ sqsubseteq ^ {*} _ {\ mathcal {R}} r \)
  • มิฉะนั้นบทบาท \ (r \) เป็นเรื่องง่าย

ตัวอย่าง:

\[\mathcal{R}=\{ u \sqsubseteq r , r \sqsubseteq s , s \sqsubseteq t , q \sqsubseteq t , \text{Trans}(r) \}\]

คอมเพล็กซ์: \ (R, S, \ t)

ง่าย: \ (U, Q \)

    \ (\ mathcal {ALC} \) + ข้อ จำกัด ของจำนวนสุทธิต่อหุ้น

    การตั้งชื่อ: \ (\ mathcal {ALCN} \)

    สำหรับบทบาทที่เรียบง่าย \ (r \) และจำนวนธรรมชาติ \ (\ n), ข้อ จำกัด จำนวน \ (\ geq nr \ leq nr = nr \) เป็นแนวคิดซึ่งความหมายถูกกำหนดให้เป็น

    \ (\ begin {align} (\ geq nr) ^ \ mathcal {I} = \ {x \ in \ Delta ^ \ mathcal {I} | \ # \ {y \ in \ Delta ^ \ mathcal {I} | (x, y) \ in R ^ \ mathcal {I} \} \ geq n \} \ \ (\ leq nr) ^ \ mathcal {I} = \ {x \ in \ Delta ^ \ mathcal {I} | \ # \ {y \ in \ Delta ^ \ mathcal {I} | (x, y) \ in R ^ \ mathcal {I} \} \ leq n \} \ \ (= nr) ^ \ mathcal {I} & = \ {x \ in \ Delta ^ \ mathcal {I} | \ # \ {y \ in \ Delta ^ \ mathcal {I} | (x, y) \ in R ^ \ mathcal {I} \} = n \ n } \ \ \ end {align} \)

    นกฮูกสร้าง:

    \ (\ begin {align} \ geq nr = \ text {นกฮูก: minCardinality} \ \ \ leq nr = \ text {นกฮูก: maxCardinality} \ \ = nr = \ text {นกฮูก: exactCardinality} \ end {align } \)

    \ (\ mathcal {ALC} \) nominals +

    การตั้งชื่อ: \ (\ mathcal {เข็ดหลาบ} \)

    ปล่อย \ (a_1, \ ldots, a_n \) บุคคลที่จะ ระบุ \ (\ {a_1, \ ldots, a_n \} \) เป็นแนวคิดซึ่งความหมายถูกกำหนดให้เป็น

    \ ((\ {a_1, \ ldots, a_n \}) ^ \ mathcal {I} = \ {a_1 ^ \ mathcal {I}, \ ldots, a_n ^ \ mathcal {I} \} \)

    นกฮูกสร้าง: นกฮูก: oneof

    เหตุผลตรรกะ

    สรุปเหตุผล

    • เริ่มต้นด้วยการยืนยันจากกฎทั่วไปและเงินที่ได้จากที่นั่นไปยังข้อสรุปที่เฉพาะเจาะจงรับประกัน
    • "จากกฎทั่วไปกับงานเฉพาะ"

    เหตุผลอุปนัย

    • เริ่มต้นด้วยการสังเกตที่มีความเฉพาะเจาะจงและ จำกัด อยู่ในขอบเขตและวิธีการที่จะได้ข้อสรุปทั่วไปที่อาจเป็นไปได้ แต่ไม่แน่ใจในที่มีแสงจากหลักฐานสะสม
    • "จากที่เฉพาะเจาะจงในการทั่วไป"

    เหตุผล Abductive

    • เริ่มต้นด้วยชุดที่ไม่สมบูรณ์ของการสังเกตและวิธีการที่จะอธิบายล้วนเป็นไปได้สำหรับชุด

    เหตุผลในรายละเอียด Logics (1)

    เหตุผลใน Logics รายละเอียด (2)

    ปล่อย \ (\ mathcal {I} \) จะตีความ \ (\ mathcal {T} \) จะ TBox, \ (\ mathcal {} \) จะ ABox และ \ (\ mathcal {K} = (\ mathcal {T} \ mathcal {}) \ base.We ความรู้ที่ได้รับ) กล่าวว่า

    • \ (\ mathcal {I} \) เป็นรูปแบบสำหรับ \ (\ mathcal {T} \), IFF \ (\ mathcal {I} \ models \ alpha \) สำหรับความจริงทุก \ (\ alpha \ in \ mathcal {T } \) เขียน \ (\ mathcal {I} \ models \ mathcal {T} \)
    • \ (\ mathcal {I} \) เป็นรูปแบบสำหรับ \ (\ mathcal {} \), IFF \ (\ mathcal {I} \ models \ alpha \) สำหรับความจริงทุก \ (\ alpha \ in \ mathcal { } \) เขียน \ (\ mathcal {I} \ models \ mathcal {} \)
    • \ (\ mathcal {I} \) เป็นรูปแบบสำหรับ \ (\ mathcal {K} \), IFF \ (\ mathcal {I} \ \ models mathcal {T} \) และ \ (\ mathcal {I} \ models \ mathcal {} \)
    • ความจริง \ (\ alpha \) จะถูกยกให้โดย \ (\ mathcal {K} \) เขียน \ (\ mathcal {K} \ รุ่น \ alpha \), IFF ทุกรุ่น \ (\ mathcal {I} \) จาก \ (\ mathcal {K} \) เป็นรูปแบบสำหรับ \ (\ alpha \)

    บริการการใช้เหตุผล (1)

    Satisfiability แนวคิด

    \[ \mathcal{K} \not \models C \equiv \bot \]

    ปัญหาของการตรวจสอบว่า \ (C \) พอใจ WRT \ (\ mathcal {K} \) นั่นคือไม่ว่าจะมีรูปแบบที่มีอยู่ \ (\ mathcal {I} \) ของ \ (\ mathcal {K} \) ดังกล่าวว่า \ (C ^ {\ mathcal {I}} \ NEQ \ emptyset \)

    subsumption

    \[ \mathcal{K} \models C \sqsubseteq D\]

    ปัญหาของการตรวจสอบว่า \ (C \) จะวิทย \ (D \) WRT \ (\ mathcal {K} \) นั่นคือไม่ว่าจะเป็น \ (C ^ {\ mathcal {I}} \ subseteq D ^ {\ mathcal { I}} \) ในทุกรุ่น \ (\ mathcal {I} \) ของ \ (\ mathcal {K} \)

    Satisfiability (Consistency)

    \[ \mathcal{K} \not \models \top \sqsubseteq \bot\]

    ปัญหาของการตรวจสอบว่า \ (\ mathcal {K} \) มีความสอดคล้องคือไม่ว่าจะมีรูปแบบ

    บริการการใช้เหตุผล (2)

    การตรวจสอบเช่น

    \[ \mathcal{K} \models C(a)\]

    ปัญหาของการตรวจสอบว่าการยืนยัน \ (C () \) เป็นที่พอใจ WRT \ (\ mathcal {K} \) นั่นคือไม่ว่าจะเป็น \ (^ {\ mathcal {I}} \ in C ^ {\ mathcal {I }} \) ในทุกรุ่น \ (\ mathcal {I} \) ของ \ (\ mathcal {K} \)

    การซ่อมแซม

    \[\{a | \mathcal{K} \models C(a)\}\]

    ปัญหาการหาบุคคลทั้งหมด \ (\) ซึ่งเป็นแนวคิด \ (C \) WRT \ (K \) นั่นคือหาทั้งหมด \ (\) สำหรับให้ \ (C \) นั้น \ (^ { \ mathcal {I}} \ in C ^ {\ mathcal {I}} \) ในทุกรุ่น \ (\ mathcal {I} \) ของ \ (\ mathcal {K} \)

    ความเข้าใจ

    \[\{C | \mathcal{K} \models C(a)\}\]

    ปัญหาการหาชื่อชั้นเรียนทั้งหมด \ (C \) ซึ่ง indivdual \ (\) เป็น wrt \ (K \) นั่นคือหาทั้งหมด \ (C \) สำหรับให้ \ (\) นั้น \ ( ^ {\ mathcal {I}} \ in C ^ {\ mathcal {I}} \) ในทุกรุ่น \ (\ mathcal {I} \) ของ \ (\ mathcal {K} \)

    บริการการใช้เหตุผล (3)

    เราสามารถลดการบริการทั้งหมดเพื่อตรวจสอบ satisfiability:

    Satisfiability แนวคิด

    \ (K \ ไม่ได้ \ รุ่น C \ equiv \ bot \ longleftrightarrow \) มีอยู่ \ (x \) นั้น \ (K \ ถ้วย \ {C (x) \} \) พอใจ

    subsumption

    \ (K \ รุ่น C \ sqsubseteq D \ longleftrightarrow K \ ถ้วย \ {C \ sqcap \ NEG D (x) \} \) เป็น unsatisfiable

    Instance ตรวจสอบ

    \ (K \ รุ่น C () \ longleftrightarrow K \ ถ้วย \ {\ NEG C () \} \) เป็น unsatisfiable

    อัลกอริทึม Tableau

    วิธีที่เราสามารถ proove satisfiability ของแนวคิด?

    (จำเอาไว้: แนวคิดคือพอใจถ้ามีรูปแบบ \ (\ mathcal {I} \) satisfiying มัน.)

    เราจำเป็นต้องมีขั้นตอนการตัดสินใจที่สร้างสรรค์สำหรับรุ่นที่สร้าง

    \ (\ longrightarrow \) อัลกอริทึม Tableau

    ขั้นตอนการพิสูจน์:

    • เปลี่ยนแนวคิดให้เป็นรูปแบบปกติการปฏิเสธ (NNF)
    • ใช้กฎความสำเร็จในการสั่งซื้อโดยพลการเป็นเวลานานที่สุด
    • แนวคิดพอใจถ้าและเพียงถ้าฉากปะทะกันฟรีสามารถจะได้มาซึ่งการปกครองเสร็จสิ้นไม่สามารถใช้ได้

    ภาพนิ่งใหม่

    TBox \ (\ mathcal {T} \):

    \ (\ begin {align} \ text {Man} \ equiv \ ข้อความ NEG \ {ผู้หญิง} \ ข้อความ sqcap \ {คน} \ \ \ text {ผู้หญิง} & \ ข้อความ sqsubseteq \ {คน} \ \ \ text {แม่ } \ equiv \ text {ผู้หญิง} \ sqcap \ exists \ text {hasChild}. \ \ top \ \ end {align} \)

    ABox \ (\ mathcal {} \):

    \ (\ begin {align} \ text {แมน (สตีเฟน)} \ \ \ ข้อความ NEG \ {Man (MONICA)} \ \ \ text {ผู้หญิง (เจสสิก้า)} \ \ \ text {hasChild (สตีเฟน, เจสสิก้า)} \ \ \ end {align} \)

    ปล่อย \ (\ mathcal {I} \) จะตีความด้วย:

    \ (\ begin {align} \ text {Man} ^ \ mathcal {I} = \ {สตีเฟ่น \} \ \ \ text {ผู้หญิง} ^ \ mathcal {I} = \ {เจสสิก้า MONICA \} \ \ \ ข้อความแม่ {} ^ \ mathcal {I} = \ {MONICA \} \ \ \ text {คน} ^ \ mathcal {I} = \ {เจสสิก้า, โมนิก้า, สตีเฟ่น \} \ \ \ text {hasChild} ^ \ mathcal {I} = \ {\ langle MONICA สตีเฟ่น \ rangle \ langle สตีเฟน, เจสสิก้า \ rangle \} \ \ \ end {align} \)

    แล้วก็ถือว่า

    \ (\ mathcal {I} \ models \ mathcal {T} \ text {และ} \ mathcal {I} \ models \ mathcal {} \)

    ปฏิเสธรูปแบบปกติ

    แนวความคิดที่อยู่ในรูปแบบปกติการปฏิเสธ (NNF) ถ้าปรากฏทั้งหมดใน negations มันอยู่ในหน้าของแนวคิดอะตอม

    ทุกคน \ (\ mathcal {ALC} \) แนวคิดสามารถเปลี่ยนเป็นหนึ่งเทียบเท่าใน NNF ใช้กฎดังต่อไปนี้:

    \[ \begin{aligned} NNF(C) &= C, \text{ if } C \text{ is atomic }\\ NNF(\neg C) &= \neg C, \text{ if } C \text{ is atomic}\\ NNF(\neg \neg C) &= NNF(C) \\ NNF(C \sqcup D) &= NNF(C) \sqcup NNF(D) \\ NNF(C \sqcap D) &= NNF(C) \sqcap NNF(D) \\ NNF(\neg(C \sqcup D)) &= NNF(\neg C) \sqcap NNF(\neg D) \\ NNF(\neg(C \sqcap D)) &= NNF(\neg C) \sqcup NNF(\neg D) \\ NNF(\forall R.C) &= \forall R.NNF(C) \\ NNF(\exists R.C) &= \exists R.NNF(C) \\ NNF(\neg \forall R.C) &= \exists R.NNF(\neg C) \\ NNF(\neg \exists R.C) &= \forall R.NNF(\neg C) \\ \end{aligned} \]

    ปฏิเสธแบบปกติ - ตัวอย่าง

    เปลี่ยนแนวคิด

    \[\neg (\neg (A \sqcup \neg B) \sqcap \neg C))\]

    ถึงแนวคิดเทียบเท่าในรูปแบบปกติปฏิเสธ:

    \[ \begin{aligned} &NNF(\neg (\neg (A \sqcup \neg B) \sqcap \neg C))\\ &= NNF(\neg \neg (A \sqcup \neg B)) \sqcup NNF(\neg \neg C)\\ &= NNF(A \sqcup \neg B) \sqcup NNF(C)\\ &= NNF(A \sqcup \neg B) \sqcup C\\ &= NNF(A) \sqcup NNF(\neg B) \sqcup C\\ &= A \sqcup \neg B \sqcup C\\ \end{aligned} \]

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) satisfiability แนวคิด

    ฉาก (กราฟเสร็จ) สำหรับ \ (\ mathcal {ALC} \) เป็นแนวคิดที่มุ่งเน้นการติดป้ายกราฟ \ (G = \ langle V, E, L \ rangle \) ซึ่งแต่ละโหนด \ (x \ in V \) จะมีป้ายกับชุด \ (L (x) \) จากแนวคิดและขอบแต่ละ \ (\ langle x, y rangle \ \ in E \) จะถูกกำกับด้วยชุด \ (L (\ langle x, y rangle \ \ )) บทบาทของ

    กราฟเสร็จ \ (G \)

    • มีการปะทะกันถ้า \ (\ {\ NEG \} \ in L (x) \) สำหรับแนวคิดอะตอมบาง \ (\) หรือ \ (\ bot \ in L (x) \) หรือ \ (\ NEG \ \ top ใน L (x) \)
    • เสร็จสมบูรณ์แล้วถ้ากฎเสร็จไม่สามารถนำมาใช้กับมัน

    กฎระเบียบสำหรับการเสร็จ \ (\ mathcal {ALC} \) satisfiability แนวคิด

    \ (\ sqcap \) กฎ ถ้า \ (C \ sqcap D \ in L (V), \ text {บาง} \ v ใน V \ text {และ} \ {C, D \} \ ไม่ได้ \ subseteq L (V) \)
    แล้วก็ \ (L (V) = L (V) \ ถ้วย \ {C, D \} \)
    \ (\ sqcup \) กฎ ถ้า \ (C \ sqcup D \ in L (V), \ text {บาง} \ v ใน V \ text {และ} \ {C, D \} \ ฝา L (V) = \ emptyset \)
    แล้วก็ \ (\ text {เลือก} X \ in \ {C, D \} \ text {} และปล่อยให้ L (V) = L (V) \ ถ้วย \ {X \} \)
    \ (อยู่แล้ว \ \) กฎ ถ้า \ (\ exists RC \ in L (V), \ text {บาง} \ v ใน V, \ text {และไม่มี} r \ text {สืบ-} \) \ (v '\ text {} ของวี \ text {เช่นนั้น} C \ in L (V) \)
    แล้วก็ \ (V = V \ ถ้วย \ {v '\}, E = E \ ถ้วย \ {\ langle V, v' \ rangle \}, L (v ') = \ {C \} \) \ ( \ text {} และ L (\ langle วี 'rangle \ = \ {r \} \) \ (\ text {สำหรับจุดยอดใหม่} V V)' \)
    \ (\ forall \) กฎ ถ้า \ (V, v '\ in V, v' \ text {เป็น} r \ text {ตัวตายตัวแทนของ} V, \ forall RC \ in L (V) \ text {และ} C \ ไม่ได้ \ in L (v ' ) \)
    แล้วก็ \ (L (v ') = l (v') \ ถ้วย {C} \)

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) satisfiablity แนวคิด - ตัวอย่างที่ 1

    เราตรวจสอบว่า \ (C = (A \ sqcap \ NEG) \ sqcup B \) พอใจ มันมีอยู่ใน NNF ดังนั้นเราโดยตรงสามารถใช้อัลกอริทึมฉากไป

    \[(A \sqcap \neg A) \sqcup B.\]

    กฎเฉพาะคือ \ (\ sqcup \ ข้อความ {กฎ} \) เรามีสองเป็นไปได้ ประการแรกเราสามารถลอง

    \[L(x)=\{C, A \sqcap \neg A\}.\]

    แล้วเราสามารถใช้ \ (\ sqcap \ ข้อความ {กฎ} \) และได้รับ

    \[L(x)=\{C, A \sqcap \neg A, A, \neg A\}.\]

    เราได้รับการปะทะกันจึงเลือกนี้ไม่ประสบความสำเร็จ ประการที่สองเราสามารถลอง

    \[L(x)=\{C, B\}.\]

    ไม่มีกฎมากขึ้นมีผลบังคับใช้และเราได้รับการปะทะกันไม่ ดังนั้น \ ((A \ sqcap \ NEG) \ sqcup B \) พอใจ

    รูปแบบ \ (\ mathcal {I} \) satisfiying มันจะได้รับโดย

    \[\Delta^\mathcal{I}=\{x\}, A^\mathcal{I}=\emptyset, B^\mathcal{I}=\{x\}.\]

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) satisfiablity แนวคิด - ตัวอย่างที่ 2

    เราตรวจสอบว่า \ (C = \ sqcap \ exists rB \ sqcap \ forall r. \ NEG B \) พอใจ มันมีอยู่ใน NNF ดังนั้นเราโดยตรงสามารถใช้อัลกอริทึมฉากไป

    \[C=A \sqcap \exists r.B \sqcap \forall r.\neg B.\]

    การประยุกต์ใช้ \ (\ sqcap \ ข้อความ {กฎ} \) ให้

    \[L(x)=\{C, A, \exists r.B, \forall r.\neg B\}.\]

    การประยุกต์ใช้ \ (\ text อยู่ \ {กฎ} \) ให้

    \ (\ begin {align *} L (x) = \ {C, A, \ exists rB, \ forall r. \ NEG B \} \ \ L (y) = \ {B \} \ \ ลิตร ( \ langle x, y rangle \) = \ {r \} \ end {align *} \)

    การประยุกต์ใช้ \ (\ forall \ ข้อความ {กฎ} \) ให้

    \ (\ begin {ชิด} L (x) = \ {C, A, \ exists rB, \ forall r. \ NEG B \} \ \ L (y) = \ {B, \ NEG B \} \ \ L (\ langle x, y rangle \) = \ {r \} \ end {ชิด} \)

    เราได้รับการปะทะกันและไม่มีทางเลือกอื่น ๆ ที่เป็นไปได้ ดังนั้น \ (\ sqcap \ exists rB \ sqcap \ forall r. \ NEG B \) เป็น unsatisfiable และมีรูปแบบที่มีอยู่ไม่มี

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) TBoxes

    เราขยายฉากอัลกอริทึมในการตรวจสอบ satisfiability ของ \ (\ mathcal {ALC} \) TBoxes

    • \ (\ mathcal {ALC} \) TBox มีหลักการอย่างเดียว (GCIs) ของฟอร์ม \ (C \ sqsubseteq D \) (หมายเหตุที่สัจพจน์ของฟอร์ม \ (C \ equiv D \) สามารถเขียนใหม่เป็น \ (C \ sqsubseteq D \) และ \ (D \ sqsubseteq C \))
    • GCI ทุกเทียบเท่ากับ \ (\ \ top sqsubseteq \ NEG C \ sqcup D \)

    เราสามารถ internalize TBox ทั้งหมดเป็นความจริงเดียว:

    \[\mathcal{T}=\{C_i \sqsubseteq D_i | 1 \leq i \leq n\}\]

    เทียบเท่ากับ

    \[ \top \sqsubseteq \underset{1 \leq i \leq n}{{\LARGE\sqcap}} \neg C_i \sqcup D_i \]

    ปล่อย \ (C_ \ mathcal {T} \) เป็นแนวความคิดทางด้านขวาของ GCI แล้วกฎเพิ่มเติมคือ

    \ (\ mathcal {T} \) กฎ ถ้า \ (C_ \ mathcal {T} \, \, \ ไม่ได้ \ in L (V), \ text {บาง} \ v ใน V \)
    แล้วก็ \ (L (V) = L (V) \ ถ้วย \ {C_ \ mathcal {T} \} \)

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) TBoxes - ตัวอย่าง

    สมมติว่าเรามี TBox \ (\ mathcal {T} = \ {\ sqsubseteq \ exists rA \} \) และต้องการที่จะตรวจสอบว่าแนวคิด \ (\) พอใจ เราเริ่มต้นด้วย

    \[L(x)=\{A\}\]

    กฎเฉพาะคือ \ (\ mathcal {T} - \ text {กฎ} \) ทำให้เราได้รับ

    \[L(x)=\{A, \neg A \sqcup \exists r.A\}\]

    หลังจากใช้ \ (\ sqcup \ ข้อความ {กฎ} \) เป็นตัวเลือกแรกที่นำไปสู่​​การปะทะกันดังนั้นเราจะใช้ส่วนที่สองของ disjuction และได้รับ

    \[L(x)=\{A, \neg A \sqcup \exists r.A, \exists r.A\}\]

    เราสามารถใช้ \ (\ exists \ ข้อความ {กฎ} \) และได้รับ

    \ (\ begin {align *} L (x) = \ {\ NEG \ sqcup \ exists rA, \ exists rA \} \ \ L (y) = \ {\} \ end {align * } \)

    ณ จุดนี้เราสามารถเรียกใช้ขั้นตอนเดียวกันบน \ (y \) ดังนั้นอัลกอริทึมจะไม่ยุติ

    การแก้ไข: เราต้องการที่จะค้นพบวงจร \ (\ longrightarrow \) ปิดกั้น

    การปิดกั้นสำหรับ \ (\ mathcal {ALC} \)

    เป้าหมาย: ตรวจสอบให้แน่ใจสิ้นสุดของอัลกอริทึมฉาก
    การแก้ไข: ตรวจสอบรอบที่อาจเกิดขึ้นเนื่องจากการประยุกต์ใช้ \ (\ mathcal {T} - \ text {กฎ} \)
    ผล: กราฟเสร็จอยู่เสมอแน่นอน

    การปิดกั้น:

    โหนด \ (v '\ in V \) ถูกบล็อกโดยตรงโดยโหนด \ (\ v ใน V \) ถ้า

    1. \ (\ v) เป็นบรรพบุรุษของ \ (v '\)
    2. \ (L (v ') \ subseteq L (V) \)
    3. ไม่มีโหนดบล็อกโดยตรง \ (V ^ {''} \) นั้น \ (V'' \) เป็นบรรพบุรุษของ \ (\ v)

    โหนด \ (v '\) ถูกบล็อคถ้าอย่างใดอย่างหนึ่ง

    1. \ (v '\) ถูกบล็อกโดยตรงหรือ
    2. มีโหนดบล็อกโดยตรง \ (\ v) ซึ่งเป็นบรรพบุรุษของ \ (v '\)

    อัลกอริทึมสำหรับ Tableau \ (\ mathcal {ALC} \) TBoxes ด้วยการปิดกั้น - ตัวอย่าง

    สมมติว่าเรามี TBox \ (\ mathcal {T} = \ {\ sqsubseteq \ exists rA \} \) และต้องการที่จะตรวจสอบว่าแนวคิด \ (\) พอใจ

    เราได้รับฉากปะทะกันฟรี

    \ (\ begin {align *} L (x) = \ {\ NEG \ sqcup \ exists rA, \ exists rA \} \ \ L (y) = \ {\ NEG \ sqcup \ อยู่ rA, \ exists rA \} \ end {align *} \)

    ประเด็น \ (y \) ถูกบล็อกโดยตรงโดย \ (x \)

    เราจะได้รับแบบ จำกัด โดยคำนึงถึงว่า

    • โหนดที่ถูกปิดกั้นไม่ได้เป็นตัวแทนองค์ประกอบในรูปแบบ
    • ขอบจากโหนด \ (\ v) ไปยังโหนดบล็อกโดยตรง \ (v '\) จะถูกแสดงในรูปแบบที่เป็น "ขอบ" จาก \ (\ v) ไปยังโหนดที่บล็อกโดยตรง \ (V' \)

    สำหรับตัวอย่างของเราที่เราได้รับ

    \[ \Delta^\mathcal{I}=\{x\}, A^\mathcal{I}=\{x\}, r^\mathcal{I}=\{\langle x,x \rangle\} \]

    ข้อมูลอย่างย่อ

    • ความหมายของนกฮูกจะขึ้นอยู่กับรายละเอียด Logics
    • Logics รายละเอียดเป็นเศษเล็กเศษน้อย decidable ของลอจิกสั่งซื้อครั้งแรก
    • สรุปเหตุผลในนกฮูกเป็นไปได้
    • อัลกอริทึมฉากที่เป็นหนึ่งในวิธีการที่พบมากที่สุดสำหรับเหตุผลที่นกฮูก