Дискретка учебник
.pdf
|
0bB @b |
@@bB1 |
|
|||
|
|
B |
|
|
B |
|
|
|
BB |
|
|
BB |
|
00bDD |
01BbDD |
10bDD |
BbDD |
11 |
||
|
D |
D |
|
D |
|
D |
|
DD |
|
DD |
DD |
|
DD |
И так далее. Так как на каждом ярусе дерева число ветвей, ведущих от корня, удваивается, то на n-ом ярусе число ветвей (число булевых
наборов) равно 2n. |
|
2 способ (методом математической индукции) |
|
Базис индукции |
|
Для n = 1 |
|B1| = 21 , то есть утверждение теоремы верно . |
Индуктивный переход |
|
Пусть теорема доказана для k = n − 1, то есть |Bn−1| = 2n−1. |
|
Докажем тождество для k = n. |
|
|
Набор |
α |
|
= |
|
(α1, α2, . . . , αn−1, αn) |
длины n отличается от набо- |
||||||
ра |
β = |
(α1, α2, . . . , αn−1) длины n-1 наличием одной координаты |
|||||||||||
αn |
{ |
0, 1e. Таким образом, набор α может принимать 2 значения: |
|||||||||||
e |
B |
} |
|
|
|
|
|
|
e |
|
, α2, . . . , αn−1, 1). Так количество |
||
α =e(α1, α2, . . . , αn−1, 0) либо |
α = (α1 |
||||||||||||
|
|
| |
| |
|
e |
· |
|
2n−1 |
|
|
|
|
e |
всех наборов |
β |
равно |
, то |
различных наборов α в 2 раза больше, |
|||||||||
|
|
|
e |
||||||||||
то есть |
|
n |
= 2 |
|
2n−1 = 2n. |
|
|
|
|
||||
Определение 2.3. Каждому двоичному набору αe Bn можно взаимно однозначно сопоставить целое неотрицательное число
|
|
|
|
|
|
|
|
|
n |
|
P (α) = αn ·20 |
+αn−1 ·21 |
|
|
|
|
|
|
∑i |
||
+αn−2 ·22 +· · ·+α2 ·2n−2 +α1 ·2n−1 = |
αi ·2n−i. |
|||||||||
e |
|
|
|
|
|
|
|
|
=1 |
|
Это число P (αe) называют номером набора αe. |
|
|
|
|
||||||
Например, |
набору |
|
α1 = (01001) соответствует |
номер |
||||||
P (α1) = 1 · 20 + 0 · 21 + 0 · 22 + 1 · 23 + 0 · 24 = 1 + 8 = 9. |
||||||||||
e |
|
e |
|
|
≤ |
|
≤ |
− |
|
e |
Очевидно, что набор |
α |
- |
двоичное разложение своего номера |
P (α). |
||||||
|
e |
|
e |
2n |
|
1. |
|
|||
Из определения номера следует, что 0 P (α) |
|
|
||||||||
11
Определение 2.4. Функция fe(x1, x2, . . . , xn−1, xn), областью определения которой является n-мерный булев куб Bn, а множеством значений - множество B {0, 1}, называется булевой функцией или
функцией алгебры логики.
Набор символов переменных (x1, x2, . . . , xn−1, xn) обычно обозначается xe (то есть xe = (x1, x2, . . . , xn−1, xn) ).
Множество всех булевых функций, зависящих от n переменных, принято обозначать через P2(n).
2.2Способы задания булевых функций
2.2.1Табличный способ задания
Любую булеву функцию f(xe) при n ≥ 1 можно задать таблицей T (f), в которой двоичные наборы σe = (σ1, σ2, . . . , σn) выписываются строго в порядке возрастания их номеров (так называемое стандартное или лексикографическое расположение наборов). Булевы наборы располагают в левой части таблицы, а соответствующее данному набору значение функции - в правой. Такая таблица называется таблицей истинности булевой функции.
|
|
|
|
x1 x2 |
· · · |
xn−1 xn |
f(x1, x2, . . . , xn−1, xn) |
||||
P (σ) = 0 |
|
|
0 |
0 |
· · · |
0 |
0 |
f(0, 0, . . . , 0, 0) |
|||
P (σ) = 1 |
|
|
0 |
0 |
· · · |
0 |
1 |
f(0, 0, . . . , 0, 1) |
|||
σ |
|
|
|
0 |
0 |
|
1 |
0 |
f |
, , . . . , |
, |
P (e) = 2 |
|
|
· · · |
|
(0 0 |
1 0) |
|||||
e |
|
|
|
|
|
|
|
|
|
|
|
σ |
n |
|
|
1 |
1 |
· · · |
0 |
1 |
f |
· · · |
, |
|
− 3 |
· · · |
, , . . . , |
||||||||
P (e) = 2n |
|
(1 1 |
0 1) |
||||||||
P (σ) = 2n |
− 2 |
1 |
1 |
· · · |
1 |
0 |
f(1, 1, . . . , 1, 0) |
||||
e |
|
|
|
1 |
1 |
|
1 |
1 |
f |
, , . . . , |
, |
σ |
|
|
1 |
|
|||||||
P (e) = 2 |
− |
· · · |
|
(1 1 |
1 1) |
||||||
e |
|
|
|
|
|
|
|
|
|
||
Замечание 2.2. Так как |Bn| = 2n, то таблица истинности булевой функции, зависящей от n переменных, содержит ровно 2n строк.
Замечание 2.3. Таблица истинности задаёт любую функцию алгебры логики единственным образом.
12
Пример 2.2. Табличный способ задания функции двух переменных:
0 |
x1 x2 |
f(x1, x2) |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
2 |
1 |
0 |
1 |
3 |
1 |
1 |
0 |
2.2.2Векторный способ задания булевой функции
Так как левая часть таблицы истинности любой двоичной функции n переменных одинакова, различаются лишь правые части, то булевы функции удобно задавать вектором значений
fe= (α0, α1, α2, . . . , α2n−2, α2n−1),
где координата αi равна значению функции f(xe) на наборе σei, имеющем номер i ( то есть, f(σei) = αi, P (σei) = i).
При векторном задании функции столбец из правой части таблицы истинности переписывают в виде вектора-строки.
Пример 2.3. fe(x1, x2) = (0110) - векторный способ задания функции из примера 2.2.
Замечание 2.4. Длина вектора-строки булевой функции n переменных равна 2n. И наоборот - соответствующий показатель степени двойки булевого набора при векторном задании функции определяет число переменных этой функции.
Замечание 2.5. Вектор значений двоичной функции также задаёт её единственным образом.
Теорема 2.2. Число булевых функций, зависящих от n переменных, равно 22n :
|P2(n)| = 22n .
13
Доказательство. Так как длина вектора значений двоичной функции n переменных равна k = 2n, а различные функции имеют различные векторы значений, то число различных функций совпадает с количе-
ством различных наборов длины k. Число всех наборов длины k равно 2k = 22n . То есть, |P2(n)| = 22n . 
2.2.3Носитель функции алгебры логики
Определение 2.5. Наборы, на которых значение функции равно 1, называют единичными наборами . Множество всех единичных наборов данной функции - единичным множеством или носителем булевой функции Nf .
Nf = {σe Bn|f(σe) = 1}
Аналогично, наборы, на которых значение функции равно 0, называют нулевыми наборами . Множество всех нулевых наборов данной функции - дополнением к носителю двоичной функции Nf .
Nf = Nf = {σe Bn | f(σe) = 0}
Очевидно, что для задания булевой функции достаточно указать либо только носитель функции, либо только дополнение к нему. Перечисление единичных (нулевых) наборов определяет еще один способ задания булевой функции - с помощью носителя.
Замечание 2.6. Так как все двоичные наборы принадлежат либо носителю, либо его дополнению, то | Nf | + | Nf |= 2n.
Пример 2.4. Указать носитель и его дополнение для функции из примера 2.2.
Решение. |
|
|
Подчеркнем в таблице истинности функ- |
||||
|
x1 |
x2 |
|
f(x1, x2) |
|||
|
|
|
|
ции наборы, на которых значение функ- |
|||
0 |
0 |
|
0 |
||||
0 |
1 |
|
1 |
ции равно 1. Эти наборы принадлежат |
|||
|
|
|
|
|
носителю Nf . Неподчеркнутые наборы |
||
1 |
0 |
|
1 |
||||
|
|
|
|
|
составляют дополнение к множеству Nf . |
||
1 |
1 |
|
0 |
||||
|
|
|
|
|
|
|
|
Выпишем оба множества: Nf = {(01), (10)}; Nf = {(00), (11)}.
14
2.2.4Геометрический способ задания двоичной функции
К геометрическим способам задания булевых функций относятся изображение функции на булевом кубе и карты Карно.
На булевом кубе обычно изображаются функции, зависящие не более чем от 3 переменных. Это связано со сложностью изображения и отсутствием наглядности двоичных кубов Bn при n > 4 (см. замечание 2.1 после примера 2.1 на стр. 10).
На кубе B2 или B3 отмечают двоичные наборы (вершины куба), затем каким-либо образом выделяют наборы носителя. Мы будем закрашивать вершины носителя в черный цвет. Вершины, принадлежащие дополнению к носителю, останутся белыми.
Карты Карно можно рассматривать как некую плоскую развертку n−мерного куба Bn. Подробно они будут изучены в разделе 6.1 на странице 90.
Замечание 2.7. Геометрическое изображение любой булевой функции задаёт её единственным образом. И наоборот, любую двоичную функцию можно изобразить на кубе, притом едиственным образом.
Пример 2.5. Изобразить геометрически функцию fe(x1, x2) = (0110) из примера 2.2.
Решение. Обозначим вершины носителя на двоичном кубе черным цветом:
x2
u6 e
(01) (11)
eu - x1
(00)(10)
Пример 2.6. Изобразить геометрически функцию, заданную вектором fe= (0110 0110).
Решение. Поскольку длина вектора |
значений |
функции |
равна |
|||
8 |
= |
23, |
функция зависит от 3-х |
переменных (см. |
замеча- |
|
ние |
2.4 |
на |
стр.13). Строим трехмерную |
систему |
координат, рису- |
|
ем единичный куб. Носитель данной функции содержит 4 набора: Nf = {(001), (010), (101), (110)}. Отмечаем эти вершины на кубе.
15
x |
y |
z |
|
f |
|
|
|
z |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
|
0 |
|
|
|
6 |
|
|
e |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
0 |
0 |
1 |
|
1 |
(001) |
u |
|
|
(011) |
||||
0 |
1 |
0 |
|
1 |
|
|
|
|
|
|
|
||
0 |
1 |
1 |
|
0 |
|
|
|
|
(111) |
|
|||
|
|
|
|
|
|
||||||||
|
(101) |
u |
|
|
e |
|
- |
|
y |
||||
1 |
0 |
0 |
|
0 |
|
|
(000)e |
|
u(010) |
||||
1 |
0 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
(100) |
|
|
(110) |
|
||||||||
1 |
1 |
0 |
|
1 |
|
|
|
||||||
|
e |
|
|
u |
|
|
|
|
|||||
1 |
1 |
1 |
|
0 |
х |
|
|
|
|
|
|
|
|
Мы изучили 4 способа задания булевых функций. Еще один способ, с помощью формул, мы изучим в пункте 2.3.3 на стр. 19.
2.2.5 Способы задания функций алгебры логики, изучаемые в нашем курсе:
1. Таблица истинности
2. Вектор значений
3. Носитель функции либо его дополнение
4. Геометрический способ
5. Формула
2.3Элементарные булевы функции
2.3.1Двоичные функции одной переменной
Логических функций одной переменной 221 = 22 = 4. Перечислим таблицы истинности всех функций .
|
x |
x |
|
|
а) |
0 |
0 |
f1(x) = x |
- тождественная функция . |
1 |
1 |
|
|
|
Какое бы значение (0 или 1) не принимала переменная х, значение тождественной функции совпадает со значением переменной.
16
|
x |
|
|
|
f2(x) = |
|
= ¬x - функция отрицание, инверсия, |
|
|
x |
|
x |
|||
б) |
|
|
|
логическое "НЕ" (в информатике часто обозначается |
|||
0 |
1 |
|
|||||
|
1 |
0 |
|
"NOT" ). |
|||
Какое бы значение не принимала переменная х, функция "отрицание" принимает противоположное значение .
|
x |
0 |
|
|
в) |
0 |
0 |
f3(x) ≡ 0 |
- функция тождественный нуль . |
1 |
0 |
|
|
|
Вне зависимости от значений переменной х, значение функции всегда
равно нулю. |
|
|
||
|
x |
1 |
f4(x) ≡ 1 |
- функция тождественная единица |
г) |
|
|
||
0 |
1 |
|||
1 |
1 |
. |
|
|
|
|
|||
Значение функции всегда равно единице.
2.3.2Булевы функции двух переменной
Всего двоичных функций двух переменных 222 = 24 = 16. Однако, лишь семь из них имеют свои названия. Именно с их таблицами ис-
тинности мы сейчас познакомимся . |
|
|||||
|
x |
y |
xy |
f1(x, y) = x · y = x y = x&y = xy |
- функ- |
|
|
0 |
0 |
0 |
|||
а) |
0 |
1 |
0 |
ция конъюнкция, логическое умножение, логиче- |
||
ское "И" ( в информатике обычно обозначается |
||||||
|
1 |
0 |
0 |
|||
|
"AND"). |
|
||||
|
1 |
1 |
1 |
|
||
|
|
|
||||
Замечание 2.8. Логическое умножение булевых переменных 0 и 1 соответствует обычному умножению чисел 0 и 1.
Замечание 2.9. xy = min(x, y).
|
x |
y |
x y |
f2(x, y) = x y |
- функция дизъюнкция, |
|
б) |
0 |
0 |
0 |
|||
0 |
1 |
1 |
логическое сложение, |
"логическое ИЛИ" |
||
|
1 |
0 |
1 |
("OR"). |
|
|
|
1 |
1 |
1 |
|
|
|
Замечание 2.10. x y = max(x, y).
17
|
x |
y |
x y |
|
|
|
0 |
0 |
0 |
f3(x, y) = x y |
- функция сложение |
в) 0 |
1 |
1 |
|||
1 |
0 |
1 |
по модулю 2, "исключающее ИЛИ" ("ХOR"). |
||
|
|
||||
1 |
1 |
0 |
|
|
|
Замечание 2.11. Значение данной функции равно остатку от деления обычной алгебраической суммы чисел х и y на 2.
Замечание 2.12. На двоичных наборах (00), (01) и (10), на которых сумма чисел х и y не превышает 1, оба сложения ( логическое и по модулю 2) равны между собой. Различаются эти функции алгебры логики только на наборе (11).
|
x |
y |
x y |
г) |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
1 |
0 |
0 |
|
1 |
1 |
1 |
f4(x, y) = x y = x ≡ y - функция
эквивалентность, "логическое тождество".
Замечание 2.13. Значение функции "эквивалентность" на каждом наборе противоположно значению функции "сложение по модулю 2". Cправедливо тождество x y = x y.
|
x |
y |
x → y |
|
0 |
0 |
1 |
д) 0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
|
f5(x, y) = x → y = x y - функция
импликация, "логическое следование".
Замечание 2.14. "Импликация" - единственная из перечисленных функций, которая не обладает свойством коммутативности, то есть
x → y ̸≡y → x
.
Замечание 2.15. Мнемоническое правило для запоминания: из "лжи" может следовать всё, что угодно; из "истины" следует только истина.
18
|
x |
y |
x|y |
|
|
|
0 |
0 |
1 |
f6(x, y) = x|y |
- функция штрих |
е) 0 |
1 |
1 |
|||
1 |
0 |
1 |
Шеффера, "НЕ И" |
("NOT AND"). |
|
|
|
||||
1 |
1 |
0 |
|
|
|
Замечание 2.16. x|y = xy.
|
x |
y |
x ↓ y |
|
|
|
|
0 |
0 |
1 |
f7(x, y) = x ↓ |
y |
- функция стрелка |
ж) 0 |
1 |
0 |
||||
1 |
0 |
0 |
Пирса, "НЕ ИЛИ" |
("NOT OR"). |
||
|
|
|
||||
1 |
1 |
0 |
|
|
|
|
Замечание 2.17. x ↓ y = x y.
Вышеперечисленные функции одной и двух переменных называются элементарными булевыми функциями. Остальные двоичные функции двух и более переменных можно выразить через элементарные с помощью формул.
2.3.3Формулы
Определение |
2.6. Функция |
F называется |
суперпозици- |
ей функций |
f,f1,f2, . . . , fm, |
если имеет |
место равенство |
F (x1, x2, . . . , xn) = f(g1(x1, . . . , xn), g2(x1, . . . , xn), . . . , gk(x1, . . . , xn)),
где каждая из функций gi(x1, x2, . . . , xn) совпадает либо с одной из переменных (тождественная функция), либо с одной из функций f1,f2, . . . , fm.
Формулой называется выражение, описывающее эту суперпозицию.
Пример 2.7.
а) Функция f1(x, y) = x|y = x&y является суперпозицией функций
"отрицание" (¬) и "конъюнкция" (&). При этом x|y и x&y - формулы, описывающие эту суперпозицию.
б) Функция f2(x, y, z) = x y → (x z) является суперпозицией функций "дизъюнкция" ( ) и "импликация " (→).
19
Таким образом, формулы задают ещё один удобный способ задания булевых функций.
Определение 2.7. Если функция задана формулой, то говорят, что формула реализует или представляет данную функцию.
Замечание 2.18. Как видно из примера 2.7 а), одна и та же функция может задаваться несколькими формулами. В отличие от остальных способов задания, представление булевой функции формулой не единственно.
Определение 2.8. Формулы, реализующие одну и ту же функцию, называются эквивалентными или равносильными.
Для доказательства эквивалентности формул строят таблицу истинности или вектор значений соответствующих функций и сравнивают их. В случае равенства полученных функций формулы, их реализующие, равносильны.
Пример 2.8. Формулы x|y и x&y из примера 2.7 а) эквивалентны.
2.3.4Приоритет выполнения булевых функций
1.Сначала выполняются все действия в скобках.
2.Функция "отрицание переменной" выполняется прежде других булевых функций. При этом учитывают, что, в случае инверсии некоторой формулы, скобки вокруг этой формулы могут быть опущены. Так, в примере 2.7 а) в формуле x&y отсутствуют скобки : x&y = (x&y), поэтому сначала вычисляют выражение x&y, а затем инвертируют его значение.
3.Логическое умножение (&) выполняется раньше, чем сложение (и логическое ( ), и по модулю два ( )).
Замечание 2.19. Порядок выполнения функций алгебры логики совпадает с порядком выполнения одноименных функций в математике.
20