Таблица классов поста
Таблица классов постаСкачать файл - Таблица классов поста
Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:. Класс функций сохраняющих ноль. Класс функций сохраняющих единицу. Количество линейных функций от переменных равно. Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса. Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор не мог бы быть полным. Докажем, что если набор не содержится полностью ни в одном из данных классов, то он является полным. По определению, найдется такой вектор , что. Рассмотрим , где либо , при. Таким образом мы получили одну из констант. Существуют такие , что , , зафиксируем все , тогда. В итоге имеем три функции: Среди нелинейных членов ее представления в виде полинома Жегалкина , выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем и. Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде , где в квадратных скобках указаны члены, которые могут и не присутствовать остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов. В итоге получим функцию , а также либо функцию , либо функцию. Поскольку функцию можно выразить через и , а функцию через и , то мы получили базис , ,. Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ , то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде. Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов , , , ,. В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса. Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм , вторая — для представления в виде полиномов Жегалкина. Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы. Теорема о максимальном числе функций в базисе: Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему можно назвать базисом класса линейных функций. Набор булевых функций является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. Дискретная математика и алгоритмы Булевы функции. Пространства имён Статья Обсуждение. Просмотры Чтение Правка История. Навигация Заглавная страница Сообщество Текущие события Свежие правки Случайная статья Справка. Инструменты Ссылки сюда Связанные правки Спецстраницы Версия для печати Постоянная ссылка. Последнее изменение этой страницы: Политика конфиденциальности Описание Викиконспекты Отказ от ответственности. Содержание 1 Полные системы функций 2 Замкнутые классы булевых функций 3 Формулировка и доказательство критерия Поста 3. Если любая булева функция , являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым англ. Множество булевых функций называется полной системой англ. Полная система функций называется безызбыточной англ. Говорят, что функция сохраняет ноль , если. Говорят, что функция сохраняет один , если. Говорят, что функция самодвойственна англ. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения. Говорят, что функция монотонна англ. Говорят, что функция линейна англ. Рассмотрим функцию, не сохраняющую ноль — то есть функцию, для которой. Тогда может принимать два значения: Рассмотрим функцию, не сохраняющую один — то есть функцию, для которой. Таким образом, возможны четыре варианта: Мы получили и имеем константу, равную , поскольку. Возьмем отрицание от и член исчезнет. Присутствуют три члена, без: Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции. Присутствуют два члена, без. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции будет состоять только из одного члена. Если это так, то не составляет труда выразить через и. Например, если функция принимает истинное значение, когда аргументы c номерами ложны, а все остальные истины, то функцию можно выразить как , где ставится перед аргументами с номерами. Выразим через и аналогично пункту 3. Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.
Полные системы функций и теорема Поста
В каком веке социология оформилась как наука
Полные системы функций. Теорема Поста о полной системе функций
Сделать массажный стол своими руками
T killah feat роман bestseller вася текст
Диагностика пограничных психических расстройств
Булевы функции
Контрольная по всеобщей истории 6 класс
Приказ минздрава 254н от 21.04 2016
1 понятие гражданского правоотношения