วิธีลดความซับซ้อนของนิพจน์บูลีน: ฟังก์ชันกฎหมายและตัวอย่าง

วันนี้เราจะมาเรียนรู้วิธีลดความซับซ้อนของนิพจน์เชิงตรรกะด้วยกันทำความคุ้นเคยกับกฎหมายพื้นฐานและศึกษาตารางความจริงของฟังก์ชันลอจิก

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

การดำเนินงาน

ในการเรียนรู้วิธีลดความซับซ้อนของนิพจน์เชิงตรรกะคุณจำเป็นต้องทราบ:

• ฟังก์ชันใดบ้างที่อยู่ในพีชคณิตบูลีน
• กฎแห่งการลดและการเปลี่ยนแปลงของนิพจน์
• ลำดับการดำเนินงาน

ตอนนี้เราจะพิจารณาปัญหาเหล่านี้โดยละเอียด เริ่มต้นด้วยการดำเนินการ พวกเขาค่อนข้างจำง่าย

1. ก่อนอื่นเราสังเกตการคูณเชิงตรรกะในในวรรณคดีเรียกว่าการดำเนินการร่วมกัน ถ้าเงื่อนไขถูกเขียนเป็นนิพจน์การดำเนินการจะถูกระบุด้วยเครื่องหมายถูกกลับหัวเครื่องหมายคูณหรือ "&"
2. ฟังก์ชั่นที่พบมากที่สุดถัดไปคือการเพิ่มตรรกะหรือการแยก มีเครื่องหมายถูกหรือเครื่องหมายบวกกำกับไว้
3. ฟังก์ชั่นการปฏิเสธหรือการผกผันมีความสำคัญมาก จำไว้ว่าคุณแยกคำนำหน้าในภาษารัสเซียอย่างไร ในทางกราฟิกการผกผันจะถูกระบุโดยคำนำหน้าหน้านิพจน์หรือเส้นแนวนอนด้านบน
4. ผลลัพธ์เชิงตรรกะ (หรือนัย)แสดงด้วยลูกศรจากความหมายถึงผล หากเราพิจารณาการดำเนินการจากมุมมองของภาษารัสเซียก็จะสอดคล้องกับการสร้างประโยคประเภทนี้: "if ... then ... "
5. ถัดมาคือความเท่าเทียมกันซึ่งแสดงด้วยลูกศรสองหัว ในภาษารัสเซียการดำเนินการจะมีลักษณะดังนี้: "เท่านั้น"
6. Schaeffer Stroke แยกสองนิพจน์ด้วยไปป์
7. ลูกศรเพียร์ซเช่นเดียวกับเส้นขีดของแชฟเฟอร์จะแยกนิพจน์ด้วยลูกศรชี้ลงในแนวตั้ง

อย่าลืมจำไว้ว่าการดำเนินการเป็นสิ่งที่จำเป็นดำเนินการตามลำดับที่เข้มงวด: การปฏิเสธการคูณการบวกผลลัพธ์ความเท่าเทียมกัน ไม่มีกฎลำดับความสำคัญสำหรับการทำงานของ Schaeffer stroke และ Pierce arrow ดังนั้นจึงต้องดำเนินการตามลำดับที่ปรากฏในนิพจน์ที่ซับซ้อน

ตารางความจริง

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

สำหรับการรวมตารางจะมีลักษณะดังนี้:

ตารางสำหรับการแยกการดำเนินการ:

การปฏิเสธ:

Corollary:

ความเท่าเทียมกัน:

Schiffer จังหวะ:

ลูกศรของเพียร์ซ:

กฎหมายลดความซับซ้อน

กฎแห่งตรรกะที่เรียบง่ายและชัดเจนจะช่วยให้เราพบคำตอบสำหรับคำถามเกี่ยวกับวิธีลดความซับซ้อนของนิพจน์เชิงตรรกะในวิทยาการคอมพิวเตอร์

เริ่มจากกฎแห่งความขัดแย้งที่ง่ายที่สุดถ้าเราคูณแนวคิดตรงข้าม (A และไม่ใช่ A) เราก็จะได้คำโกหก ในกรณีของการเพิ่มแนวคิดที่ตรงกันข้ามเราได้ความจริงกฎหมายนี้เรียกว่า "กฎของข้อที่สามที่ถูกยกเว้น" บ่อยครั้งในพีชคณิตบูลีนจะมีนิพจน์ที่มีการปฏิเสธสองครั้ง (ไม่ใช่ A) ซึ่งในกรณีนี้เราจะได้รับคำตอบ A นอกจากนี้ยังมีกฎของ de Morgan สองข้อ:

• ถ้าเรามีการปฏิเสธของการบวกเชิงตรรกะเราจะได้การคูณของสองนิพจน์ที่มีการผกผัน (ไม่ใช่ (A + B) = notA * notB);
• กฎข้อที่สองทำงานในทำนองเดียวกันถ้าเรามีการปฏิเสธของการดำเนินการคูณเราจะได้รับการบวกสองค่าด้วยการผกผัน

การทำสำเนาเป็นเรื่องปกติธรรมดาอย่างหนึ่งค่าเดียวกัน (A หรือ B) จะถูกเพิ่มหรือคูณกันเอง ในกรณีนี้กฎแห่งการทำซ้ำจะมีผลบังคับใช้ (A * A = A หรือ B + B = B) กฎของการดูดซึมยังเกิดขึ้น:

• A + (A * B) = A;
• ก * (A + B) = A;
• A * (ไม่ใช่ A + B) = A * B

กฎแห่งพันธะมีสองประการ:

• (A * B) + (A * B) = A;
• (A + B) * (A + B) = ก.

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

ตัวอย่างที่ 1

เราได้ศึกษาคุณสมบัติทั้งหมดของการทำให้ตรรกะง่ายขึ้นสำนวนตอนนี้คุณต้องรวบรวมความรู้ใหม่ในทางปฏิบัติ เราขอเชิญชวนให้คุณวิเคราะห์ตัวอย่างสามตัวอย่างจากหลักสูตรของโรงเรียนและตั๋วสำหรับการสอบแบบรวม

ในตัวอย่างแรกเราต้องทำให้นิพจน์ง่ายขึ้น:(C * E) + (C * ไม่ใช่ E) ก่อนอื่นเราดึงความสนใจของเราไปที่ข้อเท็จจริงที่ว่าทั้งวงเล็บแรกและตัวที่สองมีตัวแปร C เหมือนกันเราขอแนะนำให้คุณนำมันออกจากวงเล็บ หลังจากจัดการเสร็จแล้วเราจะได้นิพจน์: C * (E + notE) ก่อนหน้านี้เราได้พิจารณากฎแห่งการยกเว้นข้อที่สามเราจะนำมาใช้กับสำนวนนี้ ต่อไปนี้เราสามารถยืนยันได้ว่า E + ไม่ใช่ E = 1 ดังนั้นนิพจน์ของเราจึงอยู่ในรูปแบบ: C * 1 เราสามารถลดความซับซ้อนของนิพจน์ผลลัพธ์ได้มากยิ่งขึ้นโดยรู้ว่า C * 1 = C

ตัวอย่างที่ 2

งานต่อไปของเราจะเป็นแบบนี้: อะไรคือสิ่งที่จะเป็นนิพจน์ตรรกะที่เรียบง่ายไม่ (C + notE) + not (C + E) + C * E?

โปรดทราบว่าในตัวอย่างนี้มีการปฏิเสธการแสดงออกที่ซับซ้อนมันคุ้มค่าที่จะกำจัดมันได้รับคำแนะนำจากกฎหมายของเดอมอร์แกน นำไปใช้เราจะได้นิพจน์: notC * E + notC * notE + C * E เราสังเกตการทำซ้ำของตัวแปรอีกครั้งในสองแง่เรานำมันออกจากวงเล็บ: notC * (E + notE) + C * E เราใช้กฎหมายการยกเว้นอีกครั้ง: ไม่ใช่ C * 1 + C * E เราจำได้ว่านิพจน์ "notC * 1" เท่ากับ notC: notC + C * E นอกจากนี้เราขอเสนอให้ใช้กฎหมายการกระจาย: (ไม่ใช่ C + C) * (ไม่ใช่ C + E) เราใช้กฎหมายการยกเว้นข้อที่สาม: ไม่ใช่ C + E

ตัวอย่างที่ 3

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

ลดความซับซ้อนของนิพจน์: (D + E) * (D + F)

1. D * D + D * F + E * D + E * F;
2. D + D * F + E * D + E * F;
3. D * (1 + F) + E * D + E * F;
4. D + E * D + E * F;
5. D * (1 + E) + E * F;
6. D + E * F.

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