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

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

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