Функции алгебры логики (фал).
В результате выполнения арифметических операций получают новое двоичное число. Устройство, реализующее действия над двоичными числами, можно рассматривать как функциональный преобразователь. Если рассматривать отдельные разряды исходных чисел и конечных результатов вычислений в качестве аргументов и функций, то устройство, осуществляющее арифметическое действие имело бы большое количество входов и выходов. Причем на каждый вход поступал бы один разряд исходного числа (0 или 1), а с каждого выхода снимался бы один двоичный разряд результата (0 или 1).
Для анализа и синтеза таких устройств необходимо иметь математический аппарат, позволяющий оперировать с двоичными переменными. Основы такого аппарата были впервые сформированы в середине прошлого века английским математиком Д.Булем. Переменные величины и функции от них, которые могут принимать только два значения 0 или 1, носят названиебулевских или логических переменных и функций.
Функциями алгебры логики (ФАЛ)
называются функции, определенные на
наборе двоичных переменных(
,
,
...
)
и сами принимающие в качестве своих
значений либо нуль, либо единицу. Задать
ФАЛ - это значит определить ее значение
(0 или 1) на каждом возможном наборе
значений аргументов. Количество различных
наборов аргументов равно количеству
различных чисел, которые могут быть
изображены с помощьюn
разрядов, т.е. 2. Так как на каждом
наборе аргументов ФАЛ может принимать
одно из двух значений, то количество
различных ФАЛ отп аргументов
конечно и равно
Ниже рассматриваются всевозможные
ФАЛ отn аргументов дляn=0, 1, 2.
1. n=0. Существуют
=2
различные ФАЛ; f1=0 - константа нуль,
f2=1 - константа единица.
2. n=1. Существуют
=4
различные ФАЛ.
Их можно определить с помощью табл. 2.6 в левой части которой указаны возможные наборы аргументов, а в правой значения ФАЛ на каждом наборе. Такая таблица называется таблицей истинности ФАЛ.
Кроме уже известных ФАЛ f1
иf2 в табл.3.1.
определены еще две ФАЛ:f3=x
- функция тождества;f4=
- функция отрицания (читаетсяf
равно "нех").
Таблица3.1
-
х
f1
f2
f3
f4
0
1
0
0
1
1
0
1
1
0
3. n=2. Существуют
=16
различных ФАЛ, которые задаются их
таблицей истинности (табл. 2.7.).
Первые шесть ФАЛ табл. 2.7. уже известны:f1 - константа 0;f2
константа 1;f3=
;
f4=
;
f5=
;
f6=
.
Функцияf7
называетсядизъюнкцией,
обозначаетсяf7=
\/
илиf7=
+
;
дизъюнкция принимает значение
1,если хотя быодин.из
аргументовpaвен 1.
Таблица3.2.
-
x1
x2
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
f16
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
1
1
1
0
0
0
1
0
0
1
0
0
Функция f8 называется
конъюнкцией, обозначаетсяf8=
/\
;
конъюнкция принимает значение 1,
если оба аргумента равны 1. Функцияf8
называетсяэквивалентностью
(равнозначностью) и обозначаетсяf9=
~
;
принимает значение 1, если аргументы
равны. Функцияf10 называетсясложением по модулю два
и обозначаетсяf10=
;
принимает значение 1 на тех наборах,
где значения аргументов не совпадают.
Функцияf11 называется
импликацией x1 в
x2 обозначаетсяf11=
.
Функцияf12 называетсяимпликацией x2 в
х1 и
обозначаетсяf12=
.
Функцияf13 называетсяфункцией Вебба
(стрелка Пирса) и
обозначаетсяf13=
.
Функцияf14 называетсяфункцией Шеффера
и обозначаетсяf11=
/
.
Функцииf15 иf16
специальных названий не имеют.
Перечисленные 14 ФАЛ называются элементарными и имеют особое значение в алгебре логики. Количество различных ФАЛ с увеличениемn растет очень быстро. Уже дляn=4 существуют 5536 различных ФАЛ.