математика. урок (2). Конспект в тетради и прикрепить к платформе классы булевых функций
 Скачать 49.47 Kb.
|
|
ЗАДАНИЕ СДЕЛАТЬ КОНСПЕКТ В ТЕТРАДИ И ПРИКРЕПИТЬ К ПЛАТФОРМЕ Классы булевых функций. Общее число булевых функций равно Р2(n) =  . Из множества этих функций выделяют некоторые классы функций.Пусть имеется булева функция f(x1, x2,…,xn), зависящая от n переменных. Пусть переменным этой функции присвоены значения: x1 = 1, x2= ,…, xn = n, где j {0, 1}, (j=1,2,…,n). Тогда f(1, 2,…, n) – значение функции f при заданных значениях аргументов. 1. Булева функция f сохраняет константу 0, если f(0,0,…,0) = 0. К0 -множество всех булевых функций, сохраняющих константу 0. Булева функция принадлежит классу К0, если на наборе (0,0,…,0) она принимает значение 0. На остальных наборах значение функции произвольно.
2. Булева функция f сохраняет константу 1, если f(1,1,…,1) = 1. К1 - множество всех булевых функций, сохраняющих константу 1. Булева функция принадлежит классу К1, если на наборе (1,1,…,1) она принимает значение 1. На остальных наборах значение функции произвольно.
Функции, не сохраняющие 0 и 1 Функция называется «не сохраняющей 0», если при подстановке нулевых значений аргументов ее значение равно 1. Функция называется «не сохраняющей 1», если при подстановке единичных значений аргументов ее значение равно 0. Пример:  При x= 0 f= 1, при x= 1 f= 0, следовательно, эта функция не сохраняет 0 и не сохраняет 1. Пример: f=x. При x= 0 f= 0, при x= 1 f= 1, следовательно, эта функция сохраняет 0 и сохраняет 1. 3. Функция  называется двойственной к функции  , если  Двойственными являются: 1 и 0, х и  , и \/, ху и у хНапример,  . Булева функция называется самодвойственной, если она равна двойственной себе функции.  Класс самодвойственных функций обозначается S Для самодвойственной функции можно записать f(a,b,c) =  . – самодвойственная функция; – самодвойственная функция.Определить самодвойственность можно по таблице истинности
Чтобы найти противоположные наборы, нужно мысленно разделить таблицу истинности пополам, сравнить крайние и средние наборы. Функция на противоположных наборах должна принимает противоположные значения: - на противоположных наборах (0,0) и (1,1) функция принимает противоположные значения 0 и 1. - на противоположных наборах (0,1) и (1,0) функция принимает противоположные значения 0 и 1. 4. Булева функция называется линейной, если ее можно представить в виде полинома Жегалкина:   ,  – линейная функция.Множество всех линейных булевых функций обозначается L.  – нелинейная функция, так как есть произведение переменных.5. Булева функция называется монотонной, если для любых двух наборов, таких, что (1, 2,…, n) (1’, 2’,…, n’) имеет место равенство f(1, 2,…, n) f(1’, 2’,…, n’) Множество всех монотонных булевых функций обозначается M. Монотонные наборы:   (1,0,1)(1,1,1) (0,0,1,0)(1,0,1,1)(1,0,1,0)(1,1,0,0) – не сравнимы. Их отбрасывают по таблице истинности
Набор (1,1) – самый большой будет сравним с любым другим набором. Набор (0,0) – самый маленький будет сравним с любым другим набором. Наборы (0,1) и (1,0) - не сравнимы. На меньшем наборе функция принимает меньшее значениемонотонна. Каждый из классов булевых функций: класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс линейных функций, класс монотонных функций и множество всех булевых функций, является замкнутым. Критерии полноты Поста-Яблонского Теорема о функциональной полноте была сформулирована в 1921 г. американским ученым Эмилем Постом и доказана советским ученым Яблонским С.В. Система булевых функций является полной, когда в ней имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая единицу, хотя бы одна не самодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. не сохраняющую константу 0; Таблица некоторых элементарных булевых функций: «+» - принадлежит классу, «-» не принадлежит.
Функционально полными являются: {, ,¬}, {+, ,1}, {,¬}, {, ¬}, {|}, {}. |
0
0
0
1