Direct Proof

^25847a

• Used for proving an "if p then q" (conditional sentence) sentence is true.
• หรือถ้าได้เป็นประโยคมา ก็ลองแปลงให้เป็น Conditional sentence ก่อน
• Its application to prove that a “for all” statement is true.
  • A “for all” statement can always be rewritten as an “if-then” statement.

Process of Direct Proof

• First line → Assume that p is true.
• (IN-BETWEEN) USE DEFINITIONS AND OUR BACKGROUND KNOWLEDGE
• Last line → q is true

Proof by Contradiction (Indirect Proof)

• Used for proving an "if p then q" (conditional sentence) sentence is true. — เหมือนกับ Direct Proof

Process of Indirect Proof

• To prove that “if p, then q” is true.
  • Assume that “p is true” and “$\neg$q is true (q is false)”
  • and try to derive a “contradiction”
• Always start by 2 assumptions!!

Proof by Contrapositive

• (A special case of proof by contradiction)
• To prove that “if p, then q” is true.
  • เวลาใช้อันนี้จะ Proof “if $\neg$q, the $\neg$p” instead.
  • พอตั้งเสร็จก็ Proof ด้วย Direct Proof ต่อได้เลย

Deductive Reasoning

• The process of drawing a conclusion from a sequence of propositions
• The argument is valid if an only if:
  • if all the premises are true, then the conclusion must be true;
    otherwise, the argument is invalid.

วิธีทำง่าย ๆ เลยก็คือเอา Premises กับ Conclusion ที่ให้ มาเขียน Truth Table แล้วดูในช่องที่ Premises ทุกตัวเป็น True, แล้วเหมือนกันในทุกช่อง Conclusion ก็ต้องเป็น True ถ้ามีอันใดอันนึงเป็น False ขึ้นมา ถือว่า Invalid ทันที

• แต่ Method นี้จะทำงานได้ดีตอนเฉพาะ Variable น้อย ๆ คือถ้าเยอะ Size ของ Truth Table มันก็ grows exponentially ใช่มะ ๆ

Resolution Proofs

Terms

• Atom (Atomic Formula)
  • No logical connective
  • Ex: p, q, r
• Literal
  • An atom or the negation of an atom
  • Ex: p, $\neg$p, q, $\neg$q, r, $\neg$r
• Clause
  • A disjunction using OR only of one or more literals
  • Ex: p $\lor$ q, $\neg$p $\lor$ q $\lor$ r, p, $\neg$p ✅
  • Ex: p $\rightarrow$ q ❌
    The “resolution” rule works with “clauses” only!!

Process of Resolution Proof

^RPPS

• ทำให้ Premises & Conclusion ทุกตัวเป็น Clauses ก่อน
  • If a given sentence is NOT in the form of a clause → Convert to a clause or;
  • หรือเป็น A conjunction of clauses ก็ได้ ก็คือเชื่อมด้วย $\land$ (and) แล้วมันจะแตกออกมาเป็น 2 premises ได้นะ
  • ก็คือถ้าพูดจริง ๆ แล้วก็เหมือนว่า Premises ทุกตัว เชื่อมด้วย and อยู่แล้ว
• แล้วก็เอาแต่ละ premises มาจับรวมกัน พยายามให้ได้ Conclusion โดยสมมติว่า
  • p จับกับ $\neg$p $\lor$ q จะเหลือแค่ q ก็คือเหมือนถูกตัดออกไปนั่นเอง
  • เราไม่จำเป็นต้องใช้ทุก Premises ขอให้ได้ Conclusion แค่นั้นก็พอแล้ว

Mathematical Induction

• Use to show that a statement $S(n)$ is true;

Process

• มาวิธีการทำเลยดีกว่าจะได้ง่าย ๆ
• ต้องแบ่งออกเป็นสองฝั่ง
  1. Basis Step
  2. Induction Step
• โดยต้องทำ Basis Step ก่อนเป็นอย่างแรก เพราะง่ายที่สุด เหมือนได้คะแนนฟรี โดยการแทนตัวเลขลงไป โดยตัวเลขก็ต้องตรงกับ Domain ที่โจทย์กำหนดด้วยนะ
• ต่อมาก็เขียนใน Induction Step
  • Assume that $S(n)$ is true (induction hypothesis) – เราจะเปรียบเสมือนว่ามันคือ Tool (Helper)
  • We want to prive that $S(n+1)$ is true. – อันนี้คือ Task (สิ่งที่เราต้องทำ)
• ละเราก็เขียนลง Memo เล็ก ๆ โดยการแทนตรง ๆ ไปเลย ว่า $S(n+1)$ ได้เป็นอะไร แล้วก็เก็บไว้
• เวลา Prove ก็เริ่มจาก $S(n+1)$ แล้วก็ Prove อีกฝั่ง หรือพยายามจัดรูปอะไรก็แล้วแต่ ไม่มีวิธีตายตัว แต่พยายามจัดให้ได้รูปก่อน แล้วมันจะแทนอะไรบางอย่างได้