ฟังก์ชันเชิงตรรกะเรียกว่ารูปแบบปกติที่เชื่อมต่อกัน รูปแบบที่เชื่อมต่อกันของการแทนฟังก์ชันเชิงตรรกะ

รูปแบบปกติของฟังก์ชันลอจิคัล การแทนฟังก์ชันบูลีนในรูปแบบของการแยกเงื่อนไขที่เชื่อมต่อกันขององค์ประกอบของหน่วย Ki 2.7 เรียกว่ารูปแบบปกติที่แยกจากกันของ DNF ของฟังก์ชันนี้ มีตัวแปรลอจิคัลตัวใดตัวหนึ่งที่มีหรือไม่มีการปฏิเสธ ดังนั้นรูปแบบการนำเสนอฟังก์ชันนี้เรียกว่า SDNF รูปแบบปกติที่แยกส่วนสมบูรณ์แบบของฟังก์ชันนี้ อย่างที่คุณเห็นเมื่อเขียนฟังก์ชัน SDNF คุณจะต้องสร้างการแยกส่วนของ minterms ทั้งหมดที่ฟังก์ชันรับค่า 1

หากงานนี้ไม่เหมาะกับคุณ ที่ด้านล่างของหน้าจะมีรายการผลงานที่คล้ายกัน คุณยังสามารถใช้ปุ่มค้นหา

บรรยาย 1.xx

รูปแบบปกติของฟังก์ชันลอจิคัล

การเป็นตัวแทนของฟังก์ชันบูลีนในรูปแบบของการแยกส่วนคำที่เชื่อมต่อกัน (ส่วนประกอบของหน่วย)เค ฉัน

, (2.7)

เรียกว่า รูปแบบปกติที่ไม่ต่อเนื่องกัน(DNF) ของฟังก์ชันนี้

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

เมื่อคำนึงถึงสิ่งข้างต้นแล้ว ทฤษฎีบทต่อไปนี้จึงเป็นไปตามทฤษฎีบท 2.1

ทฤษฎีบท 2 ฟังก์ชันบูลีนใดๆ(ไม่เหมือนกัน 0) สามารถนำเสนอในรูปแบบ SDNF, .

ตัวอย่างที่ 3 ให้เรามีตารางที่กำหนดฟังก์ชั่นฉ (x 1 , x 2 , x 3 ) (ตารางที่ 10)

ตารางที่ 10

ตามสูตร (2.6) เราได้รับ:

อย่างที่คุณเห็นเมื่อเขียนฟังก์ชัน SDNF คุณจะต้องสร้างการแยกส่วนของ minterms ทั้งหมดที่ฟังก์ชันรับค่า 1

การแสดงฟังก์ชันบูลีนในรูปแบบของคำร่วมที่แยกจากกัน (องค์ประกอบเป็นศูนย์)ฉัน

, (2.8)

เรียกว่า รูปแบบปกติที่เชื่อมต่อกัน(CNF) ของฟังก์ชันนี้

หากเงื่อนไข CNF ที่แยกออกมาทั้งหมดเป็นเงื่อนไขสูงสุด นั่นคือ พวกมันมีหนึ่งในตัวแปรลอจิคัลทั้งหมดของฟังก์ชัน โดยมีหรือไม่มีการปฏิเสธ ดังนั้น CNF ดังกล่าวจึงถูกเรียกว่ารูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบ(SKNF) ของฟังก์ชันนี้

ทฤษฎีบท 3 ฟังก์ชันบูลีนใดๆ(ไม่เหมือนกับ 1) สามารถส่งไปที่ SKNF ได้, และการเป็นตัวแทนดังกล่าวเป็นเพียงสิ่งเดียวเท่านั้น.

การพิสูจน์ทฤษฎีบทสามารถดำเนินการได้คล้ายกับการพิสูจน์ทฤษฎีบท 2.1 โดยอาศัยบทแทรกแชนนอนต่อไปนี้เกี่ยวกับการสลายตัวแบบเชื่อมต่อ

Lemma ของแชนนอน - ฟังก์ชันบูลีนใดๆ f (x 1, x 2, …, x m) จากม ตัวแปรสามารถแสดงได้เช่นนี้:

. (2.9)

ควรสังเกตว่าทั้งสองรูปแบบของการเป็นตัวแทนของฟังก์ชันลอจิคัล (DNF และ CNF) มีความสามารถเท่ากันในทางทฤษฎี: สูตรลอจิคัลใด ๆ สามารถแสดงได้ทั้งใน DNF (ยกเว้นศูนย์ที่เหมือนกัน) และใน CNF (ยกเว้นที่เหมือนกัน ). การแสดงฟังก์ชันในรูปแบบใดรูปแบบหนึ่งอาจสั้นกว่านั้นขึ้นอยู่กับสถานการณ์

ในทางปฏิบัติ DNF มักถูกใช้บ่อยที่สุดเนื่องจากแบบฟอร์มนี้คุ้นเคยกับบุคคลมากกว่า: ตั้งแต่วัยเด็กเขาคุ้นเคยกับการเพิ่มผลิตภัณฑ์มากกว่าการคูณผลรวม (ในกรณีหลังเขามีความปรารถนาที่จะเปิดวงเล็บโดยสัญชาตญาณและด้วยเหตุนี้จึงย้ายไปยัง DNF)

ตัวอย่างที่ 4 สำหรับฟังก์ชัน f (x 1 , x 2 , x 3 ) กำหนดโดยตาราง 10 เขียนถึง SKNF

ต่างจาก SDNF เมื่อรวบรวม SCNF ในตารางความจริงของฟังก์ชันลอจิคัล คุณต้องดูการรวมกันของตัวแปรที่ฟังก์ชันรับค่า 0 และสร้างการรวมของ maxterms ที่สอดคล้องกันแต่ตัวแปรจะต้องถูกถ่ายด้วยการผกผันแบบย้อนกลับ:

ควรสังเกตว่าเป็นไปไม่ได้ที่จะย้ายจาก SDNF ของฟังก์ชันไปยัง SCNF โดยตรงหรือในทางกลับกัน เมื่อพยายามแปลงผลลัพธ์ผลลัพธ์จะเป็นฟังก์ชันที่ตรงกันข้ามกับฟังก์ชันที่ต้องการ นิพจน์สำหรับฟังก์ชัน SDNF และ SCNF สามารถรับได้โดยตรงจากตารางความจริงเท่านั้น

ตัวอย่างที่ 5 สำหรับฟังก์ชัน f (x 1 , x 2 , x 3 ) กำหนดโดยตาราง 10 ให้ลองเปลี่ยนจาก SDNF เป็น SKNF

ใช้ผลลัพธ์ของตัวอย่าง 2.3 เราได้รับ:

ดังที่คุณเห็น ภายใต้การผกผันทั่วไป เราได้รับ SCNF ของฟังก์ชันลอจิคัล ซึ่งเป็นค่าผกผันของฟังก์ชันที่ได้รับในตัวอย่าง 2.4:

เนื่องจากมี maxterms ทั้งหมดที่ไม่ได้อยู่ในนิพจน์สำหรับ SCNF ของฟังก์ชันที่กำลังพิจารณา

1. การใช้คุณสมบัติของการดำเนินการ (ดูตารางที่ 9) ข้อมูลประจำตัว (), ผลรวมโมดูโล 2 (), ความหมาย () เราไปยังการดำเนินการและ, หรือ, ไม่ใช่ (ในรูปแบบบูลีน)

2. การใช้คุณสมบัติของการปฏิเสธและกฎของ De Morgan (ดูตารางที่ 9) เรารับรองว่าการดำเนินการปฏิเสธจะมีผลกับตัวแปรแต่ละตัวเท่านั้น ไม่ใช่กับนิพจน์ทั้งหมด

3. การใช้คุณสมบัติของการดำเนินการเชิงตรรกะ AND และ OR (ดูตารางที่ 9) เราได้รับรูปแบบปกติ (DNF หรือ CNF)

4. หากจำเป็น ให้ไปยังรูปแบบที่สมบูรณ์แบบ (SDNF หรือ SKNF) ตัวอย่างเช่น หากต้องการรับ SCNF คุณมักจะต้องใช้คุณสมบัติ:

ตัวอย่างที่ 6 แปลงฟังก์ชันลอจิคัลเป็น SKNF

ดำเนินการตามขั้นตอนของอัลกอริธึมด้านบนตามลำดับเราได้รับ:

เมื่อใช้คุณสมบัติการดูดซับเราจะได้:

ดังนั้นเราจึงได้ฟังก์ชัน CNFฉ (x 1 , x 2 , x 3 - ในการรับ SCNF คุณจะต้องทำซ้ำแต่ละการแยกส่วนซึ่งมีตัวแปรใดๆ หายไป สองครั้งกับตัวแปรนี้และด้วยการปฏิเสธ:

2.2.6. การลดฟังก์ชันลอจิกให้เหลือน้อยที่สุด

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

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

วิธีการของควินน์

ฟังก์ชันที่จะย่อเล็กสุดจะแสดงในรูปแบบ SDNF และการดำเนินการติดกาวที่ไม่สมบูรณ์ทั้งหมดที่เป็นไปได้จะถูกนำไปใช้กับฟังก์ชันนั้น

, (2.10)

แล้วจึงดูดซึม

, (2.11)

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

โปรดทราบว่าด้านซ้ายของสมการ (2.10) สามารถย่อให้เล็กสุดได้ทันทีด้วยวิธีที่ง่ายและชัดเจนยิ่งขึ้น:

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

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

วิธีแผนที่คาร์นอฟ

วิธีการแมปการ์โนต์ (ตาราง) เป็นวิธีที่มองเห็นได้ง่ายกว่า ใช้แรงงานน้อยกว่า และเชื่อถือได้ในการลดฟังก์ชันลอจิคัล แต่การใช้งานจริงนั้นจำกัดอยู่ที่ฟังก์ชันของตัวแปร 3-4 ตัว และตัวแปรสูงสุด 5-6 ตัว

แผนที่การ์โนต์ นี่คือรูปแบบตารางสองมิติที่ใช้แทนตารางความจริงของฟังก์ชันบูลีน ซึ่งช่วยให้คุณค้นหา DNF ขั้นต่ำของฟังก์ชันลอจิคัลในรูปแบบภาพกราฟิกได้อย่างง่ายดาย แต่ละเซลล์ของตารางเชื่อมโยงกับ SDNF minterm ของฟังก์ชันที่ถูกย่อให้เล็กสุด และในลักษณะที่แกนสมมาตรใดๆ ของตารางสอดคล้องกับโซนที่ผกผันร่วมกันด้วยความเคารพต่อตัวแปรบางตัว การจัดเรียงเซลล์ในตารางทำให้ง่ายต่อการกำหนดเงื่อนไขการผสานของ SDNF (แตกต่างกันในเครื่องหมายผกผันของตัวแปรเพียงตัวเดียว): เซลล์เหล่านี้จะอยู่ในตารางแบบสมมาตร

ตารางความจริงและแผนที่ Carnaugh สำหรับฟังก์ชัน AND และ OR ของสองเลนจ ตัวแปรต่างๆ จะแสดงในรูป 8. ค่าจะถูกเขียนลงในแต่ละเซลล์ของแผนที่ก ค่าของฟังก์ชันในชุดค่าอาร์กิวเมนต์ที่สอดคล้องกับเซลล์นี้เอ็น สหาย

ก) และ ข) หรือ

ข้าว. 8. ตัวอย่างแผนที่ Karnaugh สำหรับฟังก์ชันของตัวแปรสองตัว

ในแผนที่ Karnaugh มีเพียง 1 เดียวสำหรับฟังก์ชัน And ดังนั้นจึงไม่สามารถยึดติดกับสิ่งใดๆ ได้ นิพจน์สำหรับฟังก์ชันขั้นต่ำจะมีเฉพาะคำที่สอดคล้องกับ 1 นี้เท่านั้น:

ฉ = x ย .

ในแผนที่ Carnot สำหรับฟังก์ชัน OR มี 1 สามตัวอยู่แล้ว และคุณสามารถสร้างคู่ที่ผสานกันสองคู่ โดยที่ 1 ตรงกับคำนั้นเอ็กซ์ซี , ถูกใช้สองครั้ง ในนิพจน์สำหรับฟังก์ชันขั้นต่ำสุด คุณต้องจดคำศัพท์สำหรับคู่ที่ติดกาวเข้าด้วยกัน โดยปล่อยให้ตัวแปรทั้งหมดที่ไม่เปลี่ยนแปลงสำหรับคู่นี้อยู่ในนั้น และลบตัวแปรที่เปลี่ยนค่าของมันออก สำหรับการติดกาวแนวนอนที่เราได้รับ x และสำหรับแนวตั้งย ด้วยเหตุนี้เราจึงได้นิพจน์

ฉ = x + y

ในรูป 9 แสดงตารางความจริงของสองฟังก์ชันจากสามตัวแปร (ก ) และแผนที่การ์โนต์ (ข และ ค) ฟังก์ชัน ฉ 2 แตกต่างจากตัวแรกตรงที่ไม่ได้กำหนดไว้ในตัวแปรสามชุด (ในตารางจะระบุด้วยเส้นประ)

เมื่อกำหนดฟังก์ชัน DNF ขั้นต่ำ จะใช้กฎต่อไปนี้ เซลล์ทั้งหมดที่มี 1 จะรวมกันเป็นพื้นที่สี่เหลี่ยมปิดที่เรียกว่า k-คิวบ์ โดยที่ k = log 2 K, K จำนวน 1 ในพื้นที่สี่เหลี่ยม ในกรณีนี้ แต่ละพื้นที่ควรเป็นรูปสี่เหลี่ยมผืนผ้าที่มีจำนวนเซลล์ 2 k โดยที่ k = 0, 1, 2, 3, …. สำหรับเค = เรียกว่า 1 สี่เหลี่ยมหนึ่งคือลูกบาศก์และมี 2 1 = 2 หน่วย สำหรับเค = 2 สี่เหลี่ยมมี 2 2 = 4 หน่วย และเรียกว่าสองลูกบาศก์; สำหรับ k = 3 ขอบเขตของ 2 3 = 8 หน่วย เรียกว่าสามลูกบาศก์ - เป็นต้น สามารถเรียกหน่วยที่ไม่สามารถรวมกันเป็นสี่เหลี่ยมได้ศูนย์ลูกบาศก์ ซึ่งมีหน่วยเดียวเท่านั้น (2 0 = 1) ดังที่เห็นได้แม้กระทั่งเค พื้นที่สามารถมีรูปทรงสี่เหลี่ยมได้ (แต่ไม่จำเป็น) และหากเป็นเลขคี่เค สี่เหลี่ยมเท่านั้น

ข้าว. 9. ตัวอย่างแผนที่ Karnaugh สำหรับฟังก์ชันของตัวแปร 3 ตัว

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

แต่ละพื้นที่ที่ระบุบนแผนที่ Karnaugh จะแสดงเป็น DNF ขั้นต่ำด้วยการเชื่อม จำนวนข้อโต้แย้งที่เป็นเค น้อยกว่าจำนวนอาร์กิวเมนต์ของฟังก์ชันทั้งหมดม นั่นคือจำนวนนี้เท่ากันม.ค - การรวม DNF ที่น้อยที่สุดแต่ละครั้งจะประกอบด้วยข้อโต้แย้งเหล่านั้นเท่านั้นซึ่งสำหรับพื้นที่ที่เกี่ยวข้องของแผนที่มีค่าโดยไม่มีการผกผันหรือเฉพาะที่มีการผกผันเท่านั้นนั่นคือ อย่าเปลี่ยนความหมาย

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

สำหรับฟังก์ชันตามแผนที่ Karnaugh ในรูป 9,ข เราพบ

เนื่องจากตัวแปรสำหรับพื้นที่ปิดด้านบน x 1 และ x 2 มีค่าที่ไม่มีการผกผันสำหรับค่าที่ต่ำกว่า x1 เรื่องที่มีการผกผันและ x 3 โดยไม่มีการผกผัน

ค่าที่ไม่ได้กำหนดในแผนที่ในรูป 9,วี สามารถกำหนดเพิ่มเติมได้โดยการแทนที่ด้วยศูนย์หรือหนึ่ง สำหรับฟังก์ชันนี้เป็นที่ชัดเจนว่าการแทนที่ทั้งค่าที่ไม่ได้กำหนดด้วย 1 จะทำกำไรได้มากกว่า ในกรณีนี้ จะมีการสร้างพื้นที่สองพื้นที่ซึ่งเป็น 2 คิวบ์ประเภทต่างๆ จากนั้นนิพจน์สำหรับฟังก์ชัน DNF ขั้นต่ำจะเป็นดังนี้:

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

แผนที่ Carnaugh สามารถวาดได้หลายวิธี (รูปที่ 10)

ข

ข้าว. 10. วิธีต่างๆ ในการนำเสนอแผนที่ Carnaugh
สำหรับฟังก์ชัน 3 ตัวแปร

แต่ตัวเลือกที่สะดวกที่สุดสำหรับแผนที่ Karnaugh สำหรับฟังก์ชันของตัวแปร 2-4 ตัวคือตัวเลือกที่แสดงในรูปที่ 1 11 ตาราง เนื่องจากแสดงสำหรับแต่ละเซลล์ก เรามีตัวแปรทั้งหมดในรูปแบบตรงหรือแบบผกผัน

ข

ข้าว. สิบเอ็ด ภาพแผนที่ Carnaugh ที่สะดวกที่สุด
สำหรับฟังก์ชัน 3 (ก) และตัวแปร 4 (b)

สำหรับฟังก์ชันของตัวแปร 5 และ 6 วิธีการแสดงในรูปที่ 1 10,วี

ข้าว. 12. รูปภาพแผนที่ Karnaugh สำหรับฟังก์ชัน 5 ตัวแปร

ข้าว. 13. รูปภาพแผนที่ Karnaugh สำหรับฟังก์ชันของตัวแปร 6 ตัว

พื้นฐานมาตรฐาน สูตรเบื้องต้นเป็นตัวอักษร การรวมระดับประถมศึกษา (การแยกส่วน) Disjunctive (conjunctive) รูปแบบปกติและรูปแบบที่สมบูรณ์แบบ ทฤษฎีบท: ฟังก์ชันบูลีนใดๆ ที่แตกต่างจาก 0 (จาก 1) สามารถแสดงในรูปแบบของ SDNF (SCNF) ความสมบูรณ์ของพื้นฐานมาตรฐาน ตัวอย่างของฐานที่สมบูรณ์: พื้นฐาน Zhegalkin, จังหวะ Schaeffer, ลูกศร Peirce

พื้นฐานมาตรฐาน เป็นชุดของการดำเนินการพื้นฐานของพีชคณิตแบบบูลีนสามรายการ: การบวก (สหภาพ) การคูณ (จุดตัด) และการปฏิเสธ

ที่นี่เราจะโทร ตัวอักษร ตัวแปร x หรือการปฏิเสธ x และแสดงถึง xˆ จุดตัดบูลีนของตัวอักษรหลายตัวที่กำหนดโดยตัวแปรที่แตกต่างกัน เช่น การแสดงออกของรูปแบบ X = xˆ 1 xˆ 2 - - xˆ l เรียกว่า การรวมระดับประถมศึกษา - ข้อกำหนดที่ว่าตัวแปรทั้งหมดจะแตกต่างกันนั้นพิจารณาจากสิ่งต่อไปนี้ หากคำร่วมมีตัวอักษรที่เหมือนกันหลายตัว ดังนั้นเนื่องจากการสับเปลี่ยน ความสัมพันธ์และความสม่ำเสมอของคำร่วม จึงเป็นไปได้ที่จะเหลือเพียงตัวอักษรเดียว (เช่น x 1 x 1 = x 1) ที่เป็นไปได้โดยผ่านไปยังสูตรที่เทียบเท่ากัน หากการร่วมมีตัวแปรและการปฏิเสธของมัน สูตรจะเท่ากับค่าคงที่ 0 เนื่องจาก x x = 0 และสำหรับสูตรใดๆ Y เรามี Y x x = 0

การแยกตัวของคำสันธานเบื้องต้นหลายคำเรียกว่า รูปแบบปกติที่ไม่ต่อเนื่องกัน , หรือ ดีเอ็นเอฟ - ตัวอย่างเช่น,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

ถ้าองค์ประกอบของตัวแปรในแต่ละการเชื่อมเบื้องต้นของ DNF ที่กำหนดเหมือนกัน DNF จะถูกเรียก สมบูรณ์แบบ - ตัวอย่างที่ให้มาคือ DNF ที่ไม่สมบูรณ์แบบ ตรงกันข้ามกับสูตร

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

มีฟอร์มที่สมบูรณ์แบบ

เนื่องจากการบวกและการคูณพีชคณิตแบบบูลีนเป็นการดำเนินการแบบสมมาตร และคุณสามารถตีความการบวกเป็นการคูณ และการคูณเป็นการบวกได้เสมอ จึงมีแนวคิดสองประการ - รูปแบบปกติที่เชื่อมต่อกัน (เคเอ็นเอฟ ) ซึ่งเป็นคำเชื่อมของการแยกทางเบื้องต้น และ รูปแบบการเชื่อมต่อที่สมบูรณ์แบบ (เอสเคเอ็นเอฟ - จากหลักการของความเป็นคู่สำหรับการแบ่งครึ่งทางแบบสมมาตร เป็นไปตามว่าข้อความใด ๆ เกี่ยวกับ DNF จะได้รับคำตอบด้วยข้อความคู่เกี่ยวกับ CNF ซึ่งได้มาจากการแทนที่การบวก (การแยกจากกัน) ด้วยการคูณ การคูณ (การรวมกัน) ด้วยการบวก ค่าคงที่ 0 ด้วยค่าคงที่ 1 ค่าคงที่ 1 โดยมีค่าคงที่ 0 ความสัมพันธ์ลำดับกับคู่ (ผกผัน) ตามลำดับ ดังนั้นเราจะเน้นไปที่การศึกษาเฉพาะ DNF ต่อไป

ทฤษฎีบท 1.4ฟังก์ชันบูลีนใดๆ ที่ไม่ใช่ค่าคงที่ 0 สามารถแสดงเป็น SDNF ได้

◀ให้เราตกลงกันว่าโดย x σ เราหมายถึงสูตร x ถ้า σ = 1 และสูตร x ถ้า σ = 0 ให้ฟังก์ชัน f(y 1 , . . . , y n) ใช้ค่า 1 บนเวกเตอร์ (t 1 , . , t n ) (เวกเตอร์ดังกล่าวเรียกว่า หน่วยที่เป็นส่วนประกอบ - จากนั้นการเชื่อมระดับประถมศึกษายังรับค่า 1 ในชุดนี้ด้วย แต่จะหายไปในเวกเตอร์บูลีน n มิติอื่นๆ ทั้งหมด พิจารณาสูตร

ซึ่งผลรวม (ยูเนี่ยน) ขยายไปยังชุดเหล่านั้นทั้งหมด (t 1, . . . , t n) ของค่าอาร์กิวเมนต์ที่ฟังก์ชันที่กำหนดรับค่า 1 โปรดทราบว่าชุดของชุดดังกล่าวไม่ว่างเปล่าดังนั้น ผลรวมมีอย่างน้อยหนึ่งเทอม

เป็นเรื่องง่ายที่จะเห็นว่าสูตร Φ กลายเป็น 1 สำหรับค่าเหล่านั้นและเฉพาะค่าเหล่านั้นของตัวแปรที่ฟังก์ชันดังกล่าวกลายเป็น 1 ซึ่งหมายความว่าสูตร Ψ แสดงถึงฟังก์ชัน f

ข้อพิสูจน์ 1.1.พื้นฐานมาตรฐานเสร็จสมบูรณ์

◀ อันที่จริง ถ้าฟังก์ชันไม่ใช่ค่าคงที่ 0 ก็สามารถแสดงฟังก์ชันนั้นได้ในรูปแบบของ SDNF ซึ่งเป็นสูตรที่อยู่เหนือพื้นฐานมาตรฐาน ค่าคงที่ 0 สามารถแทนได้ด้วยสูตร f(x 1, x 2, . . . , x n) = x 1 x 1

ตัวอย่างที่ 1.2พิจารณาฟังก์ชันของตัวแปร 3 ตัว m(x 1, x 2, x 3) (ตารางที่ 1.4) เรียกว่า หน้าที่ส่วนใหญ่ . ฟังก์ชันนี้จะประเมินเป็น 1 หากอาร์กิวเมนต์มากกว่าครึ่งหนึ่งมีค่า 1 ดังนั้นจึงมักเรียกว่าฟังก์ชันการลงคะแนน มาสร้าง SDNF ให้มันกันดีกว่า

ความสมบูรณ์ของพื้นฐานมาตรฐานทำให้สามารถเลือกระบบการทำงานอื่นๆ ที่สมบูรณ์ได้ ความสมบูรณ์ของเซต F สามารถกำหนดได้จากการพิจารณาดังต่อไปนี้ สมมติว่าฟังก์ชันบัสมาตรฐานทั้งสามฟังก์ชันสามารถแสดงได้ด้วยสูตรส่วน F จากนั้นตามทฤษฎีบท 1.3 เอกลักษณ์ F จะสมบูรณ์

ตัวอย่างที่ 1.3ชุดการดำเนินการของการบวกโมดูโล 2 การคูณและค่าคงที่ 1 เรียกว่า พื้นฐาน Zhegalkin - การบวกแบบโมดูโล 2 และการคูณเป็นการดำเนินการพื้นฐานของวงแหวน Z2 นิพจน์ที่ประกอบด้วยตัวช่วยคือพหุนามเหนือวงแหวน Z2 ค่าคงที่ 1 ในกรณีนี้จำเป็นในการเขียนคำศัพท์อิสระ เนื่องจาก xx = x ดังนั้นปัจจัยทั้งหมดในพหุนามจึงมีดีกรี 1 ดังนั้น เมื่อเขียนพหุนาม คุณสามารถทำได้โดยไม่ต้องมีแนวคิดเรื่องดีกรี ตัวอย่างของสูตรบนพื้นฐาน Zhegalkin:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

สูตรดังกล่าวเรียกว่าพหุนาม Zhegalkin ในความเป็นจริง พหุนาม Zhegalkin เป็นพหุนามเหนือวงแหวน Z2

การสร้างสูตรบนพื้นฐาน Zhegalkin ไม่ใช่เรื่องยากซึ่งแสดงถึงการดำเนินการของการบวกและการปฏิเสธของพื้นฐานมาตรฐาน (การคูณของทั้งสองฐานเป็นเรื่องปกติ):

x+y=x⊕y⊕xy, x =x⊕1.

ดังนั้นพื้นฐาน Zhegalkin จึงเป็นชุดที่สมบูรณ์
จะเห็นได้ว่าสำหรับฟังก์ชันบูลีนใดๆ พหุนาม Zhegalkin นั้นถูกกำหนดไว้อย่างไม่ซ้ำกัน

(แม่นยำยิ่งขึ้นขึ้นอยู่กับลำดับของข้อกำหนด) ค่าสัมประสิทธิ์ของพหุนาม Zhegalkin ที่มีตัวแปรจำนวนน้อยสามารถพบได้โดยใช้วิธีค่าสัมประสิทธิ์ไม่แน่นอน

ตัวอย่างที่ 1.4ลองพิจารณาชุดของฟังก์ชันเดียว - Schaeffer stroke* ชุดนี้เสร็จสมบูรณ์ดังต่อไปนี้จากตัวตนที่ตรวจสอบได้ง่ายต่อไปนี้:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y)

ตัวอย่างที่ 1.5พื้นฐานที่ประกอบด้วยฟังก์ชันเดียวคือลูกศร Peirce ก็เสร็จสมบูรณ์เช่นกัน การทดสอบนี้คล้ายกับกรณีของ Schaeffer stroke อย่างไรก็ตาม ข้อสรุปนี้สามารถสรุปได้บนพื้นฐานของหลักการความเป็นคู่สำหรับการแยกครึ่งทางแบบสมมาตร

*จังหวะของแชฟเฟอร์เป็นแบบไบนารี่แต่ไม่เชื่อมโยงกัน ดังนั้นเมื่อใช้แบบฟอร์มมัดคุณควรระวัง: ผลลัพธ์ขึ้นอยู่กับลำดับการดำเนินการ ในกรณีนี้ ขอแนะนำให้ระบุลำดับการดำเนินการอย่างชัดเจนโดยใช้วงเล็บ เช่น เขียน (x | y) | z ไม่ใช่ x | ใช่ | z แม้ว่าทั้งสองรูปแบบจะเท่ากันก็ตาม

คำจำกัดความ 1.ร่วม monomial (ร่วมประถม)จากตัวแปรคือการรวมกันของตัวแปรเหล่านี้หรือการปฏิเสธของตัวแปรเหล่านี้

ตัวอย่างเช่น, เป็นคำเชื่อมเบื้องต้น

คำจำกัดความ 2monomial ที่ไม่ต่อเนื่อง (การแยกส่วนเบื้องต้น)จากตัวแปรเรียกว่าการแยกตัวของตัวแปรเหล่านี้หรือการปฏิเสธของตัวแปรเหล่านี้

ตัวอย่างเช่นเป็นการแตกแยกเบื้องต้น

คำจำกัดความ 3สูตรที่เทียบเท่ากับสูตรพีชคณิตเชิงประพจน์ที่กำหนดและแยกจากกันของ monomials เชื่อมเบื้องต้นเรียกว่า รูปแบบปกติที่ไม่ต่อเนื่องกัน(DNF) ของสูตรนี้

ตัวอย่างเช่น,– ดีเอ็นเอฟ.

คำจำกัดความที่ 4สูตรที่เทียบเท่ากับสูตรพีชคณิตเชิงประพจน์ที่กำหนดและเป็นคำเชื่อมของ monomials ที่แยกจากกันเบื้องต้นเรียกว่า รูปแบบปกติที่เชื่อมต่อกัน(CNF) ของสูตรนี้

ตัวอย่างเช่น, – เคเอ็นเอฟ.

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

อัลกอริทึมสำหรับการสร้างแบบฟอร์มปกติ

การใช้ความเท่าเทียมกันของพีชคณิตเชิงตรรกะแทนที่การดำเนินการพื้นฐานทั้งหมดในสูตร: การร่วม การแตกแยก การปฏิเสธ:

กำจัดเชิงลบสองเท่า

ใช้คุณสมบัติของสูตรการกระจายและการดูดซึมกับการดำเนินการของการเชื่อมและการแตกแยกหากจำเป็น

2.6. รูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบและรูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบ

ฟังก์ชันบูลีนใดๆ สามารถมีการแสดงได้หลายรูปแบบในรูปแบบของ DNF และ CNF สถานที่พิเศษท่ามกลางการนำเสนอเหล่านี้ถูกครอบครองโดย DNF ที่สมบูรณ์แบบ (SDNF) และ CNF ที่สมบูรณ์แบบ (SCNF)

คำจำกัดความ 1. รูปแบบปกติที่ไม่ต่อเนื่องที่สมบูรณ์แบบ(SDNF) คือ DNF ซึ่งแต่ละ monomial ที่เชื่อมต่อกันมีตัวแปรแต่ละตัวจากเซตเพียงครั้งเดียว ไม่ว่าจะเป็นตัวมันเองหรือการปฏิเสธของมันเอง

ในเชิงโครงสร้าง SDNF สำหรับแต่ละสูตรพีชคณิตเชิงประพจน์ที่ลดลงเป็น DNF สามารถกำหนดได้ดังต่อไปนี้:

คำจำกัดความ 2 รูปแบบปกติที่ไม่ต่อเนื่องที่สมบูรณ์แบบ(SDNF) ของสูตรพีชคณิตเชิงประพจน์เรียกว่า DNF ซึ่งมีคุณสมบัติดังต่อไปนี้:

คำจำกัดความ 3 รูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบ(SCNF) คือ CNF ซึ่งแต่ละ monomial ที่แยกจากกันจะมีตัวแปรแต่ละตัวจากเซตเดียวเท่านั้น และตัวมันเองหรือการปฏิเสธก็จะปรากฏขึ้นมา

ในเชิงโครงสร้าง SCNF สำหรับสูตรพีชคณิตเชิงประพจน์แต่ละสูตรที่ลดลงเหลือ CNF สามารถกำหนดได้ดังต่อไปนี้

คำจำกัดความที่ 4 รูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบ(SCNF) ของสูตรพีชคณิตเชิงประพจน์ที่กำหนดเรียกว่า CNF ซึ่งมีคุณสมบัติดังต่อไปนี้

ทฤษฎีบท 1ฟังก์ชันบูลีนทุกฟังก์ชันของตัวแปรที่ไม่เป็นเท็จเหมือนกันสามารถแสดงได้ใน SDNF และด้วยวิธีที่ไม่เหมือนใคร

วิธีการค้นหา SDNF

วิธีที่ 1

วิธีที่ 2

เลือกบรรทัดที่สูตรรับค่า 1;

เราเขียนการแยกคำสันธานภายใต้เงื่อนไขว่าหากตัวแปรถูกรวมเข้ากับค่า 1 แล้วเราจะเขียนตัวแปรนี้ ถ้ามีค่า 0 แสดงว่ามันเป็นการปฏิเสธ เราได้รับ SDNF

ทฤษฎีบท 2ฟังก์ชันบูลีนทุกฟังก์ชันของตัวแปรที่ไม่เป็นจริงเหมือนกันสามารถแสดงได้ใน SCNF และด้วยวิธีเฉพาะ

วิธีการค้นหา SCNF

วิธีที่ 1– ใช้การแปลงที่เท่ากัน:

วิธีที่ 2– การใช้ตารางความจริง:

เลือกบรรทัดที่สูตรรับค่า 0;

เราเขียนการรวมของการแยกออกภายใต้เงื่อนไขว่าถ้ามีตัวแปรรวมอยู่ในการแยกย่อยด้วยค่า 0 เราจะเขียนตัวแปรนี้ลงไป ถ้ามีค่าเป็น 1 แสดงว่ามันเป็นการปฏิเสธ เราได้รับ SKNF

ตัวอย่างที่ 1สร้างฟังก์ชัน CNF

สารละลาย

มากำจัดการเชื่อมต่อ "" โดยใช้กฎของการแปลงตัวแปร:

= /de กฎของมอร์แกนและการปฏิเสธสองครั้ง/ =

/กฎการกระจาย/ =

ตัวอย่างที่ 2มอบสูตรให้กับ DNF

สารละลาย

มาแสดงการดำเนินการเชิงตรรกะโดยใช้และ:

= /มาแยกประเภทการปฏิเสธเป็นตัวแปรและลดค่าลบสองเท่า/ =

= /กฎการกระจาย/

ตัวอย่างที่ 3เขียนสูตรใน DNF และ SDNF

สารละลาย

เมื่อใช้กฎแห่งตรรกศาสตร์ เราลดสูตรนี้ให้อยู่ในรูปแบบที่มีเพียงการแยกสันธานระดับประถมศึกษาเท่านั้น สูตรผลลัพธ์จะเป็น DNF ที่ต้องการ:

ในการสร้าง SDNF เรามาสร้างตารางความจริงสำหรับสูตรนี้กัน:

เราทำเครื่องหมายแถวเหล่านั้นของตารางที่สูตร (คอลัมน์สุดท้าย) รับค่า 1 สำหรับแต่ละแถวดังกล่าวเราจะเขียนสูตรที่เป็นจริงในชุดตัวแปรของแถวนี้:

บรรทัดที่ 1: ;

บรรทัดที่ 3: ;

บรรทัดที่ 5: .

การแยกกันของสูตรทั้งสามนี้จะใช้ค่า 1 เฉพาะกับเซตของตัวแปรในบรรทัดที่ 1, 3, 5 เท่านั้น และดังนั้นจึงจะเป็นรูปแบบปกติการแยกส่วนที่สมบูรณ์แบบที่ต้องการ (PDNF):

ตัวอย่างที่ 4นำสูตรมาสู่ SKNF ได้ 2 วิธี:

ก) ใช้การแปลงที่เท่ากัน

b) การใช้ตารางความจริง

สารละลาย:

ให้เราแปลงการแยกส่วนประถมศึกษาที่สอง:

สูตรดูเหมือนว่า:

b) จัดทำตารางความจริงสำหรับสูตรนี้:

เราทำเครื่องหมายแถวเหล่านั้นของตารางที่สูตร (คอลัมน์สุดท้าย) รับค่า 0 สำหรับแต่ละแถวดังกล่าวเราจะเขียนสูตรที่เป็นจริงในชุดตัวแปรของแถวนี้:

บรรทัดที่ 2: ;

บรรทัดที่ 6: .

การรวมกันของทั้งสองสูตรนี้จะใช้ค่า 0 เฉพาะกับชุดของตัวแปรในบรรทัดที่ 2 และ 6 เท่านั้น และดังนั้นจึงจะเป็นรูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบที่ต้องการ (PCNF):

คำถามและงานสำหรับการแก้ปัญหาอิสระ

1. ใช้การแปลงที่เทียบเท่า ลดสูตรเป็น DNF:

2. ใช้การแปลงที่เท่ากัน นำสูตรไปที่ CNF:

3. ใช้กฎการกระจายตัวที่สอง แปลง DNF เป็น CNF:

ก) ;

4. แปลง DNF ที่กำหนดเป็น SDNF:

5. แปลง CNF ที่กำหนดเป็น SCNF:

6. สำหรับสูตรลอจิคัลที่กำหนด ให้สร้าง SDNF และ SCNF ในสองวิธี: ใช้การแปลงที่เทียบเท่า และใช้ตารางความจริง

ข) ;

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

คำสันธานเบื้องต้น (ร่วม)เรียกว่าคำเชื่อมของตัวแปร หรือการปฏิเสธ โดยที่ตัวแปรแต่ละตัวเกิดขึ้นมากที่สุด

ครั้งหนึ่ง.

รูปแบบปกติที่ไม่ต่อเนื่องกัน(DNF) เป็นสูตรที่มีรูปแบบของการแยกตัวของคำสันธานพื้นฐาน

การแยกทางเบื้องต้น (การแยกทาง)เรียกว่าการแยกตัวของตัวแปรโดยมีหรือไม่มีการปฏิเสธ

แบบฟอร์มปกติที่เชื่อมต่อกัน(CNF) เป็นสูตรที่มีรูปแบบของจุดร่วมของการแยกย่อยเบื้องต้น

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

อัลกอริทึมสำหรับการสร้าง DNF:

1. ไปที่การดำเนินการบูลีนโดยใช้สูตรการแปลงที่เทียบเท่า

2. ไปที่สูตรที่มีการปฏิเสธใกล้เคียง นั่นคือสูตรที่มีการปฏิเสธไม่สูงกว่าตัวแปร - ใช้กฎของ De Morgan

3. เปิดวงเล็บ - ใช้กฎการกระจาย

4. ใช้เงื่อนไขซ้ำ ๆ กันทีละครั้ง - กฎแห่งความเป็นเอกภาพ

5. ใช้กฎการดูดซึมและการดูดซึมครึ่งหนึ่ง

ตัวอย่างที่ 6ค้นหาสูตร DNF: .

ในพีชคณิตแบบบูลมันเป็นความจริง หลักการของความเป็นคู่- มันเป็นดังนี้

ฟังก์ชันนี้เรียกว่า คู่ไปที่ฟังก์ชัน if เหล่านั้น. ในการค้นหาฟังก์ชันที่เป็นสองเท่าของฟังก์ชันที่กำหนด จำเป็นต้องสร้างการปฏิเสธของฟังก์ชันจากการปฏิเสธของอาร์กิวเมนต์

ตัวอย่างที่ 7ค้นหาฟังก์ชันคู่ของ

ในบรรดาฟังก์ชันเบื้องต้นของพีชคณิตของตรรกะ 1 คือคู่กับ 0 และในทางกลับกัน x คือคู่กับ x, คู่กับ , คู่และในทางกลับกัน

หากในสูตร F 1 แสดงถึงฟังก์ชันเราจะแทนที่คำสันธานทั้งหมด

การแยกส่วน, การแยกส่วนร่วม, 1 บน 0, 0 บน 1 จากนั้นเราจะได้สูตร F * แทนฟังก์ชัน * dual ถึง

รูปแบบปกติที่เชื่อมต่อกัน (CNF) เป็นแนวคิดคู่สำหรับ DNF ดังนั้นจึงสามารถสร้างได้ง่ายตามรูปแบบต่อไปนี้:

ตัวอย่างที่ 8ค้นหาสูตร CNF: .

โดยใช้ผลลัพธ์ของตัวอย่างที่ 6 เราได้

รูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบและรูปแบบปกติที่เชื่อมต่อกันที่สมบูรณ์แบบในแต่ละประเภทของรูปแบบปกติ (แบบแยกส่วนและแบบเชื่อมต่อกัน) เราสามารถแยกแยะประเภทของรูปแบบที่สมบูรณ์แบบ SDNF และ SCNF ได้

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

DNF ใดๆ สามารถลดลงเป็น SDNF ได้โดยการแยกคำสันธานที่ไม่มีตัวแปรทั้งหมด เช่น โดยการบวกตัวแปรที่หายไป x i จะถูกคูณโดยใช้กฎการกระจาย

ตัวอย่างที่ 9ค้นหา SDNF สำหรับ DNF ของตัวอย่างที่ 6

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

CNF ใด ๆ สามารถลดลงเป็น SCNF ได้โดยการเพิ่มคำร่วมที่ไม่มีตัวแปร X i ใด ๆ โดยการร่วมและใช้กฎการกระจาย

ตัวอย่างที่ 10นำ KNF มาสู่ SKNF:

ในการสร้าง SCNF คุณสามารถใช้ไดอะแกรม

ตัวอย่างที่ 11ค้นหา SCNF สำหรับสูตรของตัวอย่างที่ 6

ทุกฟังก์ชันมี SDNF และยิ่งไปกว่านั้นคือฟังก์ชันที่ไม่ซ้ำใคร แต่ละฟังก์ชันมี SCNF และยิ่งไปกว่านั้นคือฟังก์ชันที่ไม่ซ้ำใคร

เพราะ SDNF และ SKNF ถูกกำหนดไว้โดยเฉพาะโดยสูตร สามารถสร้างได้โดยใช้ตารางความจริงของสูตร

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

ในการสร้าง SCNF โดยใช้ตารางความจริง จำเป็นต้องเลือกแถวในนั้นโดยที่ F = 0 และเขียนการแยกทางเบื้องต้นที่สมบูรณ์ จากนั้นจึงเชื่อมต่อพวกมันด้วยเครื่องหมายร่วม หากในแถวที่ต้องการของตารางความจริง (F=0) ค่าของตัวแปรสอดคล้องกับศูนย์ ดังนั้นในอนุประโยคที่สมบูรณ์แบบ ค่านั้นจะถูกนำไปใช้โดยไม่มีการปฏิเสธ ถ้าเป็นหนึ่ง ก็จะมีการปฏิเสธ

ตัวอย่างที่ 12ค้นหา SDNF และ SCNF โดยใช้ตารางความจริงสำหรับสูตรตัวอย่างที่ 6

ตารางที่ 14 แสดงเฉพาะค่าสุดท้าย F=10101101 คุณควรตรวจสอบความถูกต้องของข้อความนี้ด้วยตนเองโดยสร้างตารางความจริงโดยละเอียด

ตารางที่ 14

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

หากฟังก์ชันลอจิคัลแสดงผ่านการแยกส่วน การเชื่อม และการปฏิเสธของตัวแปร รูปแบบการนำเสนอนี้จะเรียกว่าปกติ

ในบรรดารูปแบบปกติ รูปแบบปกติที่สมบูรณ์แบบนั้นมีความโดดเด่น (รูปแบบที่ฟังก์ชันเขียนในลักษณะเฉพาะ)

รูปแบบปกติที่ไม่ต่อเนื่องที่สมบูรณ์แบบ (PDNF)

คำนิยาม. สูตรเรียกว่าการรวมระดับประถมศึกษาหากเกิดขึ้นจากการรวมตัวแปรจำนวนหนึ่งหรือการปฏิเสธของตัวแปรเหล่านั้น

ตัวอย่าง: y, ฌ y, x 1 ∧ ฌ x 2 ∧ x 3 ∧ x 4

คำนิยาม. สูตรนี้เรียกว่ารูปแบบปกติที่ไม่ต่อเนื่อง (DNF) หากเป็นการแยกส่วนของคำสันธานพื้นฐานที่ไม่ซ้ำกัน

DNF เขียนในรูปแบบต่อไปนี้: F 1 ∨ F 2 ∨ ... ∨ F n โดยที่ F i คือคำเชื่อมระดับประถมศึกษา

ตัวอย่าง: ฌ x 1 ∧ x 2 ∨ x 1 ∧ ฌ x 2 ∨ x 1 ∧ ฌ x 2 ∧ x 3 , ฌ y 1 ∨ y 1 ∧ y 2 ∨ ฌ y 2

คำนิยาม. สูตรตรรกะในตัวแปร k เรียกว่า รูปแบบปกติที่ไม่ต่อเนื่องกันสมบูรณ์แบบ (PDNF) ถ้า:
1) สูตรคือ DNF ซึ่งแต่ละการรวมระดับประถมศึกษาจะเป็นการรวมของตัวแปร k x 1, x 2, ..., x k และในตำแหน่งที่ i ของการรวมนี้จะมีตัวแปร x i หรือการปฏิเสธของมัน ;
2) คำสันธานเบื้องต้นทั้งหมดใน DNF ดังกล่าวมีความแตกต่างกันแบบคู่

ตัวอย่าง: (ฌ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ฌ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ฌ x 3)

รูปแบบปกติที่เชื่อมต่อกันอย่างสมบูรณ์แบบ (PCNF)

คำนิยาม. สูตรเรียกว่าการแยกส่วนเบื้องต้น หากเกิดขึ้นจากการแยกตัวแปรจำนวนหนึ่งหรือการปฏิเสธของตัวแปรเหล่านั้น

ตัวอย่าง: ฌ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ฌ x 3

คำนิยาม. สูตรเรียกว่ารูปแบบปกติที่เชื่อมต่อกัน (CNF) หากเป็นการรวมกันของการแยกทางเบื้องต้นที่ไม่ซ้ำ

CNF เขียนในรูปแบบต่อไปนี้: F 1 ∧ F 2 ∧ ... ∧ F n โดยที่ F i คือการแยกส่วนเบื้องต้น

ตัวอย่าง: (x 1 ∨ ฌ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (ฌ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ฌ x 2 ∨ ฌ x 3)

คำนิยาม. สูตรตรรกะในตัวแปร k เรียกว่ารูปแบบปกติที่เชื่อมต่อกันอย่างสมบูรณ์แบบ (CPNF) ถ้า:
1) สูตรคือ CNF ซึ่งแต่ละการแยกย่อยเบื้องต้นคือการแยกของตัวแปร k x 1, x 2, ..., x k และในตำแหน่งที่ i ของการแยกย่อยนี้จะมีตัวแปร x i หรือการปฏิเสธ
2) การแยกส่วนเบื้องต้นทั้งหมดใน CNF ดังกล่าวมีความแตกต่างกันแบบคู่

ตัวอย่าง: (x 1 ∨ x 2 ∨ x 3) ∧ (ฌ x 1 ∨ ฌ x 2 ∨ x 3)

สังเกตว่า ฟังก์ชันลอจิคัลใดๆ ที่ไม่เท่ากันกับ 0 หรือ 1 สามารถแสดงเป็น SDNF หรือ SKNF ได้.

อัลกอริทึมสำหรับการสร้าง SDNF โดยใช้ตารางความจริง

1. เลือกแถวตารางทั้งหมดที่มีค่าฟังก์ชันเท่ากับหนึ่ง
2. สำหรับแต่ละบรรทัด ให้เขียนการรวมตัวแปรทั้งหมดดังนี้: หากค่าของตัวแปรบางตัวในชุดนี้เท่ากับ 1 เราจะรวมตัวแปรนั้นไว้ในการร่วม ไม่เช่นนั้น จะเป็นค่าปฏิเสธ
3. เราเชื่อมต่อคำสันธานผลลัพธ์ทั้งหมดกับการดำเนินการแยกกัน

อัลกอริทึมสำหรับการสร้าง SCNF โดยใช้ตารางความจริง

1. เลือกแถวตารางทั้งหมดที่มีค่าฟังก์ชันเป็นศูนย์
2. สำหรับแต่ละบรรทัด ให้เขียนการแยกตัวของตัวแปรทั้งหมดดังนี้: ถ้าค่าของตัวแปรบางตัวในชุดนี้เท่ากับ 0 เราจะรวมตัวแปรนั้นไว้ในการร่วม ไม่เช่นนั้น จะเป็นค่าปฏิเสธ
3. เราเชื่อมโยงการแยกส่วนที่เกิดขึ้นทั้งหมดเข้ากับการดำเนินการร่วม

การวิเคราะห์อัลกอริธึมแสดงให้เห็นว่าหากค่าของฟังก์ชันเป็น 0 ในแถวส่วนใหญ่ของตารางความจริง ดังนั้นเพื่อให้ได้สูตรเชิงตรรกะ จะดีกว่าถ้าสร้าง SDNF มิฉะนั้น - SCNF

ตัวอย่าง: ให้ตารางความจริงของฟังก์ชันลอจิคัลของตัวแปร 3 ตัวมา สร้างสูตรตรรกะที่ใช้ฟังก์ชันนี้

เพราะ ในแถวส่วนใหญ่ของตารางความจริง ค่าของฟังก์ชันคือ 1 จากนั้นเราจะสร้าง SCNF เป็นผลให้เราได้สูตรตรรกะต่อไปนี้:
F = (ฌ x ∨ y ∨ z) ∧ (ฌ x ∨ y ∨ ฌ z)

ลองตรวจสอบสูตรผลลัพธ์ เพื่อทำเช่นนี้ เราจะสร้างตารางความจริงของฟังก์ชัน

เมื่อเปรียบเทียบตารางความจริงดั้งเดิมกับตารางที่สร้างขึ้นสำหรับสูตรตรรกะ เราสังเกตว่าคอลัมน์ของค่าฟังก์ชันตรงกัน ซึ่งหมายความว่าฟังก์ชันลอจิคัลถูกสร้างขึ้นอย่างถูกต้อง