52
3)
формулы дистрибутивности (
6.6 ), (
6.7);
4)
элементарные поглощения (
6.18 ) … (
6.21)
.
Обычно формула приводится к ДНФ, а затем отдельные слагаемые
поглощаются.
6.3. логические функции
6.3.1. способы представления логических функций
Логическая функция (функция алгебры высказываний)
f(
X
1
,
X
2
,
…,
X
n
) от
n переменных —
n-рная операция на множестве [0; 1].
В этой функции логические переменные
X
1
,
X
2
, …,
X
n
представляют
собой высказывания и принимают значения 0 или 1.
Существует 2
2
n
различных логических функций от
n переменных.
Логические операции, рассмотренные в подразд. 6.2, можно рас-
сматривать как логические
функции от двух переменных.
Набор функций, с помощью которого можно представить (выра-
зить) все логические функции, называется
функционально-полным
или
базисом. Основными базисами являются:
1) булевый базис, состоящий из конъюнкции, дизъюнкции и от-
рицания;
2) базис NOR, состоящий из
стрелки Пирса;
3) базис NAND, включающий в себя штрих Шеффера.
Рассмотрим некоторые способы представления логических функ-
ций.
А н а л и т и ч е с к и й.
Функция задается в виде алгебраического
выражения, состоящего из функций одного или нескольких базисов,
применяемых к логическим переменным.
Т а б л и ч н ы й. Функция задается в виде таблицы истинности
(соответствия), которая содержит 2
n
строк (по числу наборов аргу-
ментов),
n столбцов по числу переменных и один столбец значений
функции. В
такой таблице каждому набору аргументов соответствует
значение функции.
Ч и с л о в о й. Функция задается в виде десятичных (восьмеричных,
шестнадцатеричных) эквивалентов номеров тех наборов аргументов,
на которых функция принимает значение 1. Нумерация наборов на-
чинается с нуля. Аналогичным образом логическая
функция может
быть задана по нулевым значениям.
Пример 6.1. Функция задана аналитически:
f X Y Z
Y
Z X Y
Z
Y
Z
( , , ) (
) (
)
.
=
+
+
+ +
Записать функцию в табличном и числовом представлениях.
53
Р е ш е н и е. Переход к другому представлению возможен и в
таком
виде. Однако лучше преобразовать функцию, чтобы упростить про-
цесс перехода к другому представлению.
Опустим отрицание до переменных по законам де Моргана (6.8),
(6.9):
f X Y Z
Y
Z X Y
Z
Y
Z Y Z
X Y Z Y Z
( , , ) (
) (
)
.
=
+
+
+ +
=
+
+
+
Сократим одинаковые слагаемые по формуле (6.10) и перегруппи-
руем их:
f X Y Z
Y Z
X Y Z Y Z
X Y Z Y Z
( , , )
.
=
+
+
+
=
+
+
По полученному выражению построим таблицу истинности путем
подстановки значений переменных в строке и записи значения функ-
ции в эту строку (табл. 6.2).
Чтобы представить
функцию в числовом представлении, выпишем
номера наборов, на которых функция принимает значение 1: 1, 2, 4,
5, 6, 7, и номера наборов, на которых функция принимает значение
0: 0, 3.
Тогда функция
f X Y Z
X Y Z Y Z
( , , )
=
+
+
имеет два числовых
представления. В
первом случае перечисляются все наборы, на кото-
рых функция равна 1:
f (1, 2, 4, 5, 6, 7)
= 1.
Во втором случае перечисляются все наборы, на которых функция
равна 0:
f(0, 3)
= 0.
Все эти представления эквивалентны и описывают одну функ-
цию.
Т а б л и ц а 6.2.
Достарыңызбен бөлісу: