1 Множества. Логика Буля - лекции

Это определение можно записать с помощью логических формул

так:

Из неѐ видно, что

Эквивалентность определяется теми элементами множеств A и B , которые для них являются общими. Элементы, не входящие ни в A , ни в B , также считаются эквивалентными:

Из условия дополнительности операций вытекают следующие соотношения:

15

ЛЕКЦИЯ 3. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ И ИХ СВОЙСТВА. МЕТОДЫ ДОКАЗАТЕЛЬСТВА В ЛОГИКЕ БУЛЯ

Элементарные булевы функции. Логическая переменная x , прини-

мающая одно из двух возможных значений 0 или 1, называется булевой.

Функция f (x1 , x2 , ..., xn ) n булевых переменных называется булевой. Еѐ об-

ластями определения и значений является множество {0, 1}.

Любую булеву функцию можно задать таблицей (истинности), в которой перечисляются все наборы возможных значений переменных, и для каждого такого набора указывается соответствующее значение функции.

Две булевы функции, принимающие одинаковые значения при одних и тех же наборах значений переменных, называются равными.

Набор значений переменных, на котором булева функция принимает значение 1, называется единичным.

Построим таблицу истинности булевой функции одной переменной

(табл. 1):

17

Табл. 2

Всего булевых функций двух переменных – шестнадцать, трѐх переменных – тридцать две и так далее. Понятно, что число булевых функций

n переменных равно 22n .

Как видно из таблицы 2, к функциям двух переменных относятся и

Коммутативность показывает, что порядок записи переменных в дизъюнкции, конъюнкции, может быть любым (аналог в алгебре чисел – сумма, произведение не зависит от порядка записи сомножителей, слагаемых). Коммутативными операциями также являются сумма по модулю два,

Ассоциативность показывает, что порядок выполнения конъюнкции и дизъюнкции может быть произвольным. Ассоциативной также является операция сумма по модулю два.

4. Дистрибутивность объединения относительно пересечения и наоборот:

Дистрибутивность определяет правила раскрытия скобок. В алгебре чисел умножение дистрибутивно относительно сложения. Сумма по модулю два дистрибутивна.

5. Поглощение пересечения, объединения:

Законы поглощения позволяют упрощать булевы функции. 6. Инволютивность (закон двойного дополнения):

A A .

Закон двойного отрицания:

x x .

19

Операции над булевыми функциями имеют следующий приоритет: наиболее сильная операция – отрицание, затем следует конъюнкция, потом

– дизъюнкция, затем – импликация, затем – эквивалентность. Порядок выполнения других операций указывают скобки. Для упрощения записи знак конъюнкции можно не записывать по аналогии со знаком умножения в алгебре чисел. Например, законы де Моргана записываются так: xy x y ,

x y x y .

Чтобы доказать законы 1–8 и другие теоретико-множественные равенства, можно:

–нарисовать диаграммы Эйлера–Венна левой и правой частей равенства и убедиться в том, что они совпадают;

–воспользоваться таблицей истинности;

–провести формальное рассуждение по следующей схеме.

Пусть требуется доказать теоретико-множественное равенство M N , где M и N – некоторые множества.

Первая часть доказательства состоит в том, чтобы показать, что если некоторый элемент принадлежит множеству M , то он также принадлежит множеству N . Этим будет доказана справедливость отношения M N .

Во второй части доказательства нужно показать, что если некоторый элемент принадлежит множеству N , то он также принадлежит множеству

9 Огастес де Морган (1806, Мадура, Индия — 1871, Лондон) – шотландский математик и логик; профессор математики университетского колледжа в Лондоне; первый президент Лондонского математического общества. Основные труды: по математической логике и теории рядов; к своим идеям в алгебре ло-

гики пришёл независимо от Дж. Буля; изложил элементы логики высказываний и логики классов,

дал первую развитую систему алгебры отношений; с его именем связаны известные теоретико-

множественные соотношения (законы де Моргана).

20

►Пример. Докажем справедливость тождества

(a b) (c d ) ((a b) (c d )) ((a b) | (c d ))

с помощью таблицы истинности.

Аналогично докажите коммутативность суммы по модулю два, стрелки Пирса, штриха Шеффера; ассоциативность суммы по модулю два.

Решение. Пусть

Таблица истинности (табл. 4) имеет вид:

21

Табл. 4

Наборы значений из нулей и единиц для левой части f L совпали с наборами правой части f R , значит, исходное тождество верное.

В правильности тождества можно убедиться с помощью диаграмм Эйлера-Венна.

На рис. 5, 6 изображены две операции – a b и c d , – из левой части данного тождества. В роли исходных областей выберем эллипсы, тогда диаграмма будет содержать 16 областей (если выбрать круги, то диаграмма будет содержать 14 областей и будет неполной).

22

Искомое выражение получается при объединении C1 и C2 :

произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению

окончательно получаем

A B A B .

Приходим к выводу, что A B A B .

Так как x x 0 , левая часть равенства равна нулю. Раскрывая скобки в правой части, также получаем нуль.

24