Булевы алгебры.
Пусть М – множество, в котором выделены два
несовпадающих элемента:
.
Предположим, что над его элементами определены три операции: первая
каждому элементу
сопоставляет некоторый элемент
,
вторая каждой паре элементов
сопоставляет элемент
,
третья каждой паре элементов
сопоставляет элемент
.
Множество М называется булевой алгеброй, если для всех
элементов x, y, z из М
справедливы следующие равенства:
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Операция
называется булевым дополнением, а операции
– булевым умножением и булевым сложением. Элементы
называются булевым нулем и булевой единицей.
Алгебра логики.
Логической переменной называется переменная величина, которая может принимать только два значения: 0 и 1. Логической функцией от п логических переменных называется функция от этих переменных, которая может принимать только два значения: 0 и 1. Логическая функция задана, если для любого набора значений ее аргументов определено соответствующее значение функции. Таким образом, логическая функция может быть задана таблицей ее значений для любого набора переменных:
|
|
|
… |
|
|
|
0 |
0 |
… |
0 |
|
|
0 |
0 |
… |
1 |
|
|
… |
… |
… |
… |
… |
|
1 |
1 |
… |
1 |
|
Количество строк в этой таблице равно количеству различных наборов
значений переменных, т.е. количеству различных последовательностей и
нулей и единиц длины п. Поэтому таблица имеет
строк.
Количество различных логических функций от п переменных равно
количеству различных последовательностей и нулей и единиц длины
,
т.е.
.
Над логическими переменными и логическими функциями можно выполнять булевы операции (т.е. сложение, умножение, дополнение). Множество логических функций с операциями отрицания (дополнения), конъюнкции (умножения) и дизъюнкции (сложения) называется алгеброй логики. При этом две функции в алгебре логики считаются совпадающими, если они зависят от одних и тех же аргументов и задаются одинаковыми таблицами.
Любую логическую функцию можно задать не только таблицей, но и
формулой, т.е. выражением, составленным из независимых логических
переменных с помощью булевых операций. Функцию вида
,
где
равно
или
,
назовем элементарным произведением. Она принимает значение 1 тогда и
только тогда, когда все
равны 1. Рассмотрим произвольную логическую
функцию
.
Выделим в таблице, задающей эту функцию, строки, в которых функция
равна 1. Пусть таких строк k и
– элементарные произведения, соответствующие этим строкам.
Тогда
.
Таким образом можно задать формулой любую функцию, заданную таблицей.
Например, пусть функция задается таблицей:
|
x |
y |
z |
|
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
Семь строк этой таблицы соответствуют значениям
.
Поэтому формула для
будет содержать семь членов:
.
Упростим это выражение:
Литература
[1] Л. А. Басова, М. А. Шубин, Л. А. Эпштейн Лекции и задачи по математике. – М. Просвещение, 1981.
