ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1344
Скачиваний: 1
3
Дискретная математика или, как часто говорят, компьютерная ма-
тематика в XXI веке стала универсальным языком описания и исследо-
ваний в менеджменте, превратилась в базовый инструмент анализа и мо-
делирования. Именно на этом языке сегодня осмысливают свои пробле-
мы и поддерживают профессиональное общение системные аналитики,
управленческие консультанты, специалисты по организационному про-
ектированию.
Настоящее пособие рекомендовано студентам первого курса факуль-
тета прикладной математики, информатики и механики ВГУ всех форм
обучения. Оно содержит не только необходимый перечень упражнений
для изучения основных понятий дискретной математики, но и изложен-
ные в компактной форме теоретические сведения и задания для приоб-
ретения и закрепления навыков решения прикладных задач.
§1.
Булевы наборы. Единичный n-мерный куб
Обозначим через
E
множество
{
0; 1
}
, тогда
E
n
представля-
ет собой множество упорядоченных наборов вида
(
α
1
, α
2
, . . . , α
n
)
, где
α
i
∈
E, i
= 1
, . . . , n
. Такие наборы называются булевыми. Для кратко-
сти будем обозначать
α
α
= (
α
1
, α
2
, . . . , α
n
)
. Число
n
называется длиной
набора, множество
E
n
- единичным n-мерным кубом, сами наборы - вер-
шинами куба. Весом или нормой набора
α
α
длины
n
называется число
его координат, равных единице:
∥
α
α
∥
=
n
∑
i
=1
α
i
.
Каждому булеву набору
α
α
длины
n
можно поставить в соответ-
ствие число
ν
(
α
α
) =
n
∑
i
=1
α
i
2
n
−
i
,
называемое номером набора
α
α
. Набор
α
α
является, очевидно, двоичным
разложением числа
ν
(
α
α
)
. Расстоянием (Хемминга) между вершинами
α
α
и
β
β
куба
E
n
называется число
ρ
(
α
α, β
β
) =
n
∑
i
=1
|
α
i
−
β
i
|
,
равное числу координат, в которых они различаются. Наборы
α
α
и
β
β
∈
E
n
называются соседними, если
ρ
(
α
α, β
β
) = 1
и противоположными,
если
ρ
(
α
α, β
β
) =
n
. Неупорядоченная пара соседних наборов (вершин) на-
зывается ребром куба. Говорят, что набор
α
α
∈
E
n
предшествует набору
4
β
β
∈
E
n
(обозначается
α
α
≤
β
β
), если
α
i
≤
β
i
для всех
i
= 1
, . . . , n
.
Если при этом
α
α
̸
=
β
β
, то говорят, что
α
α
строго предшествует
β
β
. Если
имеет хотя бы одно из соотношений
α
α
≤
β
β
или
β
β
≤
α
α
, то наборы
α
α
и
β
β
называются сравнимыми. В противном случае наборы
α
α
и
β
β
на-
зываются несравнимыми. Набор
α
α
∈
E
n
непосредственно предшествует
набору
β
β
∈
E
n
, если
α
α < β
β
и
ρ
(
α
α, β
β
) = 1
.
Отношение предшествования между наборами является отноше-
нием частичного порядка на
E
n
. Через
α
α
⊕
β
β
обозначим набор
(
α
1
⊕
β
1
, α
2
⊕
β
2
, . . . , α
n
⊕
β
n
)
, полученный сложением по
mod
2
век-
торов
α
α
и
β
β
.
На нижеприведенном рисунке изображены диаграммы часто упо-
требляемых множеств
E
3
и
E
4
.
Рис. 1
Упражнения
1.1.
Найти число наборов из
E
n
веса
k
. Чему равно всех вершин куба
E
n
?
1.2.
Найти номера наборов
(0111)
,
(10101)
,
(110010)
. Найти векторы
длины 6, являющиеся двоичным разложением чисел 11, 17, 20.
1.3.
Найти число неупорядоченных пар соседних вершин
E
n
.
1.4.
Показать, что для любых
α
α, β
β, γ
γ
∈
E
n
справедливы соотношения
а)
ρ
(
α
α, γ
γ
)
≤
ρ
(
α
α, β
β
) +
ρ
(
β
β, γ
γ
)
;
б)
ρ
(
α
α, γ
γ
) =
ρ
(
α
α
⊕
β
β, γ
γ
⊕
β
β
)
;
в)
ρ
(
α
α, β
β
) =
∥
α
α
∥
+
∥
β
β
∥ −
2
∥
α
α
∩
β
β
∥
;
г)
ρ
(
α
α, β
β
) =
∥
α
α
+
β
β
∥
.
Здесь через
α
α
∩
β
β
обозначается вектор,
i
-я координата которого равна
1 тогда и только тогда, когда
α
i
=
β
i
= 1
.
5
§2.
Способы задания булевых функций.
Элементарные функции. Формулы
Функция
f
(
x
1
, x
2
, . . . , x
n
)
, определенная на множестве
E
n
и прини-
мающая значения на множестве
E
=
{
0; 1
}
, называется булевой функ-
цией. Множество всех булевых функций обозначим Б .
Булеву функцию
f
(
x
1
, x
2
, . . . , x
n
)
можно задать таблицей:
x
1
x
2
. . .
x
n
−
1
x
n
f
(
x
1
, x
2
, . . . , x
n
−
1
, x
n
)
0
0
. . .
0
0
f
(0
,
0
, . . . ,
0
,
0)
0
0
. . .
0
1
f
(0
,
0
, . . . ,
0
,
1)
0
0
. . .
1
0
f
(0
,
0
, . . . ,
1
,
0)
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
1
1
. . .
1
1
f
(1
,
1
, . . . ,
1
,
1)
Здесь наборы
α
α
∈
E
n
расположены в порядке возрастания из номеров.
В дальнейшем предполагая такое стандартное расположение наборов,
будем задавать функцию
f
(
x
1
, x
2
, . . . , x
n
)
набором
(
γ
0
, γ
1
, . . . , γ
2
n
−
1
)
,
в котором координата
γ
i
представляет собой значение функции
f
(
x
1
, x
2
, . . . , x
n
)
на наборе
α
α
с номером
i
(
i
= 0
,
1
, . . . ,
2
n
−
1)
.
Символом
N
f
будем обозначать множество
{
α
α
:
α
α
∈
E
n
, f
(
α
1
, α
2
, . . . , α
n
) = 1
}
.
Множество
N
f
называется множеством истинности функции
f
. Между
множеством булевых функций
f
от
n
переменных и множеством под-
множеств
N
f
⊆
E
n
существует взаимнооднозначное соответствие. Это
соответствие обладает следующими свойствами.
Пусть
f
1
(
x
1
, . . . , x
n
)
,
f
2
(
x
1
, . . . , x
n
)
– произвольные булевы функ-
ции. Тогда
а)
N
¯
f
=
E
n
\
N
f
;
б)
N
f
1
∧
f
2
=
N
f
1
∩
N
f
2
;
в)
N
f
1
∨
f
2
=
N
f
1
∪
N
f
2
;
г)
f
1
≤
f
2
⇔
N
f
1
⊆
N
f
2
.
Булевы функции, заданные следующими таблицами, будем назы-
вать элементарными.
x
0 1
f
1
f
2
0
0
1
0
1
1
0
1
1
0
6
x
1
x
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
0
Приведем обозначения и названия этих функций
1. Функции
0
и
1
называются тождественными нулем и единицей.
2. Функция
f
1
называется тождественной функцией и обозначается
через
x
.
3. Функция
f
2
называется отрицанием
x
и обозначается через
¯
x
или
¬
x
и читается "не
x
".
4. Функция
f
3
называется конъюнкцией
x
1
и
x
2
, обозначается
x
1
&
x
2
или
x
1
·
x
2
или
x
1
∧
x
2
и читается "
x
1
и
x
2
".
5. Функция
f
4
называется дизъюнкцией
x
1
и
x
2
, обозначается
x
1
∨
x
2
и читается "
x
1
или
x
2
".
6. Функция
f
5
называется суммой по модулю 2
x
1
и
x
2
, обозначается
x
1
⊕
x
2
и читается "
x
1
плюс
x
2
".
7. Функция
f
6
называется эквивалентностью
x
1
и
x
2
, обозначается
x
1
↔
x
2
или
x
1
∼
x
2
и читается "
x
1
эквивалентно
x
2
".
8. Функция
f
7
называется импликацией
x
1
и
x
2
, обозначается
x
1
→
x
2
и читается "из
x
1
следует
x
2
".
9. Функция
f
8
называется штрихом Шеффера
x
1
и
x
2
, обозначается
x
1
|
x
2
и читается "не (
x
1
и
x
2
)".
10. Функция
f
10
называется стрелкой Пирса
x
1
и
x
2
, обозначается
x
1
↓
x
2
и читается "не (
x
1
или
x
2
)".
Символы
¬
,
∧
(&)
,
∨
,
⊕
,
↔
,
→
,
|
,
↓
называются логическими связками.
Булева функция может быть задана при помощи формулы. Для
определения формулы введем следующие группы символов:
1)
малыми латинские буквы с индексами или без них :
x, y, z, x
1
,
x
2
, . . . , x
n
, . . .
; обозначим множество этих символов через
X
;
2)
булевы функции:
0
и
1
;
3)
логические связки:
¬
,
∧
(&)
,
∨
,
⊕
,
↔
,
→
,
|
,
↓
; обозначим множество
логических связок через
σ
;
7
4)
скобки (,).
Определение.
Формулой над множеством связок
σ
назовем:
а)
символы первой и второй группы;
б)
если
U
и
B
– формулы, то формулами назовем (
¬ U
), (
U ∧ B
),
(
U ∨ B
), (
U → B
), (
U ↔ B
), (
U ⊕ B
), (
U|B
), (
U ↓ B
);
в)
никаких других формул, кроме введенных в пунктах а) и б), в ал-
гебре высказываний нет.
Для сокращения записи формул принимаются следующие соглаше-
ния:
а)
внешние скобки у формул опускаются;
б)
формула (
¬ U
) записывается в виде
¯
U
;
в)
формула (
U ∧ B
) записывается в виде (
UB
);
г)
считается, что связка
¬
сильнее любой другой связки из
σ
;
д)
связка
∧
сильнее, чем любая из связок
∨
,
⊕
,
↔
,
→
,
|
,
↓
.
Эти соглашения позволяют, например, формулу
((
x
∧
y
)
→
(
¬
z
))
переписать в виде
xy
→
¯
x
.
Говорят, что формула алгебры высказывания
Φ
реализует булеву
функцию
f
, если множества истинности
N
f
, N
Φ
функций
f
и
Φ
, рас-
сматриваемых как функции от одних и тех же переменных, совпадают:
N
F
=
N
Φ
.
Пусть
{
x
1
, x
2
, . . . , x
n
}
– множество тех переменных, которые встре-
чаются хотя бы в одной из формул
U
или
B
. Формулы
U
и
B
назы-
ваются эквивалентными (обозначается
U
=
B
или
U ≡ B
), если на
всяком наборе
(
α
1
, α
2
, . . . , α
n
)
значений переменных
x
1
, x
2
, . . . , x
n
зна-
чения функций, реализуемых формулами
U
и
B
, совпадают.
Формула называется тождественно истинной (тождественно лож-
ной), если реализуемая ею функция равна 1 (соответственно 0) на всяком
наборе переменных.
Формула называется выполнимой(опровержимой), если существует
набор значений переменных, на котором реализуемая формулой функ-
ция принимает значение 1 (0).
Упражнения
2.1.
Найти число булевых функций от
n
переменных, принимающих на
противоположных наборах одинаковые значения.