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

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

Перейти к: навигация, поиск

Содержание

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

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

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

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

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

Есть алфавит X(n) = {x1, … xn}. Буква xiσ есть xi, если σ = 1, и i, если σ = 0.

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

Конъюнкция ранга r K = xi1σ1xirσr, 0 ≤ r ≤ n; K = 0 при r = 0.

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

Элементарная конъюнкция — конъюнкция, у которой все переменные в буквах различны: xikσkxilσl при k ≠ l

[править] Импликанта

Элементарная конъюнкция К называется импликантой f, если Kf = 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])


Основы Кибернетики


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

пт пт пт пт пт
Февраль
09 16 26
Март
02 09 16 23 30
Апрель
06 13 20 27
Май
04 11 18 25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Личные инструменты
Разделы