рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Замкнутые классы булевых функций

Замкнутые классы булевых функций - раздел Математика, ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ Выше Показано, Что Любая Функция Может Быть Выражена В Виде Днф, Те. Формулой...

Выше показано, что любая функция может быть выражена в виде ДНФ, те. формулой, использующей функциональные знаки &,v,-> и

символы переменных Еще один интересный пример дает система функций

(1)

Выше показано, что. Используя это равенство и закон

де Моргана (свойство 11), выразим дизъюнкциючерез функции

системы (1).

i

Поэтому в любой ДНФ можно выразить дизъюнкцию и отрицание через функции системы (1). Примеры:

1) = [заменяем знак отрицания] =-[заменяем знак дизъюнкции] == [раскрываем скобки] =

2)= [заменяем знак дизъюнкции] =

3)

То же преобразование можно выполнить проще, заменяя сначала знак дизъюнкции

. Первое слагаемое равно 0, так как

содержит произведение , и его можно из формулы удалить

Оставшуюся часть преобразуем, заменяя знак отрицания

Как видно из рассмотренных примеров, если в формуле после произведенных замен раскрыть скобки и выполнить умножения и

сложения, а также поглощение по правилам эквивалентных преобразований, то получится формула, представляющая сумму по модулю 2 некоторых конъюнкций переменных (в каждой конъюнкции переменные не повторяются, но, в отличие от элементарных конъюнкций без отрицаний) и, быть может, константы 1

Полученная формула, порожденная логическими константами 0 и

1 и функцияминазывается многочленом Жегалкина

Можно показать, что различные (с точностью до перестановки слагаемых в сумме и сомножителей в конъюнкциях) многочлены представляют различные функции, т е. имеет место единственность представления булевой функции многочленом Жегалкина

В самом деле, пусть два многочлена и

равны как функции, т е на одинаковых наборах принимают одинаковые значения Тогда для какого-нибудь существенного переменного (пусть это), вынеся за скобки из

всех содержащих его членов, Р и Q можно представить в виде

где- многочлены, зависящие от переменных

Достаточно показать, что как многочлены Легко

проверить, что для п = 1 утверждение о единственности многочлена верно: все функции одной переменной - в табл 5. Тем самым выполнено базовое условие для применения метода математической индукции по числу переменных п . Выполним индукционный шаг: предположим, что

утверждение справедливо для функций (л —1) переменных и докажем его для п . Поскольку Р и Q тождественно равны, то при они

также равны Но при этом )

Значит, совпадают как многочлены, по предположению

индукции, и, прибавивк обеим частям (*) и, соответственно, к (**), получим

Левые части этих равенств равны, следовательно, равны и правые,

в том числе, при X = , откуда равны как функции. Тогда, по

предположению индукции, они совпадают и как многочлены, что завершает доказательство

Возникает вопрос' как определить для системы функций, можно ли с ее помощью выразить любую логическую функцию. В связи с этим рассмотрим несколько понятий

Замыкание системы булевых функцийD - класс всех суперпозиций функций системы D .

Примеры:1) Если система D - множество из двух функций: конъюнкции и дизъюнкции, то ее замыкание - всевозможные ДНФ такие, что входящие в них элементарные конъюнкции не содержат

*»••

отрицаний переменных (например, ). Любую

другую суперпозицию конъюнкции и дизъюнкции можно привести к такому виду: во всякой формуле, представляю'щей собой конъюнкцию дизъюнкций можно раскрыть скобки и преобразовать ее в дизъюнкцию конъюнкций. Так,

2) Если система D состоит из одной функции то ее

замыкание - всевозможные суммы различных переменных.

Замкнутый класс булевых функций- множество функций К ,

любая суперпозиция которых принадлежит К , т.е. замкнутый класс представляет собой множество булевых функций, замкнутое относительно операции суперпозиции.1,

Примеры.1) Замыкание любой системы функций - замкнутый класс.

2) 4 функции одной переменной - замкнутый класс.

3) 2 функцииобразуют замкнутый класс.

4) Множество сумм по модулю 2 нечетного числа переменных является замкнутым классом, поскольку подстановка в такую функцию вместо переменной функции этого класса увеличивает число вхождений переменных в формулу на четное число; при этом некоторые слагаемые

могут взаимно сократиться ввиду эквивалентности , и число

переменных остается нечетным, поскольку при сокращениях в формуле переменные устраняются парами.

Упражнение.Показать, что указанные в последнем примере функции образуют замыкание системы, состоящей иэ одной функции

трех переменных

Упражнение.Проверить, является ли замкнутым класс,

содержащий все дизъюнкции переменных, состоящие из нечетного числа членов (т.е и т.д.).

Функционально полная система функций - система, замыкание которой составляет - множество всех логических функций.

Как показано выше, системы функций и

полны.

Можно обобщить построения, примененные при рассмотрении полноты систем многочленов Жегалкина, и сформулировать следующее утверждение.

Пусть система- полная и пусть каждая из функций

может быть выражена суперпозицией через функции

Тогда система тоже полная, потому что в формуле,

составленной из функциональных знаков системы, можно

заменить каждое вхождение символа функциина ее выражение через

символы функций

Вот несколько примеров.

(1) Системаполна, так как (закон деМоргана).

(2) Аналогично показывается полнота системы

(3) Системаполна, поскольку

– Конец работы –

Эта тема принадлежит разделу:

ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

На сайте allrefs.net читайте: "ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ"

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Замкнутые классы булевых функций

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Элементамимножества: записьобозначает принадлежность
элемента а множеству А , записьобозначает, что элемент b не принадлежит А . Множество

Порождающей процедуры
Простейший пример - задание последовательности элементов множества формулой, содержащей параметр: Задавая раз

Суперпозиция функций
Соответствием G между множествами А и В называется подмножество. Если

Бинарные отношения
Начнем с примеров. Натуральные числа могут быть полными квадратами, как 4, 81, 144, или не быть ими, как 5, 30, 48. Это свойство, или признак числа можно трактовать как принадлежн

Отношения порядка
Важный тип бинарных отношений - отношения порядка. Отношение строгого порядка -бинарное отношение, являющееся антирефлексивным, антисимметричным и транзитивным: обозначени

Свойства бинарных операций
Ассоциативной бинарной операциейназывается операция, если она обладает свойством . Ассоциативность ' п

Алгебры
Алгебра - не только математическая дисциплина. Тот же термин обозначает вполне определенную структуру. Алгебройназывается множество М вместе с заданной на нем систе

Представления логических функций
В базовом курсе содержались элементы математической логики-истинные и ложные высказывания и операции над ними. Теперь рассмотрим те же и другие понятия и соотношения, используя - функциона

Булева функция (логическая функция, функция алгебры
^логики)- это функция одной или нескольких переменных I, где

Логические формулы. Булева алгебра
"Задание функций непосредственно таблицей удобно лишь при небольшом числе переменных. Другим средством представления функций является суперпозиция, символическим (аналитическим) выражением кот

Дизъюнктивные нормальные формы
I Важным примером эквивалентности является разложение булевой функции по переменной- представление функции

I §2. Предполные классы
Здесь мы рассмотрим 5 замкнутых классов, играющих особую роль в вопросе о функциональной полноте Они называются предполными. причина будет выявлена ниже. 1) Класс

Критерий полноты системы булевых функций (теорема
Поста)- системаполна в том и только в том случае, если для каждого рзклассов

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги