Основы Кибернетики, Определения
Материал из eSyr's wiki.
(Различия между версиями)
(Отмена правки № 1256 участника 92.194.36.166 (обсуждение)) |
(→Импликанта) |
||
| Строка 16: | Строка 16: | ||
==== Импликанта ==== | ==== Импликанта ==== | ||
| - | Элементарная конъюнкция ''К'' называется '''импликантой''' ''f'', если ''K'' ∨ ''f''. | + | Элементарная конъюнкция ''К'' называется '''импликантой''' ''f'', если ''K'' ∨ ''f'' = ''f''. |
==== Простая импликанта ==== | ==== Простая импликанта ==== | ||
Версия 11:28, 11 апреля 2009
Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи
Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([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σl ≠ xikσ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])
