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 |– (=> S1 S2)
    • To prove “(=> S1 S2)”:
      Assume S1. Prove 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