Спирина, М.С. Дискретная математика

Алгоритмы А. А. Маркова являются не только средством некоторых теоретических построений, но и основой специализированного языка программирования, который применяется в качестве языка символьных преобразований при разработке систем искусственного интеллекта. Наибольшее распространение для формализации понятия «алгоритм» получили так называемые рекурсивные функции, широко использую­ щие элементы теории множеств, особенно композицию функций, де­ картова произведения, операции с подмножествами. Рассмотрим несколько задач, решаемых с помощью теории множеств. Задача 14. Пятьдесят лучших студентов колледжа наградили за успехи поездкой в Англию и Германию. Из них 5 не владели ни одним разговорным иностранным языком, 34 знали английский язык и 27 — немецкий. Сколько студентов владели двумя разго­ ворными иностранными языками? Решение. Введем обозначения множеств: Е — множество студентов, не владеющих ни одним иностран­ ным языком; А — множество всех студентов, \А\ = 50; В — множество студентов, владеющих английским языком, 1*1 = 34; С — множество студентов, владеющих немецким языком, |С| = = 27; D — множество студентов, владеющих английским и немец­ ким языками, |Z)| = х. Представим множества графически с помощью кругов Эйлера (рис. 1.20). Способ 1. Составим уравнение: 34х - jc + 2 7 - x + jc + 5 = 50, откуда х = 16. Способ 2. Найдем \D\ из уравнения |5 | + |С| - \D\ =\A\ - 5 или 34 + + 27 - х = 50 - 5, отсюда х = 16. Следовательно, 16 студентов свободно общались на двух ино­ странных языках. Задача 15. Каждый студент группы программистов занимается в свободное время либо в НСО, либо спортом. Сколько студентов в группе, если 23 увлекаются спортом, 12 занимаются в НСО, а 7 совмещают занятия в НСО и увлечение спортом? Решение. Изобразим множества кру­ гами Эйлера, обозначив множества «спортсменов» — А и «исследователей» — В (рис. 1.21). Тогда п(А П В) = 7, п(А) = Рис. 1 .20. Схематическоеизоб- =23, п(В) = 12; п(А[] В) =п(А) +п(В) - ражение условия задачи 14 - п{А П В) = 23 + 12 - 7 = 28. 60