Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пример 1. Пусть $ — множество «элементарных» функций. Следующие выражения являются формулами над
1) {[(#ьг2) Т ж,1 + х2);
2) [а\(^2 + ж3)]:
ГЛ. 1. АЛГЕБРА ЛОГИКИ
15
В дальнейшем будем обозначать формулы заглавными готическими буквами с квадратными скобками, в которых перечисляются функции, необходимые для их построения. Так
означает, что формула % достроена из /1? ..В тех случаях, когда нужно обратить внимание на множество тех переменных, которые участвуют в построении формулы, пишут
Пусть — произвольная формула над тогда формулы, которые использовались для ее построения, будем
называть подформулами формулы §1.
Пусть формула % является формулой над множеством
где имеет те же переменные, что и /< (1—1, . . у).
Определение. Рассмотрим формулу __
Говорят, что формула © имеет то же строение, что и формула 51.
Пример 2.
Очевидно, что §( и © имеют одинаковое строение.
В дальнейшем строение формулы обозначается через С (с индексами или без них), и формула Ш однозначно определяется строением С и упорядоченной совокупностью {Д, /г, .. /Л. Поэтому можно писать 51 =»
Сопоставим теперь каждой формуле- ?«).
над $ функцию хп) из Рг, опираясь на индук-
тивное определение формул.
а) Базис индукции. Если €С(а?1, ..хп) = ...
,.хп), где то формуде «(®1т ..хп) сопоставим
функцию }{хи ..Хп\,
Ч1и •./Л
§1(А, ..., хп).
..., gX которая получается из 51 путем замены
1) $ = {хи (Хі&а:2)>, % = [ж1&(ж2&г3)];
2) 0 = {хі, (аг± -*? л’2)}, © = [хг -> (х2 -*? ^)].
- С[Д, д,..., Л].
16 4.1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
б) Индуктивный переход. Пусть Ш(хи ...
..., хп)=и(Аи ..Ат), где (г = 1, ..т) является
ЛИСО формулой Над Либо СИМВОЛОМ ПеремеННОЙ Яд!,.
Тогда по предположению индукции А% сопоставлена либо функция /4 из Ра, либо тождественная функция /{— Сопоставим формуле %{хи ,.хп) функцию /(ад, ...
« ? ?» Хп) /о (Д, . . /т) .
Если функция / соответствует формуле то говорят также, что формула §1 реализует функцию /. Поскольку функции рассматриваются с точностью до фиктивных переменных, мы считаем, что формула % реализует и любую функцию, равную /.
Замечание 1. Если функция {(х1, ..хп), реализуемая формулой &(.?„ ..хп), имеет несущественную переменную хи то при п > 1 переменную Хг можно удалить, заменив функцию / равной ей функцией /', а формулу % — формулой 9Г, получающейся из I в результате отождествления переменной Xi с любой из оставшихся переменных. Очевидно, что §(' является формулой над ф и реализует функцию /'.
Функцию /, соответствующую формуле будем называть суперпозицией функций из а процесс получения функции / из ^ будем называть операцией суперпозиции.
Пример 3. Пусть Д(х„ а;г), /г(ж,, х2, *,)' и Д(х,, Хг, я-3) — функции, соответствующие формулам из примера 1.
1) Формула (((Я|Яг) + яч) + %г) строится за три шага.
Мы имеем следующие подформулы:
\XyXi}, ( (х&г)| + Хх)I, ({ {Х&г)I + XI) + Хг).
В табл. 4 приводятся соответствующие им функции, которые вычисляются с использованием табл. 3 и правила б). Последний столбец определяет функцию и(хи ха); очевидно, что }±(хи хй) = тах(а:1, хг).
Таблица 4
я, Х1 (ГС, Я*) ((х^Н-х,)
0 0 0 0 0
0 1 0 0 1
1 0 0 1 1
1 1 1 0 1
ГЛ. 1. АЛГЕБРА ЛОГИКИ 17
2) Функцию /г(#1, ж2, ж3) мы будем строить несколько иным путем (также вытекающим из определения). Для каждого набора (ои о2) о3), используя табл. 2 и 3, найдем
/г(С1, 02, 0з) = (0,(02 + 0а))
(см. табл. 5)'.
Таблица 5
*1 ж* /дСяГц хв, х,) X,, X,)
0 0 0 0 0
0 0 1 1 1
0 1 0 4 1
0 1 1 0 0
1 0 0 0 0
1 0 1 0 0
1 1 0 0 0
1 1 1 0 0
3) Для нахождения функции 1$(х{, ж2, жэ) будем, опираясь на табл. 2 и 3, искать те наборы, на которых формула
{ж( V [(ж2 -? ^з) (^8 -*? я2)]>
обращается в 1. Очевидно, что это равносильно нахождению случаев, при которых формула
(ж, V [(ж2 ж3) (аг, -*• ж2)]>
равна 0. Последнее имеет место при х± — 0 и в тех случаях, когда [(ж2 -*? ж8) (жг -*• жг)] обращается в 0. Наконец, формула [{жг ха) (жа -*? жг)] обращается в 0, когда по крайней мере одна из формул (ж2-^ж3), (жэ-^жг) обращается в 0, что имеет место при жг = 1, ж3 = 0 или при ж2 =* 0, жа = 1. Таким образом, /з(ж1( жг, ж3) равна 1 на наборах (0,0,1) и (0,1,0) (см. табл. 5).
Замечание 2. Пункт б) в определении формул можно ааменить на пункт, использующий две более простые операции.
1) Операция подстановки переменных. Пусть
/Ж, ... ХП \
\^1 * * 1
2 С. В. Яблонский .
ГеТблютека чду]
18 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
— подстановка переменных (лчу ие обязана отличаться от при V Ф р). Эта подстановка позволяет произвести подстановку переменных у функции ${хи ..#„) и получить в результате функцию /(^ц, ...» 2Г|„). Очевидно, подстановка переменных включает в себя переименование переменных, перестановку переменных и отождествление переменных.
2) Операция бесповторной подстановки функций. Она позволяет строить выражения 1{АХ, ..., Ат)ч где Ai — либо формула, либо переменная из 17, причем хотя бы одно из отлично от переменной, а множества переменных, входящих в ^ и Ане нересекаются.
Очевидно, что всякая формула над $ может быть получена из функций, принадлежащих путем применения сначала операции бесповторной подстановки функций (многократной), а затем операции подстановки переменных (причем однократной).
