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

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

К функциям, сохраняющим ноль, относятся

f(x ₁, x ₂)= x ₁ Ú x ₂ и    f(x ₁, x ₂)= x ₁ × x ₂.

К функциям, не сохраняющим ноль, относятся f(x)= и f(x ₁, x ₂)= x ₁ ~ x _2.

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

К функциям, сохраняющим единицу, относятся:

f(x ₁, x ₂)= x ₁ Ú x ₂ и f(x ₁, x ₂)= x ₁ × x ₂.

К функциям, не сохраняющим единицу, относятся:

f(x)=  и   f(x ₁ , x ₂)= x ₁ Å x ₂.

Булева функция называется линейной , если она представима полиномом Жегалкина первой степени.

В булевой алгебре доказывается теорема о возможности представления любой булевой функции от n переменных с помощью полинома Жегалкина n-ой степени.

В общем случае полином имеет вид:

f ⁿ(Х) = K₀ Å K₁x₁ Å ... Å K_n x_n Å ...

... Å K_n+1x₁x₂ Å K_n+2x₁x₃ Å ... Å K_n+lx_n-1x_n Å ...

...Å K_n+mx₁x₂...x_n.

K ₀, K ₁, …, K_{n + m} - являются коэффициентами полинома и представляют собой логические константы K_i =0или K_i=1.

В алгебре Жегалкина одноименный полином (полином Жегалкина) можно считать аналогом канонической нормальной формы функции для булевой алгебры.

Полином Жегалкина является линейным (1-ой степени) , если все коэффициенты общего полинома, начиная с K_{n +1}, равны нулю.

В отношении функции от двух переменных линейный полином Жегалкина имеет вид: f ²(Х)= K ₀ Å K ₁ x ₁ Å K ₂ x ₂.

Примерами линейных функций являются:

y = x ₁Å x ₂ (K ₀ =0, K ₁ = K ₂ =1),

y = =1Å x (K ₀ = K ₁ =1, K ₂ =0).

Примеры нелинейных функций:  y = x ₁ × x ₂,  

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

A =(a₁, a₂, ..., a_n) > B =(b₁, b₂, ..., b_n)Þ f( A ) ³  f( B ).

Между наборами аргументов А и В имеет место отношение возрастания в том и только том случае, если имеет место отношение неубывания для всех компонент этого набора:

a_i ³ b_i (i =1, 2, ..., n)

и, по крайней мере, для одной компоненты имеет место отношение возрастания.

Примеры наборов, для которых имеет место отношение возрастания:

(1011) > (0011)

(1011) > (0001)

 (0001) > (0000).

Примеры несопоставимых наборов (1011) и (0111), (1000) и (0111).

В отношении функции от двух переменных несопоставимыми являются наборы (01) и (10)

Примеры немонотонных функций:

y = , y = x ₁Å x ₂.

Две булевы функции f ⁿ(Х) и gⁿ(Х) называются двойственными , если для любых наборов аргументов выполняется равенство 

то есть функции f и g на противоположных наборах аргументов Х и  принимают противоположные значения.

Два набора аргументов называются противоположными, если каждая из их компонент принимает противоположные значения, например,

Х = (0101) и = (1010).

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

Примером самодвойственной функции является: у = .

Примеры не самодвойственных функций: у=х₁ × х₂, у=х₁Ú х₂, у=х₁Å х₂.

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

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

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

 

 

Функция	К0	К1	К L	К M	К S
0	+	-	+	+	-
1	-	+	+	+	-
	-	-	+	-	+
х1 × х2	+	+	-	+	-
х1Ú х2	+	+	-	+	-
х1Å х2	+	-	+	-	-
х1 ~ х2	-	+	+	-	-
х1 D х2	+	-	-	-	-
х1® х2	-	+	-	-	-
х1 | х2	-	-	-	-	-
х1¯ х2	-	-	-	-	-

 

 

Таблица 2.10. Принадлежность булевых функций к замечательным классам

 

2.15.3 Конструктивный подход к доказательству функциональной
полноты системы булевых функций

Подход базируется на следующей теореме булевой алгебры:

Теорема. Пусть система булевых функций {f ₁, …, f_m} является функционально полной и любая из функций f ₁, …, f_m может быть выражена с помощью суперпозиции через функции g ₁, …, g_k. Тогда система булевых функций {g ₁, …, g_k} также является функционально полной.

При этом в качестве исходной системы {f ₁, …, f_m} обычно используется система S ₁ (булев базис).

Пример 2.18. Докажем функциональную полноту системы S ₅ ={|} (универсальный базис), выразив инверсию, конъюнкцию и дизъюнкцию с помощью только функции штрих Шеффера .

Таким образом, согласно приведенной теореме, система S ₅ является функционально полной.

Контрольные вопросы и задачи

1. Записать законы двойственности. Доказать один из них. (5)

2. Упростить выражение  с использованием законов булевой алгебры. (2)

3. Является ли аналитическая форма булевой функции  нормальной, и если является, то какой (дизъюнктивной или конъюнктивной)? (3) Может ли эта форма являться канонической, и если может, то какой (дизъюнктивной или конъюнктивной) и при каких условиях? (2)

4. Действует ли сочетательный закон в отношении операции запрета? Ответ обосновать. (5)

5. Записать функцию  с помощью операций булева базиса. (2)

6. Записать функцию   в канонических формах. (4)

7. Не пользуясь таблицей истинности, получить канонические формы булевой функции  . (8)

8. Записать функцию   в символической форме. (5)

9. Представить функцию  в канонических формах. (6)

10. Сколько 1-кубов накрывается одним 4-кубом? Ответ обосновать. (5)

11. Записать все 2-кубы, которые накрываются кубом XX10X. (3)

12. Найти существенные импликанты булевой функции . (10)

13. Булева функция от четырех переменных принимает значение, равное нулю, на наборах (0, 7, 8, 13) и безразличное значение – на наборах (2, 6, 10, 14). Найти минимальную ДНФ этой функции. (10)

14. Привести пример минимального покрытия булевой функции от четырех переменных, для которого S^a =10, S^b=14. (6)

15. Привести пример булевой функции от четырех переменных, для которой минимальная ДНФ совпадает с канонической, а минимальная КНФ не совпадает с канонической, и число существенных вершин равно пяти. Функцию представить в числовой форме. (5)

16. Для функции из примера 15 найти минимальную КНФ. (6)

17. Является ли покрытие булевой функции, состоящее из кубов 0X0, 10X, X00 минимальным? Ответ обосновать. (5)

18. Минимальное единичное покрытие булевой функции состоит из кубов 0X0 и X10. Найти минимальную КНФ. (6)

19. В отношении минимального покрытия сформулировать условия, при которых цена схемы с парафазными входами, построенной на элементах булева базиса по минимальной форме, совпадает с ценой S^a минимального покрытия. (3)

20. Перечислить все базовые функции булевой алгебры, сохраняющие константу 0. (3)

21. Является ли функция равнозначности нелинейной? Утверждение доказать. (3)

22. Является ли функция запрета монотонной? Утверждение доказать.(3)

23. Реализовать дизъюнкцию в базисе Жегалкина. (4)

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

Синтез комбинационных схем

⇐ Предыдущая891011121314151617Следующая ⇒

Поделиться: