Из примеров видно, что несравнимые наборы - это те, в которых есть компоненты типа (01) в одном наборе и (10) в другом наборе на соответствующих местах.

Определение 3. Функция f(х₁,…,х_n) называется монотонной (принадлежит классу М), если для любых двух сравнимых между собой наборов б, в Вⁿ из того, что б предшествует в, следует, что f(б) не больше f(), то есть бв f(б) f(в).

Если же существует такая пара наборов, что бв, но f(б) > f(в), то функция f(х1,…,хn) - немонотонная По аналогии с непрерывными функциями, которые изучаются в курсе математического анализа, функции алгебры логики можно было бы назвать неубывающими. Но поскольку мы не будем иметь дело с невозрастающими функциями, можно говорить просто о монотонности..

Пример 20. Тождественная функция f(x) = x является монотонной, поскольку б=(0) (1)=в и f(б)=0 < 1=f()

Пример 21. f(x,y) = xy - монотонная функция.

Действительно, наборы (01) и (10) несравнимы, их в расчёт брать не будем. Для других наборов имеем:

(00) (01) и f(0,0)=0 1= f(0,1).

(00)-- (11) и f(0,0)=0 1= f(1,1).

(01) (11) и f(0,1)=1 1= f(1,1).

(10)-- (11) и f(1,0)=1 1= f(1,1).

Мы убедились, что xy равна 0 лишь на наборе (00), который предшествует всем остальным наборам, так что условие монотонности функции выполняется.

Пример 22. f(x,y)=x&y - монотонная функция, т.к. равна 1 лишь на наборе (11), которому предшествуют все остальные.

Пример 23. Константы 0 и 1 являются монотонными функциями, т.к. для любых наборов будет f(б)=f(в).

Пример 24. f(x)=x' - немонотонная функция, т.к. при б=(0) и в=(1) имеем бв, но f(б)=1> 0=f(в).

Пример 25. f(x,y)=xy - немонотонная функция.

Действительно,

(00)---- (01) и f(0,0)=1 1=f(1,1) ,

(10)---- (11) и f(1,0)=0 1=f(1,1).

Но при (00)---- (10) получим

f(0,0)=1 > 0=f(1,0).

Условие монотонности функции не выполняется!

Пример 26. Определим монотонность функции сложение по модулю 2:

f(x,y)= x+y.

Наборы (01) и (10) несравнимы, их в расчёт брать не будем.

Для других наборов имеем:

(00) (01) и f(0,0)=0 1= f(0,1).

(00)-- (10) и f(0,0)=0 1= f(1,0).

(00) (11) и f(0,0)=0 0= f(1,1).

(10) (11) и f(1,0)=1 > 0= f(1,1).

Последнее условие говорит о том, что функция x+y немонотонна.

5.2 Распознавание монотонной функции по вектору её значений

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

1. Сравниваем левую половину вектора значений функции (вектор ц₂) со второй, правой его половиной (вектор ш₂).

Если условие ц2 ш2 нарушено, то функция немонотонна, иначе переходим к п.2.

2. Сравниваем в каждой половине вектора значений функции левые четвертины (векторы ц₄₁ и ц₄₂ ) с правыми четвертинами (векторы ш₄₁ и ш₄₂ ).

Если хотя бы одно из условий ц₄₁ ш₄₁ и ц₄₂ ш₄₂ нарушено, то функция немонотонна, иначе переходим к п.3.

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

Рисунок 1 показывает разбиение вектора значений функции трёх переменных.



Рисунок 1 - Части вектора значений функции f(x,y,z)

Рассмотрим несколько примеров распознавания монотонности функции с помощью приведённого алгоритма. Начнём с функций (дизъюнкции и импликации) двух переменных, проанализированных в примерах 21 и 25, соответственно. Затем рассмотрим пару функций трёх переменных.

Пример 21.1. Функция xy представляется вектором её значений (01 11), Видим В этом и следующих примерах левая половинка ц₂ вектора значений функции отделена пробелом от ш₂ - правой половинки этого вектора. , что условие ц₂ ш₂ выполняется, поэтому рассмотрим соответствующие четвертины. Сравнение левых (подчёркнутых) четвертин показывает, что ц₂₁=0 < 1=ш₂₁, сравнение правых четвертин даёт ц₂₂=ш₂₂.

Это означает, что ц₂₁ ш₂₁ и ц₂₂ ш₂₂, то есть ни одно из проверяемых условий не нарушено - дизъюнкция монотонна.

Пример 25.1. Импликация xy представляется вектором значений (11 01). Сравнение половинок ц₂=(11) и ш₂=(01) сразу же обнаруживает нарушение условия ц₂ ш₂. Этот факт ещё раз подтверждает вывод, сделанный в примере 25: функция xy немонотонна.

Пример 18.1. В примере 18 познакомились с функцией голосования, отражающей принятие решения «по большинству голосов». Проверим эту функцию на монотонность.

Вектор значений этой функции - (0001 0111). Сравнивая (см. рисунок 1) левую половину этого вектора с правой половиной, убеждаемся, что

ц₂=(0001) (0111)=ш₂.

Сравниваем левые четвертины (подчёркнутые):

ц₄₁=(00) (01)=ш₄₁.

Сравниваем правые четвертины: ц₄₂=(01)? (11)=ш₄₂.

Условие предшествования выполняется для обеих четвертин. Поэтому сравним осьмушки, то есть соответствующие левые и правые половинки четвертин. Получим:

ц₈₁=ш₈₁=0, ц₈₂=0 < 1=ш₈₂,

ц₈₃=0 < 1=ш₈₃, ц₈₄=ш₈₄=1.

Выполнение всех условий предшествования осьмушек доказывает монотонность функции голосования. O

Пример 27. Пусть функция задана вектором значений (1111 0010).

Сравнение половинок ц₂=(1111) и ш₂=(0010) приводит к выводу, что эта функция немонотонна, т.к. не выполняется условие ц₂ш₂ .

Пример 28. Для функции x+y анализ вектора её значений (01 10) неприменим, поскольку ц₂=(01) и ш₂=(10) - несравнимые наборы.

Пример 29. Для функции стрелка Пирса xy вектор её значений (10 00). Сравнение ц₂=(10) с ш₂=(00) показывает, что эта функция немонотонна, ибо условие ц₂ш₂ нарушается.

5.3 О замкнутости класса монотонных функций

Теорема о замкнутости класса M. Множество M всех монотонных функций образует замкнутый класс.

Доказательство. Надо показать, что суперпозиция монотонных функций тоже будет монотонной функцией. Пусть даны функции g(y₁, …,y_m), f₁(x₁, …,x_n),…, f_m(x₁, …,x_n), входящие в класс M. Условимся, не нарушая общности, следующие рассуждения проводить для m=3 и n=2.

Подставим y₁=f₁(x₁,x₂), y₂=f₂(x₁,x₂), y₃=f₃(x₁,x₂) вместо аргументов в функцию g(y₁,y₂,y₃) и покажем, что полученная суперпозиция также будет монотонной функцией. Заметим, что после подстановки получится функция от двух аргументов:

g(y₁,y₂,y₃)=g( f₁(x₁,x₂), f₂(x₁,x₂), f₃(x₁,x₂) ) h(x₁,x₂)

Подставим в функцию h(x₁,x₂) любую пару наборов б=(б₁,б₂) и в=(в₁, в₂) таких, что бв. Получим

h(б) g( f₁(б), f₂(б), f₃(б) ) = g(г),

h(в) g( f₁(в), f₂(в), f₃(в) ) = g(д),

где г=( f₁(б), f₂(б), f₃(б) ) и д=(f₁(в),f₂(в),f₃(в) ) - булевы векторы.

Так как бв и функции f₁(x₁,x₂), f₂(x₁,x₂), f₃(x₁,x₂) монотонны, то f₁(б)f₁(в), f₂(б)f₂(в), f₃(б)f₃(в). Значит, гд. Поскольку функция g(y₁,y₂,y₃) тоже монотонна, то g(г) g(д). Отсюда h(б) h(в), то есть h(x₁,x₂) - монотонна, и класс M замкнут. O

5.4 Распознавание монотонной функции по формуле

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

Теорема об условиях монотонности функций. Монотонными являются те и только те функции, которые или являются константами 0 и 1, либо допускают представление в виде ДНФ без инверсий.

Пример 30. Прежде, чем привести доказательство этой теоремы, рассмотрим функцию голосования f(x,y,z)=(0001 0111), в монотонности которой мы убедились (см. пример 17.1).

Представим её в виде СДНФ и попробуем избавиться от переменных, входящих в формулу со знаком инверсии:

f(x,y,z)=x'yz xy'z xyz' xyz =

={ два последних слагаемых отличаются тем, что переменная z в одном из них - со знаком инверсии, а в другом - без инверсии }=

=x'yz xy'z xy(z' z)= x'yz ( xy'z xy) = x'yz x(y'z y) =

= x'yz x(z y) = (x'yz xz) xy = z(x'y x) xy =

= z(y x) xy = yz xz xy.

Этот пример может служить иллюстрацией к следующему ниже доказательству необходимости.

Доказательство необходимости. Допустим, что функция монотонна. Константы 0 и 1 монотонны, поэтому их из дальнейших рассуждений исключим. Представим монотонную функцию, отличную от 0 и 1, в виде СДНФ. Докажем, что в ней отсутствуют слагаемые, то есть полные правильные элементарные конъюнкции Напомним, что элементарная конъюнкция называются правильной, если в неё каждая переменная входит не более одного раза (включая её вхождение со знаком инверсии). Правильную элементарную конъюнкцию называют полной относительно переменных х₁, х₂,…, х_n , если в неё каждая из этих переменных входит один и только один раз (может быть, под знаком инверсии). , в которые входят переменные со знаком инверсии. Допустим, что это не так, то есть что в СДНФ существует полная правильная элементарная конъюнкция К₁, содержащая хотя бы одну переменную с инверсией.

Поскольку функция монотонна, в СДНФ найдётся другое слагаемое К₂, которое отличается от К₁ лишь тем, что переменная, входящая в К₁ с инверсией, входит в К₂ без инверсии.

Используя формулы равносильных преобразований, можно получить ДНФ, в которой отсутствует одна переменная, входящая в СДНФ с инверсией (см. пример 30).

Точно так же можно поступить и с другими слагаемыми и переменными, входящими в них со знаком инверсии. Так получится СДНФ, в которой нет ни одной полной правильной элементарной конъюнкции, содержащей хотя бы одну переменную с инверсией. Полученное противоречие с допущением доказывает утверждение. O

Доказательство достаточности. Пусть теперь функция может быть представлена в виде ДНФ, в которую переменные входят без знака инверсии. Мы убедились, что константы 0 и 1, дизъюнкция и конъюнкция монотонны (см. примеры 20 - 22), а функция инверсии - немонотонна (см. пример 23). ДНФ состоит из дизъюнкции элементарных конъюнкций, то есть представляет собой суперпозицию монотонных функций. Следовательно, в силу теоремы о замкнутости класса монотонных функций, функция, представленная в виде ДНФ без инверсий, будет монотонной. O

Пример 31. Конъюнкция любого числа переменных - монотонная функция.

Пример 32. СДНФ функции x+y имеет вид x'yxy'. Эту формулу невозможно преобразовать так, чтобы избавиться от вхождения переменных с инверсиями, поскольку среди двух слагаемых К₁=x'y и К₂=xy' нет такого, которое отличалось бы одно от другого лишь тем, что переменная, входящая в К₁ с инверсией, входила бы в К₂ без инверсии. Значит, функция x+y немонотонна, в чём мы уже убедились в примере 26. O

Пример 33. Пусть дана функция f(x,y,z)=(xy+x)xz. Будет ли она монотонной? Представим эту функцию в виде ДНФ. Займёмся сначала частью формулы, заключённой в скобки. Учитывая, что y+1=y', получим xy+x=x(y+1) = xy'. Вернёмся теперь к данной формуле и обозначим б=xy' и в=xz. Зная, что бв= (бв)', получим:

для бв : xy'xz=x(y'z),

для бв : (x(y'z))'= x'(y'z)' = x'yz'.

Видим, что формула представлена как ДНФ с переменными, входящими с инверсией, от которых нельзя избавиться. Значит, f(x,y,z)=(xy+x)xz - немонотонная функция.

Заметим, кстати, что эта f(x,y,z) представляется суперпозицией немонотонных функций + и , и, следовательно, немонотонна.O

5.5 Задания для самостоятельной работы

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

1	x( xy)	7	(xy)(x'y')
2	x( yx)	8	(0110)
3	xy(xy)	9	(0110 0111)
4	xyz'	10	(1001 0110)
5	xyz(xyz)'	11	(0001 0111)
6	(xy)' x'y	12	xy yz zx x

5.6 О мощности класса монотонных функций

Для количества монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но формулу для точного числа |M| вроде тех, которые имеются для других замкнутых классов, до сих пор получить не удаётся.

6. Критериальная таблица для некоторых булевых функций

Построим таблицу, в которой строки сопоставлены элементарным булевым функциям, а столбцы - замкнутым классам. Знаком плюс отметим принадлежность функции соответствующему классу, знаком минус - непринадлежность. Такого рода таблицу часто называют критериальной, поскольку она полезна для выяснения, какие функции могут образовать функционально полные системы. Обратите внимание, что тождественная функция x принадлежит всем замкнутым классам, а стрелка Пирса и штрих Шеффера не принадлежат ни одному.

Замечание. Интересен вопрос: сколько всего замкнутых классов булевых функций существует? Можно ли перечислить все замкнутые классы? Американский логик и математик Эмиль Леон Пост установил, что количество замкнутых классов булевых функций бесконечно, но имеется эффективная процедура перечисления всех замкнутых классов [9].

После того, как мы познакомились с пятью множествами (T⁰, T¹, L, S и M) булевых функций, обладающими свойством замкнутости, пора узнать, какова их роль в ответе на один из главных вопросов алгебры логики (см. раздел 1.1):

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

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

Нам известно достаточное условие (см. раздел 1.2) того, что некая система булевых функций является ФПС. Познакомимся с необходимыми и достаточными условиями для ФПС, сформулированными Эмилем Леоном Постом.

7. Критерий Поста для функционально полных систем

7.1 Необходимые и достаточные условия для ФПС

Теорема Поста. Для того чтобы система булевых функций была функционально полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из замкнутых классов T⁰, T¹, L, M и S.

Иначе говоря, система булевых функций является ФПС тогда и только тогда, когда в ней содержится:

§ хотя бы одна функция, не сохраняющая константу 0,

§ хотя бы одну функция, не сохраняющая константу 1,

§ хотя бы одна нелинейная функция,

§ хотя бы одна несамодвойственная функция и

§ хотя бы одна немонотонная функция.

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

Пример 34. Посмотрим, будет ли полна система {xy, x+1}. Критериальная таблица для этой системы будет выглядеть так:

	T0	T1	L	S	M
xy	+	+	-	-	+
x+1	-	-	+	+	-

Видим, что в каждом столбце имеется знак минус. Вывод: указанная система является ФПС.

Замечание. Этот вывод не так уж неожидан. Ведь если учесть, что x+1=x', то станет очевидно, что речь идёт о рассмотренной (в разделе 1.2) функционально полной системе ₁=,. O

Пример 35 . Выяснить, будет ли полной система булевых функций

{ f = xy, M¹_g = {0,7}, h=(0111 1111) }.

Нам предстоит построить критериальную таблицу, поэтому проведём исследование данных функций на принадлежность классам T⁰, T¹, S, L, M. Прежде всего, обратим внимание на то, как представлены функции:

· функция f(x,y) задана формулой,

· функция g(x,y,z) задана характеристическим множеством

M¹_g = {б Вⁿ : f(б)=1},

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

У нас g(0,0,0) = g(1,1,1) = 1. Ясно, что g(x,y,z) T⁰ и g(x,y,z)T¹ ,

· функция h(x,y,z) задана вектором своих значений.

Как и для f(x,y), по этому вектору легко определить, что

h(x,y,z) T⁰ и h(x,y,z) T¹ .

Про функцию f(x,y) = xy мы уже знаем (см. раздел 8), что

f(x,y) T⁰ , f(x,y) T¹, f(x,y) L , f(x,y) S , f(x,y) M.

Для исследования функций g(x,y,z) и h(x,y,z) на монотонность и самодвойственность построим таблицу истинности:

Займёмся сначала самодвойственностью этих функций. Необходимое и достаточное условия самодвойственности (раздел 6.1) не выполняется ни для g, ни для h, то есть на противоположных наборах у функций одинаковые значения вместо различных:

g(0,0,0) = g(1,1,1), g(0,0,1) = g(1,1,0),

h(0,0,0) ? h(1,1,1), но h(0,0,1) = h(1,1,0), h(0,1,0) = h(1,0,1).

Проверим также достаточное условие несамодвойственности. Оно выполняется для обеих функций: несовпадение количества нулей и единиц в векторе значений функций очевидно. Значит, g(x,y,z) S , h(x,y,z) S.

Теперь посмотрим свойство монотонности, сравнивая половинки векторов значений функций, четвертинки и так далее (раздел 7.2). Для g(x,y,z) нарушено условие

ц₂ = (1000) (0001) = ш₂.

Поэтому g(x,y,z) M.

Для h(x,y,z) сравнение показывает следующее:

ц₂ = (0111) (1111) = ш₂ ,

ц₄₁ = (01) (11) = ш₄₁, ц₄₂ = (11) (11) = ш₄₂.

Для осьмушек также очевидно выполнение аналогичных условий. Значит, h(x,y,z) M .

Чтобы узнать о линейности наших функций, представим их полиномами Жегалкина, заметив, что такое представление единственно. Для g(x,y,z) воспользуемся треугольником Паскаля, а для h(x,y,z), чтобы не повторяться, применим метод неопределённых коэффициентов. Итак, строим треугольник Паскаля для g(x,y,z).

Левые единицы треугольника Паскаля подсказывают вид полинома Жегалкина:

g(x,y,z) = 1 + z + y + yz + x + xz + xy. Значит, g(x,y,z) L

По таблице истинности функции h(х,y,z), найдём коэффициенты полинома Жегалкина:

h(х, y, z) = ₀+₁х+₂y+₃z+₁₂xy+₁₃хz+₂₃yz+₁₂₃хyz

h(0,0,0) = 0 = ₀. ₀=0.

h(0,0,1) = 1 = ₀ + ₃ = 0 + ₃. ₃=1.

h(0,1,0) = 1 = ₂ . ₂=1.

h(0,1,1) = 1 = ₂₃ + ₂ +₃ = ₂₃ +1+1. ₂₃=1.

h(1,0,0) = 1 = _{1. 1}=1.

h(1,0,1) = 1 = ₁+₃+₁₃ = 1+ 1+₁₃. ₁₃=1.

h(1,1,0) = 1 = ₁+₂+₁₂=1+ 1+₁₂. ₁₂=1.

h(1,1,1) = 1 =₁+₂+₃+₁₂+₁₃+₂₃+₃₃ =

=1+1+1 + 1 + 1 + 1+₃₃. ₃₃=1.

Используя полученные значения коэффициентов при неизвестных, напишем полином Жегалкина:

h(х,y,z) = х + y + z + xy + хz + yz + хyz .

Видно, что h(x,y,z) L.

Теперь у нас есть все сведения, чтобы заполнить критериальную таблицу.

Мы видим, что все функции исследуемой системы входят в класс T¹ - в соответствующем столбце критериальной таблицы нет ни одного минуса. Поскольку условия теоремы Поста не выполняются, делаем вывод: данная система булевых функций не является ФПС. O

Замечание 1. Вычисления коэффициентов можно было бы прекратить, как только нашли коэффициент ₂₃=1 при конъюнкции yz - стало ясно, что h(x,y,z) L. Но всё же интересно было найти представление этой функции полиномом Жегалкина.

Замечание 2. Если к исследованной в этом примере системе добавить какую-нибудь функцию, которая принесёт «-» в столбец T¹ (например, из множества T⁰), то полученная новая система станет функционально полной. f = xy, M¹_g = {0,7}, h=(0111 1111)

7.2 Задания для самостоятельной работы

Выяснить, будет ли полной система булевых функций

1	f1=xy, f2=xy, f3=xy, f4=xyyzzx
2	Mf0={0,1,2}, g=(0111), h=xy, t=yz1
3	f1=xy(xy), f2=xyxy, f3=1, f4=xy yz zx
4	f=xy, Mg0={00,11}
5	f=xy yz zx x, Mg1={0,1,3}, h= (0110)
6	f=(0110), g=(1100 0011), Mh1={0,3,5,6}
7	f= x y z, g=(1,1), Mh0={10}, t=x'xy'

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

7.3 Свойства функций, не входящих в классы T⁰, M, S, L

Лемма о функции, не сохраняющей константу 0. Если булева функция не сохраняет константу 0, то из неё подстановкой вместо каждого аргумента переменной x можно получить либо константу 1, либо инверсию x'.

Доказательство. Пусть f(x₁, x₂, …, x_n)T⁰ - функция, не сохраняющая константу 0. Заменим каждый её аргумент на x и получим функцию, зависящую от одного аргумента g(x)=f (x ,…, x). Посмотрим, какие значения может принимать эта функция при x=0 и x=1:

Случай x=0: g(0)=f (0,…,0)=1, поскольку f(x₁, x₂, …, x_n)T⁰.

Случай x=1 может иметь два варианта:

§ g(1)=1. Поскольку g(0)=g(1)=1, ясно, что g(x) - константа 1.

§ g(1)=0. Это значит, что g(x) = x'. O

Пример 36. Функция эквивалентности a b , как выяснили в разделе 2, не сохраняет константу 0. Подставим вместо аргументов переменную x и получим: xx = 1.

Пример 37. Функция штрих Шеффера a | b тоже не сохраняет константу 0. Подставляя вместо a и b переменную x, будем иметь g(x)= x | x. Поэтому g(0)=0|0 = 1 и g(1)=1|1 = 0. Следовательно, x | x = x'.

Лемма о немонотонной функции. Если функция немонотонна, то из неё подстановкой констант 0, 1 и переменной x вместо некоторых переменных можно получить инверсию x'.

Доказательство. Сначала условимся называть соседними по координате k такие два булевых вектора одинаковой длины, у которых k-я компонента в одном векторе равна 1, а в другом - 0, а все другие компоненты векторов совпадают.

Пусть дана функция f(x₁, x₂, …, x_n)M. Поскольку она немонотонная, найдутся два таких вектора и , для которых бв и f()>f(), то есть f()=1, f()=0.

Очевидно, что среди таких векторов найдутся и соседние, и пусть они являются соседними по k-й компоненте, так что _k =0, _k =1, а все остальные компоненты совпадают.

Рассмотрим функцию g(x)= f(₁, … , _k-1, x , _k+1, …, _n) и покажем, что g(x)=x'. Мы имеем:

g(0) = f(₁, …,_k-1, 0, _k+1, …, _n) = {учтём, что 0 = _k }=

= f(₁, …,_k-1, _k, _k+1, …, _n) = f()=1.

g(1) = f(₁, …,_k-1, 1, _k+1, …, _n) = {учтём, что 1 = _k }=

= f(₁, …,_k-1, _k, _k+1, …, _n) = f()=0.

Так как g(0)=1, g(1)=0, то g(x)=x'. O

Пример 38. Рассмотрим стрелку Пирса f(y,z)=yz. Эта функция немонотонна (см. пример 29), так что найдём векторы =(00) и =(10), которые оказываются соседними по 1-й компоненте, то есть

бв и f(0.0)=1 > 0=f(1,0).

Построим функцию g(x) так: вместо 1-й переменной y подставим x, а вместо z - константу 0. Получим инверсию переменной x:

g(x) = f(x, 0) = x0 = (x 0)' = x'.

Пример 39. Возьмём функцию f(x,y,z)=(xy+x)xz = x'yz', о которой в примере 33 узнали, что она немонотонна. Вектор её значений выглядит так: (1111 0010). Соседними по 3-й компоненте оказываются векторы

=(110) и =(111).

Видно, что бв, причём f(1,1,0)=1 > 0=f(1,1,1).

Поскольку ₁=₁=₂=₂=1, сформируем g(x) так: вместо переменных x и y подставим 1, а вместо переменной z подставим x :

g(x) = f(1, 1, x) = 1' 1&x' = x'.

В результате получили инверсию переменной x, что и утверждается в лемме о немонотонной функции.

Лемма о несамодвойственной функции. Если функция несамодвойственна, то из неё подстановкой вместо аргументов переменной x и её инверсии x' можно получить константу 0 или 1.

Доказательство. Пусть f(x₁,…,x_n)S. Тогда найдётся такая пара противоположных наборов (₁,…, _n) и (₁',…,_n'), что

f(₁,…,_n)= f(₁',…,_n'). (*)

Заменим в f(x₁, …, x_n) переменную x_j на , j=1,…, n, то есть на функцию x, если _j =1, и на функцию x', если _j = 0. Полученную таким образом функцию одного аргумента обозначим через g(x). Она может быть представлена так:

Заметим, кстати, что

x¹=x, x⁰=x', 0⁰ = 0' = 1 = 1¹ , 0¹ = 1⁰ = 1' =0, 0 = ' , 1 = .

Покажем, что g(x) является константой, вычислив g(0) и g(1).

Имеем

,

.

Однако набор (₁,…,_n) выбран так, чтобы выполнялось равенство (*). Но тогда g(0)=g(1), что возможно лишь при условии, когда g(x)=Const. O

Пример 40. Проиллюстрируем приведённое доказательство функцией

f(x, y, z) = xy' x'z y'z'.

Она несамодвойственна, потому что удовлетворяет достаточному условию несамодвойственности (см. раздел 6.1): в векторе её значений, как видно их таблицы истинности, количество единиц (= 5) не совпадает с количеством нулей (= 3). Видно также, что на двух противоположных наборах (011) и (100) функция принимает равные значения:

f(0,1,1)=f(1,0,0)=1.

Функция g(x) будет выглядеть так:

g(x)=f(x⁰, x¹, x¹) = f (x', x, x) =x'x'xxx'x'=1.

Так убедились, что подстановка x и x' вместо аргументов несамодвойственной функции превращает функцию в константу. O

Лемма о нелинейной функции. Если функция нелинейная, то из неё подстановкой вместо аргументов констант 0, 1, переменных x, y, их инверсий x' и y' и, возможно, инверсией самой функции можно получить конъюнкцию xy.

Доказательство. Рассмотрим полином Жегалкина нелинейной функции f(x₁,…,x_n). Поскольку он нелинейный, в нём найдётся член, содержащий конъюнкцию не менее двух переменных. Не уменьшая общности, будем предполагать, что этими переменными являются переменные x₁ и x₂.

Разделим все конъюнкции полинома на четыре группы:

1. конъюнкции, содержащие x₁ и x₂,

2. конъюнкции, содержащие x₁ и не содержащие x₂,

3. конъюнкции, содержащие x₂ и не содержащие x₁,

4. остальные конъюнкции.

В первых трёх группах вынесем за скобки соответственно x₁x₂, x₁, x₂. Тогда полином Жегалкина примет вид:

f(x₁,…,x_n)=x₁x₂f₁(x₃,…,x_n) + x₁f₂(x₃,…,x_n) + x₂f₃(x₃,…,x_n) + f₄(x₃,…,x_n).

Здесь f₁(x₃,…,x_n) 0, поскольку f(x₁,…,x_n)L. Значит, найдётся хотя бы один набор (₃,…,_n), на котором значение этой функции не равно 0, то есть f₁(₃,…,_n)=1. По условию леммы можно эту константу 1 подставить в функцию f(x₁,…,x_n):

f(x₁,x₂,₃,…,_n)=x₁x₂ + x₁f₂(₃,…,_n) + x₂f₃(₃, …, _n) + f₄(₃, …, _n) =

= x₁x₂ + ax₁ + bx₂ + c ,

где a, b, c - булевы константы.

Если a=b=c=0, то конъюнкция получена - лемма доказана.

Но пусть это не так - рассмотрим другой случай. По условию леммы допустима подстановка переменных x, y, x'=x+1, y'=y+1. Положим в последней формуле x₁=x+b, x₂=y+a, раскроем скобки и удалим пары одинаковых конъюнкций (они подчёркнуты). Получим функцию, зависящую от x и y:

g(x,y) = (x+b)(y+a)+a(x+b)+b(y+a)+c =

= xy+by+ax+ab+ax+ab+by+ab+c =

= xy+ab+c = xy + d.

Здесь, как легко догадаться, d=ab+c. Если d=0, лемма доказана. Если же d=1, то g(x,y)= xy+1 и свидетельствует о том, что g(x,y)=(xy). По условию леммы можно инвертировать исходную функцию, что мы и сделаем, получив конъюнкцию xy. O

Пример 41. Проиллюстрируем приведённое доказательство функцией, про которую в примере 3 узнали, что она нелинейная В примере 3 функция имела вид xyz. В примере 41 аргументы функции переименованы специально. :

f(x₁,x₂,x₃)= x₁ x₂x₃ = x₁x₂x₃+x₁+1.

В соответствии с приведённым выше доказательством подставим в наш полином Жегалкина f₁(x₃) = x₃=1. Получим

f(x₁,x₂,1)= x₁x₂+x₁+1 = g(x₁,x₂).

Учитывая обозначения, используемые в доказательстве, положим a=1, b=0, c=1 и сделаем замену x₁=x+b=x, x₂=y+a=y+1.

Получим

g(x,y) = x(y+1)+x+1 = xy+x+x+1=xy+1.

Инверсия функции g(x,y) приведёт к конъюнкции xy. O

Теперь, надеюсь, мы готовы к доказательству теоремы Поста.

7.4.Доказательство теоремы Поста

Необходимость. Известно, что система - ФПС. Надо доказать, что множество не содержится целиком ни в одном из пяти замкнутых классов.

Докажем сначала, что содержит хотя бы одну монотонную функцию. Допустим, что это не так, и в все функции монотонные. Так как класс монотонных функций замкнут, то любая суперпозиция монотонных функций является монотонной, и никакая монотонная функция не может быть представлена такой суперпозицией. Но ведь, по условию, - ФПС, и в соответствии с определением ФПС, через функции, входящие в , можно выразить любую функцию. Однако, если монотонную функцию нельзя выразить через , значит, не является ФПС. Получили противоречие. Выходит, что в должна быть хотя бы одна немонотонная функция.

Аналогично можно доказать, что содержит

· хотя бы одну функцию, которая не входит в Т⁰,

· хотя бы одну функцию, которая не входит в Т¹,

· хотя бы одну функцию, которая не входит в L и

· хотя бы одну функцию, которая не входит в S.

Так доказали, что множество не содержится целиком ни в одном из пяти замкнутых классов T⁰, T¹ , L, S и M. O

Достаточность. Пусть имеется множество , которое не содержится целиком ни в одном из пяти замкнутых классов. Требуется доказать, что - ФПС.

Рассмотрим два множества функций: ₁=, и - заданное множество. Множество ₁ является ФПС, как было показано в разделе 1.2, а будет ФПС, если каждая функция из ₁ может быть представлена суперпозицией функций из (см. лемму о достаточном условии полноты в разделе 1.2).

Покажем, что конъюнкцию и инверсию (функции системы ₁ ) можно выразить через функции, не входящие в классы T⁰, T¹, L, S и M.

Введем следующие обозначения для функций множества :

f⁰ T⁰ - функция, не сохраняющая константу 0;

f¹ T¹ - функция, не сохраняющая константу 1;

f_M M - немонотонная функция,

f_S S - несамодвойственная функция,

f_L L - нелинейная функция.

Используем леммы Здесь уместно вспомнить персонажей сказки о репке: деда, бабку, внучку и Жучку. Кошке и мышке лемм не досталось. предыдущего раздела, чтобы функции системы ₁=, выразить через функции системы

= { f ⁰ , f¹, f_M, f_S, f_L }.

Схема Эту схему, опубликованную в [1], разрешила в 2006 г. мне использовать одна из авторов - Быкова С.В., моя томская коллега. В приведённом здесь рисунке по сравнению с оригиналом изменены обозначения. , изображённая на рисунке 2, способствует пониманию плана доказательства.

Рисунок 2 - Схема доказательства достаточности условий Поста

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

Начнем с функции f⁰T⁰. По лемме о функции, не сохраняющей константу 0, подстановкой вместо аргументов переменной x получим один из двух вариантов:

а) константу 1,

б) инверсию x'.

Проанализируем случай (а). Имея константу 1 и подставляя её вместо каждого аргумента функции f¹T¹, получим константу 0. Затем по лемме о немонотонной функции, подставляя в функцию f_M M вместо аргументов полученные константы 0, 1 и переменную x, получим инверсию x'. Итак, случай (а) привёл к тому, что инверсия выражена суперпозицией функций f⁰, f¹ и f_M .

Теперь рассмотрим случай (б), когда из функции f⁰ получена инверсия x (нижняя ветка рисунка 2). По лемме о несамодвойственной функции, подставляя в f_SS вместо аргументов переменную x и ее инверсию x, получим тоже один из двух вариантов:

(в) константу 0 ( средняя ветка рисунка 2),

(г) константу 1 ( нижняя ветка рисунка 2).

Если имеем случай (в), то, подставляя константу 0 вместо каждого аргумента функции f⁰ , получим, как и в случае (а), константу 1.

Если имеем случай (г), то, подставляя вместо каждого аргумента функции f¹ константу 1, получим константу 0.

Итак, к этому моменту у нас есть инверсия x , константы 0 и 1. Остаётся применить лемму о нелинейной функции: подставляя в функцию f_LL константы 0 и 1, тождественные функции x и y, их инверсии x и y, и, возможно, инвертировав после этого саму функцию f_L, можно получить конъюнкцию x&y.

Вывод: конъюнкция и инверсия представимы суперпозицией функций из . Значит, - ФПС. O

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

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

8. Знаменитые логики-математики

8.1. Джордж БУЛЬ

БУЛЬ Джордж (2.11.1815, Линкольн, ? 8.12.1864, Баллинтемпл близ Корка), родился и вырос в семье небогатого ремесленника Джона Буля, увлечённого наукой. Отец, интересуясь математикой и логикой, дал первые уроки своему сыну, но тот не сумел обнаружить рано свои выдающиеся таланты в точных науках, и его первым увлечением стали классические авторы. Лишь к семнадцати годам Буль дошёл до высшей математики, продвигаясь медленно из-за отсутствия действенной помощи.

С шестнадцати лет Дж.Буль начал работать помощником учителя в частной школе в Донкастере и, так или иначе, продолжал преподавание на разных должностях в течение всей жизни. Он был женат (с 1855 г.) на Мэри Эверест, племяннице знаменитого географа Джорджа Эвереста. Мэри Эверест-Буль также занималась научными исследованиями и вела занятия в школе, а после смерти мужа много сил уделяла популяризации его вклада в логику.

Четыре их дочери снискали известность как учёные (геометр Алисия, химик Люси) или члены семей учёных (Мэри, жена математика и писателя Ч.Г. Хинтона, и Маргарет, мать математика Дж. И. Тейлора), а пятая --Этель Лилиан Войнич -- прославилась как писатель. [14].

Хотя мальчик посещал местную школу, его можно считать самоучкой. В 12 лет знал латынь, затем овладел греческим, французским, немецким и итальянским языками. В 16 лет уже преподавал в деревенской школе, а в 20 открыл собственную школу в Линкольне. В редкие часы досуга зачитывался математическими журналами Механического института, интересовался работами математиков прошлого - Ньютона, Лапласа, Лагранжа, проблемами современной алгебры….

В своей работе «Законы мышления» (1854 г.) Дж.Буль окончательно сформулировал основы математической логики. Он также попытался сформулировать общий метод вероятностей, с помощью которого из заданной системы вероятных событий можно было бы определить вероятность последующего события, логически связанного с ними.

В 1857 году Дж.Буль был избран членом Лондонского Королевского общества. Его работы «Трактат о дифференциальных уравнениях» (1859 г.) и «Трактат о вычислении предельных разностей» (1860 г.) оказали колоссальное влияние на развитие математики. В них нашли свое отражение наиболее важные открытия Дж.Буля. Сегодня идеи Буля используются во всех современных цифровых устройствах [15]. Джордж Буль умер на пятидесятом году жизни от воспаления лёгких.

8.2.Огастес де МОРГАН

По происхождению шотландец, Огастес (Август) де МОРГАН (De Morgan Augustus) родился в июне 1806 г. в Индии, в округе Мадрас. Обучался математике в Тринити Колледже в Кембридже. В 1828 г. Морган становится профессором математики при только что открывшемся Лондонском университетском колледже, который является ныне частью лондонского университета. Профессура Моргана падает на время с 1828 по 1831 г. и с 1836 по 1866 г. Видный педагог и страстный библиограф, он с 1847 г. выполнял также обязанности секретаря королевского астрономического общества и, кроме того, явился основателем и первым президентом (1866) Лондонского математического общества. А. Морган известен и как отец Уильяма Френда Моргана (1839--1917) -- английского писателя, артиста и изобретателя. Любопытно отметить, что в числе учеников А. де Моргана была дочь Байрона леди Августа Лавлейс, автор пространных комментариев к итальянскому описанию универсальной вычислительной машины Чарльза Бэббиджа.

Морган выступил инициатором применения логических исчислений к обоснованию теорем теории вероятностей, предварив аналогичное стремление Дж. Буля. На этом пути Морган хотел продемонстрировать работоспособность своего исчисления, понятия которого он, прежде всего, переводит” на теоретико-вероятностный язык. Например, понятие относительного произведения отношений ставится им в параллель с понятием условной вероятности.

Важное место в логических исследованиях де Моргана занимает также изучение выводов из количественно определяемых предложений, не укладывающихся в силлогистические рамки. Такие выводы анализируются Морганом вслед за И. Ламбертом.

Моргану принадлежит также идея трактовки отрицания понятия как дополнения до существующего “универсума рассуждения” (аналог современного понятия об универсальном классе). Это последнее понятие стало играть в дальнейшем столь важную роль в логических системах Дж. Буля и П. С. Порецкого. Дополнение к данному классу рассматривается им как совокупность предметов, не содержащихся в этом классе, но отграниченных вместе с последними рамками определенного универсального класса, выделяемого (посредством внелогических критериев) обычно для системы понятий некоторой научной дисциплины или ее отдельного фрагмента.

Работы де Моргана не были в достаточной степени поняты его современниками. Сложная и не всегда единообразная символика отпугивала многих читателей, склонных прагматически требовать от новой теории немедленных практических приложений. Основное историческое значение системы де Моргана сводится главным образом к тому, что она стимулировала развитие алгебры отношений Ч. С. Пирса и дала толчок Дж. Булю к созданию исчисления классов, которое у де Моргана было представлено явно недостаточно [16].

Умер Огастес де МОРГАН 8 марта 1871 года в Лондоне.

8.3 Чарльз Сандерс ПИРС

ПИРС Чарльз Сандерс (Charles Sanders Peirce) (10 сентября 1839, Кембридж, Массачусетс -- 19 апреля 1914, близ Милфорда, Пенсильвания) -- американский философ, логик, математик и естествоиспытатель. Родоначальник прагматизма, Пирс выдвинул принцип, согласно которому содержание понятия целиком исчерпывается представлением о его возможных последствиях. Основатель семиотики, автор работ по математической логике. Сын Бенджамина Пирса, профессора астрономии и математики Гарвардского университета.

В 1859 году Чарльз Пирс окончил Гарвард-колледж, а в 1863 -- с отличием Научную школу Гарвардского университета, где изучал математику и физику. С 1861 года он работал в Береговой и геодезической службе США.

Занимаясь профессионально главным образом астрономическими и геодезическими исследованиями, увлекся также философией и логикой. В 1869--1872 годах в Гарварде, Балтиморе и Бостоне читал лекции по логике, истории и философии науки

В 1871 при активном участии Пирса был создан Метафизический клуб, объединивший математиков, естествоиспытателей, юристов, теологов.

В 1869 - 1875 годах Пирс работал ассистентом в Гарвардской обсерватории. В 1877 г. за свои научные исследования был избран членом Американской академии искусств и наук в Бостоне, а в 1879 г. стал членом Национальной академии наук США. Тогда же он получил приглашение преподавать логику в университет Джона Хопкинса. В 1884--1911 г.г. читал отдельные лекционные курсы как приглашенный профессор Гарвардского университета. После получения небольшого наследства в 1891 г. Пирс вышел в отставку из Береговой и геодезической службы. Последние годы жизни провел в бедности и забвении.

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

В ноябре 1877 г. и январе 1878 г. в журнале «Ежемесячник популярной науки» вышли в свет две программные статьи Пирса: «Закрепление верования» и «Как сделать наши идеи ясными». Они и стали истоком прагматистского направления в философии. Именно здесь Пирс ввёл сам термин «прагматизм» (по-гречески означает «дело» или «действие») и сформулировал свой знаменитый принцип.

Многие идеи Пирса до сих пор используются современными логиками. Введение им многоместных предикатов значительно расширило логику отношений, а предложенные им модификации булевой алгебры, объединяющие ее с логикой де Моргана и теорией вероятностей, использованы Э. Шредером (алгебра логики Буля--Шредера). Интерес Пирса к умозаключениям позволил ему обнаружить факты, которые позднее назовут «парадоксами материальной импликации», а внимание к знакам -- предположить, что неправильная их трактовка приводит ко многим философским ошибкам. Этот тезис был позднее развит логическими позитивистами и философами [17].

8.4 Генри Морис ШЕФФЕР

ШЕФФЕР Генри Морис, американский логик-математик, родился в Украине в 1882 году в семье польских евреев. В 1892 году родители вместе с ним уехали в США. Высшее образование Генри Морис получил в Гарвардском университете, где изучал логику под научным руководством Джосайя Ройса. Университет закончил в 1905 году и получил степень магистра в 1907 году. В 1908 году он защитил диссертацию на степень PhD (доктора философии) и на специальную стипендию поехал в Европу. После возвращения в США он по одному году проработал в Сити-колледже Нью-Йорка, в университетах Миннесоты, Миссури, Корнеля, а также в университете штата Вашингтон. В 1916 году его пригласили на факультет философии Гарвардского университета, где он проработал 36 лет до выхода на пенсию в 1952 году.

Шеффер очень любил преподавать математическую логику. Ему нравились занятия в классах с небольшим количеством студентов. Шеффер был ростом 5 футов 5 футов 152 см. (1 фут = 0.3048 м.) и был известен не только своей бодростью и остроумием, но раздражительностью и нервозностью. Например, он не любил, когда в классе появлялись незнакомые люди, и мог приказать им уйти.

Шеффер был женат и жил в небольшой комнатке, заполненной книгами по логике и толстыми папками бумаг с записями своих идей. В последние 20 лет жизни он страдал от тяжёлой депрессии. Ему очень нравилось где-нибудь побыть одному.

В 1913 году Г.М. Шеффер определил булеву алгебру с помощью единственной бинарной операции NAND (НЕ-И). Исчисление высказываний могло быть сформулировано посредством одной истинностной таблицы, описывающей так называемый Штрих Шеффера, который обозначается вертикальной линией. Эти факты были также обнаружены Чарльзом Пирсом в 1880 году, но соответствующая статья им не была опубликована вплоть до 1933 года.

Г.М.Шеффер был малоизвестным среди логиков, поскольку почти не публиковал своих исследований. Он почти всегда описывал их где-нибудь в заметках или в кратких рефератах вместо того, чтобы сделать подробную публикацию. Штрих Шеффера, как говорилось, был им открыт в 1913 году, но стал широко известным лишь в 1925 году благодаря книге Б. Рассела «Начала математики» («Principia Mathematica»). Бертран Рассел высоко оценил открытие Шеффера. Оно позволило ему упростить изложение своей логики во втором издании этой книги. «Математическая логика» Уилларда ван Ормана Куайна была также во многом основана на Штрихе Шеффера [18]. Умер Генри Морис Шеффер в 1964 году.

8.5 Стивен Коул КЛИНИ

КЛИНИ Стивен (Стефан) Сам Клини произносил свою фамилию как Клейни. Ошибочная транслитерация Клини утвердилась в Советском Союзе в связи с изданием переводов его книг именно под такой фамилией. Имя Stephen часто читается как Стефен или Стефан. Коул (Stephen Cole Kleene) родился: 5 января 1909 в Хартфорде, штат Коннектикут, США. Его отец Густав Адольф Клини - профессор экономики в Тринити-колледже, Хартфорд, штат Коннектикут. Мать Стефана - Алиса Лена Коул - поэт и автор нескольких пьес.

Стивен Клини учился Амхерст-колледже, Амхерст, штат Массачусетс, где получил степень бакалавра с отличием в 1930 году. Он был очарован математикой и потому поступил в Принстонский университет. В эти годы университетский математик Освальд Веблен продвигал свою идею: развитие логики требует тщательного анализа математиками. По совету Веблена его ученик Алонзо Чёрч начал разрабатывать своё «лямбда-исчисление».

В 1934 году в Принстон приехал Курт Гёдель, который стал широко известен после того, как в 1932 году в Вене доложил свою знаменитую теорему о неполноте. Гёдель рассказал о своих работах в Принстонском институте перспективных исследований. Прослушав лекции Гёделя, А.Чёрч предположил, что можно использовать своё «лямбда-исчисление» для выяснения вычислимости функций. Это предположение исследовал С.Клини, рассмотрев более общие рекурсивные функции, используемые Гёделем. Защитив в 1934 году на эту тему диссертацию, Клини получил степень доктора философии.

Большая часть его последующей работы была посвящена систематическому изучению этого класса рекурсивных функций, о чём он написал в 1952 году в великолепной книге «Введение в метаматематику». Его работы совместно с работами А. Чёрча, К. Гёделя и А. Тьюринга дали начало разделу математической логики -- теории вычислимости. Клини известен также изобретением так называемых регулярных выражений. Его именем названы Алгебра Клини, Звёздочка Клини, теорема Клини о рекурсии, теорема Клини о неподвижной точке. Он внёс важный вклад в теорию конечных автоматов. Работал также в области интуиционистсткой математики. Введённое им понятие (рекурсивной) реализуемости формул лежит в основе интуиционистской интерпретации арифметических суждений.

С.К.Клини работал в Принстоне до 1935 года, потом переехал в г. Мэдисон преподавать математику в Висконсинский университет перспективных исследований. В 1941 году он вернулся доцентом в свою альма-матер, в Амхерст-колледж. В этом колледже работал Джордж Рой Эллиотт - профессор английского языка и литературный критик. Его любимой темой было творчество Шекспира. Стивен познакомился с дочерью профессора Нэнси Элиот и через год женился на ней . У Стивена и Нэнси было четверо детей.

В том же 1942 году Стивен поступил лейтенантом в Школу морского резерва ВМФ США в Нью-Йорке в качестве навигационного инструктора. Позже он был директором проекта в Военно-морской исследовательской лаборатории в Вашингтоне.