Основы Кибернетики, Определения
Материал из eSyr's wiki.
(Различия между версиями)
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1256 участника 92.194.36.166 (обсуждение)) |
||
| Строка 1: | Строка 1: | ||
| - | == | + | == Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи == |
| - | + | ||
| - | + | === Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1: гл.1, §2]) === | |
| - | + | ||
| + | ==== Функция алгебры логики ==== | ||
| + | '''Функция алгебры логики''' — функция, переводящая вектор из n-элементов множества B = {0, 1} в элемент множества B. То есть, для каждого набора нулей и единиц у функции определено значение, равное нулю или единице. | ||
| + | |||
| + | ==== Буква x<sup>σ</sup> ==== | ||
| + | Есть алфавит ''X''(n) = {''x''<sub>1</sub>, … ''x''<sub>n</sub>}. '''Буква ''x''<sub>i</sub><sup>σ</sup>''' есть ''x''<sub>i</sub>, если σ = 1, и ''x̅''<sub>i</sub>, если σ = 0. | ||
| + | |||
| + | ==== Конъюнкция ранга r ==== | ||
| + | '''Конъюнкция ранга r''' ''K'' = ''x''<sub>i<sub>1</sub></sub><sup>σ<sub>1</sub></sup>…''x''<sub>i<sub>r</sub></sub><sup>σ<sub>r</sub></sup>, 0 ≤ r ≤ n; ''K'' = 0 при ''r'' = 0. | ||
| + | |||
| + | ==== Элементарная конъюнкция ==== | ||
| + | '''Элементарная конъюнкция''' — конъюнкция, у которой все переменные в буквах различны: ''x''<sub>i<sub>k</sub></sub><sup>σ<sub>l</sub></sup> ≠ ''x''<sub>i<sub>k</sub></sub><sup>σ<sub>l</sub></sup> при k ≠ l | ||
| + | |||
| + | ==== Импликанта ==== | ||
| + | Элементарная конъюнкция ''К'' называется '''импликантой''' ''f'', если ''K'' ∨ ''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]) === | ||
| + | |||
| + | {{Курс Основы Кибернетики}} | ||
Версия 17:51, 3 февраля 2008
Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи
Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([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 называется простой импликантой, если при вычёркивании любой буквы 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])
