Конъюнктивной нормальной формой логической функции называется. «учебник по дискретной математике днф, сднф, кнф, скнф. Алгоритм построения КНФ
Введем понятие элементарной дизъюнкции.
Элементарной дизъюнкцией называется выражение вида
Конъюнктивной нормальной формой (КНФ) логической функции называется конъюнкция любого конечного множества попарно различных элементарных дизъюнкций. Например, логические функции
представляют собой конъюнкции элементарных дизъюнкций. Следовательно, они записаны в конъюнктивной нормальной форме.
Произвольная логическая функция, заданная аналитическим выражением, может быть приведена к КНФ путем выполнения следующих операций:
Использования правила инверсии, если операция отрицания применена к логическому выражению;
Использования аксиомы дистрибутивности относительно умножения:
Использования операции поглощения:
Исключения в дизъюнкциях повторяющихся переменных или их отрицаний;
Удаления всех одинаковых элементарных дизъюнкций, кроме одной;
Удаления всех дизъюнкций, в которые одновременно входят переменная и ее отрицание.
Справедливость перечисленных операций вытекает из основных аксиом и тождественных соотношений алгебры логики.
Конъюнктивная нормальная форма называется совершенной, если каждая входящая в нее элементарная дизъюнкция содержит в прямом или инверсном виде все переменные, от которых зависит функция.
Преобразование КНФ к совершенной КНФ осуществляется путем выполнения следующих операций:
Прибавления к каждой элементарной дизъюнкции конъюнкций переменных и их отрицаний, если они не входят в данную элементарную дизъюнкцию;
Использования аксиомы дистрибутивности;
Удаление всех одинаковых элементарных дизъюнкций, кроме одной.
В совершенной КНФ может быть представлена любая логическая функция, кроме
тождественно равной единице (). Отличительным свойством совершенной КНФ является то, что представление в ней логической функции единственно.
Элементарные дизъюнкции, входящие в совершенную КНФ функции, носят название конституент нуля. Каждая конституента нуля, входящая в совершенную КНФ, обращается в нуль на единственном наборе значений переменных, который является нулевым набором функции. Следовательно, число нулевых наборов логической функции совпадает с числом конституент нуля, входящих в ее совершенную КНФ.
Логическая функция константа нуля в совершенной КНФ представляется конъюнкцией 2nконституент нуля. Сформулируем правило составления СКНФ логической функции по таблице соответствия.
Для каждой строки таблицы соответствия, в которой функция равна нулю, составляется элементарная дизъюнкция всех переменных. При этом в дизъюнкцию входит сама переменная, если ее значение равно нулю, или отрицание, если ее значение равно единице. Полученные элементарные дизъюнкции объединяются знаком конъюнкции.
Пример 3.4. Для логической функции z(x), заданной таблицей соответствия 2.2, определим совершенную конъюнктивную форму.
Для первой строки таблицы, которая соответствует нулевому набору функции 000, находим конституенту нуля . Выполнив аналогичные операции для второй, третьей и пятой строк, определим искомую совершенную КНФ функции:
Необходимо отметить, что для функций, число единичных наборов которых превышает число нулевых наборов, более компактной является их запись в виде СКНФ и наоборот.
Стандартный базис. Элементарные формулы - литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.
Стандартный базис - это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.
Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ 1 xˆ 2 . . . xˆ л, называется элементарной конъюнкцией . Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x 1 x 1 = x 1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.
Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой , или ДНФ . Например,
x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .
Если состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, то ДНФ называется совершенной . Приведенный пример - это ДНФ, не являющаяся совершен- ной. Напротив, формула
x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4
есть совершенная форма.
Поскольку в булевой алгебре сложение и умножение - симметричные операции и всегда можно интерпретировать сложение как умножение, а умножение как сложение, существует и двойственное понятие - конъюнктивная нормальная форма (КНФ ), представляющая собой конъюнкцию элементарных дизъюнкций, и совершенная конъюнктивная форма (СКНФ ). Из принципа двойственности для симметричных полуколец вытекает, что любому утверждению относительно ДНФ отвечает двойственное утверждение относительно КНФ, которое получается заменой сложения (дизъюнкции) умножением, умножения (конъюнкции) сложением, константы 0 константой 1, константы 1 константой 0, отношения порядка двойственным (обратным) порядком. Поэтому далее мы остановимся на изучении только ДНФ.
Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.
◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y 1 , . . . , y n) принимает значение 1 на векторе (t 1 , . . . , t n) (такой вектор называют конституэнтой единицы ). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу
в которой сумма (объединение) распространяется на все те наборы (t 1 , . . . , t n) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество таких наборов не пусто, так что в сумме есть по крайней мере одно слагаемое.
Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f.
Следствие 1.1. Стандартный базис является полным.
◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x 1 , x 2 , . . . , x n) = x 1 x 1 .
Пример 1.2. Рассмотрим функцию трех переменных m(x 1 , x 2 , x 3) (табл. 1.4), называемую мажоритарной функциеи ̆. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.
Полнота стандартного базиса позволяет подбирать и другие полные системы функций. Полнота множества F может быть установлена из следующих соображений. Предположим, каждая из трех функций стандартного бузиса представима формулой над F . Тогда в силу теоремы 1.3 иножество F будет полным.
Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина . Сложение по модулю 2 и умножение - базовые операции кольца Z2, выражения, составленные с их помощью - это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина - это многочлен над кольцом Z2.
Нетрудно сконструировать формулы над базисом Жегалкина, представляющие операции сложения и отрицания стандартного базиса (умножение у двух базисов общее):
x+y=x⊕y⊕xy, x =x⊕1.
Поэтому базис Жегалкина - полное множество.
Можно показать, что для любой булевой функции полином Жегалкина определен однозначно
(точнее, с точностью до порядка слагаемых). Коэффициенты полинома Жегалкина при небольшом количестве переменных можно найти методом неопределенных коэффициентов.
Пример 1.4. Рассмотрим множество из единственной функции - штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:
x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).
Пример 1.5. Базис, состоящий из единственной функции - стрелки Пирса, также является полным. Проверка этого аналогична случаю штриха Шеффера. Впрочем, это заключение можно сделать и на основании принципа двойственности для симметричных полуколец.
*Штрих Шеффера - бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.
Нормальные формы логических функций Представление булевой функции в форме дизъюнкции конъюнктивных термов конституент единицы Ki 2.7 называется дизъюнктивной нормальной формой ДНФ этой функции. содержат в точности по одной все логические переменные взятые с отрицаниями или без них то такая форма представления функции называется совершенной дизъюнктивной нормальной формой СДНФ этой функции. Как видно при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов при которых функция принимает значение 1.
Поделитесь работой в социальных сетях
Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск
Лекция 1.хх
Нормальные формы логических функций
Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) K i
, (2.7)
называется дизъюнктивной нормальной формой (ДНФ ) этой функции.
Если все конъюнктивные термы в ДНФ являются минтермами , т. е. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ ) этой функции. СДНФ называется совершенной , потому что каждый терм в дизъюнкции включает все переменные; дизъюнктивной , потому что главная операция в формуле дизъюнкция. Понятие “ нормальной формы ” означает однозначный способ записи формулы, реализующей заданную функцию.
С учётом сказанного выше из теоремы 2.1 вытекает следующая теорема.
Теорема 2. Любая булева функция (не равная тождественно 0 ) может быть представлена в СДНФ , .
Пример 3. Пусть имеем таблично заданную функцию f (x 1 , x 2 , x 3 ) (табл. 10).
Таблица 10
|
f (x 1 , x 2 , x 3 ) |
|||
На основании формулы (2.6) получаем:
Как видно, при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов, при которых функция принимает значение 1.
Представление булевой функции в форме конъюнкции дизъюнктивных термов (конституент нуля) D i
, (2.8)
называется конъюнктивной нормальной формой (КНФ ) этой функции.
Если все дизъюнктивные термы КНФ являются макстермами , т. е. содержат в точности по одной все логические переменные функции, взятые с отрицаниями или без них, то такая КНФ называется совершенной конъюнктивной нормальной формой (СКНФ ) этой функции.
Теорема 3. Любая булева функция (не равная тождественно 1 ) может быть представлена в СКНФ , причём такое представление единственно .
Доказательство теоремы может быть проведено аналогично доказательству теоремы 2.1 на основании следующей леммы Шеннона о конъюнктивном разложении.
Лемма Шеннона . Любая булева функция f (x 1 , x 2 , …, x m ) от m переменных может быть представлена так :
. (2.9)
Нужно отметить, что обе формы представления логической функции (ДНФ и КНФ) теоретически являются равными по своим возможностям: любую логическую формулу можно представить как в ДНФ (кроме тождественного нуля), так и в КНФ (кроме тождественной единицы). В зависимости от ситуации представление функции в той или иной форме может быть короче.
На практике же чаще всего используется ДНФ , т. к. эта форма является для человека более привычной: с детства ему привычнее складывать произведения, чем умножать суммы (в последнем случае у него интуитивно появляется желание раскрыть скобки и перейти тем самым к ДНФ).
Пример 4. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, написать её СКНФ.
В отличие от СДНФ, при составлении СКНФ в таблице истинности логической функции нужно смотреть комбинации переменных, при которых функция принимает значение 0, и составить конъюнкцию соответствующих макстермов, но переменные нужно брать с обратной инверсией :
Нужно отметить, что непосредственно перейти от СДНФ функции к её СКНФ или наоборот невозможно. При попытке таких преобразований получаются функции, обратные по отношению к желаемым. Выражения для СДНФ и СКНФ функции непосредственно можно получить только из её таблицы истинности.
Пример 5. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, попробовать перейти от СДНФ к СКНФ.
Используя результат примера 2.3 получим:
Как видно, под общей инверсией получилась СКНФ логической функции, которая является обратной по отношению к функции, полученной в примере 2.4:
т. к. содержит все макстермы, которых нет в выражении для СКНФ рассматриваемой функции.
1. Используя свойства операций (см. табл. 9) тождественность (), сумма по модулю 2 (), импликация (), переходим к операциям И, ИЛИ, НЕ (в базис Буля).
2. Используя свойства отрицания и законы де Моргана (см. табл. 9) добиваемся, чтобы операции отрицания относились только к отдельным переменным, а не к целым выражениям.
3. Используя свойства логических операций И и ИЛИ (см. табл. 9), получаем нормальную форму (ДНФ или КНФ).
4. При необходимости переходим к совершенным формам (СДНФ или СКНФ). Например, для получения СКНФ часто нужно использовать свойство: .
Пример 6. Преобразовать в СКНФ логическую функцию
Выполняя по порядку шаги приведённого выше алгоритма, получим:
Используя свойство поглощения, получим:
Таким образом, мы получили КНФ функции f (x 1 , x 2 , x 3 ). Чтобы получить её СКНФ, нужно каждую дизъюнкцию, в которой не хватает какой-либо переменной, повторить дважды с этой переменной и с её отрицанием:
2.2.6. Минимизация логических функций
Поскольку одну и ту же логическую функцию можно представить ра з личными формулами, то нахождение наиболее простой фо р мулы, задающей булеву функцию, упрощает логическую схему, реализующую булеву фун к цию. Минимальной формой л о гической функции в некотором базисе можно считать такую, которая содержит минимальное число суперпозиций фун к ций базиса, допуская и скобки. Однако трудно построить эффективный а л горитм такой минимизации с получением минимальной скобочной фо р мы.
Рассмотрим более простую задачу минимизации при синтезе комбинационных схем, при которой ищется не минимальная скобочная форма функции, а её минимальная ДНФ. Для этой задачи существуют простые эффективные алгоритмы.
Метод Квайна
Минимизируемая функция представляется в СДНФ, и к ней применяются все возможные операции неполного склеивания
, (2.10)
а затем поглощения
, (2.11)
и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом.
Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простым и очевидным способом:
Этот способ плох тем, что при такой непосредственной минимизации конъюнктивные термы или исчезают, хотя возможны ещё случаи их использования для склеивания и поглощения с оставшимися термами.
Нужно отметить, что метод Квайна является достаточно трудоёмким, поэтому вероятность допущения ошибок во время преобразований достаточно велик. Но его преимуществом является то, что теоретически его можно использовать для любого числа аргументов и при увеличении количества переменных преобразования усложняются не так сильно.
Метод карт Карно
Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум 5-6 переменных.
Карта Карно это двумерная табличная форма представления таблицы истинности булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Каждой клетке таблицы сопоставляется минтерм СДНФ минимизируемой функции, причём так, что любым осям симметрии таблицы соответствуют зоны, взаимно инверсные по какой-либо переменной. Такое расположение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично.
Таблицы истинности и карты Карно для функций И и ИЛИ двух пер е менных представлены на рис. 8. В каждую клетку карты записывается зн а чение функции на соответствующем этой клетке наборе значений аргуме н тов.
А ) И б ) ИЛИ
Рис. 8. Пример карт Карно для функций двух переменных
В карте Карно для функции И только одна 1, поэтому её ни с чем невозможно склеить. В выражении для минимальной функции будет только терм, соответствующий этой 1:
f = x y .
В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy , используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x , а для вертикальной y , в итоге получим выражение
f = x + y .
На рис. 9 приведены таблицы истинности двух функций трёх переменных (а ) и их карты Карно (б и в ). Функция f 2 отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).
При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k -кубами , где k = log 2 K , K количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2 k , где k = 0, 1, 2, 3, … . Для k = 1 прямоугольник называется один-куб и содержит 2 1 = 2 единицы; для k = 2 прямоугольник содержит 2 2 = 4 единицы и называется два-куб ; при k = 3 область из 2 3 = 8 единиц называется три-куб ; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами , которые содержат только одну единицу (2 0 = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k только прямоугольников.
|
б в |
||||||
Рис. 9. Пример карт Карно для функций трёх переменных
Эти области могут пересекаться, т. е. одни и те же клетки могут входить в разные области. Затем записывается минимальная ДНФ функции как дизъюнкция всех конъюнктивных термов, соответствующих k - кубам.
Каждая из указанных областей на карте Карно представляется в минимальной ДНФ конъюнкцией, число аргументов в которой на k меньше общего числа аргументов функции m , т. е. это число равно m k . Каждая конъюнкция минимальной ДНФ составляется лишь из тех аргументов, которые для соответствующей области карты имеют значения либо без инверсий, либо только с инверсией, т. е. не меняют своего значения.
Таким образом, при охвате клеток карты замкнутыми областями следует стремиться к тому, чтобы число областей было минимальным, а каждая область содержала возможно большее число клеток, так как при этом будет минимальным число членов в минимальной ДНФ и число аргументов в соответствующей конъюнкции будет минимальным.
Для функции по карте Карно на рис. 9, б находим
поскольку для верхней замкнутой области переменные x 1 и x 2 имеют значения без инверсий, для нижней x 1 имеет значение с инверсией, а x 3 без инверсии.
Неопредёленные значения в карте на рис. 9, в можно доопределить, заменив нулём или единицей. Для данной функции видно, что оба неопределённых значения выгоднее заменить 1. При этом образуются две области, являющиеся различными видами 2-кубов. Тогда выражение для минимальной ДНФ функции будет следующим:
При построении замкнутых областей допускается сворачивание карты Карно в цилиндр как по горизонтальной, так и по ве р тикальной осям с объединением противоположных граней ка р ты, т. е. единицы, расположенные по краям карты Карно симметри ч но, также могут быть объединены.
Карты Карно можно рисовать разными способами (рис. 10).
|
x 2 x 3 |
||||||||||
а б
Рис. 10.
Разные способы изображения карт Карно
для функции 3 переменных
Но самыми удобными вариантами карт Карно для функций 2-4 переменных являются показанные на рис. 11 таблицы, т. к. в них для каждой ячейки показ а ны все переменные в прямом или инверсном виде.
а б
Рис. 11.
Наиболее удобное изображение карт Карно
для функций 3 (а
) и 4 (б
) переменных
Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 10, в .
Рис. 12. Изображение карты Карно для функции 5 переменных
Рис. 13. Изображение карты Карно для функции 6 переменных
Другие похожие работы, которые могут вас заинтересовать.вшм> |
|||
| 9020. | ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ | 96.34 KB | |
| Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу в виде совершенной д. н. ф. Для этого в таблице истинности для каждой для функции отмечаем все строки, в которых | |||
| 6490. | Описание и минимизация логических функций | 187.21 KB | |
| В словесной форме выражается взаимосвязь между аргументами функции и ее значениями. Пример: функция трех аргументов принимает значение когда любые два или более аргументов функции равны. Состоит в построении таблицы истинности содержащей значения функции для всех наборов значений аргументов. В данном примере по таблице истинности получаем такую запись в виде ДНФ... | |||
| 6707. | Проектирование реляционных баз данных. Проблемы проектирования в классическом подходе. Принципы нормализации, нормальные формы | 70.48 KB | |
| Что такое проект реляционной базы данных Это набор взаимосвязанных отношений в которых определены все атрибуты заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений которые относятся к принципам поддержки целостности. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных это фундамент будущего программного комплекса который будет использоваться достаточно долго и многими пользователями. | |||
| 4849. | Формы и методы осуществления функций государства | 197.3 KB | |
| Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов | |||
| 17873. | Формирование логических УУД у учащихся 3 класса | 846.71 KB | |
| Психолого-педагогические аспекты проблемы формирования логических универсальных действий у младших школьников Методики оценки сформированности логических УУД. Разработка концепции развития универсальных учебных действий в системе общего образования отвечает новым социальным запросам. Важнейшей задачей современной системы образования является формирование универсальных учебных действий УУД. Сформированность универсальных учебных действий является залогом профилактики школьных трудностей. | |||
| 2638. | Техническая реализация логических связей в системах автоблокировки | 1.04 MB | |
| Техническая реализация логических связей в системах автоблокировки Техническая реализация алгоритмов управления трехзначной и четырехзначной АБ может быть достигнута при помощи релейных контактных и бесконтактных дискретных и интегральных логических элементов... | |||
| 10203. | ПРИМЕНЕНИЕ КОНЦЕПЦИИ РИСК ОРИЕНТИРОВАННОГО ПОДХОДА ДЛЯ ПОСТРОЕНИЯ СТРУКТУРНО-ЛОГИЧЕСКИХ МОДЕЛЕЙ ВОЗНИКНОВЕНИЯ И РАЗВИТИЯ ЧС | 70.8 KB | |
| Общий анализ риска Производственная среда насыщается мощными технологическими системами и технологиями которые делают труд человека производительным и менее тяжелым физически однако более опасным. Для риска характерны неожиданность и внезапность наступления опасной ситуации. Ежедневно мы сталкиваемся с многочисленными рисками но большая часть из них остается потенциальными т. Теория риска предусматривает количественную оценку негативного воздействия на человека а также нанесения ущерба его здоровью и жизни. | |||
| 11576. | Понятие, виды и формы сделок. Последствия несоблюдения требуемой формы сделок | 49.82 KB | |
| Признание сделки недействительной виды недействительной сделки. Прикладная ценность курсовой работы заключается в упрощении понятия сделки то есть публичного его представления в более доступной форме. | |||
| 6213. | Приближение функций | 3.08 MB | |
| Первая состоит в замене некоторой функции заданный аналитически или таблично другой функцией близкой к исходной но более простой и удобной для вычислений. Например замена функции многочленом позволяет получать простые формулы численного интегрирования и дифференцирования; замена таблицы приближающей функцией позволяет получать значения в ее промежуточных точках. Возникает также и вторая задача восстановление функции на некотором отрезке по заданным на этом отрезке значениям функции в дискретном множестве точек. Ответ на такой вопрос... | |||
| 14058. | Эволюция функций государства | 29.99 KB | |
| Российское государство как правовое явление прежде всего должно обеспечивать реализацию назначения государства а также его основных конституционных характеристик как демократического федеративного правового социального светского государства с республиканской формой правления. Главное назначение государства определяется ст. | |||
Простой конъюнкцией называется конъюнкция одной или нескольких переменных , при этом каждая переменная встречается не более одного раза (либо сама , либо ее отрицание ).
Например, является простой конъюнкцией,
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций .
Например, выражение является ДНФ.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма , у которой в каждую конъюнкцию входят все переменные данного списка (либо сами , либо их отрицания ), причем в одном и том же порядке .
Например, выражение является ДНФ, но не СДНФ. Выражение 
является СДНФ.
Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных , при этом каждая переменная входит не более одного раза (либо сама , либо ее отрицание ).Например, выражение - простая дизъюнкция,
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение - КНФ).
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.
Например, выражение 
является СКНФ.
Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:
а) переход от ДНФ к КНФ
Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:
Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;
б) переход от КНФ к ДНФ
Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)
Таким образом, получили ДНФ.
Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;
в) сокращение ДНФ (или СДНФ) по правилу Блейка
Применение этого правила состоит из двух частей:
Если среди дизъюнктных слагаемых в ДНФ имеются слагаемые 
, то ко всей дизъюнкции добавляем слагаемое К
1 К
2 . Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;
Если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,
или
Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ 
, после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):
в) переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, z , вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
г) переход от КНФ к СКНФ
Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z , то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):
Таким образом, из КНФ получена СКНФ.
Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.
