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

Печатается по решению редакционно-издательского совета Набережночелнинского института Казанского (Приволжского) федерального университета от 25.04.14 Матросова, доктор техн. наук, профессор, зав.кафедрой программирования Национального Исследовательского Томского госуниверситета, Р.А.Валиев, к.ф.-м.наук, доцент, зав.кафедрой информационных систем Набережночелнинского института Казанского Им нужно знать логические основы компьютера и пользоваться командами развилки и цикла при создании программ для компьютеров. Но детально эти функции изучаются в рамках вузовской дисциплины «Математическая логика». Именно функционально полные системы булевых функций позволяют создавать те конструктивные элементы, из которых строятся сколь угодно сложные системы управления цифровыми автоматами.Благодаря критерию Э.Л.Поста можно определить, какие функции образуют функционально полную систему (ФПС), и принимать решение, какие элементы стоит изготавливать для того, чтобы из них можно было конструировать сколь угодно сложные дискретные управляющие устройства. Вы узнали, что такое ФПС булевых функций и что такое замкнутый класс, какие функции образуют замкнутый класс, какова мощность того или иного замкнутого класса и какие замкнутые классы надо исследовать, чтобы опознать ФПС. Хотелось бы надеяться, что Вам, уважаемый читатель, стали немного ближе и Джордж Буль, который уже в 12 лет самостоятельно изучил пять языков, и непонятый современниками Огастес де Морган, и умерший в бедности и забвении философ Чарльз Сандерс Пирс, и не публиковавший своих исследований Генри Морис Шеффер, и альпинист, громкоголосый любитель анекдотов Стефен Коул Клини, и страдающий от психической болезни однорукий Эмиль Леон Пост, и наш российский математик Иван Иванович Жегалкин, который не побоялся протестовать против политики тогдашнего министра просвещения. Поскольку перед вами не учебник, а пособие, ограниченное только одной темой, остались в стороне другие, не менее интересные вопросы, имеющие отношение к булевым функциям. Например, какими техническими элементами реализуются булевы функции, как минимизировать их количество без ущерба для функционирования построенного цифрового устройства, как из этих элементов синтезировать цифровой автомат с заданными управляющими параметрами и др.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В заключение отмечу вот что. Мне знаком неподдельный интерес студентов к личностям ученых, чьи фамилии звучат в названиях формул и теорем. Учитывая это, а также тот факт, что наши учебные программы не предполагают удовлетворение этого интереса, я позволил себе в пособие включить параграф с краткими сведениями о следующих упомянутых в брошюре математиках: БУЛЬ Джордж, де МОРГАН Огастес, ПОСТ Эмиль Леон , КЛИНИ Стефен Коул, ШЕФФЕР Генри Морис, ПИРС Чарльз Сандерс, ЖЕГАЛКИН Иван Иванович

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

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

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

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

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

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

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

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

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

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

Определение. Пусть даны булевы функции g(y1,…,ym), f1(x1,…,xn), …, fm(x1,…,xn).

Суперпозицией этих булевых функций будем называть функцию f(x1,…,xn), если она представима формулой g ( f1(x1,…,xn), .…, fm(x1,…,xn) ).

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

Пример. Пусть даны следующие функции: g(x,y,z)=xy®x" Az, f1(a,b)=AUB, f2(a,b,c)=ac?b, f3(a,b,c)=a®b®c.

Полагая x=f1(a,b), y=f2(a,b,c) и z=f3(a,b,c), внесем эти формулы в формулу, представляющую функцию g(x,y,z), и получим суперпозицию исходных функций: f(a,b,c)=(AUB)(ac?b) ® (AUB)" A (a®b®c).

Пояснение. Обратите внимание, что функции f1, f2, …, fm в определении суперпозиции зависят от одинакового количества аргументов. В этом примере функция f1 зависит от двух аргументов, f2 и f3 - от трех аргументов, то есть количество аргументов у функций, чья суперпозиция рассматривается, различно. Так бывает в большинстве практических задач. Чтобы «совместить практику с теорией» и соответствовать вышеприведенному определению, надо вспомнить, что всегда можно добавлять в соответствующие функции недостающие фиктивные аргументы. В нашем примере функция f1 могла быть представлена, скажем, так: f1(a,b,c) = (AUB)(CUC"). Теперь и здесь стало три аргумента, как в f2 и f3.

***

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

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

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

Примером такой полной системы является a0 ={&,U,O}.

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

Лемма о достаточном условии полноты. Пусть система a={f1,f2,…,fm} - ФПС, и любая из входящих в нее функций может быть выражена с помощью суперпозиции через функции некоторой другой системы a ={g1, g2, …, gk}. Тогда система a тоже ФПС.

Доказательство. Возьмем произвольную булеву функцию f. Поскольку система a по условию леммы является полной, можно f представить как суперпозицию функций, взятых из a, то есть соответствующая формула может иметь следующий вид f = f(f1, f2, …, fm).

В свою очередь, по условию леммы каждая функция fi I a , i=1, …, m, участвующая в построении этой формулы, может быть выражена формулой над a , то есть с помощью функций GJIA : f1=f1(g1,g2,…,gk), f2=f2(g1,g2,…,gk), . . . . . . . . . . fm=fm(g1,g2,…,gk).

Заменим в формуле f(f1, f2, …, fm) вхождение каждого символа функции FIIA ( i=1,…, m) соответствующей формулой над a : f(f1, f2, …, fm) = f(f1(g1,g2,…,gk), …, fm(g1,g2,…,gk)).

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

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

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

1. Докажем сначала, что системы a1={&,O} и a2={U,O} функционально полны. Для этого покажем, что любая функция из a0 выражается через a1 или a2.

Действительно, из законов де Моргана и отрицания следует, что в каждой из этих двух систем недостающая до a0={&,U,O} функция выражается через остальные две: XUY=( х" y")"; xy=( х" U y")" (1)

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

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

2. Докажем, что функционально полны также и системы, состоящие каждая из одной единственной функции: a3={?} (штрих Шеффера) и a4={?}(стрелка Пирса).

Надо убедиться, что выполняется определение функциональной полноты системы, то есть что функции полной системы a0 = {&,U,O} выражаются через a3 = {?} и a4. ={?}.

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

Теперь посмотрим, как может быть представлена дизъюнкция. С учетом выражения инверсии через a3 и a4 , получим: XUY = (XUY)"" = (х?y)" = (х?y)?(х?y).

Аналогично этому получим формулу конъюнкции: х&y = (xy)"" = (х?y)"? (х?y)?(х?y).

Следовательно, a3 сводится к a1, а a4 сводится к a2. Принимая во внимание лемму о достаточном условии полноты и учитывая, что a1 и a2 - ФПС, делаем вывод, что a3 и a4 - тоже ФПС. O

3. Система a5={&,A,1}тоже функционально полна. Действительно, функция A выражается через инверсию: х"=XA1, и, следовательно, a5 сводится к a1={&,O}. Значит, a5 - ФПС по определению. O

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

4. Докажем функциональную полноту системы функций a = { x®y, ( XAYAZ)" }.

Для этого выразим функции известной ФПС a2={ x", XUY} через функции системы a . Получим:

1) x"=( XAXAX )".

2) XUY= x"®y = (XAXAX)" ® y.

В соответствии с леммой о достаточном условии полноты заключаем, что система a = { x®y, ( XAYAZ)" } является ФПС. O

***

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

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

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

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

2. Замкнутым классом является множество всех дизъюнкций вида x1Ux2U…Uxn , поскольку, как нетрудно увидеть, подстановка вместо какой-либо переменной xk, k=1,2,…,n, дизъюнкции вида y1Uy2 U…U ym снова даст дизъюнкцию.

***

Некоторые подмножества множества булевых функций также являются замкнутыми классами: § КЛАССТ0 функций, сохраняющих константу 0;

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

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

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

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

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

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

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

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

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

2. Функция f(х1,х2,х3)=х1х2"Ux1х2х3" принадлежит Т0. Действительно, f(0,0,0)=0&0"U0&0&0"=0.

3. Функция эквивалентности x«y I Т0, поскольку 0«0 = 1.

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

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

| T0 |=2К/2=-2К-1, где К=2n

Пример. Из всех 16 элементарных булевых функций f(х1,х2) в класс Т0 входят следующие восемь (n=2, К = 22 = 4, | Т0 | = 24-1 = 8): { 0, U, &, A, A, @ , х1, х2 }.

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

Доказательство. Пусть даны функции g(y1, …, ym), f1(x1, …, xn),…, fm(x1, …, xn), входящие в класс Т0. Условимся последующие выкладки для краткости проводить при m=3 и n=2. Подставим y1=f1(x1,x2), y2=f2(x1,x2), y3=f3(x1,x2) вместо аргументов в функцию g(y1, y2, y3) и покажем, что полученная суперпозиция на наборе из всех нулей принимает значение ноль. Заметим, что после подстановки получится функция от двух аргументов: g(y1,y2,y3) = g( f1(x1,x2), f2(x1,x2), f3(x1,x2) ) ? h(x1,x2).

Вычислим h(0,0). Учитывая, что f1(x1,x2)IT0, f2(x1,x2)IT0, f3(x1,x2)IT0 и g(y1,y2,y3)IT0, получим: h(0,0) ? g (f1(0,0), f2(0,0), f3(0,0)) = g(0,0,0) = 0.

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

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

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

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

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

{ 1, U, &, «, ®, ¬, х1, х2 }.

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

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

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

Мы познакомились в разделе 1.2 с ФПС a5={&,A,1}. Эта система интересна тем, что позволяет провести аналогию между арифметическими операциями умножения и сложения чисел 0 и 1 и булевыми операциями & и A над булевыми константами 0 и 1. В самом деле, конъюнкция х&y подобна операции умножения над числами 0 и 1, а операция XAY похожа на операцию сложения: 0 0=0; 0 1=1 0=1. Если теперь понимать под числами 1 и 0 числа двоичной системы счисления, то арифметическую операцию сложения 1 1 можно считать подобной логической операции A и вместо знака A пользоваться знаком .

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

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

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

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

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

Р1(х1,х2) = a0 а1х1 а2х2 а12х1х2 , а ПЖ от трех переменных - вид

Р1(х1,х2,х3)=а0 а1х1 а2х2 а3х3 а12х1х2 а13х1х3 а23х2х3 а123х1х2х3.

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

Построить полином Жегалкина можно следующими способами: 1) воспользовавшись таблицей истинности и неопределенными коэффициентами, как описано в теореме;

2) преобразованием исходной формулы по следующему правилу: а) преобразовать формулу так, чтобы использовались только операции & и O;

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

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

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

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

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

Пример 1. Методом неопределенных коэффициентов найдем ПЖ для f(x,y)=x®y. f(x,y)=a0 а1х а2y a3xy f(0,0)=1=a0 a10 a20 a30=a0 ………… . a0=1 f(0,1)=1=1 a10 a2y a30. 1=1 a2 … a2=0 f(1,0)=0=1 a11 0y a310. 0=1 a1 …...a1=1 f(1,1)=1=1 1 0y a311=1 1 a3=a3 ….. a3=1

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

Пример 2. Преобразованием формул найдем ПЖ для импликации и дизъюнкции, учитывая, что x" = х 1 и y" = y 1: x®y=x"Uy=(x"Uy)""=(x&y")"=(x(y 1))"=x(y 1) 1=xy x 1.

XUY = (XUY)""=(x"&y")"=((x 1)(y 1))"=(xy y x 1) 1=xy x y.

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

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

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

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

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

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

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

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

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

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

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

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

P(x1,…,xn)= ?0 ?1x1 ?2x2 … ?nxn, ?II{0,1}, i=0,…,n. (*)

Например, все функции одной переменной имеют вид f(x) ? Р(х) = ?0 ?1x.

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

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

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

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

Известно, что x«y = (x®y)(y®х). Используя формулу x®y=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. Функция XUY = xy x y - нелинейная, что видно из рассмотренного выше примера 2.

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

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

Доказательство. Известно, что полином Жегалкина линейной функции f(x1, …, xn) имеет вид P(x1, …, xn)= ?0 ?1x1 ?2x2 … ?nxn.

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

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

(n=2, |L|= 22 1 =8)

{0, 1, A, «, х1, х2, х1", х2"}.

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

Доказательство этой теоремы подобно доказательству теоремы о замкнутости класса Т0. Пусть даны функции g(y1,…,ym), f1(x1,…,xn),…, fm(x1,…,xn), входящие в класс L. Условимся, не нарушая общности, следующие рассуждения проводить для m=3 и n=2.

Подставим y1=f1(x1,x2), y2=f2(x1,x2), y3=f3(x1,x2) вместо аргументов в функцию g(y1,y2,y3) и покажем, что полученная суперпозиция также будет линейной функцией. Заметим, что после подстановки получится функция от двух аргументов: g(y1,y2,y3)=g( f1(x1,x2), f2(x1,x2), f3(x1,x2) )? h(x1,x2) (1)

Учтем, что функции g, f1, f2 и f3 линейны, и представим их полиномами Жегалкина: g(y1,y2,y3) = ?0 ?1y1 ?2y2 ?3y3 , f1(x1,x2) = ?01 ?11x1 ?21x2 , f2(x1,x2) = ?02 ?12x1 ?22x2 , (2) f3(x1,x2) = ?03 ?13x1 ?23x2 .

Напомним, что в ПЖ все коэффициенты при переменных равны 0 или1: ?j, ?IKI{0,1}, j=0,1,2,3; i=0,1,2; k= 1,2,3. (3)

Формула (1) после подстановки полиномов (2) примет следующий вид: g(y1,y2,y3)=a0 a1(?01 ?11x1 ?21x2) a2(?02 ?12x1 ?22x2)

a3(?03 ?13x1 ?23x2)=

=(a0 a1?01 a2?02 a3?03) (a1?11 a2?12 a3?13)x1

(a1?21 a2?22 a3?23)x2?

?h(x1,x2).

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

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

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

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

1 (XYUX"y)Az 7 (1000 1110)

2 x"y U y"z U z"TU t"x 8 xyz"Uxy"

3 xy(XAY) 9 (0110 0111)

4 (x®y)(y®x)«z 10 (1001 0110)

5 XYZU(XAYAZ)" 11 (x ? y)?(y?z)

6 (x®y)" A x"y 12 (XAY)(x"Uy")

3.

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

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

Определение. Будем называть булеву функцию f*(x1,x2,…,xn), n?1, двойственной относительно функции f(x1,x2,…,xn), если она получена из f(x1,x2,…,xn) инверсией всех аргументов и самой функции: f*(x1, x2,…, xn) ? f "(x1", x2",…, xn").

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

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

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

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

Заметим, что то же самое получим, если применить формулы равносильных преобразований: f*(x1,x2)=(х1"Ux2")"=(х1&х2)""=x1&x2.

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

Действительно, f*(x1,x2)=(х1"х2")" = (х1Ux2)"" = х1Ux2.

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

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

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

Еще раз убедимся в этом, используя приведенное замечание. Известно, что стрелка Пирса - это функция НЕ-ИЛИ: х1?х2=(x1Ux2)".

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

f*(x1,x2)=(x1&x2)" = х1|х2

Пример 11. Построим функцию, двойственную импликации, с учетом замечания. f(x1,x2)= х1®х2= х1" U x2 .

Заменив U на &, получим f*(x1,x2)= х1"&x2 = х1@x2 .

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

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

Оказалось, что для f(x1,x2)=х1 х2 двойственной функцией будет f*(x1,x2)= х1«х2.

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

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

Хотелось бы надеяться, что Вам, уважаемый читатель, стали немного ближе и Джордж Буль, который уже в 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. Большая советская энциклопедия [Электронный ресурс]. Режим доступа: ПОЛНОТА

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

14. Википедия. [Электронный ресурс] Режим доступа: http://ru.wikipedia.org/wiki/Буль,_Джордж

15. Энциклопедический словарь. [Электронный ресурс] Режим доступа: Буль

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, [Электронный ресурс] Режим доступа: 19. J J OCONNOR and E F Robertson. Stephen Cole Kleene. MACTUTOR History of Mathematics. [Электронный ресурс] Режим доступа: 20. J J OCONNOR 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. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ ОПРЕДЕЛЕНИЕ ТАБЛИЦЕЙ ИСТИНОСТИ

НАЗВАНИЯ И ОБОЗНАЧЕНИЯ f0 = 0 - константа 0. f15 =1 - константа 1. f3(x) = x - переменная x (тождественная функция). f5(y) = y - переменная y (тождественная функция). f12(x) = , x?, ¬x - отрицание x, инверсия x;

читается « не x», « неверно, что x ». f10(y) = , y?, ¬y - отрицание y, инверсия y ;

читается « не y», « неверно, что y». f1(x, y) = x&y, х y, xy - конъюнкция, логическое умножение;

читается « х и y ». f7(x, y) = XUY - дизъюнкция, логическое сложение;

читается « х или y ». f6(x, y) = x y - сложение по модулю два, дизъюнкция с исключением;

читается « х плюс y». f13(x, y) = x ® y - импликация, логическое следование;

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

«если x, то y». f9(x, y) = x«y , x~ y - эквиваленция, эквивалентность;

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

f2(x, y) = XAY = (x®y)? - антиимпликация, левая коимпликация;

читается « x не имплицирует y». f8(x, y) = xy = (XUY)? - стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера;

читается «х стрелка Пирса y». f14(x, y) = x|y = (xy)? - штрих Шеффера, антиконъюнкция;

читается « х штрих Шеффера y » f11(x, y) = y ® x - обратная импликация;

читается « y импликация x », « y влечет х». «если y, то x». f4(x, y) = x@y = (y®x)? - правая коимпликация;

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