Кнф конъюнкти́вная норма́льная фо́рма

1. Пример нахождения СДНФ
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К 
примеру, возьмём одну из таблиц истинности статьи Минимизация логических функций методом 
Квайна, в которой нахождение 
СДНФ
встречается несколько раз: 
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 
1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 
В ячейках строки́ 
отмечаются лишь те комбинации, которые приводят 
логическое выражение в состояние единицы. 
Далее рассматриваются значения переменных при которых функция равна 1. Если значение 
переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без 
инверсии. 
Первый столбец содержит 
1
в указанном поле. Отмечаются значения всех четырёх переменных, 
это: 
•
= 0 
•
= 0 
•
= 0 
•
= 0 
Нулевые значения — тут все переменные представлены нулями — записываются в конечном 
выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит 
так: 
Переменные второго члена: 
•
= 0 
•
= 0 
•
= 0 
•
= 1 
в этом случае будет представлен без инверсии: 
Таким образом анализируются все ячейки 
. Совершенная ДНФ этой функции 
будет дизъюнкцией всех полученных членов (элементарных конъюнкций). 
Совершенная ДНФ этой функции: 

---

Гомоморфизмы алгебраических систем
Пусть 
и 
— две однотипные алгебраические 
системы.
Отображение 
называют гомоморфизмом алгебраической системы в 
алгебраическую систему , если выполняются следующие условия:
1) для любой n-арной операции 
и любых элементов 
2) 
для любого n-арного отношения 
и любых 
элементов 
из того, что 
, следует, 
что 
.
Мы будем использовать обозначение 
для отображения , 
являющегося гомоморфизмом алгебраической системы 
в 
алгебраическую систему 
.
В определении гомоморфизма первое условие, которое можно рассматривать как 
условие "сохранения операций", означает следующее. Если отображение — 
гомоморфизм, то, вычисляя образ результата применения любой операции 
к 
любому кортежу аргументов из носителя алгебраической системы , т.е. образ 
произвольного элемента 
, мы можем сначала определить образ каждого 
из аргументов и уже к ним, т.е. к элементам 
, на носителе 
алгебраической системы применить рассматриваемую операцию (точнее, 
операцию второй алгебраической системы, которая соответствует операции ; 
напомним, что соответствующие друг другу операции и отношения однотипных 
алгебраических систем мы договорились обозначать одинаково). Эта ситуация 
проиллюстрирована на рис. 4.2. 
Второе условие в определении гомоморфизма выражает "сохранение отношений": 
если элементы 
первой алгебраической системы связаны отношением , 
т.е. 
, то их образы 
при 
гомоморфизме связаны "тем же"* отношением во второй алгебраической системе, 
т.е. 
.
*
Точнее, так же обозначенным. Заключая слова "тем же" в кавычки, мы еще раз 
подчеркиваем условность одинакового обозначения операции и отношений 
однотипных алгебраических систем. 
Заметим сразу, что из того, что 
, не следует, вообще 
говоря, что 
. Если же это имеет место, т.е. для всякого n-арного 
отношения 
и любых 
тогда и только 

---

тогда, когда 
, то такой гомоморфизм называют строгим 
гомоморфизмом.
Если строгий гомоморфизм алгебраической системы в алгебраическую 
систему является биекцией 
, то его называют изоморфизмом. Из 
определения изоморфизма следует, что для изоморфизма 
обратное 
отображение 
также является изоморфизмом. В этом случае 
алгебраические системы и называют изоморфными и пишут 
. Если 
алгебраические системы интересуют нас лишь со стороны свойств их операций и 
отношений, то изоморфные алгебраические системы в этом смысле не различимы, и 
тогда говорят о совпадении алгебраических систем с точностью до изоморфизма.
Если гомоморфизм является инъекцией, то его называют мономорфизмом или 
вложением. В том случае, когда существует вложение алгебраической системы в 
алгебраическую систему , которое является также строгим гомоморфизмом, то 
говорят, что первая алгебраическая система изоморфно вкладывается во вторую.
Если гомоморфизм 
является сюръекцией, то его называют 
эпиморфизмом на . При эпиморфизме носитель алгебраической 
системы совпадает с образом носителя алгебраической системы при 
отображении , то есть 
. В этом случае говорят также, что алгебраическая 
система является гомоморфным образом системы при гомоморфизме , и 
записывают это как 
.
Гомоморфизм алгебраической системы в себя 
называют эндоморфизмом алгебраической системы . Эндоморфизм, являющийся 
изморфизмом, называют автоморфизмом.
Легко доказать следующее утверждение.