Упражнения.

1. Чему равно число различных логических функций трех переменных?

2. Представить префиксные формулы логических функций трех переменных f(x₁; x₂; x₃) в инфиксной форме, если f₁ - , f₂ - &, f₃ - , f₄ – 1;

1. f₁ (x₃, f₃ (x₁, f₂ (f₄(x₁), x₂)));

2. f₃ (f₁ (x₃, x₁), f₂ (x₁, f₃ (x₁, f₄ (x₂))));

3. f₃ (f₄ (x₁), f₁ (x₂, f₂ (x₃, f₃ (x₁, f₄ (x₃)))));

Вычислить f на наборах значений: а) (0, 1, 1), б) (1, 0, 1).

3. Вычислить f на наборах а) (0, 1, 0), б) (1, 1, 0) значения функций f(x₁, x₂, x₃):

1. (x₁ ≈ x₂) ((x₁ & x₃) x₂);

2. ((x₃ ) & x₂) (x₁ x₃);

3. ((x₂ x₃) & x₁) ≈ ((x₁ x₃) x₂);

4. Доказать справедливость следующих соотношений:

а) x (y z)= (x y) z (ассоциативность дизъюнкции);

б) x (y z)= (x y) z (ассоциативность конъюнкции);

в) x ( ) y z = x y z;

г) x (y z) = x y x z (дистрибутивность конъюнкции относительно дизъюнкции);

д) x (y z) = (x y) (x z) (дистрибутивность дизъюнкции относительно конъюнкции);

e) x x = x;

ж) x x y = x;

5. Построением таблиц истинности подтвердить справедливость вышеприведенных правил.

2.7. Упрощение д.Н.Ф. Тупиковые (относительно упрощения) д.Н.Ф.

Пусть R – произвольная д.н.ф. и R=R' V K; R=R' V K', где К – некоторая элементарная конъюнкция из R, R' – д.н.ф., образованная из остальных конъюнкций, - некоторый множитель из К, К' – произведение остальных сомножителей.

Рассматриваются 2 типа преобразований д.н.ф.

1. Операции удаления элементарной конъюнкции.

Переход от д.н.ф. R к д.н.ф. R' – преобразование, осуществляемое путем удаления К. Определена операция тогда и только тогда, когда R'=R.

2. Операции удаления множителя.

Переход от д.н.ф. R к д.н.ф. R'VK' – преобразование, осуществляемое путем удаления . Преобразование осуществляется тогда и только тогда, когда R'VK'=R.

Определение. Д.Н.Ф. R, которую нельзя упростить при помощи преобразований 1 и 2, называется тупиковой д.н.ф. относительно преобразований 1 и 2.

Нетрудно видеть, что среди тупиковых д.н.ф. функций

f(x₁, …, x_n) всегда содержатся и минимальные, возможно, правда, не все.

Пример. f(x₁, x₂, x₃)

Таблица 12

x1	x2	x3	f(x1, x2, x3)
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

В качестве исходной возьмем совершенную д.н.ф.

R = V x₃ V x₂x₃ V x₁ V x₁x₂ V x₁x₂x₃

R = V x₃ V x₂x₃ V x₁ V x₁x₂ V x₁x₂x₃ =

= V x₂x₃ V x₁ =R'

V x₃ V x₂x₃ V x₁ V x₁x₂ V x₁x₂x₃ =

= V x₃ V x₁x₂.

Упражнения.

1. Найти СДНФ логических функций трех переменных f₁ – f₄, заданных в таблице 13.

Таблица 13

X	y	z	f1	f2	f3	f4
0	0	0	0	0	1	0
0	0	1	0	0	0	1
0	1	0	0	1	0	0
0	1	1	1	1	1	1
1	0	0	1	0	1	1
1	0	1	0	1	0	0
1	1	0	1	1	1	1
1	1	1	1	1	0	0

2. Получить СДНФ логической функции f(x, y, z), используя табличное представление функции, если f задана булевой формулой:

1. y z x y x z x ;

2. x y y z z y ;

3. x z y z y z;

4. x x y z y z;

5. y z z y z x y z;

6. _z y z y x y z;

7. x y y z x z x (z ).

3. Получить СДНФ, используя расщепление (обратное склеивание);

4. Для функций заданных в виде ДНФ, получить СДНФ, используя эквивалентные преобразования, и упростить СДНФ, используя метод Блейка-Прецкого.

а) f(x, y, z) = xz yz ;

б) f(x, y, z) = xy xz y z ;

в) f(x, y, z) = y yz x z;

г) f(x, y, z) = y z xyz;

5. Привести формулы ДНФ:

а) f(x, y, z) = ;

б) f(x, y, z) = .

6. Получить СКНФ для функций f₁ – f₂ из таблицы 13.

7. Используя изоморфизм булевых алгебр логических функций и двоичных векторов, выполнить булевые операции над логическими функциями трех переменных f₃ и f₄ из таблицы 13.