Лекция 3: множества и логика



Скачать 95.82 Kb.

Дата15.02.2017
Размер95.82 Kb.
Просмотров154
Скачиваний0

Лекция 3: множества и логика
Дискретная математика, ВШЭ, факультет компьютерных наук
(Осень 2014 – весна 2015)
Мы уже использовали понятие множества и в дальнейшем будем его использовать посто- янно. Сейчас мы обсудим это понятие и связанные с ним более систематически.
Неформально, множество — это совокупность каких-то элементов и полностью определяет- ся своими элементами. Мы будем говорить, что элемент x принадлежит множеству A, если он является его элементом. Обозначать это будем так: x ∈ A (таким образом, эта запись означает утверждение и принимает логические значения «истина», «ложь»).
Равенство множеств A = B это утверждение, которое означает, что множества состоят из одних и тех же элементов. Более подробно: любой элемент множества A принадлежит множе- ству B и любой элемент множества B принадлежит множеству A.
Эти два условия естественно разделить. Получим отношение включения между множества- ми. Если любой элемент множества A принадлежит множеству B, то множество A называется подмножеством множества B, обозначение A ⊆ B.
Равенство множеств и включение напоминают равенство чисел и сравнение чисел по вели- чине и обладают похожими свойствами.
Есть уникальное множество — пустое, — которое не содержит никаких элементов. Обозна- чение ∅.
Если элементов в множестве мало, его можно задать, указав все эти элементы. При этом принято заключать список элементов в фигурные скобки. Хотя на письме мы вынуждены записывать множества в каком-то порядке, этот порядок не играет роли. Поэтому
{0, 2, 4, 6, 8} = {4, 2, 0, 8, 6}
и это просто разные обозначения множества четных цифр.
Количество элементов в множестве A, если оно конечно, будем обозначать |A| и называть мощностью множества. Мощность возможно определить и для бесконечных множеств, но это более тонкий вопрос и сейчас мы его обсуждать не будем.
На множествах определено большое количество операций, самые важные из которых мы сейчас перечислим.
Объединение множеств. Обозначение A ∪ B. Это множество, состоящее в точности из всех элементов множеств A и B.
Пересечение множеств. Обозначение A ∩ B. Это множество, состоящее в точности из тех элементов, которые принадлежат обоим множествам A и B.
Разность множеств. Обозначение A \ B. Это множество, состоящее в точности из тех эле- ментов, которые принадлежат множеству A, но не принадлежат множеству B.
Симметрическая разность множеств. Обозначение A
B. Это множество, состоящее в точ- ности из тех элементов, которые принадлежат ровно одному из множеств: либо A, либо B.
Есть графический способ иллюстрировать операции с множествами: круги Венна. На па- ре кругов легко нарисовать объединение, пересечение, разность и симметрическую разность множеств.
Элементами множества могут быть другие множества. По любому множеству A определено множество его подмножеств, которое обозначается 2
A
. Есть способ определить возведение в степень A
B
для любых множеств, но мы пока его не будем обсуждать.
Декартово произведение множеств. Обозначение A × B. Это множество, состоящее из всех последовательностей длины 2 вида (a, b), где a ∈ A, b ∈ B.
1

Формулу произведения можно выразить через декартово произведение так:
|A × B| = |A| · |B|.
Декартова степень множества. Обозначение A
n
. Это множество, состоящее из всех после- довательностей длины n, каждый член которых принадлежит множеству A.
1
Теоретико-множественные тождества
Может так оказаться, что две разные формулы с теоретико-множественными операциями за- дают одно и то же множество при любых значениях входящих в них переменных множеств.
Такая пара фомул образует теоретико-множественное тождество и запиывается через знак равенства.
Простейшие примеры тождеств
A ∪ B = B ∪ A; A ∩ B = B ∩ A; (A ∪ B) ∪ C = A ∪ (B ∪ C); (A ∩ B) ∩ C = A ∩ (B ∩ C).
Они очевидны из определения.
Вот менее очевидный пример тождества:
(A ∩ B) \ C = (A \ C) ∩ B.
Нарисуем левую и правую часть на картинке кругов Венна. Видим, что множество получается одно и то же в обоих случаях.
Почему рассуждение с картинкой корректно? Оно на самом деле скрывает под собой разбор возможных случаев. Каждый элемент может принадлежать или не принадлежать одному из трех множеств. Поэтому всего есть 8 вариантов, которые отмечены на рисунке. Для каждого варианта можно проверить, что элемент входит в множество, задавамое левой частью, тогда и только тогда, когда он входит в множество, задаваемое правой частью.
Аналогично можно доказывать и другие тождества. Например, тождества дистрибутивно- сти для объединения и пересечения
(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C);
(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C).
Ассоциативность симметрической разности
(A
B)
C = A
(B
C)
также можно увидеть на картинке.
2
Логические переменные, логические связки
Но при большом количестве переменных-множеств круги Венна становятся не слишком удоб- ными.
Заметим, что значение каждой формулы с множествами задается фактически таблицей, в которой для каждого набора вариантов вхождений элемента в множество указано, принадле- жит ли данный элемент множеству-результату.
Вхождения элементов принимают логические значения «истина» 1 и «ложь» 0. Таблица,
о которой шла речь, задает функцию из наборов логичеких значений в логические значения.
Такие функции называются булевыми (или логическими). Функции от логических аргумен- тов, отвечающие основным операциям, назовем логическими связками. Обычно используют- ся такие связки как отрицание конъюнкция (соответствует пересечению), дизъюнкция (со- ответствует объединению), сумма по модулю 2, она же XOR, она же «исключающее ИЛИ»
2

(соответствует симметрической разности), равносильность ≡ и импликация (или логическое следование) →. Вот таблицы для этих связок x
y x ∧ y x ∨ y x → y x ⊕ y
0 0
0 0
1 0
0 1
0 1
1 1
1 0
0 1
0 1
1 1
1 1
1 0
Есть еще связка, применяемая к одной переменной: отрицание ¬0 = 1, ¬1 = 0.
Теоретико-множественной операции разности A \ B не соответствует связка в стандартном наборе. задаваемую ею функцию можно выразить через имеющиеся связки. Это функция x ∧
¬y.
Получаем более упорядоченный способ доказательства теоретико-множественных формул:
составить соответствующие логические формулы Φ
1
и Φ
2
, после чего проверить, что Φ
1
и
Φ
2
задают одну и ту же логическую функцию. Разумеется, в общем случае мы ничего не выигрываем. Всё равно нужно разбирать таблицы истинности. Но в некоторых случаях так рассуждать проще.
Дело в том, что одни связки выражаются через другие, что облегчает доказательство ра- венства функций. Например,
x ⊕ y = x ∧ ¬y ∨ ¬x ∧ y.
(1)
Обратите внимание, что в правой части пропущены скобки. Восстанавливаются они, если ука- зать старшинство связок. Порядок убывания старшинства отрицание, конъюнкция, дизъюнк- ция, импликация, XOR.
В виде логических тождеств выражаются законы логики. Приведем два примера. Законы де Моргана
¬(x ∨ y) = ¬x ∧ ¬y;
¬(x ∧ y) = ¬x ∨ ¬y определяют как брать отрицание от дизъюнкции или конъюнкции. Тождество x → y = ¬y → ¬x выражает принцип контрапозиции (теорема равносильна обратной к противоположной). Этот принцип часто используется в математических доказательстввах: вместо доказательства утвер- ждения «если А, то Б» зачастую удобнее изменить посылку и доказывать равносильное утвер- ждение «если не Б, то не А».
Приведем пример использования логических формул при доказательстве теоретико-мно- жественных тождеств. Докажем, что
(A
1
∩ A
2
∩ A
3
∩ · · · ∩ A
n
) \ (B
1
∪ B
2
∪ · · · ∪ B
n
) = (A
1
\ B
1
) ∩ (A
2
\ B
2
) ∩ · · · ∩ (A
n
\ B
n
).
(2)
Запишем логическую формулу для левой части
(a
1
∧ a
2
∧ · · · ∧ a n
) ∧ ¬(b
1
∨ b
2
∨ · · · ∨ b n
).
Применяя закон де Моргана, получим a
1
∧ a
2
∧ · · · ∧ a n
∧ ¬b
1
∧ ¬b
2
∧ · · · ∧ ¬b n
Конъюнкция коммутативна, поэтому та же самая функция предствляется формулой
(a
1
∧ ¬b
1
) ∧ (a
2
¬b
2
) ∧ · · · ∧ (a n
∧ ¬b n
).
Но это и есть логическая формула, отвечающая правой части (2).
3

3
Полнота систем связок
Система связок называется полной, если формулами, использующими эти связки, можно вы- разить любую булеву функцию. Введенных связок уже достаточно для полноты. Более того,
справедлива следующая теорема.
Теорема 1. Система {¬, ∧} полна.
Прежде доказательства теоремы сделаем такое наблюдение. Если выразить какую-то связ- ку через заданную систему связок, то для доказательства полноты достаточно искать форму- лы, включающие эту дополнительную связку. Действительно, дополнительную связку всегда можно исключить, подставляя ее выражение через исходную систему связок (размер формулы при этом может сильно увеличиться).
3.1
Первое доказательство полноты
С помощью де Моргана дизъюнкция выражается через конъюнкцию и отрицание (и наоборот):
x ∨ y = ¬(¬x ∧ ¬y);
x ∧ y = ¬(¬x ∨ ¬y)
(мы также использовали очевидное тождество ¬¬x = x).
Поэтому достаточно доказать полноту системы связок {¬, ∧, ∨}.
Для начала выразим функцию f
α
, которая принимает значение 1 только на одном наборе значений переменных α
1
, α
2
, . . . , α
n
. Эта функция выражается как конъюнкция литералов
(литерал — переменная или ее отрицание). Если α
i
= 1, то включаем в конъюнкцию перемен- ную x i
. Если α
i
= 0, то включаем в конъюнкцию отрицание переменной ¬x i
Конъюнкция принимает значение 1 лишь тогда, когда все ее аргументы принимают значе- ние 1. Поэтому лишь для набора (α
1
, . . . , α
n
) эта конъюнкция принимает значение 1.
Чтобы выразить произвольную функцию f , возьмем дизъюнкцию f
α
по всем таким α,
что f (α) = 1. Такая дизъюнкция равна 1 в любой точке α. Если же f (β) = 0, то все члены дизъюнкции обращаются в 0 и вся дизъюнкция обращается в 0. Получили искомое выражение.
Формула, которую мы получили, имеет специальный вид. Он называется дизъюнктивная нормальная форма (ДНФ). По определению, это дизъюнкция конъюнкций литералов. Приме- ром ДНФ является дизъюнкция переменных x
1
∨ x
2
∨ · · · ∨ x n
. Заметим, что если мы будем для такой функции выписывать ДНФ тем способом, который изложен в доказательстве, по- лучится куда более длинная ДНФ (в ней будет 2
n
− 1 конъюнктов). ДНФ, которые возникли в доказательстве, называют (из уважения к их длине) совершенными. Задача нахождения самой короткой ДНФ, предсатвляющей данную функцию, в общем случае очень трудна.
3.2
Второе доказательство
Мы уже выразили ⊕ через конъюнкцию, дизъюнкцию и отрицание, см. (1). Значит, доста- точно выразить любую функцию через {∧, ⊕, ¬}. Более того, нам потребуется разве что одно отрицание.
Будем строить выражение функции в системе {∧, ⊕, 1} (разрешаем использовать констан- ту 1). Для этих связок выполняются обычные свойства арифметических операций (они реали- зуются как умножение и сложение чисел с точностью до четности). Поэтому любую формулу с этими связками возможно преобразовать в тождественно равную ей формулу в виде многочле- на (сумма произведений). Такие многочлены называются многочлена Жегалкина. У свободный член у этих многочленов равен 0 или 1.
Докажем полноту {∧, ⊕, 1} индукцией по числу переменных. База индукции — 0 перемен- ных. Константа 1 уже есть, осталось выразить константу 0: 0 = 1 ⊕ 1.
Пусть утверждение о полноте доказано для всех булевых функций от n переменных. Дока- жем его для булевых функций от n + 1 переменной. По функции f (x
0
, x
1
, . . . , x n
) определим две функции от n переменных:
f
0
(x
1
, . . . , x n
) = f (0, x
1
, . . . , x n
);
f
1
(x
1
, . . . , x n
) = f (1, x
1
, . . . , x n
).
4

По предположению индукции они выражаются в системе {∧, ⊕, 1}. Тогда равенство f (x
0
, x
1
, . . . , x n
) = (1 ⊕ x
0
) ∧ f
0
(x
1
, . . . , x n
) ⊕ x
0
∧ f (1, x
1
, . . . , x n
)
выполняется для всех значений переменных (при x
0
= 0 обращается в 0 второе слагаемое, при x
0
= 1 — первое). Подставляя в правую часть формулы для f
0
и f
1
, получаем представление для f .
Чтбы доказать полноту системы {∧, ⊕, ¬}, осталось избавиться от 1. Это просто: 1⊕x = ¬x.
3.3
О полноте теоретико-множественных операций
Можно ли выразить любую функцию связками, отвечающими теоретико-множественным опе- рациям? Ответ: нет. Причина очень проста. Эти связки, как говорят, сохраняют 0, т.е. задают булевые функции, которые на наборе из одних 0 принимают значение 0. Но тогда и любая формула из таких связок будет сохранять 0 (подставляем только 0 всюду).
Значит, отрицание выразить через такие фуннкции не удастся. И это вполне понятно: «от- рицание» множества A невозможно определить корректно. В него должны входить все эле- менты, которые не принадлежат A. То есть, в отрицание множества {1} обязаны входить и все равнобедренные треугольники, и функция sin x. Это вполне бессмысленно. (Замечание: ча- сто используемая операция дополнения к множеству всегда применяется в тех случаях, когда множество является подмножеством некоторого большого фиксированного множества (универ- сума), скажем, множества натуральных чисел. В этом случае дополнение есть просто разность универсума и нашего множества.
Однако любую функцию, которая сохраняет 0, выразить через теоретико-множественные связки, возможно. Проверить это легко, используя представления функций в виде ДНФ. Если функция сохраняет 0, ее ДНФ должна в каждом конъюнкте содержать хотя бы одну перемен- ную. Но такой дизъюнкт выражается через теоретико-множественную разность:
x
1
∧ x
2
∧ · · · ∧ x k
∧ ¬y
1
∧ · · · ∧ ¬y n
= (x
1
∧ x
2
∧ · · · ∧ x k
) \ (y
1
∨ y
2
∨ · · · ∨ y n
).
3.4
Формула включений - исключений
Теперь вернемся к переслительной комбианторике. Наша цель — обобщить формулу суммы. В
теоретико-множественных обозначениях эта формула утверждает
|A ∪ B| = |A| + |B|,
если A ∩ B = ∅.
Если пересечение множеств непусто (варианты не взаимно исключающие), формула суммы неверна.
Определим, насколько ошибается формула суммы. Посмотрев на круги Венная, видим, что элементы пересечения посчитаны дважды (один раз как элементы A, другой — как элемен- ты B). То есть ошибка в точности равна |A ∩ B| и правильная формула имеет вид
|A ∪ B| = |A| + |B| − |A ∩ B|.
Посмотрим, что будет в случае трех множеств. Элементы, которые входят в два множества,
посчитаны дважды, а элементы, входящие во все множества, посчитаны трижды. Правильная формула будет иметь вид
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ B| − |B ∩ C| + |A ∩ B ∩ C|.
Действительно, для каждой области диаграммы Венна посчитаем ее вклад в такую сумму и убедимся, что вклад всех областей, кроме внешней, равен 1.
Теперь уже можно предложить хороший вариант для общей формулы:
|A
1
∪ A
2
∪ · · · ∪ A
n
| =
i
|A
i
| −
i|A
i
∩ A
j
| + · · · =
∅=I⊂{1,2,...,n}
(−1)
|I|+1
i∈I
A
i
(3)
Это правильная формула.
5

3.5
Первое доказательство
Индукция по числу множеств. База индукции — одно множество, формула очевидна.
Индуктивный переход использует формулу для объединения двух множеств.с
|(A
1
∪ · · · ∪ A
n−1
) ∪ A
n
| = |A
1
∪ · · · ∪ A
n−1
| + |A
n
| − |(A
n
∩ A
1
) ∪ · · · ∪ (A
n
∪ |A
n−1
)|.
Для первого и третьего слагаемых по предположению индукции справедлива формула (3) для n − 1. Поэтому первое слагаемое дает вклад в (3) для n для всех множеств I, которые не содер- жат n. Второе отвечает множеству I = {n}. Последнее отвечает множествам I, содержащим n
(перемена знака связана с переменой мощности множества).
3.6
Второе доказательство
Формула (3) очень похожа на обычное алгебраическое тождество
1 − (1 − x
1
)(1 − x
2
) . . . (1 − x n
) = x
1
+ x
2
+ · · · + x n
− x
1
x
2
− · · · + x
1
x
2
x
3
+ . . .
(4)
И это неслучайно. Введем индикаторную (или характеристическую) функцию множества.
Для множества A по определению χ
A
(x) = 1, если x ∈ A, и χ
A
(x) = 0, если x /
∈ A.
Мощность множества легко выражается как сумма индиктора по всему универсуму (мы считаем, что все множества лежат в одном универсуме):
|A| =
u
χ
A
(u).
Теперь заметим, что индикаторная функция для дополнения множества (т.е. разности уни- версума и множества) равна 1 − χ
A
, для пересечения множеств это просто произведение ин- дикаторных функций этих множеств. А индикторная функция для объединения A = ∪
i
A
i выражается как
χ
A
= 1 − (1 − χ
A
1
)(1 − χ
A
2
) . . . (1 − χ
A
n
)
(5)
(используем закон де Моргана и выражаем дополнение к объединению как пересечение допол- нений). Теперь заменим правую часть (5) на правую часть (4), произведения индикаторных функций — на индикаторные функции пересечений и просуммируем по универсуму.
3.7
Формула для симметрической разности
В симметрическую разность A
1
A
2
· · ·
A
n входят те элементы, которые принадлежат нечетному числу множеств из семейства A
i
. Для мощности симметрической разности также есть формула через пересечения:
|A
1
A
2
· · ·
A
n
| =
i
|A
i
| − 2
i|A
i
∩ A
j
| + 4
i|A
i
∩ A
j
∩ A
k
| − . . .
(6)
Эту формулу также легко получить с помощью индикаторов. Пусть A = A
1
A
2
· · ·
A
n
Тогда

A
= 1 − (1 − 2χ
A
1
)(1 − 2χ
A
2
. . . (1 − 2χ
A
n
).
Действительно, 1 − 2χ
A
принимает значения ±1, причем −1 означает вхождение элемента в множество. Если элемент входит в четное число множеств, на таком элементе произведение будет равно +1 (вклад в правую часть равен 0), а если в нечетное — то −1 (вклад в правую часть равен 2). Теперь осталось раскрыть скобки и заменить произведения индикаторов на индикаторы пересечений.
6


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал