Классическая логика

Раздеп. Классическая логика Лекция . Карты Карно Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно. Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой. В таб.2.4.1. показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. В таб.2.4.2. приведена разметка карты Карно для n=4 переменных. таблица 2.4.1. Таблица 2.4.2. Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток). Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила; 1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,... 2. Каждая клетка, входящая в группу из 2m клеток, должна иметь m соседних в группе. 3. Каждая клетка должна входить хотя бы в одну группу. 4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе. 5. Число групп должно быть минимальным. Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания. Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем). Для упрощения записи мы не будем отмечать переменные, хотя сохраним их обозначения как и в таблицах 2.4.1, 2.4.2. Приведем шаблоны для n=3, которые помогают строить покрытия единицы (1). Приведем шаблоны для n=4, которые помогают строить покрытия единицы (1) Пример 2.4.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений. 1) f(x,y,z)=(1011 0101); 2) f(x1,x2,x3,x4)=(1011 1111 1011 1100). Решение. 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимся двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с 0). Таким образом, f(0,0,1)=f(1,0,0)=f(1,1,0)=0. Раздел. Классическая логика Лекция. Алгебра Жегалкина