Декомпозиция функций Пример 2

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

• Функция представляется через функцию меньшей размерности и функциональные переменные.  

• Пример: функция от пяти переменных, принимающая значения 0 и 1.  

• Функция принимает значения 0 в точках 2, 6, 10, 11, 12, 17, 21, 22 и 1 в точках 5, 7, 9, 15, 27, 28, 30, 31.  

• Задача: представить функцию в виде системы с меньшим количеством переменных.  

• Рассматривается безповторная функциональная композиция.  

• Матрица речи разбивает пространство переменных на две части.  

• Пример разбиения: икс а и икс б.  

• Матрица речи похожа на таблицу истинности, но двумерная.  

• Единицы ставятся на пересечении строк и столбцов, соответствующих единичным точкам функции.  

• Пример заполнения: точки 5, 7, 9, 15, 27, 28, 30, 31.  

• Пустые клетки указывают на точки, где функция не определена.  

• Объединение строк и столбцов для уменьшения количества переменных.  

• Пример объединения: второй и последний столбцы, первый и второй строки.  

• Объединение возможно, если новое количество строк или столбцов можно закодировать меньшим количеством переменных.  

• Условия до композиции: если после объединения строк или столбцов новое количество строк или столбцов можно закодировать меньшим количеством переменных, то декомпозиция возможна.  

• Пример: декомпозиция по столбцам возможна, по строкам – нет.  

• Объединение столбцов возможно, если логарифм нового количества столбцов по основанию два меньше количества переменных.  

• Пример: объединение столбцов возможно, так как логарифм двух столбцов меньше трех переменных.  

• Новая матрица речи: строки остаются прежними, столбцов становится два, вводится функциональная переменная фиа.  

• Новая матрица речи: строки остаются прежними, столбцов становится два.  

• Введение функциональной переменной  

• Объединяем строки, заполняя пустые ячейки единицами.  

• Проверяем правильность заполнения, исправляя ошибки.  

• Получаем матрицу свечи.  

• Кодируем столбцы, используя функциональную переменную фиа.  

• Проверяем, определена ли функция во всех точках.  

• Функция определена во всех точках и принимает значения 0 и 1.  

• Записываем функцию, зависящую от переменных икс один, икс два и фиа.  

• Функция полностью определена, но может быть не полностью определена в некоторых случаях.  

• Записываем значения функции в точках.  

• Минимизируем функцию, применяя закон склеивания и импликативную таблицу.  

• Находим ядро покрытия и записываем функцию в более правильном виде.  

• Функция зависит от переменных икс один, икс два и фиа.  

• Рисуем схему включения функциональных и терминальных переменных.  

• Функция эф зависит от переменных икс один, икс два и фиа.  

• Переменные икс три, икс четыре, икс пять включаются в функцию фиа.  

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

• Функция от пяти переменных представлена в виде системы функций от трех переменных.  

• Важно знать минимизацию и покрытие для правильного выполнения декомпозиции.  

• Покрытие находится на глазок.  

• Строка покрывает столбец, если содержит единицу в этом столбце.  

• Первая строка покрывает первые два столбца, последняя строка также базовая.  

• Если не все столбцы покрыты, возможны несколько вариантов покрытия.  

• Если есть еще одна строка с единицей, будет два варианта покрытия.  

• Пример: первое покрытие включает строки 1, 2, 3, второе покрытие включает строки 1, 2 и 4.  

• Первый столбец покрывается строкой а или больше ничего.  

• Второй столбец покрывается строкой а или б.  

• Третий столбец покрывается строкой б или ц.  

• Четвертый столбец покрывается только строкой ц.  

• Внешняя операция мультипликативная, внутренние аддитивные.  

• Применение законов булевой алгебры для преобразования выражений.  

• Пример: поглощение скобок и преобразование дизъюнкции в конъюнкцию.  

• Важность понимания логических операций в дискретной математике.  

• Вопросы и ответы по теме.