ФОРМУЛЫ. СУПЕРПОЗИЦИЯ. ОСНОВНЫЕ ТАВТОЛОГИИ

аранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики.

Лекция. 20. Формулы. Суперпозиция. Основные тавтологии

Лекция 20. ФОРМУЛЫ. СУПЕРПОЗИЦИЯ. ОСНОВНЫЕ ТАВТОЛОГИИ

План лекции:

  1. Формулы. Реализация функций формулами.
  2. Понятие суперпозиции.

2. Способы задания булевых функций.

  1. Эквивалентность формул. Основные тавтологии алгебры логики.

  1. Формулы. Реализация функций формулами

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

Пусть – некоторое подмножество функций из .

а) Базис индукции. Каждая функция называется формулой над .

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

Пример 1. Пусть – множество элементарных функций. Следующие выражения являются формулами над :

  1. ;
  2. ;
  3. .

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

Пусть – произвольная формула над , тогда формулы, которые использовались для ее построения, будем называть подформулами формулы .

Пусть является формулой над множеством . Возьмем множество функций .

Рассмотрим формулу , которая получается из путем подстановки . Говорят, что формулы и имеют одно и то же строение.

Пример 2. Следующие формулы и имеют одинаковое строение:

  1. , ;
  2. , .

Строение формулы обозначается через и формула однозначно определяется строением и упорядоченной совокупностью . Поэтому можно писать

.

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

а) Базис индукции. Если , где , то формуле сопоставим функцию .

б) Индуктивный переход. Пусть , где является либо формулой над , либо символом переменной . Сопоставим формуле функцию .

Если функция соответствует формуле , то говорят также, что формула реализует функцию .

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

Функция зависит существенным образом от аргумента , если существуют такие значения переменных , что

.

В этом случае называется существенной переменной . В противном случае – несущественной или фиктивной.

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

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

  1. Понятие суперпозиции

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

Операция суперпозиции включает две простые операции.

  1. Операция подстановки переменных. Пусть

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

.

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

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

Пример 3. Пусть имеется элемент, работа которого описывается некоторой булевой функцией (рис. 1,а). Результаты применения операции приведены на рис. 1,б (изменение обозначения входов) и рис. 1,в (подача одного и того же сигнала на несколько входов).

а) б) в)

Рис. 1. Иллюстрация применения операции

Пример 4. Выразим операцию отрицания через штрих Шеффера:

;; .

Пример 5. Пусть работа двух элементов описывается функциями и . Соединим элементы, как показано на рис. 2.

Рис. 2. Иллюстрация применения операции

Тогда функция на выходе схемы получается в результате подстановки функции на место третьего аргумента функции :

.

Пример 6. Рассмотрим систему функций , где

, , .

Представим в виде суперпозиции этих функций сумму по модулю 2:

, или .

Для стрелки Пирса по аналогии можно записать:

, или .

  1. Эквивалентность формул. Основные тавтологии алгебры логики

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

Определение. Формулы и называются эквивалентными, если соответствующие им функции и равны, т. е. . Запись означает, что формулы и эквивалентны.

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

  1. (коммутативность дизъюнкции).
  2. (ассоциативность дизъюнкции).
  3. (коммутативность конъюнкции).
  4. (ассоциативность конъюнкции).
  5. (правило повторения для дизъюнкции).
  6. (правило повторения для конъюнкции).

(операции с 0 и 1 для дизъюнкции и конъюнкции).

  1. (закон двойного отрицания).

(правила инверсии).

  1. (дистрибутивность конъюнкции).
  2. (дистрибутивность дизъюнкции).

(законы де Моргана).

18. .

19. .

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

С целью упрощения записи формул принимают следующие соглашения.

  1. Приоритет логических связок. Пусть – множество логических связок:

.

а) считают, что связка сильнее любой двухместной связки из ;

б) связка считается сильнее, чем любая из оставшихся связок.

2. Обозначим через любую из связок , . В силу закона ассоциативности можно вместо формул , использовать выражение , которое не является формулой, но может быть превращено в нее путем расстановки скобок.

3. Внешние скобки у формул опускаются. Опускаются также скобки у выражения, над которым стоит знак отрицания.

Эти соглашения позволяют, например, формулу записать в виде .

Рассмотрим некоторые следствия из тождеств 1 – 19.

Тождества 2 и 3 позволяют рассматривать логические суммы и произведения с любым числом слагаемых и результат не зависит от расстановки скобок. Поэтому далее будем использовать следующие обозначения:

, .

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

  1. Если в логическом произведении один из сомножителей равен 0, то и произведение равно 0.
  2. Если в логическом произведении, содержащем не менее двух сомножителей, имеется сомножитель, равный 1, то этот сомножитель можно зачеркнуть.
  3. Если в логической сумме, содержащей не менее двух слагаемых, имеется слагаемое, равное 0, то это слагаемое можно зачеркнуть.
  4. Если в логической сумме одно из слагаемых равно 1, то сумма равна 1.

Пример 7. Правило поглощения:

.

ФОРМУЛЫ. СУПЕРПОЗИЦИЯ. ОСНОВНЫЕ ТАВТОЛОГИИ