Как сделать суперпозицию

Обновлено: 05.07.2024

При функциональном программировании часто используется суперпозиция функций. Для ее реализации используются следующие функции:

Nest [expr, x, n] — n раз применяет выражение (функцию) ехрг к заданному аргументу х,
NestList [f, x, n] — возвращает список результатов (п+1)-кратного применения функции f к заданному аргументу х;
Fold[f, x, list] — дает последний элемент в FoldList [f, x, list];
FoldList [f, x, ] — возвращает список ;
ComposeList [ < f , f . >, x] — генерирует список в форме .

Примеры, иллюстрирующие действие этих функций, представлены ниже:

Функции Fixed Point и Catch

В функциональном программировании вместо циклов, описываемых далее, может использоваться следующая функция:

FixedPoint [ f, expr ] — вычисляет expr и применяет к нему f, пока результат не перестанет изменяться;
FixedPoint [ f, expr, SameTest->comp] — вычисляет expr и применяет к нему f, пока два последовательных результата не дадут True в тесте SameTest.

Пример применения функции FixedPoint:

Последний результат (ноль) выводится в отдельной (нумерованной) ячейке вывода и означает завершение процесса итераций — деления t на 2.

Следующий пример показывает, как можно создать цепную дробь с помощью функции Nest:

Еще одна функция такого рода — это Catch:

Catch [expr] — вычисляет expr, пока не встретится Throw [value], затем возвращает value;
Catch [expr, form] — вычисляет expr, пока не встретится Throw [value, tag], затем возвращает value;
Catch [expr, form, f] — возвращает f [value, tag] вместо value. Ниже представлены некоторые конструкции циклов с оператором Catch:

Реализация рекурсивных и рекуррентных алгоритмов

Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:

В этом простейшем примере результат вычислений есть возвращаемое функцией sen значение — численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.

Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри ее тела, а рекуррентность — получение результата на данном шаге по результатам вычислений на предшествующих шагах.

Рассмотрим, как это делается, с помощью описанных выше функций. Классический пример реализации рекурсивного алгоритма — вычисление факториала путем задания функции, в теле которой есть обращение к ней же самой:

Полезно, однако, обратить внимание на возможность явного задания результата для конкретных значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная с n=2 и выше, в соответствии с классическим определением факториала.

Для реализации рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или FixedPoint. В следующих примерах показано вычисление

квадратного корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции newtonS:

Далее зададим функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения f(x) при начальном значении х ₀ = а, по следующим формулам:

Эту функцию можно записать следующим образом:

Тогда вычисления корня из выражения е^x - 2 с начальным приближением х ₀ = 0.5 при числе итераций n можно организовать с помощью функций Nest и NestList:

В первом случае возвращается только окончательный результат, а в других — еще и все промежуточные. Функция FixedPoint позволяет осуществлять итерации

до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:

Более сложные примеры функционального программирования мы рассмотрим позже, при описании создания пакетов расширения систем Mathematica.

Функция f, получаемая из функций f₁, f₂,…f_n с помощью операций подстановки и переименования аргументов, называется суперпозицией функций.

Всякая формула, выражающая функцию f как суперпозицию других функций, задаёт способ её вычисления, т. е. формулу можно вычислить, если вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.

По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул в различных базисах

Формулы F_i и F_j представляющие одну и ту же логическую функцию f_i, называются эквивалентными. Так, эквивалентными формулами являются:

Если какая-либо формула F содержит подформулу F_i, то замена F_i на эквивалентную F_j не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.

Для упрощения сложных алгебраических выражений булевой функции выполняют эквивалентные преобразования, используя законы булевой алгебры и правила подстановки и замещения,

При написании формул булевой алгебры следует помнить:

· число левых скобок равно числу правых скобок,

· нет двух рядом стоящих логических связок, т. е. между ними должна быть формула,

· нет двух рядом стоящих формул, т. е. между ними должна быть логическая связка,

· логическая связка “×” сильнее логической связки “Ú”,

· если “ù ” относится к формуле (F₁×F₂) или (F₁Ú F₂), то прежде всего следует выполнить эти преобразования по закону де Моргана: ù(F₁×F₂)=`F₁Ú`F₂ или ù(F₁ÚF₂)=`F₁×`F₂;

· операция “×” сильнее “Ú”, что позволяет опускать скобки.

· по закону коммутативности:

· по закону дистрибутивности:

· по закону де Моргана:

· по закону противоречия:

Пример: выполнить преобразования формулы

· по закону де Моргана

· по закону дистрибутивности:

· по законам коммутативности и дистрибутивности:

· по закону противоречия:

· по закону Порецкого

· по закону де Моргана:

· по закону дистрибутивности:

· по закону поглощения:

Пример: выполнить преобразование формулы:

1) преобразовать формулу в базис булевой алгебры:

2) опустить знак “` “ до двоичных переменных:

3) преобразовать формулу по закону дистрибутивности:

4) вынести за скобку `x₂ по закону дистрибутивности:

5) преобразовать по закону дистрибутивности:

6) использовать закон противоречия:

Свойства булевых функций

Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f₀, f₁. f₁₅? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.

Самодвойственные булевы функции

Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.

Монотонные булевы функции

Например, для функций f(x₁; x₂) монотонными функциями являются:

если (0; 0)£(0; 1), то f(0; 0)£f(0; 1),

если (0; 0)£(1; 0), то f(0; 0)£f(1; 0),

если (0; 1)£(1; 1), то f(0; 1)£f(1; 1),

если (1; 0)£(1; 1), то f(1; 0)£f(1; 1).

Таким условиям удовлетворяют следующие функции:

Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.

Линейные булевы функции

Алгебра Жегалкина, опирающаяся на базис F₄=, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0£i£n:

Например, для логических функций f₈(x₁; x₂)

Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.

Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x₁; x₂;…;x_n)=b₀×1Åb₁×x₁Å…Åb_n×x_n называют линейными.

Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.

Если логическая функция задана таблицей или формулой в любом базисе, т.е. известны значения булевой функции для различных наборов булевых переменных, то можно вычислить все

коэффициенты b_i полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.

таблица 1.18
Наименование закона	Эквивалентные формулы
коммутативности	x₁ Å x₂=x₂ Å x₁
ассоциативности	x₁Å (x₂ Å x₃)=(x₁Å x₂) Å x₃;
дистрибутивности	x₁×(x₂ Å x₃)=x₁×x₂ Å x₁×x₃;
свойство “1”	xÅ 1=`x;
свойство “0”	xÅ 0=x;
сложение по модулю 2	xÅ x=0; xÅ`x=1.

Пример: дана булева функция f(x₁;x₂)=x₁Úx₂ . Значение этой функции известны для всех наборов булевых переменных.

Следовательно, (x₁Úx₂)=x₁Åx₂Åx₁×x₂, т. е. дизъюнкция есть нелинейная булева функция.

Пример: дана булева функция f(x₁;x₂)=(x₁®x₂). Значение этой функции также известны для всех наборов двоичных переменных.

В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.

таблица 1.19
f_i	эквивалентные формулы
f₇	(x₁Úx₂)=x₁Å x₂Å x₁×x₂;
f₈	(x₁¯x₂)=ù(x₁Úx₂)=1Å x₁Å x₂Å x₁×x₂;
f₉	(x1«x2)=(`x₁×`x₂Úx₁×x₂)=1Å x₁Å x₂;
f₁₂	`x₁=1Å x₁;
f₁₃	(x₁¯x₂)=(`x₁Úx₂)=1Å x₁Å x₂Å x₁×x₂;
f₁₄	(x₁½x₂)=ù(x₁×x₂)=1Å x₁×x₂.

Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F₂=:

Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.

1.5.6.4. Функции, сохраняющие “0”

Функция f(x₁; x₂;. x_n) называется сохраняющей “0”, если для наборов значений двоичных переменных (0; 0;. 0) функция принимает значение f(0; 0;…0)=0.

Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “0”, сама является функцией, сохраняющей “0” Поэтому множество функций, сохраняющих “0”, не позволяет формировать функции, не сохраняющие “0”.

1.5.6.5. Функции, сохраняющие “1”

Функция f(x₁; x₂;…x_n) называется сохраняющей “1”, если для наборов значений двоичных переменных (1; 1;…1) функция принимает значение f(1;1;…1)=1.

Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “1”, сама является сохраняющей “1”. Поэтому множество функций, сохраняющих “1”, не позволяет формировать функции, не сохраняющие “1”.

Пусть имеется некоторый набор K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции, полученные с помощью конечного числа применения двух операций;

можно переименовать любую переменную, входящую в функцию из K;

вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.

Суперпозицию еще иначе называют сложной функцией.

Пример 7.1. Если дана одна функция х|y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z) и т. д.

Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым, если его замыкание совпадает с ним самим.

Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции.

Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором (в этом убедились в разд. 5), но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина (разд. 6). Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина).

Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание.

Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:

Так как очевидно , т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда , штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией (студенты могут проверить это сами). Для функций 3-х или более переменных шефферовских функций очень много (конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются).

Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.

Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций:

Т₀ – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т₀ – это класс функций, сохраняющих 0);
Т₁ – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т₁ – это класс функций, сохраняющих единицу) (заметим, что число функций от п переменных принадлежащих классам Т₀ и Т₁ равно 2 2n-1 );
L – класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;
М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных: s1 = (x₁, x₂. x_n)

s ₁ = ( х₁ , х₂ , … , х_п ) и s ₂ = ( y₁ , y_2,… , y_п) . Будем говорить, что набор s ₁ меньше набора s ₂ (s ₁ £ s ₂ ), если все х_i £ y_i. Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п = 2 наборы (0,1) и (1,0) не сравнимы между собой). Функция от п переменных называется монотонной , если на меньшем наборе она принимает меньшее или равное значение. Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Понятно, что несравнимые наборы – это те, в которых есть некоторые координаты типа (0,1) в одном наборе и (1,0) в другом на соответствующих местах (в дискретной математике монотонные функции это только как бы “монотонно возрастающие функции”, “монотонно убывающие” функции здесь не рассматриваются).

Пример. В нижеследующей таблице функции f₁, f₂ являются монотонными функциями, а функции f₃, f₄ – нет.

Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.

Способы задания функций

0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1

Gi - значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.

Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)

На векторах, помеченных звездочкой, функция обращается в 1.

Nf = = [1,3,4,6] [] – указаны номера векторов.

3. В виде формулы.

Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают.

Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно.

Фиктивные переменные у функции можно добавлять и исключать.

Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.

Читайте также: