Proofs

• Proof of sentence Sn in knowledge base KB

  • Sentence sequence S1, S2, …, Sn such that each Si is
    • A sentence in KB, or
    • Inferable from sentences occurring previously in the proof

• Standard proof techniques

  • Deduction Theorem
    • If KB ? S1 |– S2, then KB |– (implies S1 S2)
    • To prove (implies S1 S2):
      • Assume S1. Derive S2.
    • Refutation Theorem
      • If KB ? (not S) |– false, then KB |– S
      • To prove S:
        • Assume (not S). Prove false.

Previous slide

Next slide

Back to first slide

View graphic version