Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
*„), Щ]и ../Д.
Каждой формуле 5t(a;lt ..., хп) сопоставляется функция /(#!, ..., я„) из Ph, при этом говорят также, что формула §t реализует функцию /. Аналогичный смысл здесь имеют суперпозиция функций из 45 и операция суперпозиции. Далее вводится понятие эквивалентности формул §1 и S3: St — S3, если соответствующие им функции /$ И /д равны.
Опираясь на понятие эквивалентности, можно описать основные свойства элементарных функций. Укажем некоторые из них. Пусть (ж, ° х2) обозначает любую из функций тт(ж,, хг), ^.^(mod A), max(.Tj, я2), х% + ?+ хг (mod к).
1. Функция обладает свойством ассоциатив-
2. Функция {xi ° xz) обладает свойством коммута-
Далее мы иногда будем обозначать функции min (sj, хг) и шах (.г,, х2) соответственно через и Vi2),
Б силу свойства ассоциативности и соглашения о том, что операция & выполняется раньше операции V (см. замечания 1—3 § 3 гл. 1), можно употреблять для записи формул выражения, получающиеся из формул путем опускания некоторых скобок.
Укажем еще несколько групп тождеств (правил), относящихся уже к системе элементарных функций
3. Правила спуска символа 1 «вглубь» формулы:
5. Правило исключения «чистых» вхождений пере-* менпой:
пости:
( (х± ° Хг) о Х3) = (#! в (Х2 сгз)).
тивности:
(^1 ° лгг) = (д:г ° х
{О, 1, ..к — 1, /с {х), . . /*_t (я),
тт(ж1( х2), max(a*i, хг)).
7и (4 {??)) я=
при о = 0Л
О при 0<с < к — 1, 7, (я) при о = к — 1;
г = 1 ? h {х) V 2 ? lz {х) V... V {к - 1) /*_д (х).
ГЛ. 2. Л-ЗЯЛЧНАЯ ЛОГИКА 47
6. Правило введения переменной:
Х1 = XI (/0 (^з) V . . . V /а-1(х2))-
7. Правила упрощений:
1а(х) ПрИ Т =
(я) {%) = | ff0
при т Ф с;
от = min (о, т); о V т = тах (о, т);
(к — \)х — х\ 0 ? х — 0;
(к — 1) V х — к — 1; 0 V х = х.
Опираясь па некоторый запас тождеств (например, тождества 1—7) для системы элементарных функций
(0, 1, ..к — 1, /0 (я), . •/д-i [х),
min(;rlt х2), max(xi, х2)},
можно при помощи эквивалентных преобразований получить новые тождества.
Рассмотрение свойств элементарных функций показывает, что не для всех обобщений булевых функций сохраняются соответствующие свойства. Поясним это на примерах.
Пример 1.
1) ~ (~я) = х, но х Ф х (при fc>3) .
2) ~min(;rlt х2) = max(~?lt ~ х2), но
min(a:i, хг)?* тах(<ж1т х2).
В заключение приведем тождество, представляющее аналог совершенной д. н. ф. и играющее важную роль в последующем изложении:
/ (#ii * * *i хп) = V ^oi(^i)&* ? • & 1апЫ & / fait * 1 *i®n)-
Доказывается оно прямой проверкой.
Нетрудно видеть, что каждая формула над множеством элементарных функций (0, 1, ..к — 1, 10(х)^ ... ..Д-Дя), minfxi, Xi)t шах^, я2)} может быть при помощи тождеств 1—7 преобразована к д. н. ф. Отсюда легко доказать, что правила 1—7 позволяют перейти от любой формулы над данным множеством к любой другой формуле, эквивалентной исходной. Последнее свидетельствует о том, что система тождеств 1—7 в известном смысле обладает полнотой.
л. 4^.7 ьііиїХііїХБІ и иііІІҐЛЦИНМИ
§ 2. Примеры полных систем
В Рк определение полноты выглядит так же, как и в Рг.
Определение. Система $ функции Д, /2, .. из Рк называется (функционально). полной, если любая функция из Рк может быть записана в виде формулы через функции этой системы.
Ниже рассматриваются примеры полных систем. Для обоснования полноты мы будем использовать принцип сведения задачи о полноте одних систем к задаче о полноте других (см. § 5, гл. 1).
1. Система $ = Рк полна. Очевидно, что множество всех функций из Рк представляет полную систему.
2. Система
ф = Ш, 1, ..к — 1, 10{х), ..Д-Дя),
тіп^!, х2), шах(?і, хг)}
является полной.
Теорема 2. Система
$ = {0, 1, ..., к — 1, 10(х), ..7ц-і(я)»
тіп(я'и х2), тах^і, га)}
является полной в Рк.
Доказательство. Пусть 1(хи . •^—произвольная функция из Рк. Для нее имеет место разложение
/ (*^11 • • '> V (жі) & * * * & ^оп{р^п} & /(^ії * *
Данная формула (правая часть) построена из функций, входящих в Теорема доказана.
3. Система $ = {?, тах(^!, х2)У является полной. 1 Теорема 3. Система ф = (я, тах(я1} хг)} полна в Рк.
Доказательство. а) Построение констант. Из функции х = х + 1 получаем функции
ж + 2 = (ж+1)+1, х + к-1=(х + к — 2)+1,
х — хЛ-к = {хЛ-{к — 4))+1.
Легко видеть, что
тах (х, х + 1, ..., х ~Ь к — 1) — к — 1.
Отсюда при помощи х получаем остальные константы
гл. 2. ft-Значил я логика
49
б) Построение функций одной переменной. Сначала получаем функции /Да) (? = 0,,.к— 1):
Ji (а) = 1 + шах {а + а}.
a^ft— 1—i
В самом деле, если х = i, то левая часть равна к — 1, а правая часть есть
1 -f max {i + а} = 1 + max {г + а} =
ct^fc—1— i i+a^fc—1
— 1 + A — 2*=A — 1;
если x ?= i, то левая часть равна 0, а правая —
1 + max {х + а} = 1 + (я -f {к — 1 — х)) — к = 0,
a,?=h—1—I
Введем функции Да), где
18 При X=it 10 при хфЬ,
Покажем, что
/5[ Да) = s + 1 + max[/Д а), к — 1 — а].
Последнее легко усматривается из графиков, изображенных на рис, 1.
к-1
к-1 т °
k-f-?Q О
-4-0—
О 1 i-lii+7 к-1 Sim
к-1т
-В-К4
О 1 И i i+1 к-1
mv[$(&,k-f-sj
Рис. 1
О 1 Hii+S k-J з +/+пшд[? (х), k-hsJ
