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

Материал из 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σlxikσl при k ≠ l

Импликанта

Элементарная конъюнкция К называется импликантой f, если Kf.

Простая импликанта

Импликанта К функции 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!) | Алгоритмы решения задач | Теормин | Определения

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