Основы Кибернетики, Определения

Материал из eSyr's wiki.

Содержание 1 Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи 1.1 Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1: гл.1, §2]) 1.1.1 Функция алгебры логики 1.1.2 Буква xσ 1.1.3 Конъюнкция ранга r 1.1.4 Элементарная конъюнкция 1.1.5 Импликанта 1.1.6 Простая импликанта 1.2 Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1: гл. 1, §3]) 1.2.1 Сокращённая ДНФ 1.3 Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1: гл. 1, §4]) 1.4 Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю. И. Журавлева о ДНФ сумма минимальных ([1: гл. 1, §5]) 1.5 Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1: гл. 1, §6]) 1.6 Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значений для ранга и длины ДНФ ([1: гл. 1, §7]) 1.7 Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров ([1: гл. 1, §§2, 3, 7]) 1.8 Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1: гл. 1, §8])

[править] Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи

[править] Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1: гл.1, §2])

[править] Функция алгебры логики

Функция алгебры логики — функция, переводящая вектор из n-элементов множества B = {0, 1} в элемент множества B. То есть, для каждого набора нулей и единиц у функции определено значение, равное нулю или единице.

[править] Буква x^σ

Есть алфавит X(n) = {x₁, … x_n}. Буква x_i^σ есть x_i, если σ = 1, и x̅_i, если σ = 0.

[править] Конъюнкция ранга r

Конъюнкция ранга r K = x_i1^σ₁…x_ir^σ_r, 0 ≤ r ≤ n; K = 0 при r = 0.

[править] Элементарная конъюнкция

Элементарная конъюнкция — конъюнкция, у которой все переменные в буквах различны: x_ik^σ_k ≠ x_il^σ_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])