Главная | Обратная связь

ТАБЛИЧНОЕ ЗАДАНИЕ БУЛЕВСКИХ ФУНКЦИЙ

БУЛЕВСКИЕ ФУНКЦИИ

 

 

НАЧАЛЬНЫЕ ПОНЯТИЯ

Пусть E₂ ={0,1}.

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

 

ОПРЕДЕЛЕНИЕ

Всякое отображение , где n Î N, называется булевской функцией.

Вместо полного наименования “булевская функция” допустимо использование сокращения - б.ф. Название является историческим и связано с близостью таких функций к исследовавшимся математиком Булем теоретико-множественным и логическим структурам. Для булевских функций применяется и другое наименование - функции алгебры логики (ф.а.л.). В настоящем пособии будет преимущественно использоваться первое наименование.

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

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

Если логическая форма U учитывает факторы F₁ , . . . , F_n, то функция истинности для значений U в зависимости от значений F₁ , . . . , F _n - это некоторая булевская функция .

Множество всех булевских функций обозначается как P₂.

Пусть . Будем использовать символы переменных x₁, . . . , x_n для обозначения первой, второй, . . . , n-й компонент двоичных наборов, являющихся элементами области определения f.

Если задан произвольный двоичный набор (s₁,..., s_n), то значение s_iбудет называться значением переменной x_i.

ТАБЛИЧНОЕ ЗАДАНИЕ БУЛЕВСКИХ ФУНКЦИЙ

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

Если , то соответствующая таблица имеет вид:

x1 x2. . . x n	f(x1 ,. . . , xn)
0 0. . .0	f(0 , . . . ,0)
. . .	. . .
s1 s2 . . . sn	f(s1, s2, . . , sn)
. . .	. . .
1 1. . .1	f(1, . . . , 1)

 

Приведенная таблица имеет 2ⁿ строк и n +1 столбец. В первых n элементах строк таблицы задаются все возможные наборы значений переменных x₁, . . . , x_n. Поэтому таблица имеет 2ⁿ строк. Последний элемент всякой строки содержит значение функции на наборе значений переменных этой функции, выписанном левее этого элемента в той же строке.

При этом двоичные наборы значений переменных x₁, . . . , x_n в строках выписываются в порядке возрастания значений двоичных чисел, представляемых этими наборами. Это означает, что для задания произвольной функции f достаточно указать последний столбец табличного задания этой функции. Такой столбец является двоичным набором, содержащим 2ⁿэлементов. Следовательно, многообразие всех возможных функций алгебры логики определяется множеством всех двоичных наборов длины 2ⁿ. Поэтому существует ровно различных булевских функций . Множество всех таких б.ф. обозначается как .

 

 

4.3.СУЩЕСТВЕННАЯ ЗАВИСИМОСТЬ ФУНКЦИЙ
ОТ ПЕРЕМЕННЫХ

ОПРЕДЕЛЕНИЕ

Булевская функция f (x₁ , . . . , x_n) существенно зависит от переменной x_i если: $ s₁, . . . , s _i-1, , s _{i +1} . . , s_n Î E₂

(f(s₁, . . . , s_i-1, 0, s _{i +1} . . , s_n) ¹ f (s₁, . . . , s_i-1, 1, s_{i +1} . . , s_n)).

 

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

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

" s₁, . . . , s _i-1, , s _{i +1} . . , s_n Î E₂

(f(s₁, ... , s _i-1, 0,s_{i +1}, … , s_n) = f(s₁, ..., s_i-1, 1, s_{i +1}, …, s_n)).

 

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

Для лучшего понимания явления существенности переменных рассмотрим следующие два вопроса:

 

1)как по заданной функции из P₂ можно просто определить ее существенные и несущественные переменные?

2) если некоторая переменная булевской функции несущественна, то в каком смысле эта б.ф. является функцией меньшего числа переменных?