![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задание 6. 6.1. Требуется выделить из данного набора из 5 функций полные наборы функций и базисы:
6.1. Требуется выделить из данного набора из 5 функций полные наборы функций и базисы: 1) f1 (x, y, z) = (x y)¯ (y ~ z), 2) f2 (x, y) = x + y x, 3) f3 (x, y, z) = x ~ (y z), 4) f4 (x, y) = x + 5) f5 (x, y, z) = x y Ú Решение. Составляем таблицу истинности для каждой из этих 5-и функций. Заметим, что для f2 и f4 таблицу можно составить отдельно.
Отсюда очевидно, что f1 (x, y, z) Î T0 (принадлежит классу Т0) и f1 Ï T1, f1 Ï M, S (не принадлежит Т1 и М, S), аналогично f3 не принадлежит T0, T1 и M, S. Функция f5 принадлежит Т1 и не принадлежит Т0 и М, S. Осталось проверить линейность этих функций. f3 = x ~ (y z) = f5 = x y Для f1 требуется проверка нелинейности. Составим полином Жегалкина для f1: P = a0 + a1 x + a2 y + a3 z + a4 x y + a5 x z + a6 y z + a7 x y z. Находим последовательно a: a0 = 0, a3 = 1, a2 = 1, a4 = 0, a5 = 0, a1 = 1, a1 + a3 + a6 = 1, откуда a6 = 1; значит, функция f1 нелинейна (что, впрочем, следует и из того, что f1 в таблице истинности содержит нечетное число единиц (равное 3). Для f2 и f4 составляем свои таблицы истинности.
Отсюда следует, что f2 принадлежит T0, не принадлежит T1, не принадлежит M, S; f2 является полиномом Жегалкина f2 = x + y + 1 и, значит, принадлежит L, принадлежит также T1, но не принадлежит M, S. Все эти сведения сведём в таблицу Поста.
Таким образом, мы видим, что базисами являются: 1) f3, 2) f1 и f4, 3) f2 и f4, 4) f1 и f5, 5) f2 и f5. Они являются полными наборами, как и любые наборы, содержащие базисы.
|