97. Мднф. Импликанта булевой фенкции. Основное свойство импликанты. Импликанта, покрывающая единицу булевой функции.

Минимальная ДНФ - это ДНФ, имеющая наименьшее среди всех число вхождений переменных. МДНФ может быть одна или несколько.

Это цель задачи минимизации. Минимальная ДНФ - это самая простая ДНФ, которая может быть у функции. На ее основе можно строить достаточно простые (по количеству элементов) схемы, реализующие функцию.

Функция f, зависящая от n переменных x₁, x₂, ...., x_n, называется булевой, или переключательной, если функция f и любой из ее аргументов X_i, (i E 1..n) принимают значения только из множества {О, 1}. Аргументы булевой функции также называются булевыми.

Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.При матричном способе булева функция f (х₁, ...,х_n) задается таблицей истинности (табл. 1.1 и 1.2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

При геометрическом способе булева функция f (х₁, ..., х_n) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор у = <y₁, y₂,...,y_n> y_i E {0,1} есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции. Например, булева функция, заданная табл. 1.1, геометрически представляется 3-мерным кубом (рис. 1).

При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры. Аналитический способ задания булевых функций занимает особое место в проектировании цифровых автоматов. Фактически, все преобразования над булевыми функциями, необходимые для построения цифровых автоматов, ведутся на аналитическом уровне.

Определение. Булева функция g(x₁,...,x_n) называется импликантой булевой функции f(x₁,...,x_n), если для любого набора переменных, на котором g=1, справедливо f=1.

Система импликант булевой функции называется полной, если каждая единица БФ покрывается импликантой из этой системы.

Свойства импликант : 1) Между импликантой и самой функцией существует отношение включения g(x)Ìf(x). 2) Можно утверждать, что для любого набора аргументов, на котором функция равна нулю, ее импликанта также равна нулю. 3) Если g(x) и j(x) являются импликантами функции f(x), то их дизъюнкция также является импликантой этой функции.

Простейшими примерами импликант могут служить конъюнктивные термы, входящие в ДНФ данной функции.

Произвольная дизъюнкция этих термов также является импликантой функции.

Определение : Простой (первичной) импликантой булевой функции называется конъюнктивный терм, который сам является импликантой этой функции, но никакая его собственная часть уже не является импликантой этой функции.

Под собственной частью терма понимается новый терм, полученный из исходного, путем вычеркивания произвольного числа букв.