Элементарное произведение

Cтраница 3

Операция склеивания может быть применена только к конституентам ( в общем случае элементарным произведениям) с переменными, у которых все степени, за исключением одной, совпадают. Например, хуг можно склеить с xyz, так как степени переменных у и г ( у1 и z) совпадают, а степени переменной х различны. Такие конституенты называются соседними. Из способа распределения конституент на карте Вейча следует, что все соседние конституенты имеют на карте соседние клетки. [31]

Так называемая первая каноническая форма называется еще дизъюнктивной нормальной формой и является суммой элементарных произведений. Элементарное произведение - произведение, содержащее все элементарные высказывания или их отрицания. [32]

Дизъюнктивная ( соответственно конъюнктивная) нормальная форма называется совершенной, если все составляющие ее элементарные произведения ( соответственно элементарные дизъюнкции) являются конституентами единицы ( соответственно конституентами нуля) для одного и того же множества М переменных. [33]

Построив накрытие М булевой функции на карте Карнау, нетрудно найти явные выражения для элементарных произведений, соответствующих всем конфигурациям этого накрытия, и построить определяемую данным накрытием дизъюнктивную нормальную форму. С этой целью достаточно выяснить, значения каких переменных остаются постоянными для всех наборов, определяющих места любой заданной правильной конфигурации из рассматриваемого накрытия. Нетрудно видеть, что все такие и только такие переменные входят в элементарное произведение / г, соответствующее конфигурации К. Ясно также, что каждая такая переменная входит в элементарное произведение р в прямом или инверсном виде, соответственно тому, равняется ли ее значение на всех наборах, составляющих конфигурацию К, единице или нулю. [34]

Для правильного понимания сформулированного определения необходимо напомнить, что, согласно принятому в предыдущей главе условию, элементарное произведение, состоящее из пустого множества, сомножителей, принимается равным единице. Таким образом, константа 1 является собственной частью любого элементарного произведения. В силу сделанного замечания состоящее из одного сомножителя ( буквы) элементарное произведение, являясь импликантой какой-либо булевой функции, не равной тождественно единице, будет всегда простой импликантой этой функции. [35]

Используя это правило, легко найти, например, что конфигурации, состоящей из элементарных квадратиков 5 и 4, соответствует элементарное произведение xyz, а конфигурации ( ( 2 X 2) - квадрату. [36]

Следовательно, доказательство полноты системы функций И, ИЛИ и НЕ сводится к доказательству представления любой булевой функции в форме дизъюнкции элементарных произведений. [37]

А 1 - А, составленное из элементов А -, или их отрицаний А ] и содержащее п сомножителей, называется элементарным произведением. [38]

Карты Вейча из примера 2 в § 3 - 4.| Элементарные произведения, получаемые конституент. [39]

Поэтому склеивать можно соседние две, четыре, или в общем случае 2 единиц на карте Вейча, а отыскание минимальной ДНФ сводится к определению минимального числа наиболее коротких элементарных произведений, накрывающих все единицы на карте данной функции. [40]

Схема объекта диагностики. [41]

Поскольку все минимальные диагностические тесты ( их может быть несколько) находятся среди элементарных тестов, решение первой задачи сводится к выбору, после преобразования &V к / &, элементарных произведений минимальной длины. Ввиду трудоемкости указанного преобразования при последующем изложении мы будем интересоваться другими способами построения минимальных диагностических тестов, которые исключают необходимость подобного преобразования. [42]

В нулевом цикле производится последовательное умножение младшего разряда множителя Ь0 на все разряды множимого ( начиная от а0 до a, i), причем после перемножения каждой пары десятичных цифр полученное элементарное произведение суммируется ( после соответствующего сдвига) с накопленной ранее суммой элементарных произведений. Результатом выполнения нулевого цикла является частичное произведение С0, равное произведению множимого на младший разряд множителя. [43]

Вместе указанные квадраты накрывают все единицы функции /, и потому эта функция ( с точностью до безразличных значений, обозначенных черточками) может быть представлена в виде дизъюнкции соответствующих им элементарных произведений / у и V хг. [44]

В первом цикле вырабатываются два элементарных произведения путем умножения нулевого разряда множимого а0 на первый разряд множителя fei и первого разряда множимого аг на нулевой разряд множителя &0 - Затем вычисляется сумма этих элементарных произведений и переноса из нулевого цикла. Младший разряд полученной суммы равен первому разряду окончательного произведения, а старший является переносом в следующий разряд. [45]

Страницы: 1 2 3 4