อัลกอริทึมสำหรับสร้างตารางความจริงของนิพจน์เชิงตรรกะ

วันนี้ในบทความนี้จะมีการพิจารณารายละเอียดเกี่ยวกับการสร้างตารางความจริงของนิพจน์เชิงตรรกะ กับปัญหานี้มักมีเด็กนักเรียนที่สอบผ่านการสอบแบบเป็นเอกภาพในสาขาวิทยาการคอมพิวเตอร์ ในความเป็นจริงพีชคณิตบูลีนที่เรียกว่าไม่ซับซ้อนถ้ารู้กฎที่จำเป็นการดำเนินงานและกฎสำหรับการสร้างตารางความจริง เราจะแก้ไขปัญหาเหล่านี้ในวันนี้

พีชคณิตบูลีน

พีชคณิตตรรกะขึ้นอยู่กับนิพจน์เชิงตรรกะง่ายๆที่เชื่อมโยงกันโดยการดำเนินการสร้างนิพจน์ที่ซับซ้อน ควรสังเกตว่าพีชคณิตแบบบูลมีการดำเนินการสองแบบไบนารี: การคูณและการบวก (ร่วมและการแยกตามลำดับ); หนึ่ง unary คือการผกผัน นิพจน์ทั่วไปทั้งหมด (องค์ประกอบของนิพจน์เชิงตรรกะที่ซับซ้อน) ใช้ค่าใดค่าหนึ่ง: "1" หรือ "0", "true" หรือ "false", "+" หรือ "-" ตามลำดับ

พีชคณิตของตรรกะขึ้นอยู่กับสัจพจน์ง่ายๆค่อนข้างน้อย:

• การเชื่อมโยงกัน;
• คือการสับเปลี่ยน;
• การดูดซึม;
• distributivity;
• additionality

ถ้าคุณรู้ว่ากฎหมายเหล่านี้และคำสั่งของการดำเนินงานของฟังก์ชันการสร้างตารางความจริงของนิพจน์เชิงตรรกะจะไม่ทำให้เกิดปัญหาใด ๆ จำได้ว่าการดำเนินการจะต้องดำเนินการในลำดับที่เข้มงวด: การปฏิเสธการคูณการเพิ่มผลให้ความเท่าเทียมกันเท่านั้นจากนั้นไปที่การดำเนินงานของแถบ Schiffer หรือลูกศร Pirs โดยวิธีการสำหรับสองหน้าที่สุดท้ายไม่มีกฎของลำดับความสำคัญให้ดำเนินการในลำดับที่พวกเขาอยู่

กฎสำหรับการรวบรวมตาราง

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

ในการสร้างตารางตรรกะได้อย่างถูกต้องคุณต้องกำหนดจำนวนแถวก่อน ฉันจะทำเช่นนี้ได้อย่างไร? นับจำนวนตัวแปรที่สร้างขึ้นจากการแสดงออกที่ซับซ้อนและใช้สูตรง่ายๆ: A = 2 กับพลังของ n A คือจำนวนแถวในตารางความจริงที่คอมไพล์ n เป็นจำนวนตัวแปรที่ป้อนนิพจน์เชิงตรรกะที่ซับซ้อน

ตัวอย่าง: การแสดงออกที่ซับซ้อนประกอบด้วยตัวแปรสามตัว (A, B และ C) ดังนั้นการหลอกลวงต้องยกขึ้นเป็นกำลังที่สาม ในตารางความจริงที่รวบรวมไว้เราจะมีแปดบรรทัด เพิ่มบรรทัดเดียวสำหรับชื่อของคอลัมน์

จากนั้นเราจะหันไปหานิพจน์และกำหนดลำดับการกระทำที่จะดำเนินการ ควรทำเครื่องหมายคำสั่งด้วยดินสอ (หนึ่งสองและอื่น ๆ )

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

จากนั้นให้กรอกส่วนหัวของตารางของเรา ด้านล่างนี้คุณจะเห็นตัวอย่างนี้

ตอนนี้ไปในการกรอกชุดค่าผสมที่เป็นไปได้ ตัวแปรสองตัวแปรจะมีดังต่อไปนี้: 00, 01, 10, 11. สำหรับตัวแปรสามตัวแปร: 000, 001, 010, 011, 100, 101, 110, 111

คุณสามารถดำเนินการคำนวณและกรอกข้อมูลในเซลล์ที่เหลืออยู่ของตารางผลลัพธ์ได้

ตัวอย่าง

ตอนนี้เราพิจารณาตัวอย่างของการสร้างตารางความจริงของนิพจน์เชิงตรรกะ: การผกผัน A + B * A

1. การนับตัวแปร: 2. จำนวนเส้น: 4 + 1 = 5
2. ลำดับของการกระทำ: การผกผันครั้งแรก, การรวมกันครั้งที่สอง, disjunction ที่สาม
3. จำนวนคอลัมน์: 3 + 2 = 5
4. เราเริ่มวาดและเติมตาราง

ตามกฎแล้วงานจะฟังดูว่า "กี่ชุดมีเงื่อนไข F = 0" หรือ "ในชุดค่าผสม F = 1" ในคำถามแรกคำตอบคือ 1 ในสอง - 00, 01, 11

อ่านงานที่คุณได้รับอย่างระมัดระวัง คุณสามารถแก้ปัญหาได้อย่างถูกต้อง แต่ทำผิดพลาดในการเขียนคำตอบ อีกครั้งเราให้ความสำคัญกับลำดับการกระทำ:

• ปฏิเสธ;
• คูณ;
• การเพิ่ม

งาน

การสร้างตารางความจริงสามารถช่วยในการหาคำตอบสำหรับปัญหาตรรกะยาก เมื่อต้องการติดตามกระบวนการรวบรวมนิพจน์และตารางความจริงโดยเงื่อนไขของภารกิจตรรกะคุณสามารถในส่วนนี้ของบทความ

ให้สี่ค่าของจำนวน A: 1) 7, 2) 6, 3) 5, 4) 4. คำตอบว่า "การผกผัน (A น้อยกว่า 6) + (A น้อยกว่า 5)" เป็นเท็จหรือไม่?

คอลัมน์แรกของเราจะเต็มไปด้วยค่า 7, 6, 5, 4 ในลำดับนี้ ในคอลัมน์ถัดไปเราต้องตอบคำถาม "และน้อยกว่า 6" คอลัมน์ที่สามจะเต็มไปด้วยวิธีเดียวกัน แต่ตอนนี้เราตอบคำถามว่า "และน้อยกว่า 5 หรือไม่"

กำหนดลำดับของการดำเนินงาน เราจำได้ว่าการปฏิเสธดังกล่าวมีความสำคัญมากกว่าการแยกแยะ ดังนั้นเราจึงเติมคอลัมน์ถัดไปโดยมีค่าที่ตรงกับเงื่อนไขไม่ (A น้อยกว่า 6) คำถามที่สี่จะตอบคำถามหลักของงานของเรา ด้านล่างนี้คุณจะเห็นตัวอย่างของการกรอกตาราง

โปรดทราบว่าเรามีหมายเลขคำตอบการแสดงออกผิดจะอยู่ที่ A = 5 นี่เป็นคำตอบที่สาม