Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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). Здесь б₁ < в₁ , б₂ > в₂ .