Cтраница 3
Любая переключательная функция имеет конечное множество простых импликант, число которых не больше числа конституент 1 в СДНФ. Дизъюнкция всех простых импликант функции называется сокращенной ( так как число членов в ней не больше, чем в совершенной) ДНФ функции. Из этого определения следует, что каждая функция имеет единственную сокращенную ДНФ. [31]
Очевидно, что если ни один из первых конституентов системы связок не совпадает с обязательными конституентами системы пар, то система пар конституентов будет являться и общей системой пар и связок конституентов. [32]
Если останется один соседний конституент, то можно исключить одну переменную, соответствующую координате этого конституента, причем эта переменная исключается либо обязательно, либо условно в зависимости от того, какой конституент ( обязательный или условный) остался. Если оставшийся конституент является обязательным, то отмечаем его знаком, это означает, что данный конституент мы уже использовали и в дальнейшем не будем рассматривать. [33]
Конституенты 2 и 6 используются в качестве обязательных при упрощении конституента 14, тогда для конституента 7 они будут условными. [34]
Граф G ( f. [35] |
Гранью графа Коп ( 2, 3) называется такое подмножество вершин, что дизъюнкция соответствующих конституент равносильна некоторой элементарной конъюнкции. [36]
Если ни один из обязательных конституентов общей системы пар и связок конституентов не совпадает с запрещенными конституентами этой же системы, то такая система является согласованной, а соответствующая ей потенциально-импульсная форма - интегрируемой. При этом сразу может быть найдена функция F: обязательными конституентами этой функции будут все обязательные конституенты пар и все конституенты связок, вошедших в общую систему; запрещенными будут все запрещенные конституенты пар и первые конституенты связок, не вошедших в общую систему, за исключением конституентов, входящих в такие связи, вторые конституенты которых являются обязательными. [37]
Исключая из импликантной таблицы столбцы, обозначенные уже накрытыми конституентами, мы методом перебора сможем найти минимальные накрытия оставшихся конституент. [38]
Поскольку конституента единицы от п переменных требует для своего построения п - 1 двухвходовых совпадений, а общее число конституент равно 2, то мы приходим к следующему выводу. [39]
Переключательная функция представлена в конъюнктивной совершенной нормальной форме ( КСНФ), если все ее составляющие эле ментарные дизъюнкции являются конституентами нуля для данного множества переключательных аргументов. [40]
Дизъюнктивная ( соответственно конъюнктивная) нормальная форма называется совершенной, если все составляющие ее элементарные произведения ( соответственно элементарные дизъюнкции) являются конституентами единицы ( соответственно конституентами нуля) для одного и того же множества М переменных. [41]
В случае неравенства Ах Вх 0 дело обстоит так, что в А - f - В не должны входить с коэффициентами 1 все члены разложения по конституентам для остальных переменных ( кроме х), иначе будем иметь А - - В 1, где есть знак тождества. Отсюда также получается красивый графический прием для исключения неизвестных, который мы осветим уже после того, как опишем графический метод Венна. [42]
Предположим, что переменными, от которых зависит функция /, будут переменные х, у, г, и, так что первая импликанта /, ( конституента с номером 15) будет иметь вид: /, хуги. Для нахождения в явном виде остальных импликант воспользуемся следующим очевидным приемом: 1) выписываем для каждой простбй импликанты Р какую-нибудь конституенту единицы К, номер которой входит в обозначающее множество импликанты Р; 2) по разностям, соответствующим импликанте Р, определяем переменные, которые отсутствуют в представляющем ее элементарном произведении, и вычеркиваем эти переменные из конституенты К. [43]
Нетрудно убедиться в том, что для любой конституенты единицы К существует один и только один набор а значений переменных, входящих в К, на котором эта конституента обращается в единицу. Построенный таким образом набор а и конституента единицы К, которая на этом наборе об ращается в единицу, называются соответствующими друг другу. [44]
Пирамидальный дешифратор при га 4. [45] |