Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 8-9

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

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

Каждая карта Карно разделена на квадратики (или они подразумеваются), причем каждому квадратику соответствует единственная комбинация значений всех переменных. Пример карты Карно для двух переменных:

__y_
|_|__|
x|_|__|

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

Карту Карно для функции четырех переменных получим из карты для f(x, у, z), вставив две строки в середину. Карту Карно для функции пяти переменных f(x, у, z, ч, v) можно составить из двух карт для функции четырех переменных, расположив их симметрично относительно общей вертикальной границы. Карты Карно, разновидностями таблиц истинности, также позволяют выписывать булевы функции в двух стандартных формах. Одна из этих форм - СовДНФ. При ее написании принимаются во внимание только те клетки карты Карно, в которых значение функции равно 1. Для этих клеток строятся логические произведения всех переменных, взятых без отрицания или с отрицанием в соответствии с правилами, изложенными для построения СовДНФ по таблице истинности.

Вторая форма - СовКНФ. Здесь необходимо отметить те клетки карты, в которых значение функции 0, и составить для них логические суммы всех переменных, взятых без отрицания или с отрицанием, но уже в соответствии с правилами, изложенными для построения СовКНФ по таблице истинности.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным