Определение. G implicants на булева функция е. е елементарен връзка се нарича просто, ако не е част от implicants г не е implicant функция е.
Примерът показва, че implicants и. Те са сред първите, implicants на ф. Implicants G1. g2. G4. g6 не са прости, защото те са implicants на функция F. например G5 е част G1. Заявяваме, без доказателство две предложения, които са полезни в подготовката на минималната DNF.
1. дизюнкция произволен брой implicants на булева функция е също implicant тази функция.
2. Всяко Булева функция е е еквивалентно на дизюнкцията на всички свои председатели implicants. Тази форма на представяне на булева функция се нарича понижено DNF.
Търсене на всички възможни implicants на булева функция е в горния пример дава възможност да се гарантира, че основните implicants са само две: G3 и G5 .Sledovatelno, съкратено DNF на функцията F е в следния формат:
Както се вижда от таблица. 1 implicants G3. G5 заедно покриване на единици, всички единици функция F. Първи съкращение DNP е първата стъпка в намирането на минимални форми на булеви функции. Както вече споменахме, в съкратен DNF се състои от всички председатели implicants на булева функция. Понякога поради намаленото DNF може да премахне един или повече председатели implicants без да се скъса на равностойността на оригиналната функция. Такива прости implicants наричат излишни. Премахване на излишни председатели implicants на съкращение DNF - на втория етап от минимизиране.
Определение. Съкратено DNF на булева функция се нарича терминал, ако няма допълнителни прости implicants.
Премахване на излишни председатели implicants на намалената DNF на булева функция не е прост процес, т.е.. Функция Е. Булева може да има няколко безизходица DNF.
Одобрение. Deadlock DNF на булева функция е. съдържаща минимален брой писма, са минимални. Минимална DNF може да бъде и много други.
Разполагате с няколко методи за свеждане до минимум. Всички те са на практика се различават само в първия етап - етапа на получаване на намалената DNF. Трябва да се отбележи, че, за съжаление, търсенето на минималния DNF винаги е свързано с някои груба сила решения. Има методи за намаляване на това изброяване, но винаги остава.
метод Куайн се базира на използването на две основни отношения.
1. Степента на свързване
където А - всеки елементарен продукт.
2. усвояване Ratio
Валидността на двете съотношения лесно да бъде проверен. Методът се състои в последователното изпълнение на всички възможни залепване и след това всички придобиване, което води до скъсен DNF. Методът е приложим за перфектен DNF. От съотношението на усвояване предполага, че произволно начално продукт се абсорбира от който и да е част от него.
Достатъчно е да се покаже, че произволно председатели implicants могат да бъдат получени. В действителност, прилагането на операция стр разгръщане (обратна операция свързване):
всички липсващи променливи на оригиналната функция F, които получаваме набор от S съставки на единство. При поставяне на всички съставки на S получи implicant стр. Последното е очевидна, тъй като операцията на свързване е на обратната страна на операцията на разгръщане. Комплектът S съставки задължително присъстват в перфектни функции F DNP от р - това implicant.
Пример. Да бъде Булева функция дадена истина маса (табл. 9.12). PDNF изглежда:
За удобство да маркират всяка съставна единица на функцията е PDNF всяко десетично число (произволен). Извършване на свързване. 1 само съставна залепени с съставна част 2 (променливата) 3 и съставка (променливата), съставка на съставния 2 и 4 м. D.
Резултатът е
Имайте предвид, че резултатът винаги е свързването елементарни ПРОИЗВОДСТВО denie, която е обща част от залепени избиратели.
На следващо място, които взимаме в залепване получи на основните продукти. Залепени само на онези продукти, които съдържат същите променливи. В момента има два случая на свързване:
с появата на едни и същи елементарни парчета Допълнителна лепене-Bani невъзможно. Извършване на поглъщане (DNP зачеркнете от получената абсорбира всички елементарни работа), ние получаваме кондензирано DNP:
Ние се пристъпи към втория етап. За минимален DNF трябва да бъде отстранен от всички допълнителни съкращение ИЕЯС прости implicants на. Това се прави с помощта на специален implikantnoy Куайн матрица. Редици от тази матрица се отбелязват чрез прости implicants на булева функция, т.е., членове на понижено DNF и колони - .. съставки възел, т.е. членове PDNF булева функция ...
Пример (продължение). Implikantnaya матрица има формата (таблица. 3).
Както вече бе отбелязано, основните implicants поглъща някои съставки на единство, ако то е собствената й част. Сажди лзвани implikantnoy матрица клетка в пресечната точка на ред (считано от основните implicants) и колона (с съставна единица) се маркира с кръст (таблица. 3). Минимум DNP implikantnoy конструира чрез матрица, както следва:
1) колони са избраните implikantnoy матрици, които имат само един кръст. Съответстващи на тези кръстове са прости implicants наречените основни и форма т.нар ядро на булева функция. Kernel задължително включени в минималния DNF.
2) обсъждат различни избор използва множество прости implicants които ще определят кръстоски оставащата след gical implikantnoy матрица и избрани от вариантите
минималния общ брой на знаците в набор от implicants.
Пример (продължение). В основата на нашите функции са implicants; .Implikanta - излишно, тъй като в основата на колоните обхваща всички implicants план матрица. Следователно, функцията има уникален безизходица и минимално DNF:
Трябва да се отбележи, че редица N на кръстове в един ред винаги е с мощност от 2. Освен това, читателят може лесно да се провери, че
,където к - броят на писма, съдържащи се в основните implicants.
Имайте предвид също така, че се използват различни съотношения, е възможно да се разшири "в обхвата на метода Куайн отвъд перфектен DNF.
Пример. Минимизиране булева функция е от Quine:
1. Премахване на негативите и скобите, използвайки горните зависимости
2. Възстановяване PDNF функция е, като се използва действието на разгръщане
3. Ние ще намерите съкратен DNF функция е, производство на всички възможни лепене PDNF на
4. търси минимум DNP функция е за матрица implikantnoy (раздел. 4). В основата на булеви функции. .Minimalnye DNF:
Свързани статии