Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
f 1 , f 3 и f 4 , являются выходными полюсами. Им соответствуют термы: f 1 (x 1 , x 2 , x 3 ), f 3 (x 1 x 2 , f 1 (x 1 , x 2 , x 3 )), f 4 (f 3 (x 1 x 2 , f 1 (x 1 , x 2 , x 3 ), x 3 ), x 3 , f 2 (f 1 (x 1 , x 2 , x 3 ), f 1 (x 1 , x 2 , x 3 ), x 3 )). На рис. 6.26б изображен функциональный элемент, определяемый верши- ной, помеченной символом f 4 . Ему соответствует устройство, показанное на рис. 6.26в. ¤ В примере 6.11.1 продемонстрировано, что каждый вывод схемы порож- дает некоторый терм. Говорят, что функция f реализуется схемой Σ, если существует такой выход a схемы Σ, что функция f a , соответствующая терму выхода a, экви- валентна функции f . Схемы из функциональных элементов с одним выходом, у которых вход- ные полюса помечены символами x 1 , x 2 , . . ., x n , а вершины, отличные от вход- ных полюсов, — символами ∨, &, ¬, называются X n -функциональными схе- мами. Сложностью схемы из функциональных элементов называется чис- ло ее вершин, отличных от входных полюсов. X n -Функциональная схема Σ, •³ ³³ ³³ ³³ ³ ³ 1• ½ ½ ½ ½ ½½ > • ¢ ¢ ¢ ¢ ¢¢¸ • •H HH j HH H j Á • ©© ©© ©© *• ? • - H HH j•H HH j A A A A AAU U - x 3 x 2 x 1 f 4 f 3 & ¬ f 1 f 2 1 1 1 1 2 3 3 3 2 2 1 2 1 2 • ¡ ¡ ¡ µ - @ @ @ R f 4 f 4 а б в Рис. 6.26 220 Глава 6. АЛГЕБРА ЛОГИКИ • • • • • • ¬ ¬ ¬ • HH H j HH H j ©© © * • • ©© ©© ©© * HH HH HH HH HH H H j XXXX XXXX XXXX z -• -• ¡ ¡ ¡ µ m ∨ & & & ∨ x 3 x 2 x 1 Рис. 6.27 g = z J(y 1 ,y 2 ,y 3 )+1 z 1 z 2 · · · z 8 y 3 y 2 y 1 Рис. 6.28 реализующая функцию f , называется минимальной, если всякая другая X n - функциональная схема, реализующая f , имеет сложность, не меньшую, чем сложность схемы Σ. Сложность минимальной схемы, реализующей функ- цию f , называется сложностью функции f в классе схем из функциональ- ных элементов и обозначается через L(f ). Пример 6.11.2. Сложность функции f = (x 1 ∨ x 2 )x 3 ∨ x 1 x 2 x 3 совпадает со сложностью X 3 -функциональной схемы, изображенной на рис. 6.27, и рав- на 8: L(f ) = 8. ¤ 3. Мультиплексоры Мультиплексором 2 m каналов (MUX 2 m ) называется схема с m + 2 m вхо- дами y 1 , y 2 , . . ., y m , z 1 , z 2 , . . ., z 2 m и одним выходом g, в которой при y 1 = b 1 , . . . , y m = b m выход g принимает значение g = z J(b 1 ,...,b m )+1 , где J(b 1 , . . . , b m ) = 2 0 b 1 + 2 1 b 2 + . . . + 2 m−1 b m На рис. 6.28 показан мультиплексор MUX 8 6.11. ЛОГИЧЕСКИЕ СЕТИ 221 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 222 Глава 6. АЛГЕБРА ЛОГИКИ присоединен инвертор 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. Проверка теоретико-множественных соотношений с помощью алгебры логики Мы уже отмечали, что теоретико-множественным операциям ∪, ∩, , ⊕ соответствует операции ∨, ∧, , ⊕ на множестве формул. Заменяя теоретико- множественные выражения на формулы и анализируя эти формулы, можно свести исследование взаимоотношения теоретико-множественных выраже- ний к изучению взаимосвязи формул. Следующий пример демонстрирует, как происходит проверка теоретико- множественных соотношений с помощью алгебры логики. 6.13. ЛОГИЧЕСКИЕ ЗАДАЧИ 223 Пример 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. На следствии по делу о похищении автомобиля были допрошены четыре гангстера — Андре, Боб, Стив, Том. Андре сказал, что машину похитил Боб, Боб утверждал, что виноват Том. Том заверил следо- вателя, что Боб лжет. Стив настаивал, что автомобиль угнал не он. Следо- вателю удалось установить, что только один из гангстеров сказал правду. Кто похитил автомобиль? 224 Глава 6. АЛГЕБРА ЛОГИКИ Решение. Обозначим высказывания “Андре украл”, “Боб украл”, “Стив украл”, “Том украл” через А, Б, С и Т соответственно. Тогда показания ганг- стеров имеют вид Б, Т, Т, С. Поскольку только один из гангстеров сказал правду, имеет место истинная формула ϕ БT T С ∨ БTT С ∨ Б T T С∨ ∨Б T T С. В этой формуле первый и четвертый конъюнкты тождественно ложны (так как содержат T T). Поэтому ϕ ∼ БTTС∨Б T TС ∼ БTС∨Б TС ∼ ∼ Б ∧ С. Поскольку имеет место Б и С, автомобиль украл Стив. ¤ Минимизация КНФ зачастую позволяет свести серию сложных условий к достаточно простым. Пример 6.13.2. В институте решили организовать гимнастическую сек- цию и понадобилось разработать правила приема в эту секцию. Студенты внесли несколько предложений: • если студент не здоров и не отличник, то он не может быть принят; • если студент является отличником, то не может быть, чтобы он был здоров и его не приняли; • если студент не здоров, то он не отличник и не будет принят; • если студент не принят, то он не отличник. Оказалось, что внесенные предложения сводятся двум простым и есте- ственным правилам (которые и были взяты за основу). Действительно, рас- смотрим элементарные высказывания: З — студент здоров, О — студент яв- ляется отличником, П — студент принят в секцию. Тогда внесенные предло- жения записываются и преобразуются следующим образом: З О → П ∼ З О ∨ П ∼ З ∨ О ∨ П ∼ З ∨ О ∨ П; О → ЗП ∼ О ∨ З ∨ П ∼ О ∨ З ∨ П; З → О П ∼ З ∨ О П ∼ З ∨ О П; П → О ∼ П ∨ О. Конъюнкция ϕ полученных формул составляет описание внесенных предло- жений. Минимальная ДНФ для формулы ϕ имеет вид ЗП ∨ П О, что соот- ветствует предложению “Студент здоров и принят, или не принят и не явля- ется отличником”. Вместе с тем, МКНФ формулы ϕ представляется в виде (О ∨ П)(П ∨ З), что эквивалентно формуле (О → П)(П → З). Последняя формула и соответствует двум искомым правилам: • если студент является отличником, то он будет принят в секцию; • если студент принят, то необходимо, чтобы он был здоров. ¤ ЗАДАЧИ И УПРАЖНЕНИЯ 225 Задачи и упражнения 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)). 226 Глава 6. АЛГЕБРА ЛОГИКИ 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) |