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

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

Способы задания функций

1. Табличный

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

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

2. Векторный

F = (g_1...g_n)

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

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

Носителем данной функции – совокупность всех единичных векторов этой функции (N_f – носитель функции f)

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

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

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

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

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

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

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

Строим таблицу функций при n = 1.

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

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

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

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

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

Ф = {ф₁…ф_k}

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

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

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

Ф₁ = {Y…x_n}

Фi = (x1 … ф_j(x₁…x_n) … x_n)

Ф⁽¹⁾ – множество всех элементарных суперпозиций из системы Ф.

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

Функция g называется суперпозицией функций из системы, если

$ N : g Î Фⁿ

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

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

G = F_ф

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

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

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

__

X ® Y = X V Y

_ _

X ¯ Y = X Y

Лекция 4