Формы задания и синтез логических функций
ЛЕКЦИЯ 2
--------
План
1.Формы задания лог. ф-ций.
2.Синтез ПОЛФ.
3.Дать доп.примеры синтеза ПОЛФ(с пом. ПК).
4.Минимизация с пом.осн.з-нов логики.
2.Формы задания и синтез логических функций
Традиционно логические функции задаются с помощью таблиц истин-
ности,где в левой ее части вписаны входные наборы,а в правой - значе-
ние функции на этих наборах.Однако входные наборы можно представлять в
виде 8-ичных или 16-ичных кодов,которые легко разворачиваются в двоич-
ные коды,являющиеся по сути входными наборами.
Таблица перевода 8-ичных кодов в
2-ичную систему счисления.
---------T--------¬
¦ 8-ая ¦ 2-ая ¦
+--------+--------+
¦ 0 ¦ 000 ¦
¦ 1 ¦ 001 ¦
¦ 2 ¦ 010 ¦
¦ 3 ¦ 011 ¦
¦ 4 ¦ 100 ¦
¦ 5 ¦ 101 ¦
¦ 6 ¦ 110 ¦
¦ 7 ¦ 111 ¦
L--------+---------
Для перевода целого 8-ичного числа в 2-ичную систему счисления
достаточно представить каждую 8-ичную цифру данного числа в виде 2-ич-
ной триады.
Пример 1.
73(8) = 111011(2)
54321(8) = 101100011010001(2)
Пример 2.
Логическая функция от 6 переменных задана следующими 8-ичными ра-
бочими наборами:
РН(6) = 31,51,71.
Этим РН(6) соответствуют следующие 2-ичные коды:
011001,101001,111001.
2.1. Синтез полностью определенных логических функций
-----------------------------------------------------
Полностью определенной логической функцией(ПОЛФ) от N переменных
называется такая функция,которая задана на всех 2^N наборах.Синтез
ПОЛФ можно проиллюстрировать решением простой задачи.
Задача 2.1.
-----------
Приемная комиссия в составе трех членов комиссии и одного предсе-
дателя решает судьбу абитуриента большинством голосов . В случае рав-
ного распределения голосов большинство определяется голосом председа-
теля. Построить автомат для тайного голосования.
Решение.
-------
Выразим условие задачи в виде таблицы истинности (табл.2.1). Здесь
х4-председатель,х3...х1 - члены комиссии,у-полностью определенная
выходная функция; у=1,если абитуриент успешно прошел собеседова-
ние.
Таблица 2.1.
------------------T-----¬
¦х4 х3 х2 х1 ¦ у ¦
+-----------------+-----+
¦ 0 0 0 0 ¦ 0 ¦
¦ 0 0 0 1 ¦ 0 ¦
¦ 0 0 1 0 ¦ 0 ¦
¦ 0 0 1 1 ¦ 0 ¦
¦ 0 1 0 0 ¦ 0 ¦
¦ 0 1 0 1 ¦ 0 ¦
¦ 0 1 1 0 ¦ 0 ¦
¦ 0 1 1 1 ¦ 1 ¦
¦ 1 0 0 0 ¦ 0 ¦
¦ 1 0 0 1 ¦ 1 ¦
¦ 1 0 1 0 ¦ 1 ¦
¦ 1 0 1 1 ¦ 1 ¦
¦ 1 1 0 0 ¦ 1 ¦
¦ 1 1 0 1 ¦ 1 ¦
¦ 1 1 1 0 ¦ 1 ¦
¦ 1 1 1 1 ¦ 1 ¦
L-----------------+------
Конъюнкции входных переменных, на которых функция принимает зна-
чение 1, будем называть единичными , или рабочими наборами(РН) . Набо-
ры, на которых функция принимает значение 0, будем называть нулевыми,
или запрещенными наборами(ЗН).
Кстати,данная таблица истинности может быть представлена следую-
щими 8-ичными кодами единичных наборов:7,11,12,13,14,15,16.17.Нулевые
наборы для ПОЛФ не задаются:они получаются автоматически.
Для того,чтобы по таблице истинности найти функцию, достаточно
выписать все рабочие наборы и соединить их знаком логического сложе-
ния.Если переменная входит в РН единицей,то она записывается в прямом
виде,иначе - в инверсном. Из табл.2.1 получаем
__ _ _ __ __ __ _ _ __
у=х4х3х2х1 + х4х3х2х1 + х4х3х2х1 + х4х3х2х1 + х4х3х2х1+ х4х3х2х1 +
__
+ х4х3х2х1 + х4х3х2х1
Данное выражение представляет собой совершенную дизъюнктивную нор-
мальную форму (СДНФ) булевой функции
ДОМАШНЕЕ ЗАДАНИЕ 1
1.Выполнить синтез 16 табличных функций от 2-х переменных(лекция
1,табл.1.3).
2.Выполнить ситез функций,заданных 8-ичными рабочими наборами:
- РН(3) = 0,2,5,7;
- РН(4) = 14,15,10,11.
3.Отминимизировать полученные в п.2 ДЗ1 функции,используя основ-
ные законы логики.
4.Отминимизиpовать функции от 3-х пеpеменных под 8-ичными номеpами:
267,173,370,111,123,146,230,345,356,234.
5.Отминимизировать функцию автомата для тайного голосования.