Вечернего и заочного обучения
 Скачать 0.85 Mb.
|
Дискретная математикаПрограмма дисциплины
Теоретический материалТеорема 1. Любую функцию  можно представить в виде СДНФ.Простые конъюнкции составляются для тех наборов (x1, …, xn), где f = 1; если xi = 0, берем  , если xi = 1, берем xi.Составляя дизъюнкцию простых конъюнкций, получаем СДНФ. Теорема 2. Любую функцию  можно представить в виде СКНФ. Простые дизъюнкции составляются для тех наборов (x1,…, xn), где f = 0; если xi = 1, берем , если xi = 0, берем xi.Конъюнкция простых дизъюнкций дает СКНФ. Теорема 3 (Поста). Для того чтобы некоторый набор функций был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T0, T, L, M, S: T0 – класс функций, сохраняющих 0; T – класс функций, сохраняющих 1; L – класс линейных функций; M – класс монотонных функций; S – класс самодвойственных функций. Классы функцийT0 : f(0,0,…,0) = 0; T1 : f(1,1,…,1) = 1; L : f(x1,…, xn) = a0 + a1x1 +…+ anxn; S : f(x1,…, xn) = f*( x1,…, xn) =  ;M : f(1) f(2) при 1 < 2 (1 = (x1,…, xn); 2 = (x1,…, xn);  ).Логические функции двух переменных f(x1, x2)
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
