Cтраница 3
В дальнейшем, говоря об элементарной конъюнкции, будем называть ее просто конъюнкцией. [31]
СДНФ содержит не более Ds элементарных конъюнкций, каждая из которых состоит из O ( log2 D) сомножителей. [32]
Если в ДНФ имеется несколько одинаковых элементарных конъюнкций, то мы оставляем только одну. [33]
На каждом шаге кольцевой алгоритм использует элементарные конъюнкции, входящие в окрестность k - ro порядка некоторой конъюнкции и информационные отметки этих конъюнкций. [34]
Конституента ( полная конъюнкция) - элементарная конъюнкция, в которую по одному разу входит каждая переменная, определяющая состояние среды. [35]
Эти формы представляют собой лишь дизъюнкции элементарных конъюнкций или конъюнкции элементарных дизъюнкций. [36]
Дизъюнкцию D элементарных конъюнкций назовем тупиковой относительно элементарной конъюнкции К, если D поглощает К ( см. раздел 2), а дизъюнкция, получающаяся из D при удалении любой конъюнкции, уже не поглощает К. [37]
Если же xi не входит в элементарную конъюнкцию, в / - м компоненте ставится прочерк. В этом случае на каждом этапе сравнение может производиться лишь между элементарными конъюнкциями, соответствующими троичным наборам из соседних по номеру групп. [38]
Такие конъюнкции всех переменных формулы называются элементарными конъюнкциями. [39]
Функция, в СДНФ которой добавлена одна элементарная конъюнкция, принимает значение 1 еще только на одном наборе. Пусть R - исходное отношение, a R1 - отношение, которому соответствует ЛФО ( У. Ана логичное рассуждение в случае удаления одной конъюнкции завершает доказательство. [40]
Для минимизации БФ по методу Квайна все элементарные конъюнкции в записи ее совершенной ДНФ сравниваются попарно. Если две конъюнкции таковы, что имеют вид axi и axi, то вместо них выписывается единственная конъюнкция a ( L - 1) - го ранга. [41]
Число переменных ( аргументов), составляющих элементарную конъюнкцию или дизъюнкцию, называется ее р а н том. & xs, xj XiXzXaXi является элементарной конъюнкцией летвертфго ранга; функция М ( х, у, г) i хуг - элементарной конюънкцией третьего ранга. [42]
Очевидно, что полные элементарные конъюнкции являются элементарными конъюнкциями. [43]
G s - различные; Ki называются полными элементарными конъюнкциями. [44]
Каждой грани, содержащейся в Nf, соответствует элементарная конъюнкция, имеющая не менее двух множителей с отрицаниями и не менее одного множителя без отрицаний. [45]