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

Дисциплины:

Архитектура (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. Полнота множества функций



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

Задание 7. Проверка булевой функции на принадлежность к классам , , L – 1ч.

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

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

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

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

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

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

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

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

P Булева функция n переменных называется сохраняющей константу 0, если на аргументе, …

P Булева функция n переменных называется сохраняющей константу 1, если на аргументе, …

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

7.5. Заполните пропуски:

P Если первая координата булева вектора равна 1, то булева функция …сохраняющей константу 0

P Если в последнем столбце и последней строке таблицы значений булевой функции 1, то эта функция …константу…

P Если булева функция представлена многочленом Жегалкина, степень которого больше…, то булева функция линейной не является.

7.6. В выражении f ◊ ê замените символы ◊ ê так, чтобы оно обозначало:

· f – булева функция, сохраняющая константу 0;

· f – булева функция, не сохраняющая константу 1;

· f – линейная булева функция.

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

?7.7.Исследуйте функцию на принадлежность к классу булевых функций, сохраняющих константу 0. Результат оформите символически:

а)

x y f

б) ; в) ; г) ;



д) .

?7.8.Исследуйте функцию на принадлежность к классу булевых функций, сохраняющих константу 1. Результат оформите символически:

а)

x y z f

б) ; в) ; г) ;

д) .

¶7.9. Выясните, сколько булевых функций двух переменных:

а) сохраняют константу 0, но не сохраняют константу 1;

б) не сохраняют константу 0 и не сохраняют константу 1.

?7.10. Исследуйте функцию на принадлежность к классу линейных булевых функций. Результат оформите символически:

а) ; б) ; в) ;

г) ; д) ; ¶е) .

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

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

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

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

Булева функция n переменных называется сохраняющей константу 0, если на аргументе, состоящем из одних нулей (нулевом), она принимает значение, равное нулю. Класс подобных булевых функций обозначается символом . Таким образом, если , то .

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

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



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

Пример 1: Исследуйте функцию

x y f

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

Решение: Булева функция задана таблицей значений. В первой строке последнего столбца этой таблицы находится 1, то есть: , . Значит, по определению, данная функция не принадлежит классу булевых функций, сохраняющих константу 0: .

Ответ: .

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

Решение: Найдем значение булевой функции , заданной аналитически, на нулевом аргументе:

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

Ответ: .

Булева функция n переменных называется сохраняющей константу 1, если на аргументе, состоящем из одних единиц (единичном), она принимает значение, равное единице. Класс подобных булевых функций обозначается символом . Таким образом, если , то .

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

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

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

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

Решение: Булева функция трех переменных задана булевым вектором. Его последняя координата равна 1, то есть: . Значит, по определению, данная функция принадлежит классу булевых функций, сохраняющих константу 1: .

Ответ: .

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

Решение: Найдем значение булевой функции , заданной аналитически, на единичном аргументе:

. Таким образом,

, , следовательно, по определению, булева функция

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

Ответ: .

Булева функция n переменных называется линейной, если она представима многочленом Жегалкина степени не выше первой. Класс подобных булевых функций обозначается символом L. Таким образом, если , то .

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

Пример 5. Исследуйте функцию на принадлежность к классу линейных булевых функций. Результат оформите символически.

Решение: Представим булеву функцию многочленом Жегалкина аналитическим способом.

. Таким образом, . Подробный процесс аналитического способа представления булевой функции многочленом Жегалкина с указанием всех используемых свойств булевых функций был показан в примерах 2, 4 задания 6 самостоятельной внеаудиторной работы.

Найдем степень многочлена Жегалкина для данной функции. Наибольшую степень, равную 2, имеет конъюнктивный одночлен . Значит, степень многочлена Жегалкина равна 2: . следовательно, по определению, данная функция

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

Ответ: .

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

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

 


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

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