Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Полином Жегалкина. Полная система для его построения
Полином Жегалкина — полином (многочлен) над , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения Исключающее ИЛИ. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики. Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде или в более формализованном виде как Примеры полиномов Жегалкина: Полная система для его построения: По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали: 1. Хотя бы одна функция, не сохраняющая 0. 2. Хотя бы одна функция, не сохраняющая 1. 3. Хотя бы одна нелинейная функция. 4. Хотя бы одна немонотонная функция. 5. Хотя бы одна несамодвойственная функция. Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина. Дополнительно: По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина. Теорема доказывается следующим образом. Заметим, что различных булевых функций от n переменных штук. При этом конъюнкций вида существует ровно 2n, так как из n возможных сомножителей каждый или входит в конъюнкцию, или нет. В полиноме у каждой такой конъюнкции стоит 0 или 1, то есть существует различных полиномов Жегалкина от n переменных. Теперь достаточно лишь доказать, что различные полиномы реализуют различные функции. Предположим противное. Тогда приравняв два различных полинома и перенеся один из них в другую часть равенства, получим полином, тождественно равный нулю и имеющий ненулевые коэффициенты. Тогда рассмотрим слагаемое с единичным коэффициентом наименьшей длины, то есть с наименьшим числом переменных, входящих в него (любой один, если таких несколько). Подставив единицы на места этих переменных, и нули на места остальных, получим, что на этом наборе только одно это слагаемое принимает единичное значение, то есть нулевая функция на одном из наборов принимает значение 1. Противоречие. Значит, каждая булева функция реализуется полиномом Жегалкина единственным образом.
Теорема Поста. Замкнутые классы функций. Примеры. Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество. § Класс конъюнкций K, являющийся замыканием множества . Он представляет собой множество функций вида . § Класс дизъюнкций D, являющийся замыканием множества . Он представляет собой множество функций вида . По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали: 1. Хотя бы одна функция, не сохраняющая 0. 2. Хотя бы одна функция, не сохраняющая 1. 3. Хотя бы одна нелинейная функция. 4. Хотя бы одна немонотонная функция. 5. Хотя бы одна несамодвойственная функция. Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина.
29.Определения теории графов. Смежность. Связность. Виды графов(ор-, псевдо- и т.д.).
Изоморфизм графов. Примеры
|
|||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 548; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.80.24.244 (0.005 с.) |