Минимизация контактных схем, реализующих булевы функции
Введение
Теория булевых функций составляет фундамент современной дискретной математики. Булевы функции являют собой самые простые объекты дискретной природы. Язык булевых функций хорошо приспособлен для описания разбиения целого на части и взаимодействия этих частей. Поэтому он широко используется в самых разнообразных областях человеческого знания: будь то собственно математика (теория множеств и математическая логика, алгебра, теория графов и комбинаторика, теория информации, теория кодирования, теория формальных языков и языков программирования, распознавание образов и т. д.), техника (анализ и построение различных устройств коммутации, управления и переработки информации, включая современные ЭВМ), экономика и математическая биология. Список областей, где могут применяться и с успехом применяются результаты и методы теории булевых функций, нетрудно продолжить и далее.
Введение
1 Описание релейно-контактной схемы
2 Реализация булевых функций релейно-контактными схемами.
3 Понятие контактной схемы
4 Алгоритмы реализация булевых функций с помощью контактных схем.
5 Решение логических задач с помощью контактных схем.
6 Проблема минимизации контактных схем
7 Функция Шеннона и ее асимптотическое поведение.
Заключение
Список литературы
1. Яблонский С. В. Введение в дискретную математику. — М.: Наука. — 1986
2. Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит. — 2000
3. Супрун В.П. Основы теории булевых функций. — М.: Ленанд / URSS. — 2017
4. Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука. – 1972
Каждой контактной схеме можно сопоставить логическую (булеву) функцию, принимающую значение 1 для тех и только тех наборов значений переменных, приписанных двухполюсникам, которым соответствует проводимость в схеме (есть ток от "входа" к "выходу"). Эта функция называется функцией проводимости схемы. В качестве функции проводимости можно взять дизъюнкцию всех конъюнкций, соответствующих всем "существенным" цепям, т.е. таким цепям, соединяющим "вход" и "выход", которые ни через какую вершину не проходят дважды.С другой стороны, для каждой формулы алгебры высказываний, используя равносильную ей ДНФ (или КНФ) можно построить указанным образом контактную схему, функция проводимости которой равносильна данной формуле. Говорят тогда, что данная контактная схема реализует эту формулу.Схема называется минимальной, если она содержит минимальное число контактов среди всех схем, имеющих ту же функцию проводимости. В частности, минимальной ДНФ соответствует минимальная контактная схема среди всех схем, являющихся параллельным соединением последовательных цепочек.