таблица истинности для основных логических

51
Законы де Моргана
•
:
X Y
X Y
⋅ =
+ ;
(6.8)
X Y
X Y
+ =
⋅ . 
(6.9)
Идемпотентность
•
:
X 
+ X = X;
(6.10)
X
⋅ X = X.
(6.11)
Закон противоречия
•
:
X X
⋅
= 0. 
(6.12)
Закон 
•
«
исключения третьего»:
X
X
+
=1. 
(6.13)
Свойства констант
•
:
X
⋅ 1 = X;
(6.14)
X
⋅ 0 = 0;
(6.15)
X
+ 1 = 1;
(6.16)
X
+ 0 = X.
(6.17)
Элементарные поглощения
•
:
X
+ XY = X;
(6.18)
X
XY
X Y
+
=
+ ; 
(6.19)
X(X 
+ Y ) = X;
(6.20)
X X Y
XY
(
)
.
+
=
(6.21)
Преобразование стрелки Пирса
•
:
X Y
X Y
↓ =
+ . 
(6.22)
Преобразование штриха Шеффера
•
:
X Y X Y
= ⋅ . 
(6.23)
Правило 6.1 (порядок применения формул при преобразованиях).
Перечисленные  формулы  рекомендуется  применять  в  следующем 
порядке:
1)
преобразование  стрелки  Пирса  (6.22)  и  штриха  Шеффера 
(
6.23);
2)
законы де Моргана (6.8 ), (6.9);

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. 

жүктеу/скачать 4,7 Mb.

Достарыңызбен бөлісу: