Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
/** (хи .,11гп)= & (а;®1 V • • ? V я«71)-
(°1 °эт)
**(°1....*п)“1
ГЛ. I. АЛГЕБРА ЛОГИКИ 29
Левая часть есть }(хи ..., я:„), а правая может быть преобразована далее:
& 1V - • • & («11V * ? •
(0-р...,0п} (°1>-*• >°л)
Ф(о1,...,ап)~ 1 ^...оТ1)=0
- 4 У*°л
(«1 Оп)
Таким образом, получаем разложение
...,Хп) = & (ж”1 V • * * V Я?1].
(°1*- 1°п)
/(о1,...,оп)= О
Это выражение носит пазвание совершенной конъюнктивной нормальной формы (совершенной к.н. ф.).
Пример 11. 1). Построить совершенную к. н. ф. ДЛЯ функции хл -*? х2.
Имеем
хх -*» х.2 ~ х\ V ^3 = ^1 V я2.
2) Построить совершенную к. н. ф. для функции ](хи Хл, я^з), заданной табл. 7.
Имеем
/ (#1, г2, я^з) = (ял V х2 V ягэ) (я:, V хъ V хя) X
Х(я, V я:2 V х&) (я: 1 V х2 V я:8).
Итак, в качестве средства для задания булевых функций наряду с таблицами можно использовать язык формул над множеством функций, состоящим из отрицания, конъюнкции и дизъюнкции. Поскольку табличный язык по громоздкости примерно эквивалентен языку совершенных д. и. ф. (совершенных к. н. ф), то можно утверждать, что язык формул, использующий отрицания, конъюнкции и дизъюнкции, не хуже языка таблиц. Можно показать, что на самом деле он существенно лучше табличного языка. Для пояснения рассмотрим функцию
/(#,, . .Хго) = я?! V.. .V я:20.
Данная формула в правой части насчитывает 39 символов (20 символов переменных и 19 символов V), таблица для 1{хи ..., х2о) содержит 2го, т. е. более миллиона строк.
ЗО Ч. І. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
§ 5. Полнота п замкнутость
Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции х, хл & х2 и х% V х2. В связи с этим возникает вопрос, в какой мере является случайным наличие таких систем элементарных функций? Сейчас мы не собираемся давать исчерпывающего ответа на поставленный вопрос, а лишь покажем, что такого рода свойством обладают и некоторые другие системы элементарных функций.
Определение. Система функций ІД, /2, .. ,, Д, ...} нз Р2 называется (функционально) полной, если любая булева функция может быть записана в виде формулы через функции этой системы.
Рассмотрим примеры полных систем.
1. Система Рг ~~ множество всех булевых функций — является полной системой.
2. Система $ = {.г, х! & х2, од V х2} представляет полную систему.
Ясно, что не каждая система является полной, па-пример, система $ — {0, 1) не полная. Следующая теорема позволяет сводить вопрос о полноте одних систем к вопросу о полноте других систем.
Теорема 5. Пусть даны две системы функций из Рг:
$=</„/„...>, (і)
С-=(Яі, ёг, (II)
относительно которых известно, что система I полна и каждая ее функция выражается в виде формулы через функции системы II. Тогда система II является полной.
Доказательство. Пусть к — произвольная функция из Р2- В силу полноты системы I можно выразить к формулой над ф, т. е.
к = С[Д, /2, ..., /*, ...]
(в скобках мы выписываем все функции системы хотя в формуле фактически встречается лишь конечное их число). По условию теоремы
/і = Сі[&и ІГг, * * •],
/а = С2Ы1, ?а, . - •],
ГЛ. 1. АЛГЕБРА ЛОГИКИ 31
Поэтому МЫ можем В формуле С[/1, /2, ...] исключить вхождения функций /і, /2} ..заменив их формулами над О*). Это можно записать так:
С[/ь /г, • • -1 = #2, . • ?], Сг[#о ^2, • •.], • • •]*
Последнее выражение определяет формулу над ?} со строением С'. Мы получаем
С\С^і, ?^2, ? • •], gг^ • • *1, . . “ С [^1} ?Д) • • -]і
или, окончательно,
Л = С'[?і, ?г, . . .],
т. е. мы выразили /г в виде формулы над О. Теорема доказана.
Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем.
3. Система $ = {’х, ад & ад} является полной. Для доказательства возьмем за систему I систему 2 (стр. 30), а за систему II — систему 3 и используем тождество
ад V х2 = ад & хг,
которое вытекает из свойств 4 элементарных функций.
4. Система $ = {а*, ад V ад} является полной.
Этот факт доказывается либо аналогично предыдущему, либо через принцип двойственности.
5. Система $ = {ад/ад} является полной.
Для доказательства за систему I возьмем систему 3, п за систему II — систему 5. Легко видеть, что
ад/ад ~хи (ад/ад)/(ад/ад) — ад/ад = ад &ад.
6. Система $ = {0, 1, адад, ад + ад) является полной.
*) Не всегда эти замены можно произвести все одновременно, так как при замене, .вообще говоря, могут возникнуть новые вхождения символов Д,/г, .,. Например, если
= X) & Х-2, ?\ ~ Х{ V х2, §2 = Х\ -р ДД, А =г= Х1 & (х% & Х3),
ТО
й == х1 & х2 — XI + ад + (лд V лд).
А х[ Л (ад & лд) = ЯГ] -р (ад & а"з) ~Ь (ад V (ад & ад) ) =
** Х1 + Х% + х9 + {х2 V хз) + (ЯД V (ЛД ф ЛД + (ад V лд))).
32
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Для доказательства опять за систему I возьмем систему 3, а за систему II — систему 6. Мы имеем
х± + 1 = Х\ъ
Х&г =Xi& Хг.
Так как формула, построенная из констант 0, 1 и функций xtx2 и х± + х2, после раскрытия скобок и несложных алгебраических преобразований переходит в полином по mod 2, то мы получаем следующую теорему, принадлежащую И. И. Жегалкину.
