67605
Булева алгебра, математическая логика, алгебра логики
Лекция
Математика и математический анализ
Каждому двоичному набору можно сопоставить число номер опр расстоянием Хемминга между вершинами и куба называется число опр наборы и называются соседними если и противоположными если все координаты разные.
Русский
2014-09-12
273 KB
1 чел.
Лекция №14 (14.03.00)
Булева алгебра, математическая логика, алгебра логики.
Литература:
1. Яблонский. Введение в дискретную математику. 1986, Москва, “Наука”
2. Гаврилов, Сапоженко. Задачи и упражнения по курсу дискретной математики.
опр || набор =(1, 2,…, n) где i{0,1}, i=1,…,n называется Булевым (двоичным) набором.
- i - компоненты набора (координаты вектора)
- n – длина набора (размерность).
опр || нормой вектора называют сумму его координат.
опр || множество всех двоичных наборов длины n образуют n-мерный булев (или двоичный) куб . Наборы называют вершинами куба .
Каждому двоичному набору можно сопоставить число (номер)
опр || расстоянием Хемминга между вершинами и куба называется число
опр || наборы и называются соседними если и противоположными если (все координаты разные).
опр || набор предшествует (или не больше) набора (), если i i, i=1,…,n.
Если , , то набор строго меньше (строго предшествует) набору ().
опр || наборы и называются сравнимыми, если или .
опр || набор непосредственно предшествует если и
утв || отношение является отношением частичного порядка на множестве .
опр || функция определенная на множестве и принимающая значения из множества {0,1} называется функцией алгебры логики (булевой функцией).
Множество всех булевых функций, зависящих от будем обозначать .
При n = 0 функция называется ноль местной (const) f=0 или f=1.
В произвольном случае f можно задать таблицей
|
… |
f |
||||
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
0 |
||
|
0 |
0 |
0 |
1 |
1 |
|
|
… |
… |
… |
… |
… |
… |
|
1 |
1 |
1 |
… |
1 |
1 |
в которой наборы выписываются в порядке возрастания их номеров.
Имея в виду такое расположение наборов функцию можно задать вектором ее значений
(1, 2,…, k), k=2n.
Элементарные функции
0 и 1 - местные
|
x |
f=0 |
f=1 |
f1 |
f2 |
|
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
f=0 - тождественный ноль,
f=1 - тождественная единица,
f1(x)=x – тождественная функция
;; - отрицание x, не x, not x
Двуместные функции
|
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
||
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
f3 - называется конъюнкция
f4 - дизъюнкция
f5 - сложение по модулю 2
f6 - эквиваленция (когда )
f7 - импликация
из правды правда, из лжи правда/ложь
f8 - штрих Шеффера, (антиконъюнкция, не-и)
f9 стрелка Пирса, антидизъюнкция, функция Вебба, не или
Символы … называются логическими связками.
опр || зависит существенным образом от аргумента , если такие значения переменных , что .
опр || Если для всех наборов то переменная xi называется фиктивной переменной.
опр || функции f1 и f2 называются равными, если f1 получается из f2 добавлением или изъятием фиктивных элементов.
Формулы
опр ||Формулой над множеством Ф функциональных символов будем называть всякое (и только такое) выражение вида
1) 0, 1- константы;
2) x-любая переменная из множества X;
3) выражения вида (UB), где U,B – формулы, - символ любой двуместной связки (,,,,,).
4) - отрицание;
Для сокращения записи формул принимаются следующие соглашения:
а) внешние скобки опускаются;
б) считается, что операция отрицания выполняется в первую очередь;
в) следующей по старшинству считается операция конъюнкции; затем – все остальные.
Примеры:
- не есть формула, так как неправильно стоят скобки,
- не стоят скобки вообще
Сопоставим формуле функцию
опр || Функцию называют симметричной по переменным , если для подстановки
Основные эквивалентности алгебры логики
Свойства:
1) коммутативность
2) ассоциативность
3) дистрибутивность
а)
б)
в)
4) правила Деморгана
а)
б)
5) правила поглощения
а)
б)
6)
а)
б)
7
а)
б)
в)
г)
д)
8)
а)
б)
в)
9)
а)
б)
Примеры
Доказать эквивалентность формул
Двойственные функции
опр || функция называется двойственной функцией к функции .
Пример.
|
x1 |
x2 |
x3 |
||
|
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
Правило ||
Чтобы получить двойственную функцию нужно инвертировать , а затем перевернуть таблицу.
Соответствие элементарных функций
f 0, 1, x, , x1&, x1
f* 1, 0, x, , x1, x1&
Из определения двойственности следует, что
Теорема || Пусть
Тогда
Доказательство ||
Отсюда вытекает принцип двойственности: двойственной к формуле
является формула .
Пусть формула содержит только символы &, , . Тогда для получения из U нужно заменить:
Из принципа двойственности вытекает, что
.
В частности,
.
