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

  • D min =D 1 туп =D 2туп

  • D min =D 1 =D 2 Задача 3

  • 2 3 4 4

  • Типовой расчёт. вар 63. Московский государственный институт радиотехники, электроники и автоматики


    Скачать 428.5 Kb.
    НазваниеМосковский государственный институт радиотехники, электроники и автоматики
    АнкорТиповой расчёт. вар 63.doc
    Дата05.11.2017
    Размер428.5 Kb.
    Формат файлаdoc
    Имя файлаТиповой расчёт. вар 63.doc
    ТипЗадача
    #10144
    КатегорияМатематика

    Подборка по базе: Тема 2. 14 Государственный бюджет ответы.docx, - для института.pdf, Образование социальных институтов (исправленный вариант).docx, задание по теме Государственный механизм и государственный аппар, Карагандинский государственный медицинский университет.docx, Министерство образования и науки Российской Федерации Уральский , ГОСТ 19.201-78 (СТ СЭВ 1627-79). Государственный стандарт Со.rtf, КОНТРОЛЬНАЯ РАБОТА СОЦИАЛЬНЫЙ ИНСТИТУТ ПОНЯТИЕ ТИПОЛОГИЯ СТРУКТУ, На 01.01.2021 Государственный долг.doc, Охрана труда как институт трудового права 1081 (1).doc



    МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

    (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

    Типовой расчёт

    по предмету

    « Основы дискретной математики »

    студента группы ВСС 1-97

    Рахмукова Владимира

    Москва, 2000 г.

    Вариант 63
    Задача 1

    Проверить полноту системы функций ={ fi ; gj }, найти Dmin для функций fi , gj. Представить формулами над  и функциональными схемами над  функции 0,1,,&,,hk.
    63 = (2100)3



    1. Проверяем полноту системы функций .







    T0

    T1

    S

    M

    L







    x1

    x2

    x3

    f0

    g1

    f0

    +

    -

    -

    -

    +







    0

    0

    0

    0

    1

    g1

    -

    -

    +

    -

    -







    0

    0

    1

    1

    1

























    0

    1

    0

    0

    1

























    0

    1

    1

    1

    0

























    1

    0

    0

    1

    1

























    1

    0

    1

    0

    0

























    1

    1

    0

    1

    0

























    1

    1

    1

    0

    0



    Определение линейности функции.
    Найдём многочлен Жегалкина для функций и :







    В многочлене Жегалкина конъюнкций переменных нет, следовательно, функция линейная.







    В многочлене Жегалкина есть конъюнкции переменных, поэтому функция нелинейная.

    Система функций целиком не входит ни в один из 5 замкнутых классов , таким образом, критерий полноты системы функций (Теорема Поста) выполняется (необходимость).


    1. Достаточность.


    Доказательством достаточности является построение из функции системы основных элементарных булевых функций.


    1. Берём функцию, не принадлежащую классу , т.е. функцию и получаем:

    отрицание
    Воспользуемся Леммой 1, и из функции , используя , получим одну из констант. Найдём взаимно противоположные пары наборов, на которых значение функции одно и тоже. Например, наборы . Выбираем любой из них.

    , получаем константу 1.

    Взяв её отрицание, получим константу 0:

    Константу 0 можно также получить и следующим образом:
    Берём, так как , следовательно

    1. По Лемме 3 из функции можно получить конъюнкцию или дизъюнкцию.


    Чтобы сохранить конъюнкцию , подставим вместо константу 1.



    теперь вместо . получаем конъюнкцию xy =

    Дизъюнкцию xy получим по закону двойственности


    Формула над для функции .

    x1

    x2

    h0

    0

    0

    0

    0

    1

    1

    1

    0

    0

    1

    1

    0


    Функциональные схемы над функций .



    Определение Dмин для функций f0, g1 .




    x1

    x2

    x3

    f0

    g1

    0

    0

    0

    0

    1

    0

    0

    1

    1

    1

    0

    1

    0

    0

    1

    0

    1

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    0

    0

    1

    1

    0

    1

    0

    1

    1

    1

    0

    0



    1. Для функции .




    • Интервалов ранга 1 нет.

    • Интервалы ранга 2:



    • Интервалов ранга 3 нет.



    • , , ранг





    1. Для функции .

    • Интервалов ранга 1 нет.

    • Интервалы ранга 2:



    • Интервалов ранга 3 нет.



    • , , ранг

    Задача 2

    Найти Dсокр, Dя, все Dmin для f ( x1, x2, x3, x4 ) методом Карно и Квайна.




    63= ( 0011 1111 )2



    Метод Карно




    00

    01

    11

    10

    00




    1

    1




    01

    1

    1







    11

    1










    10




    1

    1

    1









    00

    01

    11

    10

    00




    1

    1




    01

    1

    1







    11

    1










    10




    1

    1

    1






    00

    01

    11

    10

    00




    1

    1




    01

    1

    1







    11

    1










    10




    1

    1

    1


    Dmin=D1туп=D2туп

    Метод Квайна.


    x3x4

    x1x2

    00

    01

    11

    10

    00




    1

    1




    01

    1

    1







    11

    1










    10




    1

    1

    1

























    k1

    0001

    *

    00-1

    *

    -0-1

    1

    k2

    0100

    *

    0-01

    5

    -0-1




    k3

    0011

    *

    -001

    *







    k4

    0101

    *

    010-

    4







    k5

    1100

    *

    -100

    3







    k6

    1001

    *

    -011

    *







    k7

    1010

    *

    10-1

    *







    k8

    1011

    *

    101-

    2
















    k1

    k2

    k3

    k4

    k5

    k6

    k7

    k8

    1

    X




    X







    X




    X

    2



















    X

    X

    3




    X







    X










    4




    X




    X













    5

    X







    X


















    k4

    4

    X

    5

    X







    Dmin=D1=D2

    Задача 3

    Построить минимальную функциональную схему для функции f из задачи 2 на элементах {,&,}.






    Задача 4

    Построить минимальную контактную схему для той же функции.





    Задача 5

    Решить задачу об оптимальном назначении с матрицей эффективности В.




    ai\bi

    0

    0

    0

    0

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4





    ai\bi

    0

    0

    0

    0

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4






    ai\bi

    0

    0

    0

    0

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4




    ai\bi

    0

    0

    0

    0

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4

    4

    1

    2

    3

    4





    Задача 6

    Найти максимальный поток в транспортной сети. Пропускная способность рёбер определяется элементами матрицы В из задачи 5.


    1 (1)

    1 (1)

    3 (1)

    2 (0)

    4 (0)

    2 (0)

    3 (0)

    2 (2)

    4 (2)

    1 (0)

    2 (0)

    3 (3)

    4 (3)

    1 (0)

    1 (0)

    b

    a

    G


    |
    4 (3)







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