misle.ru страница 1
скачать файл

Дополнение


К курсу «Дискретная математика для программистов»

Карты Карно

Изложение построено в форме дополнений к учебнику «Дискретная математика для программистов 3-е издание». Места дополнений указаны с помощью номеров параграфов учебника. Новые заголовки подчеркнуты.


3.1.4' Функции k-значной логики

Рассмотрим множество Ek ={0, 1, … k–1} и множество функций Pk, n, имеющих n аргументов типа Ek и возвращающих значение типа Ek. Такие функции называются функциями k-значной логики и являются обобщением функций алгебры логики: P2, n = Pn.

Функции k-значной логики можно задавать таблицами, подобными таблицам истинности для обычной двузначной логики, причем в таблицах используются элементы из Ek, а не E2.

Нетрудно видеть, что |Pk, n|= k^(k^n), где знак ^ означает операцию возведения в степень. Число функций k-значной логики растет еще быстрее, чем число булевых функций. Так, уже для трехзначной логики аналог таблицы подраздела 3.1.4 для всех функций двух переменных содержит 39=19683 строк и не может быть помещён в книгу.

Функцию k-значной логики можно представить как систему функций обычной двузначной логики следующим образом. Функция f(x1, …, xn)  Pn, k представляется системой функций {g1(y11, …, y1m, …, yn1, …, ynm),…, gm(y11, …, y1m, …, yn1, …, ynm)}, где m = log2k. Здесь значения функции f и переменных xi принадлежат множеству E2, а значения функций gj и переменных yij принадлежат множеству Ek. При этом если значение переменной xi имеет двоичный код ai1aim, то значение функции f(x1, …, xn) имеет двоичный код

g1(a11, …, a1m, …, an1, …, anm)…gm(a11, …, a1m, …, an1, …, anm)

Другими словами, функция gj вычисляет j-ую цифру в двоичном представлении числа f(x1, …, xn).

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

Функции k-значной логики далее в этом учебнике не рассматриваются.



3.3. Двойственность и симметрия

Понятия двойственности и симметрии с успехом …


Мы рассматриваем двойственность и симметрию …



3.3.3.' Симметрические функции

Булева функция n переменных называется симметрической, если её значение инвариантно относительно перестановок значений аргументов.

Понятие симметрической функции применимо только к функциям двух и большего числа переменных.



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

При перестановке значений в наборе общее количество нулей и единиц сохраняется.



Пример Функция, заданная формулой ~xyz  x~yz  xy~z является симметрической и принимает значение 1 тогда и только тогда, когда две переменных из 3 равны 1 и одна равна 0.

ТЕОРЕМА Существует 2n+1 различных симметрических функций n переменных.

Доказательство Ясно, что на любом наборе значений n переменных, в котором содержится k значений 1 (и, соответственно nk значений 0), симметрическая функция принимает одно и то же значение (1 или 0). Таким образом, симметрическую функцию f от n переменных можно задать булевским вектором (f0,f1,…,fn), где fi – значение функции на наборах значений, содержащих i единиц.
3.4.1.' Минимальные термы

Выражение вида x11… xnn , которое присутствует в следствии 2 теоремы о разложении булевой функции по переменным, имеет большое значение в теории булевых функций и специальное название: минимальный терм, или совершенный одночлен, или конституанта единицы, или, наиболее коротко, минтерм. Нетрудно видеть, что минтерм – это реализация булевой функции n переменных, которая имеет значение 1 ровно на одном наборе значений переменных, а именно на наборе (1,…,n). Отсюда и из следствия 2 непосредственно следует



СЛЕДСТВИЕ 3 [к теореме о разложении булевой функции по переменным] Любую булеву функцию, кроме 0, можно представить как дизъюнкцию некоторых минтермов.

Ясно, что при фиксированном n имеется ровно 2n различных минтермов. Обычно минтерм обозначают mi, где i0..(2n–1), i называется номером минтерма, или прямо указывают булевский вектор (1,…,n), на котором минтерм принимает значение 1. Из структуры формулы, задающей минтерм, непосредственно следует, что двоичное представление номера минтерма задает тот набор значений (в установленном порядке), на котором минтерм принимает значение 1.

Говорят, что система булевых функций ортогональна, если их конъюнкция есть тождественный ноль. Нетрудно видеть, что имеет место следующая

ЛЕММА 1 Любое множество из двух или более различных минтермов ортогонально.

Говорят, что система булевых функций выполнима, если их дизъюнкция не есть тождественный ноль. Нетрудно видеть, что имеет место следующая



ЛЕММА 2 Любое множество минтермов выполнимо.

Двойственным к минтерму является макстерм — булева функция, которая принимает значение 0 на единственном наборе значений переменных. Ясно, что макстерм реализуется формулой x11… xnn . Используя принцип двойственности, на макстермы нетрудно распространить все наблюдения, которые сделаны для минтермов.


3.6.3.' Карты Карно

Карта Карно1(используется также термин диаграмма Вейча) — это замечательное представление булевой функции, позволяющее наглядно и эффектно описать и реализовать многие, в том числе сложные, операции с булевыми функциями и реализующими их формулами. В картах Карно применяются сразу несколько понятий, рассматриваемых в этом учебнике: код Грея (1.3.3.), таблицы истинности (3.1.1.), минтермы (3.4.1.'), единичный гиперкуб (3.4.5), табличные представления булевой функции (3.6.1.).

Карта Карно для представления функций n переменных является таблицей, которая содержит 2n клеток. Если n чётное, n=2k, то таблица содержит k строк и k столбцов, а если нечётное, n=2k+1, то таблица содержит k строк и 2k столбцов. Каждая ячейка карты Карно символизирует один минтерм. Ниже приведены таблицы для n =1, 2, 3, 4 и 5, в клетках которых выписаны вектора соответствующих минтермов.



n =1

1

0


n =2

11

01

10

00


n = 3

110

111

011

010

100

101

001

000


n =4

1100

1110

0110

0100

1101

1111

0111

0101

1001

1011

0011

0001

1000

1010

0010

0000


n =5

11001

11001

11101

11101

01100

01100

01000

01000

11011

11011

11111

11111

01110

01110

01010

01010

10011

10011

10111

10111

00110

00110

00010

00010

10001

10001

10101

10101

00100

00100

00000

00000

Неформально алгоритм построения карты Карно можно описать следующим образом. Представим себе мысленно, что переменные приписаны сторонам матрицы против часовой стрелки: первая сверху, вторая слева, третья снизу, четвёртая справа, пятая снова сверху и так далее. При переходе от четного n к нечётному дублируется каждый столбец, а при переходе от нечётного n к чётному дублируется каждая строка. После этого к векторам добавляются 0 или 1 для новой переменной по следующему правилу: для "верхних" переменных в левой половине 1, в правой – 0, для "левых" переменных в верхней половине 1, в правой – 0, для нижних и правых – в средней части 1, по краям – 0. В приведенных таблицах добавляемые элементы подчеркнуты, чтобы сделать процесс более наглядным.

Заметим следующее. На каждой карте Карно представлены все 2n минтермов. Распределение минтермов по клеткам карты однозначно и может быть сделано один заранее для каждой карты. Карту Карно можно рассматривать как развертку тора, то есть считать верхнюю сторону смежной с нижней, а правую – с левой. В этом случае легко видеть, что для каждой ячейки все её четыре соседа отличаются ровно в одном разряде. Подобным же свойством обладают коды Грея и вершины единичного гиперкуба.

3.6.3." Представление булевой функции на карте Карно

Допустим, что карта Карно для заданного n, то есть распределение минтермов по клеткам таблицы, заранее вычислена. Тогда можно построить следующее представление любой булевой функции, заданной таблицей истинности. Рассматривается булева матрица того же размера, что и карта Карно. Каждой строке таблицы истинности соответствует некоторый минтерм. Если значение в этой строке равно 1, то записываем 1 в соответствующую ячейку матрицы, в противном случае записываем 0. Фактически, элементы вектора значений таблицы истинности булевой функции раскладываются по ячейкам булевой матрицы, а правило раскладывания задается картой Карно.



Пример Функция g(x, y, z), заданная в примере подраздела 3.4.5. имеет следующее представление на карте Карно.

1

0

0

1

0

0

1

1

Рассмотрим некоторые примеры применения карт Карно для решения задач с булевыми функциями. Первый пример связан с минимизацией дизъюнктивных форм (подразделы 3.4.4. и 3.4.6.). Заметим, что так же, как каждая отдельная ячейка с 1 соответствует минтерму, каждая прямоугольная группа смежных ячеек, содержащих 1, соответствует элементарной конъюнкции. Таким образом, задача минимизации дизъюнктивной формы сводится к отысканию покрытия всех ячеек содержащих 1 на карте Карно минимальным количеством прямоугольников.



Пример Для функции g(x, y, z), заданной в примере подраздела 3.4.5, минимальное покрытие на карте Карно содержит два элемента, они выделены штриховкой.

1

0

0

1

0

0

1

1

Второй пример связан с построением канонических форм для функций и их комбинаций. Карта Карно для одной заданной функции очевидным образом задает её СДНФ – достаточно выписать минтермы, указанные ячейками с 1, и соединить их знаками дизъюнкции. Столь же просто можно построить СДНФ для отрицания, дизъюнкции и конъюнкции заданных функций. Для получения СДНФ отрицания достаточно просто инвертировать матрицу. Для получения СДНФ конъюнкции или дизъюнкции произвольного числа k булевых функций можно поступить следующим образом. Взять матрицу, заполненною нулями, и добавить в каждую ячейку независимо 0 или 1 для каждой функции. При этом в некоторых ячейках окажется 0, в некоторых 1, а в некоторых какие-то числа вплоть до k. Все ненулевые ячейки образуют СДНФ дизъюнкции, все ячейки, равные k, образуют СДНФ конъюнкции.



Третий пример связан с эффективным вычислением значения булевой функции. Вообще говоря, если булева функция представлена картой Карно и задан набор значений переменных (1,…,n), то ответ получается за один шаг: значение функции на заданном наборе содержится в ячейке, соответствующей минтерму (1,…,n). Таким образом задача сводится к быстрому отысканию нужной ячейки. Здесь можно применить различные подходы. Один из вариантов приведен в алгоритме 3.4.

1 Морис Карно, род. 1924



скачать файл



Смотрите также: