Основы Кибернетики, Определения
Материал из eSyr's wiki.
(Различия между версиями)
(→Импликанта) |
(→Элементарная конъюнкция) |
||
| Строка 13: | Строка 13: | ||
==== Элементарная конъюнкция ==== | ==== Элементарная конъюнкция ==== | ||
| - | '''Элементарная конъюнкция''' — конъюнкция, у которой все переменные в буквах различны: ''x''<sub>i<sub>k</sub></sub><sup>σ<sub> | + | '''Элементарная конъюнкция''' — конъюнкция, у которой все переменные в буквах различны: ''x''<sub>i<sub>k</sub></sub><sup>σ<sub>k</sub></sup> ≠ ''x''<sub>i<sub>l</sub></sub><sup>σ<sub>l</sub></sup> при k ≠ l |
==== Импликанта ==== | ==== Импликанта ==== | ||
Текущая версия
[править] Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи
[править] Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1: гл.1, §2])
[править] Функция алгебры логики
Функция алгебры логики — функция, переводящая вектор из n-элементов множества B = {0, 1} в элемент множества B. То есть, для каждого набора нулей и единиц у функции определено значение, равное нулю или единице.
[править] Буква xσ
Есть алфавит X(n) = {x1, … xn}. Буква xiσ есть xi, если σ = 1, и x̅i, если σ = 0.
[править] Конъюнкция ранга r
Конъюнкция ранга r K = xi1σ1…xirσr, 0 ≤ r ≤ n; K = 0 при r = 0.
[править] Элементарная конъюнкция
Элементарная конъюнкция — конъюнкция, у которой все переменные в буквах различны: xikσk ≠ xilσl при k ≠ l
[править] Импликанта
Элементарная конъюнкция К называется импликантой f, если K ∨ f = f.
[править] Простая импликанта
Импликанта К функции f называется простой импликантой, если при вычёркивании любой буквы K получается элементарная конъюнкция, которая не является импликантой f.
[править] Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1: гл. 1, §3])
[править] Сокращённая ДНФ
Сокращённая ДНФ — дизъюнкция всех простых импликант f
[править] Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1: гл. 1, §4])
[править] Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю. И. Журавлева о ДНФ сумма минимальных ([1: гл. 1, §5])
[править] Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1: гл. 1, §6])
[править] Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значений для ранга и длины ДНФ ([1: гл. 1, §7])
[править] Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров ([1: гл. 1, §§2, 3, 7])
[править] Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1: гл. 1, §8])
