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

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

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

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

เรียนรู้วิธีการลดความซับซ้อนของการแสดงออกทางตรรกะที่คุณต้องรู้:

• สิ่งที่มีคุณสมบัติไม่พีชคณิตบูลีน;
• ลดและกฎหมายแปลงสำนวน
• คำสั่งของการดำเนินงาน

ตอนนี้เรามองไปที่ปัญหาเหล่านี้ในรายละเอียดมาก ขอเริ่มต้นด้วยการดำเนินงาน พวกเขาจะสวยง่ายต่อการจดจำ

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

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

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

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

สำหรับการร่วมของตารางมีดังนี้

การดำเนินการหย่าตาราง:

ปฏิเสธ:

ผลที่ตามมา:

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

เครื่องอ่านบาร์โค้ด Schiffer:

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

ความเรียบง่ายของกฎหมาย

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

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

• ถ้าเรามีการปฏิเสธนอกจากตรรกะเราได้รับคูณสองนิพจน์ที่มีการผกผัน (ไม่ได้ (A + B) = * Nea Neuve);
• การกระทำที่คล้ายกันและกฎหมายที่สองเรากินปฏิเสธการคูณที่เราได้รับจะเพิ่มสองค่ากับการผกผัน

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

• A + (A * B) = a;
• A * (A + B) = a;
• A * (HEA + B) = A * บี

ไม่มีกฎหมายพันธะสองคนคือ:

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

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

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

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

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

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

งานต่อไปของเราจะเป็นสิ่งที่ยังคงเป็นนิพจน์บูลีนที่เรียบง่ายไม่ได้ (C + มัน) ไม่ + (C + E) + C * E?

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

ตัวอย่างที่ 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 * เอฟ

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