Нормальные формы логических функций
Определение. Полной конъюнкцией n переменных называется конъюнкция состоящая из n переменных или их отрицаний, в которой каждая переменная встречается только один раз.
Например, x1
2 x3,
1
x2 3 - полные конъюнкции трех переменных.
Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) логической функции называется формула, представляющая данную функцию, и имеющая вид дизъюнкции полных конъюнкций, которые формируются для наборов переменных при которых функция равна 1.
Для функции n переменных СДНФ имеет вид:
f( x1,x2,…,xn ) = 
x
x
… x
, (1.7)
где s
– равно значению переменной x в любом наборе
значений переменных, для которого значения функций равно 1, причем
для любой логической функции существует единственное представление ее в виде (1.7). Покажем, как найти СДНФ на следующем примере.
Пример. Представить функцию f( x1,x2,x3 ), заданную табл. 1.15 в СДНФ.
Таблица 1.15
предыдущаяследующая