Chapters

ประพจน์

ประพจน์ (Proposition) คือ ประโยคที่บอกค่าความจริงได้ โดยที่ค่าความจริงนั้นสามารถจะเป็นจริงหรือเท็จเพียงอย่างใดอย่างหนึ่งเท่านั้น การสร้างประพจน์ (Constructing Propositions)  โดยทั่วไปจะใช้อักษรภาษาอังกฤษแทนประพจน์ อักษรที่นิยมใช้ตัวอย่างเช่น p, q, r, s, … เป็นต้น ประพจน์ที่มีค่าความจร...

ตรรกศาสตร์ภาคแสดง

ตรรกศาสตร์ภาคแสดง คือ ข้อความทางตรรกศาสตร์ ที่สามารถแสดงให้อยู่ในรูป ของฟังก์ชันและเมื่อแทนค่าตัวแปรในฟังก์ชันแล้วสามารถส่งค่ากลับเป็นจริง หรือ เท็จ ได้ ประพจน์ภาคแสดง (Predicate) ประพจน์ภาคแสดง (predicate) เป็นการปรับปรุงประพจน์แบบเดิม (proposition) ด้วยการ สร้างประพจน์ P(c) จากฟังก์ชันข...

เทคนิคการพิสูจน์

เทคนิคการพิสูจน์ การอ้างเหตุผลที่สมเหตุสมผล (valid argument) คือ การอ้างจากเหตุทั้งหมดที่เป็นจริง แล้ว ส่งให้ผลเป็นจริง หรือ การแสดงว่าประพจน์ผสมต่อไปนี้เป็น สัจนิรันดร์ กฎการอนุมาน การอ้างเหตุผลที่พิสูจน์แล้วว่าสมเหตุสมผล สามารถนำไปใช้ในการอ้างเหตุผล ของปัญหาที่ใหญ่ขึ้นได้โดยไม่จำเป็นต้อ...

เซต

เซต สัญลักษณ์ทางคณิตศาสตร์ เพื่อใช้แทนกลุ่มของสิ่งต่าง ๆ ที่เราสนใจ โดยสมาชิกของเซตอาจมีศูนย์หรือมากกว่าศูนย์ชิ้นก็ได้ และลำดับการเขียนสมาชิกของเซตนั้นไม่มีความสำคัญ เซตที่เราสามารถบอกจำนวนสมาชิกได้ เราเรียกว่า เซตจำกัด (finite sets) แต่สำหรับเซตที่มีจำนวน สมาชิกไม่จำกัดนั้น เราเรียกว่า เซต...

ความสัมพันธ์

ความสัมพันธ์ ความสัมพันธ์ (relation) คือเซตของคู่อันดับซึ่งเป็นสับเซตของผลคูณคาร์ทีเซียนของเซต A และ เซต B นิยมเขียนแทนด้วยสัญลักษณ์ R (Relation R is a subset of the ordered pairs in AXB) ซึ่งในความหมายข้างต้นจะประกอบด้วย 2 ส่วน คือ คู่อันดับ ผลคูณคาร์ทีเซียนของเซต A และเซต B (AXB) ค...

ฟังก์ชัน

ฟังก์ชัน ความสัมพันธ์ชนิดหนึ่งซึ่งหากกำหนดให้ f เป็นสับเซตของ AxB แล้ว จะได้ f เป็นฟังก์ชันจาก A ไป B ก็ต่อเมื่อ สมาชิก x ใน A ตัวที่เท่ากัน ต้องมีสมาชิก y ใน B ที่ไม่ แตกต่างกัน (นั้นคือ x ใด ๆ จับคู่กับ y ได้เพียงตัวเดียวเท่านั้น) อิมเมจ พรีอิมเมจ และ เรนจ์ (Image, Pre-image and Range)...

พื้นฐานการนับ

พื้นฐานการนับ พื้นฐานการนับ (basics of counting) เกี่ยวข้องกับกฎในการนับจำนวนของวิธีการหรือรูปแบบ ของสิ่งของหรืองานต่าง ๆ ที่เป็นไปได้ภายใต้เงื่อนไขที่โจทย์กำหนด โดยมีกฎ 5 ข้อ คือ กฎการคูณ กฎการบวก กฎการบวกและการคูณ กฎการลบ กฎการหาร กฎการคูณ (The Product Rule) กำหนดให้ จำนวนวิธีใ...

วิธีอุปนัยเชิงคณิตศาสตร์

วิธีอุปนัยเชิงคณิตศาสตร์ วิธีอุปนัยเชิงคณิตศาสตร์ (mathematical induction) เป็นวิธีที่ใช้ในการพิสูจน์ว่าฟังก์ชันของ ประพจน์ใด ๆ หรือข้อความทางคณิตศาสตร์ใด ๆ เป็นจริงเสมอ สำหรับเลขจำนวนนับทุกจำนวนที่ กำหนดให้มา กำหนดให้ S(n) แทนข้อความหนึ่งทางคณิตศาสตร์ วิธีอุปนัยเชิงคณิตศาสตร์เป็นวิธีการพิ...

การเรียกตัวเอง

การเรียกตัวเอง ในการเขียนนิยามการเรียกตัวเอง (recursive defnitions) ต้องมีการระบุ 2 ส่วน ดังต่อไปนี้ 1. ส่วนพื้นฐาน (Basis) เป็นส่วนที่มีการนิยามค่าต่ำสุดที่โปรแกรมยังท างานได้อยู่ ในส่วนนี้จะ กลายเป็นเงื่อนไขในการหยุดท างานของโปรแกรมแบบเรียกตัวเอง 2. ส่วนอุปนัย (Induction) เป็นส่วนที่มีก...

การวิเคราะห์บิ๊กโอ

การวิเคราะห์บิ๊กโอ การคำนวณเวลาในการประมวลผลของโปรแกรมที่เป็นมาตรฐาน กลางจึงจะไม่คำนวณเป็นหน่วยวินาที แต่จะคำนวณโดยใช้ฟังก์ชันที่แปรผันกับจำนวนข้อมูล n ที่ ป้อนเข้าไป กำหนดให้โปรแกรมใด ๆ ใช้เวลาในการประมวลผล T(n)T(n) = ค่าคงที่ x nT(n) = c*nโดยที่ c เป็นค่าคงที่ และ n เป็นจำนวนข้อมูลที่โปร...

ทฤษฎีกราฟ

ทฤษฎีกราฟ กราฟไม่ระบุทิศทาง (Undirected Graph) พิจารณาปัญหาต่อไปนี้ เจ้าหน้าที่คนหนึ่งอาศัยอยู่ที่เมือง A ต้องการส ารวจเส้นทางไปยังเมืองต่าง ๆ ทุกเส้นทาง โดยมีเงื่อนไขดังนี้ 1) ผู้เดินทางต้องผ่านเมืองต่าง ๆ โดยใช้เส้นทางที่ไม่ซ้ ากันและต้องผ่านทุกเส้นทาง 2) ผู้เดินทางต้องเริ่มที่เมือง A...

ออโตมาตา

ออโตมาตา (automata) หรือ เครื่องจักรกลอัตโนมัติ เป็นโมเดลจำลองทางคณิตศาสตร์ของระบบสถานะจำกัด (fnite state sytems) ที่มีจำนวนสถานะชัดเจนอยู่ในโมเดลนั้น ๆ เราสามารถเขียนโมเดลออโตมาตาในลักษณะเดียวกันกับกราฟระบุทิศทาง โดยที่มีเส้นเชื่อมแสดงการเปลี่ยนแปลงสถานะ และจุดยอดแสดงสถานะต่างๆ ในโมเดล ออโตมาตาทำ...