20.Постановка задачи минимизации в классе днф

Задачей минимизации при точном ее решении является отыскание для функции F(X) минимальной или кратчайшей ДНФ. При ее приближенном решении целью минимизации ставят, как правило, отыскание некоторой безызбыточной ДНФ, “достаточно близкой” к минимальной или кратчайшей. Из приведенного выше рассмотрения следует, что минимизация может быть проведена в два этапа. На первом этапе для функции F(X) строится ее сокращенная ДНФ, а на втором этапе, выбрасывая из сокращенной ДНФ избыточные максимальные интервалы, можно получить МДНФ или КДНФ. Причем, на первом этапе задача решается однозначно и сложность заключается лишь в большом числе максимальных интервалов (простых импликант) произвольной функции F(X).

21. формулы де Моргана в алгебре Буля. ху=ху ; ху=ху

22. Таблица истинности функций шеффера и вебба

Функция Шеффера - сложное высказывание, которое ложно а случае истинности составляющих высказываний и истинно во всех остальных случаях. 00-1;01-1;10-1;11-0. Функция Вебба (или-не) 00-1;01-0;10-0; 11-0.

23. свойство транзитивности отношений m_im_jm_k (m_iRm_j)(m_jRm_k) m_i R m_k

24,125. пересечение отношений. Пересечением 2-х совместимых по типу отношений А и В называется отношения состоящие из мн-ва, принадлежащих одновременно обоим отношениям А и В.

28. эквивалентные мн-ва и мощность мн-ва. Мощность множества – обобщащее понятие, кол-во элементов конечного мн-ва. А эквивалентно В (А~B) – если каждому элементу множества А можно по некоторым правилам поставить в соответствие один и только один эл-нт мн-ва В, и наоборот. Говорят что между эл-ми мн-в А и В установлено взаимоодназначное соответствие. Два конечных множества эквивалентны тогда и только тогда, когда в них одинаковое количество элементов

29.Геометрическое представление фал

ФАЛ имеют и геометрическое представление, так функция 2-х переменных рассматривают как плоскость, заданную в системе координат х1х2.. Отложим по каждой оси единичные отрезки   х1 и х2. Получим квадрат, вершины которого – комбинации переменных.

Две вершины, принадлежащие одному ребру “склеиваются” по переменной меняющейся вдоль ребра.

Для функции 3-х переменных геометрическое представление выполняются в виде куба, вершины которого обозначены десятичными цифрами, двоичными цифрами и произвольными переменными хi. Рёбра куба поглощают вершины. Грани куба поглощают свои рёбра и, следовательно, вершины.

30. способы задания множеств. 1) перечислением- пр перечислении множеств его эл-ты принято заключать в фигурные скобки. 2) аналетический. описание св-тв – для задание некоторого множества Х, состоящего из эл-ов, обладающих св-ом А, используют запись Х={х|А(х)} читается « Х множество элементов х таких, что А(х).

32. неполностью определенные ФАЛ. Подмножество FM_yM_x называется функцией, если для каждого элемента х, х M_x найдется не более одного элемента у M_y вида (х,у)F, при этом ф-ия называется всюду( полностью определенной) , в протвном случае – частично определенной. реально на практике функции либо не определены полностью, либо есть запрещенные комбинации.

33,119. способы задания отношений. 1) для дискретного конечного мн-ва достаточно перечисление всех отношений во всех парах. 2) матричный ( матрица размерностью NN, где N- мощность мн-ва) a_ij={0-если xRy, 1 –если xнеRy}. 3)графический. Отношение представленны в виже дуг. Наилудшая альтернатива которая находится в отношении R со свеми остальными. 4) с помощью сечений. Верхнее сечение – перечень всех альтернатив находящихся с данной в отношении R, т.е лучшее. Нижнее – перечень всех альтернатив, которые хуже.