Функции алгебры логики, зависящие от одного аргумента
№ п/п |
|
|
|
|
|
|
|
|
|
||
1 |
0 |
0 |
0 |
1 |
1 |
2 |
1 |
0 |
1 |
0 |
1 |
3 |
|
н/с |
с |
с |
н/с |
Рассмотрим
множество функций, зависящих от двух
аргументов, т.е.
:
.
Количество этих функций составляет
.
Среди этих функций найдутся функции
как существенно, так и несущественно
зависящие от аргументов
и
.
Рассмотрим только те функции алгебры
логики вида
,
которые существенно зависят от своих
аргументов. Эти функции представлены
в виде таблицы истинности (табл. 1.4).
Таблица 1.4
Таблица истинности элементарных функций алгебры логики
|
|
|
|
|
|
|
|
|
|
|
|
(+) |
↓ |
|
→ |
||
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
(&)
(~)
/
В
таблице 1.4 функции
означают следующее:
функция
логического сложения, дизъюнкция
(функция «или») :
;
функция
логического умножения, конъюнкция
(функция «и»):
;
эквиваленция,
функция принимает значение 1 если
значения обоих аргументов одинаковы:
;
сложение по модулю2,
принимает значение 1 при различных
значениях аргументов:
;
функция
Вебба, принимает значения, обратные
дизъюнкции:
;
штрих
Шеффира – принимает значения, обратные
конъюнкции:
импликация:
(читается, если
,
то
,
или
влечет за собой
,
или
имплицирует
).
Свойства операций дизъюнкции, конъюнкции и отрицания
Коммутативность.
;
.
Ассоциативность.
;
.
Дистрибутивность.
;
.
Теоремы А. Де-Моргана.
;
Имеют место следующие выражения
;
;
;
;
;
;
;
.
Свойства
операций дизъюнкции, конъюнкции и
отрицания могут быть доказаны с помощью
таблиц истинности. Приведём пример
даказательства. Докажем, например, одну
из теорем А. Де-Моргана
.
Слева и справа от знака равенства стоят
функции ылгебры логики:
и
,
равенство которых необходимо установить.
Вспомним определение равенства функций
алгебры логики: две функции алгебры
логики называются равными тогда и только
тогда, когда на равных наборах значений
аргументов они принимают одинаковые
значения. Составим таблицы истинности
для функций
и
(таблицы 1.5 и 1.6 соответственно).
Таблица 1.5 Таблица истинности для функции |
|
Таблица 1.6 Таблица истинности для функции |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
На основе таблиц 1.5 и 1.6 можно сделать вывод о равенстве функций алгебры логики и .
Свойства сложения по модулю 2
Для функции сложения по модулю 2 имеют место коммутативный, ассоциативный, а также дистрибутивный закон относительно конъюнкции.
Коммутативность.
;
Ассоциативность.
.
Дистрибутивность относительно конъюнкции.
.
Имеют место следующие очевидные соотноше6ния:
;
;
;
.
Кроме
того, имеет место формула
.
Свойства импликации
В отличие от ранее рассмотренных функций для импликации не имеют места коммутативный и ассоциативный законы:
и
.
Для импликации выполняются следующие соотношения:
;
;
;
;
;
;
;
.
Функции дизъюнкции и конъюнкции могут быть выражены через импликацию:
;
.
Доказательство этих формул может быть проведено на основе таблиц истинности. Проверка справедливости этих соотношений предоставляется студентам.
Свойства операции штрих Шеффера и функции Вебба.
Для функций Шеффера и Вебба имеет место коммутативный закон:
;
.
Свойство ассоциативности для этих функций не выполняется.
;
.
Имеют место следующие очевидные соотношения:
;
;
;
;
;
;
;
;
;
.
Доказательство соотношений рекомендуется студентам провести самостоятелльно.