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

Функция 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 может быть представлена формулой , т.е. данная функция не зависит от х₃.

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

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

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

Если логическая функция, зависящая от n переменных, записана в виде дизъюнкции элементарных конъюнкций ЭК₁ÚЭК₂Ú...ÚЭК_r и хотя бы одна ЭК не содержит все n переменных, то такая форма задания называется дизъюнктивной нормальной формой (ДНФ). ДНФ – дизъюнкция конечного множества попарно различных элементарных конъюнкций.

Например: f(аbсd)=аÚ Úbd.

Произвольная функция, например, так называемая скобочная форма, может быть приведена к ДНФ следующим образом:

• выполнить все операции инверсии, применяемые к логическим выражениям (группе переменных);

• раскрыть все скобки;

• в полученном выражении произвести все упрощения.

Например:

f(х₁х₂х₃)= =

= = =

= = .

Получили ДНФ функции f(х₁х₂х₃).

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

Пусть задана таблица истинности функции сложения по модулю 2 (Å) (табл. 32).

Таблица 32

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

а	b	z=аÅb
0	0	0
0	1	1
1	0	1
1	1	0

Тогда z(аb)= bÚа , т.е. это СДНФ.

Первый член СДНФ соответствует строке 01, второй – строке 10.

Элементарные конъюнкции, входящие в СДНФ функции, называются конституентами единицы (или минтермами). Конституента единицы обращается в 1 (истинна) на единственном наборе значений переменных. Так, подстановка входного набора 01 (база аb) обращает в 1 конституенту b ( 1=1). Если считать выражение z(аb) уравнением, то наборы 01, 10 – его решения.

От СДНФ легко перейти к номерам рабочих наборов в различных системах. Так: z(аb)®01₂Ú10₂®1₁₀Ú2₁₀.

Аналогично по СДНФ можно получить рабочие наборы, считая остальные запрещенными: z(аb)=1,2[0,3].

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

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

Пример.

Получили СДНФ.

Имеется способ получения СДНФ из ДНФ с использованием обобщенного кода, в котором для обозначения недостающих переменных в соответствующих позициях используются знаки «–» (или «~» – «тильда»), а для остальных – символы 0,1.

Пример.

Функцию представим в виде: 00-Ú0-1.

Тогда, подставляя вместо «–» всевозможные комбинации 0,1, получим:

Таким образом, получили номера 000, 001, 011, которые соответствуют членам СДНФ.

СДНФ переключательной функции, тождественно равной 1 (тождественно истинной), содержит 2ⁿ констинтуэнт (n – число переменных).

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

Выражение вида , содержащее множество попарно различных переменных или их инверсий, называется элементарной дизъюнкцией (ЭД).

Если переключательная функция, зависящая от n переменных, записана в виде конъюнкции элементарных дизъюнкций ЭД₁·ЭД₂·...·ЭД_r и хотя бы одна ЭД не содержит все n переменных, то такая форма задания называется конъюнктивной нормальной формой (КНФ). КНФ – конъюнкция конечного множества попарно различных элементарных дизъюнкций.

Например: f(аbсd)=а( Úс)(bÚd).

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

• заданную функцию инверсировать, получить ДНФ инверсной функции;

• ДНФ инверсной функции инверсировать еще раз, получить тождественную исходной функцию в КНФ;

• на каждом этапе следует производить необходимые упрощения.

Пример.

f(х₁х₂х₃)= ;

(х₁х₂х₃)= =

= ;

(х₁х₂х₃)= .

Получили КНФ.

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

Пример.

f(х₁х₂х₃)=

=

=

Если все элементарные дизъюнкции, входящие в КНФ, содержат все n переменных, от которых зависит функция, то такая форма называется совершенной конъюнктивной нормальной (СКНФ).

СКНФ может быть получена по запрещенным (нулевым) наборам функции, например по таблице истинности. Для получения СКНФ по таблице истинности необходимо составить элементарные дизъюнкции всех переменных для каждой строки таблицы, в которой функция равна 0. При этом в дизъюнкцию входит сама переменная, если ее значение равно 0, и отрицание переменной, если ее значение равно 1.

Так, для функции сложения по модулю 2 (табл. 32) СКНФ имеет вид:

.

Элементарные дизъюнкции, входящие в СКНФ функции, называются конституентами нуля (макстермами).

Конституента нуля обращается в нуль на единственном наборе переменных, который является запрещенным (нулевым) набором функции. Например, для функции сложения по модулю 2 конституента нуля (аÚb) обращается в 0 на наборе 00, а конституента нуля – на наборе 11.

От СКНФ можно перейти к номерам запрещенных наборов в различных системах счисления. Для получения двоичных номеров в порядке базы функции (например, аb) необходимо заменить символы переменных с инверсией на 1, а без инверсии – на 0 и записать вместо элементарных дизъюнкций соответствующие совокупности двоичных чисел.

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

Для преобразования КНФ в СКНФ можно выполнить дизъюнкцию каждой элементарной дизъюнкции, не содержащей i-ю переменную, с тождественно ложным выражением . Таких недостающих переменных может быть несколько; тогда надо добавлять соответствующие тождественно истинные выражения. Затем применяется распределительный закон и производятся необходимые упрощения.

Например:

Соответствующие запрещенные наборы: 100, 110, 101, 111, 010 (база х₁х₂х₃).

Получим СДНФ и СКНФ ПФ, заданной десятичным номером №174₁₀.

Таблица истинности ПФ №174₁₀ показана в табл. 33

Таблица 33

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

переменные			ВС	f(abc)
а	b	с
0	0	0	0	0	20
0	0	1	1	1	21
0	1	0	2	1	22
0	1	1	3	1	23
1	0	0	4	0	24
1	0	1	5	1	25
1	1	0	6	0	26
1	1	1	7	1	27

СДНФ – совершенная дизъюнктивная нормальная форма:

СКНФ – совершенная конъюнктивная нормальная форма:

14 Основные бинарные логические операции

Конъюнкцией называется бинарная логическая операция, соединяющая две двоичных переменных а и b, принадлежащих множеству {0,1}, в такую переключательную функцию с, которая равна 1 (истинна) только тогда, когда равны 1 (истинны) обе переменных. Операция конъюнкции обозначается символом Ù (&) или просто «×». В ряде случаев точку также опускают.

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

Таблица 14

Бинарная конъюнкция

b а	0	1
0	0	0
1	0	1	с=аÙb

Таким образом, конъюнкция – это операция В²aВ, где В – двухэлементное множество {0,1}, где 0,1 – значения истинности переменных. Известна также другая форма таблицы истинности – одномерная:

Таблица 15

Бинарная конъюнкция

а	b	с=аÙb
0	0	0
0	1	0
1	0	0
1	1	1

Конъюнкция n переменных истинна тогда и только тогда, когда все составляющие ее переменные истинны (равны 1).

Логическая операция, соответствующая союзу «или» в неразделительном смысле, называется дизъюнкцией (disjunctio – «разделение»). Пример дизъюнкции: «На экзамене по дискретной математике я получу 5 или 4».

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

Дизъюнкция обозначается символом Ú.

В латыни союзу «или» в неразделительном смысле соответствует слово vel. Символ Ú происходит от первой буквы этого слова.

Таблица истинности дизъюнкции (одномерная) имеет вид табл. 16.

Таблица 16

Бинарная дизъюнкция

а	b	с=аÚb
0	0	0
0	1	1
1	0	1
1	1	1

Дизъюнкция n переменных ложна тогда и только тогда, когда все составляющие ее переменные ложны.

Логическая операция, соответствующая частице «не», словосочетанию «неверно, что», называется инверсией. Пример инверсии: «Студент Петров не отличник», «Неверно, что студент Иванов является спортсменом».

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

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

Таблица истинности унарной операции инверсии ВaВ имеет вид табл. 17.

Таблица 17

Бинарная инверсия

а
0	1
1	0

Логическая операция, соответствующая союзу «если...то», называется импликацией.

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

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

Импликация обозначается символом ®.

Таблица истинности импликации имеет вид табл. 18.

Таблица 18

Импликация

а	b	с=а®b
0	0	1
0	1	1
1	0	0
1	1	1

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

Логическая операция, соответствующая союзу «тогда и только тогда, когда», называется эквиваленцией (эквивалентностью).

Пример эквиваленции (эквивалентности): «Я поеду к морю тогда и только тогда, когда сдам экзамен по дискретной математике».

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

Таблица истинности эквиваленции имеет вид табл. 19.

Таблица 19

Эквиваленция

а	b	с=а«b
0	0	1
0	1	0
1	0	0
1	1	1

Далее мы познакомимся с другими логическими операциями, которым нет простого эквивалента в разговорной речи, например, суммой по модулю 2 (исключающее ИЛИ).

Заметим, что операции могут быть выражены через другие операции, например, импликация а®b может быть представлена в виде , что может быть доказано построением соответствующих таблиц истинности.

Область определения ПФ n переменных – множество всех возможных наборов длины n при матричном задании ПФ, а при геометрическом способе задания – множество всех вершин n-мерного куба.

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

Например, для бинарной ПФ: вырожденная ПФ (табл. 20) – такая функция, которая зависит не от всех n переменных.

Таблица 20

Вырожденная ПФ

				BC	z
x3	х2		x1
0		0	0	0	1
0		0	1	1	1
0		1	0	2	1
0		1	1	3	1
1		0	0	4	0
1		0	1	5	0
1		1	0	6	0
1		1	1	7	0

Из таблицы (см. табл. 20) видно, что столбец функции является инверсным столбецу х₃, т.е. , от х₂, х₃ – z не зависит!

Двоичные ПФ описывают элементную базу электронной вычислительной техники и устройств автоматики и телемеханики – комбинационные и последовательностные автоматы, которые будут рассмотрены в дальнейшем.

Итак, основные двоичные логические операции:

1) дизъюнкция Ú («ИЛИ»);

2) конъюнкция & («И»);

3) инверсия или отрицание («НЕ»);

4) импликация ® («ЕСЛИ, ТО»);

5) эквиваленция « («ТОГДА И ТОЛЬКО ТОГДА, КОГДА»).

Кроме того, имеется операция:

6) сумма по модулю 2 Å («НЕВЕРНО, ЧТО ТОГДА И ТОЛЬКО ТОГДА, КОГДА» «ИЛИ-ИЛИ»).

Имеются также специальные операции:

7) стрелка Пирса ¯ («ИЛИ-НЕ»);

8) штрих Шеффера½(«И-НЕ») и др.

Алгебра, несущим множеством которой является множество ПФ, а операциями – дизъюнкция, конъюнкция и инверсия, называется булевой алгеброй ПФ.

ПФ можно описать некоторые условия, например, равенства (неравенства) некоторых битов, значения отдельных битов 0 или 1, например:

,

означает, что бит a₁ должен быть равен нулю и при этом биты a₂ и a₃ равны.

Решить логическое уравнение – значит, определить значения переменных, при которых соответствующая ПФ=1 (истинна), где 1 – константа.

Решить систему логических уравнений – значит определить значения переменных, при которых соответствующая ПФ=1.

Пример. Дана таблица истинности для трех ПФ (табл. 21).

Таблица 21

Таблица истинности трех ПФ

			ВС	z1	z2	z3
a3	a2	a1
0	0	0	0	1	0	1
0	0	1	1	0	1	0
0	1	0	2	0	1	0
0	1	1	3	0	0	1
1	0	0	4	0	1	0
1	0	1	5	0	0	1
1	1	0	6	1	0	1
1	1	1	7	0	1	0

z₁=0,6[1,2,3,4,5,7],

z₂=1,2,4,7[0,3,5,6]=a₁Åa₂Åa₃=1,

z₃=0,3,5,6[1,2,4,7].

Здесь указаны номера наборов, на которых ПФ равны единице. Это так называемая символическая форма задания ПФ (СФ ПФ).

Видно, что общих решений нет.

Если же взять:

,

то получим:

z₂=0,3,5,6[1,2,4,7], т.е.

решение системы z₁,z₂,z₃=0,6.

Если же в уравнении указывается равенство с другой переменной или функцией, то, как мы уже знаем из теории множеств:

a₁Åa₂Åa₃=a₃, a₁Åa₂Åa₃Åa₃=0, a₁Åa₂=0.

Решение: 01,10 (a₁a₂).

15 Элементарные переключательные функции одной переменной

Переключательные (логические) функции, соответствующие логическим операциям В²aВ, называют элементарными. Количество переключательных (логических) функций от n переменных определяется выражением 2²ⁿ, поскольку |Bⁿ|=2ⁿ, а на каждом из 2ⁿ наборов переключательная (логическая) функция может принимать одно из значений из того же множества В (табл. 23).

Таблица 23

Переключательные функции от n переменных

№	Набор	Номер логической функции
п/п	значений переменных	0	1	2	3	...	22n-1
1	00...00	0	1	0	1	...	1
2	00...01	0	0	1	1	...	1
3	00...10	0	0	0	0	...	1
4	00...11	0	0	0	0	...	1
. . .	. . .	. . .	. . .	. . .	. . .	...	. . .
22	11...11	0	0	0	0	...	1

Например, рассмотрим все переключательные (логические) функции одной переменной (табл. 24).

Таблица 24

Переключательные функции одной переменной

	Переключательная (логическая) функция
х	f0(x)	f1(x)	f2(x)	f 3(x)
0	0	1	0	1
1	0	0	1	1

Поскольку 2²¹=4, то имеется четыре логических функции одной переменной, две из них – константы: f₀(x)=0, f₃(x)=1 (f₀(x) – константа нуля, f₃(x) – константа единицы). Здесь номер функции означает десятичное число, соответствующее двоичному числу, записанному в соответствующем столбце табл. 24.

Функция f₂(x)=х, т.е. совпадает со значением переменной. Эта функция называется функцией повторения. Функция нам уже известна – это инверсия.

Можно заметить, что для каждой функции одной переменной существует инверсная ей функция: