Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

218
Глава 6. АЛГЕБРА ЛОГИКИ
z
1
z
2
z
p
g
1
g
2
g
q
Решетка элементов
&
(c
ih
)
d
C
CC
¤
¤¤
d
C
CC
¤
¤¤ · · ·
d
C
CC
¤
¤¤
b
³
³
P
P
b
³
³
P
P
b
³
³
P
P
f
1
f
2
f
m
b
((
hh b
((
hh b
((
hh
Решетка элементов
&
(a
ih
)
Решетка элементов
&
(b
hj
)
Рис. 6.29
Рис. 6.30
Пример 6.11.3. Если
m = 3,
y
1
= 1,
y
2
= 0,
y
3
= 1,
то
g =
= z
J(1,0,1)+1
= z
6
. ¤
С помощью мультиплексора MUX
2
m
, придавая переменным z
1
, z
2
, . . ., z
2
m
постоянные значения, можно реализовать любую булеву функцию
f (y
1
, y
2
, . . . , y
m
).
4.
Программируемые логические матрицы
Рассмотрим схему, состоящую из p входов z
1
, . . ., z
p
и q выходов g
1
, . . ., g
q
(рис. 6.29), в которой значения выходов определяются матрицей соедине-
ний (c
ih
), 1 6 i 6 p, 1 6 h 6 q, c
ih
∈ {0, 1} по следующим правилам:
g
h
= (z
1
∨ c
1h
) · (z
2
∨ c
2h
) · . . . · (z
p
∨ c
ph
). Таким образом, g
h
= z
i
1
z
i
2
. . . z
i
r
,
где c
i
1
h
= c
i
2
h
= . . . = c
i
r
h
= 1, а остальные c
ih
равны 0. Полученная схема называется решеткой c p входами и q выходами элементов &, которая определяется матрицей соединений (c
ih
).
Программируемой логической матрицей (ПЛМ) называется изображен- ная на рис. 6.30 схема, получающаяся соединением решетки A с 2n входа- ми и k выходами, определяемой матрицей соединений (a
ih
), и решетки B
с k входами и m выходами, определяемой матрицей соединений (b
hj
).
Опишем преобразования, которые происходят при прохождении через
ПЛМ значений переменных x
1
, x
2
, . . ., x
n
. Поскольку к каждому входу x
i

6.12. ПРОВЕРКА ТЕОРЕТИКО-МНОЖЕСТВЕННЫХ СООТНОШЕНИЙ
219
присоединен инвертор x
i
, на 2n входов решетки A подаются значения пере- менных x
1
, x
1
, x
2
, x
2
, . . . , x
n
, x
n
. После прохождения решетки A h-й выход принимает значение функции (x
1
∨ a
1h
)(x
1
∨ a
2h
) . . . (x
n
∨ a
2n−1,h
)(x
n
∨ a
2n,h
),
а последующей операции инвертирования соответствует функция
(x
1
∨ a
1h
)(x
1
∨ a
2h
) . . . (x
n
∨ a
2n−1,h
)(x
n
∨ a
2n,h
).
Полученные k значений (1 6 h 6 k) подаются на входы решетки B, после прохождения которой на выходе j образуется значение функции
k
^
h=1
((x
1
∨ a
1h
)(x
1
∨ a
2h
) . . . (x
n
∨ a
2n−1,h
)(x ∨ a
2n,h
) ∨ b
hj
).
В заключение после инвертирования по законам де Моргана на выходе j
получаем значение функции
f
j
=
k
_
h=1
b
hj
(x
1
∨ a
1h
)(x
1
∨ a
2h
) . . . (x
n
∨ a
2n−1,h
)(x
n
∨ a
2n,h
), j = 1, . . . , m.
Функции f
j
соответствует дизъюнкция конъюнктов (определяемых форму- лами (x
1
∨ a
1h
)(x
1
∨ a
2h
) . . . (x
n
∨ a
2n−1,h
)(x
n
∨ a
2n,h
)) таких, что b
hj
= 1.
Таким образом, при соответствующем выборе матриц (a
ih
) и (b
hj
) можно одновременно реализовать m произвольных ДНФ, содержащих не более k
различных конъюнктов от переменных x
1
, x
2
, . . ., x
n
§ 6.12.
Проверка теоретико-множественных соотношений с помощью алгебры логики
Мы уже отмечали, что теоретико-множественным операциям ∪, ∩, , ⊕
соответствует операции ∨, ∧, , ⊕ на множестве формул. Заменяя теоретико- множественные выражения на формулы и анализируя эти формулы, можно свести исследование взаимоотношения теоретико-множественных выраже- ний к изучению взаимосвязи формул.
Следующий пример демонстрирует, как происходит проверка теоретико- множественных соотношений с помощью алгебры логики.

220
Глава 6. АЛГЕБРА ЛОГИКИ
Пример 6.12.1. С помощью алгебры логики проверим истинность соот- ношения
(A ⊕ B) \ C = A ⊕ (B \ C)
(6.5)
для любых множеств A, B, C.
Поставим в соответствие множествам A, B и C логические переменные
x, y и z. В силу тождества A \ B = A ∩ B (см. пример 1.1.6) выражение
(A⊕B)\C преобразуется в формулу ϕ ­ (x⊕y)∧z, а выражение A⊕(B\C) —
в формулу ψ ­ x ⊕ (y ∧ z). Составив таблицы истинности формул ϕ и ψ:
x
0 0
0 0
1 1
1 1
y
0 0
1 1
0 0
1 1
z
0 1
0 1
0 1
0 1
ϕ
0 0
1 0
1 0
0 0
ψ
0 0
1 0
1 1
0 1,
убеждаемся, что ϕ 6∼ ψ: f
ϕ
(1, 0, 1) = 0, а f
ψ
(1, 0, 1) = 1. Тем самым соотно- шение (6.5) неверно.
Для построения контрпримера, опровергающего равенство (6.5), восполь- зуемся различием значений функций f
ϕ
и f
ψ
на наборе (1, 0, 1). Считая,
что 1 соответствует множествам, содержащим некоторый элемент a, а 0 —
множеству, не содержащему этот элемент, положим
A ­ {a}, B ­ ∅, C ­ {a}.
Имеем (A ⊕ B) \ C = A \ A = ∅, тогда как A ⊕ (B \ C) = A ⊕ ∅ = A 6= ∅. ¤
§ 6.13.
Логические задачи
Аппарат алгебры логики позволяет решать так называемые “логические”
задачи. При этом самым трудным моментом является построение “модели”
задачи, т. е. выделение элементарных высказываний и сведение задачи к про- верке некоторых свойств высказываний, возникающих из условий задачи.
Пример 6.13.1. На следствии по делу о похищении автомобиля были допрошены четыре гангстера — Андре, Боб, Стив, Том. Андре сказал, что машину похитил Боб, Боб утверждал, что виноват Том. Том заверил следо- вателя, что Боб лжет. Стив настаивал, что автомобиль угнал не он. Следо- вателю удалось установить, что только один из гангстеров сказал правду.

6.13. ЛОГИЧЕСКИЕ ЗАДАЧИ
221
Решение. Обозначим высказывания “Андре украл”, “Боб украл”, “Стив украл”, “Том украл” через А, Б, С и Т соответственно. Тогда показания ганг- стеров имеют вид Б, Т, Т, С. Поскольку только один из гангстеров сказал правду, имеет место истинная формула ϕ ­ БT T С ∨ БTT С ∨ Б T T С∨
∨Б T T С. В этой формуле первый и четвертый конъюнкты тождественно ложны (так как содержат T T). Поэтому ϕ ∼ БTTС∨Б T TС ∼ БTС∨Б TС ∼
∼ Б ∧ С. Поскольку имеет место Б и С, автомобиль украл Стив. ¤
Минимизация КНФ зачастую позволяет свести серию сложных условий к достаточно простым.
Пример 6.13.2. В институте решили организовать гимнастическую сек- цию и понадобилось разработать правила приема в эту секцию. Студенты внесли несколько предложений:
• если студент не здоров и не отличник, то он не может быть принят;
• если студент является отличником, то не может быть, чтобы он был здоров и его не приняли;
• если студент не здоров, то он не отличник и не будет принят;
• если студент не принят, то он не отличник.
Оказалось, что внесенные предложения сводятся двум простым и есте- ственным правилам (которые и были взяты за основу). Действительно, рас- смотрим элементарные высказывания: З — студент здоров, О — студент яв- ляется отличником, П — студент принят в секцию. Тогда внесенные предло- жения записываются и преобразуются следующим образом:
З О → П ∼ З О ∨ П ∼ З ∨ О ∨ П ∼ З ∨ О ∨ П;
О → ЗП ∼ О ∨ З ∨ П ∼ О ∨ З ∨ П;
З → О П ∼ З ∨ О П ∼ З ∨ О П;
П → О ∼ П ∨ О.
Конъюнкция ϕ полученных формул составляет описание внесенных предло- жений. Минимальная ДНФ для формулы ϕ имеет вид ЗП ∨ П О, что соот- ветствует предложению “Студент здоров и принят, или не принят и не явля- ется отличником”. Вместе с тем, МКНФ формулы ϕ представляется в виде
(О ∨ П)(П ∨ З), что эквивалентно формуле (О → П)(П → З). Последняя формула и соответствует двум искомым правилам:
• если студент является отличником, то он будет принят в секцию;
• если студент принят, то необходимо, чтобы он был здоров. ¤

222
Глава 6. АЛГЕБРА ЛОГИКИ
Задачи и упражнения
1. Составить таблицы истинности формул:
а) (y → x ∨ z) ∨ (x ∨ y → z);
б) x | y ↓ z | y ↓ x;
в) (x → y) ⊕ (y → z) ⊕ (z → x);
г) x ⊕ y → z ∨ x | y ∧ x;
д) (x ∨ y → zu) → x ∨ y;
е) x ∨ yz → zu ∨ y;
ж) (xz → y ∨ u) ∨ ((x → u ∨ z) → y);
з) (x ∨ y → z) ∨ (u → yz ∨ x);
и) (z → x ∨ y) → (z ∨ u → xy);
к) (x ∨ yz → u) → (y → xz ∨ u);
л) (z ∨ yu → x) ∨ (y ∨ z → u);
м) (x ∨ y ↔ xz) → x ∨ z;
н) x | (y → z) ↓ (z ⊕ x → y);
о) x | y | z → x ↓ y ↓ z;
п) x → z ⊕ (y ⊕ z)(x ⊕ y);
р) x ⊕ y ⊕ z ↔ x ↓ z;
с) (x ⊕ y | z) → (x ⊕ y) | (x ⊕ z);
т) (x ⊕ y → z) → (x → y ⊕ z);
у) xy ↓ z → x ↓ y;
ф) x(y ↓ z) → xy) ↓ z;
х) x ∨ y | z → (x ∨ y) | z;
ц) x ∨ y ↓ z → xy | z.
2. Установить, какие из следующих формул являются тождественно истинны- ми и какие — тождественно ложными:
а) (x → y) → ((x → z) → (x → y ∧ z));
б) (x → y) → ((x ∧ z) → (y ∨ z));
в) (x ⊕ y ↔ z)(x → yz);
г) xyz((x ∨ y)z → (x ↔ z ⊕ y));
д) (x ∨ y) ↓ (x ⊕ y) ⊕ (x → y → (x ∨ y)).

ЗАДАЧИ И УПРАЖНЕНИЯ
223 3. Проверить эквивалентности:
а) xy ∨ zu ∼ (x ∨ z)(x ∨ u)(y ∨ z)(y ∨ u);
б) x ∧ (x ∨ z) ∧ (y ∨ z) ∼ (x ∧ y) ∨ (x ∧ z);
в) xy ∨ xz ∨ yz ∨ z ∼ x ∨ y;
г) (x ∨ xy ∨ xy)(x ∨ xz ∨ xy ∨ xyz) ∼ x ∨ y;
д) (x ∨ y ∨ zx ∨ y ∨ yx ∨ u)(x ∨ xz ∨ xyz) ∼ x ∨ z;
е) (xy ∨ xyz ∨ xz)(x ∨ xz ∨ yx ∨ z) ∼ x ∨ z;
ж) (x ∨ xy ∨ yzu ∨ xu)(y ∨ yu ∨ yz(x ∨ u)) ∼ y ∨ u;
з) xyz(x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ yz)(xy ∨ yz) ∼ xyz;
и) xyz(x ∨ xyz ∨ z)(xz ∨ zu ∨ u)(xz ∨ yu) ∼ xyz;
к) (x ∨ xy ∨ y(z ∨ u))(yu ∨ x y u ∨ xu ∨ xy)yz ∼ yz;
л) xy ∨ xyz ∨ xzu ∨ xyu ∨ xu z ∼ x ∨ z;
м) xz ∨ x zu ∨ yzu ∨ xyz ∨ zu ∼ x ∨ z ∨ u;
о) yz ∨ xyz ∨ xzu ∨ xzu ∨ xzu ∼ x ∨ z;
п) xu ∨ xyu ∨ xzu ∨ xyu ∨ yu ∼ y ∨ u;
р) x yz ∨ xyz ∨ xy z ∨ xyz ∨ x z ∼ y ∨ z;
с) xy z ∨ xyz ∨ yzu ∨ yz ∨ yzu ∼ x ∨ z;
т) x yz ∨ xyz ∨ xyz ∨ xyz ∼ z;
у) (xz ∨ xy z ∨ xyz ∨ xz)(zu ∨ zu ∨ xyz) ∼ z;
ф) (xyz ∨ xyz ∨ yz ∨ xyz)(x ∨ xy ∨ x yz) ∼ x ∨ y;
х) (xy ∨ xz ∨ xy ∨ x y z)(x y ∨ yxz ∨ xzu ∨ xzu) ∼ x ∨ y;
ц) (yz ∨ xyz ∨ xyz)(xy ∨ x y ∨ xyz) ∼ xyz ∨ yz;
ч) (xyu ∨ xy ∨ yxu)(xu ∨ xyu ∨ x yu) ∼ xu ∨ yu ∨ xy;
ш) (x z ∨ z ∨ zu ∨ xy)(z ∨ zu ∨ xu ∨ y z u) ∼ z ∨ u ∨ xy ∨ x y;
щ) (yu ∨ xu ∨ xyu ∨ x yu)(x ∨ x u ∨ yu) ∼ x ∨ yu;
ы) y ∨ z ∨ x ∨ z ∨ xy ∼ xz ∨ yz;
э) x ∨ y(x ∨ z) ∨ yx ∨ z ∼ xy;
ю) x ∨ y ∨ z ∨ x ∨ z ∨ xy ∼ xz ∨ yz;
я) xz ∨ y ∨ y ∨ yx ∨ z ∼ xy ∨ yz.

224
Глава 6. АЛГЕБРА ЛОГИКИ
4. Привести к ДНФ, КНФ, СДНФ и СКНФ следующие формулы:
а) (x ∨ z)(x ∨ yz);
б) x ∨ ((x → yz)((z ⊕ u) → xu));
в) ((x | z ↓ x) ⊕ xy) ↔ (z → x);
г) x ∨ y ∨ x ∨ y ∨ z ∨ xyz;
д) y ∨ z ∨ x ∨ y ∨ z ∨ xyz;
е) xy ∨ yz ∨ x ∨ yz ∨ xyz;
ж) x ∨ (x ∨ z)y ∨ xy ∨ zxy ∨ x y;
з) yz ∨ xyz ∨ (x ∨ y)z ∨ yz ∨ x z;
и) x ∨ xyz ∨ y ∨ z(x ∨ y);
к) (xyz ∨ x(y ∨ z))z ∨ (x ∨ z)y ∨ xyz;
л) xy ∨ zx ∨ y;
м) xy ∨ yz ∨ x ∨ y ∨ z;
н) y ∨ z ∨ y z ∨ y ∨ xy ∨ xz;
о) (x ∨ y)(x ∨ z)(y ∨ z);
п) x ∨ y ∨ z ∨ z ∨ x(yz ∨ y z);
р) x ∨ z → y ∨ (y ↔ z);
с) (x ↔ (y → z)) ∨ x → y ∨ z;
т) xyz → x y → x ↔ z;
у) x ∨ y → z ↔ z → xy;
ф) x ∨ (y ∨ z → x) ↔ x → yz;
х) x → y → x → (z → x → y);
ц) x → y → z → x(y → z);
ч) xyz → yz → (z → xy);
ш) x ↔ (z → y) ∨ y → x ∨ y;
щ) (z → xy) ↔ (x → yz);
ы) z → y → x ↔ xz;
э) (z → y → x) → y(z ↔ x);
ю) (xy → z → (x ∨ z → xy)) → xy;
я) (x → (y ↔ x ∨ z)) → ((y → x ∨ z) → xz).

ЗАДАЧИ И УПРАЖНЕНИЯ
225 5. Используя метод Квайна и карты Карно, найти МДНФ и МКНФ следующих формул:
а) x y z ∨ xyz ∨ xyz ∨ xyz ∨ xyz;
б) y ∨ x z ∨ x ∨ z;
в) xz ∨ y z ∨ xy ∨ x ∨ y;
г) x ∨ yz ∨ y ∨ z;
д) (x → y(x → z)) → y(x ∨ y ↔ z);
е) (y → z → x) → (y ∨ z → x → yz);
ж) (x → (x ∨ y ↔ z)) → (x ∨ y ↔ yz);
з) ((yz ↔ x) → z) → y(x ∨ z ↔ z);
и) ((x ↔ yz) → z) → (x ∨ z ↔ y);
к) ((x ↔ y ∨ z) → x ∨ z) → (xz ∨ y → x y);
л) (z → (x ↔ y ∨ z)) → (xz ∨ y ↔ xyz);
м) (xy → z → y) → (xz ↔ x ∨ y);
н) (xz → (y ↔ z)) → (x ∨ y → xz);
о) ((y ∨ z ↔ xz) → y) → (z → x → xy);
п) (yz → x → z) → x(y ↔ z);
р) ((y ↔ z) → (x ∨ y → x z)) → yz → x;
с) (x → (y ∨ z ↔ x)) → y(z ↔ xy);
т) (x ∨ y z → x ∨ z) → y → x ∨ z;
у) ((y ∨ z ↔ xz) → xy) → y → x;
ф) x ∨ y → z → (x → yz → y(x ↔ z));
х) (xz → (y ↔ z)) → (x ∨ y → x → y ∨ z);
ц) (y ∨ z → x) → (z → y → xz);
ч) (xy → (x ∨ yz → y)) → (x ∨ z ↔ y ∨ z);
ш) (x → (x ∨ z ↔ y)) → (x ∨ z → yz);
щ) (y → (x ∨ z → z)) → x(y ↔ xz);
ы) ((y ∨ z ↔ x) → y) → (y → x ∨ z → yz → x);
э) (xy → (x ∨ z → y)) → (x ∨ z ↔ y ∨ z);
ю) (xz → (y ∨ z → x)) → (y ∨ z ↔ xy);
я) (xy → z → y) → (z → x ∨ y).

226
Глава 6. АЛГЕБРА ЛОГИКИ
1 1
1 1
1 1
1 1
1 1
1
x
y
z
u
x
y
z
u
0 0
0 0
0 0
0 0
0 0
0 0
Рис. 6.31
Рис. 6.32
6. Найти СДНФ и МДНФ по карте Карно, изображенной на рис. 6.31.
7. Найти СКНФ и МКНФ по карте Карно, изображенной на рис. 6.32.
8. Найти полиномы Жегалкина для следующих формул:
а) x ↓ y | z; б) (x → y)(y ↓ z); в) x | ((x → y) ∨ z).
9. Найти полином Жегалкина для булевой функции f , заданной следующим вектором значений. Определить, каким классам Поста принадлежит функ- ция f :
а) (10110100); б) (10010110); в) (11110101).
10. Проверить с помощью теоремы Поста полноту следующих систем булевых функций:
а) {→, ¬}; б) {↔, ⊕}; в) {↓}; г) {∧, →, ⊕}.

Какие из указанных систем образуют базис?
11. Среди всех булевых функций от двух переменных (см. § 6.3) найти всевоз- можные базисы, состоящие из одной, двух, трех функций.
12. Состоялся розыгрыш футбольного кубка между командами “Пламя”, “Ре- корд”, “Стрела” и “Трактор”. Было высказано три прогноза: победит “Пла- мя” или “Рекорд”; не победит “Пламя”; не победит ни “Рекорд”, ни “Трактор”.

Известно, что подтвердился только один прогноз. Какая команда выиграла кубок?
13. Андрей, Борис, Вова и Саша играли в футбол и разбили окно. Когда их спросили, кто это сделал, были получены следующие ответы. Андрей сказал,
что окно разбил не он и не Вова, а играть в футбол предложил Саша. Борис

ЗАДАЧИ И УПРАЖНЕНИЯ
227
ответил, что окно разбивал не он, а Вова, и добавил, что в футбол он играет лучше, чем Саша. Вова утверждал, что ни он, ни Андрей не разбивали окна,
а в футбол на улице он больше не будет играть. Саша заявил, что окно разбил не он, а Вова, и когда он пришел, игра была в полном разгаре.

Выяснилось, что каждый из ребят дал два правдивых показания и одно ложное. Кто разбил окно?
14. Три молодые супружеские пары собрались на дружеский ужин. Завязалась беседа. Были высказаны следующие утверждения:
• Андрош: Все трое мужчин на пять лет старше своих жен;
• Ева: Не стану отрицать, я самая старшая из всех жен;
• Имре: Нам с Юлишкой вместе 52 года;
• Ласло: Всем шестерым вместе 151 год;
• Юлишка: Нам с Ласло вместе 48 лет.

Марта была хозяйкой и не смогла принять участие в беседе. Кому сколько лет и кто на ком женат?
15. Пять отпускников встретились в клубе и завели разговор о том, кто где живет:
• Амели: Я живу в Акапулько, как и Бенуа, а Пьер живет в Париже;
• Бенуа: Я живу в Бресте, Шарль — тоже; Пьер живет в Париже;
• Пьер: Я, как и Амели не живу во Франции; Мелани же живет в Мадриде;
• Мелани: Мой отец живет в Акапулько, мать в Париже, а сама я живу в Клермон-Ферране;
• Шарль: Амели приехала из Акапулько, Бенуа — тоже, а я сам живу в Клермон-Ферране.

Известно, что каждый сказал два раза правду и один раз пошутил. Кто где живет?
16. Три брата, Пьер, Поль и Жак, во время отпуска собрали всех своих детей на даче. Вот что каждый из детей сказал:
• Изабелла: Мне на три года больше, чем Жану;
• Тереза: Моего отца зовут Жаком;
• Ив: Мне на 2 года больше, чем Изабелле;