Главная страница
Навигация по странице:

  • Практическое задание 2 Тема 2. Основные формулы комбинаторики

  • Практическое задание 3 Тема 4. Нормальные формы. Тупиковая, минимальная и сокращенная ДНФ

  • Практическое задание 4 Тема 7. Полные и двудольные графы. Операции над графами. Связность. Диаметр, радиус, центр графа

  • Решение: G

  • Дискретная математика. Дискретная математика решение. Решение Возьмём неравенство Рассмотрим уравнение


    Скачать 175.49 Kb.
    НазваниеРешение Возьмём неравенство Рассмотрим уравнение
    АнкорДискретная математика
    Дата03.11.2022
    Размер175.49 Kb.
    Формат файлаdocx
    Имя файлаДискретная математика решение.docx
    ТипРешение
    #768918



    Практическое задание 1

    Тема 1. Множества, соответствия, отношения

    1. Пусть A, B, C, - множество точек плоскости, координаты которых удовлетворяют условиям , и соответственно. Изобразите в системе координат x0y множество D, полученное из множеств A, B и C по формуле
      .

    Решение:

    Возьмём неравенство: .

    Рассмотрим уравнение: .

    Мы получили уравнение окружности с центром в точке (0,0) и радиусом 2.

    Возьмем пробную точку (0,1) и подставим её в неравенство:

    .

    Эта точка удовлетворяет неравенству. Следовательно, неравенству соответствует внутренняя часть окружности.




    1. Выяснить взаимное расположение множеств D, E, F, если А, В, Х – произвольные подмножества универсального множества U.



    условие

    D

    E

    F

    \ А)  (Х\В)

     ( X)

    ĀX

    Решение:

    Используем диаграмму Эйлера-Венна.



    U= {1,2,3,4,5,6,7,8}, A= {1,2,4,5}, B= {4,5,6,7}, X= {2,3,5,7}.







    Практическое задание 2

    Тема 2. Основные формулы комбинаторики

    1. Сколькими способами из колоды в 36 листов можно выбрать не упорядоченный набор из 5 карт так, чтобы в этом наборе было бы точно:

    3 туза, 3 карты черной масти

    Решение:

    3 туза

    - количество способов, достать 3 туза из 4-х

    – количество способов (в дополнение к этим трём тузам) достать оставшиеся 2 карты из 32-х

    – общее количество способов

    3 карты черной масти:

    2 пары карт черной масти



    Общее количество способов:

    Ответ: 2802

    2. Сколько различных слов можно получить перестановкой букв слова a?



    условие

    Диктатура

    Как гласные, так и согласные идут в алфавитном порядке

    Решение:

    Ответ: 126 способов.
    3. Найти наибольший член разложения бинома

    Пусть - наибольший член разложения бинома ,

    .
















    т.к.



    Ответ: Наибольший член разложения бинома .

    1. Найти коэффициенты при x22 в разложении данного выражения (3-x2+x5)12 по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов.

    Решение:






    0

    2

    4

    6


    Практическое задание 3

    Тема 4. Нормальные формы. Тупиковая, минимальная и сокращенная ДНФ

    Для данных функций и , заданных векторно в

    f

    g

    0111 1110

    1011 1111 1110 0010

    , проделать следующее:

    1. Записать их СДНФ и СКНФ.

    2. Методом Квайна найти сокращённую ДНФ.

    3. Для сокращенной ДНФ построить матрицу Квайна, указать ядровые импликанты.

    4. С помощью матрицы Квайна найти минимальную ДНФ, указать её сложность.

    5. Найти минимальную ДНФ данной функции с помощью карт Карнау, сравнить полученный результат с ДНФ, найденной в п.4.

    Решение:

    Таблицы истинности функций.

    x y z



    000

    0

    001

    1

    010

    1

    011

    1

    100

    1

    101

    1

    110

    1

    111

    0




    x y z t

    f(x,y,z,t)

    0000

    1

    0001

    0

    0010

    1

    0011

    1

    0100

    1

    0101

    1

    0110

    1

    0111

    1

    1000

    1

    1001

    1

    1010

    1

    1011

    0

    1100

    0

    1101

    0

    1110

    1

    1111

    0




    1. СДНФ:

    ,



    СКНФ:






    1. Сокращенная ДНФ: .


    0 0 1

    0 1 -

    0 1 0 +

    1 0 -

    0 1 1 +

    1 0 0 +


    1 0 1 +

    1 1 0


    - - 0

    I полоса

    II полоса



    0 0 0 0 +

    0 1 - -




    0 0 1 0 +

    0 0 1 1 +

    1 0 0 -



    - - 1 0

    1 - - 0

    - 0 0 -



    0 1 0 0 +

    0 1 0 1 +

    0 1 1 0 +

    1 0 0 0 +

    1 0 0 1 +

    1 0 1 0 +

    1 1 0 0

    0 1 1 1 +

    1 1 1 0


    1 1 1 1



    III полоса

    I полоса


    II полоса
    Сокращенная ДНФ данной булевой функции имеет вид:

    .


    1. Получение из сокращенной ДНФ минимальной ДНФ с помощью матрицы Квайна.

    простой импликанты

    1

    2

    3

    простые импликанты
    единичные наборы







    0 0 1







    1

    0 1 0




    1




    0 1 1







    1

    1 0 0

    1







    1 0 1

    1







    1 1 0




    1






    № простой импликанты

    1

    2

    3

    4

    5

    простые импликанты
    единичные наборы











    0 0 0 0




    1

    1







    0 0 1 0




    1

    1

    1




    0 0 1 1




    1







    1

    0 1 0 0




    1




    1

    1

    0 1 0 1

    1













    0 1 1 0







    1







    0 1 1 1







    1

    1




    1 0 0 0










    1

    1

    1 0 0 1













    1

    1 0 1 0
















    1 1 1 0

    1















    4. Для функции все три импликанты являются ядровыми. Поэтому сокращённая ДНФ является и минимальной, её сложность равна 6.

    Для функции ядровыми импликантами являются 1, 2, 3, и 5.

    Минимальная ДНФ: , её сложность равна 12.

    5. Найдем минимальную ДНФ с помощью карт Карнау.

    yz

    x

    01

    11

    11

    10

    0

    1

    1

    0

    0

    1

    1

    0

    1

    1

    Минимальная ДНФ, , сложность равна шести. Эта полученная минимальная ДНФ отличается от полученной в пункте 4. Сложности полученных ДНФ одинаковые.

    zt

    xy

    10

    11

    11

    11

    11

    1

    1

    0

    0

    10

    0

    0

    0

    1

    00

    0

    1

    1

    1

    10

    1

    1

    1

    1

    Минимальная ДНФ: , совпадает с полученной в пункте 4.



    Практическое задание 4

    Тема 7. Полные и двудольные графы. Операции над графами. Связность. Диаметр, радиус, центр графа

    Даны графы G1 и G2. В таблице 3.1.

    1. Найдите G1G2, G1∩G2, G1G2 аналитически и изобразить результат графически.

    2. Для графа G=G1G2 найдите матрицу смежности, матрицу инцидентности, компоненты сильной связности, маршруты (но не цепи) длины 7; простые цепи, простые циклы, исходящие из вершины 1. С помощью матрицы смежности определите количество путей длины 2, 3, 4 из вершины 1 в вершину 4, из вершины 2 в вершину 4, выясните имеются ли контуры в графе.

    3. Найдите степени всех вершин, радиус и диаметр графа G.

    4. Является ли граф G эйлеровым, если нет, то постройте эйлеров цикл.

    G1

    G2

    1 2



    3 4

    1



    3 2


    Решение:

    G1

    G2

    1 2



    3 4

    1



    3 2



    .



    1 2



    3 4

    G=G1G2



    1



    3 2




    , ,

    1 2



    3 4


    2. Матрица смежности

    Матрица инцидентности.
    , ,4), , , , , .

    .

    Матрица связанности.



    Граф имеет один компонент связности {1, 2, 3}.

    1 2



    3

    Маршрут: 1 – 2 – 3.

    Циклы: 1 – 2 – 4 – 1, 1 – 3 – 4 – 1. .

    Цепи: 1 – 2 – 4, 1 – 3 - 4.
    Из вершины 1 в вершину 4, следует 1 путь. Из вершины 2 в вершину 4, следует 1 путь.
    3. Радиус = 1 (1 – 2). Диаметр = 2 (3 – 1 – 2).
    Вершина 1 = 2 степень, вершина 2 = 3 степень, вершина 3 = 2 степень,

    вершина 4 вершина = 0.
    4. Эйлеров цикл: 1 – 2 – 4 - 3 – 1.

    1 2



    3 4


    написать администратору сайта