Восстановление булевой функции по изображающему числу
Восстановление булевой функции по изображающему числу - раздел Философия, ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ
Рассмотрим Методы, Позволяющие Переходить От Задания Булевой ...
Рассмотрим методы, позволяющие переходить от задания булевой функции в виде изображающего числа к явному выражению ее через элементы.
Дизъюнктивная нормальная форма (ДНФ). Пусть имеется множество, состоящее из n элементов А1 ..., Аn. Произведение вида доставленное из элементов Ai или их отрицаний Aj и содержащее n сомножителей, называется элементарным произведением. Из n элементов можно составить 2n различных элементарных произведений. Изображающее число каждого элементарного произведения имеет только одну единицу в одном из 2n разрядов. Например, выпишем для трех высказываний А, В, С все возможные элементарные произведения и их изображающие числа по отношению к b [А, В, С]:
Совершенная дизъюнктивная нормальная форма (СДНФ) булевой функции — сумма элементарных произведений. Чтобы по данному изображающему числу восстановить булеву функцию в СДНФ, нужно суммировать элементарные произведения, изображающие числа которых имеют единицы в тех же разрядах, что и изображающее число булевой функции. Например, 1001 0110 имеет единицы в разрядах 0, 3, 5, 6, поэтому
Конъюнктивная нормальная форма (КНФ). Элементарными суммами для лnэлементов А1 ..., Аn называются суммы вида составленные из элементов Аi или их отрицаний `Aj и содержание n слагаемых. Из n элементов можно составить 2n элементарных сумм. Изображающие числа элементарных сумм содержат только один 0 в одном из 2n разрядов. Например, для трех высказываний А, В, С имеем
Конъюнктивная нормальная форма булевой функции представляет собой произведение элементарных сумм. Для того чтобы написать булеву функцию, соответствующую данному изображающему числу в КНФ, необходимо перемножить элементарные суммы, изображающие числа которых имеют те же 0, что и изображающее число булевой функции. Например, число 1001 0110 имеет 0 в разрядах 1, 2, 4 и 7, поэтому 1001 0110 =
Представление в форме суммы первых имнликант. Рассмотрим булеву функцию F(A, В, С, ...). Функция f(A, В, С, ...) называется импликантой функции F(A, В, С, ...), если f(А, В, С, ...)®F(A, В, С, ...). Изображающее число #f импликанты функции F имеет нули в тех разрядах, в каких имеет нули изображающее число #F наличие же единицы в разряде изображающего числа #f влечет за собой наличие единицы в аналогичном разряде изображающего числа #F.
Если P1 и Р2 представляют собой какие-либо произведения из элементов А, В, С, ... или из их отрицаний и P1®P2, то Р2 получается из P1 отбрасыванием некоторых сомножителей, например и т. д.
Функция f(A, В, С, ...) называется первой импликантой функции F(A, В, С, ...), если f®F, и не существует такой функции f'(A, В, С, ...), что f’®F и f®f', например
Элементарные произведения отвечающие единицам в разрядах 1, 2, 3 и 5 #F, по определению,— импликанты функции F. Так както, во-первых,— импликанты функции F, во-вторых, так как ни один из элементов А, В,не является импликантой функции F, то, следовательно, — первые импликанты функции F, и, в-третьих, импликанта А×`С — несущественная. Запишем столбцы базиса b [А, В, С], соответствующие единицам в изображающем числе #F в виде двоичных чисел и отметим, как и в базисе b [А, В, С], разряды этих чисел буквами А, В, С в порядке справа налево.
Объединению импликант отвечающих столбцам 1 и 3 в базисе b [А, В, С], можно поставить в соответствие аналогичную операцию на числах 001 и 011, отличающихся только содержимым второго разряда, причем результат объединения, т.е. А×`С, выражается как 0´1, где символ « ´ » во втором разряде указывает на то, что элемент В отсутствует в возникающей импликанте. Аналогично можно объединить (повернутые) столбцы 001 и 101, а также столбцы 010 и 011, в результате получим числа ´ 01 и 01 ´, отвечающие импликантам А В и ВС, соответственно. Число 0´1 выражает тот факт, что среди номеров единичных разрядов изображающего числа #.F=0111 0100 имеются числа 1 и 3 и, кроме того, что изображающее число #А • С=0101 0000 имеет единицы в разрядах 1 и 3. Аналогично, число х01 показывает, что в ФР есть два единичных разряда 1 и 5 и что #А`×B=0100 0100 имеет единицы в разрядах 1 и 5.
Так как в данном процессе попарно объединяться могут колонки, отличающиеся содержимым только одного разряда, то перед началом работы для удобства следует распределить все номера единичных разрядов на группы, объединяя в одну группу числа (номера столбцов), которые, будучи записаны в двоичном коде, имеют одинаковое число единиц. Например, если #.F= 0111 0100, то числа 1, 2 образуют одну группу, числа 3, 5 — другую.
Качественное описание задачи распознавания i
Распознавание образов (объектов, сигналов, ситуаций, явлений или процессов) — едва ли не самая распространенная задача, которую человеку приходится решать практически ежесекундно от первого до посл
Основные задачи построения систем распознавания
Рассмотренный в § 1.1 пример свидетельствует о том, что распознавание сложных объектов и явлений требует создания специальных систем распознавания — сложных динамических систем, сос
Экспертные системы распознавания
Рассмотренная классификация систем распознавания и принципы их функционирования отражают современное состояние вопроса. Все виды систем распознавания базируются на строго формализов
Содержательная трактовка проблемы распознавания
Процесс распознавания состоит в том, что система распознавания на основании сопоставления апостериорной информации относительно каждого поступившего на вход системы объекта или явле
Постановка задачи распознавания
Пусть задано множество объектов или явлений Ω={w1 ..., ..., wz}, а также множество возможных решений L={l1, ..., lk}, которые могут
Метод решения задачи распознавания
Рассмотренная постановка проблемы распознавания позволяет определить последовательность задач, возникающих при разработке системы распознавания, предложить их формулировки и возможн
Системы распознавания без обучения
Построение систем распознавания без обучения возможно при наличии полной первоначальной априорной информации, которая представляет собой совокупность: 1) сведений о том, какова есте
Обучающиеся системы распознавания
Использование методов обучения для построения систем распознавания необходимо в случае, когда отсутствует полная первоначальная априорная информация. Ее объем позволяет подразделить
Самообучающиеся системы распознавания
На практике иногда приходится сталкиваться с необходимостью построения распознающих устройств в условиях, когда провести классификацию объектов либо невозможно, либо по тем или другим соображениям
Критерий Байеса
Критерий Байеса — правило, в соответствии с которым стратегия решений выбирается таким образом, чтобы обеспечить минимум среднего риска. Применение критерия Байеса целесообразно в с
Минимаксный критерий
При построении систем распознавания возможны такие ситуации, когда априорные вероятности появления объектов соответствующих классов неизвестны. Минимизировать значение среднего риск
Критерий Неймана—Пирсона
При построении некоторых систем распознавания могут быть неизвестны не только априорные вероятности появления объектов соответствующих классов, но и платежная матрица (1.7). В подоб
Процедура последовательных решений
Ранее предполагалось, что решение о принадлежности распознаваемого объекта w соответствующему классу Ωi, i=l, ..., m, принимается после измерения всей совокупности
Регуляризация задачи распознавания
В соответствии со стратегией Байеса, если у распознаваемого объекта со измеренное значение признака х = х0 , то
Рабочего словаря признаков
В § 5.1 был рассмотрен один из возможных методов выбора пространства признаков системы распознавания, обеспечивающий в пределах выделенных ресурсов максимальное значение критерия ка
Сравнительная оценка признаков
Выше были рассмотрены достаточно общие методы выбора совокупности признаков, которые целесообразно и доступно использовать при построении системы распознавания. Однако на практике д
Изображающие числа и базис
Булева функция считается заданной, если можно указать значения истинности этой функции при всех возможных комбинациях значений истинности входящих в нее элементов. Таблицу, которая
Зависимость и независимость высказываний
Условия независимости. Поскольку каждая булева функция может иметь два значения истинности, n булевых функций могут образовывать 2n комбинаций значений истинности. По опр
Булевы уравнения
Решение многих задач, связанных с распознаванием объектов, может быть сведено к нахождению решений булевых алгебраических уравнений с одним (или более) неизвестным. Примером булева
Замена переменных
Понятие замены переменных в алгебре логики аналогично понятию замены переменных в обычной алгебре. Если А, В, С, ... — элементарные высказывания и совершается замена переменных, то,
Решение логических задач распознавания
В логических системах распознавания классы и признаки объектов рассматриваются как логические переменные. Чтобы подчеркнуть эту особенность, для обозначения классов и признаков введ
Решение задач распознавания при большом числе элементов
Приложение изложенных в предыдущих параграфах методов построения сокращенного базиса и решения логических задач существенно ограничивается объемом памяти ЭВМ и их быстродействием. Т
Распознавание объектов в условиях их маскировки
Маскировка — один из основных методов снижения эффективности разведки противника в общем комплексе мероприятий по противодействию. Решение проблемы маскировки требует привлечения, с
Распознавание в условиях противодействия
Рассмотрим задачу распознавания объектов в условиях, когда противник может препятствовать как выявлению отдельных признаков объектов, так и сознательно изменять свою тактику в отнош
Алгоритмы распознавания, основанные на вычислении оценок
Логические алгоритмы распознавания, рассмотренные выше, в ряде случаев не позволяют получить однозначное решение о принадлежности распознаваемого объекта к определенному классу. Ю.
Общая характеристика структурных методов распознавания
Во многих случаях апостериорная информация о распознаваемых объектах или явлениях содержится в записях соответствующих сигналов (электрокардиограмм, энцефалограмм, отраженных от цел
Основные элементы аппарата структурных методов распознавания
Говоря о средстве описания объектов в терминах непроизводных элементов и их отношений, употребляют понятие язык. Правила этого языка, определяющие способы построения объекта из непр
Постановка задачи оптимизации процесса распознавания
Прежде всего покажем, что с увеличением числа признаков, используемых при распознавании, вероятность правильного распознавания неизвестных объектов также увеличивается.
Вер
Алгоритм управления процессом распознавания
Рассмотренные понятия позволяют построить алгоритм управления процессом распознавания в виде правила последовательного поиска решений, обеспечивающего разработку оптимального плана
Частные подходы к принятию решений при распознавании
Решение задачи оптимизации распознавания в рассмотренной постановке требует наличия определенных данных. Когда они отсутствуют, приходится пользоваться частными подходами к пр
Алгебраический подход к задаче распознавания
Выше рассмотрены алгоритмы распознавания: детерминированные алгоритмы, основанные на проведении в признаковом пространстве решающей границы (границы, разделяющей классы и представля
Эффективность вероятностных систем распознавания
Чтобы оценить эффективность вероятностных систем распознавания на основе математического моделирования, можно использовать метод статистических испытаний. Для проведения таких испыт
Эффективность логических систем распознавания
При построении логических систем распознавания приходится сталкиваться с ситуацией, когда значения истинности элементов А1..., Аn, выражающих признаки объектов
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
доставленное из элементов Ai или их отрицаний Aj и содержащее n сомножителей, называется элементарным произведением. Из n элементов можно составить 2n различных элементарных произведений. Изображающее число каждого элементарного произведения имеет только одну единицу в одном из 2n разрядов. Например, выпишем для трех высказываний А, В, С все возможные элементарные произведения и их изображающие числа по отношению к b [А, В, С]:
составленные из элементов Аi или их отрицаний `Aj и содержание n слагаемых. Из n элементов можно составить 2n элементарных сумм. Изображающие числа элементарных сумм содержат только один 0 в одном из 2 n разрядов. Например, для трех высказываний А, В, С имеем
и т. д.
отвечающие единицам в разрядах 1, 2, 3 и 5 #F, по определению,— импликанты функции F. Так как
то, во-первых,
— импликанты функции F, во-вторых, так как ни один из элементов А, В,
не является импликантой функции F, то, следовательно, 
— первые импликанты функции F, и, в-третьих, импликанта А×`С — несущественная. Запишем столбцы базиса b [А, В, С], соответствующие единицам в изображающем числе #F в виде двоичных чисел и отметим, как и в базисе b [А, В, С], разряды этих чисел буквами А, В, С в порядке справа налево.
отвечающих столбцам 1 и 3 в базисе b [А, В, С], можно поставить в соответствие аналогичную операцию на числах 001 и 011, отличающихся только содержимым второго разряда, причем результат объединения, т.е. А×`С, выражается как 0´1, где символ « ´ » во втором разряде указывает на то, что элемент В отсутствует в возникающей импликанте. Аналогично можно объединить (повернутые) столбцы 001 и 101, а также столбцы 010 и 011, в результате получим числа ´ 01 и 01 ´, отвечающие импликантам А В и ВС, соответственно. Число 0´1 выражает тот факт, что среди номеров единичных разрядов изображающего числа #.F=0111 0100 имеются числа 1 и 3 и, кроме того, что изображающее число #А • С=0101 0000 имеет единицы в разрядах 1 и 3. Аналогично, число х01 показывает, что в ФР есть два единичных разряда 1 и 5 и что #А`×B=0100 0100 имеет единицы в разрядах 1 и 5.
Новости и инфо для студентов