Логические основы компьютера

Пример 5. Пусть a и b - высказывания, V(a) = 0, V(b) = 1. Тогда

$$ V(a \vee \neg b) = V(a) \vee V(\neg b) = V(a) \vee \neg V(b) = 0 \vee \neg 1 = 0 \vee 0 = 0. $$

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

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

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

$$A$$	$$B$$	$$\neg A$$	$$A \ B$$	$$A \vee B$$	$$A \to B$$	$$A \leftrightarrow B$$	$$A \oplus B$$	$$A \mid B$$	$$A \downarrow B$$
0	0	1	0	0	1	1	0	1	1
0	1	1	0	1	1	0	1	1	0
1	0	0	0	1	0	0	1	1	0
1	1	0	1	1	1	1	0	0	0

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

Невыполнимой формулой, или противоречием, называется всегда ложная формула.

Пример 6. Высказывание $$ A \vee \neg A$$ является тавтологией, а высказывание $$ A \ \neg A$$ - противоречием.

Проверим с помощью таблицы истинности, что высказывание $$ ((A \to B) \to A) \to A$$ является тавтологией ( табл. 4.2).

Таблица истинности для формулы $$((A \to B) \to A) \to A$$

A	B	$$A \to B$$	$$(A \to B) \to A$$	$$((A \to B) \to A) \to A$$
0	0	1	0	1
0	1	1	0	1
1	0	0	1	1
1	1	1	1	1

В записи формул соблюдаются следующие приоритеты относительно символов логических связок: сначала $$\neg$$, потом $$\$$ и $$ \mid$$, после этого $$ \vee, \downarrow$$ и $$ \oplus$$, затем $$ \to$$ и, наконец, $$ \leftrightarrow$$. Порядок применения операций с одинаковым приоритетом регулируется скобками.

Пример 7. Следующие высказывания являются тавтологиями:

$$ A \to A$$;

$$ A \to (B \to A) $$;

$$(\neg B \to \neg A) \to (A \to B) $$;

$$ (A \to B) \ (B \to C) \to (A \to C) $$.

Свойства логических операций

Две формулы называются равными, или эквивалентными, если их значения совпадают для любых означиваний переменных. Обозначим через 1 тавтологию, а через 0 - противоречие.

Ниже перечислены основные свойства логических операций:

a b = b a;

$$ a \vee b = b \vee a$$;

ассоциативность операций $$\$$ и $$ \vee$$:

(a b) с = a (b с);

$$ (a \vee b) \vee с = a \vee (b \vee с) $$;

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

$$ a \ (a \vee b) = a$$;

$$ a \vee (a \ b) = a$$;

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

$$ a \ (b \vee с) = (a \ b) \vee (a \ с);\\ a \vee (b \ с) = (a \vee b) \ (a \vee с) $$;

дополнительность (законы 0 и 1):

$$ a \ \neg a =0$$;

$$ a \vee \neg a =1$$,

для произвольных элементов a, b и c (все свойства легко проверить с помощью таблиц истинности).

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

$$A \to B = \neg A \vee B; \\ A \leftrightarrow B = (A \ B) \vee (\neg A \ \neg B);\\ A \oplus B = (A \ \neg B) \vee (\neg A \ B);\\ A \mid B = \neg (A \ B);\\ A \downarrow B = \neg (A \vee B). $$

Таким образом, для произвольного высказывания существует эквивалентное ему высказывание, содержащее из связок только $$\$$, $$ \vee$$ и $$ \neg$$.

Замечание 2. Множество операций конъюнкции и отрицания обладает свойством полноты. Действительно, $$ A \vee B = \neg (\neg A \ \neg B) $$.

Замечание 3. Множество операций дизъюнкции и отрицания обладает свойством полноты. В самом деле, $$ A \ B = \neg (\neg A \vee \neg B) $$.

Замечание 4. Штрих Шеффера обладает свойством полноты. Действительно, $$ \neg A = A \mid A; A \ B = (A \mid B) \mid (A \mid B) $$.

Замечание 5. Стрелка Пирса обладает свойством полноты. В самом деле, $$ \neg A = A \downarrow A; A \vee B = (A \downarrow B) \downarrow (A \downarrow B) $$.

Свойства операций используются для упрощения формул.

В дальнейшем знак $$\$$ иногда заменяется знаком * или опускается, а отрицание формулы a обозначается в виде $$\bar a$$.

Пример 8. Имеем:

$$\overline{ab}\vee b \vee \bar c=\bar a \vee \bar b \vee \bar b \bar {\bar c}=\bar a \vee \bar b=\overline _ab}$$

$$\overline {ab\vee b \vee c}(\bar a c)=\overline{b \vee c}(\bar a c)=\bar b \bar c \bar a c=0$$

Понятие булевой алгебры

Множество M, на котором определены бинарные операции $$ \vee$$ и $$\$$ и унарная операция $$ \neg$$, для которых выполняются свойства 1 - 4 из п. 4.1.4 (коммутативность, ассоциативность, дистрибутивность и законы поглощения), и в котором существуют элементы 0 и 1, удовлетворяющие свойству 5 (законы 0 и 1), называется булевой алгеброй.

Символы 0 и 1 обозначают некоторые элементы множества M, а символы $$ \vee$$, $$\$$ и $$ \neg$$ - операции на этом множестве. Операция $$ \neg$$ называется операцией дополнения, или отрицания. Операции $$ \vee$$ и $$\$$ по-прежнему будут называться операциями дизъюнкции и конъюнкции, соответственно.

Равенства, выражающие свойства 1 - 5 булевой алгебры, перечисленные в п. 4.1.4, называются еще тождествами булевой алгебры.

Пример 9. Множество {0, 1} c операциями дизъюнкции, конъюнкции и отрицания является булевой алгеброй.

Пример 10. Множество высказываний S c операциями дизъюнкции, конъюнкции и отрицания является булевой алгеброй.

Пример 11 (булева алгебра множеств). Пусть M - множество. Множество подмножеств M c операциями объединения, пересечения и дополнения до M является булевой алгеброй. Здесь $$ 0 = \varnothing, 1 = M$$.

Утверждение 1. Булева алгебра обладает следующим свойством:

если a b = a c и $$a \vee b = a \vee c$$, то b = c.

Доказательство. Имеем:

$$b= b \vee (b \ a) = b \vee (c \ a) = (b \vee c) \ (b \vee a) = \\ = (b \vee c) \ (c \vee a) = c \vee (b \ a) = c \vee (c \ a) = c. $$

Замечание. Если в каждом равенстве из свойств 1 - 5 одновременно заменить символ $$\$$ на символ $$\vee$$, символ $$\vee$$ на символ $$\$$, а также 0 на 1 и 1 на 0, то множество равенств не изменится. Символы $$\$$ и $$\vee$$, а также символы 0 и 1 называются двойственными.

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

Утверждение 2. Операции булевой алгебры обладают следующими свойствами:

конъюнкция с 1 и дизъюнкция с 0:

a 1 = a;

$$a \vee 0 = a$$;

идемпотентность операций $$\$$ и $$\vee$$:

a a = a;

$$a \vee a = a$$;

конъюнкция с 0 и дизъюнкция с 1:

a 0 = 0;

$$a \vee 1 = 1$$;

дополнение 0 и 1:

$$\neg 0 = 1$$;

$$\neg 1 = 0$$;

инволютивность дополнения:

$$\neg\neg a = a$$;

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

$$\neg (a \ b) = \neg a \vee \neg b;\\ \neg (a \vee b) = \neg a \ \neg b$$

для произвольного элемента a множества M.

Доказательство. Докажем по одному из двойственных равенств, второе равенство получается взаимной заменой двойственных символов:

$$a \ 1 = a \ (a \vee \neg a) = a$$ (по закону 0 и 1 и закону поглощения);

$$a = a \ 1 = a \ (a \vee \neg a) = (a \ a) \vee (a \ \neg a) = (a \ a) \vee 0 = a \ a$$ (по закону 0 и 1 и закону дистрибутивности);

$$a \ 0 = a \ (a \ \neg a) = (a \ a) \ \neg a = a \ \neg a = 0$$,

$$\neg 0 = \neg 0 \vee 0 = 0 \vee \neg 0 = 1$$;

$$\neg\neg a \ \neg a = 0 = a \ \neg a и \neg\neg a \vee \neg a = 1 = a \vee \neg a$$,

следовательно, по утверждению 1, $$\neg\neg a = a$$;

аналогично,

$$a \ b \ (\neg a \vee \neg b) = (a \ b \ \neg a) \vee (a \ b \ \neg b) = 0 \vee 0 = 0;\\ a \ b \vee (\neg a \vee \neg b) = (a \vee \neg a \vee \neg b) \ (b \vee \neg a \vee \neg b) = 1, $$

поэтому $$\neg (a \ b) = \neg a \vee \neg b.$$

Следствие 1. Элементы 0 и 1 в булевой алгебре единственны. В самом деле, пусть имеются элементы 0' и 1' из множества M, такие что $$a \ \neg a = 0' $$ и $$a \vee \neg a = 1' $$ для произвольного элемента a из M. Тогда

$$0' = 0' \vee 0 = 0 \vee 0' = 0;\\ 1' = 1' \ 1 = 1 \ 1' = 1. $$

Следствие 2. 1) Если a b = 1, то a = 1 и b = 1.

2) Если $$a \vee b = 0$$, то a = 0 и b = 0.

Действительно, пусть $$a \ b = 1$$. Тогда

$$a = a \ 1 = a \ (a \ b) = (a \ a) \ b = a \ b = 1, $$

и, точно так же, b = 1. Аналогично для двойственного утверждения.

Логические задачи

Рассмотрим примеры решения логических задач с помощью алгебры логики.

Пример 12. Аня, Боря, Витя, Гриша и Даша решают, пойти ли им в кино. Ситуация описывается следующими высказываниями:

Если Аня пойдет, то и Боря пойдет;

Хотя бы кто-то из Вити и Гриши пойдет;

В кино пойдет либо Боря, либо Даша, но не оба;

Витя и Даша либо оба пойдут в кино, либо оба не пойдут;

Если Гриша пойдет, то пойдут также Аня и Витя.

Предполагая, что все высказывания истинны, определите, кто пойдет в кино.

Введем атомарные высказывания:

a: "Аня пойдет в кино"; b: "Боря пойдет в кино";

v: "Витя пойдет в кино";g: "Гриша пойдет в кино";

d: "Даша пойдет в кино".

Представим в виде высказываний условия задачи:

$$a \to b$$;

$$v \vee g$$;

$$b \oplus d$$;

$$v \leftrightarrow d$$;

$$g \to a \ v$$.

Выразим все операции через операции конъюнкции, дизъюнкции и отрицания. В результате получим:

$$1=(\bar a \vee b)(v \vee g)(b \bar d \vee \bar b d)(vd \vee \bar v \bar d)(\bar g \vee av)=\\ \((\bar a \vee b)(b \bar d \vee \bar b d))((v \vee g)(\bar g \vee av))(vd \vee \bar v \bar d)=\\ =(b \bar d \vee \bar a \bar b d)(v \bar g \vee av)(vd \vee \bar v \bar d)=\\ =(b \bar d \vee \bar a \bar b d))(v \bar g d \vee avd)=\bar a \bar b v \bar g d.$$

Поэтому $$\bar a=1, \bar b=1, v=1, \bar g =1, d=1$$ следовательно, a=0, b=0, v=0, g=0, d=0,

так что, Витя и Даша пойдут в кино, а Аня, Боря и Гриша не пойдут.

Пример 13. Секретные документы находятся в одном из трех сейфов. Три агента передали по два сообщения - одно о том, в каком сейфе находятся документы, и одно о том, в каком сейфе их нет.

Первый агент:

"Документы не в первом сейфе";

"Документы во втором сейфе".

Второй агент:

"Документы не в первом сейфе";

"Документы в третьем сейфе".

Третий агент:

"Документы не в третьем сейфе";

"Документы в первом сейфе".

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

Введем высказывания:

a: "Документы в первом сейфе";

b: "Документы во втором сейфе";

с: "Документы в третьем сейфе".

Tогда сообщения агентов могут быть представлены в виде:

первый агент: $$\neg a, b$$;

второй агент: $$\neg a, c$$;

Имеем: $$a \bar b \bar c \vee \bar a b \bar c \vee\bar a \bar b c=1$$, так как документы находятся только в одном сейфе. Возможны три случая.

$$a \bar b \bar c=1$$, или a = 1, b = 0, c = 0. В этом случае оба сообщения первых двух агентов неверны, что, по условию, невозможно.

$$\bar a b \bat c=1$$, или a = 0, b = 1, c = 0. Тогда второй и третий агенты прислали по одному верному сообщению и по одному неверному, что противоречит условию задачи.

$$\bar a \bar b c=1$$, или a = 0, b = 0, c = 1. В этом случае первый агент прислал одно верное сообщение и одно неверное, второй - два верных, третий - два неверных, так что все условия выполняются.

Таким образом, секретные документы находятся в третьем сейфе.

Понятие логической функции

Пусть B = {0, 1} и n - натуральное число.

Логическая, или булевская функция - это функция вида

$$f: B^n \to B. $$

Если логическая функция имеет n аргументов, то область ее определения содержит $$2^n$$ элементов, а всего таких функций $$2^{2^n}$$

Пример 14. Пусть n = 1. Все логические функции с одним аргументом имеют вид:

$$f_0(x) = 0$$ для $$x \in B$$;

$$f_1(x) = x$$ для $$x \in B$$;

$$f_2(0) = 1, f_2(1) = 0;$$

$$f_3(x) = 1$$ для $$x \in B$$.

Логические функции имеют конечное число аргументов, поэтому такие функции могут определяться в виде таблиц истинности. В табл. 4.3 определены функции из примера 14.

Логические функции с одним аргументом

x	$$f_0$$	$$f_1$$	$$f_2$$	$$f_3$$
0	0	0	1	1
1	0	1	0	1

Переменная, которая принимает значения на множествеB, называется булевской, или логической.

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

Пример 15. Функция $$f: B^3 \to B$$ вида $$f(x, y, z) = x \vee \neg y \ z, $$ для $$x, y, z \in B$$, является логической функцией.

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

Логические функции с двумя аргументами (остальные 8)

A	B	0	$$\neg(A \to B)$$	A	$$\neg(B \to A)$$	B	$$\neg B$$	$$B \to A$$	1
0	0	0	0	0	0	0	1	1	1
0	1	0	0	0	1	1	0	0	1
1	0	0	1	1	0	0	1	1	1
1	1	0	0	1	0	1	0	1	1

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

Утверждение 3. Пусть $$f: B^n \to B$$ - логическая функция. Тогда

$$f(x_1, \dots, x_i, \dots, x_n)=x_if(x_1, \dots, 1, \dots, x_n)\vee \bar {x_i} f(x_1, \dots, 0, \dots, x_n),$$

для $$i = 1, 2, \dots, n$$;

$$f(x_1, \dots, x_j, \dots, x_n)=(x_j \vee f(x_1, \dots, 0, \dots, x_n)*)\bar {x_j} \vee f(x_1, \dots, 1, \dots, x_n))$$

для $$j = 1, 2, \dots, n$$.

Доказательство. Если $$x_i = 0$$, то обе части первого равенства совпадают с $$f(x_1, \dots, 0, \dots, x_n) $$, а если $$x_i = 1$$, то с $$f(x_1, \dots, 1, \dots, x_n) $$, для $$i = 1, 2, \dots, n$$. Аналогично, если $$x_j = 0$$, то обе части второго равенства совпадают с $$f(x_1, \dots, 0, \dots, x_n) $$, а если $$x_j = 1$$, то с $$f(x_1, \dots, 1, \dots, x_n) $$, для $$j = 1, 2, \dots, n.$$

И утверждения 3 следует следующее утверждение.

Утверждение 4. Пусть $$f: B^n \to B$$ - логическая функция. Тогда

$$f(x_1, x_2, \dots, x_n)=\overline{x_1}\dots \overline {x_{n-1}} \overline {x_n}f(0, \dots, 0,0) \vee \overline {x_1}\dots \overline {x_{n-1}}x_nf(0, \dots, 0,1) \vee\\ \dots\\ \vee x_1x_2\dots x_nf(1,\dots, 1,1);\\ F(x_1, x_2, \dots, x_n)=(x_1 \vee \dots \vee x_{n-1} \vee x_n \vee f(0, \dots, 0,0)\cdot\\ \cdot (x_1 \vee \dots \vee x_{n-1} \vee \overline {x_n} \vee f(0,\dots, 0,1)) \cdot\\ \dots\\ \cdot \overline {x_1} \vee \dots \vee \overline {x_2} \vee \overline {x_n} \vee f(1, \dots, 1,1)).$$

Доказательство. Обе формулы нетрудно проверить с помощью индукции по числу аргументов.

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

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

Из утверждения 4 следует, что представление логической функции в СДНФ единственно, с точностью до порядка следований элементарных конъюнкций. Аналогично для СКНФ.

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

Пример 17. Найдем СДНФ функции $$f(x,y)-\bar xy \vee \overline {xy}$$ и определим, при каких значениях аргументов она принимает значение 1. Имеем:

$$f(x,y)=\bar x y \vee \bar x \vee \bar y=\bar x \vee \bar y=\bar x(y \vee \bar y)\vee (x \vee \bar x)\bar y=\bar x y \vee \bar x \bar y \vee x \bar y$$

Из утверждения 4 следует, что

$$f(x,y)=\bar x \bar yf(0,0)\vee \bar x y f (0,1)\vee x \bar y f(1,0)\vee xyf(1,1)$$

Поэтому f(0,0)=f(0,1)=f(1,0) , а f(1,1)=0 .

Пример 18. Найдем СДНФ и СКНФ логической функции, которая соответствует таблице истинности 4.5.

Таблица истинности для функции с 3 аргументами

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

СДНФ функции выглядит следующим образом:

$$f(x,y,z)=\bar x \bar y z \vee \bar x y \bar z \vee x \bar y \bar z \vee xy \barrz \vee xyz$$

Она упрощается до ДНФ: $$f(x,y,z)=\bar x \bar y z \vee y \bar z \vee x \bar z \vee xy$$.

СКНФ функции имеет вид:

$$f(x,y,z)=(x \vee y \vee z)(x \vee \bar y \vee \bar z)(\bar x \vee y \vee \bar z)$$

Определим операции на множестве логических функций из $$ B^n$$ в B.

Пусть $$ f: B^n \to B$$ и $$ g: B^n \to B$$. Положим

$$ (\neg f)(x_1, x_2, \dots, x_n) = \neg f(x_1, x_2, \dots, x_n),\\ (f \ g)(x_1, x_2, \dots, x_n) = f(x_1, x_2, \dots, x_n) \ g(x_1, x_2, \dots, x_n),\\ (f \vee g)(x_1, x_2, \dots, x_n) = f(x_1, x_2, \dots, x_n) \vee g(x_1, x_2, \dots, x_n),\\ 0(x_1, x_2, \dots, x_n) = 0, 1(x_1, x_2, \dots, x_n) = 1, $$

для $$ x_1, x_2, \dots, x_n \in B$$.

Утверждение 5. Множество логических функций из Bn в B с определенными выше операциями образуют булеву алгебру.

Доказательство. Нетрудно проверить, что так определенные операции удовлетворяют всем свойствам 1 - 5 из п. 4.1.4.

Электронные логические схемы

Электронная логическая схема состоит из базовых логических элементов, или вентилей. Логический элемент (logic gate) - это логическая функция, которая преобразует входные сигналы (значения аргументов) в выходной сигнал (значение функции).

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

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

Ниже перечисляются базовые логические элементы. Для каждого из них приводятся три вида обозначений: обозначения ГОСТ, обозначения Международной электротехнической комиссии (англ. IEC - International electrotechnical commission) и обозначения ANSI. Входные сигналы показаны слева, а выходные справа.

В дальнейшем для построения логических схем используются обозначения ГОСТ.

Схема НЕ

На рис. 4.2 приведена схема НЕ (NOT gate), или инвертора - логического отрицания, соответствующего логической функции $$f(x)=\bar x$$.

(рис 4.2) Инвертор: (a) ГОСТ; (b) IEC; (c) ANSI

Схема повторителя

На рис. 4.3 приведена схема повторителя (BUFFER): $$f(x)=x$$.

(рис 4.3) Повторитель: (a) ГОСТ; (b) IEC; (c) ANSI

Схема И

Схема И (AND gate) соответствует логической конъюнкции: $$f(x,y)=x \ y$$( рис. 4.4).

(рис 4.4) Схема И: (a) ГОСТ; (b) IEC; (c) ANSI

Схема ИЛИ

(рис 4.5) Схема ИЛИ: (a) ГОСТ; (b) IEC; (c) ANSI

На рис. 4.5 приведена схема ИЛИ (OR gate) - логической дизъюнкции:$$f(x,y)=x \vee y$$.

Схема И-НЕ

Схема И-НЕ (NAND gate) соответствует штриху Шеффера, или отрицанию конъюнкции: $$f(x,y)=x \mid y= \overline{x \ y}$$ ( рис. 4.6).

(рис 4.6) Схема И-НЕ: (a) ГОСТ; (b) IEC; (c) ANSI

Схема ИЛИ-НЕ

На рис. 4.7 приведена схема ИЛИ-НЕ (NOR gate) - стрелки Пирса, или отрицания дизъюнкции: $$f(x,y)=x \downarrow y=\overline{x \vee y}$$

(рис 4.7) Схема ИЛИ-НЕ: (a) ГОСТ; (b) IEC; (c) ANSI

Схема ИСКЛЮЧАЮЩЕЕ ИЛИ

Схема ИСКЛЮЧАЮЩЕГО ИЛИ (XOR gate) соответствует строгой дизъюнкции:$$f(x,y)=x \oplus y = \bar x y \vee x \bar y$$ (рис. 4.8).

(рис 4.8) Схема ИСКЛЮЧАЮЩЕЕ ИЛИ: (a) ГОСТ; (b) IEC; (c) ANSI

Схема ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ

Заметим, что

$$\overline {x \oplus y}=\overline {\bar x y \vee x \bar y}=(x \vee \bar) (\bar x \vee y)= \bar x \bar y \vee xy=x \leftrightarrow y$$

Схема ИСКЛЮЧАЮЩЕГО ИЛИ-НЕ (XNOR gate) соответствует эквиваленции $$x \leftrightarrow y: f(x,y)= x \leftrightarrow y=\bar x \bar y \vee xy$$ ( рис. 4.9).

(рис 4.9) Схема ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ: (a) ГОСТ; (b) IEC; (c) ANSI

На практике вентили И-НЕ и ИЛИ-НЕ строятся проще, чем вентили И и ИЛИ; кроме того, они могут иметь более двух входов.

Пример 19. Электронная логическая схема, которая соответствует логической функции $$f(A,B,C)=(\overlina{AB}\vee \overline{A \vee B})\vee C)$$, показана на рис. 4.10.

(рис 4.10) Схема функции

Упростим схему. Имеем:

$$f(A,B,C)=(\overline{AB} \vee \overline{A \vee B})\vee C=\bar A \vee \bar B \vee \bar A \bar B \vee C=\overline {AB} \vee C$$

Поэтому схемы, представленные на рис. 4.10 и 4.11, равносильны.

(рис 4.11) Схема функции

Пример 20. Построим логическую функцию по схеме рис. 4.12.

(рис 4.12) Схема функции f

Имеем: $$f(A,B)=(A \mid B) (A \vee B)$$. Упростим функцию f ( на рис. 4.8):

$$f(A,B)=\overline {AB}(A \vee B)=(\bar A \vee \bar B)(A \vee B)=A\bar B \vee \bar A B=A \oplus B$$

Пример 21. Построим схему одноразрядного сумматора. Имеем:

$$0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 10_2.$$

Ясно, что для реализации сумматора необходима схема с тремя входами: два входа для значений разряда и один - для переноса из предыдущего разряда. Схема должна иметь два выхода, соответствующих значению разряда и переносу в следующий разряд ( рис. 4.13). Такую схему называют полным сумматором. Схема без входного переноса называется полусумматором.

В табл. 4.6 приведена таблица истинности для одноразрядного полного сумматора. В ней параметр z соответствует переносу из предыдущего разряда, S - сумме, а R - переносу в следующий разряд.

Таблица истинности одноразрядного сумматора

x	y	z	S	R
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

По таблице имеем:

$$S=\bar x \bar yz \vee \bar x y \bar z \vee \ \bar y \bar z \vee xyz=(\bar x \bar y \vee xy)z\vee(\bar x y \vee x \bar y)\bar z=\\ = x \oplus yz \vee(x \oplus y)\bar z=(x \oplus y)\oplus z;\\ R=\bar x yz \vee x \bar y z \vee xy \bar z \vee xyz=(\bar x y \vee x \bar y)z \vee xy(\bar z \vee z)=(x \oplus y)z \vee xy.$$ (рис 4.13) Схема полного одноразрядного сумматора: z - вход переноса, S - сумма,R - выход переноса

Битовые операции

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

Битовыми называют операции над цепочками битов. Основными битовыми операциями являются побитовые операции и битовые сдвиги.

Побитовые операции

Побитовые операции - это операции, которые применяются к каждому биту из цепочки битов. Основными побитовыми операциями являются побитовое отрицание bitNot, побитовая конъюнкция bitAnd, побитовая дизъюнкция bitOr и побитовая строгая дизъюнкция bitXor.

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

Побитовая операция отрицания соответствует побитовому применению функции inv(x) = 1 - x, для $$x \in \{0, 1\}$$.

Пример 22. Пусть для хранения чисел используется 4 байта. Тогда $$bitNot(2^{32} - 1) = 0$$. Соответственно, $$bitNot(0) = 2^{32} - 1 = 4294967295$$.

Найдем результат побитовой операции отрицания, примененной к числу 275. Имеем: $$275 = 100010011_2$$, или в 4 байтах,

00000000 00000000 00000001 00010011.

Применив к каждому биту функцию inv(x) = 1 - x, получим:

11111111 11111111 11111110 11101100.

Таким образом, bitNot(275) = 4294967020.

Побитовые операции конъюнкции, дизъюнкции и строгой дизъюнкции соответствуют побитовому применению функций

f(x, y) = min(x, y), g(x, y) = max(x, y), h(x, y) = (x + y) mod 2,

соответственно, где $$x, y \in \{0, 1\}$$.

Пример 23. Найдем результаты применения побитовых бинарных операций к числам 14 и 26. Имеем: $$14 = 1110_2$$, $$26 = 11010_2$$. Поэтому

Следовательно,

bitAnd(14, 26) = 10; bitOr(14, 26) = 30; bitXor(14, 26) = 20.

Обозначим через Deg(x) множество показателей степеней 2 в разложении числа x по степеням 2. Тогда

$$Deg(bitAnd(x, y)) = Deg(x) \cap Deg(y);\\ Deg(bitOr(x, y)) = Deg(x) \cup Deg(y);\\ Deg(bitXor(x, y)) = Deg(x) \Delta Deg(y),$$

где символами $$\cap$$, $$\cup$$ и $$\Delta$$ обозначены операции пересечения, объединения и симметрической разности множеств, соответственно.

Пример 24. Пусть x = 15, y = 28. Тогда

$$15 = 2^3 + 2^2 + 2 + 1;\\ 28 = 2^4 + 2^3 + 2^2.$$

Поэтому Deg(15) = {0, 1, 2, 3}, Deg(28) = {2, 3, 4}. Имеем:

$$\{0, 1, 2, 3\} \cap \{2, 3, 4\} = \{2, 3\};\\ \{0, 1, 2, 3\} \cup \{2, 3, 4\} = \{0, 1, 2, 3, 4\}.\\ \{0, 1, 2, 3\} \Delta \{2, 3, 4\} = \{0, 1, 4\}.$$

Следовательно,

$$bitAnd(15, 28) = 2^2 + 2^3 = 12;\\ bitOr(15, 28) = 1 + 2 + 2^2 + 2^3 + 2^4 = 31;\\ bitXor(15, 28) = 1 + 2 + 24 = 19.$$

Ясно, что операции объединения, пересечения и симметрической разности могут применяться к самим степеням 2. В данном случае имеем:

$$\{1, 2, 2^2, 2^3\} \cap \{2^2, 2^3, 2^4\} = \{2^2, 2^3\};\\ \{1, 2, 2^2, 2^3\} \cup \{2^2, 2^3, 2^4\} = \{1, 2, 2^2, 2^3, 2^4\}.\\ \{1, 2, 2^2, 2^3\} \Delta \{2^2, 2^3, 2^4\} = \{1, 2, 2^4\}.$$

Свойства операции bitXor рассматриваются также в п. 5.1.

Битовые сдвиги

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

Пусть двоичное представление целого неотрицательного числа x имеет вид: $$x = b_{0b1} \dots b_{n - 1}b_n$$. Тогда операции арифметических битовых сдвигов определяются следующим образом:

$$b_{0b1} \dots b_{n - 1}bn \to b_{0b1} \dots b_{n - 1}b_n0$$ - арифметический сдвиг влево;

$$b_{0b1} \dots b_{n - 1}b_n \to b_{0b1} \dots b_{n - 1}$$ - арифметический сдвиг вправо.

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

$$b_{0b1} \dots b_{n - 1}b_n \to b_1 \dots b_{n - 1}b_n0$$ - логический сдвиг влево;

$$b0b1 \dots b_{n - 1}b_n \to 0b_{0b1} \dots b_{n - 1}$$ - логический сдвиг вправо.

Обозначим через bitShiftLeft и bitShiftRight - операции арифметических сдвигов влево и вправо, соответственно, а через bitLeft и bitRight - операции логических сдвигов соответственно влево и вправо.

Нетрудно заметить, что

bitShiftLeft(x) = 2x; bitShiftRight(x) = bitRight(x) = x div 2

(см. п. 1.1). Таким образом, арифметический сдвиг влево соответствует удвоению числа. Кроме того, заметим, что если число x - четное, а в этом случае его младший разряд равен 0, то в результате сдвига вправо получится число, ровно в 2 раза меньшее исходного. Если же младший разряд числа равен 1, то получится целая часть частного от деления на 2.

В типах данных число разрядов фиксировано, поэтому при логическом сдвиге влево теряется старший разряд. Найдем число, которое получается при логическом сдвиге числа x влево на 1 разряд, если число разрядов в типе данных равно n + 1.

Имеем: $$ x=b_0 2^n+b_1 2^{n-1}+\dots+b_{n-1}*2+b_n$$. Поэтому

$$ bitLeft(x)=b_1 2^n+b_2 2^{n-1}+\dots+b_n*2+0=\\ =2(b_0 2^n+b_1 2^{n-1}+\dots+b_n )-b_0 2^{n+1}=2x-b_0 2^{n+1}.$$

Таким образом, если старший разряд числа x равен 0, то логический сдвиг влево приведет к удвоению числа. Далее, старший разряд числа x, для $$x<2^{n + 1}$$, равен 1, если $$x \ge 2^n$$. Пусть $$x = 2^n + y$$, где $$0 \le y \le 2^n$$. Тогда $$bitLeft(2^n + y) = 2(2^n + y) - 2^{n + 1} = 2y$$. Следовательно, если старший разряд числа равен 1, то в результате его логического сдвига влево получится его удвоенный остаток от деления на $$2^n$$.

Пример 24. Пусть тип данных содержит 4 байта.

Для числа 23 имеем:

bitShiftLeft(23) = bitLeft(23) = 46; 
 bitShiftRight(23) = bitRight(23) = 11,

что легко получить из определения операций, так как $$23 = 10111_2$$.

Найдем сдвиг влево для максимального числа. Имеем:

$$bitLeft(2^{32} - 1) = 2(2^{32} - 1) - 2^{32} = 2^{32} - 2.$$

Таким образом, bitLeft(4294967295) = 4294967294.

В общем случае, пусть число разрядов равно n + 1 и $$0 < z \le 2^n$$. Тогда $$2^{n + 1} - z \ge 2^n$$. Поэтому

$$bitLeft(2^{n + 1} - z) = 2(2^{n + 1} - z) - 2^{n + 1} = 2^{n + 1} - 2z.$$

В частности, если тип данных содержит 4 байта, то $$bitLeft(2^{31}) = 0$$, а для арифметического сдвига имеем: $$bitShiftLeft(2^{31}) = 2^{32}$$.

Рассмотрим битовые сдвиги на k разрядов, где $$k \ge 0$$. Покажем, что арифметический сдвиг влево на k разрядов числа x соответствует умножению x на $$2^k$$. Арифметический сдвиг вправо на k разрядов числа x приводит к целой части частного от деления x на $$2^k$$.

Пусть опять представление целого неотрицательного числа x в двоичном виде имеет вид: x = b0b1 \dots bn - 1bn. Тогда арифметический битовый сдвиг на k разрядов влево определяется следующим образом:

$$ bitShiftLeft(x,k)=b_0 b_1\dotsb_{n-1} b_n\underbrace{0\dots0}$$

Ясно, что $$bitShiftLeft(x, k) = x * 2^k$$.

Пример 25. Для числа 5 имеем:

bitShiftLeft(5, 1) = 10; 		bitShiftLeft(5, 2) = 20; 
bitShiftLeft(5, 3) = 40;		bitShiftLeft(5, 4) = 80.

Соответственно,

$$101_2 = 5;\\ 1010_2 = 10;\\ 10100_2 = 20;\\ 101000_2 = 40;\\ 1010000_2 = 80.$$

Арифметический и логический битовые сдвиги на k разрядов вправо совпадают и определяются следующим образом:

$$bitShiftRight(x,k)=bitRight(x,k)=\begin{cases} b_ob_1\dots b_{n-k}, k \le n,\\ 0, k >n \end{cases}$$

Пусть $$k \le n$$. Имеем:

$$bitRight(x,k)=b_02^{n-k}+b_12^{n-k-1}+\dots +b_{n-k}=\\ =\frac{1}{2^k}(b_02^n+b_12^{n-1} \dots +b_{n-k}2^k+b_{n-k-1}2^{n-k}+\dots +b_n)-\\ -\frac{1}{2^k}(b_{n-k-1}2^{n-k}+\dots+b_n)=\frac{x}{2^k}-\frac{b_{n-k-1}2^{n-k}+\dots+b_n}{2^k}$$

Следовательно, $$bitRight(x, k) = x div 2^k$$.

Пример 26. $$bitRight(100, 5) = 100 \;\div\; 2^5 = 3$$.

Пусть тип данных содержит n + 1 разряд. Определение логического сдвига влево на k разрядов имеет вид:

$$ bitLeft(x,k)=\begin{cases} b_k b_{k+1}\dots b_n \underbrace{0\dots0}_k, k \le n\\ 0, k > n \end{cases}$$

Пусть $$k \le n$$. Тогда

$$bitLeft(x,k)=b_k 2^n+b_{k+1} 2^{n-1}+\dots+b_n 2^k= \\ =2^k (b_0 2^n+\dots+b_{k-1} 2^{n-k+1}+b_k 2^{n-k}+b_{k+1} 2^{n-k-1}+\dots+b_n )-\\ -(b_0 2^{n+k}+\dots+b_{k-1} 2^{n+1} )=2^k x-2^{n+1} (b_0 2^{k-1}+\dots+b_{k-1} ).$$

Пример 27. Рассмотрим битовые сдвиги числа 14 на 2 разряда влево и вправо. Имеем: $$14 = 1110_2$$, n = 3, k = 2.

Арифметический сдвиг влево на 2 разряда: $$111000_2 = 56 = 14 * 2^2$$.

Логический сдвиг вправо на 2 разряда:

$$0011_2 = 3 = 14 \div 4 =\frac{14}{2^2}-\frac{2}{2^2}$$

Логический сдвиг влево на 2 разряда:

$$1000_2 = 8 = 2^2 * 14 - 2^4 * 3 = 56 - 48.$$

Пример 28. Пусть тип данных содержит 4 байта. Рассмотрим логический сдвиг максимального числа влево на k разрядов, для $$k \le 32$$. Имеем:

$$bitLeft(2^{32} - 1, k) = 2^k(2^{32} - 1) - 2^{32}(2^k - 1) = 2^{32} - 2^k. $$

Например,

$$bitLeft(2^{32} - 1, 31) = 2^{32} - 2^{31} = 2^{31} = 2147483648. $$

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

Пример 29. Для числа $$10010101_2$$ имеем:

$$10010101_2= bitOr(bitLeft(1, 7), bitLeft(1, 4), bitLeft(1, 2), 1) = = 2^7 + 2^4 + 2^2 + 1 = 149. $$

Пример 30. Вычислим bitOr(bitShiftLeft(5, 2), bitShiftLeft(3, 1)).

Имеем:

$$ bitShiftLeft(5, 2) = bitShiftLeft(101_2, 2) = 10100_2;\\ bitShiftLeft(3, 1) = bitShiftLeft(11_2, 1) = 110_2. $$

Поэтому $$bitOr(10100_2, 00110_2) = 10110_2 = 22$$.

Упражнения

Определите, является ли высказыванием предложение

a) "Проверьте напряжение в электросети";

b) "Что посеешь, то и пожнешь";

c) "Земля вращается вокруг Солнца";

d) "Это предложение ложное".

Составьте из высказываний A: "Идет дождь" и B: "Мы сидим дома" высказывание

a) A B;

b) $$A \vee B$$;

c) $$A \to B$$;

d) $$\neg B \to A$$;

e) $$A \leftrightarrow B$$;

f) $$A \oplus B$$;

g) $$A \mid B$$;

h) $$A \downarrow B$$.

Составьте из высказываний A: "Идет дождь" и B: "Мы сидим дома" сложное высказывание, которое является

a) тавтологией;

b) противоречием.

Определите, является ли тавтологией высказывание

a) $$ (А \ \neg А) \vee \neg А$$;

b) $$А \vee \neg В \vee \neg А$$;

c) $$ (А \ \neg А) \vee B$$;

d) $$ (А \vee \neg В) \vee А$$.

Составьте таблицу истинности для высказывания

a) $$(A \mid B) \leftrightarrow (A \downarrow B)$$;

b) $$A \oplus B \oplus C$$.

Упростите выражение

a)$$ab \vee \bar a \vee \bar b$$;

b) $$ab \bar c \vee \bar a b \bar c \vee bc$$;

c) $$\bar a \bar b \bar c \vee \bar a b \bar c \vee a \vee c$$;

d) $$\overline{ab| \overline{a \vee b} \vee ab(a \vee b)$$.

Покажите, что в произвольной булевой алгебре верно равенство

a)$$a \bar b\vee \bar a b =(a \vee b)(\bar a \vee \bar b)$$;

b) $$a\vee b \vee c=a\bar b\vee b\bar c\vee c \bar a\vee abc$$.

Используя свойства логических операций, решите задачу.

Сестры Маша, Даша и Глаша испекли пирог. Одна из них месила тесто, другая готовила начинку, а третья выпекала пирог. Известно, что каждое из следующих высказываний истинно:

если Глаша месила тесто, то Даша готовила начинку;

если Маша выпекала пирог, то месила тесто Даша;

если Глаша готовила начинку, то Маша выпекала пирог;

если Даша месила тесто, то Маша готовила начинку;

если Глаша выпекала пирог, то Маша месила тесто.

Кто из них месил тесто, кто готовил начинку, а кто выпекал пирог?

Составьте для логической функции таблицу истинности и постройте по ней 1) СДНФ; 2) СКНФ, если функция на множестве {0, 1} определяется следующим образом:

a)$$f(x,y,z)=\begin{cases} 1, x+y+z > 1,\\ 0, x+y+z \le1 \end{cases}$$

b)$$f(x,y,z)=\begin{cases} 1,x < y+z,\\ 0, xge y+z \end{cases}$$

Постройте электронную логическую схему для функции

a) $$f(a,b,c)=\overline{z \vee \bar b}\vee \bar c$$

b)$$ f(a,b,c)=(a\mid b)(a \downarrow c)$$.

Составьте таблицу истинности и постройте электронную логическую схему для одноразрядного полусумматора (см. пример 21).

Постройте электронные логические схемы для логической операции 1) конъюнкции; 2) дизъюнкции; 3) отрицания; 4) строгой дизъюнкции; 5) эквиваленции, используя только

a) схему И-НЕ;

b) схему ИЛИ-НЕ.

Постройте электронные логические схемы для функций из упр. 4.9.

Постройте логическую функцию по электронной логической схеме

a) рис. 4.14 (a); b) рис. 4.14 (b). (рис 4.14) Электронные логические схемы

Вычислите результат побитовой операции отрицания, если тип данных использует для хранения чисел 4 байта, для числа

a) 33;

b) $$2^{32} - 7$$.

Вычислите результат побитовой операции:

a) bitAnd(7, 8);

b) bitOr(16, 1);

c) bitXor(9, 9);

d) bitAnd(17, 23);

e) bitOr(17, 23);

f) bitXor(17, 23);

g) bitAnd(100, 10);

h) bitOr(25, 5);

i) bitXor(0, 10).

Вычислите результат арифметического битового сдвига

a) bitShiftLeft(33);

b) bitShiftRight(19, 2).

Вычислите результат логического битового сдвига числа x на k разрядов влево для типа данных с 32 разрядами:

a) $$x = 2^{31} + 15, k = 1$$;

b) $$x = 2^{32} - 20, k = 1$$;

c) x = 70, k = 5;

d) $$x = 2^{30} + 10, k = 2$$.

Вычислите bitOr(bitLeft(6, 3), bitLeft(10, 2), bitLeft(7, 1)).

Вычислите bitAnd(bitRight(26, 3), bitRight(17, 4)).