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

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

Теорема Поста.

Теорема Поста. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ   В Предыдущем Параграфе Были Рассмотрены Некоторые Классы Буле...

 

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

— класс булевых функций, сохраняющих 0;

— класс функций, сохраняющих 1;

— класс линейных функций;

— класс монотонных функций;

— класс самодвойственных функций.

Все перечисленные классы функционально замкнуты.

Теперь докажем критерий полноты.

Теорема 1: (теорема Поста). Для полноты системы функций необходимо и достаточно, чтобы для каждого из классов в системе нашлась функция , ему не принадлежащая.

Доказательство.

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

Докажем достаточность. Сначала, отождествляя переменные, упростим функции из с тем, чтобы они по-прежнему удовлетворяли условиям теоремы Поста. Затем докажем, что суперпозициями из полученных функций можно получить константы, отрицание и конъюнкцию.

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

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

Таким образом, если функция не принадлежит классу , то, отождествляя переменные, получим либо константу 1, либо отрицание. Аналогично, если функция не принадлежит классу , то после отождествления переменных мы получим либо константу 0, либо отрицание. В результате мы получаем обе константы или отрицание (быть может, и то и другое).

Пусть мы получим константы. Можно показать, что отрицание можно представить в виде суперпозиции. Это следует из теоремы 6 предыдущего параграфа.

Если мы получим только отрицание, то, как следует из теоремы 3 §3 суперпозицией из произвольной несамодвойственной функции и отрицания можно получить константы 0 и 1. Таким образом, мы получили функции 0, 1, . Из теоремы 3 и теоремы 4 §3 следует, что суперпозицией из нелинейной функции и отрицания можно получить конъюнкцию. По следствию 1 теоремы 1 §3 следует, что конъюнкция и отрицание образуют полную систему функций.

При проверке, выполняются ли для некоторой системы функций условия теоремы Поста, мы будем составлять таблицы, которые назовем таблицами Поста. Они будут иметь вид:

 

 
         
         
         
         

 

В клетках таблицы Поста ставится плюс или минус, в зависимости от того, входит функция, стоящая в данной строке, в класс, стоящий в данном столбце, или не входит. Для полноты системы функции необходимо и достаточно (в силу теоремы Поста), чтобы в каждом столбце присутствовал хотя бы один минус. Это будет означать, что для каждого из классов в данной системе функций есть функция, не принадлежащая этому классу. Например, таблица Поста для системы функций имеет вид:

 

 
+ + - - +
+ + - - +
- - + + -

 

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

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

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

Определение 2: Собственный функционально замкнутый класс называется предполным, если он не содержится ни в каком функционально замкнутом классе, отличном от самого себя и от класса всех функций алгебры логики.

Следствие (из теоремы Поста):

1. Система функций не полна тогда и только тогда, когда она целиком входит в один из классов .

2. Ни один из классов не содержится в другом.

3. Действительно, если бы какой-либо класс содержался в другом, то в формулировке теоремы Поста этот класс можно было бы отбросить.

Рассмотрим таблицы Поста для следующих систем функций

а) ;

б) ;

в) ;

г) ;

д) .

 

   
а) + + + - + + - - + + - + + + -
б) - + + + + + - - + + - + + + -
в) - - + - -
г) + - + - + - - - - + + + + + -
д) + - + - + + - - - + + - + + +

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

Всякий собственный функционально замкнутый класс содержится в одном из классов.

Действительно, если некоторый функционально замкнутый класс не содержится ни в одном из пяти указанных классов, то для каждого из них в классе найдется функция, ему не принадлежащая. Но тогда по теореме Поста класс содержит все функции алгебры логики.

Теорема 2: Функционально замкнутые классы являются предполными и других предполных классов нет.

Доказательство: Из следствия 3 теоремы Поста следует, что других предполных классов нет, а из следствия 2 следует, что каждый из пяти перечисленных классов является предполным.

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

На самом деле имеет место более точный результат.

Теорема 3: Всякий базис полной системы функций не может содержать более четырех функций.

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

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

 

Замечание об общей теории функционально замкнутых классов.

Общая теория функционально замкнутых классов построена известным американским математиком Э. Постом (результат оформлен в виде монографии в 1941г.). Основным результатом этой работы является построение всех подалгебр (т.е. функционально замкнутых систем) алгебры логики.

Мы выяснили, что вопрос о полноте системы функций алгебры логики приводит к рассмотрению предполных функционально замкнутых классов. Оказывается, что целый ряд вопросов сводится к изучению других функционально замкнутых классов, не обязательно предполных. Можно ожидать, что число различных функционально замкнутых классов бесконечно и даже что их множество имеет мощность континуум. Действительно, классы естественно задавать какими-либо системами функций, их порождающими. Поскольку множество функции алгебры логики счётно, множество различных систем функций имеет мощность континуум. Конечно, различные системы функций часто порождают один и тот же класс. Но нет оснований заранее считать это отождествление настолько сильно, что число различных классов будет конечно или счётно. На самом деле оказывается, что множество классов счётно.

Множество классов удобно представлять в виде дерева, вершины которого соответствуют классам. Если один класс входит в другой, то вершину, соответствующую первому, располагаем под вершиной, соответствующей второму, причем эти вершины соединяются отрезками. Классы допускают естественное расположение по этажам. В основании дерева (в первом этаже) находится класс всех функций алгебры (обозначим его через ). Во втором этаже — предполные классы, в третьем — классы, которые не содержатся ни в одном классе, кроме предполных; вообще в - м этаже – классы, которые не принадлежат предыдущим этажам и не содержатся ни в одном классе, не принадлежащим этим этажам. Число этажей бесконечно. Существенно, что в каждом этаже имеется конечное число классов (и даже ограниченное некоторой константой) и что если класс содержится в некотором классе из - го этажа, то он или сам принадлежит - му этажу или содержится в некотором классе -го этажа. В частности, в каждый класс - го этажа входит лишь конечное число (ограниченное общей константой) классов следующего этажа и что в нем существует конечный базис, причем число элементов в базисах для всех таких классов ограниченно. Не следует думать, что, перебирая таким способом этажи, мы рано или поздно рассмотрим все классы, т.е. что каждый класс принадлежит какому-либо этажу. Однако оказывается, что этим свойством обладают все классы, кроме конечного числа классов, в некотором смысле предельных («классов бесконечного этажа»). Однако мы не приводим здесь описания всех классов.

 

 

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

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

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...

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

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

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

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

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(для студентов специальности «Прикладная математика», «Информатика», «Системный анализ», «Компьютерные системы и сети»)

Прямое произведение множеств. Бинарные отношения.
  Пусть и - произвольные элементы. Из элементов

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

И порядка. Фактор-множество.
  В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар

Булевы алгебры.
  Определение 1: Пусть - отношение порядка на множестве

Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры. Определение 8: Линейно упорядоченное множество, удовлетворяющее условию мини

Мощность множества. Сравнение мощностей.
  Пусть даны конечные множества и , число элементов которых равно

Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).
Два конечных множества будут равномощными, если в них содержится одинаковое число элементов. Если имеем дело с бесконечными множествами, то вопросы, связанные с мощностями, решаются путём установле

Определение 3: Множество, эквивалентное множеству чисел натурального ряда, называется счетным.
Натуральный ряд чисел – это счётное множество. Все множества, равномощные множеству , имеют такую же мощность. Теорема 4:

Трансфинитная индукция.
  Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами

Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.
Подобие для линейно упорядоченных множеств - есть бинарное отношение между линейно упорядоченными множествами, являющееся отношением эквивалентности. Фактор-множество по этому отношению эквивалентн

Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают. 2) Обозначим через множес

Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «и

Формулы алгебры логики. Тавтологии.
  В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм

Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве , называе

Формулы и тавтологии логики предикатов.
  При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1) – индивид

Формальный язык логики высказываний.
  Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она

Предикатов. Свойства теорий первого порядка.
  Для записи формул логики предикатов используется следующий алфавит: скобки, запятые, символы исчисления высказываний (отрицание

Задачи для самостоятельной работы.
1.Определить истинность следующих высказываний, если , ,

Определение формулы и суперпозиции.
  Пусть имеется счетное множество переменных , где

Принцип двойственности.
  Пусть – некоторое подмножество множества булевых функций: .

Линейные функции. Монотонные функции.
  Рассмотрим систему функций: , ,

Задачи для самостоятельной работы.
1) Сколько имеется различных двоичных наборов длины ? 2) Сколько имеется

Правила комбинаторики.
  Начнем с основных принципов комбинаторики, т.е. с правил. Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило слож

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.
Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом. Например, из двух букв и

Определение 8: Конечные упорядоченные множества называются размещениями.
Теорема 3: Количество всех размещений из элементов по элемен

Определение 10: Конечные неупорядоченные множества называются сочетаниями.
Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен. Сочетаний из элементов по

Свойства сочетаний.
  Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след

Комбинаторика с повторениями.
  Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить

Определение 2: Группы, составленные из объектов, которые принадлежат одному из типов элементов, называют сочетаниями с повторениями.
Число всевозможных сочетаний с повторениями обозначают следующим символом: . Сочетания с повторениями, как было показано в примере

Упражнения для самостоятельной работы.
  1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?  

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