![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Минимизация нормальных формМинимальной ДНФ (МДНФ) функции f(x1, ... ,xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими видами ДНФ, реализующими функцию f. Если для всякого набора Элементарная конъюнкция K называется импликантом функции f, если для всякого набора Импликант K функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f. Ясно, что всякий импликант функции f есть часть функции f. Теорема.Всякая функция реализуется дизъюнкцией всех своих простых имликант (ПИ). Доказательство. Пусть f(x1, ..., xn) есть функция, а A = K1 v ... v Km – дизъюнкция всех ее простых импликант. Пусть Если A( Если f( Следовательно, f = A. Теорема доказана. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ. Пусть A и B – произвольные формулы. Из свойств булевых операций вытекают следующие обратимые правила преобразования ДНФ: 1) 2) 3) 4) 5) Теорема( Квайна ). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращения ДНФ функции f. Доказательство.Пусть имеем сокращенную ДНФ функции f. Проведем все операции развертывания к каждому простому импликанту для получения недостающих переменных в каждом дизъюнктивном слагаемом сокращенной ДНФ. В полученном выражении из нескольких одинаковых дизъюнктивных слагаемых оставим только по одному экземпляру. В результате получим СДНФ функции f. Теперь, исходя из полученной СДНФ, в обратном порядке проведем операции добавления одинаковых дизъюнктивных слагаемых (с помощью правил идемпотентности), неполного склеивания и поглощения. В итоге получим исходную сокращенную ДНФ.
|