4.3. Суперпозиции и формулы
Суперпозицией функции f1, f2, ..., fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных, а формулой называется выражение, описывающее эту суперпозицию. Понятие суперпозиции очень важно в алгебре логики, поэтому рассмотрим его более подробно.
Пусть дано множество (конечное или бесконечное) исходных функций
M = { f1, f2, ..., fm }. Символы переменных х1, х2, ..., хi, ..., хn считают формулами глубины 0. Формула F имеет глубину k+ 1, если F имеет вид fi(F1, F2, ... Fni ), где fi Î M, пi – число аргументов fi, а F1, F2, ... Fni – формулы, максимальная из глубин которых равна k. F1, F2, ... Fni называются подформулами F, fi называется внешней или главной операцией формулы F. Все подформулы формул F1, F2, ... Fni также называются подформулами F. Например, f1(x1, x3) – это формула глубины 1, a f2(f1(x1, x3), f3(x1, f2(x1, x2))) – формула глубины 3, содержащая одну подформулу глубины 2 и две подформулы глубины 1.
Конкретные формулы, как правило, имеют более привычный вид, при котором знаки функций стоят между аргументами (такую запись называют
инфиксной). Например, если f1 обозначает дизъюнкцию, f2 – сложение по
mod 2, а f3 – конъюнкцию, то приведенная выше формула примет вид:
(х1 Ú х3) Å (х1 Ù (х1 Å х2)).
Все формулы, построенные описанным образом, т.е. содержащие только символы переменных, скобки и знаки функций из множества М, называются формулами над М.
Возможны и другие варианты понятия глубины. Например, часто считается, что расстановка отрицаний над переменными не увеличивает глубины; в случае, когда М содержит ассоциативную операцию f, можно определить глубину так, что применение f к формулам с той же внешней операцией f не увеличивает глубину формулы. Например, х1 (х2 Ú х3 х4) и х1 х2 (х2 Ú х3 х4)
имеют одну и ту же глубину 3.
Всякая формула, выражающая функцию f как суперпозицию других функций, задает способ ее вычисления (при условии, что известно, как вычислить исходные функции). Этот способ определяется следующим очевидным правилом: формулу можно вычислить, только если уже вычислены значения всех ее подформул.
Вычислим, например, формулу (х1 Ú х3) Å (х1 Ù (х1 Å х2)) на наборе х1 = 1, х2 = 1, х3 = 0. Получим (используя табл. 4.2): х1 Ú х3 = 1; х1 Ù (х1 Å х2) = х1 Ù 0 = = 0; (х1 Ú х3) Å (х1 Ù (х1 Å х2)) = 1 Å 0 = 1.
Таким образом, формула каждому набору значений аргументов ставит в соответствие значение функции и, следовательно, может служить наряду с таблицей способом задания и вычисления функции. В частности, по формуле, вычисляя ее на всех 2n наборах, можно восстановить таблицу функции. О формуле, задающей функцию, говорят, что она реализует или представляет эту функцию.
Представление данной функции формулой, в отличие от табличного задания, не единственно. Например, если в качестве исходного множества функций зафиксировать множество {f1, f7, f10,}, т.е. функции И, ИЛИ, НЕ, то функцию штрих Шеффера можно представить формулами
а функцию стрелка Пирса – формулами
Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными. Эквивалентность формул обозначается знаком равенства; поэтому можно записать f14(x1, x2) = `х1 Ú `х2 или х1 Ù х2 .
Существует стандартный метод, позволяющий ответить на вопрос эквивалентны две формулы или нет. По каждой формуле восстанавливается таблица функции, а затем полученные две таблицы сравниваются. Иначе говоря, для каждого набора значений переменных проверяется, равны ли на нем значения формул. Этот метод требует 2´2n вычислений (если считать, что обе формулы зависят от п переменных) и на практике оказывается слишком громоздким. Существуют и другие методы установления эквивалентности формул и получения новых формул, эквивалентных исходной – методы эквивалентных преобразований формул.