Конъюнктивные формы представления логических функций. Нормальные формы: днф, кнф, сднф, скнф Примеры скнф для некоторых функций
Стандартный базис. Элементарные формулы - литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 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, хотя обе формы равнозначны.
Простой дизъюнкцией { англ. inclusive disjunction } или дизъюнктом { англ. disjunct } называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
Простая дизъюнкция
- полная , если в неё каждая переменная (или её отрицание) входит ровно один раз;
- монотонная , если она не содержит отрицаний переменных.
Конъюнктивная нормальная форма, КНФ { англ. conjunctive normal form, CNF } нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.
Пример КНФ: $f(x,y) = (x \lor y) \land (y \lor \neg { z })$
СКНФ
Совершенная конъюнктивная нормальная форма, СКНФ { англ. perfect conjunctive normal form, PCNF } - это такая КНФ, которая удовлетворяет условиям:
- в ней нет одинаковых простых дизъюнкций
- каждая простая дизъюнкция полная
Пример СКНФ: $f(x,y,z) = (x \lor \neg { y } \lor z) \land (x\lor y \lor \neg { z })$
Теорема: Для любой булевой функции $f(\vec { x })$, не равной тождественной единице, существует СКНФ, ее задающая.
Доказательство: Поскольку инверсия функции $\neg { f } (\vec x)$ равна единице на тех наборах, на которых $f(\vec x)$ равна нулю, то СДНФ для $\neg { f } (\vec x)$ можно записать следующим образом:
$\neg { f } (\vec x) = \bigvee\limits_ { f(x^ { \sigma_ { 1 } } , x^ { \sigma_ { 2 } } , ... ,x^ { \sigma_ { n } }) = 0 } (x_ { 1 } ^ { \sigma_ { 1 } } \wedge x_ { 2 } ^ { \sigma_ { 2 } } \wedge ... \wedge x_ { n } ^ { \sigma_ { n } }) $, где $ \sigma_ { i } $ обозначает наличие или отсутствие отрицание при $ x_ { i } $
Найдём инверсию левой и правой части выражения:
$ f(\vec x) = \neg ({ \bigvee\limits_ { f(x^ { \sigma_ { 1 } } , x^ { \sigma_ { 2 } } , ... ,x^ { \sigma_ { n } }) = 0 } (x_ { 1 } ^ { \sigma_ { 1 } } \wedge x_ { 2 } ^ { \sigma_ { 2 } } \wedge ... \wedge x_ { n } ^ { \sigma_ { n } }) }) $
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: $ f(\vec x) = \bigwedge \limits_ { f(x^ { \sigma_1 } , x^ { \sigma_2 } , \dots ,x^ { \sigma_n }) = 0 } $ $(\neg { x_1^ { \sigma_1 } } \vee \neg { x_2^ { \sigma_2 } } \vee \dots \vee \neg { x_n^ { \sigma_n } }) $
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть построена для любой функции, не равной тождественному нулю, то теорема доказана.
Алгоритм построения СКНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно $0$.
- Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть $0$, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные дизъюнкции связываем операциями конъюнкции.
Пример построения СКНФ для медианы
1). В таблице истинности отмечаем те наборы переменных, на которых значение функции равно $0$.
| x | y | z | $ \langle x,y,z \rangle $ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2). Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть $0$, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
| x | y | z | $ \langle x,y,z \rangle $ | |
| 0 | 0 | 0 | 0 | $(x \lor y \lor z)$ |
| 0 | 0 | 1 | 0 | $(x \lor y \lor \neg { z })$ |
| 0 | 1 | 0 | 0 | $(x \lor \neg { y } \lor z)$ |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | $(\neg { x } \lor y \lor z)$ |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
3). Все полученные дизъюнкции связываем операциями конъюнкции.
$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg { x } \lor y \lor z) \land (x \lor \neg { y } \lor z) \land (x \lor y \lor \neg { z })$
Примеры СКНФ для некоторых функций
Стрелка Пирса: $ x \downarrow y = (\neg { x } \lor { y }) \land ({ x } \lor \neg { y }) \land (\neg { x } \lor \neg { y }) $
Исключающее или: $ x \oplus y \oplus z = (\neg { x } \lor \neg { y } \lor z) \land (\neg { x } \lor y \lor \neg { z }) \land (x \lor \neg { y } \lor \neg { z }) \land (x \lor y \lor z)$
Для всякой логической формулы с помощью тождественных преобразований можно построить бесконечно много равносильных ей формул. В алгебре логики одной из основных задач является поиск канонических форм (т. е. формул, построенных по единому правилу, канону).
Если логическая функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных, то такая форма представления называется нормальной.
Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).
Совершенная дизъюнктивная нормальная форма (СДНФ)
Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.
Примеры: y, ¬ y, х 1 ∧ ¬ х 2 ∧ х 3 ∧ х 4
Определение. Формула называтся дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций.
ДНФ записывается в следующей форме: F 1 ∨ F 2 ∨ ... ∨ F n , где F i - элементарная конъюнкция
Примеры: ¬ х 1 ∧ х 2 ∨ х 1 ∧ ¬ х 2 ∨ х 1 ∧ ¬ х 2 ∧ х 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2
Определение.
Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х 1 , х 2 , …, х k , причем на i-м месте этой конъюнкции стоит либо переменная х i , либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.
Пример: (¬ х 1 ∧ х 2 ∧ х 3) ∨ (х 1 ∧ ¬ х 2 ∧ х 3) ∨ (х 1 ∧ х 2 ∧ ¬ х 3)
Совершенная конъюнктивная нормальная форма (СКНФ)
Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.
Примеры: ¬ х 3 , х 1 ∨ х 2 , х 1 ∨ х 2 ∨ ¬ х 3
Определение. Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций.
КНФ записывается в следующей форме: F 1 ∧ F 2 ∧ ... ∧ F n , где F i - элементарная дизъюнкция
Примеры: (х 1 ∨ ¬ х 2) ∧ х 3 , (х 1 ∨ х 2) ∧ (¬ х 1 ∨ х 2 ∨ х 3) ∧ (х 1 ∨ ¬ х 2 ∨ ¬ х 3)
Определение.
Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х 1 , х 2 , …, х k , причем на i-м месте этой дизъюнкции стоит либо переменная х i , либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.
Пример: (х 1 ∨ х 2 ∨ х 3) ∧ (¬ х 1 ∨ ¬ х 2 ∨ х 3)
Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ .
Алгоритм построения СДНФ по таблице истинности
- Выбрать все строки таблицы, в которых значение функции равно единице.
- Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае - ее отрицание.
- Все полученные конъюнкции связываем операциями дизъюнкции.
Алгоритм построения СКНФ по таблице истинности
- Выбрать все строки таблицы, в которых значение функции равно нулю.
- Для каждой такой строки записать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в конъюнкцию включаем саму переменную, в противном случае - ее отрицание.
- Все полученные дизъюнкции связываем операциями конъюнкции.
Анализ алгоритмов показывает, что если на большей части строк таблицы истинности значение функции равно 0, то для получения ее логической формулы лучше построить СДНФ, в противном случае - СКНФ.
Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.
| x | y | z | F (x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)
Проверим полученную формулу. Для этого построим таблицу истинности функции.
| x | y | z | ¬ x | ¬ x ∨ y ∨ z | ¬ z | ¬ x ∨ y ∨ ¬ z | F (x, y, z) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Сравнив исходную таблицу истинности и построенную для логической формулы, заметим, что столбцы значений функции совпадают. Значит, логическая функция построена верно.
Нормальные формы логических функций Представление булевой функции в форме дизъюнкции конъюнктивных термов конституент единицы 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 | |
| Российское государство как правовое явление прежде всего должно обеспечивать реализацию назначения государства а также его основных конституционных характеристик как демократического федеративного правового социального светского государства с республиканской формой правления. Главное назначение государства определяется ст. | |||
Конъюнктивная нормальная форма удобна для автоматического доказательства теорем . Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания , закон де Моргана , дистрибутивность .
Энциклопедичный YouTube
-
1 / 5
Формулы в КНФ :
¬ A ∧ (B ∨ C) , {\displaystyle \neg A\wedge (B\vee C),} (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , {\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),} A ∧ B . {\displaystyle A\wedge B.}Формулы не в КНФ :
¬ (B ∨ C) , {\displaystyle \neg (B\vee C),} (A ∧ B) ∨ C , {\displaystyle (A\wedge B)\vee C,} A ∧ (B ∨ (D ∧ E)) . {\displaystyle A\wedge (B\vee (D\wedge E)).}Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
¬ B ∧ ¬ C , {\displaystyle \neg B\wedge \neg C,} (A ∨ C) ∧ (B ∨ C) , {\displaystyle (A\vee C)\wedge (B\vee C),} A ∧ (B ∨ D) ∧ (B ∨ E) . {\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}Построение КНФ
Алгоритм построения КНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
A → B = ¬ A ∨ B , {\displaystyle A\rightarrow B=\neg A\vee B,} A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . {\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).}2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
¬ (A ∨ B) = ¬ A ∧ ¬ B , {\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,} ¬ (A ∧ B) = ¬ A ∨ ¬ B . {\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.}3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения КНФ
Приведем к КНФ формулу
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . {\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).}Преобразуем формулу F {\displaystyle F} к формуле, не содержащей → {\displaystyle \rightarrow } :
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \neg Y\vee Z)\vee \neg X).}В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . {\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).}Например, следующая формула записана в 2-КНФ:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . {\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).}
