2015-06-28
820
Функция 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 дается полезная информация о свойствах всех функций двух переменных. Пользуясь этой таблицей можно проверить полноту заданной системы функций, а также построить другие базисы.
Задача минимизации ДНФ
