Определение булевых функций

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

Булевой функцией переменных будем называть однозначное отображение пространства , которое является прямым произведением пространств , состоящих из двух элементов, в пространство . Один из элементов будем обозначать Ø (или «ложь», «Л», «false»), другой – 1 (или «истина», «И», «true»). Пространство аргументов содержит элементов, каждый из которых записывается в виде -мерного вектора . Общее количество различных булевых функций – .

Среди булевых функций выделяются так называемая тавтология – функция, равная единице при любом наборе аргументов, и противоречие – функция, принимающая значение Ø при любом наборе аргументов. Отрицанием истины считается ложь, и наоборот: 1 0, 0 1. Отрицание функции – это такая функция , которая для любого набора аргументов принимает значение, противоположное соответствующему значению .

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

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

Перечень булевых функций двух переменных приведен в табл. 1.1.

Таблица 1.1

Булевы функции

X 1					F	Обозначение	Название
X 2
						Ø	Противоречие
					X 1 X 2	, «.», &	Конъюнкция
					X 2\ X 1	\	Разность
					X 2		Проекция Р2 (X1, X2) = X2
					X 1 \ X 2		Разность
					X 1		Проекция Р1 (X1, X2) = X1
					X 1 \ X 2 X 1 \ X 2	∆, xor, +	Симметричная разность, сложение по модулю 2
					X 1 X 2	, +, or	Дизъюнкция
					(X 1 X 2)		Стрелка Пирса (польский штрих)
					X 1 X 2	, ,	Эквивалентность
					X 1		Отрицание X1
					X 1 X 2 X 1 X 2		Импликация
					X 2		Отрицание X2
					X 2 X 1 X 2 X 1		Импликация
					(X 1 X 2)	­	Штрих Шеффера
						I	Тавтология

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

- коммутативные законы:

, ;

- ассоциативные законы:

, ;

- дистрибутивные законы:

, ;

- законы идемпотентности:

, ;

- закон двойного отрицания

;

- законы Де Моргана:

, ;

- законы поглощения:

, .

В таком случае данное множество с введенными операциями представляет собой алгебру, притом булеву.

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

Сопоставим с элементами множества М высказывания, с операциями сложения – дизъюнкцию, с операциями умножения – конъюнкцию, со знаком отрицания – отрицание высказывания, со знаками эквивалентности – равенства. В таком случае обнаружится, что алгебра логики является интерпретацией булевой алгебры. Роль истины играет единица (1), лжи – ноль (0): , , , .

Еще одна интерпретация булевой алгебры – множества с операциями объединения, пересечения и дополнения. Имеются и другие интерпретации, например релейные схемы.

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

С отрицанием величины он сопоставил арифметическую разность , с конъюнкцией – арифметическое выражение , а с дизъюнкцией – арифметическое выражение . Данные операции даже использовались как эквиваленты логических операций в первых ЭВМ.

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

Контрольные задания

1. Максимально упростить выражение своего варианта, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравнить упрощенное выражение с исходным:

1) (a (רd b)) ((רa (רb d)) c) רc (a (b רd)),

2) ((a c) (a d)) (((c (c b)) רc) רa),

3) (רb d) ((רd c) (a c) (רd רc) (a רc)) (b d),

4) (a רc) (רa רb) (רb c) (רa b) (b c),

5) (a c) ((b רd) (רa רd) (d b) (רa d)) (a רc),

6) ((רb רc) (a b)) (d רc) (((רb רa) c) (a b)),

7) (a רc) (רa רb) (b c) (רa b) (c רb),

8) ((a (c (b c))) ר(c d) (c רd)) (c (רd רc) d),

9) ((a רa) (רb רd) (רb רc) (רc d)) ((רb c) (c d)),

10) (a רc) ((רa d) (b d) (רa רd) (b רd)) (a c),

11) ((d רc) (רd רb) (c רb)) ((רd b) (c b)) (רa a),

12) ((רc רd) (b c)) (רa רd) (((רc רb) d) (c b)),

13) ((a b) (רb c d) (רa רb c d) רb רc d,

14) ((a b) (a רb)) ((רa b) (c רd) (רa רb) (d c)),

15) ((רb c) (רc d) רa) (רa b רc d) ר(c d) a,

16) ((b c) (d (רb רc))) (רd רa) ((c b) (רd רc)),

17) (b d) ((c רd) (a c) (רd רc) (a רc)) (רb d),

18) ((רc d) (d a)) ((b רb) (רc רa) (רc רd) (רd a)),

19) (a רd) (((רc רb) d) (c b)) ((רd רc) (c b)),

20) (((d (d c)) רd) רb) ((b d) (b a)),

21) ((רb (רc a)) d)) רd (b (c רa)) (b (רa c)),

22) ((c רa) (רa רb) (a c) (רb a)) (b רd) (b d),

23) (d (רa רd) a) ((b (d (d c))) ר(c a) (d רa)),

24) (רc רb) (d c) (רb с) (d רc) (b רd).

Пример. (רc רb) (d c) (רb c) (d רc) (b רd):

1) (רc רb) (רb c)= רb,

2) (d c) (d רc)= d,

3) d (b רd)= (b d) (d רd)= (b d) I= b d,

4) רb d (b רd)= רb b d=I d=I.

2. Установить эквивалентность левой и правой частей следующих логических выражений:

1) ((a|b)|(a~b))|((c+d)→(d/c))=((b→c)→(a/c))↓((a|d)|(d→ רb)),

2) ((a רc)↓(b/c)) ((a|d)/(b d))=((a|b)|(a+ רb))→((c+d) (d→c)),

3) ((a↓b) (a+b))/((c/d)↓(c~d))=((c→a) (c→b)) →((a↓d) (b↓d)),

4) ((a~b)/(a↓b))↓((c~d)↓(c/d))=((c/a)↓(c/b))|((a↓d)↓(b↓d)),

5) ((a b) (a+b))/((d/c)↓(d~c))=((a→c) (b→c)) →((a|d)|(b|d)),

6) ((a b)/(a+b)) ((c/d)↓(c~d))=((c/a)↓(c/b)) ((a d)/(b↓d)),

7) ((d→b)→(רc/b))↓((c a)|(d→a))=((רc|d)|(c+d))|((a~b)→(רa/b)),

8) ((a|b)/(רa+ רb)) ((d/c)↓(c~d))=((רa↓ רd)↓(b/ רd)) ((a→c)/(b/c)),

9) ((c/a) (c~a))/((d/b)↓(d~b))=((a b) (c→b))→((d/a) (c d)),

10) ((c~b)/(b↓c))↓((רa~ רd)↓(a/d))=((b↓d)↓(c↓d))|((a/b)↓(a/c)),

11) ((a/d) (a~d))/((b/c)↓(b~c))=((b→d) (a|b))→((c d)|(a→c)),

12) ((b↓d)↓(c↓d)) ((a→b)/(a/c))=((b c)/(b+c)) ((a/d)↓(a~d)),

13) ((c→d)|(c+d))|((a~b)→(a b))=((a→ רc)→(a/d))↓((b→d)|(b→ רc)),

14) ((b d)↓(b c)) ((d→a)/(c/a))=((c|d)|(רc~ רd))→((a+b) (b→a)),

15) ((d/a) (d~a))/((c/b)↓(רc+b))=((a b) (d→b))→((c d) (c/a)),

16) ((c→d)/(c~d)) ((a b)↓(a+b))=((b c)↓(b/d)) ((a|c)/(a/d)),

17) ((רc→b)→(d↓b))↓((a→d)|(a→c))=((c d)|(c~d))|((רa+ רb)→(a/b)),

18) ((a c)↓(b/ רa)) ((c→d)/(b/d))=((b|c)|(b~c))→((a+d) (a→d)),

19) ((b↓ רd) (רb+d))/((a/c)↓(a~c))=((רc→b) (d→c)) →((a/b) (a d)),

20) ((d a)↓(b d))|((a/c)↓(b/c))=((a+ רb)/(b a))↓((רc~ רd)↓(d/c)),

21) ((a↓b) (רa~b))/((c/d)↓(c~d))=((רa→d) (רd→b))→((c→a)|(c→b)),

22) ((c→a)/(a+ רc)) ((d/b)↓(b~d))=((a↓b)↓(c/b)) ((d→a)/(c d)),

23) ((c| רb)|(c~ רb))|((רa+ רd)→(רa/ רd))=((c→ רd)→(רb/ רd))↓

↓((רb| רa)|(רa→c)),

24) ((c↓ רb) (c+ רb))/((רd/ רa)↓(רd~ רa))=((רd→ רb) (רd→c))→

→ ((רb↓ רa) (c↓ רa)).

Пример основных фрагментов программы:

/ frazn, + xor, or, and, fimp, fsp,

| fsh, ~, = feqv – логические функции и их идентификаторы;

function fsp(x,y:boolean): boolean;

begin fsp:=(not x) and (not y); end;

function feqv(x,y:boolean): boolean;

begin feqv:=(not x) and (not y) or x and y; end;

function frazn(x,y:boolean): boolean;

begin frazn:=x and (not y); end;

function fimp(x,y:boolean): boolean;

begin fimp:=(not x) or y; end;

begin

for a:=false to true do

for b:=false to true do

for c:=false to true do

for d:=false to true do begin

m1:=fsp(c,not b); m2:=c xor (not b); m3:=frazn(not d,not a); m4:=feqv(not d,not a); m5:=m1 or m2; m6:=fsp(m3,m4);

f1:=frazn(m5,m6);

n1:=fimp(not d,not b); n2:=fimp(not d,c); n3:=fsp(not b,not a);

n4:=fsp(c,not a); n5:=n1 and n2; n6:=n3 or n4;

f2:=fimp(n5,n6);

fsrav:=feqv(f1,f2);

write('| ');

if a then write('1') else write('0');

if b then write(' 1') else write(' 0');

if c then write(' 1') else write(' 0');

if d then write(' 1') else write(' 0');

write(' | ');

if f1 then write(' 1') else write(' 0');

write(' | ');

if f2 then write(' 1') else write(' 0');

write(' | ');

if fsrav then write(' 1') else write(' 0');

writeln(' | ');

end;

readln;

end.

Результат работы программы – таблица истинности:

Дата добавления: 2015-06-04