Cтраница 4
Диаграмма Вейча позволяет получить выражение переключательной ф-ции в дизъюнктивной нормальной форме ( ДНФ), представляющей собой дизъюнкцию произведений аргументов. В отличие от СДНФ входящие в ДНФ произведения не обязательно содержат все переменные. Для получения ДНФ в заполненной диаграмме обводят прямоугольными контурами все единицы. [46]
Из предложения 1.3 мы непосредственно выводим, что всякая тупиковая дизъюнктивная нормальная форма любой булевой функции совпадает с этой функцией. [47]
При использовании диаграммы Вейча функцию предварительно следует привести к дизъюнктивной нормальной форме ( ДНФ) - выразить в виде логической суммы простых конъюнкций. Простая конъюнкция, в которую входят все аргументы рассматриваемой логической функции, называется минтермом. [48]
Применим законы дистрибутивности, чтобы результат вновь предстал в дизъюнктивной нормальной форме. [49]
Другое следствие из этого предположения состоит в том, что дизъюнктивная нормальная форма формулы длины п имеет длину, асимптотически равную cnllogn, где с - некоторая константа, так как такая формула может включать асимптотически только 0 ( n / logn) различных атомарных формул. [50]
Возникает задача нахождения в классе - ( / з) дизъюнктивной нормальной формы, имеющей наиболее простое строение. [51]
В специальном случае последняя задача представляет особый интерес вследствие важности дизъюнктивной нормальной формы. Последняя представляет собой дизъюнкцию конъюнкций, причем каждая конъюнкция состоит из переменных исходной формулы или их отрицаний. Такая формула называется сокращенной ( в противоположность совершенной) дизъюнктивной нормальной формой. В данном случае p V q является сокращенной дизъюнктивной нормальной формой исходного выражения. Таким образом, попросту говоря, задача состоит в отыскании простейшего дизъюнктивного нормального выражения данной формулы. [52]