Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Раздел 4. Функции алгебры логики



Тема 4.3. Полнота множества функций. Важнейшие замкнутые классы. Теорема Поста

Задание 9. Исследование множества булевых функций на полноту – 1ч.

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

Задание для самостоятельной внеаудиторной работы:

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

&9.2.Выучите определение функционально полной системы булевых функций. Какие функционально полные системы Вам известны? Сформулируйте критерий Поста. Выясните, как он применяется при исследовании системы булевых функций на полноту. Познакомьтесь с примерами таких исследований.

Основные сведения из теории:

9.3. Закончите определение:

P Основные функционально замкнутые классы булевых функций называются …

P Система булевых функций называется функционально полной, если любую булеву функцию …

P Обобщенной функцией Шеффера называется булева функция n переменных, представляющая собой …

9.4. Закончите утверждение:

P Для того, чтобы система булевых функций была функционально полной, необходимо и достаточно, …

P Если в каждом столбце критериальной таблицы Поста найдется хотя бы один минус, то система булевых функций…

Задачи и упражнения:

Вы, уважаемый студент, знаете, что классы Поста получили свое название в честь американского математика и логика польского происхождения Эмиля ЛеонаПоста (1897-1954). Среди его многочисленных открытий - критерий функциональной полноты системы булевых функций (критерий Поста). Выполняя упражнения задания 9, Вы узнаете ряд фактов из жизни этого великого ученого.

Юный Эмиль был очень одаренным ребенком, успешно изучающим школьные дисциплины. Но одна наука занимала его особенно. Именно с ней Эмиль хотел связать свою жизнь. Вы откроете эту науку, если выполните задание C9.5.

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

. Пост Э.Л.

наука математика физика
функция

 

наука химия астрономия
функция

В Нью-Йорке Эмиль Пост получил элитарное математическое образование. Он закончил учебное заведение, среди выпускников которого числятся одиннадцать обладателей Нобелевской премии. Спустя годы он вернулся в свою alma mater в качестве преподавателя. Вы узнаете это престижное учебное заведение, если выполните задание C9.6.



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

учебное заведение Бруклинский колледж Хантер колледж
функция

 

учебное заведение Городской колледж Нью-Йорка Колледж Манхеттена
функция

Дальнейшее математическое образование Пост получает в стенах Колумбийского университета. Он активно включается в семинар, посвященный изучению фундаментальной работы английских математиков Альфреда Уайтхеда и Бертрана Рассела «Основания математики» (1910-1913). Основной целью этих ученых было перестроение здания математики на базе некоторого набора исходных понятий, сформулированных на языке логики. Все остальное должно выводиться строго в согласии с правилами логических доказательств. Уайтхед и Рассел пытались представить весь набор понятий, аксиом и теорем математики как подмножества соответствующих множеств на языке логики. В дальнейшем были обнаружены погрешности в построениях англичан. Однако, само развитие математики во многом обязано их этапной работе.

В 1918 году Пост получает степень магистра. В своей докторской диссертации он доказывает полноту и непротиворечивость аксиоматики пропозиционального исчисления именно из «Основания математики» по отношению к таблично – истинностному методу. Вы узнаете, в каком году Э.Л. Пост защитил докторскую диссертацию, если выполните задание C9.7.

C9.7. Для систем булевых функций построены критериальные таблицы Поста.Исследуйте данные системы на функциональную полноту:



а)   б)
+ - - + -   - + + - +
+ + - - -     + -   +
- - + - -     -     +

 

в)   г)
+ - - + +   + - + - -
- + - + -   -   -    

 

год защиты диссертации
результаты исследования систем на полноту а) полная; б) неполная; в) неполная; г) полная а) полная; б) неполная; в) полная; г) полная а) полная; б) неполная; в) неполная; г) неполная а) неполная; б) неполная; в) неполная; г) полная

Следующий академический год Э.Л. Пост провел в качестве стипендиата – исследователя в Принстонском университете. Именно в это время он публикует критерий функциональной полноты системы, в настоящее время более известный как критерий Поста. Вы узнаете, в каком году это произошло, если выполните задание C9.8.

C9.8.Исследуйте системы на функциональную полноту:

а) ; б) ; в) .

год публикации критерия Поста
результаты исследования систем на полноту а) неполная; б) полная; в) неполная а) неполная; б) полная; в) полная а) полная; б) полная; в) полная а) неполная; б) неполная; в) полная

Своеобразным стилем научной деятельности Поста были скрупулезность и нежелание выпускать в свет незавершенную работу. Именно это и лишило ученого заслуженного приоритета в одном весьма заметном для развития математики вопросе. Так, еще во время своего пребывания в Принстоне Эмиль Леон Пост вплотную подошел к формулировке, которая лишь в 1931 году была совершенно независимо опубликована другим математиком. Значительно позже в письме к нему Пост заметил, что «независимо от чувства обиды на судьбу, я восхищаюсь Вашей работой, ведь, в конце концов, не идеи, а их реализация дает основание оценить их величие». Вы откроете фамилию этого математика, если выполните задание C9.9.

C9.9. Исследуйте системы на функциональную полноту:

а) ; б) ; в) .

фамилия математика А. Тьюринг Б. Рассел К. Гёдель А. Уайтхед
портрет математика
результаты исследования систем на полноту а) полная; б) неполная; в) неполная а) неполная; б) полная; в) неполная а) полная; б) полная; в) неполная а) полная; б) полная; в) полная

?9.10.Выясните, является ли булева функция из задания C9.6. обобщенной функцией Шеффера.

¶9.11.Задайте аналитически булеву функциютак, чтобы система , где

была:

а) функционально полной; б) функционально неполной.

Методические указания по выполнению работы:

Для успешного решения задач и упражнений рекомендуется детально изучить следующий теоретический материал и рассмотреть примеры:

Классы Поста – это основные функционально замкнутые классы булевых функций .

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

Любая булева функция представима в совершенном нормальном виде (композиции трех булевых функций: конъюнкции, дизъюнкции и отрицания). Следовательно, по определению, система булевых функций является функционально полной.

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

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

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

 
         
         
         

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

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

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

Выясните, является ли данная система функционально полной.

Решение: Система булевых функций является функционально полной, так как в каждом столбце критериальной таблицы Поста присутствует хотя бы один минус (по критерию Поста).

Ответ: - функционально полная система.

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

1) построить критериальную таблицу Поста для системы булевых функций;

2) провести исследование одной булевой функции системы на принадлежность ко всем классам Поста и по его результатам заполнить соответствующую строку критериальной таблицы;

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

4) провести исследование остальных функций системы на принадлежность лишь тем классам, столбцы которых не содержат минусов и не заштрихованы и по их результатам заполнить соответствующие строки критериальной таблицы;

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

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

Пример 2. Докажите, что система булевых функций является функционально полной.

Решение: Для доказательствафункциональной полноты системы воспользуемся алгоритмом.

1) Для удобствавведем следующие обозначения: . Построим критериальную таблицу Поста для системы булевых функций :

 
         
         
         

2) Исследуем на принадлежность ко всем классам Поста. Зададим булевым вектором .

· Его первая координата равна 0, то есть: . Значит, по определению, данная функция принадлежит классу булевых функций, сохраняющих константу 0: (в первой строке первого столбца критериальной таблицы Поста ставим знак «+»).

· Последняя координата булева вектора равна 1, то есть: . Значит, по определению, данная функция принадлежит классу булевых функций, сохраняющих константу 1: (в первой строке второго столбца критериальной таблицы Поста ставим знак «+»).

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

· Так как в булевом векторе после единиц нет нулей, будет монотонной (по достаточному условию монотонности), то есть (в первой строке пятого столбца критериальной таблицы Поста ставим знак «+»).

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

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

 
+ + - - +
         
         

3) Поскольку в третьем и четвертом столбцах таблицы «минусы» уже есть, отметим штриховкой оставшиеся ячейки этих столбцов (для проверки полноты системы исследовать на линейность и самодвойственность оставшиеся булевы функции не нужно).

 
+ + - - +
         
         

4) Исследуем на принадлежность к классам Поста , , M. Зададим булевым вектором .

· Его первая координата равна 0, то есть: . Значит, по определению, данная функция принадлежит классу булевых функций, сохраняющих константу 0: (во второй строке первого столбца критериальной таблицы Поста ставим знак «+»).

· Последняя координата булева вектора равна 1, то есть: . Значит, по определению, данная функция принадлежит классу булевых функций, сохраняющих константу 1: (во второй строке второго столбца критериальной таблицы Поста ставим знак «+»).

· Так как в булевом векторе после единиц нет нулей, будет монотонной (по достаточному условию монотонности), то есть (во второй строке пятого столбца критериальной таблицы Поста ставим знак «+»).

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

 
+ + - - +
+ +     +
         

5) Поскольку минусов не появилось ни в первом, ни во втором, ни в пятом столбцах таблицы, исследуем на принадлежность к соответствующим классам Поста. Зададим булевым вектором .

· Его первая координата равна 1, то есть: , . Значит, данная функция не принадлежит классу булевых функций, сохраняющих константу 0: (в третьей строке первого столбца критериальной таблицы Поста ставим знак «-»).

· Последняя координата булева вектора равна 0, то есть: , . Значит, данная функция не принадлежит классу булевых функций, сохраняющих константу 1: (в третьей строке второго столбца критериальной таблицы Поста ставим знак «-»).

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

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

 
+ + - - +
+ +     +
- -     -

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

Ответ: - функционально полная система.

Пример 3. Исследуйте на полноту систему булевых функций .

Решение: Воспользуемся результатами примера 2. Сохраним введенные обозначения и составим критериальную таблицу Поста для системы булевых функций (удалим третью строку из таблицы Поста для системы ):

 
+ + - - +
+ +     +

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

Ответ: не является функционально полной.

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

Пример 4. Выясните, является ли функция обобщенной функцией Шеффера.

Решение: Исследуем функцию на принадлежность ко всем классам Поста. Для этого зададим ее таблицей значений:

x y z f

· В первой строке последнего столбца этой таблицы находится 1, то есть: , , следовательно, .

· В последней строке последнего столбца этой таблицы находится 0, то есть: , , следовательно, .

· По таблице хорошо видно, что на паре противоположных аргументов - четвертом и пятом значения функции совпадают: . Значит, .

· Достаточное условие монотонности для данной функции не выполняется, так как после единиц в булевом векторе присутствуют нули. Исследуем функцию по определению. Первый ее аргумент (000) сравним с четвертым (011), так как предшествует ему: . А соответствующие значения функции не предшествуют: (000) , так как . Таким образом, .

· Представим булеву функцию многочленом Жегалкина аналитическим способом: = . Найдем степень многочлена Жегалкина для данной функции: . следовательно, .

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

Ответ: - обобщенная функция Шеффера.

Список литературы:

1. Спирина М.С. Дискретная математика: учебник для студ. СПО / М.С. Спирина, П.А. Спирин. - М.: Академия, 2012. – 368 с. (глава 4, п.4.8, стр. 196).

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!