Implicants на булева функция

Решение на проблема за минимизиране на Булева функция от Куайн и подобрен метод Куайн Mc-KLASCO се основава на концепциите за implicants и техните системи.

Определение. Булева функция г (X), наречена implicant булева функция е (X), ако за всеки даден набор от аргументи, на която г (X) = 1, F (X) също е равен на единица.

1) Между implicant и самата функция съществува включване връзка г (X)Ì F (X).

2) Може да се твърди, че за всеки набор от аргументи, на които функцията е нула, то implicant също е нула.

3) Когато г (X) и к (X) са implicants функция е (X), след това им дизюнкция също implicant тази функция.

Най-простият Примерите implicants съединителната условия могат да бъдат включени в произволна функция на DNP.

Произволен дизюнкция на тези условия е също implicant функция.

Opredelenie.Prostoy (първична) implicant Булева функция се нарича конюнктива термин, който от своя страна е implicant тази функция, но не е част от неговия собствен, вече не е implicant тази функция.

Определение. Съгласно правилното част на понятието се отнася до нов термин, получени от изходните, чрез изтриване на произволен брой символи.

За този пример, функцията (#) председатели implicants са:

Комплект председатели implicants може да бъде свързана с набор от максимални кубчета.

Определение. Разделение на всички председатели implicants на булева функция е DNF тази функция, която се нарича съкратена - PDNF.

За функцията (#) от пример PDNF на:

Концепцията за "намаляване" е отличен със DNF в смисъл, че тя обикновено съдържа по-малко букви и думи в сравнение с KDNF. За нашия пример KDNF съдържа 15 букви и 5 условия, както и PDNF - 8 букви и 4 термин.