Правила записи фал в сднф и скнф

В СДНФ функция f(хn,…,х1) представляется в виде дизъюнкции функций, которые называются конституентами единицы. Конституента единицы имеет также другие названия: характеристическая функция единицы, минтерм.

Конституента единицы – это ФАЛ n переменных, которая равна единице только на одном наборе переменных. На остальных наборах конституента единицы равна нулю.

Число различных конституент единицы среди функций n переменных равно правила записи фал в сднф и скнф - student2.ru , т.е. числу различных наборов n переменных. Конституенту единицы будем обозначать буквой m с индексом, равным номеру набора, на котором конституента единицы равна единице. Обычно конституенты единицы выражают в виде конъюнкции всех переменных, каждая из которых входит в конъюнкцию один раз в прямой или инверсной форме.

Конституенту единицы mi в виде конъюнкции n переменных получают следующим образом: записывают конъюнкцию n переменных, располагая последние в определенной последовательности, например, начиная с переменной с наибольшим номером, и двоичное n-разрядное число, равное i; над переменными, позиции которых совпадают с позициями нулей в двоичном числе i, ставят знаки отрицания.

Пример 1. Записать конституенту единицы m27, n=6.

Записываем 6-разрядное двоичное число, равное 27: 27{10) = 011011(2) и конъюнкцию шести переменных, начиная со старшей переменной х6: x6x5x4x3x2x1. Из записи двоичного числа 011011 следует, что знаки отрицания нужно поставить над шестой и третьей переменными: m27 = правила записи фал в сднф и скнф - student2.ru 6х5х4 правила записи фал в сднф и скнф - student2.ru 3х2х1.

Дизъюнкция конституент единицы, равных единице на тех же наборах, что и заданная функция, называется СДНФ ФАЛ.

Любая ФАЛ f(xn,…,x1), кроме константы нуль, может быть представлена в СДНФ:

f(xn,…,x1) = mj1Úmj2Ú…Úmjl, (1)

где j1, j2,…, jl– номера наборов, на которых ФАЛ равна единице; l– число таких наборов, на которых ФАЛ равна единице.

Справедливость соотношения (1) вытекает из того, что каждая единица функции f(xn,…,x1) в ее СДНФ представляется конституентой единицы с соответствующим номером. Из соотношения (1) следует, что любая ФАЛ имеет единственную СДНФ.

Структура СДНФ такова, что на произвольном наборе переменных в правой части соотношения (1) или все конституенты единицы равны нулю, если функция на этом наборе равна нулю, или только одна из конституент единицы равна единице, а остальные равны нулю, если функция на этом наборе равна единице. Поэтому справедливость соотношения (1) сохранится, если в нем знак дизъюнкции заменить на знак сложения по модулю два:

f(xn,…,x1) = mj1 Åmj2Å…Åmjl. (2)

Представление ФАЛ в виде (2) называют совершенной полиномиальной нормальной формой (СПНФ).

Любая ФАЛ может быть задана таблицей ее значений в зависимости от значений переменных. Переход от табличного представления ФАЛ к алгебраическому в виде СДНФ выполняют в такой последовательности:

-записывают ряд конъюнкций всех переменных и соединяют их знаками дизъюнкции; количество конъюнкций равно числу наборов, на которых заданная ФАЛ равна единице;

-под каждой конъюнкцией записывают набор переменных, на котором ФАЛ равна единице; над переменными, равными нулю в этом наборе, ставят знаки отрицания.

Это правило называют правилом записи ФАЛ по единицам, т.е. по единичным значениям функции.

Пример 2. Представить функцию φ(x3, x2, x1), заданную табл. 1, в СДНФ.

Так как функция φ(x3, x2, x1) трех переменных принимает значение, равное единице, на четырех наборах переменных, то записываем четыре конъюнкции трех переменных, объединенные знаком дизъюнкции, и под каждой конъюнкцией – соответствующие наборы переменных:

x3x2x1 Úx3x2x1 Úx3x2x1Úx3x2x1

0 1 0 1 0 0 1 0 1 1 1 1.

Расставляя знаки отрицания над переменными, равными нулю в каждом наборе, получим:

правила записи фал в сднф и скнф - student2.ru

Пример 3. Представить функцию штрих Шеффера f14(x2, x1) в СДНФ.

Функция f14(x2, x1) равна единице на трех наборах переменных: 0,0; 0,1 и 1,0. Поэтому правила записи фал в сднф и скнф - student2.ru .Эту форму функции f14(x2, x1) можно преобразовать и привести к принятой записи:

правила записи фал в сднф и скнф - student2.ru

правила записи фал в сднф и скнф - student2.ru

В СКНФ заданная ФАЛ f(xn, …, x1) представляется в виде конъюнкции функций, которые называются конституентами нуля. Конституента нуля имеет также другие названия: характеристическая функция нуля, макстерм.

Конституента нуля – это ФАЛ n переменных, которая равна нулю только на одном наборе переменных. Число различных конституент нуля равно правила записи фал в сднф и скнф - student2.ru , т.е. числу различных наборов переменных. Конституенты нуля будем обозначать буквой М с индексом, равным номеру набора, на котором конституента нуля равна нулю. Обычно конституенты нуля выражают в виде дизъюнкции всех переменных, каждая из которых входит в дизъюнкцию в прямой или инверсной форме.

Конституенту нуля Мi в виде дизъюнкции n переменных получают следующим образом:

-записывают дизъюнкцию n переменных и двоичное n-разрядное число, равное i;

-над переменными, позиции которых совпадают с позициями единиц в двоичном числе i, ставят знаки отрицания.

Пример 4. Записать конституенту нуля М27, n=6.

Запишем дизъюнкцию шести переменных, начиная с первого: x6Úx5Úx4Úx3Úx2Úx1 и 6-разрядное двоичное число, равное 27: 27(10) = 011011(2). Расставляя знаки отрицания над первой, второй, четвертой и пятой переменными, получим конституенту нуля правила записи фал в сднф и скнф - student2.ru

Конъюнкция конституент нуля, равных нулю на тех же наборах, что и заданная функция, называется СКНФ ФАЛ.

Любая ФАЛ, кроме константы единицы, может быть представлена в СКНФ

f(xn,…,x1) = Mj1×Mj2×… ×Mjl, (3)

где j1, j2, …, jl – номера наборов, на которых функция равна нулю; l – число таких наборов.

Справедливость соотношения (3) следует из того, что каждый нуль функции f(xn,…,x1) в ее СКНФ представляется конституентой нуля с соответствующим номером, которая обращает функцию на данном наборе в нуль. Из соотношения (3) следует, что любая ФАЛ имеет единственную СКНФ.

Структура СКНФ такова, что на произвольном наборе переменных в правой части соотношения (3) или только одна конституента нуля равна нулю, а остальные равны единице, если функция на этом наборе равна нулю; или все конституенты нуля равны единице, если функция на этом наборе равна единице. Так как на любом наборе переменных одновременное равенство нулю двух и более конституент нуля исключено, то справедливость соотношения (3) сохранится, если в нем знак конъюнкции заменить на знак эквивалентности:

f(xn, …, x1) = Mj1ºMj2ºMº…ºMjl. (4)

Совершенная форма в виде (4) не имеет установившегося названия. Переход от табличного представления ФАЛ к алгебраическому в виде СКНФ выполняют в такой последовательности:

-записывают ряд дизъюнкций всех переменных и объединяют их знаком конъюнкции; количество дизъюнкций равно числу наборов, на которых заданная ФАЛ равна нулю;

-под каждой дизъюнкцией записывают набор переменных, на котором функция равна нулю;

-над переменными, которые в данном наборе равны единице, ставят знаки отрицания

Так как функция f(x3, x2, x1) равна нулю на пяти наборах переменных (табл. 1), то записываем пять дизъюнкций трех переменных и объединяем их знаком конъюнкции; под дизъюнкциями записываем наборы, на которых функция равна нулю:

(x3Úx2Úx1)(x3Úx2Úx1)( x3Úx2Úx1)( x3Úx2Úx1)( x3Úx2Úx1)

0 0 0 0 1 0 1 0 0 1 1 0 1 1 1.

Поставив знаки отрицания над переменными, равными единице, получим:

f(x3, x2, x1) = (x3 ˅ x2 ˅ x1)( x3 ˅ правила записи фал в сднф и скнф - student2.ru

Пример 5. Представить функцию стрелка Пирса f8(x2, x1) в СКНФ.

Функция f8(x2,x1) равна нулю на трех наборах переменных: 0,1; 1,0 и 1,1. Поэтому правила записи фал в сднф и скнф - student2.ru

СКНФ функции f8(x2,x1) можно преобразовать к виду:

правила записи фал в сднф и скнф - student2.ru

Отметим, что по определению правила записи фал в сднф и скнф - student2.ru , т.е. конституенты нуля и единицы, имеющие одинаковые индексы, инверсны друг другу. Например, правила записи фал в сднф и скнф - student2.ru Действительно, так как, М11 =

= правила записи фал в сднф и скнф - student2.ru 11 = правила записи фал в сднф и скнф - student2.ru , то, согласно правилу де Моргана, справедливо равенство правила записи фал в сднф и скнф - student2.ru СДНФ называют формой И/ИЛИ, что говорит о том, что в данной форме внутренней операцией является конъюнкция (И), а внешней – дизъюнкция (ИЛИ). СКНФ называют формой ИЛИ/И, в которой внутренняя операция – дизъюнкция, а внешняя - конъюнкция. Внутренняя операция выполняется первой, а внешняя – последней.

Наиболее широкое распространение получили базисы ФАЛ И-НЕ и ИЛИ-НЕ. Логические элементы И-НЕ и ИЛИ-НЕ являются базовыми (основными) в сериях интегральных схем (ИС) ДТЛ, ТТЛ, ТТЛШ, ЭСЛ, КМОП-логики. Поэтому после нахождения минимальных ДНФ и КНФ часто возникает необходимость представления этих форм в базисах функций И-НЕ и ИЛИ-НЕ.

Наши рекомендации