diskr_edit (1023554), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Все указанные строки (1-ую и 2-ую) и столбцы (1-ый, 2-ой, 3-ий и 4-ый) вычеркиваем из таблицы покрытий. После этого все элементы таблицы окажутся вычеркнутыми. Следовательно, два существенных импликанта x₂&x₃ и x₁&x₃ покрывают все элементарные конъюнкции СДНФ.

Итак, минимальная ДНФ для нашей функции имеет вид:

F₂(x₁, x₂, x₃) = x₂&x₃ V x₁&x₂ .

Рассмотрим еще один пример нахождения минимальной ДНФ булевой функции.

Пример 4.21.

Пусть булева функция задана таблицей

Таблица 4.7

Применим вначале алгоритм Квайна - Мак-Класки для нахождения сокращенной ДНФ.

Очевидно, в силу алгоритма 4.3, данная функция имеет следующую формулу в СДНФ:

F(x₁, x₂, x₃, x₄) = x₁&x₂&x₃&x₄ V x₁&x₂ &x₃ &x₄ V x₁&x₂&x₃&x₄ V

x₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄.

Выпишем наборы переменных, на которых функция принимает значение 1, причем эти наборы упорядочим по группам так, что в каждую группу входят наборы с одинаковым числом единиц.

Группы A₀ нет.

Группа A₁:

0 1 0 0

Группа A₂:

0 0 1 1

0 1 0 1

1 0 1 0

1 1 0 0

Группа A₃:

0 1 1 1

1 0 1 1

1 1 0 1

Группы A₄ нет.

Производим попарное сравнение наборов переменных, входящих в соседние группы.

При сравнении групп A₁ и A₂:

вместо (0 1 0 0) и (0 1 0 1) получим (0 1 0 –);

вместо (0 1 0 0) и (1 1 0 0) получим (– 1 0 0);

При сравнении групп A₂ и A₃:

вместо (0 0 1 1) и (0 1 1 1) получим (0 – 1 1);

вместо (0 0 1 1) и (1 0 1 1) получим (– 0 1 1);

вместо (0 1 0 1) и (0 1 1 1) получим (0 1 – 1);

вместо (0 1 0 1) и (1 1 0 1) получим (– 1 0 1);

вместо (1 0 0 1) и (1 0 1 1) получим (1 0 – 1);

вместо (1 0 0 1) и (1 1 0 1) получим (1 – 0 1);

вместо (1 1 0 0) и (1 1 0 1) получим (1 1 0 –).

После этого этапа массив R пуст, т. к. все наборы участвовали в образовании наборов с прочерками, а массив P = P(1) включает следующие наборы:

(0 1 0 –);

(– 1 0 0);

(0 – 1 1);

(– 0 1 1);

(0 1 – 1);

(– 1 0 1);

(1 0 – 1);

(1 – 0 1);

(1 1 0 –).

Теперь попарно сравниваются между собой наборы с прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R.

Для нашего примера

вместо (0 1 0 –) и (1 1 0 –) получим (– 1 0 –);

вместо (– 1 0 0) и (– 1 0 1) получим (– 1 0 –)

После этого этапа в массив R попадают наборы, не участвовавшие в образовании наборов с двумя прочерками:

(0 – 1 1);

(– 0 1 1)

(0 1 – 1);

(1 0 – 1);

(1 – 0 1);

Массив P(2) состоит из набора с двумя прочерками:

(– 1 0 –).

Набор с двумя прочерками один и процедура сравнения заканчивается. Поэтому все наборы из P(2) попадают в массив R, который после этого включает наборы:

(0 – 1 1);

(– 0 1 1)

(0 1 – 1);

(1 0 – 1);

(1 – 0 1);

(– 1 0 –).

Сокращенная ДНФ имеет вид:

F₁(x₁, x₂, x₃, x₄) = x₁&x₃&x₄ V x₂&x₃&x₄ V x₁&x₂&x₄ V x₁&x₂&x₄ V x₁&x₃&x₄ x₂&x₃.

Найдем теперь минимальную ДНФ с помощью таблицы покрытий (алгоритм 4.7).

Составляем таблицу покрытий.

Для нашего примера получим следующую таблицу (таблица 4.8) из 8 столбцов, соответствующих 8 элементарным конъюнкциям СДНФ F(x₁, x₂, x₃, x₄) и 6 строк, соответствующих 6 простым импликантам сокращенной ДНФ F₁(x₁, x₂, x₃, x₄).

Таблица 4.8

	0011	0100	0101	0111	1001	1011	1100	1101
0-11	*			*
-011	*					*
01-1			*	*
10-1					*	*
1-01					*			*
-10-		*	*				*	*

Выделяем столбцы, содержащие одну метку – это 2-ой и 7-ой столбцы. Оба этих столбца определяют один и тот же импликант x₂&x₃ (ему соответствует 6-ая строка), который является существенным. Он покрывает следующие четыре элементарные конъюнкции СДНФ: x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄ (им соответствуют 2-ой, 3 - ий, 7 - ой и 8 - ой столбцы). Все указанные строки и столбцы вычеркиваем из таблицы покрытий. После этого таблица примет вид:

Таблица 4.9

	0011	0111	1001	1011
0-11	*	*
-011	*			*
01-1		*
10-1			*	*
1-01			*

В полученной таблице нет одинаковых столбцов. В полученной таблице нет пустых строк. Выбираем такую совокупность существенных импликантов, которая покрывает все столбцы и содержит наименьшее количество букв. Для нашей таблицы это импликанты x₁&x₃&x₄ и x₁&x₂&x₄ (1 - ая и 4 - ая строки таблицы 4. 9), т. к. они покрывают все оставшиеся столбцы.

Итак, минимальная ДНФ для нашей функции имеет вид:

F₂(x₁, x₂, x₃, x₄) = x₁&x₃&x₄ V x₁&x₂&x₄ V x₂&x₃ .

4.9. Применение алгебры булевых функций к релейно-контактным схемам

Рассмотрим электрические релейно-контакные схемы, главный элемент которых – электромагнитное реле.

Пусть x₁, x₂, ... , x_n – набор контактов в схеме. Контакты могут быть размыкающими и замыкающими. Контакт называется замыкающим, если он замыкается при подаче напряжения. Контакт называется размыкающим, если он размыкается при подаче напряжения. Один и тот же контакт в схеме может быть как замыкающим, так и размыкающим.

Каждой последовательно- параллельной схеме сопоставим функцию проводимости:

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

Функция проводимости схемы, состоящей из одного элемента x, для замыкающего контакта есть f(x) = x, а для размыкающего контакта f(x) = x.

Функция проводимости схемы, состоящей из двух последовательно соединенных контактов x и y (рис. 4. 1) есть f(x, y) = x&y.

Рис. 4. 1

Функция проводимости схемы, состоящей из двух параллельно соединенных контактов x и y (рис. 4. 2) есть f(x, y) = x V y.

Рис. 4. 2

Каждой последовательно-параллельной схеме можно поставить в соответствие формулу логики булевых функций, реализующую функцию проводимости этой схемы. Две схемы считаются эквивалентными, если они имеют одинаковую функцию проводимости. Применяя равносильные преобразования, можно упрощать релейно-контактные схемы, заменяя их эквивалентными, с меньшим числом контактов.

Пример 4.22.

Найдем функцию проводимости схемы, изображенной на рис. 4. 3.

Рис. 4.3

f(x, y, z) = (y&z) V (x&y&z) V (x&y&z)  (y&z) V (y&z)  z.

Эквивалентная схема изображена на рис. 4.4.

Рис 4.4

Контрольные вопросы к теме 4

1. Выберите правильный вариант ответа 1 – 4 для следующих вопросов:

а) Сколько существует различных булевых функций n переменных? б) Сколько существует различных наборов переменных для булевой функции n переменных?

Варианты ответа: 1) 2ⁿ; 2) 2² ; 3) n²; 4) n!.

2. Какое из следующих утверждений верно:

а) Переменные булевой функции и сама булева функция принимают значения 0 или 1;

б) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел;

в) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1;

г) Значения переменных булевой функции и значения самой функции совпадают с множеством действительных чисел;

3. Выберите правильный вариант ответа 1 – 4 для следующих вопросов:

а) Сколько может быть различных ДНФ у булевой функции?

б) Сколько может быть различных СДНФ у булевой функции?

в) Сколько может быть различных КНФ у булевой функции?

г) Сколько может быть различных СКНФ у булевой функции?

Характеристики

Список файлов книги