คณิตศาสตร์ไม่ต่อเนื่อง - ตรรกศาสตร์เชิงโจทย์

กฎของตรรกะทางคณิตศาสตร์ระบุวิธีการให้เหตุผลข้อความทางคณิตศาสตร์ อริสโตเติลนักปรัชญาชาวกรีกเป็นผู้บุกเบิกการหาเหตุผลเชิงตรรกะ การให้เหตุผลเชิงตรรกะเป็นพื้นฐานทางทฤษฎีสำหรับคณิตศาสตร์หลาย ๆ ด้านและตามมาด้วยวิทยาศาสตร์คอมพิวเตอร์ มีการประยุกต์ใช้งานจริงมากมายในวิทยาการคอมพิวเตอร์เช่นการออกแบบเครื่องคอมพิวเตอร์ปัญญาประดิษฐ์ความหมายของโครงสร้างข้อมูลสำหรับภาษาโปรแกรมเป็นต้น

Propositional Logicเกี่ยวข้องกับข้อความที่สามารถกำหนดค่าความจริง "จริง" และ "เท็จ" ได้ จุดประสงค์คือเพื่อวิเคราะห์ข้อความเหล่านี้ไม่ว่าจะเป็นรายบุคคลหรือแบบประกอบ

Prepositional Logic - คำจำกัดความ

ประพจน์คือชุดของข้อความประกาศที่มีทั้งค่าความจริง "จริง" หรือค่าความจริง "เท็จ" ประพจน์ประกอบด้วยตัวแปรเชิงประพจน์และตัวเชื่อมเราแสดงตัวแปรเชิงประพจน์ด้วยตัวพิมพ์ใหญ่ (A, B, ฯลฯ ) Connectives เชื่อมต่อตัวแปรเชิงประพจน์

ตัวอย่างบางส่วนของข้อเสนอมีให้ด้านล่าง -

  • "มนุษย์เป็นมนุษย์" จะส่งกลับค่าความจริง "TRUE"
  • "12 + 9 = 3 - 2" จะส่งกลับค่าความจริง "FALSE"

ต่อไปนี้ไม่ใช่ข้อเสนอ -

  • "A น้อยกว่า 2" เป็นเพราะถ้าเราไม่ให้ค่าเฉพาะของ A เราไม่สามารถบอกได้ว่าข้อความนั้นเป็นจริงหรือเท็จ

Connectives

ในตรรกะเชิงประพจน์โดยทั่วไปเราใช้การเชื่อมต่อห้าแบบซึ่ง ได้แก่

  • หรือ ($ \ lor $)

  • และ ($ \ land $)

  • การปฏิเสธ / ไม่ ($ \ lnot $)

  • นัย / if-then ($ \ rightarrow $)

  • ถ้าและเฉพาะในกรณีที่ ($ \ Leftrightarrow $)

OR ($\lor$) - การดำเนินการ OR ของสองประพจน์ A และ B (เขียนเป็น $ A \ lor B $) เป็นจริงถ้าตัวแปรประพจน์ A หรือ B เป็นจริงอย่างน้อยที่สุด

ตารางความจริงมีดังนี้ -

ก∨ข
จริง จริง จริง
จริง เท็จ จริง
เท็จ จริง จริง
เท็จ เท็จ เท็จ

AND ($\land$) - การดำเนินการ AND ของสองประพจน์ A และ B (เขียนเป็น $ A \ land B $) เป็นจริงถ้าทั้งตัวแปรประพจน์ A และ B เป็นจริง

ตารางความจริงมีดังนี้ -

ก∧ข
จริง จริง จริง
จริง เท็จ เท็จ
เท็จ จริง เท็จ
เท็จ เท็จ เท็จ

Negation ($\lnot$) - การปฏิเสธของประพจน์ A (เขียนเป็น $ \ lnot A $) เป็นเท็จเมื่อ A เป็นจริงและเป็นจริงเมื่อ A เป็นเท็จ

ตารางความจริงมีดังนี้ -

¬ก
จริง เท็จ
เท็จ จริง

Implication / if-then ($\rightarrow$)- นัย $ A \ rightarrow B $ คือประพจน์“ ถ้า A แล้ว B” เป็นเท็จถ้า A เป็นจริงและ B เป็นเท็จ กรณีที่เหลือเป็นเรื่องจริง

ตารางความจริงมีดังนี้ -

ก→ข
จริง จริง จริง
จริง เท็จ เท็จ
เท็จ จริง จริง
เท็จ เท็จ จริง

If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ คือการเชื่อมต่อเชิงตรรกะแบบสองเงื่อนไขซึ่งเป็นจริงเมื่อ p และ q เหมือนกันกล่าวคือทั้งสองเป็นเท็จหรือทั้งสองอย่างเป็นจริง

ตารางความจริงมีดังนี้ -

ก⇔ข
จริง จริง จริง
จริง เท็จ เท็จ
เท็จ จริง เท็จ
เท็จ เท็จ จริง

Tautologies

Tautology เป็นสูตรที่เป็นจริงเสมอสำหรับทุกค่าของตัวแปรเชิงประพจน์

Example - พิสูจน์ $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ เป็น tautology

ตารางความจริงมีดังนี้ -

ก→ข (A → B) ∧ก [(A → B) ∧ A] → B
จริง จริง จริง จริง จริง
จริง เท็จ เท็จ เท็จ จริง
เท็จ จริง จริง เท็จ จริง
เท็จ เท็จ จริง เท็จ จริง

ดังที่เราเห็นทุกค่าของ $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ คือ "True" มันเป็น tautology

ความขัดแย้ง

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

Example - พิสูจน์ว่า $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ เป็นความขัดแย้ง

ตารางความจริงมีดังนี้ -

ก∨ข ¬ก ¬ข (¬ A) ∧ (¬ B) (A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
จริง จริง จริง เท็จ เท็จ เท็จ เท็จ
จริง เท็จ จริง เท็จ จริง เท็จ เท็จ
เท็จ จริง จริง จริง เท็จ เท็จ เท็จ
เท็จ เท็จ เท็จ จริง จริง จริง เท็จ

ดังที่เราเห็นทุกค่าของ $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ คือ "False" มันเป็นความขัดแย้ง

ฉุกเฉิน

Contingency คือสูตรที่มีทั้งค่าจริงและค่าเท็จสำหรับทุกค่าของตัวแปรเชิงประพจน์

Example - พิสูจน์ $ (A \ lor B) \ land (\ lnot A) $ a contingency

ตารางความจริงมีดังนี้ -

ก∨ข ¬ก (A ∨ B) ∧ (¬ A)
จริง จริง จริง เท็จ เท็จ
จริง เท็จ จริง เท็จ เท็จ
เท็จ จริง จริง จริง จริง
เท็จ เท็จ เท็จ จริง เท็จ

ดังที่เราเห็นทุกค่าของ $ (A \ lor B) \ land (\ lnot A) $ มีทั้ง "True" และ "False" มันเป็นความบังเอิญ

Propositional Equivalences

สองคำสั่ง X และ Y มีความเท่าเทียมกันทางตรรกะหากมีเงื่อนไขสองข้อต่อไปนี้ -

  • ตารางความจริงของแต่ละคำสั่งมีค่าความจริงเหมือนกัน

  • คำสั่ง bi-conditional $ X \ Leftrightarrow Y $ เป็น tautology

Example - พิสูจน์ว่า $ \ lnot (A \ lor B) และ \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ เทียบเท่ากัน

การทดสอบโดยวิธี1 st (ตารางความจริงที่ตรงกัน)

ก∨ข ¬ (A ∨ B) ¬ก ¬ข [(¬ A) ∧ (¬ B)]
จริง จริง จริง เท็จ เท็จ เท็จ เท็จ
จริง เท็จ จริง เท็จ เท็จ จริง เท็จ
เท็จ จริง จริง เท็จ จริง เท็จ เท็จ
เท็จ เท็จ เท็จ จริง จริง จริง จริง

ที่นี่เราจะเห็นค่าความจริงของ $ \ lnot (A \ lor B) และ \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ เหมือนกันดังนั้นงบจึงเทียบเท่ากัน

การทดสอบ 2 ครั้งวิธีการ (Bi-conditionality)

¬ (A ∨ B) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
จริง จริง เท็จ เท็จ จริง
จริง เท็จ เท็จ เท็จ จริง
เท็จ จริง เท็จ เท็จ จริง
เท็จ เท็จ จริง จริง จริง

เนื่องจาก $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ เป็น tautology งบจึงเทียบเท่า

ผกผัน Converse และ Contra-positive

Implication / if-then $ (\ rightarrow) $ เรียกอีกอย่างว่าคำสั่งเงื่อนไข มีสองส่วน -

  • สมมติฐาน, น
  • สรุป q

ดังที่ได้กล่าวไว้ก่อนหน้านี้แสดงเป็น $ p \ rightarrow q $

Example of Conditional Statement-“ ถ้าคุณทำการบ้านคุณจะไม่ถูกลงโทษ” ที่นี่ "คุณทำการบ้าน" คือสมมติฐาน p และ "คุณจะไม่ถูกลงโทษ" คือข้อสรุป q

Inverse- การผกผันของคำสั่งเงื่อนไขคือการปฏิเสธของทั้งสมมติฐานและข้อสรุป ถ้าคำสั่งคือ“ ถ้า p แล้ว q” ค่าผกผันจะเป็น“ ถ้าไม่ใช่ p แล้วไม่ใช่ q” ดังนั้นสิ่งผกผันของ $ p \ rightarrow q $ คือ $ \ lnot p \ rightarrow \ lnot q $

Example - สิ่งที่ตรงกันข้ามของ“ ถ้าคุณทำการบ้านคุณจะไม่ถูกลงโทษ” คือ“ ถ้าคุณไม่ทำการบ้านคุณจะถูกลงโทษ”

Converse- การสนทนาของคำสั่งเงื่อนไขคำนวณโดยการแลกเปลี่ยนสมมติฐานและข้อสรุป ถ้าคำสั่งคือ“ ถ้า p แล้ว q” การสนทนาจะเป็น“ ถ้า q แล้ว p” สนทนาของ $ p \ rightarrow q $ คือ $ q \ rightarrow p $

Example - บทสนทนาของ "ถ้าคุณทำการบ้านคุณจะไม่ถูกลงโทษ" คือ "ถ้าคุณไม่ถูกลงโทษคุณทำการบ้านของคุณ"

Contra-positive- ผลตรงกันข้ามของเงื่อนไขคำนวณโดยการแลกเปลี่ยนสมมติฐานและข้อสรุปของคำสั่งผกผัน ถ้าคำสั่งคือ“ ถ้า p ดังนั้น q” ผลบวกจะเป็น“ ถ้าไม่ใช่ q แล้วไม่ใช่ p” ตรงกันข้ามของ $ p \ rightarrow q $ คือ $ \ lnot q \ rightarrow \ lnot p $

Example - สิ่งที่ตรงกันข้ามของ "ถ้าคุณทำการบ้านคุณจะไม่ถูกลงโทษ" คือ "ถ้าคุณถูกลงโทษคุณไม่ได้ทำการบ้านของคุณ"

หลักการคู่

หลักการความเป็นคู่ระบุว่าสำหรับคำสั่งจริงใด ๆ คำสั่งคู่ที่ได้จากการเปลี่ยนสหภาพเป็นทางแยก (และในทางกลับกัน) และการเปลี่ยนชุดสากลเป็นชุด Null (และในทางกลับกัน) ก็เป็นจริงเช่นกัน หากคู่ของคำสั่งใด ๆ เป็นคำสั่งนั้นเองจะมีการกล่าวself-dual คำให้การ.

Example - คู่ของ $ (A \ cap B) \ cup C $ คือ $ (A \ cup B) \ cap C $

แบบฟอร์มปกติ

เราสามารถแปลงประพจน์ใดก็ได้ในสองรูปแบบปกติ -

  • รูปแบบปกติ Conjunctive
  • รูปแบบปกติที่ไม่ต่อเนื่อง

รูปแบบปกติ Conjunctive

คำสั่งผสมอยู่ในรูปแบบปกติร่วมกันถ้าได้มาจากการดำเนินการและระหว่างตัวแปร (การปฏิเสธของตัวแปรที่รวมอยู่) ที่เชื่อมต่อกับ OR ในแง่ของการดำเนินการชุดเป็นคำสั่งผสมที่ได้รับจากการแยกระหว่างตัวแปรที่เชื่อมต่อกับสหภาพแรงงาน

Examples

  • $ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $

  • $ (P \ cup Q) \ cap (Q \ cup R) $

รูปแบบปกติที่ไม่ต่อเนื่อง

คำสั่งผสมอยู่ในรูปแบบปกติที่ไม่ต่อเนื่องหากได้มาจากการดำเนินการหรือระหว่างตัวแปร (การปฏิเสธของตัวแปรที่รวมอยู่) ที่เชื่อมต่อกับ ANDs ในแง่ของการดำเนินการเซ็ตมันเป็นคำสั่งผสมที่ได้รับจากยูเนี่ยนระหว่างตัวแปรที่เชื่อมต่อกับทางแยก

Examples

  • $ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $

  • $ (P \ cap Q) \ cup (Q \ cap R) $