Заметим, что разделение конструкций на синтаксическую и семантическую части доста-точно естественно для дискретной математики. Примерно по такой же схеме (но заметно слож-нее) выглядит определение предикатов (здесь не рассматривается).
Далее будут рассматриваться формулы над множествами функций от одной и двух пере-менных, которые являются подмножествами одного множества так называемых элементарных функций B e = {0, 1, Ø, Ù, Ú, →, Å, , |, ↓} (см. раздел 1.1). Определение формул в этих бази-сах и сопоставляемых им функций является частным случаем рассмотренных выше общих конструкций.
Пример 3. Для определения функции, задаваемой (говорят также реализуемой) форму-лой, удобно использовать таблицу, строки которой соответствуют наборам значений перемен-ных, а в столбцах под знаком каждой операции стоят значения функции, реализуемой соответс-твующей подформулой. Для формулы Ф (x 1, x 2, x 3) = (x 1Ú x 2) → (x 3 (x 1 ↓ Ø x 2)) функция fФ опре-деляется в последнем столбце следующей таблицы 6:
Таблица 6. Построение таблицы истинности для функции fФ = (x 1Ú x 2) → (x 3 (x 1 ↓ Ø x 2))
x 1 | x 2 | x 3 | 1) x 1Ú x 2 | 2) Ø x 2 | 3) x 1↓2 | 4) x 3 3 | 5) 1→4 |
Заголовок x 1Ú x 2 столбца 1) и заголовок Ø x 2 столбца 2) понятны – в эти столбцы заносятся ре-зультаты указанных действий. Заголовок x 1↓2 столбца 3) означает стрелку Пирса, применённую к x 1 и функции, уже подсчитанной в столбце 2). Заголовок x 3 3 столбца 4) означает эквивалент-ность, применённую к x 3 и функции, уже подсчитанной в столбце 3). Заголовок 1→4 столбца 5) означает импликацию, посылка которой уже подсчитана в столбце 1), а заключение – в столбце 4). Таблицы, помогающие аналогичным образом вычислять булевы функции от двух-четырёх переменных по заданным формулам, называются таблицами истинности ■
Укажем на различие между таблицами 6 и 2. В таблице 2 в последнем столбце значения функции на всех наборах задавались, а понятие формулы не использовалось. В то же время в таблице 6 функция задаётся формулой, а заголовки столбцов подробно указывает на процесс вычисления булевой функции, реализуемой данной формулой.
2.1. Равносильность булевых формул. Булевы формулы Ф и Ψ называются равносиль-ными, если соответствующие им функции fФ и fΨ равны. Равносильность двух формул обозна-чается как Ф º Ψ. Равносильные формулы называют также тождественно равными, а выраже-ния вида Ф º Ψ – логическими тождествами. Вместо термина «равносильность» иногда ис-пользуется термин «эквивалентность».
Таким образом, равносильные формулы реализуют одну и ту же булеву функцию. Ниже при-водится ряд пар равносильных формул (тождеств), отражающих существенные свойства логичес-ких операций и важные соотношения между различными операциями. Они часто позволяют нахо-дить для булевых функций по реализующим их формулам более простые эквивалентные формулы. Большинство из приводимых тождеств имеют собственные имена. Часто их называют законами логики.
Пусть ○ – это одна из функций Ù, Ú, Å. Для этих трёх функций выполнены следующие две равносильности (законы ассоциативности и коммутативности).
1) Закон ассоциативность: (a ○ b 2) ○ c º a ○ (b 2 ○ c).
Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, одних операций дизъюнкции, одних операций сложения по моду-лю 2 не зависят от расстановки скобок. Поэтому вместо формул (a ○ x 2) ○ c и a ○ (b ○ c) мы бу-дем для упрощения писать выражение a ○ b ○ c, которое не является формулой непосредственно по определению, но может быть легко превращено в неё с помощью расстановки скобок.
2) Закон коммутативность: a ○ b º b ○ a
3) Законы дистрибутивные:
(a Ú b) Ù c º (a Ù c) Ú (b Ù c)
(a Ù b) Ú c º (a Ú c) Ù (b Ú c)
(a Å b) Ù c º (a Ù c) Å (b Ù c)
4) Закон двойного отрицания: Ø(Ø a) º a
5) 3аконы де Моргана (внесение отрицания внутрь скобок):
Ø (a Ú b) º Ø a Ù Ø b
Ø (a Ù b) º Ø a Ú Ø b
6) Законы упрощения:
законы идемпотентности a º a, a Ú a º a
закон противоречия a ÙØ a º 0; закон исключенного третьего a ÚØ a º 1
законы 0 и 1 a Ù0 º 0, a Ú 0 º a, a Ù1 º a, 1 º 1
7) Правила поглощения: a Ú ab º a; a (a Ú b) º a
8) Правило склеивания: a b Ú a (Ø b) º a
9) Правило вычёркивания: a b Ú Ø a º b Ú Ø a
Далее будем часто писать ab вместо a Ù b. Эта «вольность записи» общепринята, так как она приводит к заметному сокращению формул, а «оправдывается» тем, что результаты опера-ции конъюнкции 0Ù0 = 0Ù1 = 1Ù0 = 0, 1Ù1 = 1 полностью совпадает с таблицей умножения чисел 0 и 1. При отсутствии скобок знак отрицания, стоящий перед переменной, имеет самый высокий приоритет, т.е. операция отрицания выполняется прежде всего. Следующий приоритет имеет логическое умножение. Остальные операции выполняются в порядке, указанном скобка-ми.
Обратим также внимание на следующее. Все приведённые законы и правила – это не зако-ны природы. Они доказываются (точнее, проверяются) подстановкой в левую и правую части логических тождеств всех наборов значений переменных (при n = 2 – четырёх наборов, при n = 3 – восьми).
Пример 4. Проверим справедливость 2-го закона дистрибутивности
(a Ù b) Ú c º (a 1 Ú c) Ù (b Ú c)
Для левой и правой частей проверяемого тождества получаем две таблицы истинности (см. для сравнения таблицу 5):
Таблица 7а. Левая часть тождества
| Таблица 7б. Правая часть тождества
|
Поскольку правые столбцы полностью совпадают, то функция, реализуемая формулой из левой части, совпадает с функцией, реализуемой формулой из правой части. Это и означает справед-ливость 2-го закона дистрибутивности
Если в этом законе удалить знак конъюнкции (см. выше) и заменить дизъюнкцию на сло-жение, то данное тождество примет вид ab + c º (a + c)(b + c), что, разумеется, для чисел с опе-рациями умножения и сложения неверно. Заметим, что при такой же замене в 1-ом законе дистрибутивности получаем закон, очевидно выполняющийся для чисел (и даже матриц): (a + b) c º ac + bc, что ещё раз говорит об аккуратности при использовании аналогий между буле-выми и числовыми формулами ■
Многие из приведённых тождеств (2) – (7) и 1) – 9) можно не проверять, а выводить из других тождеств. Но на этом мы останавливаться не будем, стремясь к максимально возможной стандартизации рассуждений (для чего на самом деле и разрабатывалась булева алгебра ещё в 19-ом веке). Заметим, что все тождества остаются в силе, если вместо переменных a, b, c под-ставлять произвольные формулы в любом базисе.
Из определения равносильности формул непосредственно следует так называемый прин-цип замены равносильных подформул: пусть формула α является подформулой формулы Ф, формула α' равносильна α и формула Ф' получена из Ф посредством замены некоторого вхож-дения α на α'. Тогда Ф' равносильна Ф, т.е. Ф ' º Ф.
Применяя этот принцип и используя основные тождества, можно находить для заданной формулы другие равносильные ей формулы.
Пример 5. Упрощение формулы. Имеет место цепочка тождеств, устанавливающая рав-носильность всех входящих в неё формул:
((x 1→ x 2) x 1ÚØ x 1 x 2)(x 1ÚØ x 2) º ((Ø x 1Ú x 2) x 1ÚØ x 1 x 2)(x 1ÚØ x 2) º (Ø x 1 x 1Ú x 1 x 2ÚØ x 1 x 2)(x 1ÚØ x 2) º
(x 1 x 2ÚØ x 1 x 2)(x 1ÚØ x 2) º x 2(x 1ÚØ x 2) º x 1 x 2.
Дадим пояснения. В исходной формуле заменяем подформулу x 1→ x 2 на равносильную в силу формулы (2) подформулу Ø x 1Ú x 2. Получаем формулу, стоящую справа от 1-го знака º. Да-лее, заменяя в ней по 1-му закону дистрибутивности 3) формулу (Ø x 1Ú x 2) x 1 на Ø x 1 x 1Ú x 1 x 2, полу-чаем формулу, стоящую справа от 2-го знака º. Далее, используя в формуле Ø x 1 x 1 закон проти-воречия, получаем Ø x 1 x 1 º 0, откуда в силу закона нуля x Ú 0 º x выводим, что Ø x 1 x 1Ú x 1 x 2ÚØ x 1 x 2 º x 1 x 2ÚØ x 1 x 2, и получаем формулу справа от 3-го знака º. Далее, по правилу склеивания, заме-няем подформулу x 1 x 2ÚØ x 1 x 2 на x 2 и приходим к формуле справа от 4-го знака º. Пользуясь ещё раз дистрибутивностью и законом противоречия, заменяем x 2(x 1ÚØ x 2) на окончательную прос-тую формулу x 1 x 2, равносильную исходной формуле ((x 1→ x 2) x 1ÚØ x 1 x 2)(x 1ÚØ x 2) ■
Как уже говорилось, закон ассоциативности позволяет рассматривать многоместную конъюнкцию и многоместную дизъюнкцию в качестве формул. В случае n = 1 обе формулы означают х 1. Пустая конъюнкция (при п = 0) полагается равной 1, пустая дизъюн-кция – равной 0.
Законы де Моргана 5) могут быть обобщены для произвольного неотрицательного n:
Ø() º (8а)
Ø() º (8б)
При п > 2 в этом можно убедиться, представив многоместную функцию расстановкой скобок с помощью двуместных. При п = 3, например, цепочка преобразований для (8б) имеет вид:
Ø(x 1 Ù x 2 Ù x 3) = Ø((x 1 Ù x 2) Ù x 3) = Ø(x 1 Ù x 2) Ú Ø x 3) = (Ø x 1 Ú Ø x 2) Ú Ø x 3 = Ø x 1 Ú Ø x 2 Ú Ø x 3.
В случае п = 0 и п = 1 соотношения (8) выполняются очевидным образом.
Соотношения (8) допускают дальнейшее обобщение. Пусть функция f реализуется некото-рой формулой в базисе B = {0, 1, Ø, Ù, Ú}. Тогда формула, реализующая её отрицание Ø f,может быть получена по следующему алгоритму.
Алгоритм отрицания в базисе {0, 1, Ø, Ù, Ú}.
1. Все конъюнкции (значки Ù) должны быть заменены на дизъюнкции (значки Ú) и наоборот, все дизъюнкции должны быть заменены на конъюнкции.
2. Переменные xi должны быть заменены на их отрицания Ø xi.
3. Константы 0 и 1 должны быть заменены противоположными константами 1 и 0 ■
Обоснованием алгоритма являются законы де Моргана. Приведём пример, иллюстрирую-щий работу алгоритма отрицания.
Пример 6. Пусть функция f задается формулой (x 1Ù x 2)Ú(Ø x 1ÙØ x 2) º x 1 x 2 (см. тождество (5)). При отрицании левой части предполагаемого тождества получаем
Ø((x 1Ù x 2)Ú(Ø x 1ÙØ x 2)) º Ø(x 1Ú x 2)ÙØ (Ø x 1ÙØ x 2) º (Ø x 1ÙØ x 2) Ù (Ø(Ø x 1)ÚØ(Ø x 2)) º (Ø x 1Ù Ø x 2)Ù(x 1Ú
x 2) º (Ø x 1Ù x 1ÚØ x 2Ù x 1ÚØ x 1Ù x 2ÚØ x 2Ù x 2 º Ø x 2Ù x 1ÚØ x 1Ù x 2 º Ø x 1Ù x 2 Ú x 1ÙØ x 2 º x 1 Å x 2. (9)
1-ое тождество следует из 2-го закон де Моргана. 2-ое тождество получено применением законов де Моргана к обоим слагаемым дизъюнкции. 3-ье тождество получено применением закона двойного отрицания к выражениям Ø(Ø x 1) и Ø(Ø x 2). Далее последовательно использова-на дистрибутивность для 4-го тождества, закон исключённого третьего для 5-го тождества (два члена из четырёх пропадают), коммутативность в 6-ом тождестве и тождество (3) в последнем, 7-ом тождестве. Преобразования заканчиваются формулой x 1 Å x 2. Таблица 5 подтверждает, что функции x 1 x 2 и x 1 Å x 2 (т.е. эквивалентность и сложение по модулю 2) действительно являются отрицаниями друг друга, поскольку на любом наборе, где одна из них равна 1, другая равна 0, и наоборот ■
2.2. СДНФ и СКНФ. Всякая булева функция от n переменных, по определению, задаётся своими значениями на 2 n наборах нулей и единиц. Однако уже при сравнительно небольших значениях n задание функции таблицей громоздко и неудобно. Поэтому желательно иметь не-который регулярный способ представления булевых функций при помощи формул, которые (в отличие от таблиц) могут быть преобразованы, упрощены и т.д. В настоящем разделе даются наиболее известные представления булевых формул в виде совершенной дизъюнктивной нор-мальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).
Пусть σ {0, 1}. Положим
xσ = . (10)
Сформулируем несколько почти очевидных утверждений, необходимых для определения СДНФ и СКНФ.
Утверждение 1. xσ = 1 тогда и только тогда, когда x = ■
Утверждение 2. Конъюнкция … равна 1 на единственном наборе значений пе-ременных x 1, …, xk: x 1 = σ 1, …, xk = σ k ■
Следующее утверждение позволяет выразить функцию f (x 1, …, xn) через функции от мéньшего числа аргументов.
Утверждение 3. Всякая логическая функция f (x 1, …, xn) при любом k = 1, 2, …, n представляется в виде
f (x 1, …, xk, xk +1, …, xn) = f (σ 1, …, σk, xk +1, …, xn), (11)
где дизъюнкция берётся по всем 2 k наборам σ 1, …, σk значений 0 и 1.
Доказательство следует из того, что для любого набора α 1, …, αn левая и правая части (11) совпадают ■
Представление (11) произвольной булевой функции называется разложением по перемен-ным x 1, …, xk. Его частный случай при k = 1 имеет вид
f (x 1, x 2, …, xn) = x 1 f (1, x 2, …, xn) Ú Ø x 1 f (0, x 2, …, xn) (12)
и носит название формулы разложения по одной переменной. Разумеется, вместо x 1 можно взять любую другую переменную.
Воспользовавшись утверждением 3 при k = n, получаем представление
f (x 1, …, xn) = f (σ 1, …, σn). (13)
При этом в правую часть (13) входят только те «слагаемые», на которых значения f (σ 1, …, σn) равны 1. Опуская значения f (σ 1, …, σn), поскольку логическое умножение» на 1 можно не пи-сать, получаем из (13) равенство
f (x 1, …, xn) = , (14)
где дизъюнкция берётся по всем наборам σ 1, …, σn, на которых функция f (σ 1, …, σn) = 1.
Представление (8) и называется совершенной дизъюнктивной нормальной формой (сок-ращённо СДНФ) булевой функции f от n переменных. С учетом соглашения о том, что пустая дизъюнкция равна 0, оно распространяется на функцию f (x 1, …, xn), тождественно равную 0.
СДНФ обладает следующими свойствами.
1. Она является дизъюнкцией некоторых конъюнкций К 1 Ú К 2 Ú … Ú Кs.
2. Каждая из конъюнкций Кi имеет вид , где n – число переменных функции.
3. Все конъюнкции К 1, К 2, …, Кs различны.
Утверждение 4а. Представление булевой функции, обладающее свойствами 1 – 3, единст-венно с точностью до перестановки конъюнкций ■
Введём в рассмотрение также важное для дальнейшего понятие дизъюнктивной нор-мальной формы (ДНФ). От СДНФ ДНФ отличается только одним: входящие в неё конъюнк-ции не обязаны включать все переменные. Например, формула xy Ú y Ø z является ДНФ, но не яв-ляется СДНФ. Однако СДНФ является частным случаем ДНФ.
Всякая функция f (x 1, …, xn) 1 может быть выражена также в виде конъюнкции некото-рых дизъюнкций …Ú . Чтобы получить это представление, выпишем СДНФ функ-ции Ø f (x 1, …, xn) 0:
Ø f (x 1, …, xn) = . (15)
Воспользовавшись алгоритмом отрицания из раздела 2.1 и тем, что Ø(Ø f) = f), из (9) получаем
f (x 1, …, xn) = (16)
(условие суммирования Ø f (x 1, …, xn) = 1 заменено на эквивалентное условие f (x 1, …, xn) = 0).
Представление (16) носит название совершенной конъюнктивной нормальной формы (сокращённо СКНФ). С учетом соглашения о том, что пустая конъюнкция равна 1, оно распрос-траняется на функцию f (x 1, …, xn), тождественно равную 1.
СКНФ обладает следующими свойствами.
1. Она является конъюнкцией некоторых дизъюнкций D 1 Ù D 2 Ù … Ù Dt.
2. Каждая из дизъюнкций Di имеет вид , где n – число переменных функ-ции.
3. Все дизъюнкции D 1, D 2, …, Ds различны.
Утверждение 4б. Представление булевой функции, обладающее свойствами 1 – 3, единст-венно с точностью до перестановки дизъюнкций ■
Это утверждение может быть доказана непосредственно либо на основе утверждения для СДНФ, применённой к функции Ø f.
Понятие КНФ определяется аналогично понятию ДНФ.