2.2. Формулы. Реализация функций формулами
Как и в элементарной алгебре, исходя из «элементарных» функций, можно строить формулы.
Приведем индуктивное определение формул.
Определение.
Пусть В – некоторое подмножество функций из Р2.
Базис индукции. Каждая функция f(x1, …, xm) из В называется формулой над В.
Индуктивный переход. Пусть f(x1, …, xm) – функция из В и А1, …, Аm – выражения, являющиеся либо формулами над В, либо символами переменных из U. Тогда выражение f(А1, …, Аm) называется формулой над В.
Пример 1: Пусть В – множество «элементарных» функций. Следующие выражения являются формулами над В:
(((x1Λx2)+ x1)+x2);
(
Λ
(x1+x2));(
).
Пусть M[f1, …, fn] – произвольная формула над В, тогда формулы, используемые для ее построения будем называть подформулами М.
Пусть формула М= M[f1, …, fs] – формула над множеством В={ f1(x1, …, xn), …, fs(x1, …, xn) }.
Возьмем множество функций
G={g1(x1, …, xn), …, gs(x1, …, xn)},
где gi имеют те же переменные, что и fi (i=1…s).
Определение. Рассмотрим формулу N[g1, …, gs], которая получается из М путем замены (f1, …, fs) на (g1, …, gs). Говорят, что формула N имеет то же строение, что и формула М.
Пример 2.
;
;
.
Очевидно, что М и N имеют одинаковое строение. Функцию f, соответствующую формуле М, будем называть суперпозицией функций из В, а процесс получения функции f из В будем называть операцией суперпозиции.
Пример 3. Пусть функции f1(x1, x2, x3), f2(x1, x2, x3), f3(x1, x2, x3) – функции, соответствующие формулам из примера 1.
1) Формула (((x1Λx2)+x1)+x2) строится за три шага: (x1Λx2); ((x1Λx2)+x1); ((x1Λx2)+x1)+x2. Составим таблицу этой функции.
Таблица 4
-
x1
x2
(x1Λx2)
(x1Vx2)+x1
((x1Λx2)+x1)+x2
0
0
0
0
0
0
1
0
0
1
1
0
0
1
1
1
1
1
0
1
Последний столбец определяет функцию f1(x1, x2). Нетрудно видеть, что f1(x1, x2)=max (x1, x2)= x1Vx2.
2) Функцию f2(x1, x2, x3) будем строить сразу:
f2(x1, x2, x3)= Λ (x1+x2).
Таблица 5
-
x1
x2
x3
f2(x1, x2, x3)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
3)
Для нахождения функции f3(x1,
x2,
x3)
будем искать те наборы, на которых
формула: {
}
обращается в 1. Очевидно, что это происходит
тогда, когда
обращается в 0. Последнее имеет место
при x1=0
и при
.
Это же выполняется тогда, когда, по
крайней мере одна из формул (x2→x3)
или (x3→x2)
обращается в 0, что имеет место при x2=1,
x3=0
или при x2=0,
x3=1.
Таким образом f3(x1,
x2,
x3)
равна 1 на наборах (0, 0, 1) и (0, 1, 0).
Таблица 6
-
x1
x2
x3
f3(x1, x2, x3)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
Отметим, что f2(x1, x2, x3)= f3(x1, x2, x3).
Введенный таким образом язык формул удобен для записи функций алгебры логики, описывающих различные условия или высказывания.
Рассмотрим два примера. В них используются высказывания вида «имеет место х» или просто «х», а это означает, что при данных условиях х истинно, или равно 1.
Пример 4. Сложение n-разрядных чисел.
Исходим из обычного алгоритма сложения столбиком
xn … x2 x1
+
yn … y2 y1
____________
zn+1zn … z2 z1
Требуется выразить значения разрядов суммы через значения разрядов слагаемых. Для решения этого вопроса рассмотрим вспомогательные величины wn, wn-1, …, w1, где wi означает результат переноса из i-го разряда в (i+1) разряд.
Ясно, что
zi=((xi+yi)+wi-1)
(w0=0, xn+1= yn+1=0, i=1, …, n+1).
Величина wi определяется уровнем переноса из i-го разряда в (i+1)-й: «перенос в (i+1)-й разряд имеет место тогда и только тогда, когда по крайней мере две из трех величин xi, yi, wi-1 равны 1». Это высказывание можно cформулировать так: «xi и yi» или «xi и wi-1» или «yi и wi-1» или формально
wi=(((xiΛyi)V(xiΛwi-1))V(yiΛwi-1)) i=1, …, n.
Пример 5. Задача о вызове свободного лифта.
В подъезде имеется три лифта, обслуживающих n этажей. На каждом этаже имеется устройство, позволяющее при нажатии кнопки вызвать ближайший свободный лифт. Вопрос: как можно на логическом языке записать условие вызова i-го лифта (i=1, 2, 3)?
Рассмотрим задачу для случая вызова лифта на первом этаже.
Для описания исходной информации введем 3n аргументов
x1, y1, z1, x2, y2, z2, …, xn, yn, zn,
где xi=1, тогда и только тогда, когда 1-й лифт находится на i-м этаже и свободен. yi и zi – аналогично для второго и третьего лифтов.
Обозначим через
fI(x1, y1, z1, …, xn, yn, zn); fII(x1, …, zn); fIII(x1, …, zn)
функции равные 1 тогда и только тогда, когда вызывается лифт с номерами 1, 2,3 соответственно.
Условие вызова 1 лифта, или функция fI, характеризуется тем, что «1 лифт свободен или нет свободных лифтов, расположенных на более низком этаже, чем 1-й лифт. Это высказывание более подробно можно выразить следующим образом:
«1-й лифт вызывается тогда и только тогда, когда 1-й лифт находится на 1-м этаже и свободен, или на 1-м этаже нет свободных лифтов с номерами 2 и 3, и в этом случае 1-й лифт находится на 2-м этаже и свободен, или на 2-м этаже нет свободных лифтов с номерами 2 и 3 и лифт №1 находится на 3-м этаже и свободен и т.д….».
Запишем это высказывание через высказывания
x1, y1, z1, x2, y2, z2, …, xn, yn, zn:
«1-й лифт вызывается тогда и только тогда, когда x1 или «не y1», «не z1», и в том случае x2 или «не y2 и не z2» и в этом случае …».
Таким образом
fI(x1,
y1,
z1,
…, xn,
yn,
zn)=(x1V((
Λ
)
Λ(x2V((
Λ
)
Λ(…))..).
Аналогично
fII(x1,
…, zn)=(y1V((
Λ
)
Λ(y2V((
Λ
)
Λ(…))..).
fIII(x1,
…, zn)=(z1V((
Λ
)
Λ(z2V((
Λ
)
Λ(…))..).