Совершенная нормальная форма

Cтраница 2

Условия а), Ь), с), d) являются, таким образом, необходимыми и достаточными для того, чтобы дизъюнктивная нормальная форма была совершенной нормальной формой. Вместе с тем эти условия дают возможность высказать правила, позволяющие приводить любую не тождественную ложную формулу к совершенной дизъюнктивной форме. [16]

Символическое представление подсистемы ИЛИ-И. [17]

В более сложных случаях, чтобы воспользоваться формулами (4.3) и (4.18) теории вероятностей, логическую функцию (4.23) необходимо определенным образом преобразовать - привести ее к нормальной, а затем к совершенной нормальной форме. [18]

Символическое представление подсистемы ИЛИ-И. [19]

В более сложных случаях, чтобы воспользоваться формулами (5.3) и (5.18) теории вероятностей, логическую функцию ( 5.23 необходимо определенным образом преобразовать - привести ее к нормальной, а затем к совершенной нормальной форме. [20]

Необходимо попытаться образовать из диаграммы, заполненной единицами, сначала члены, содержащие одну переменную, затем члены от двух переменных и, наконец, члены от трех переменных. Один и тот же член совершенной нормальной формы, содержащий четыре переменных, может входить несколько раз в выражение функции, не изменяя ее значения. [21]

Есть несколько вариантов практического использования метода испытания остатков. Например, если функция алгебры логики задана в виде совершенной нормальной формы, то для определения остатков достаточно осуществить вынесение общего множителя за скобки. [22]

Любая переключательная функция может иметь несколько ДНФ и КНФ. Однозначность представления переключательной функции возможна при записи ее в совершенных нормальных формах. [23]

Интерпретация логических формул связывает с каждой формулой некоторую булеву функцию. Теоремы 4 и 5 показывают, что даже некоторого меньшего запаса логических формул ( совершенных нормальных форм) уже достаточно, чтобы задать любую булеву функцию. Согласно теореме 2 имеется всего 22 разных булевых функций п переменных. Число же разных логических формул в БНФ-грамматике, использующей п разных переменных, с очевидностью бесконечно. Таким образом, имеется бесконечное количество формул, задающих одну и ту же функцию, или, как мы будем говорить, эквивалентных формул. [24]

Условные обозначения основных логических элементов. [25]

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

Получение минимальной формы логического алгоритма этим методом состоит из нескольких этапов. По таблице истинности составляется исходная ( каноническая) форма переключательной функции, называемая совершенной дизъюнктивной ( СДНФ) или совершенной конъюнктивной ( СКНФ) нормальной формой. Совершенная нормальная форма обеспечивает возможность представления в ней любой логической функции. Алгоритм ее получения должен быть достаточно прост, она должна быть удобна для дальнейших преобразований. [27]

Однако для каждой функции может существовать несколько дизъюнктивных и конъюнктивных нормальных форм. Однако существует один вид дизъюнктивной нормальной формы и один вид конъюнктивной нормальной формы, в которых функция может быть записана только единственным образом. Они называются совершенными нормальными формами. [28]

Здесь слагаемое 2 - 1т соответствует возможному общему числу вхождений переменных, а слагаемое 2 1 1 соответствует возможному числу конъюнктивных или дизъюнктивных членов совершенной нормальной формы. При этом принято во внимание то, что совершенная дизъюнктивная нормальная форма, включающая более 2т - 1 конъюнктивных членов, может быть заменена функцией дополнения, или конъюнктивной формой, имеющей не более 2т 1 членов, и наоборот. Возникающая обычно возможность минимизации совершенной нормальной формы уменьшает число входных каналов, необходимых для ее схемной реализации. [29]

Для синтеза логических схем используется принцип суперпозиции наряду с применением элементарных логических функций. Наиболее рациональным является представление логических функций в нормальной форме. Для этого следует разобраться в таких понятиях, как элементарная конъюнкция, элементарная дизъюнкция, ранг функции, и перейти к совершенным нормальным формам функций. [30]

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