дискретная. дискретка. Задача Построить таблицу истинности для заданной формулы. Обозначим F
![]()
|
КОНТРОЛЬНАЯ РАБОТА Условия задач Задача 1. Построить таблицу истинности для заданной формулы. ![]() Обозначим F= ![]()
Задача 2. Преобразовать данную формулу так, чтобы она содержала только операции тесного отрицания, дизъюнкции и конъюнкции. Пользуясь свойствами операций дизъюнкции и конъюнкции, привести формулу к виду, не содержащему скобок. 2. ![]() Будем использовать известные тождества ![]() Законы де Моргана ![]() . ![]() ![]() ![]() Задача 3. Из колоды в 36 карт вынимают ![]() ![]() ![]() ![]() Случай 1. Выбор с возвращением. Так как карта после выбора возвращается в колоду, количество бубновых (9 карт), пиковых (9 карт) и других карт (18 карт) в колоде не меняются. Тогда количество способов выбрать 8 карт из 36 так, чтобы из них 3 были бубновой масти будет 9*9*9, 2 карты пиковой масти будет 9*9 и еще оставшиеся 3 другой масти будет 18*18*18. При этом, так как выбор упорядоченный, карты можно переставлять между собой, число различных перестановок равно ![]() Итого получаем ![]() Случай 2. Выбор без возвращения. Нужно выбрать 8 карт из 36 так, чтобы из них 3 были бубновой масти (всего таких карт 9), 2 карты пиковой масти (всего таких карт 9) и еще 3 другой масти (всего их 18), откуда получаем по правилу умножения ![]() способов (снова умножили на число способов упорядочить выбранные карты). Задача 4. Пользуясь Алгоритмом Дейкстры, найти кратчайшие расстояния из вершины ![]() ![]() ![]() ![]()
Решение. Найдем кратчайший путь от вершины ![]() Шаг 1. Начальная вершина v1 . Присвоим ей метку 0, остальным - ![]() Шаг 2. Из вершины v1 можно попасть в v2,v3,v4,v6 L(v1,v2)=min{ ![]() L(v1,v3)=min{ ![]() L(v1,v4)=min{ ![]() L(v1,v6)=min{ ![]() min{1,3,8,1}=1 (вершина v2) Шаг 3. Из вершины v2 можно попасть в v3 L(v2,v3)=min{3;1+2}=3 min{3,8,1}=1 (вершина v6) шаг 4. Из вершины v6 можно попасть в v3,v4,v5 L(v6,v3)=min{3;1+1}=2 L(v6,v4)=min{8;1+2}=3 L(v6,v5)=min{ ![]() min{2,3,3}=2 (вершина v3) шаг 5. Из вершины v3 можно попасть в v4 (остальные рассмотрены) L(v3,v4)=min{4;3+1}=4 min{4,6}=4 (вершина v4) шаг 6. Из вершины v4 можно попасть в v5 (остальные рассмотрены) L(v4,v5)=min{6;4+3}=6
Задача 5. Схема дорог, соединяющих населенные пункты, задана графом, показанным на рисунке. В таблице каждому ребру графа поставлен в соответствие вес, характеризующий стоимость прокладки дороги, соединяющей данные населенные пункты. При помощи алгоритма Краскала построить схему дорог, соединяющих данные населенные пункты, при наименьшей стоимости проекта. ![]()
Решение. Найдем остовное дерево минимального веса (то есть схему дорог наименьшей стоимости) с помощью алгоритма Краскала. Пронумеруем вершины графа для удобства, ребра пометим весом (стоимостью) согласно варианту. Начинаем с ребра минимального веса (x1,x2) , его вес равен 1. Затем по очереди добавляем ребра минимального веса, так, чтобы они не образовали цикла. Порядок добавления: Ребро (x1,x2), его вес равен 1. ребро (x1,x4), его вес равен 1 ребро (x4,x5), его вес равен 1 . ребро (x4,x3), его вес равен 1 ребро (41,x7), его вес равен 1 ребро (51,x6), его вес равен 1 ребро (x6,x9), его вес равен 1 ребро (x7,x8), его вес равен 1 Все вершины добавлены в дерево. Минимальное остовное дерево построено. Обведем его на чертеже: Его вес равен 1+1+1+1+1+1+1+1=8 Задача 6. Выяснить, применима ли машина Тьюринга, заданная программой ![]() ![]() ![]() Решение. Начальное состояние машины ![]() Шаг 1. Начальное слово ...0 ![]() ![]() Многоточием обозначаем бесконечную ленту. Шаг 2. Применяем правило ![]() ![]() Получаем слово: ![]() Состояние ![]() Шаг 3. Применяем правило ![]() ![]() Получаем слово: ![]() Состояние ![]() Шаг 4. Применяем правило ![]() ![]() Получаем слово: ![]() Состояние ![]() Так как мы пришли к конечному состоянию, программа машины Тьюринга применима к данному слову и переводит его в слово T =111101 (меняет первый нуль на 1). |