Лекции - Дискретная математика - файл n2.doc

Лекции - Дискретная математика
скачать (55.8 kb.)
Доступные файлы (1):
n2.doc255kb.17.10.2008 16:40скачать

n2.doc

1   2   3   4   5   6

Лекция 3

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



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

  1. Табличный

X1 X2 X3 … XN

F(X)

0 0 0 0 0 0 0 0 0







1 1 1 1 1 1 1 1 1

n



значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

  1. Векторный

F = (n)

3. Геометрический

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

Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.

Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.


  1. В виде формулы.

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

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

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

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


X


0


X

_

X


1

0

0

0

1

1

1

0

1

0

1



Таблица всех элементарных булевых функций, применяемых в записи формул




X


Y


0


&

_____

YX


X

___

XY


Y


+


V





~

_

Y


X Y

_X


YX


/


1

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


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

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

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

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

Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов.

  1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

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


Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)
Ф(1) – множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если

 g Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

Конкретное выражение суперпозиции будем называть формулой над системой Ф.

G = Fф

Суперпозиция элементарных булевых функций – формула.

Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны.

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

__

X  Y = X V Y

_ _

X  Y = X Y
1   2   3   4   5   6


Лекция 3 Определение и способ задания булевых функций
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации