Материал: 5540

Заметим: функции пронумерованы так, что номер функции, записанный в двоичной системе счисления, даёт последовательность значений соответствующей функции. Например, двоичная запись числа 13 имеет вид: 1101. Соответствующая функция f13(a, b) принимает следующие значения: f13(0, 0) = 1, f13(0, 1) = 1, f13(1, 0) = 0, f13(1, 1) = 1.

2.2 Формы представления булевых функций

Любую булеву функцию у = f(a, b) можно представить как некоторую комбинацию областей:

С0 a b, C1 a b, C2 a b, C3 a b.

Тогда, в зависимости от значения функции и заданных Сi, которые в этом случае будем называть конституентами, получим шестнадцать логических операций в виде:

y a b f (0, 0) a b f (1, 0) a b f (0, 1) a b f (1, 1) ,

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

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

совершенной дизъюнктивной нормальной формой (СДНФ).

В логике Буля действует принцип двойственности, который гласит: при одновременной замене символов  и 1 0, все логические равенства остаются в силе. Поэтому нашу СДНФ можно представить несколько иначе:

y a b f (1, 1) a b f (0, 1) a b f (1, 0)a b f (0, 0) .

Эта форма представления называется совершенной конъюнктивной нормальной формой (СКНФ).

В таблице 2.10 приведён полный список элементарных логических функций от двух аргументов в двух совершенных формах – СДНФ и СКНФ.

36

Таблица 2.10 – Элементарные логические функции

Совершенные формы представлений позволяют выразить аналитической формулой любую функцию, если известна её таблица истинности.

Пример 2.2. Представить в явном виде функцию, зависящую от трёх элементов, заданную таблицей истинности (таблица 2.11).

Таблица 2.11 – Таблица истинности

37

Решение. Выписывая соответствующие конъюнкты против единичных значений у, мы получаем СДНФ. Если же выпишем дизъюнкты против нулевых значений у, то в результате получим СКНФ.

В логике Буля действует закон склеивания:

(a b) (a b) a, (a b) (a b) a.

Применение этих законов позволяет найти более компактные аналитические выражения для заданной функции у, т.е. минимальную дизъюнктивную нормальную форму уМДНФ и минимальную конъюнктивную нормальную форму уМКНФ. Приведём соответствующие формы представления функции у, заданной таблицей 2.11:

набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.

Обращаем внимание на то, что одну и ту же конституенту (импликанту) можно склеивать с другими конституентами (импликантами) многократно, так как в логике Буля действует закон идемпотентности: a a a a a a ..., a a a a a a ..., поэтому любую конституенту можно размножать.

2.3Методы доказательств в логике Буля

Вкачестве основных законов логики Буля чаще других называют:

38

Не все восемь законов независимы друг от друга. Так, например, закон идемпотентности можно получить из закона поглощения с использованием закона дистрибутивности:

a a (a b) (a a) (a b) (a (a b)) (a (a b)) a a.

Закон поглощения может быть выведен из закона нуля и единицы: a (a b) (a 1) (a b) a (1 b) a 1 a.

При доказательствах логических выражений мы всегда должны иметь в виду принцип двойственности.

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

Влогике широко используются два подхода – аксиоматический и конструктивный. При аксиоматическом доказательстве используется жёсткая система аксиом, состоящая, например, из четырёх только что названных. Все остальные тождества нужно представлять через эти законы. При конструктивном же доказательстве мы должны воспользоваться системой конструктов, примерами которых являются диаграммы Эйлера – Вена и таблицы истинности.

Для доказательства тождества а 0 0 приверженец аксиоматического подхода приведёт примерно такую цепочку преобразований:

а 0 а (а а) (а а) а ((а а) 0) а ((а а) (а а)) а (а (а а)) а (а 1) а а а 0.

И сделает он это только ради того, чтобы формально привязаться к провозглашённой ранее системе аксиом. В то же время для конструктивиста исходное тождество не требует никаких доказательств.

39

Картина выглядит противоположным образом в отношении, например, закона дистрибутивности. Аксиоматик в данном случае не предпринимает никаких действий, а сторонник конструктивного подхода обязан продемонстрировать эквивалентность правой и левой части тождества:

а (b c) (a b) (a c).

Проведём доказательство с помощью диаграмм Эйлера – Вена (рисунок 2.8). С этой целью построим две диаграммы, которые отвечают двум операциям левой части и три диаграммы, отвечающие трём операциям правой части тождества:

Рисунок 2.8 – Диаграммы Эйлера – Вена

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

В правильности тождества можно убедиться и с помощью таблицы истинности.

Для доказательства построим таблицу 2.12. Она показывает, что наборы значений из нулей и единиц для левой части (fL) совпали с наборами правой части (fR), значит исходное тождество верно.

Таблица 2.12 – Проверка на правильность исходного тождества

40