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

  • Определение.

  • Индекс Набор 1 0100 2 0011 0101 1001 3 0111 1101 1110 4 1111 Второй уровень: Набор

  • 0011 0100 0101 0111 1001 1101 1110 1111 010- * * 0-11 * * 1-01

  • Различие методов Карно и Квайна – Мак-Класки

  • Сходство методов Карно и Квайна – Мак-Класки

  • Индекс Набор 0 0000 1 0010 1000 2 0101 0110 1001 3 0111 1110 4 1111 Второй уровень: Набор

  • 0000 0010 0101 0110 0111 1000 1001 1110 1111 00-0 * * -000 * * 0-10

  • Лекция №4. Минимизация булевых функций


    Скачать 400.29 Kb.
    НазваниеМинимизация булевых функций
    Дата16.06.2021
    Размер400.29 Kb.
    Формат файлаpdf
    Имя файлаЛекция №4.pdf
    ТипЛекция
    #217959

    С этим файлом связано 5 файл(ов). Среди них: mat_logika.docx, Лекция.pdf, Лекция №5.pdf, Лекция №3.pdf, Задачи к экзамену по математической логике и теории алгоритмов.p.
    Показать все связанные файлы
    Подборка по базе: манап лекция.docx, Готовая лекция на стропальщика.docx, нов лекция 1 по НСЭС.docx, 10 лекция.pptx, 3 лекция-.pptx, 13 лекция.pptx, План конспект лекция.docx, КД. Лекция 1. Сущность и содержание КД.doc, 1. Лекция 1-2 Элементы линейной алгебры.doc, Введение в специальность, лекция 9, 10, 21ш9-21ш11.docx

    1
    Лекция №4 по математической логике и теории алгоритмов
    Тема: Минимизация булевых функций
    методом Квайна−Мак-Класки.
    Данный метод применяется для любого числа переменных
    (практически не более 10), допускает возможность построения компьютерной программы минимизации. Рассмотрим вначале случай, когда функция представлена в виде множества единичных наборов, каждая конъюнкция которой переведена в двоичные вектора.
    Напомним, что «склеивание» можно проводить только между наборами, которые отличаются между собой только одной переменной, а, значит, число единиц в этих наборах будет отличаться только на единицу.
    Например, набору
    t
    z
    xy соответствует вектор
    1101
    , в котором 3 единицы, а соседнему с ним по переменной
    x
    набору
    t
    z
    y
    x
    соответствует вектор
    0101
    с числом единиц 2.
    Метод КвайнаМак-Класки делится на два этапа.
    На первом этапе разделим все наборы на группы по числу единиц в них.
    Определение. Индексом двоичного набора называется число единиц в нем.
    Так как склеиваться могут только наборы из соседних групп, то последовательно проводим все склеивания, которые только возможно.
    В результате этой операции на втором уровне получаем вектора, в которых используется символ «−» как символ неопределенного значения. Так после склеивания рассмотренных выше наборов, на втором уровне получим вектор
    t
    z
    y

    В результате проведенных склеиваний на втором уровне после склеивания наборов, содержащих i и
    )
    1
    (

    i
    единиц, получим группу, все элементы которой содержат i единиц. Затем снова сравниваем вектора из соседних групп, склеиваем отличающиеся только в одной позиции вектора. Это отличие может быть только в том, что в некотором разряде одного вектора стоит 0, в том же разряде второго вектора стоит 1, а все остальные разряды совпадают полностью, с учетом и символов «−». Так, если на втором уровне в группе с тремя единицами получили вектор
    1011

    , а в группе с числом единиц два получили вектор
    1010

    , то их склеиваем и получаем на третьем уровне в группе с двумя единицами вектор


    101
    . Эту операцию продолжаем

    2 до тех пор, пока возможно. В результате на r-м уровне получим вектора, число символов «−» в которых равно (r-1). Такую операцию проводим, пока возможно.
    Пример. Функция от четырех переменных представлена как 0011,
    0100, 0101, 0111, 1001, 1101, 1110, 1111.
    Решение. Разобьем конъюнкции, представленные двоичными наборами, на группы в зависимости от числа единиц в представлении:
    Первый уровень:
    Индекс
    Набор
    1 0100 2
    0011 0101 1001 3
    0111 1101 1110 4
    1111
    Второй уровень:
    Набор
    1-2 010-
    2-3 0-11 01-1
    -101 1-01 3-4
    -111 11-1 111-
    Третий уровень:
    Набор
    1-2 010-
    2-3 0-11 1-01 3-4 111-
    2-3-3-4
    -1-1
    -1-1

    3
    На втором этапе строим таблицу покрытия (таблица Квайна для исходной функции). Столбцы таблицы составляют векторы исходной функции. Строки таблицы – это полученные наборы.
    Для рассматриваемого примера таблица имеет вид:
    0011
    0100
    0101
    0111
    1001
    1101
    1110
    1111
    010-
    *
    *
    0-11
    *
    *
    1-01
    *
    *
    111-
    *
    *
    -1-1
    *
    *
    *
    *
    Суть второго этапа заключается в том, чтобы выбрать минимальное число строк, покрывающих все столбцы. Начинается решение задачи с выбора столбцов, содержащих единственную отметку (звездочку).
    Конъюнкции, которые им соответствуют являются существенными, они остаются в решении. Таким, например, является столбец 0011: в решении необходимо взять конъюнкцию 0-11, иначе конъюнкция 0011 покрыта не будет (не войдет в решение). Но выбор конъюнкции 0-11 покрывает и конъюнкцию 0111, поэтому отмечаем эти два столбца.
    Таким же образом поступаем с конъюнкцией 0100, 1001 и 1110, которые требуют в решение, соответственно, конъюнкции 010-, 1-01 и
    111-. Но первая покрывает еще и 0101, вторая – 1101, третья – 1111. В результате все исходные конъюнкции оказываются покрытыми.
    Решение найдено, функция будет иметь минимальную ДНФ в виде:
    xyz
    t
    z
    x
    z
    y
    x
    zt
    x
    f




    Заметим, что в этом примере самая короткая конъюнкция -1-1, покрывающая наибольшее число исходных конъюнкций, в решение не вошло.
    Различие методов Карно и Квайна – Мак-Класки:
    1. Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных (
    6

    n
    ). В методе Квайна –
    Мак-Класки отсутствуют ограничения на число переменных логической функции.
    2. Метод
    Карно является визуальным и сложным для алгоритмизации. Метод минимизации Квайна – Мак-Класки является систематичным и его легко алгоритмизировать.

    4
    Сходство методов Карно и Квайна – Мак-Класки:
    1. Векторы соседних клеток карты Карно соответствуют векторам соседних секций таблицы склеивания метода Квайна – Мак-Класки.
    2. Объединение в контуры на карте Карно соответствуют склеиванию в методе Квайна – Мак-Класки.
    Пример. Дана функция
    xyzt
    t
    xyz
    yzt
    x
    t
    z
    y
    x
    t
    yz
    x
    t
    z
    y
    x
    t
    z
    y
    x
    t
    z
    y
    x
    t
    z
    y
    x
    f














    Получить МДНФ методом Квайна – Мак-Класки и методом Карно.
    Решение. 1. Запишем функцию в двоичном виде и разделим двоичные векторы на секции по числу единиц. Составим таблицу интервалов, используя правило склеивания. Склеивать между собой можно только соседние векторы, которые могут находиться только в соседних секциях таблицы.
    Первый уровень:
    Индекс
    Набор
    0 0000 1
    0010 1000 2
    0101 0110 1001 3
    0111 1110 4
    1111
    Второй уровень:
    Набор
    0-1 00-0
    -000 1-2 0-10 100-
    2-3 01-1 011-
    -110 3-4
    -111 111-

    5
    Третий уровень:
    Набор
    0-1 00-0
    -000 1-2 0-10 100-
    2-3 01-1 2-3-3-4
    -11-
    -11-
    Дальнейшее склеивание невозможно. Построим таблицу покрытия
    (таблица Квайна для исходной функции):
    0000
    0010
    0101
    0110
    0111
    1000
    1001
    1110 1111
    00-0
    *
    *
    -000
    *
    *
    0-10
    *
    *
    100-
    *
    *
    01-1
    *
    *
    -11-
    *
    *
    *
    *
    Так как элементарные конъюнкции, которые соответствуют 4-6 строкам таблицы покрывают не все столбцы (1 и 2 столбцы остались без покрытия), то из 1-3 строк необходимо выбрать, те элементарные конъюнкции, которые минимально покрывают эти столбцы. Такой элементарной конъюнкцией является первая
    0 00

    Запишем МДНФ:
    yz
    yt
    x
    z
    y
    x
    t
    y
    x
    f






    2. Составим карту Карно для исходной функции:
    t
    z
    t
    z
    zt
    t
    z
    y
    x

    1 1
    y
    x
    1 1
    1
    xy
    1 1
    y
    x
    1 1
    В результате получаем МДНФ:
    yz
    t
    y
    x
    yt
    x
    z
    y
    x
    f








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