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

 

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

Таким множеством может быть бинарное множество .

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

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

Под двоичным набором  понимается совокупность значений аргументов  ПФ.

Иногда двоичные наборы в таблицах истинности удобно представлять номерами наборов:

№ набора= .

Значения функций на 2ⁿ-наборах также могут быть заданы десятичным номером:

№ функции= .

При геометрическом способе ПФ задается с помощью соответствующей отметки вершин n-мерного куба, который, по сути, является решеткой Хассэ, представляющей собой частично упорядоченное множество наборов (каждая вершина – точка n-мерного пространства) [9]. Каждый путь из вершины, соответствующей нулевому набору в вершину единичного набора, соответствует увеличению сравнимых наборов (рис. 28, отношение ³).

 

Рис.28. Геометрическое представление переключательной функции

 

Этот рисунок изображает частично упорядоченное множество наборов 000, 001, 010, 011, 100, 101, 110, 111, на которых задана переключательная функция трех переменных, например, a, b, c. Вершины, на которых функция равна 1 должны быть как-то отмечены.

Переключательная функция может быть задана и некоторым словесным описанием, указывающим, на каких наборах аргументов какое значение она принимает и исключающим неверное толкование, всякую двусмысленность. Переключательная функция может быть задана перечислением ее рабочих (единичных), запрещенных (нулевых) и условных наборов (на этих наборах функция не определена). Для упорядоченного задания n-мерных наборов переменных функции f(x₁,x₂,...,x_n) удобно рассматривать их в виде целого неотрицательного числа. При этом младший разряд располагается справа. Например, для переменных х₅,х₄,х₃,х₂,х₁ конкретное их значение истинности 1,0,0,1,1 соответствует двоичному числу 10011. Это число еще называют номером набора. Для компактной записи наборов значений переменных логической функции, целесообразно представлять их номерами – числами в десятичной, восьмеричной, шестнадцатеричной системах счисления. Такой номер-набор называют еще весовым состоянием или весом этого набора.

Так, 10011₂«19₁₀«23₈«13₁₆.

В случае использования десятичной системы счисления каждой переменной соответствует степень числа 2 (вес разряда) в зависимости от номера переменной, например, в порядке 2⁴2³2²2¹2⁰. Зафиксированный порядок переменных, каждая из которых имеет свой вес, называется базой функции (старший вес – слева). Как мы знаем, переключательная (логическая) функция может быть задана таблицей истинности, которая иногда еще называется таблицей соответствия. Рассмотрим таблицу истинности некоторой недоопределенной логической функции (табл. 11).

Таблица 11

Таблица истинности

22 х3	21 х2	20 х1	ВС	z
0	0	0	0	0
0	0	1	1	~
0	1	0	2	1
0	1	1	3	~
1	0	0	4	0
1	0	1	5	1
1	1	0	6	~
1	1	1	7	0

 

Этой таблице соответствует переключательная (логическая) функция

z(x₃x₂x₁)=2,5[0,4,7]{1,3,6}.

Здесь зафиксирована база переменных функции z – х₃х₂х₁ (в табл. 11 над этими переменными указан их вес и введен столбец весового состояния ВС), перечислены рабочие наборы в десятичном коде – 2,5, запрещенные наборы в квадратных скобках – 0,4,7 и условные наборы в фигурных скобках – 1,3,6. Такое задание функции будем называть символической формой.

Пусть задана переключательная функция f(х₅х₄х₃х₂х₁) рабочими двоичными наборами 10011, 01010, 11000 и двоичными запрещенными наборами 00111, 00101. Тогда в восьмеричной системе счисления имеем следующую символическую форму:

f(x₅x₄x₃x₂x₁)₈=23,12,30[07,05],

а в шестнадцатеричной форме

f(x₅x₄x₃x₂x₁)₁₆=13,0А,18[07,05].

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

Таблицу истинности можно представить в двухмерном виде, который, как уже говорилось, называется картой Карно (табл. 12-13).

Таблица 12

Одномерная таблица истинности некоторой функции

22 х3	21 х2	20 х1	ВС	z
0	0	0	0	0
0	1	0	2	1
1	0	0	4	0
1	0	1	5	1
1	1	1	7	0

 

Таблица 13

Двухмерная таблица истинности

 

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

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

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