Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Построение минимальных ДНФ | |
---|---|
Онлайн-сервисы
Нахождение НОД и НОК
Разложение числа на простые множители
Сравнения по модулю
Операции над множествами
Операции над векторами
Разложение вектора по базису. Доказательство, что векторы образуют базис
Чертёж треугольника по координатам вершин
Решение треугольника
Решение Пирамиды
Построение Пирамиды по координатам вершин
Чертёж многоугольника по координатам вершин
Решение систем методом Крамера и Матричным
Онлайн построение графика кривой 2-го порядка
Определение вида кривой или поверхности 2-го порядка по инвариантам
МНК и регрессионный анализ Онлайн + графики
Онлайн число, сумма и дата прописью
Алгоритмы JavaScript
Алгоритмы поиска
Алгоритмы сортировки
Уникальные элементы массива
Объединение, пересечение и разность массивов
НОД и НОК
Операции над матрицами
Дата прописью
Введение в анализ
Функции: понятие, определение, графики
Непрерывность функции
Исследование функции и построение графика
Теория множеств
Множества: понятие, определение, примеры
Точечные множества
Замкнутые и открытые множества
Мера множества
Группы, кольца, поля в математике
Поле комплексных чисел
Кольцо многочленов
Основная теорема алгебры и ее следствия
Математическая логика
Алгебра высказываний
Аксиоматика и логические рассуждения
Методы доказательств теорем
Алгебра высказываний и операции над ними
Формулы алгебры высказываний
Тавтологии алгебры высказываний
Логическая равносильность формул
Нормальные формы для формул высказываний
Логическое следование формул
Приложение алгебры высказываний для теорем
Дедуктивные и индуктивные умозаключения
Решение логических задач
Принцип полной дизъюнкции
Булевы функции
Множества, отношения и функции в логике
Булевы функции от одного и двух аргументов
Булевы функции от n аргументов
Системы булевых функций
Применение булевых функций к релейно-контактным схемам
Релейно-контактные схемы в ЭВМ
Практическое применение булевых функций
Теория формального
Формализованное исчисление высказываний
Полнота и другие свойства формализованного исчисления высказываний
Независимость системы аксиом формализованного исчисления высказываний
Логика предикатов
Логика предикатов
Логические операции над предикатами
Кванторные операции над предикатами
Формулы логики предикатов
Тавтологии логики предикатов
Преобразования формул и следование их предикатов
Проблемы разрешения для общезначимости и выполнимости формул
Применение логики предикатов в математике
Строение математических теорем
Аристотелева силлогистика и методы рассуждений
Принцип полной дизъюнкции в предикатной форме
Метод полной математической индукции
Необходимые и достаточные условия
Логика предикатов и алгебра множеств
Формализованное исчисление предикатов
Неформальные и формаль-ные аксиоматические теории
Неформальные аксиоматические теории
Свойства аксиоматических теорий
Формальные аксиоматические теории
Формализация теории аристотелевых силлогизмов
Свойства формализованного исчисления предикатов
Формальные теории первого порядка
Формализация математической теории
Теория алгоритмов
Интуитивное представление об алгоритмах
Машины Тьюринга и тезис
Рекурсивные функции
Нормальные алгоритмы Маркова
Разрешимость и перечислимость множеств
Неразрешимые алгоритмические проблемы
Теорема Гёделя о неполноте формальной арифметики
Математическая логика и компьютеры
Дискретная математика
Множества и отношения
Теория множеств: понятия и определения
Операции над множествами
Кортеж и декартово произведение множеств
Соответствия и бинарные отношения на множествах
Операции над соответствиями на множествах
Семейства множеств
Специальные свойства бинарных отношений
Отношения эквивалентности на множестве
Упорядоченные множества
Теорема о неподвижной точке
Мощность множества
Парадокс Рассела
Метод характеристических функций
Группы и кольца
Алгебраические структуры и операции
Группоиды, полугруппы, группы
Кольца, тела, поля
Области целостности в теории колец
Модули и линейные пространства
Подгруппы и подкольца
Теорема Лагранжа о порядке конечной группы
Гомоморфизмы групп и нормальные делители
Гомоморфизмы и изоморфизмы колец
Алгебра кватернионов
Полукольца и булевы алгебры
Полукольца: определение, аксиомы, примеры
Замкнутые полукольца
Полукольца и системы линейных уравнений
Булевы алгебры и полукольца
Решетки и полурешетки
Алгебраические системы
Алгебраические системы: модели и алгебры
Подсистемы алгебраических систем
Конгруэнции и фактор-системы
Гомоморфизмы алгебраических систем
Прямые произведения алгебраических систем
Конечные булевы алгебры
Многосортные алгебры
Теория графов
Теория графов: основные понятия и определения
Способы представления графов
Неориентированные и ориентированные деревья
Остовное дерево и алгоритм Краскала
Методы систематического обхода вершин графа
Алгоритмы поиска в глубину и ширину в графах
Задача о путях во взвешенных ориентированных графах
Изоморфизм, гомоморфизм и автоморфизм графов
Топологическая сортировка вершин графа
Элементы цикломатики в теории графов
Булева алгебра и функции
Булевы функции и булев куб
Таблицы булевых функций и булев оператор
Равенство булевых функций. Фиктивные переменные
Формулы и суперпозиции булевых функций
Дизъюнктивные и конъюнктивные нормальные формы
Построение минимальных ДНФ
Теорема Поста и классы
Критерий Поста
Схемы из функциональных элементов
Конечные автоматы и регулярные языки
Конечные автоматы и регулярные языки
Алфавит, слово, язык в программировании
Порождающие грамматики (грамматики Хомского)
Классификация грамматик и языков
Регулярные языки и регулярные выражения
Конечные автоматы
Допустимость языка конечным автоматом
Теорема Клини
Детерминизация конечных автоматов
Минимизация конечных автоматов
Лемма о разрастании для регулярных языков
Обоснование алгоритма детерминизации автоматов
Конечные автоматы с выходом
Морфизмы и конечные подстановки
Машины Тьюринга
Контекстно-свободные языки
Контекстно-свободные языки и грамматики
Приведенная форма КС-грамматики
Лемма о разрастании для КС-языков
Магазинные автоматы (автомат с магазинной памятью)
Алгоритм построения МП-автомата по КС-грамматике
Алгоритм построения КС-грамматики по МП-автомату
Алгебраические свойства КС-языков
Основное свойство суперпозиции КС-языков
Пересечение контекстно-свободных языков
Методы синтаксического анализа КС-языков
Восходящий синтаксический анализ и LR(k)-грамматики
Семантика формальных языков
Принцип индукции по неподвижной точке
Графовое представление МП-автоматов
Интегральное исчисление
Неопределённый и определённый
Неопределенный и определенный интегралы
Свойства интегралов
Интегрирование по частям
Интегрирование методом замены переменной
Интегрирование различных рациональных функций
Интегрирование различных иррациональных функций
Интегрирование различных тригонометрических функций
Определенный интеграл и его основные свойства
Необходимое и достаточное условие интегрируемости
Теоремы существования первообразной
Свойства определенных интегралов
Несобственные интегралы
Интегральное определение логарифмической функции
Приложения интегралов
Вычисление площадей плоских фигур
Площади фигур в различных координатах
Вычисление объемов тел с помощью интегралов
Объём тела вращения
Вычисление длин дуг кривых
Формулы длины дуги регулярной кривой
Кривизна плоской кривой
Площадь поверхности вращения тела
Интегралы в физике
Статические моменты и координаты центра тяжести
Теоремы Гульдина–Паппа
Вычисление моментов инерции
Другие приложения интегралов в физике
Основные интегралы
Вариационное исчисление
Примеры вариационных задач
Дифференциальное уравнение Эйлера
Функционалы, зависящие от нескольких функций
Задача о минимуме кратного интеграла
Финансовый анализ
Анализ эффективности
Критерии и показатели эффективности предприятия
Методы анализа эффективности деятельности
Факторный анализ прибыли от операционной деятельности
Анализ безубыточности предприятия
Операционный рычаг и эффект финансового рычага
Анализ и оценка состава, структуры и динамики доходов и расходов
Анализ рентабельности и резервов устойчивого роста капитала
Анализ распределения прибыли предприятия
Анализ и оценка чувствительности показателей эффективности
Анализ устойчивости
Финансовая устойчивость и долгосрочная платежеспособность
Характеристика типов финансовой устойчивости
Рыночная активность
Финансовый анализ рыночной активности
Методика анализа рыночной активности
Анализ и оценка дивидендного дохода на одну акцию
Инвестиционная деятельность
Инвестиции: экономическая сущность и классификация
Государственное регулирование инвестиционной деятельности
Источники финансовых ресурсов на капитальные вложения
Инвестиции в основные фонды
Оценка состояния основных фондов
Амортизация основных фондов
Капитальное строительство в инвестиционном процессе
Планирование инвестиций в форме капитальных вложений
Экономическая эффективность инвестиций
Финансирование капитальных вложений
Кредитование капитальных вложений
Кредитоспособность
Финансирование и кредитование затрат
Финансирование и кредитование инвестиционной деятельности потребительской кооперации
Финансирование и кредитование капитальных вложений потребительской кооперации
Инвестиционное строительное проектирование
Анализ инвестиций
Инвестиции и инвестиционная деятельность предприятия
Задачи финансового анализа инвестиций предприятия
Учет фактора времени в инвестиционной деятельности
Аннуитет и финансовая рента в инвестициях
Учет фактора инфляции при инвестировании
Оценка фактора риска инвестиционного проекта
Методы оценки эффективности инвестиций
Показатели эффективности инвестиционного проекта
Стоимость компании
Концепция построения международных стандартов финансовой отчетности (МСФО)
Экономическое содержание международных стандартов финансовой отчётности
Цели и принципы оценки стоимости акций и активов компании
Оценка акций и активов предприятия по справедливой стоимости
Методы оценки справедливой стоимости акций предприятия
Затратный подход к оценки стоимости компаний и акций
Сравнительный подход к оценки стоимости предприятий и акций
Доходный подход к оценке стоимости компании и акций
Выбор ставки дисконтирования при инвестировании в акции
Метод капитализации прибыли
Сравнение подходов к оценке стоимости компаний и пакетов акций
Форвардные контракты
Форвардный контракт и цена
Форвардная цена акции на бирже
Цена форвардного контракта инвестора
Форвардная цена акции с учетом величины дивиденда
Форвардная цена акции с учетом ставки дивиденда
Форвардная цена валюты на рынке форекс
Форвардный валютный курс и инфляция на рынке
Форвардная цена товара и спотовый рынок
Форвардная цена при различии ставок по кредитам и депозитам
Синтетический форвардный контракт на акции и валюту
Теория вероятностей
Основные понятия теории вероятностей
Зависимые и независимые случайные события
Повторные независимые испытания
Формула Бернулли
Одномерные случайные величины
Многомерные случайные величины
Функции случайных величин
Законы распределения целочисленных случайных величин
Законы распределения непрерывных случайных величин
Предельные теоремы теории вероятностей
Закон больших чисел и предельные теоремы
Вероятностные закономерности
Математическая статистика
Элементы математической статистики
Выборочный метод
Оценки параметров генеральной совокупности
Статистические гипотезы
Критерии согласия
Теоретические и эмпирические частоты
Теория очередей (СМО)
Определение системы массового обслуживания
Уравнения Колмогорова
Предельные вероятности состояний
Определение СМО с отказами
Определение СМО с ожиданием (очередью)
Аналитическая геометрия
Векторная алгебра
Метрические понятия и аксиомы геометрии
Равенство и подобие геометрических фигур
Бинарные отношения
Вектор, его направление и длина
Линейные операции над векторами
Линейная зависимость и независимость векторов
Отношение коллинеарных векторов
Проекции векторов на прямую и на плоскость
Угол между векторами
Ортогональные проекции векторов
Координата вектора на прямой и базис
Координаты вектора на плоскости и базис
Координаты вектора в пространстве и базис
Операции над векторами в координатной форме
Ортогональный и ортонормированный базисы
Cкалярное произведение векторов и его свойства
Выражение скалярного произведения через координаты векторов
Векторное произведение векторов и его свойства
Смешанное произведение векторов и его свойства
Ориентированные площади и объемы
Двойное векторное произведение и его свойства
Применение векторов в задачах на аффинные свойства фигур
Применение произведений векторов при решении геометрических задач
Применение векторной алгебры в механике
Системы координат
Прямоугольные координаты
Преобразования прямоугольных координат
Полярная система координат
Цилиндрическая система координат
Сферические координаты
Аффинные координаты
Аффинные преобразования координат
Аффинные преобразования плоскости
Примеры аффинных преобразований плоскости
Аффинные преобразования пространства
Многомерное координатное пространство
Линейные и аффинные подпространства
Скалярное произведение n-мерных векторов
Преобразования систем координат
Геометрия на плоскости
Алгебраические линии на плоскости
Общие уравнения геометрических мест точек
Алгебраические уравнения линий на плоскости
Уравнения прямой, проходящей через точку перпендикулярно вектору
Уравнения прямой, проходящей через точку коллинеарно вектору
Уравнения прямой, проходящей через две точки
Уравнения прямой с угловым коэффициентом
Взаимное расположение прямых
Примеры задач с прямыми на плоскости
Системы неравенств с двумя неизвестными
Системы линейных уравнений с двумя неизвестными
Линии 2-го порядка
Канонические уравнения линий второго порядка
Порядок приведения уравнения линии к каноническому виду
Эллипс
Гипербола
Парабола
Квадратичные неравенства с двумя неизвестными
Применение линий 1-го и 2-го порядков в задачах на экстремум функций
Инварианты линий
Классификация линий 2-го порядка по инвариантам
Приведение уравнения линии к каноническому виду по инвариантам
Геометрия в пространстве
Способы задания ГМТ в пространстве
Алгебраические уравнения поверхностей
Уравнения плоскости, проходящей через точку перпендикулярно вектору
Уравнения плоскости, компланарной двум неколлинеарным векторам
Уравнения плоскости, проходящей через три точки
Взаимное расположение плоскостей
Типовые задачи с плоскостями
Уравнения прямых в пространстве
Взаимное расположение прямых в пространстве
Типовые задачи с прямыми в пространстве
Поверхности 2-го порядка
Канонические уравнения поверхностей
Порядок приведения уравнения поверхности к каноническому виду
Поверхности второго порядка
Эллипсоиды
Гиперболоиды
Конусы
Параболоиды
Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций
Инварианты поверхностей
Линейная алгебра
Матрицы и операции
Линейные операции над матрицами
Умножение матриц
Возведение матриц в степень
Многочлены от матриц
Транспонирование и сопряжение матриц
Блочные матрицы
Произведение и сумма матриц Кронекера
Метод Гаусса приведения матрицы к ступенчатому виду
Элементарные преобразования матриц
Определители
Определители матриц и их основные свойства
Формула полного разложения определителя
Формула Лапласа полного разложения определителя
Определитель произведения матриц
Методы вычисления определителей
Ранг матрицы
Линейная зависимость и линейная независимость строк (столбцов) матрицы
Ранг матрицы и базисный минор матрицы
Методы вычисления ранга матрицы
Ранг системы столбцов (строк)
Обратная матрица
Обратные матрицы и их свойства
Ортогональные и унитарные матрицы
Способы нахождения обратной матрицы
Матричные уравнения
Односторонние обратные матрицы
Скелетное разложение матрицы
Полуобратная матрица
Псевдообратная матрица
Системы уравнений
Системы линейных алгебраических уравнений
Метод Гаусса решения систем линейных уравнений
Структура общего решения системы уравнений
Решение систем с помощью полуобратных матриц
Псевдорешения системы линейных уравнений
Функциональные матрицы
Функциональные матрицы скалярного аргумента
Производные матриц по векторному аргументу
Линейные и квадратичные формы и их преобразования
Приведение форм к каноническому виду
Закон инерции вещественных квадратичных форм
Знакоопределенность форм вещественных квадратичных
Формы и исследование функций на экстремум
Многочленные матрицы
Многочленные матрицы (лямбда-матрицы)
Операции над лямбда-матрицами
Простые преобразования многочленных матриц
Инвариантные множители многочленной матрицы
Функции от матриц
Собственные векторы и значения матрицы
Подобие числовых матриц
Характеристический многочлен матрицы
Минимальный многочлен матрицы
Теорема Гамильтона-Кэли
Жорданова форма матрицы
Приведение матрицы к жордановой форме
Многочлены от матриц
Применение многочленов от матриц
Функции от матриц
Линейные пространства
Линейные пространства: определение и примеры
Линейная зависимость и независимость n-мерных векторов
Размерность и базис линейного пространства
Преобразования координат в линейном пространстве
Изоморфизм линейных пространств
Подпространства
Подпространства линейного пространства
Пересечение и сумма подпространств
Способы описания подпространств
Нахождение дополнения и суммы подпространств
Нахождение пересечения подпространств
Линейные отображения
Линейные многообразия
Линейные отображения
Матрица линейного отображения
Ядро и образ линейного отображения
Линейные операторы
Линейные операторы (преобразования)
Инвариантные подпространства
Собственные векторы и значения оператора
Свойства собственных векторов операторов
Канонический вид линейного оператора
Методика приведения линейного преобразования к каноническому виду
Евклидовы пространства
Евклидовы пространства
Ортогональные векторы евклидова пространства
Ортогональный базис евклидова пространства
Ортонормированный базис евклидова пространства
Ортогональные дополнения в евклидовом пространстве
Задача о перпендикуляре
Матрица и определитель Грама и его свойства
Линейные преобразования евклидовых пространств
Канонический вид ортогонального оператора евклидова пространства
Сопряженные операторы евклидова пространства
Самосопряженные операторы евклидова пространства
Приведение квадратичной формы к главным осям
Унитарные пространства и их линейные преобразования
Комплексный анализ
Комплексные числа
Комплексные числа в алгебраической форме
Комплексные числа в тригонометрической и показательной формах
Множества на комплексной плоскости
Последовательности и ряды комплексных чисел
Комплексные функции
Функции комплексного переменного. Предел, непрерывность и производная
Элементарные функции комплексного переменного
Дифференцирование функций комплексного переменного
Аналитические функции и их свойства
Конформные отображения
Функциональные ряды в комплексной области
и их свойства Интегрирование функций комплексного переменного
Функциональные ряды и последовательности
Степенные ряды и их свойства
Разложение функций в степенные ряды
Нули аналитических функций
Ряд Лорана и разложение функций по целым степеням
Особые точки, Вычеты
Изолированные особые точки функций и полюсы
Вычеты и их применение
Вычисление интегралов с помощью вычетов
Вычеты и расположение нулей многочлена
Операционное исчисление
Дифференциальные уравнения
ДУ первого порядка
Основные понятия и определения ДУ
Метод изоклин для ДУ 1-го порядка
Метод последовательных приближений
ДУ с разделяющимися переменными
Однородные ДУ
Линейные ДУ 1-го порядка
Дифференциальное уравнение Бернулли
ДУ в полных дифференциалах
Интегрирующий множитель
ДУ, не разрешенные относительно производной
Дифференциальное уравнение Риккати
Составление ДУ семейств линий
Задачи на траектории
Особые решения ДУ
ДУ высших порядков
Понятия и определения ДУ высших порядков
ДУ, допускающие понижение порядка
Линейная независимость функций
Определители Вронского и Грама
Однородные и неоднородные дифференциальные уравнения
Задача Коши и Уравнение Эйлера
Линейные ДУ с переменными коэффициентами
Метод Лагранжа решения ДУ
Краевые задачи для ДУ высших порядков
Разложение решения ДУ в степенной ряд
Разложение решения ДУ в обобщенный степенной ряд
Нахождение периодических решений ДУ
Асимптотическое интегрирование ДУ
Системы ДУ
Системы ДУ: понятия и определения
Сведение системы ДУ к одному уравнению
Нахождение интегрируемых комбинаций
Интегрирование однородных линейных систем ДУ
Методы интегрирования неоднородных систем ДУ
Преобразование Лапласа и решение ДУ и систем
Теория устойчивости
Численные методы
Методы алгебры
Численные методы линейной алгебры
Численные методы решения СЛАУ
Итерационный метод Шульца обратной матрицы
Методы решения задач о собственных значениях и векторах матрицы
Методы решения нелинейных уравнений
Методы решения систем нелинейных уравнений
Методы теории приближений
Методы приближения сеточных функций
Методы функциональной интерполяции
Методы интегрально-дифференциальной интерполяции
Методы интегрального сглаживания
Методы интерполяции и сглаживания сплайнами
Методы численного дифференцирования и интегрирования
Методы численного дифференцирования
Методы численного интегрирования
Методы решения обыкновенных ДУ
Численные методы решения задачи Коши
Разностные схемы для решения задачи Коши
Составные схемы для решения задачи Коши
Экстраполяционные методы решения задачи Коши
Непрерывно-дискретные методы решения задачи Коши
Численные методы решения краевых задач
Методы решения ДУ в частных производных
Численные методы решения уравнений математической физики с двумя переменными
Принципы построения разностных схем для уравнений в частных производных
Разностные схемы решения уравнений в частных производных 1-го порядка
Разностные схемы решения уравнений в частных производных 2-го порядка
Численные методы решения уравнений в частных производных
Численные методы решения уравнений математической физики с тремя переменными
|
Построение минимальных ДНФСДНФ, которая строится по таблице булевой функции, зачастую оказывается весьма сложной, т.е. она содержит достаточно много элементарных конъюнкций и литералов. Необходимо уметь находить в определенном смысле минимальную ДНФ, представляющую исходную функцию. Уточним задачу. Определение 6.5. Булеву функцию Замечание 6.7. Напомним, что функции Если функция Из определения 6.5 и понятия равных булевых функций (см. определение 6.2) следует, что булевы функции Определение 6.6. ДНФ называют минимальной, если она содержит наименьшее число литералов среди всех ДНФ, эквивалентных ей. Обратим внимание на то, что под числом литералов в ДНФ понимают число всех подформул этой ДНФ, которые являются литералами. Так, СДНФ (6.9) содержит 12 литералов (по три литерала в каждой из четырех элементарных конъюнкции). Пример 6.10. ДНФ Вместо четырех литералов в исходной ДНФ получаем ДНФ, состоящую из одного литерала. Определение 6.7. Длиной ДНФ называют число входящих в нее элементарных конъюнкций. ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ. Заметим, что кратчайшая ДНФ не обязана быть в то же время минимальной среди всех ДНФ, эквивалентных исходной функции. Но поиск минимальных ДНФ, как мы сейчас увидим, проводится среди кратчайших ДНФ. Наша задача состоит в том, чтобы описать метод построения минимальной ДНФ, эквивалентной заданной булевой функции. Мы рассмотрим простейший метод такого рода, основанные на алгоритме Квайна — Мак-Клоски. Этот алгоритм исходит обязательно из СДНФ, которая строится по таблице функции так, как это было описано ранее. Алгоритм Квайна–Мак-КлоскиОпишем последовательно этапы, составляющие алгоритм Квайна–Мак-Клоски. 1. Склейка. Пусть Мы получаем элементарную конъюнкцию Операцию получения Установим геометрический смысл простой склейки* (с точки зрения структуры, или "геометрии", булева куба). Из доказательства теоремы о представлении булевой функции в виде ДНФ (см. теорему 6.2) мы знаем, что существует взаимно однозначное соответствие между множеством элементарных конъюнкций СДНФ, представляющей функцию Это значит, что наборы Следовательно, простой склейке, применяемой к элементарным конъюнкциям исходной СДНФ, представляющей функцию С алгебраической же точки зрения мы из двух элементарных конъюнкций Итак, применяя простую склейку к исходной СДНФ Замечание 6.8. Понятие простой импликанты определено через процедуру многократного повторения простой склейки. Иногда простую импликанту булевой функции Можно доказать, что эти два определения простой импликанты равносильны. Геометрия описанного выше многократного повторения простой склейки, как можно показать, состоит в дальнейшем "склеивании" каждой пары соседних ребер {граней размерности 1), на которых значение функции равно 1, в грани размерности 2, соседних граней размерности 2 в грани размерности 3 и т.д. Разбираемый ниже пример поясняет эту идею. Пример 6.11. Зададим функцию (6.11) Подвергнем простой склейке первую и третью, а также вторую и четвертую элементарные конъюнкции в (6.11): (6.12) С геометрической точки зрения склейка первой и третьей конъюнкций в формуле (6.11) означает, что функция Применяя простую склейку к (6.12) (по переменному Пример 6.12. Рассмотрим СДНФ мажоритарной функции (6.9). Имеем следующие склейки: В данном случае сразу получаем сокращенную ДНФ: Карты КарноДля булевых функций от трех и четырех переменных процедура склейки наглядно и просто выполняется на так называемых картах Карио. Форма карт Карно, представляющих собой прямоугольные таблицы, для функции от трех переменных показана на рис. 6.7, а для функции от четырех переменных — на рис. 6.8. На рис. 6.7 строки отмечены наборами значений переменного Карта Карно есть не что иное, как форма таблицы для определения булевой функции. Каждая клетка карты задается своим набором значений переменных, причем в клетках, соответствующих конституентам единицы данной функции, ставится единица, тогда как остальные клетки остаются пустыми. Карта Карно устроена так, что наборы, определяющие любые две соседние клетки, различаются в точности в одной позиции (т.е. различаются значениями ровно одной компоненты), причем клетки (одной и той же строки или одного и того же столбца), примыкающие к противоположным сторонам прямоугольника, также являются соседними в только что определенном смысле. Это можно представить себе так, что карта закручивается" в цилиндр" по обоим направлениям, т.е. в "тор". С геометрической точки зрения карта Карно есть способ изображения булева куба (размерностей 3 и 4). Любая пара соседних клеток (с учетом "закрученности" карты) определяет некоторое ребро булева куба, а любой прямоугольник, состоящий из Можно построить карты Карно и для размерностей 5 и 6, но они используются весьма редко. Может быть построена и простейшая карта Карно для функции от двух переменных, но для таких функций не возникает нетривиальных задач построения минимальной ДНФ. Пусть булева функция С геометрической точки зрения такой прямоугольник площади 2 соответствует ребру булева куба, в каждой вершине которого функция принимает значение 1. Запись прямоугольника в виде слова можно понимать как обозначение соответствующего ребра. Так, на карте, показанной на рис. 6.9, прямоугольник 11× обозначает ребро [110,111], прямоугольники же 1×1 и ×11 — ребра [101,111] и [011,111] соответственно. По таким обозначениям легко получить и ту импликанту, которая является результатом простой склейки: для этого достаточно записать литерал Наличие на карте Карно двух прямоугольников площади 2, находящихся в соседних столбцах или строках, показывает, что функция принимает значение 1 на некоторой паре соседних ребер, т.е. на некоторой грани размерности 2. Тогда они могут быть объединены в один большой прямоугольник площади 4 (рис. 6.10). Этот прямоугольник можно записать в виде слова хОх, показывая тем самым, что соответствующая грань (размерности 2) образована любой из двух пар соседних ребер: (×00, ×01) (два вертикальных прямоугольника площади 2) или (00×, 10×) (два горизонтальных прямоугольника площади 2). Точно так же можно объединять в один прямоугольник площади 8 два соседних прямоугольника площади 4 (рис. 6.11). Если такие большие прямоугольники находить сразу, то "поглощаемые" ими меньшие прямоугольники уже не рассматриваются. Тем самым, находя на карте Карно прямоугольники максимальной площади и не содержащиеся друг в друге, мы находим грани максимальных размерностей и максимальные по включению, такие, на которых заданная функция принимает единичное значение. Поскольку грань размерности Таким образом, если на карте Карно сразу выделять все максимальные (в указанном выше смысле) прямоугольники площади 2. Определение ядра. Говорят, что элементарная конъюнкция Поскольку вторая конъюнкция содержит литерал Каждая входящая в сокращенную ДНФ простая импликанта покрывает некоторую элементарную конъюнкцию исходной С ДНФ. На карте Карно этому отвечает прямоугольник, п закрывающий" соответствующую единицу. Простую импликанту называют ядровой, если она покрывает некоторую элементарную конъюнкцию исходной СДНФ, не покрываемую никакой другой простой импликантой. На карте Карно прямоугольник, соответствующий ядровой импли-канте, отыскивается очень просто: это такой прямоугольник, удалив который получим единицу, не закрытую никаким другим прямоугольником. Тогда ни одна ядровая импликанта не может быть удалена из искомой минимальной ДНФ исходной функции, т.е. все ядровые импликанты обязательно войдут в минимальную ДНФ. Множество всех ядровых импликант (склеек) сокращенной ДНФ называют ядром. Пример 6.13. а. У мажоритарной функции все импликанты являются ядровыми. Напротив, у функции, изображенной на карте Карно на рис. 6.13, ядро пусто, т.е. ядровых импликант нет вовсе. б. На карте Карно на рис. 6.14 в ядро попадают склейки Если все простые импликанты оказались в ядре, то сокращенная ДНФ и есть единственная минимальная и кратчайшая ДНФ для данной функции. Именно так обстоит дело с мажоритарной функцией (см. пример 6.12). В противном случае смотрят, не эквивалентна ли ДНФ, построенная как дизъюнкция всех ядровых импликант, исходной СДНФ. Это будет иметь место тогда и только тогда, когда ядровые импликанты покрывают в совокупности все элементарные конъюнкции исходной СДНФ. На карте Карно тогда каждая клетка, содержащая единицу, должна быть закрыта прямоугольником, отвечающим некоторой ядровой импликанте. Если это так, то ДНФ, построенная по ядру, как описано выше, есть минимальная и кратчайшая (склейки ядра закрыли все единицы карты Карно). При этом импликанты, не попавшие в ядро, все оказываются "избыточными", т.е. их удаление из сокращенной ДНФ не приводит к нарушению эквивалентности этой последней с исходной СДНФ. В остальных случаях переходят к отысканию так называемых тупиковых ДНФ. 3. Перечисление тупиковых ДНФ. Простую импликанту называют избыточной (относительно некоторой ДНФ, содержащей только простые импликанты и эквивалентной исходной СДНФ), если ее можно удалить из этой ДНФ без потери эквивалентности ее исходной СДНФ. Так, сокращенная ДНФ (см. рис. 6.14) содержит избыточные импликанты: импликанта, соответствующая прямоугольнику Тогда можно представить процесс пошагового удаления избыточных импликант, начиная с сокращенной ДНФ, в результате которого получится некоторая ДНФ, уже не содержащая ни одной избыточной склейки. Любую ДНФ, эквивалентную исходной СДНФ, содержащую все ядровые импликанты и не содержащую ни одной избыточной импликанты, называют тупиковой. Заметим, что в силу конечности множества всех импликант тупиковая ДНФ обязательно существует, т.е. в упомянутом выше процессе мы рано или поздно доберемся до такого момента, когда удаление хотя бы одной склейки приведет к тому, что "откроется" какая-то единичная клетка на карте Карно и тем самым будет потеряна эквивалентность полученной таким образом ДНФ исходной СДНФ. Для СДНФ, карта Карно которой приведена на рис. 6.14, имеются две тупиковые ДНФ (первые три конъюнкции соответствуют ядру): В общем случае для перечисления всех тупиковых ДНФ может быть использован следующий алгоритм. Мы изложим его в терминах карт Карно и, допуская вольность речи, будем отождествлять максимальные прямоугольники на карте Карно с соответствующими простыми импликантами. Присвоим каждой простой импликанте сокращенной ДНФ некоторое имя: т.е. обозначим их, например, как Записав все элементарные дизъюнкции, составим из них КНФ. Рассмотрим карту Карно на рис. 6.13. Обозначив (6.13) Тем самым мы образуем вспомогательную функцию (представленную КНФ вида (6.13)), называемую функцией Патрика. Раскрывая скобки в КНФ (6.13) и используя тождества булевой алгебры (в частности, тождество поглощения), получим ДНФ, в которой каждая элементарная конъюнкция соответствует некоторой тупиковой ДНФ и, наоборот, каждой тупиковой ДНФ может быть сопоставлена одна из этих конъюнкций. Для нашего примера поступим так: вычислим конъюнкцию первой и второй скобки в выражении (6.13), а также третьей и четвертой, пятой и шестой скобок, после чего получим (6.14) Используя тождества поглощения, в первой скобке в формуле (6.14) мы можем удалить все члены, содержащие (6.15) Элементарные конъюнкции в (6.15) определяют тупиковые ДНФ. Более того, так как в данном случае отсутствуют ядровые импликанты, найденные конъюнкции исчерпывают тупиковые ДНФ. Первая тупиковая ДНФ состоит из конъюнкций Обоснование описанного выше алгоритма может быть получено из следующих соображений. Функция Патрика, представленная КНФ, принимает значение 1 тогда и только тогда, когда каждая элементарная дизъюнкция принимает значение 1. А элементарная дизъюнкция принимает значение 1 в том и только в том случае, когда хотя бы одно ее переменное принимает значение 1. Согласно определению функции Патрика, это значит, что хотя бы одна простая импликанта выбрана для покрытия соответствующей единицы на карте Карно. Поскольку таким образом перебираются все не покрываемые ядром единицы карты Карно, то гарантируется эквивалентность искомой ДНФ исходной СДНФ. Однако, когда функция Патрика представлена ДНФ и мы выбираем в точности одну из ее элементарных конъюнкций, полагая, что все входящие в нее переменные равны 1, мы тем самым из всех возможных вариантов покрытия каждой единицы на карте Карно выбираем в точности один вариант. Значит, полученная в результате такого выбора ДНФ для исходной (минимизируемой) СДНФ действительно будет тупиковой. Но нужно заметить, что перечисление тупиковых ДНФ является самым неприятным и трудоемким этапом всего алгоритма минимизации. Если число единичных клеток карты Карно, не покрываемых ядром, достаточно велико, то функция Патрика будет весьма сложной и ее упрощение сопоставимо по трудоемкости со всем процессом минимизации. 4. Отыскание среди тупиковых ДНФ кратчайших и минимальных. Среди найденных тупиковых ДНФ находят кратчайшие и минимальные. Можно легко показать, что минимальная ДНФ всегда является кратчайшей, но обратное неверно. Так, Пример 6.14. Рассмотрим карту Карно на рис. 6.15. В результате проведения склейки получим следующую сокращенную ДНФ*: Ядро составляют склейки (простые импликанты) Шесть клеток, содержащих единицу, на карте Карно остаются непокрытыми ядровыми склейками. Для неядровых склеек (обозначенных Преобразуя ее аналогично функции (6.13), получаем Имеем, следовательно, пять тупиковых ДНФ. Запишем их, для наглядности, так: Из этих пяти тупиковых ДНФ кратчайшими являются первая и вторая. Из них, в свою очередь, минимальной является первая, так как она содержит на один литерал меньше. В итоге получаем минимальную ДНФ в виде "Обратим еще раз внимание на то, что каждый выделяемый прямоугольник на карте Карно имеет площадь, равную некоторой степени двойки. Поэтому, например, три соседние единичные клетки не могут быть объединены в один прямоугольник, а их "накроют" два прямоугольника площадью 2, пересекающиеся по одной клетке. В данном случае минимальная ДНФ оказалась единственной, хотя, как это мы видели в ранее разобранных примерах, в общем случае могут существовать несколько минимальных ДНФ. Метод БлейкаТехника карт Карно является удобным и наглядным (при определенных ограничениях на число переменных минимизируемой функции) способом реализации алгоритма Квайна–Мак-Клоски. Но существуют и другие способы проведения склейки, т.е. получения сокращенной ДНФ для исходной функции. Одним из таких способов является чисто алгебраический метод Блейка, состоящий в том, что к любой ДНФ, представляющей функцию, применяются следующие тождества: Первое из тождеств (6.16) называют тождеством (или правилом) обобщенного склеивания, второе — тождеством (или правилом) поглощения. "Технология" использования метода Блейка такова: применяют тождество обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции (вида К1К2). После этого применяют тождество поглощения. Таблицы КвайнаКак только сокращенная ДНФ тем или иным способом найдена, приступают к нахождению ядра. Ядро можно определить (без использования карты Карно) с помощью так называемой таблицы Квайна. Столбцы этой таблицы соответствуют элементарным конъюнкциям исходной СДНФ, а строки — простым импликантам сокращенной ДНФ. На пересечении строки и столбца проставляется знак "+" (плюс), если простая импликанта данной строки покрывает элементарную конъюнкцию данного столбца. Ядро вычисляется так: отмечаем столбцы с единственным знаком "+", тогда простые импликанты тех и только тех строк, в которые попал этот знак, образуют ядро. Для примера 6.13.6 (см. рис. 6.14) получим таблицу Квайна, изображенную на рис. 6.16. (В целях экономии места элементарные конъюнкции в таблице заменены цифровыми обозначениями соответствующих вершин и граней булева куба — точно так же как при обозначении прямоугольников на картах Карно. Ядровые импликанты выделены жирным шрифтом.) По таблице Квайна можно составить и функцию Патрика для перечисления тупиковых ДНФ. Для этого нужно отметить все столбцы таблицы, в которых на пересечении со строками, соответствующими ядровым импликантам, не стоит знак "+". Для разбираемого примера таковым является только последний столбец. Чтобы покрыть соответствующую элементарную конъюнкцию СДНФ, можно выбрать одну из двух простых импликант: Построение минимальных ДНФ частичных булевых функцийВ заключение рассмотрим очень кратко применение карт Карно к построению минимальных ДНФ частичных булевых функций, т.е. частичных отображений из множества Частичная булева функция может быть задана посредством карты Карно, в которой кроме клеток с единицами и пустых клеток будут клетки, заполненные прочерками (–). Такой прочерк означает, что на соответствующем наборе функция не определена. Склейка для частичной функции (заданной картой Карно) проводится таким образом, что выделяются прямоугольники максимальной площади (содержащие Пример 6.15. Пусть частичная функция По поводу рассмотренного примера возникает такой вопрос: почему не принят во внимание другой прямоугольник (площади 2), содержащий клетку с единицей и клетку с прочерком: В примере 6.15 мы доопределяем исходную функцию так, что получается функция Конечно, мы могли бы доопределить функцию Таким образом, в отличие от минимизации булевых функций при минимизации частичных булевых функций не следует выделять все максимальные прямоугольники с прочерками, содержащие данную единичную клетку карты Карно, достаточно выбрать произвольно любой из таких прямоугольников. Но, конечно, не нужно забывать о том, что каждая единица на карте должна быть покрыта некоторой склейкой. Пример 6.16. Для карты на рис. 6.20 следует взять обе склейки на четыре позиции: Заметим, что без использования склеек с прочерками мы вообще не могли бы минимизировать данную функцию. Нужно также отметить, что не всегда использование "частичности" функции позволяет получить минимальную ДНФ для нее. Так, на представленной на рис. 6.20 карте в случае, если мы переместим нижнюю единицу на строку выше, обычная склейка на две позиции дает лучший результат:
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |