![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Теорема о разложении функции по переменным
f(x1, ..., xm, xm+1, ..., xn) = где дизъюнкция берется по всем наборам из 0 и 1, которое называется разложением функции f по переменным x1, ..., xn. Прежде чем доказать утверждение, рассмотрим примеры. Пример 1. m = 1, запишем разложение по переменным х: f(x1, ..., xn) = Пример 2.m=2, запишем разложение по переменным х и f(x1,x2,…xn) =
Если f(x1, x2) = x1 Å x2, то последняя формула дает x1 Å x2 = Доказательство. Для доказательства возьмем произвольный набор (a1, ..., a n) и покажем, что левая и правая части формулы (1) принимают на этом наборе одинаковые значения. Слева имеем f(a1, ..., an). Cправа : Дизъюнкция берется по всевозможным наборам (s1, ..., sm). Если в этих наборах хотя бы одно si ¹ ai (1≤i≤m), то Следствие 1. Любую функцию f(x1, ..., xn) не равную тождественно нулю можно представить в виде: , причём единственным образом. Этот вид называется совершенной дизъюнктивной нормальной формой функции f(x1, ..., xn) и записывается СДНФ. Доказательство.Существование СДНФ для функции не равной тождественно нулю вытекает из предыдущей теоремы. Покажем, что эта СДНФ единственная. В самом деле, имеется Итак, Замечание. Cледствие 2. Любая функция алгебры логики может быть представлена в виде формулы через отрицание, & и Ú. а) Если f ≡ 0, то f(x1, ..., xn) = б) Если f(x1, ..., xn) ¹ 0 тождественно, тогда ее можно представить в виде СДНФ, где используются только связки Пример 3. Пусть функция f(x1, x2, x3) задана таблицей истинности. Запишем ее в виде СДНФ. Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f(x1, x2, x3) = x10 & x21 & x30 Úx11 & x20 & x30 Úx11&x21 & x31= =
По принципу двойственности заменим & на Ú и наоборот, получим
Пример 4. Пусть f(x1, x2, x3) = x1
Функция равна нулю только на наборе (1, 1, 0), поэтому f(x1 x2 x3)=x1
|