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

Работа из раздела: «Математика»

/

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Набережночелнинский институт

Казанского (Приволжского) федерального университета

М.Я. Товштейн

Набережные Челны

2014

УДК 519.95(075.8)

ББК 22.12я73

Т 50

Печатается по решению редакционно-издательского совета Набережночелнинского института Казанского (Приволжского) федерального университета от 25.04.14

Рецензенты: А.Ю. Матросова, доктор техн. наук, профессор, зав.кафедрой программирования Национального Исследовательского Томского госуниверситета,

Р.А.Валиев, к.ф.-м.наук, доцент, зав.кафедрой информационных систем Набережночелнинского института Казанского

(Приволжского) федерального университета.

Т 50

Товштейн М.Я. ФУНКЦИОНАЛЬНО ПОЛНЫЕ

СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ. Учебное пособие /

М.Я. Товштейн - Издательско-полиграфич. центр

филиала ФГАОУ ВПО «Казанский(Приволжский)

федер. университет» в г. Наб.Челны, 2014. - 76 с. : ил.,

табл. - Библиогр.: 22 назв.

Булевы (логические) функции знакомы уже школьникам. Им нужно знать логические основы компьютера и пользоваться командами развилки и цикла при создании программ для компьютеров. Но детально эти функции изучаются в рамках вузовской дисциплины «Математическая логика». Тема, которая освещается в данном пособии, является теоретической базой для разработчиков дискретных управляющих устройств. Именно функционально полные системы булевых функций позволяют создавать те конструктивные элементы, из которых строятся сколь угодно сложные системы управления цифровыми автоматами. А без этих автоматов уже не представляется повседневная жизнь.

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

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

УДК 519.95(075.8)

ББК 22.12я73

© Набережночелнинский институт Казанского

(Приволжского) федерального университета, 2014

© Товштейн М. Я., 2014

Введение

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

Большая советская энциклопедия [12]

Данное пособие написано на основе занятий по математической логике, проводимых с 2005 года со студентами 2-го курса факультета Прикладной математики и информационных технологий филиала Казанского федерального университета в г. Набережные Челны С 2013 года это Набережночелнинский институт Казанского (Приволжского) федерального университета. (специальность 010501.65 «Прикладная математика и информатика»). Оно ни в коей мере не претендует на оригинальность и похоже на аналогичные пособия коллег из других вузов (например, [1-4]): ведь почти все мы пользуемся одними и теми же проверенными временем классическими учебниками и задачниками [5-11], а формулировки теорем и их доказательств не меняются.

Надо сказать, что долгое время у меня и в мыслях не было писать своё пособие на тему булевых функций: студентам достаточно было в дополнение к лекциям рекомендовать какие-либо из уже упомянутых источников. Но в 2013/2014 учебном году после занятий с группой 3-курсников я убедился в правоте коллег, которые говорили, что «ЕГЭизация» школьного и «бакалавризация» высшего образования внесли свои печальные коррективы в процесс усваивания студентами вузовской программы.

Пришлось учесть два обстоятельства. Во-первых, сникший математический уровень тех, кто не поехал в столицы, а поступил учиться к нам. Во-вторых, сокращенное количество часов аудиторных занятий в учебных планах бакалавров по сравнению с тем, которое было у студентов «специалитета». Это сокращение было сделано в предположении, что будущий бакалавр сможет сам получить недостающие знания из различных бумажных и/или интернет-источников.

Таким образом, ориентация на нынешних «ЕГЭшников-бакалавров» побудила написать эту брошюру. В ней подробнее, чем это делалось мною раньше, разъясняются доказательства теорем Некоторые их них предлагаются разобрать самостоятельно., приводятся большее количество примеров. Для самопроверки усвоенного материала и для проведения практических занятий в пособие включена подборка заданий Да и задания эти, честно сказать, не ахти какие трудные!.

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

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

Об этом идёт речь в следующих абзацах, заключённых между знаками «O». Разумеется, этот материал предназначен для конечного множества любознательных читателей. Тем, кто не входит в это множество, можно эти абзацы пропустить.

Чтобы показать, в чём смысл понятия полнота системы, приведу сначала статью из Большой советской энциклопедии [12]. Цитата довольно длинная (прошу извинить за это!), но примечательна двумя фактами. Во-первых, здесь объясняется, что такое функциональная полнота, а это как раз и ожидается от «Введения», во-вторых, в ней понятие функциональной полноты в математике сопоставляется с понятием функциональной полноты в естественном языке.

Итак, ещё раз читаем эпиграф и продолжаем дальше читать здесь «… английский язык функционально полон с точки зрения целей, которые имел в виду У. Шекспир, создавая «Гамлета» (если исходить из предположения, что ему удалось полностью реализовать свой замысел). Но и любой другой из «живых» языков, на который «Гамлет» переведён, полон в том же смысле: перевод как раз и служит свидетельством этой функциональной полноты.

Аналогично (в математике), семейство функций, принадлежащих некоторому классу функций, является полным относительно этого класса (и относительно некоторого фиксированного запаса «допустимых» операций над функциями), если любую функцию этого класса можно выразить через функции данного семейства (с помощью допустимых операций). Так, любая из функций sin x или cos x составляет одноэлементный класс, полный для всех тригонометрических функций (относительно четырёх арифметических действий, возведения в квадрат и извлечения квадратного корня); три единичных вектора по осям координат образуют полный класс (относительно сложения, вычитания и умножения на действительное число) для множества всех векторов трёхмерного евклидова пространства.

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

Философская энциклопедия понятие функциональной полноты поднимает на теоретико-познавательную высоту [13]: «…на вопрос “А хватит ли выбранного базиса для того, чтобы выразить всё, что нас интересует?” положительный ответ может быть дан только в форме доказательства функциональной полноты выбранного базиса относительно точно охарактеризованного класса “всего того, что нас интересует”. Таким образом, функциональная полнота - это полнота средств выражения, достаточности языка (для определённых целей)».

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

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

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

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

БУЛЬ Джордж, де МОРГАН Огастес,

ПОСТ Эмиль Леон, КЛИНИ Стефен Коул,

ШЕФФЕР Генри Морис, ПИРС Чарльз Сандерс,

ЖЕГАЛКИН Иван Иванович

1. О полноте и замкнутости системы булевых функций

булевой функция алгоритм полином

Система полна, если её постулаты дают уже всё, что нам нужно для некоторой цели.

Стефен Коул Клини Введение в метататематику, пер. с англ., М.: Иностр. лит.,1957

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

Формула - более компактный способ представления функции, однако она задаёт функцию через другие функции. Поэтому для любой системы функций возникает вопрос: всякая ли булева функция представима формулой над ?

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

Замечание 1. Здесь и далее в тексте наряду с символом , принятым для обозначения инверсии (отрицания), используется символ ' апострофа как более удобный при наборе текста. По этой же причине не применяется надчёркивание: например, вместо пишется х' , вместо пишется (x2 x3)'.

Замечание 2. Принято символ для обозначения конъюнкции иногда опускать. В этой брошюре традиция поддерживается.

1.1 О суперпозиции булевых функций

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

Определение. Пусть даны булевы функции

g(y₁,…,y_m), f₁(x₁,…,x_n), …, f_m(x₁,…,x_n).

Суперпозицией этих булевых функций будем называть функцию f(x₁,…,x_n), если она представима формулой

g ( f₁(x₁,…,x_n), .…, f_m(x₁,…,x_n) ).

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

Пример. Пусть даны следующие функции:

g(x,y,z)=xyx' z,

f₁(a,b)=ab, f₂(a,b,c)=aсb, f₃(a,b,c)=abc.

Полагая x=f₁(a,b), y=f₂(a,b,c) и z=f₃(a,b,c), внесём эти формулы в формулу, представляющую функцию g(x,y,z), и получим суперпозицию исходных функций:

f(a,b,c)=(ab)(aсb) (ab)' (abc).

Пояснение. Обратите внимание, что функции f₁, f₂, …, f_m в определении суперпозиции зависят от одинакового количества аргументов. В этом примере функция f₁ зависит от двух аргументов, f₂ и f₃ - от трёх аргументов, то есть количество аргументов у функций, чья суперпозиция рассматривается, различно. Так бывает в большинстве практических задач. Чтобы «совместить практику с теорией» и соответствовать вышеприведённому определению, надо вспомнить, что всегда можно добавлять в соответствующие функции недостающие фиктивные аргументы. В нашем примере функция f₁ могла быть представлена, скажем, так: f₁(a,b,c) = (ab)(cc'). Теперь и здесь стало три аргумента, как в f₂ и f_3.

***

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

1.2 О функционально полных системах

Определение. Система функций = ₁, ₂,…, _m называется функционально полной (или просто полной), если любая сколь угодно сложная булева функция может быть выражена через функции ₁,…,_m с помощью суперпозиции.

Примером такой полной системы является ₀ =,,.

Для обозначения функционально полной системы примем сокращение ФПС.

Лемма о достаточном условии полноты. Пусть система =f₁,f₂,…,f_m - ФПС, и любая из входящих в неё функций может быть выражена с помощью суперпозиции через функции некоторой другой системы ⁺=g₁, g₂, …, g_k. Тогда система ⁺ тоже ФПС.

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

f = f(f₁, f₂, …, f_m).

В свою очередь, по условию леммы каждая функция f_i , i=1, …, m, участвующая в построении этой формулы, может быть выражена формулой над ⁺ , то есть с помощью функций g_j⁺ :

f₁=f₁(g₁,g₂,…,g_k),

f₂=f₂(g₁,g₂,…,g_k),

. . . . . . . . . .

f_m=f_m(g₁,g₂,…,g_k).

Заменим в формуле f(f₁, f₂, …, f_m) вхождение каждого символа функции f_i ( i=1,…, m) соответствующей формулой над ⁺:

f(f₁, f₂, …, f_m) = f(f₁(g₁,g₂,…,g_k), …, f_m(g₁,g₂,…,g_k)).

Получили другую формулу, которая, как легко догадаться, реализует ту же самую произвольную булеву функцию f. Значит, в соответствии с определением ФПС, система ⁺ тоже функционально полная. O

Замечание. Здесь в качестве аргументов функции f использовались все функции системы , а аргументами функций f₁ ,… , f_m , были все функции системы ⁺ , хотя на самом деле могут использоваться лишь некоторые из них.

На основании этой леммы докажем полноту некоторых систем функций.

1. Докажем сначала, что системы ₁=, и ₂=, функционально полны. Для этого покажем, что любая функция из ₀ выражается через ₁ или ₂.

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

хy=( х' y')'; хy=( х' y')' (1)

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

Замечание 2. За неизбыточность систем ₁ и ₂ приходится платить избыточностью формул, написанных в этих системах, поскольку каждая замена одной операции на другую по соотношению (1) вносит в формулу дополнительные знаки отрицания.

2. Докажем, что функционально полны также и системы, состоящие каждая из одной единственной функции:

₃= (штрих Шеффера) и ₄=(стрелка Пирса).

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

₀ = &,, выражаются через ₃ = и ₄. =.

Сначала посмотрим на таблицу 1, которая определяет штрих Шеффера и стрелку Пирса, чтобы увидеть, как через ₃ и ₄ выражается инверсия: x' xx xx.

Теперь посмотрим, как может быть представлена дизъюнкция. С учётом выражения инверсии через ₃ и ₄ , получим:

xy = (хy)'' = (хy)' = (хy)(хy).

Аналогично этому получим формулу

конъюнкции:

х&y = (хy)'' = (хy)' (хy)(хy).

Следовательно, ₃ сводится к ₁, а ₄ сводится к ₂. Принимая во внимание лемму о достаточном условии полноты и учитывая, что ₁ и ₂ - ФПС, делаем вывод, что ₃ и ₄ - тоже ФПС. O

3. Система ₅=,,1тоже функционально полна. Действительно, функция выражается через инверсию: х'=х1, и, следовательно, ₅ сводится к ₁=,. Значит, ₅ - ФПС по определению. O

Замечание. Оказывается, система ₅ позволяет представлять булевы функции в каноническом виде подобно СДНФ и СКНФ. Об этом поговорим подробнее ниже, в разделе 4.

4. Докажем функциональную полноту системы функций

⁺= { xy, ( xyz)' }.

Для этого выразим функции известной ФПС ₂= x', xy через функции системы ⁺. Получим:

1) x'=( xxx )'.

2) xy= x'y = (xxx)' y.

В соответствии с леммой о достаточном условии полноты заключаем, что система ⁺ = { xy, ( xyz)' } является ФПС. O

***

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

1.3 Определение замкнутого класса

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

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

2. Замкнутым классом является множество всех дизъюнкций вида x₁x₂…x_n , поскольку, как нетрудно увидеть, подстановка вместо какой-либо переменной x_k, k=1,2,…,n, дизъюнкции вида y₁y₂ … y_m снова даст дизъюнкцию.

***

Некоторые подмножества множества булевых функций также являются замкнутыми классами:

§ классТ⁰ функций, сохраняющих константу 0;

§ класс Т¹ функций, сохраняющих константу 1;

§ класс L линейных функций;

§ класс S самодвойственных функций;

§ класс М монотонных функций.

Познакомимся с этими классами.

1. Класс Т⁰ функций, сохраняющих константу 0

Определение. Булева функция сохраняет константу 0 (принадлежит классу Т⁰), если на наборе из всех нулей функция принимает значение 0:

f (00…0)=0.

Заметим, что вектор значений таких функций начинается с 0, например f = (0111 0111).

Примеры. 1. Элементарные булевы функции конъюнкция и тождественная функция принадлежат классу Т⁰ .

2. Функция f(х₁,х₂,х₃)=х₁х₂'х₁х₂х₃' принадлежит Т⁰. Действительно,

f(0,0,0)=0&0'0&0&0'=0.

3. Функция эквивалентности xy Т⁰, поскольку 00 = 1.

Теорема о мощности класса Т⁰. Количество различных булевых функций, зависящих от n переменных и сохраняющих константу 0, равно 2^К-1, где К=2n.

Доказательство. Известно, что число различных булевых функций n аргументов равно 2^К , где К=2ⁿ . В векторе значений некоторых булевых функций 1-я компонента равна 0. Таких функций ровно половина, то есть количество функций

| T⁰ |=2^К/2=^-2^К-1, где К=2ⁿ

Пример. Из всех 16 элементарных булевых функций f(х₁,х₂) в класс Т⁰ входят следующие восемь (n=2, К = 2² = 4,

| Т⁰ | = 2^4-1 = 8):

{ 0, , , , , , х₁, х₂ }.

Теорема о замкнутости класса Т⁰. Множество всех булевых функций, сохраняющих константу 0, является замкнутым классом.

Доказательство. Пусть даны функции

g(y₁, …, y_m), f₁(x₁, …, x_n),…, f_m(x₁, …, x_n),

входящие в класс Т⁰. Условимся последующие выкладки для краткости проводить при 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(0,0). Учитывая, что f₁(x₁,x₂)T⁰, f₂(x₁,x₂)T⁰, f₃(x₁,x₂)T⁰ и g(y₁,y₂,y₃)T⁰, получим: h(0,0) g (f₁(0,0), f₂(0,0), f₃(0,0)) = g(0,0,0) = 0.

Из этого следует, что суперпозиция h(x₁,x₂) принадлежит классу Т⁰. Значит, класс Т⁰ замкнут. O

2. Класс Т¹ функций, сохраняющих константу 1

Определение. Булева функция сохраняет константу 1 (принадлежит классу Т¹), если на наборе из всех единиц функция принимает значение 1.

f(111…1)=1.

Теорема о мощности класса Т¹. Количество различных булевых функций, зависящих от n переменных и сохраняющих константу 1, равно |T¹|=2^К-1, где К=2n. Доказательство подобно доказательству теоремы про |T⁰|

Пример. Из всех 16 элементарных булевых функций f(х₁,х₂) принадлежат множеству Т¹ следующие восемь (n=2, К= 2² =4, | Т¹ | = 2^4-1 = 8 ):

{ 1, , , , , , х₁, х₂ }.

Теорема о замкнутости класса Т¹. Множество всех булевых функций, сохраняющих константу 1, является замкнутым классом.

Доказательство этой теоремы подобно доказательству теоремы о замкнутости класса Т⁰

2. Класс L линейных функций

Мы познакомились в разделе 1.2 с ФПС ₅=,,1. Эта система интересна тем, что позволяет провести аналогию между арифметическими операциями умножения и сложения чисел 0 и 1 и булевыми операциями и над булевыми константами 0 и 1. В самом деле, конъюнкция хy подобна операции умножения над числами 0 и 1, а операция хy похожа на операцию сложения: 0+0=0; 0+1=1+0=1. Если теперь понимать под числами 1 и 0 числа двоичной системы счисления, то арифметическую операцию сложения Если в двоичной системе счисления при сложении 1+1=10 отбросить в сумме 10 единицу переноса в разряд двоек (2¹), то будем иметь операцию сложения по модулю 2. 1+1 можно считать подобной логической операции и вместо знака пользоваться знаком +.

Система ₅=,,1 замечательна ещё и тем, что помогает определить для некоторого класса булевых функций свойство линейности. Делается это с помощью полинома Жегалкина. Познакомимся с этим полиномом, который, оказывается, является ещё одним каноническим видом представления функции (наряду с СДНФ и СКНФ).

2.1 Полином Жегалкина

Условимся в дальнейшем изложении вместо знака писать знак + по аналогии с обычным сложением чисел 1 и 0. Заметим также, что для любой формулы F будет справедливо:

F+F=0 и F+0=F

Определение. Полиномом Жегалкина (ПЖ) будем называть многочлен, являющийся суммой констант 0 или 1 и различных одночленов, в которых все переменные входят не выше, чем в 1-й степени.

В соответствии с этим определением полином Жегалкина от двух переменных имеет вид

Р₁(х₁,х₂) = ₀+₁х₁+₂х₂+₁₂х₁х₂ ,

а ПЖ от трёх переменных - вид

Р₁(х₁,х₂,х₃)=₀+₁х₁+₂х₂+₃х₃+₁₂х₁х₂+₁₃х₁х₃+₂₃х₂х₃+₁₂₃х₁х₂х₃.

Здесь все коэффициенты с различными индексами равны 0 или 1.

Построить полином Жегалкина можно следующими способами:

1) воспользовавшись таблицей истинности и неопределёнными коэффициентами, как описано в теореме;

2) преобразованием исходной формулы по следующему правилу:

а) преобразовать формулу так, чтобы использовались только операции и ;

б) везде заменить инверсию х' на х+1;

в) раскрыть скобки, пользуясь законом (x+y)z=xz+yz;

г) привести подобные члены;

3) воспользовавшись так называемым треугольником Паскаля.

Рассмотрим несколько примеров построения полиномов Жегалкина.

Пример 1. Методом неопределенных коэффициентов найдём ПЖ для

f(x,y)=xy.

f(x,y)=₀+₁х+₂y+₃хy

f(0,0)=1=₀+₁0+₂0+₃0=₀ ………… . ₀=1

f(0,1)=1=1+₁0+₂y+₃0. 1=1+₂ … ₂=0

f(1,0)=0=1+₁1+0y+₃10. 0=1+₁ …...₁=1

f(1,1)=1=1+ 1+0y+₃11=1+1+₃=₃ ….. ₃=1

Значит, xy=1+x+xy.

Пример 2. Преобразованием формул найдём ПЖ для импликации и дизъюнкции, учитывая, что x' = х+1 и y' = y+1:

xy=x'y=(x'y)''=(xy')'=(x(y+1))'=x(y+1)+1=xy+x+1.

xy = (xy)''=(x'&y')'=((x+1)(y+1))'=(xy+y+x+1)+1=xy+x+y.

Пример 3. Пользуясь треугольником Паскаля, построим ПЖ для функции f(x,y,z)=xyz.

Нам понадобится вектор-столбец значений функции. Чтобы его получить, построим таблицу истинности для этой функции. Слева от наборов разместим слагаемые полинома Жегалкина.

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

Первая единица треугольника соответствует набору (000) - первое слагаемое многочлена есть 1. Последняя единица треугольника соответствует набору (111) и определяет слагаемое xyz. Средняя единица в левой стороне треугольника сопоставлена набору (100) - слагаемым становится x. Получили

xyz=1+x+xyz.

Проверим эту формулу. В примере 2 увидели, что xy=xy+x+1. В этой формуле вместо y напишем yz и получим

xyz = xyz + x + 1.

Известно, что любая булева функция может быть единственным способом представлена формулой в СКНФ или в СДНФ. Покажем, что для единственного представления булевой функции может использоваться также и полином Жегалкина. Именно поэтому его называют также и алгебраической нормальной формой.

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

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

Известно, что любая БФ имеет свою единственную таблицу истинности. Запишем сначала данную функцию в виде ПЖ с неопределёнными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов, то отсюда следует единственность представления булевой функции полиномом Жегалкина. O

Замечание. Количество различных полиномов Жегалкина для булевых функций n аргументов совпадает с количеством различных булевых векторов длины 2ⁿ, которое, как известно, равно 2^K, где K=2ⁿ.

2.2 Замкнутость и мощность класса L

Определение. Будем называть линейной булеву функцию, у которой полином Жегалкина имеет вид

P(x₁,…,x_n)= б₀+ б₁x₁+ б₂x₂+…+ б_nx_n, б_i0,1, i=0,…,n. (*)

Например, все функции одной переменной имеют вид

f(x) P(х) = б₀ + б₁x.

Рассмотрим, будут ли линейными некоторые известные функции.

Пример 4. f(x) = х'=x+1 - линейная функция.

Пример 5. f(x,y) = xyP(x,y)=x+y - линейная функция.

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

Известно, что xy = (xy)(yх). Используя формулу

xy=1+x+xy примера 1, получим:

Р(x,y)=(xy+x+1)(xy+y+1)=xyxy+xxy+ xy+xyy+ xy+y+xy+x+1=

=(xy+xy)+(xy+xy)+(xy+xy)+y+x+1= {учтём, что F+F=0 } = x+y+1.

Пример 7. Функция xy = xy+x+y - нелинейная, что видно из рассмотренного выше примера 2.

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

Теорема о мощности класса L. Количество различных линейных функций, зависящих от n переменных, равно 2ⁿ⁺¹.

Доказательство. Известно, что полином Жегалкина линейной функции f(x₁, …, x_n) имеет вид P(x₁, …, x_n)= б₀+б₁x₁+б₂x₂+…+б_nx_n.

Это значит, что каждый такой полином определяется своими коэффициентами, образующими булев вектор б=(б₀б₁…б_n). И наоборот: каждый булев вектор б длиной n+1 задаёт линейный полином Жегалкина для функции n переменных. Количество векторов длиной n+1 равно 2ⁿ⁺¹ . Поскольку между такими векторами и линейными полиномами Жегалкина установлено взаимно-однозначное соответствие, приходим к выводу, что количество L различных линейных функций от n аргументов равно 2ⁿ⁺¹.O

Пример. Из всех элементарных функций f(x₁,x₂) классу L принадлежат 8 функций

(n=2, |L|= 2²⁺¹ =8)

0, 1, , , х₁, х₂, х₁', х₂'.

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

Доказательство этой теоремы подобно доказательству теоремы о замкнутости класса Т⁰. Пусть даны функции g(y₁,…,y_m), f₁(x₁,…,x_n),…, f_m(x₁,…,x_n), входящие в класс L. Условимся, не нарушая общности, следующие рассуждения проводить для 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₂) (1)

Учтём, что функции g, f₁, f₂ и f₃ линейны, и представим их полиномами Жегалкина:

g(y₁,y₂,y₃) = б₀+б₁y₁+б₂y₂ +б₃y_{3 ,}

f₁(x₁,x₂) = в₀₁+ в₁₁x₁+ в₂₁x₂ ,

f₂(x₁,x₂) = в₀₂+ в₁₂x₁+ в₂₂x₂ , (2)

f₃(x₁,x₂) = в₀₃+ в₁₃x₁+ в₂₃x₂ .

Напомним, что в ПЖ все коэффициенты при переменных равны 0 или1:

б_j, в_ik{0,1}, j=0,1,2,3; i=0,1,2; k= 1,2,3. (3)

Формула (1) после подстановки полиномов (2) примет следующий вид:

g(y₁,y₂,y₃)=₀+₁(в₀₁+в₁₁x₁+в₂₁x₂)+₂(в₀₂+в₁₂x₁+ в₂₂x₂)+

+₃(в₀₃+ в₁₃x₁+в₂₃x₂)=

=(₀+₁в₀₁+₂в₀₂+₃в₀₃)+(₁в₁₁+₂в₁₂+₃в₁₃)x₁+

+(₁в₂₁+₂в₂₂+₃в₂₃)x₂

h(x₁,x₂).

В полученном полиноме из-за (3) каждая скобка - это либо константа 0, либо константа 1. Стало быть, суперпозиция h(x₁,x₂) представлена линейным ПЖ, то есть принадлежит классу L. Значит, класс L замкнут.

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

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

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

1	(xyx'y)z	7	(1000 1110)
2	x'y y'z z't t'x	8	xyz'xy'
3	xy(xy)	9	(0110 0111)
4	(xy)(yx)z	10	(1001 0110)
5	xyz(xyz)'	11	(x y)(yz)
6	(xy)' x'y	12	(xy)(x'y')

3. Двойственная функция

3.1 Определение и примеры

Определение. Будем называть булеву функцию f*(x₁,x₂,…,x_n), n1, двойственной относительно функции f(x₁,x₂,…,x_n), если она получена из f(x₁,x₂,…,x_n) инверсией всех аргументов и самой функции:

f*(x₁, x₂,…, x_n) f '(x₁', x₂',…, x_n').

Замечание. При n=0 полагают, что функция 0 двойственна 1, а 1 двойственна 0.

Построим функции, двойственные некоторым элементарным функциям.

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

Два одинаковых правых столбца убеждают нас в справедливости доказательства.

Заметим, что то же самое получим, если применить формулы равносильных преобразований:

f*(x₁,x₂)=(х₁'х₂')'=(х₁&х₂)''=x₁&x₂.

Пример 9. Пусть f(x₁,x₂)=х₁х₂. Используя определение, покажем, что для этой конъюнкции двойственной функцией будет дизъюнкция.

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

f*(x₁,x₂)=(х₁'х₂')' = (х₁х₂)'' = х₁х₂.

Замечание. Из этих примеров видно, что, если имеется формула, содержащая только ,,, то, заменяя в ней всюду на и на , получим формулу, двойственную исходной. Так можно, например, перейти от СДНФ к СКНФ.

Пример 10. Построим функцию, двойственную стрелке Пирса

х₁х₂ .

Оказалось, что для стрелки Пирса двойственной функцией будет штрих Шеффера (НЕ-И).

f(x₁,x₂)=х₁ | х_{2 .}

Ещё раз убедимся в этом, используя приведённое замечание. Известно, что стрелка Пирса - это функция НЕ-ИЛИ:

х₁х₂=(x₁x₂)'.

Заменив здесь знак на &, получим функцию НЕ-И, то есть штрих Шеффера:

f*(x₁,x₂)=(x₁&x₂)' = х₁|х₂

Пример 11. Построим функцию, двойственную импликации, с учётом замечания.

f(x₁,x₂)= х₁х₂= х₁' x₂ .

Заменив на &, получим

f*(x₁,x₂)= х₁'&x₂ = х₁x₂ .

Напомним, что функция х₁x₂ называется не обратная импликация.

Пример 12. Пусть f(x₁,x₂)=х₁+х₂. Используя определение, найдём двойственную для функции + (сложение по модулю 2) .

Оказалось, что для f(x₁,x₂)=х₁+х₂ двойственной функцией будет

f*(x₁,x₂)= х₁х₂.

В качестве упражнения получим тот же результат, используя полином Жегалкина. Вспомним, что х'=х+1 и f'(x)=f(x)+1. Тогда для f(x₁,x₂)=х₁+х₂ будем иметь:

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

f*(x₁,x₂)=f '(x₁', x₂') = (x₁+x₂)' = x₁+x₂+1.

Такое же представление f(x₁,x₂)=x₁+x₂+1 было получено в примере 6. Значит, для функции сложение по модулю 2 двойственной будет функция эквивалентности.

Пары двойственных элементарных функций

0 1 , & , | , ,

Тождественная функция и инверсия двойственны каждая самой себе.

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

3.2 Алгоритм построения таблицы истинности двойственной функции

Определение. Будем называть противоположными, или антиподами два булевых вектора одинаковой длины б=(б₁б₂…б_n) и в=(в₁в₂…в_n), если б_i?в_i , i=1,…,n.

Пример. Антиподы (00) и (11), (01) и (10), (011) и (100), (0110) и (1001).

Очевидно, что инверсия всех компонент вектора б превращает его в антипод в. В таблице истинности функции f(x₁,x₂,…,x_n) антиподом первого набора (00…0) является набор (11…1), который расположен последним. Антипод второго набора будет предпоследним и так далее.

Следуя определению двойственной функции, нужно:

· перевернуть столбец значений исходной функции f(x₁,x₂,…,x_n) - меняются местами антиподы, получим функцию f(x₁', x₂', …, x_n'),

· инвертировать компоненты столбца f(x₁',x₂',…,x_n') - получим искомую функцию f '(x₁',x₂',…,x_n').

Пример 13. В примере 10 нашли функцию, двойственную импликации

х₁х₂: f*(x₁,x₂)= х₁'х₂ = х₁x₂

Построим её теперь по приведённому алгоритму.

Пример 14. Пусть f(x₁,x₂,x₃)=x₁+x₂+x₃. Найдём для этой функции двойственную, используя известное выражение инверсии

x'= x+1.

f*(x₁,x₂,x₃) = (x₁'+x₂'+x₃')' = (x₁+1+x₂+1+x₃+1)' =

= (x₁+x₂+x₃+1)'=x₁+x₂+x₃+1+1=

= x₁+x₂+x₃.

Получили, что f*(x₁,x₂,x₃) = x₁+x₂+x₃ = f(x₁,x₂,x₃). Оказалось, что двойственная функция равносильна исходной. O

Функции, наделённые таким свойством, образуют специальный класс S самодвойственных функций. Этот класс, как и рассмотренные выше классы Т⁰, Т¹, L , является замкнутым. Но сначала дадим определение понятию самодвойственной функции.

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

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

1.	(xyx'y)z	8.	(x'y')(yx)
2.	xy	9.	xy
3.	xyz	10.	x'y'z
4.	(xy)(zt)	11.	(xy)(zt)
5.	xyz(xyz)'	12.	(x y)(yz)
6.	(1000 1110)	13.	(0110 0111)
7.	(0111 0001)	14.	(1001 0110)

4. Класс S самодвойственных функций

4.1 О количество различных самодвойственных функций

Определение. Функция, равносильная своей двойственной, называется самодвойственной:

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

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

f(x') = x', f*(х)= f '(x') = x.

Пример 16. Функция f(x)=x' - самодвойственная. Действительно, так как

f(x') = x'' = x, а f*(х) = f '(x') = x' = f(x).

Пример 17. Докажем, что функция f(x,y,z) = xyz(xy) самодвойственная. Найдём ей двойственную:

f*(x,y,z) = ( x'y' z'(x' y') )' = (x'y')' (z'' (x'y')') = (xy)(zxy) =

= xzyzxxyyxy = xzyzxy = xy(xy)z.

Получили, что f*(x,y,z)=f(x,y,z). Самодвойственность доказана. O

Утверждение об инверсии аргументов. Если функция f(х₁,х₂,…,х_n) самодвойственная, то f(х₁',х₂',…,х_n') = f '(х₁,х₂,…,х_n).

Доказательство следует из определения.

Если f '(х₁',х₂',…,х_n') = f(х₁,х₂,…,х_n), то инверсия, применённая к обеим частям этого равенства, даст

f ''(х₁',х₂',…,х_n') = f '(х₁,х₂,…,х_n)

Замечание. Эта равносильность говорит также о том, что самодвойственная функция на антиподах (х₁,х₂,…,х_n) и (х₁',х₂',…,х_n') принимает противоположные значения.

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

Пример 18. Рассмотрим функцию f(x,y,z) голосования. Она называется так потому, что принимает значение 1 только на тех наборах, в которых единиц больше, чем нулей Эту функцию ещё называют мажоритарной..

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

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

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

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

Доказательство очевидно.

Теорема о мощности класса S. Количество различных самодвойственных булевых функций, зависящих от n переменных, равно

|S|=2^К, где К=2^n-1.

Доказательство. Рассмотрим f(х₁,х₂,…,х_n)S, заданную таблицей истинности. Если на первом наборе она принимает значение , то, - согласно свойству самодвойственной функции, - на последнем наборе, который является антиподом первому, она принимает значение '.

То же можно сказать о значениях функции на втором и предпоследнем наборах и т.д. Следовательно, самодвойственная функция полностью определяется верхней половиной своего столбца значений, то есть булевым вектором длины 2ⁿ/2=2^n-1. Известно, что количество векторов длиной 2^n-1 равно 2^K, где K=2^n-1. Значит, количество различных самодвойственных функций f(х₁,х₂,…,х_n) тоже равно |S|=2^К, где К=2^n-1. O

Пример. Из элементарных 16 булевых функций самодвойственными являются лишь 4 (n=2, K=2^2-1=2, |S|=2²): тождественные функции х₁, х₂ и их инверсии х₁', x₂'.

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

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

1	(xyx'y)z	8	xy'x'yy'z
2	(xy)z	9	xyz'
3	(x(zt))y'	10	(xyz')t'x'yz
4	xyyz'y'z	11	xy'z'yz
5	xyyzzt	12	(0110 0111)
6	xy(xy)	13	(0111 0001)
7	x(yz)	14	(1001 0110)

4.3 О замкнутости класса самодвойственных функций

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

Доказательство. Надо показать, что суперпозиция самодвойственных функций тоже будет самодвойственной функцией. Пусть даны функции g(y₁, …,y_m), f₁(x₁, …,x_n),…, f_m(x₁, …,x_n), входящие в класс S. Условимся, не нарушая общности, следующие рассуждения проводить для 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(x₁,x₂), пользуясь определением двойственности. Если окажется, что h*(x₁,x₂)=h(x₁,x₂), то теорема будет доказана. Выполним два шага.

Шаг 1. Сначала заменим все аргументы h(x₁,x₂) на их инверсию:

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

=применим утверждение об инверсии аргументов

самодвойственных функций f₁, f₂, f₃ =

= g( f₁'(x₁,x₂), f₂'(x₁,x₂), f₃'(x₁,x₂) )=

=поскольку gS, применим утверждение об инверсии

её аргументов=

= g' ( f₁ (x₁,x₂), f₂ (x₁,x₂), f₃(x₁,x₂) ).

Шаг 2. Теперь найдём h*(x₁,x₂), вычислив h'(x₁',x₂').

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

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

h(x₁,x₂).

Так убедились, что h*(x₁,x₂) = h(x₁,x₂), то есть суперпозиция самодвойственных функций тоже будет самодвойственной функцией. O

Пример 19. Для иллюстрации этой теоремы подставим в функцию f₁(x,y,z)=xyz(xy) самодвойственную функцию f₂ (p)=p' вместо аргумента z. В примере 13 было установлено, что функция f₁(x,y,z) самодвойственная, так что будем выполнять суперпозицию самодвойственных функций. Получим

f₁(x,y,f₂(p))=xyp'(xy)g(x,y,p).

Теперь выполним два шага, как и при доказательстве вышеприведённой теоремы.

Шаг 1. Заменим у этой функции g(x,y,p) аргументы на их инверсии. g(x',y',p')=f₁(x',y',f₂(p')) x'y'p''(x'y') = x'y'p(x'y')

{поскольку f₂(p)S, то f₂(p')=f₂'(p) согласно

утверждению об инверсии аргументов

самодвойственной функции }

f₁(x', y', f₂'(p)).

Шаг 2. Теперь найдём инверсию этой функции:

f₁'(x',y',f₂' (p)) = ( x'y' p(x'y') )'=

= (x'y')'&( p(x'y') )' =

= (xy)&(p' (x'y')') =

= (xy)(p'xy) = xp'yp'xxyxyy = xp'yp'xyxy=xyp'(xy) =

={учтём, что p'=z}=xyz(xy).

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

5. Класс М монотонных функций

5.1 Определения и примеры

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

На множестве B=0,1 введём полный порядок: будем считать, что 0<1. Нам придётся иметь дело с функциями от n переменных, поэтому полезно ввести частичное упорядочение в булевом пространстве Вⁿ.

Определение 1. Пусть б=(б₁б₂…б_n) и в=(в₁в₂…в_n) - элементы из Вⁿ. Будем говорить, что б предшествует (младше) в, и обозначать бв, если б_k в_k для k=1,2,…,n, причём хотя бы для одного k имеет место строгое неравенство.

Пример. б=(001100), в=(001110); б₁=в₁, б₂=в₂, б₃=в₃, б₄=в₄, б₅<в₅, б ₆=в₆. Значит, бв.

Определение 2. Два вектора б и в называются сравнимыми между собой, если бв или вб. В противном случае векторы считаются несравнимыми. Частичным такой порядок называется потому, что не все элементы из Вⁿ сравнимы. Поэтому не надо путать частичный порядок на Вⁿ с полным упорядочением, которое использовалось при задания булевой функции таблицей или вектором её значений.

Вот пара примеров несравнимых между собой векторов.

1. б =(1100), в =(0110). Здесь б₁ > в₁, б₂=в₂, б₃ < ₃, б₄=в₄.

2. б =(01), в =(10). Здесь б₁ < в₁ , б₂ > в₂ .

Из примеров видно, что несравнимые наборы - это те, в которых есть компоненты типа (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 году Стивен поступил лейтенантом в Школу морского резерва ВМФ США в Нью-Йорке в качестве навигационного инструктора. Позже он был директором проекта в Военно-морской исследовательской лаборатории в Вашингтоне.

После окончания в 1946 году Второй мировой войны Клини в звании капитан-лейтенанта оставил службу и вернулся в Висконсинский университет. Ушёл на пенсию в 1979 г.

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

Умер Стивен Коул Клини 25 января 1994 в Мэдисоне, штат Висконсин.

8.6 Эмиль Леон ПОСТ

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

Мы сейчас знаем Поста как замечательного исследователя в области математической логики. Но во время учёбы в колледже он не проявлял особого интереса в этом направлении - он увлёкся астрономией. А на последнем курсе написал статью, в которой содержались важные идеи о преобразовании Лапласа. Но студент не решился опубликовать её, и она увидела свет лишь в 1930 году.

В 1917 году Эмиль получил степень бакалавра в области математики и поступил в Колумбийский университет, где в 1920 получил степень доктора философии. После получения докторской степени Э. Пост отправился в Принстонский университет, где поработал год, а затем вернулся в Колумбийский университет. Здесь его настигла болезнь маниакально-депрессивного характера, с которой он был вынужден бороться всю жизнь и которая, конечно, ограничила его возможные достижения. В 1924 году Пост отправился в Корнелл, но снова заболел. Он возобновил работу в 1927 году учителем средней школы в Нью-Йорке, а в 1932 году он начал работать в том же колледже, который когда-то закончил, и оставался там до конца жизни с перерывами из-за болезни.

В 1929 году он женился на Гертруде Сингер. Их дочь Филлис вспоминает, что все преподаватели колледжа располагались в одной комнате с большим столом в середине. И хотя учебная нагрузка отца была 16 контактных часов в неделю, он не мог продуктивно заниматься наукой в колледже, предпочитая работать дома. И Гертруда делала всё, чтобы муж мог всецело посвятить себя математике. Она ухаживала за малышкой Филлис, перепечатывала рукописи Эмиля, вела все домашние и финансовые дела.

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

После опроса Э.Пост вытаскивал 3-5 карточек и подробно объяснял по каждой новый материал. Студенты были бы рады, если бы он успевал рассказать по всем картам до звонка. Но звучал звонок, и на вопросы не оставалось времени. Удивительно, но эта, казалось бы, негибкая педагогическая методика была чрезвычайно успешна, и Пост была очень популярным преподавателем.

Один из его студентов 1943-го года вспоминал: «Эмиль Леон Пост был коренастым мужчиной, неизменно одетым в костюм-«тройку». Пустой рукав тщательно был заправлен в боковой карман. Лектор постоянно энергично ходил перед доской, говоря чётко и ясно. Внезапно он поворачивался, чтобы что-то написать мелом на доске. Это движение всегда приводило к тому, что рукав наконец освобождался из своего плена и (к облегчению аудитории) свободно болтался. Нам казалось, что эта свобода движения освобождала и его мышление во время лекции».

Умер Эмиль Леон Пост 21 апреля 1954 года. Его ранняя смерть в 57 лет была почти наверняка прямым следствием лечения маниакально-депрессивного заболевания электрическим током. После одного из ударов током у Поста случился сердечный приступ, который он не смог перенести [20].

Э.Л.Пост в результате почти 20-летней работы получил ряд фундаментальных результатов в математической логике, в частности, одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем; доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний. Он изучил системы многозначной логики с более чем тремя значениями истинности; дал одно из первых (независимое от А. М. Тьюринга) определений понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировку основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения. Э.Л. Пост доказал выразимость общерекурсивных функций и предикатов через примитивно рекурсивные, доказал так называемую теорему о нормальной форме; доказал алгоритмическую неразрешимость ряда проблем математической логики и алгебры и др.[21].

8.7 Иван Иванович ЖЕГАЛКИН

ЖЕГАЛКИН Иван Иванович родился в 1869 году в городе Мценске (Орловская губерния, Российская империя). Окончив Орловскую гимназию, он поступил в Московский университет на математическое отделение физико-математического факультета. В 1893 году окончил университет, получив дипломом 1-й степени. Иван Иванович поначалу служил в нескольких учреждениях: в Госбанке и на курсах при Обществе распространения коммерческого образования. В 1900 году Иван Иванович становится преподавателем реального училища К. Мазинга. Через два года он выдержал экзамен на магистрат и стал приват-доцентом университета.

В 1907 году защитил магистерскую диссертацию «Трансфинитные числа», которая была первой монографией по теории множеств в отечественной и мировой литературе. В 1911 году Иван Иванович вместе с другими преподавателями, несогласными с министром просвещения Л. А. Кассо. и проводимой им политики, покинул университет. Он начинает преподавать на Высших женских курсах, где с 1906 года временно исполнял обязанности декана факультета. Кроме того, Иван Иванович заведовал библиотекой и был членом Московского математического общества.

В 1923 году он возвращается в университет, становится профессором математики. В 1927 году И. И. Жегалкин написал ряд статей, посвященных некоторым важным случаям, допускающим алгоритмическое решение так называемой проблемы разрешимости. В этом же году он предложил построение алгебры логики как арифметики вычетов по модулю 2. Это позволило получить такой вариант алгебры логики, в котором законы преобразований логических выражений мало чем отличаются от законов обычной школьной алгебры, так что техника вычислений при решении тех или иных задач становится проще и понятнее.

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

С 1930 года он возглавляет кафедру математического анализа физико-механического факультета МГУ, а в Московском областном пединституте заведует кафедрой математики. Иван Иванович был инициатором создания научного семинара по математической логике, который впоследствии (в 1959 году) был преобразован в кафедру математической логики. Доктор физико-математических наук (1935), заслуженный деятель науки РСФСР (1945) И.И. Жегалкин был награждён Орденом Трудового Красного Знамени [22].

Скончался великий математик в 1947 году. Его похоронили в Москве, на Ваганьковском кладбище

Заключение

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

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

Хотелось бы надеяться, что Вам, уважаемый читатель, стали немного ближе и Джордж Буль, который уже в 12 лет самостоятельно изучил пять языков, и непонятый современниками Огастес де Морган, и умерший в бедности и забвении философ Чарльз Сандерс Пирс, и не публиковавший своих исследований Генри Морис Шеффер, и альпинист, громкоголосый любитель анекдотов Стефен Коул Клини, и страдающий от психической болезни однорукий Эмиль Леон Пост, и наш российский математик Иван Иванович Жегалкин, который не побоялся протестовать против политики тогдашнего министра просвещения.

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

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

Источники литертауры

1. Быкова С.В., Буркатовская Ю.Б. Булевы функции. Учебно-методическое пособие. Часть IV. - Томск: Томский госуниверситет, 2006. - 42 с.

2. Ахметова Н.А., Усманова З.М. Дискретная математика. Функции алгебры логики. Учебное пособие. - Уфа: УГАТУ, 2002. - 126 с.

3. Прилуцкий М.Х. Методическое пособие по курсу 'Математические основы информатики' Часть 1. - Нижний Новгород: Нижегородский госуниверситет, 2000. - 81 с.

4. Киселёва Л.Г., Смирнова Т.Г. Функции алгебры логики в примерах и задачах: Учебно-методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2008. - 57 с.

5. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1986. -384 с.

6. Марченков С.С. Булевы функции. - М.: ФИЗМАТЛИТ, 2002. - 68 с.

7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике : Учеб. пособие. - 3-е изд., перераб. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

8. Гиндикин С.Г. Алгебра логики в задачах. - М.: ФИЗМАТЛИТ, 1972. - 288 с.

9. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. - М., Наука, 1966 - 120 с.

10. Новиков П.С. Элементы математической логики. М.: ФИЗМАТГИЗ, 1959. - 400 с.

11. Клини С.К. Введение в метаматематику, пер. с англ., М.: Иностр. лит., 1957

12. Большая советская энциклопедия [Электронный ресурс]. Режим доступа: http://dic.academic.ru/dic.nsf/bse/122206/ ПОЛНОТА

13. Философская энциклопедия. В 5 томах. - М.: Советская энциклопедия, под ред. Ф.В. Константинова. 1960-1970.

14. Википедия. [Электронный ресурс] Режим доступа:

http://ru.wikipedia.org/wiki/Буль,_Джордж

15. Энциклопедический словарь. [Электронный ресурс] Режим доступа: http://dic.academic.ru/dic.nsf/es/10266/ Буль

16. Попов Ю.П. Элементы истории и теории логики. [Электронный ресурс] Режим доступа:

http: //vpn.int.ru/index.php?name=Biography&op=page&pid=791.

17. Энциклопедический словарь, 2009 [Электронный ресурс] Режим доступа: http://dic.academic.ru/dic.nsf/es/44076/ Пирс.

18. An American logician (Mathematician). WorldTechForum. Henry Maurice Sheffer, [Электронный ресурс] Режим доступа: http://worldtechforum.blogspot.ru/2012/11/henry-maurice-sheffer-american-logician.html

19. J J O'Connor and E F Robertson. Stephen Cole Kleene. MacTutor History of Mathematics. [Электронный ресурс] Режим доступа:

http://www-history.mcs.st-andrews.ac.uk/Biographies/Kleene.html

20. J J O'Connor and E F Robertson. Stephen Cole Kleene. MacTutor History of Mathematics. [Электронный ресурс] Режим доступа:

http://www-history.mcs.st-andrews.ac.uk/Biographies/ Post.html

21. Российские универсальные энциклопедии Брокгауз-Ефрон и Большая Советская Энциклопедия, объединенный словник. [Электронный ресурс] Режим доступа:

http://gatchina3000.ru/great-soviet-encyclopedia/bse/091/869.htm

22. Большая биографическая энциклопедия,2009. [Электронный ресурс] Режим доступа:

http://dic.academic.ru/dic.nsf/enc_biography/138319/ ЖЕГАЛКИН

Пртложение 1. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ ОПРЕДЕЛЕНИЕ ТАБЛИЦЕЙ ИСТИНОСТИ

НАЗВАНИЯ И ОБОЗНАЧЕНИЯ

f₀ = 0 - константа 0.

f₁₅ =1 - константа 1.

f₃(x) = x - переменная x (тождественная функция).

f₅(y) = y - переменная y (тождественная функция).

f₁₂(x) = , x, ¬x - отрицание x, инверсия x;

читается « не x», « неверно, что x ».

f₁₀(y) = , y, ¬y - отрицание y, инверсия y ;

читается « не y», « неверно, что y».

f₁(x, y) = x&y, хy, xy - конъюнкция, логическое умножение;

читается « х и y ».

f₇(x, y) = xy - дизъюнкция, логическое сложение;

читается « х или y ».

f₆(x, y) = xy - сложение по модулю два,

дизъюнкция с исключением;

читается « х плюс y».

f₁₃(x, y) = x y - импликация, логическое следование;

читается « х импликация y », « х влечёт y».

«если x, то y».

f₉(x, y) = xy , x~ y - эквиваленция, эквивалентность;

читается «х эквивалентно y »;

f₂(x, y) = xy = (xy) - антиимпликация, левая коимпликация;

читается « x не имплицирует y».

f₈(x, y) = xy = (xy) - стрелка Пирса, антидизъюнкция,

функция Вебба, функция Даггера;

читается «х стрелка Пирса y».

f₁₄(x, y) = x|y = (xy) - штрих Шеффера, антиконъюнкция;

читается « х штрих Шеффера y »

f₁₁(x, y) = y x - обратная импликация;

читается « y импликация x », « y влечёт х». «если y, то x».

f₄(x, y) = xy = (yx) - правая коимпликация;

читается « y не имплицирует x ».

Приложение 2. ПРАВИЛА РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ ФОРМУЛ

№	Название	Формулы для дизъюнкции	Формулы для конъюнкции
ТЕОРЕМЫ БУЛЕВОЙ АЛГЕБРЫ ( доказываются подстановкой значений переменных )
1	операции с константами	a 0 = a	a &0 = 0
		a 1 = 1	a & 1 = a
2	одинаковость, (идемпотентность	a a = a a a … a = a	a & a = a a&a&…&a= a
3 4	«исключенного третьего», противоречие	aa=1 ……………………	- aa=0
5	снятие двойного отрицания	a=a
ЗАКОНЫ ( ТОЖДЕСТВА )
6	переместительный	a b = b a	ab = ba
7	сочетательный	a(ba)= (ab)c = = abc	a(bc) = =(ab)c=abc
8	распределительный	a(bc) = abac	abc = =(ab)&(ac)
9	де Моргана	(ab) = a&b=ab. (a b … z) = = ab … z.	(ab) = ab (a&b&…& z)= =ab…z
ПРАВИЛА ( доказываются с помощью законов распределительного, противоречия и «исключенного третьего»)
10	склеивание	abab = a	(ab) (ab)=a
11	поглощение	aab = a	a(ab) = a
	Блейка-Порецкого	a(ab) = ab	a(ab) = ab
12	снятие импликации	ab = ab
13	снятие эквиваленции	ab = (ab)(ba) = abab

Рецензия

на учебное пособие доцента М.Я. Товштейна

«ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ»

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

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

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

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

Заведующий кафедрой информационных систем

Набережночелнинского института Казанского (Приволжского)

федерального университета, канд.физ.-мат.наук, доцент

Валиев Р.А.