1237
.pdfУпрощаем, используя закон дистрибутивности, оказывается, он справедлив и для импликации!
Избавимся от знака импликации:
Переобозначим вершины для использования Logic Converter, где переменные буквенные:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
A |
B |
C |
D |
E |
F |
G |
H |
|
|
|
|
|
|
|
|
Итак, имеем (рис. П2.2)
аб
Рис. П2.2. Развёртка куба: а – числовое обозначение вершин; б – буквенное обозначение вершин
Тогда:
Преобразуем символы логических операций, в используемые в Logic Converter в системе NI Multisim 10 by National Instruments Electronics Workbench Group (дизъюнкция – «+», инверсия – апост-
роф «’»). Хорошо, что максимальное число переменных равно 8.
131
Вводим в Logic Converter (рис. П2.3), получаем таблицу истин-
ности (A|B →10|1).
Рис. П2.3. Ввод логического выражения внутренней устойчивости куба в Logic Converter
Затем минимизируем (SIMP) (рис. П2.4).
Рис. П2.4. Минимизация логического выражения внутренней устойчивости куба в Logic Converter
132
Берем первую конъюнкцию:
1)A’B’C’F’G’H’
Это D, E (рис. П2.5).
2)A’B’D‘E’G’H’
Это C, F (рис. П2.6).
3)A’C’D‘E’F’H’
Это B, G (рис. П2.7).
Рис. П2.5. Подмножество внутренней |
Рис. П2.6. Подмножество |
устойчивости куба D, E |
внутренней устойчивости |
|
куба C, F |
Рис. П2.7. Подмножество внутренней устойчивости куба B, G
Двигаемся дальше в окошке Logic Converter (рис. П2.8). Получаем:
4) A’D‘F’G’
Это B,E,H,C (рис. П2.9). 5) B’C’D‘E’F’G’
Это A,H (рис. П2.10).
133
Рис. П2.8. Логическое выражение внутренней устойчивости куба в Logic Converter
Рис. П2.9. Подмножество внутренней |
Рис. П2.10. Подмножество |
устойчивости куба B,E,H,C |
внутренней устойчивости куба A,H |
Рис. П2.11. Подмножество внутренней устойчивости куба A,D,F,G
6) B’C’E’H’
Это A,D,F,G (рис. П2.11).
Таким образом, максимальное независимое множество содержит 4 вершины.
134
Множество внешней устойчивости куба (рис. П2.12)
Рис. П2.12. Куб
Вводим логическое выражение внешней устойчивости по методу Магу (рис. П2.13).
Рис. П2.13. Логическое выражение внешней устойчивости куба
Минимизируем (рис. П2.14–2.15).
Рис. П2.14. Минимизация логического выражения внешней устойчивости куба (часть 1)
135
Рис. П2.15. Минимизация логического выражения внешней устойчивости куба (часть 2)
Некоторые подмножества вершин уже были: DE, CF, BG, AH. А этих не было (рис. П2.16–22).
Рис. П2.16. Подмножество внешней |
Рис. П2.17. Подмножество внешней |
устойчивости куба ABCD |
устойчивости куба ACEG |
Рис. П2.18. Подмножество внешней |
Рис. П2.19. Подмножество внешней |
устойчивости куба ADFG |
устойчивости куба BCEG |
136 |
|
Рис. П2.20. Подмножество внешней |
Рис. П2.21. Подмножество внешней |
устойчивости куба BDFH |
устойчивости куба СDGH |
Рис. П2.22. Подмножество внешней устойчивости куба EFGH
Попробуйте исследовать самостоятельно проекцию усечённого конуса с четырьмя вершинами (рис. П2.23).
Рис. П2.23. Проекция усечённого конуса с четырьмя вершинами
137
ПРИЛОЖЕНИЕ 3
Алгоритмическое решение задачи о Ханойской башне
Известна легенда, согласно которой в джунглях Вьетнама существует некий затерянный город Бенарес, а в нём – буддийский монастырь, знаменующий середину мира [30]. Давным-давно монахи этого монастыря чем-то провинились перед богом Брахмой. Разгневанный Брахма на бронзовом диске воздвиг три высоких стержня и на один из них нанизал 64 диска, сделанных из чистого золота, причем так, что каждый меньший диск лежит на большем. И возложил на монахов «послушание» перекладывания дисков с первого стержня на третий, пользуясь промежуточным вторым, таким образом, чтобы всегда меньшие диски лежали над большими – т.е. не абы как, а «соблюдая законы Брамы». Возможно, каждое такое перекладывание должно было сопровождаться, как при перебирании чёток, горячими молитвами и возгласами типа «Прости нас, великий Брахма»! Сам вид Брамы вызывает неизгладимое впечатление (рис. П3.1).
Рис. П3.1. Бог Брахма
138
Как только все 64 диска будут переложены с первого на третий, как ни странно, монахи прощены не будут, а напротив, башня вместе с храмом обратятся в пыль, и под громовые раскаты погибнет весь мир.
Для 64 колец это 18 446 744 073 709 551 615 перекладываний, и если учесть скорость одного перекладывания в секунду, то получится около 584 542 046 091 лет (как говорил один известный политик, «башню сносит!»), т.е. апокалипсис наступит нескоро.
Вот детская игрушка – головоломка, известная в России с начала ХХ века (рис. П3.2).
Рис. П3.2. Головоломка «Ханойская башня»
Автор прекрасно помнит приснопамятные годы на рубеже 80-х
и«лихих» 90-х, когда в продаже появились первые «персональные» компьютеры БК 010 (Б – бытовой! компьютер) (рис. П3.3), так вот в составе игровых программ, записанных на магнитной ленте, была
изадача о Ханойской башне.
Рис. П3.3. Незабвенный БК 010, подключаемый к монитору, как правило, не входивший в комплект
139
В Ханое действительно есть башня, весьма далёкая от описанной в легенде, неофициальный символ города (рис. П3.4).
Рис. П3.4. Ханойская башня
Всамом деле, «три алмазных стержня, высотой в один локоть
итолщиной с пчелу» – это, скорее, три башни, поэтому, наверное, правильнее говорить «ханойские башни». Как утверждают источники, эту
Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas; 1842–1891)
140
легенду и игру придумал французский математик Франсуа Эдуард Анатоль Люка [30].
Важнейшие работы Люка относятся к теории чисел. Он считал, что с помощью машин или каких-либо приспособлений, сложение удобнее производить в двоичной системе, чем в десятичной. Вероятно, легенда и название игры навеяны экзотикой Вьетнама, ведь в то время он был колонизирован Францией.
В настоящее время рассматриваются задачи с четырьмя и более дисками, но мы ограничимся классическим вариантом.