Функция f(х1,..., хn) называется линейной,если полином Жегалкина этой функции имеет линейный вид:
f(х1,..., хn) = а0 Å а1 x1 Å … Å аn xn,
где аi Î {0,1} (i = 0, l,..., n).
Пример. f(х) = х, f(х) =`х = х Å 1 – линейные функции; f(х1, х2) = х1 Ú х2 = х1 Å х2 Å х1•х2 – нелинейная функция.
Лемма 7. Из линейных функций суперпозицией можно получить только линейные функции.
Следствие. Полная система функций должна содержать хотя бы одну нелинейную функцию.
Таблица 2.6. Свойства функций двух переменных
Обозначение функции | Свойства функции | ||||
Сохраняющая 0 | Сохраняющая 1 | Самодвойственность | Монотонность | Линейность | |
f1 = 0 | + | – | + | + | + |
f2 = х1 Ù х2 | + | + | – | + | – |
f3 = х1 х2 | + | – | – | – | – |
f4 = x1 | + | + | + | + | + |
f5 = х2 х1 | + | – | – | – | – |
f6 = x2 | + | + | + | + | + |
f7 = x1 Å x2 | + | – | – | – | + |
f8 = х 1Ú х2 | + | + | – | + | – |
f9 = х 1¯ х2 | – | – | – | – | – |
f10 = x1 ~ x2 | – | + | – | – | + |
f11 = `x2 | – | – | + | – | + |
f12 = x2 ® x1 | – | + | – | – | – |
f13 =`x1 | – | – | + | – | + |
f14 = x1 ® x2 | – | + | – | – | – |
f15 = x1 ½ x2 | – | – | – | – | – |
f16 = 1 | – | + | + | + | + |
В таблице 2.6 дается полезная информация о свойствах всех функций двух переменных. Пользуясь этой таблицей можно проверить полноту заданной системы функций, а также построить другие базисы.
|
|
Задача минимизации ДНФ