Частично определенные функции.Их минимальное доопределение
При конструировании логических устройств зачастую встречаются ситуации, когда у реализуемой ими булевой функции f(хn) на некоторой части наборов переменных`хn значения функции не заданы. Обычно так бывает в тех случаях, когда состояния системы, описываемые данными наборами переменных, физически не достижимы либо срабатывание управляющей системы не влияет на производственный процесс. Допустим, необходимо реализовать функцию трех переменных f =(010??001), у которой в векторе истинности на местах с номерами 3 и 4(соответствующих наборам переменных (011) и (100)) значения не заданы и могут быть выбраны любыми (0 или 1).
Определение. Если значения функции f(хn) не определены на некотором числе p наборов ее переменных`хn, то ее называют частично определенной, сокращенно – ЧОФ.
Очевидно, доопределить (то есть присвоить недостающие значения истинности функции ¦ на p неопределенных наборах) можно 2P способами. В рассмотренном выше примере р =2; 2P =4. Наборам с номерами 3 и 4 могут быть присвоены значения (00), (01), (10), (11).
Определение. Функция g называется доопределением частично определенной функции ¦, если она совпадает с ней на тех наборах, где ¦ определена.
Например, функция g = (01000001) является одним из 4 возможных доопределений частично определенной функции ¦ =(010??001).
Построение доопределений возможно различными способами. Однако для практики представляют наибольший интерес те из них, у которых реализующие их физические устройства будут иметь наиболее простую структуру. Нормальные формы таких доопределений содержат минимальное число символов переменных.
Определение. Пусть f(хn)– частично определенная функция. Ее единичным f1(хn)(нулевым f0(хn)) доопределением называют такое доопределение, где на месте неизвестных значений ¦ стоят только единицы (нули).
Допустим, для ЧОФ необходимо построить нормальную форму заданного типа.
Определение. Минимальным доопределением частично определенной функции f называют ее доопределение g, имеющее минимальное число символов переменных, входящих в соответствующую нормальную форму.
Для ДНФ справедлива следующая теорема.
Дата добавления: 2015-10-05; просмотров: 1737;