Нормальные формы логических функций

Определение. Полной конъюнкцией n переменных называется конъюнкция состоящая из n переменных или их отрицаний, в которой каждая переменная встречается только один раз.

Например, x_{1 2} x₃, ₁ x_{2 3} - полные конъюнкции трех переменных.

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

Для функции n переменных СДНФ имеет вид:

f( x₁,x₂,…,x_n ) = x x … x , (1.7)

где s – равно значению переменной x в любом наборе значений переменных, для которого значения функций равно 1, причем

для любой логической функции существует единственное представление ее в виде (1.7). Покажем, как найти СДНФ на следующем примере.

Пример. Представить функцию f( x₁,x₂,x₃ ), заданную табл. 1.15 в СДНФ.

Таблица 1.15

Из табл.1.15 видно, что f( x₁,x₂,x₃ ) = 1 будет для второй, третьей, пятой и восьмой строк.

Для второй строки x₁ = 0, x₂ = 0, x₃ = 1,

поэтому s₁ = 0, s₂ = 0, s₃ = 1.

Значит, полная конъюнкция для второй строки будет иметь вид:

= x₁º x₂º x₃¹ = x₃.

Для третьей, пятой и восьмой строк полные конъюнкции соответственно будут имеет вид:

x₁º x₂¹ x₃º , x₁¹ x₂º x₃º , x₁¹ x₂¹ x₃¹ .

Тогда согласно (1.7) СДНФ данной функции будет иметь вид:

f( x₁,x₂,x₃ ) = x₃ x₂ x₁ x₁ x₂ x₃.

Определение. Полной дизъюнкцией n переменных называется дизъюнкция состоящая из n переменных или их отрицаний, в которой каждая переменная встречается только один раз.

Например, x₁ x₃, x₂ x₃ - полные дизъюнкции трех пере-менных.

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

Для функции n переменных СКНФ имеет вид:

f( x₁, x₂, …, x_n ) = & ( ), (1.8)

f(s , …, s )=0

где _i – равно противоположному значению переменной x_i , в любом наборе перемен-

ных, для которого значение функции равно нулю.

для любой логической функции существует единственное представление ее в виде (1.8). Покажем, найти СКНФ на следующем примере.

Пример. Представить функцию f( x₁, x₂, x₃ ), заданную табл. 1.15 в СКНФ.

Из табл.1.15 видно, что f( x₁, x₂, x₃ ) = 0 будет для первой, четвертой, шестой и седьмой строк.

Для первой строки x₁ = 0, x₂ = 0, x₃ = 0,

поэтому = 1, = 1, = 1.

Следовательно, полная дизъюнкция для первой строки будет иметь вид:

= x₁¹ x₂¹ x₃¹ = x₁ x₂ x₃.

Для четвертой, шестой и седьмой строк полные дизъюнкции соответственно будут иметь вид:

x₁¹ x₂º x₃º , x₁º x₂¹ x₃º ,

x₁º x₂º x₃¹ .

Тогда согласно (1.8) СКНФ данной функции будет иметь вид:

f( x₁, x₂, x₃ ) = ( x₁ x₂ x₃ )( x_{1 2 3} )( ₁ x_{2 3} )( _{1 2} x₃ ).

Переход от СДНФ к СКНФ

Этот переход можно сделать по следующему правилу:

1) Образовать логическую сумму дизъюнктивных членов, не входящих в СДНФ функции;

2) В полученном выражении заменить символы дизъюнкций на символы конъюнкций и наоборот, аргументы x_i на их отрицания , а на .

Пример. Для данной функции

f( x₁,x₂,x₃ ) = ₁ x_{2 3} x_{1 2} x₃ x₁ x_{2 3},

представленной в форме СДНФ, составить СКНФ.

Обозначим через К_i полную конъюнкцию трех переменных для i-ой строки таблицы задания функции.

Например, для второй строки К₂ = x₁º x₂º x₃¹ = .

Тогда заданную функцию можно записать в следующем виде:

f( x₁, x₂, x₃ ) = x₁º x₂¹ x₃º x¹₁ xº₂ x¹₃ x¹₁ x¹₂ xº₃ = K₃ K₆ K₇.

Образуем логическую сумму дизъюнктивных членов, не входящих в СДНФ функции. Эта сумма будет иметь вид:

K₁ K₂ K₄ K₅ K₈ = x₁º xº₂ xº₃ xº₁ xº₂ x¹₃ xº₁ x¹₂ x¹₃ x¹₁ xº₂ xº₃ x¹₁ x¹₂ x¹₃=

= x₃ x₂ x₃ x₁ x₁ x₂ x₃.

Меняя в данном выражении символы на & и наоборот, а аргументы на их отрицания и наоборот, получим искомую СКНФ для заданной функции:

f( x₁,x₂,x₃ ) = ( x₁ x₂ x₃ )( x₁ x₂ )( x₁ )( x₂ x₃ )( ).

Переход от СКНФ к СДНФ

Этот переход осуществляется аналогично по следующему правилу:

1) Образовать логическое произведение конъюктивных членов, не входящих в СКНФ функции.

2) В полученном выражении нужно заменить символы & на , на &, аргументы x_i на , на x_i.

Пример. Для функции предыдущего примера составить СДНФ по найденной СКНФ.

Обозначим через D_i полную дизъюнкцию для i-ой строки таблицы задания данной функции.

Например, для третьей строки таблицы значения переменных ( 0,1,0 ). Следовательно, ₁ = 1, ₂ = 0, ₃ = 1.

Тогда полная дизъюнкция для третьей строки будет такая:

D₃ = = x_{1 2} x₃.

Учитывая сделанное обозначение, запишем найденную в предыдущем примере СКНФ в следующем виде:

f(x₁,x₂,x₃) = (x₁¹ x₂¹ x₃¹)( x₁¹ x₂¹ x₃º )( x₁¹ x₂º x₃º )( x₁º x₂¹ x₃¹ )( x₁º x₂º x₃º).

Учитывая, что верхние индексы при переменных в этом выражении, согласно (1.8) равны противоположному значению переменной, то получим следующие наборы значений переменных, входящие в это выражение:

( 0, 0, 0 ), ( 0, 0, 1 ), ( 0, 1, 1 ), ( 1, 0, 0 ) и ( 1, 1, 1 ).

Эти наборы переменных соответствуют 1, 2, 4, 5 и 8 строкам таблицы задания функции. Следовательно, СКНФ функции можно переписать так:

f( x₁,x₂, x₃ ) = D₁∙ D₂ ·D₄ ·D₅ ·D₈.

Из этой записи видно, что в СКНФ не входят полные дизъюнкции 3, 6 и 7 строк.

Образуем логическое произведение из этих дизъюнкций:

D₃∙D₆ D₇ = ( x₁¹ x₂º x₃¹ )( x₁º x₂¹ x₃º )( x₁º x₂º x₃¹ ) =

= ( x_{1 2} x₃ )( _X )( ₂ x₃ ).

Меняя в этом выражении & на , на & а аргументы на их отрицания и наоборот, получим СДНФ для заданной функции:

f( x₁, x₂,x₃ ) = x_{2 3} x_{1 2} x₃ x₁ x_{2 3}.

Сравнивая это выражение с СДНФ функции предыдущего примера, видим, что они одинаковые, что и должно быть т.к. f( x₁,x₂,x₃ ) – одна и та же для этих примеров.

Определение. Дизъюнктивной нормальной формой (ДНФ) логической функции называется дизъюнкция разных конъюнкций, которые не все являются полными.

Например, f( x,y,z) = x x z x z y.

Любую ДНФ можно привести к СДНФ “ расщеплением” конъюнкций, которые не являются полными.

Пример. Привести к СДНФ следующую ДНФ функции: x y x z.

В данной ДНФ конъюнкция xy не является полной, т.к. не содержит переменной z . Учитывая, что z = 1 преобразуем ДНФ следующим образом:

xy(z ) x z = xyz xy x z.

Полученная форма и есть искомая СДНФ.