Глава 4 Алгебра логики (стр. 3 )

Введем обозначения:

Теорема 4.6  О разложении булевой функции по k переменным (знак È ºÚ).

  Пример 4.7  n=3, k=2.

Доказательство:

Выберем какой-либо набор значений для переменных x1, …, xn. Пусть это будет s1, …, sn.. Заметим, что (11=1, 00=1, 10=1=0, 01=0)

Подставим в правую часть формулировки теоремы вместо x1, …, xn набор s1, …, sn. Получим. Поскольку коэффициент перед функцией равен 1 только при равных значениях si и ai, в разложении останется только один член: , и si =ai, т. е. . Получена левая часть формулы теоремы 4.6. Поскольку набор был выбран произвольно, получаем, что утверждение верно " набора x1, …, xn. ■

Следствие 1: Разложение Шеннона

Следствие 2: При k=n получаем: , т. е. выбираем те слагаемые, на которых функция равна 1. Полученная формула представляет собой СДНФ.

4.2.2  Построение совершенных нормальных форм

Построение СДНФ

1. Построение по таблице истинности

1)  Найти строки в ТИ, где f = 1.

2)  " найденному набору s1, …, sn. поставить в соответствие произведение , где

3)  Составить дизъюнкцию из произведений п.2.

2. Получение из ДНФ.

Если некоторое произведение ДНФ не содержит какой-либо переменной (пусть xk), то необходимо домножить это произведение на дизъюнкцию этой переменной и ее отрицания (т. е. на единицу, равную xk Ú`xk) и применить дистрибутивный закон.

Построение СКНФ

1. Построение по ТИ.

1)  Найти строки в ТИ, где f = 0.

2)  " найденному набору s1, …, sn. поставить в соответствие дизъюнкцию , где

3)  Составить произведение дизъюнкций из п.2.

2. Получение из КНФ.

Если некоторая элементарная дизъюнкция КНФ не содержит какой-либо переменной (пусть xk), то необходимо дизъюнктивно добавить в нее произведение этой переменной и ее отрицания (т. е. xk×`xk) и применить дистрибутивный закон.

x	y	z	f
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

  Пример 4.8  1) Получим СДНФ и СКНФ по ТИ:

2) Получим СДНФ и СКНФ из ДНФ и КНФ:

Произведения в СДНФ называются минтермами, а дизъюнкции в СКНФ – макстермами.

Может использоваться запись , которая означает, что в качестве минтермов берутся произведения, соответствующие двоичному представлению чисел . Аналогично, запись означает, что в качестве макстермов берутся дизъюнкции, соответствующие двоичному представлению чисел .

  Пример 4.9  Пусть заданы функции f и g: ; . f: 1 ® 001; 3 ® 011; 5 ® 101; 6 ® 110 Þ . g: 2 ® 010, 4 ® 100; 5 ® 101 Þ .

4.2.3  Карты Карно

Кроме аналитического, существуют геометрические способы представления булевых функций. Одним из таких способов является карта Карно.

Пусть дана булева функция f(x1, x2, …, xn), определенная на 2n наборах переменных. Наборы, отличающиеся значением только одной переменной xi, называются соседними.

Множество тех наборов, на которых f(x1, x2, …, xn) = 1, называется прообразом единицы, множество наборов, на которых f(x1, x2, …, xn) = 0 – соответственно прообразом нуля.

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

Булева функция может быть представлена на карте Карно выделением клеток, соответствующих прообразу 1. В этих клетках будем писать 1 и называть их p-клетками. Незаполненные ячейки соответствуют нулям функции. 2k соседних p-клеток, расположенных в виде прямоугольника или квадрата, образуют k-мерный p-подкуб. Он называется покрытием размерности k и соответствует произведению n–k переменных. Одна p-клетка образует 0-мерный p-подкуб (или 0-куб), две – одномерный (1-куб, покрытие размерности 1 – произведение n–1 переменной – все кроме той, которая отличается для этих наборов), четыре – двумерный, и т. п.

Для функции трех переменных карту Карно можно представить в следующем виде:

Все клетки, отмеченные скобкой xi (по строке и столбцу), представляют наборы с xi = 1, а в неотмеченных строках и столбцах клетки соответствуют наборам с xi = 0.

В случае четырех переменных карта Карно имеет следующий вид:

Пример 4.10  Заполним карту Карно для функции

4.2.4  Контрольные вопросы

1.  Какое представление функции называется ее нормальной формой?

2.  Что такое ДНФ? В чем ее отличие от КНФ?

3.  Какая нормальная форма называется совершенной?

4.  Какой формой является функция xÚy? Почему?

5.  Запишите разложение Шеннона для функции от 4 переменных f(x1,x2,x3,x4) по переменной x3.

6.  Какие существуют способы построения СДНФ и СКНФ? В чем их различие при построении по таблице истинности?

7.  Как можно получить СДНФ (СКНФ) посредством преобразований?

8.  Что называется минтермами (макстермами)?

9.  Что такое карта Карно?

10.  Какова особенность соседних клеток на карте Карно?

11.  Из какого количества клеток состоит карта Карно функции трех переменных? А функции 5 переменных?

12.  Что такое покрытие на карте Карно?

13.  Сколько клеток карты Карно составляют покрытие размерности 2? А покрытие размерности 4?

14.  Как построить карту Карно функции, представленной в ДНФ?

4.3  Контактные схемы

Контактная цепь (схема) – устройство из проводов и контактов, связывающих два полюса. Любой контакт может быть либо замкнут, либо разомкнут. Контакты будем обозначать x1, x2, x3, …

Контактной схеме будет соответствовать булева функция, которая принимает значение 1, если контур между двумя полюсами замкнут, и 0 – в противном случае. Основные операции булевой алгебры можно реализовать с помощью последовательного и параллельного соединения контактов.