Булева алгебра (стр. 5 )

1.Какие из элементарных функций двух аргументов принадлежат классу?

2. Какие из элементарных функций двух аргументов принадлежат классу ?

Упражнение №2:

Определить принадлежит ли функция классу; классу .

f(x, y)=(0,1,1,1);

f(x, y)= (1,1,1,1);

f(x, y)= (0,1,1,0);

f(x, y)= (0,0,1,0,1,0,1,1,1);

f(x, y)= (1,0,1,0,1,0,1,1,1);

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

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

В математическом анализе исследовались многие функции на возрастание и убывание. Например, функция всегда возрастает, причем возрастает на всей области определения, поэтому ее можно назвать монотонной. Функция вначале убывает на промежутке , а затем возрастает на промежутке . Эта функция не монотонна. Монотонная функция ведет себя одинаково на всей области определения. Посмотрим, какая функция называется монотонной в дискретной математике.

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

Пусть даны два набора а и b: ; , где и , - двоичные значения отдельных разрядов наборов а и b. Если одновременно выполняются условия: , ,..., , то пишут и говорят, что набор b не меньше набора а. Такие наборы называются сравнимыми. Все остальные наборы являются несравнимыми. Например, относительно наборов и нельзя сказать, что, либо , так как для первых разрядов имеем: (1 >0), а для вторых (0>1).

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

Таблица 5

xyz	f
000 001 010 011 100 101 110 111	0 0 0 1 0 1 1 1

При переходе с набора 010 на сравнимый с ним набор 011 функция возрастает, а при переходе с набора 011 на несравнимы с ним набор 100 - убы­вает.

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

Утверждение: если функция представлена в виде дизъюнкции конъюнкций (ДНФ) и в ней отсутствуют инверсные аргументы, то функция является монотонной.

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

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

Упражнение №1:

Укажите нары, содержащие сравнимые наборы:

1.	00001 и 00011
2.	1001 и 1001
3.	10001 и 01110
4.	0010 и 1100
5.	10001 и 11101

Упражнение №2:

Укажите номера наборов, которые не меньше набора 10001:

1)11001

2)01110

3)11011.

Упражнение №3:

Определите какие из функций являются монотонными.

1.

2.

3.

4.

5. ;

6. ;

Упражнение №4:

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

1. ( 0,1,1,1);

2. (0,0,0,0);

3. (0,1,1,1,0,1,1,1);

4. (1,0,1,1,1,0,1,1);

5. (0,0,0,0,1,1,1,1);

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

Функция f(x, y)=является суперпозицией функций инверсий и конъюнкций. Функция g(x, y)=x→(xy) является суперпозицией функций импликации и суммы по модулю два . Функция h(x, y,z)=(xy)~z является суперпозицией функций и ~.

Определение. Функция =называется двойственной функцией к функции f и обозначается f*.

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

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

Пример:

Запомните!(0)*=1

(1)*=1

(x)*=

Рассмотрим функции двойственные к элементарным. Функция двойственная к дизъюнкции есть конъюнкция. Докажем это:

(по правилу де Моргана).

~y)*=

()*=~y

(x/y)*=↙y

(↙y)*=x/y

Рассмотрим ещё один пример получения двойственной функций по определению.

, тогда

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

Теорема (принципа двойственности): Функция двойственная суперпозиции функций, равна суперпозиции двойственных функций. Точнее

Пример нахождения двойственных функций по принципу двойственности:

; ~(z↙(xy).

Упражнение №1:

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

a.  \/yz; d. f=x\/\/;

b.  \/ ; e. f=/\/\c;

c.  \/; f. f=x\/yz;

Упражнение №2:

Найти функцию двойственную к данной по таблице истинности:

a)  f(1,1,0,1);

b)  f(1,0,0,1);

c)  f(0,1,1,1,0,1,1,1);

d)  f(0,1,1,1,1,0,0,0);

e)  f(1,1,0,1,0,1,1,0);

f)  f(1,1,1,1,0,1,0,1,0,0,0,0,1,0,1,0);

g)  f(1,0,0,1,0,0,0,1,0,0,1,1,0,0,1,1).

Упражнение №3:

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

a)  f=(x\/y)(z\/(x~y));

b)  f=(xz\/y)/((z⊕x)\/y);

c)  f=x\/((y~xz)⊕xy/\(z↙x));

d)  f=x⊕(xz/\(~z/\(y/);

e)  f=z~((x\/y)/(z/\()));

f)  f=((xy⊕yz)\/xz)↙.

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

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

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

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

По заданному набору найти набор противоположный ему очень легко: достаточно в заданной двоичной последовательности нули заменить единицами, а единицы - нулями. Например, если 01100 - заданный набор, то противоположный ему - 10011.

В таблице 1 перечислены все четырехзначные наборы значений аргументов .

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

Таблица 6

	f f*
	1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0

В таблице наблюдается своеобразная симметрия: наборы, расположенные на одинаковых расстояниях от начала и конца таблицы являются противоположными. Это значит, что в диапазоне наборов 0в колонке, где записываются значения функции, единицы и нули можно располагать произвольным образом. При этом всякий раз будет получаться самодвойственная функция, если на противоположных наборах всю записывать противоположные значения функции. В таблице 1 приведен пример самодвойственной функции.

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

1) Во-первых, можно найти по определению функцию двойственную к данной, и проверить совпадет ли двойственная функции самой функцией.

Пример

Пусть, тогда

.

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

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

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

Примеры:

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

2) f(х, у)=(0,1,0,1,0,1,0,1) заменяем значения в векторе на обратные (1,0,1,0,1,0,1,0) и переворачиваем весь вектор f*(x, y,z)=(0,1,0,1,0,1,0,1) эта функция самодвойственная.

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

Упражнение №1:

Какие из элементарных функций двух аргументов принадлежат классу S?

Упражнение №2:

Определить принадлежит ли функция классу S?

;

;

;

;

;

.

Упражнение №3:

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

( 0,1,1,1);

(0,1,1,0);

(0,0,1,0,1,0,1,1);

(1,0,1,0,1,0,1,1);

(0,0,1,0,1,0,1,1,0,1,0,0,1,0,1,1).

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

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

Определение. Полиномом Жегалкина назовем выражение, в котором нет знаков инверсий, а конъюнкции переменных соединяются операцией суммой по модулю два.

Несколько примеров полиномов Жегалкина

Рассмотрим ряд тождеств, которые нам понадобятся в дальнейшем.

1.

2.

3., если количество слагаемых четное.
, если количество слагаемых нечетное.

4. – дистрибутивный закон.

Теорем а: Любую булеву функцию можно представить в виде полинома

Жегалкина.

Пусть дана функция преобразуем ее и полином Жегалкина.
=[пpименяем тождество 1 к]= =[применяем тождество 2 к ()]===[применяем тождество 4] .

Определение. Линейным полиномом Жегалкина назовем выражение вида:

,

где - коэффициенты, принимающие значение либо нуля либо единицы, - переменные.

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

Примеры линейных полиномов:

здесь коэффициенты .

Линейные функции

Любую функцию можно представить полиномом Жегалкина, но не любую можно представить лишь полиномом Жегалкина.

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

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

Как определить является ли функция линейной?

1) Необходимо представить функцию в виде полинома,

2) проверить является ли линейным.

Например: х~у - линейна;

х→у - не линейная, так как в полиноме есть конъюнкция.

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

Упражнение №1:

Представьте в виде полинома Жегалкина функции

1. 4.

2. x/y 5.

3. 6.

Упражнение №2:

Какие из элементарных функций являются линейными?

Какие из функций упражнения № 1 принадлежат классу L?

Теорема Поста о функциональной полноте

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

Критерий полноты системы дает теорема Поста:

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

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

Как пользоваться теоремой Поста?

Пусть дана система функций , где , , .

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

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

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

x	y	x/y
0	0	1
0	1	1
1	0	1
1	1	0

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

Покажем, что эта функция не линейная

х/у (нелинейный полином).

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

Упражнение:

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

{0, 1, , };

{х, х/\у};

{,, };

{х/\у, 0 , х→у};

{ }.

СПИСОК ЛИТЕРАТУРЫ

1.  , Сапоженко задач по дискретной математике./. – М.: Наука, 1977. – 368 с.

2.  Горбатов дискретной математики./ . – М.: Высшая школа, 1986. – 311 с.

3.  Корниенко математика./. – Томск: ТПУ, 1996. – 95с.

4.  , Максимова по теории множеств, математической логике и теории алгоритмов./. – М.: Физматлит, 2002. – 256 с.

5.  Введение в математическую логику./Э. Мендельсон. – М.: Наука, 1971.– 320 с.

6.  , Осипова дискретной математики./. – М.:Изд-во МАИ, 1992. – 264 с.

7.  Смыслова логика и ее приложения./. – Томск: ТАСУР, 1994. – 111с.

8.  и др. Современная математика./Р. Фор. – М.: Мир, 1966. – 271 с.

9.  Математика в науке и вокруг нас./Г. Фрейденталь. – М.: Мир, 1977. – 261 с.

10.  Шевелев математика. Дискретная математика. Ч. 1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Уч. пособие./. Томск: ТАСУР, 1998. – 114 с.

11.  Новиков математика для программистов. Учебник для вузов. 2-е изд./. – СПб.: Питер, 2005. – 364 с.

БУЛЕВА АЛГЕБРА

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

Составитель

Печатается в редакции составителя

Подписано к печати 31.05.12

Формат 60х84/16. Бумага офсетная.

Плоская печать. Усл. печ. л.2,56. Уч-изд. л.2,32

Тираж 20 экз. Заказ 1531. Цена свободная.

ИПЛ ЮТИ ТПУ. Ризограф ЮТИ ТПУ.

Юрга, .