Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Арифметическое разложение булевых функций ⇐ ПредыдущаяСтр 6 из 6
Если в некотором выражении булевой функции F заменить логические операции арифметическими на множестве вещественных чисел {0, 1} по следующим правилам:
, (7)
, (8)
, (9)
, если , (10)
, (11)
, если , (12)
, (13) , (14)
, (15)
то полученное в результате такой замены, раскрытия скобок и приведения подобных, выражение называется арифметическим разложением (или арифметическим полиномом) булевой функции и обозначается черев G(F) .
Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) арифметический полином G(F) имеет вид: .
Отметим некоторые свойства арифметического полинома G(F) булевой функции n переменных .
1. Полином G(F) является для функции F единственным. 2. Полином G(F) имеет степень n, если вектор w(F) содержит нечетное число единиц. 3. Сумма коэффициентов полинома G(F) равна значению булевой функции F на наборе переменных (1,1,…,1) в таблице истинности. Некоторые из методов разложения булевых функций F в канонический полином Жегалкина после соответствующей модификации могут быть применимы для разложения F в полином G(F). К таким методам относятся, в частности, рассмотренный выше метод преобразования СДНФ.
При использовании метода преобразования СДНФ необходимо в СДНФ функции F заменить логическую операцию «дизъюнкция» на операцию "арифметическое сложение", поскольку из (12) следует, что , если . Затем в полученном выражении необходимо избавиться от отрицания переменных по (7). После раскрытия скобок и приведения подобных получается искомый полином.
Пример. Составить арифметический полином G(F) СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: .
Решение. Заменим операцию дизъюнкции на операцию "арифметическое сложение" по формуле (10). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю: . Все переменные с отрицанием заменяем по формуле (7), затем раскрываем скобки и в полученном выражении приводим подобные:
Ответ:G(F)
Пример. Составить арифметический полином G(F) СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: .
Решение.
. Ответ: G(F) . ЛИТЕРАТУРА 1 Горбатов,В.А. Дискретная математика / В.А.Горбатов, А.В.Горбатов, М.В.Горбатова. – М.: АСТ Астрель, 2006. 2 Горбатов, В.А. Основы дискретной математики / В.А.Горбатов. – М.: Высшая школа, 1986. 3 Новиков, Ф.А. Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2007. 4 Плотников, А.Д. Дискретная математика: учебное пособие / А.Д.Плотников. – М.: Новое знание, 2006. 5 Супрун, В.П. Методические указания к семинарским занятиям по специальным курсам «Теория булевых функций» и «Теория автоматов» «Полиномиальное разложение булевых функций» / В.П.Супрун. – Мн.: БГУ, 1991. 6 Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий / С.Д.Шапорев. – СПб.: БХВ-Петербург, 2007. 7 Яблонский, С.В. Введение в дискретную математику / С.В.Яблонский. – М.: Наука,1988.
СОДЕРЖАНИЕ Булевы переменные и функции ……………………..…………………..………...….3 Элементарные булевы функции. Равносильности………………………………...…4 Дизъюнктивные нормальные формы ...…………..….………………….………........7 Минимизация ДНФ …………….……………………..………………….……….….10 Конъюнктивные нормальные формы …………….…..…………….…......….…..…13 Минимизация КНФ …………….……………………..………………….……….….16 Полиномиальное разложение булевых функций…..….………………………........19 Разложение булевых функций в канонический полином Жегалкина ......….…..…21 Арифметическое разложение булевых функций........................................................23 Литература……………….…..…….…………………..……………...….…….......….24
|
||
Последнее изменение этой страницы: 2018-04-12; просмотров: 184. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |