кр одмита

4.2. Элементарные булевы функции и алгебраические формы

Рассматривая векторную форму задания булевой функции, легко определить число булевых функций от п переменных – это число всех 2ⁿ-компонентных булевых векторов, т. е. . Однако это число учитывает также функции и от меньшего числа аргументов. Любую функцию отп аргументов можно считать функцией от большего числа аргументов. Для этого вводится понятие существенной зависимости и несущественной зависимости. Функция f(х₁, х₂, ... , х_n) существенно зависит от аргумента х_i, если

f(х₁, х₂, ... , х_i_– 1, 0, х_i_+ 1, … , х_n)  f(х₁, х₂, ... , х_i_– 1, 1, х_i_+ 1, … , х_n).

Переменная х_i в этом случае называется существенным аргументом. В противном случае она является несущественным или фиктивным аргументом.

Элементарными булевыми функциями являются функции от одной и двух переменных. Число функций от одной переменной равно = 4. Эти функции представлены в табл. 4.2. Две из них,f₀ и f₃, являются константами 0 и 1, переменная x для них является несущественным аргументом. Функция f₁ также является тривиальной, любое ее значение совпадает со значением аргумента: f₁(x) = x. Нетривиальной функцией является функция f₂(x) =x, называемая отрицанием, или инверсией. Ее значение всегда противоположно значению аргумента x. Из табл. 4.2 видно, что 0 = 1 и1 = 0.

В табл. 4.3 приведены все булевы функции f_i(х₁, х₂) от двух аргументов. В левом столбце показаны их выражения в терминах нескольких функций, принятых за основные. Эти основные элементарные булевы функции определяются табл. 4.4, содержащей имена функций и их обозначения, а также значения, принимаемые данными функциями на каждом из четырех наборов значений аргументов х₁ и х₂ (приведенных в верхней части таблицы), т. е. каждая из функций задана в векторном виде.

Таблица 4.2

Булевы функции от одного аргумента

	x	0	1
f₀ = 0		0	0
f₁ = x		0	1
f₂ =x		1	0
f₃ = 1		1	1

Таблица 4.3

Булевы функции от двух аргументов

х₁	0	0		1		1
х₂	0		1		0		1
f₀ = 0 – константа 0	0		0		0		0
f₁ = х₁  х₂ – конъюнкция	0		0		0		1
f₂ – отрицание импликации	0		0		1		0
f₃ = х₁	0		0		1		1
f₄ – отрицание обратной импликации	0		1		0		0
f₅ = х₂	0		1		0		1
f₆ = х₁  х₂ – сложение по модулю 2	0		1		1		0
f₇ = х₁  х₂ - дизъюнкция	0		1		1		1
f₈ = х₁ х₂ – стрелка Пирса	1		0		0		0
f₉ = х₁  х₂ – эквиваленция	1		0		0		1
f₁₀ =х₂	1		0		1		0
f₁₁ = х₂  х₁ – обратная импликация	1		0		1		1
f₁₂ =х₁	1		1		0		0
f₁₃ = х₁  х₂ – импликация	1		1		0		1
f₁₄ = х₁  х₂ – штрих Шеффера	1		1		1		0
f₁₅ = 1 – константа 1	1		1		1		1

Элементарные функции имеют особое значение в теории булевых функций, поскольку каждая из них может быть выражена одноместной или двухместной алгебраической операцией. Все операции, представленные в табл. 4.3, составляют алгебру логики. Любая булева функция от любого числа аргументов может быть представлена формулой алгебры логики. Формулу, содержащую более чем одну операцию, можно рассматривать как суперпозицию элементарных функций. Под суперпозицией функций понимается использование одних функций в качестве аргументов других функций. Для булевых функций это является возможным благодаря совпадению области значений функций с областями значений их аргументов. Таким образом, алгебраическое задание булевой функции представляет собой формулу, по которой вычисляется значение этой функции. Понятие формулы определим следующим образом:

1) каждый символ переменной есть формула;

2) если А и В – формулы, то формулами являются А и (А  В), где  – любая операция алгебры логики;

3) других формул нет.

Для установления порядка выполнения операций в формулах используются скобки. При отсутствии скобок порядок устанавливается согласно приоритетам операций. Первым приоритетом обладает операция отрицания, затем выполняется . Третьим приоритетом обладают операции  и , четвертым приоритетом – операции ~ и . Для упрощения написания формул иногда символ конъюнкции опускается. Процесс вычисления значений функции f(x₁, x₂, x₃) = по ее формуле покажем с помощью табл. 4.4, где последовательность столбцов соответствует порядку выполнения операций.

Таблица 4.4

Вычисление по формуле

x₁	х₂	х₃	х₁  х₂	(x₁  х₂) х₃		x₁	х₂х₃	x₁  х₂х₃	f(x₁, x₂, x₃)
0	0	0	0	0	1	1	0	1	1
0	0	1	0	0	1	1	0	1	1
0	1	0	1	0	1	1	0	1	1
0	1	1	1	1	0	1	1	1	1
1	0	0	1	0	1	0	0	0	0
1	0	1	1	1	0	0	0	0	1
1	1	0	1	0	1	0	0	0	0
1	1	1	1	1	0	0	1	1	1

Две разные формулы могут представлять одну и ту же функцию. Такие формулы называются равносильными. Если А и В – равносильные формулы, то А = В. В этом случае, если А является частью другой формулы, то вместо нее можно подставить В, в результате чего получится формула, равносильная исходной.

Алгебра, содержащая только три операции  ,  и , называется булевой, так же как и формула, представляющая некоторую композицию этих операций. Легко проверить по табл. 4.3 следующие основные законы булевой алгебры.

Коммутативность:

х  у  у  х; х у  у х.

Ассоциативность:

х  (у  z)  (x  y)  z; x (y z)  (x y) z.

Дистрибутивность:

x (y  z)  x y  x z; x  y z  (x  y) (x  z).

Идемпотентность:

x  x  x; x x  x.

Законы де Моргана:

=xy; =x y.

Законы операций с константами:

x  0  x; x 1  x;

x 0  0; x  1  1;

х х  1; хх  0.

Закон двойного отрицания:

х.

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

На основании этих формул выводятся следующие соотношения.

Закон поглощения:

х  х у  х; х (х  у)  х.

Действительно,

х  х у  х 1  х у  х (1  у)  х1 = х;

х (х  у)  х х  х у  х  х у  х.

Закон простого склеивания:

х у  ху  х; (х  у) (х у)  х.

Левая формула выводится с помощью закона дистрибутивности конъюнкции относительно дизъюнкции: х у  ху  х(у у)  х. Для вывода правой формулы достаточно раскрыть скобки и применить законы идемпотентности и поглощения.

Закон обобщенного склеивания:

х у х z  х у х z  y z.

Эту формулу можно вывести следующим образом:

х у х z  y z  x y x z  y z (x x)  x y (1  z) x z (1  y)  x y x z,

а если подставить у = 1, то получим

х х z = х 1 х z  1 z  х  z.

Все операции алгебры логики можно выразить через булевы операции. Справедливость следующих формул можно доказать простой подстановкой значений из табл. 4.3:

х  у = xy x y;

х ~ у =xy  x y;

х  у =x  y.

Пользуясь этими формулами, построим булево выражение, эквивалентное формуле ((х  у)  (х  z))y:

((х  у)  (х  z))y = (x  y  xz x z)y = (x  y z)y =xy yz.

Познакомимся еще с одной алгеброй на множестве логических функций – алгеброй Жегалкина.

Алгебра над множеством логических функций с двумя бинарными операциями и, двумя константами 1,0 называется алгеброй Жегалкина, если в ней выполняются следующие законы:

; ;;;

xy = yx; x(yz) = (xy)z; xx = x

В алгебре Жегалкина дизъюнкция выражается формулой, из которой видно, чтотогда, когда xy = 0 (когда x и y ортогональны).

Действительно,

Всякую формулу алгебры Жегалкина можно представить в виде полинома Жегалкина.

Для всякой логической функции существует единственный полином Жегалкина.

Содержание