3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании,

Презентация:



Advertisements
Похожие презентации
Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Advertisements

ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Элементарной дизъюнкцией называется выражение вида: Элементарной конъюнкцией называется выражение вида: Где A i - либо.
2. Логические функции (Булевы функции) Пример: Устройство для голосования. Комиссия из 3-х человек, (Peeter, Jaan, Mari), голосует по вопросу о принятии.
Логика в информатике Решение уравнений. Логические основы ПЭВМ.
4. Минимизация логических функций. Карты Карно. Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное её представление.
1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
СДНФ и СКНФ Формы булевых функций. Дополнительные операции Импликация Эквивалентность Сложение по модулю 2 Стрелка Пирса (ИЛИ-НЕ) Штрих Шеффера (И-НЕ)
1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление высказываний Высказывание – утверждение о математических.
Логические функции. Логической (булевой) функцией называют функцию F(x 1,x 2,...,x n ), аргументы которой x 1,x 2,...,x n (независимые переменные) и сама.
Булевы функции СДНФ и СКНФ. Дополнительные операции Импликация Эквивалентность Сложение по модулю 2 Стрелка Пирса (ИЛИ-НЕ) Штрих Шеффера (И-НЕ)
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 3. Тема: ДНФ. СДНФ. Цель: Определить.
Алгебра логики Основные понятия. Введение Буль (Boole) Джордж ( , Линкольн, , Баллинтемпл близ Корка), английский математик и логик.
Булевы переменные и функции Булевыми переменными называются переменные, принимающие значение 0 или 1. Булевы (или логические) функции оперируют с булевыми.
Алгебра логики Основные понятия. Введение Буль (Boole) Джордж ( , Линкольн, , Баллинтемпл близ Корка), английский математик и логик.
содержание 1определение 1.определение 2.логическоеотрицание 2.логическое отрицание 3.логическое сложение 4.логическое умножение 5логическоеследование.
Нормальные формы в математической логике Подготовил: Шинкарёв Г. Г. ГИП-104.
Булевы переменные и функции Булевыми переменными называются переменные, принимающие значение 0 или 1. Булевы (или логические) функции оперируют с булевыми.
1. Алгебра высказываний Аксёнов Сергей Владимирович к.т.н., доцент каф.ОСУ ТПУ Национальный исследовательский Томский политехнический университет Логика.
7. Элементы логических схем (логические элементы) Электрическую схему, обрабатывающую двоичные коды называют дигитальной схемой. Составляющими частями.
Транксрипт:

3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании, чем любая другая равносильная ей формула.

Определение 3.1 Дизъюнктивной нормальной формой (ДНФ) называют формулу, которая представляет собой дизъюнкцию элементарных конъюнкций. Нормальные формы дизъюнктивные конъюнктивные совершенныенесовершенные совершенныенесовершенные Пример: следующая логическая функция представлена в дизъюнктивной нормальной форме:

Доказательство: Определение 3.2 Элементарной конъюнкцией n-переменных X 1, X 2,..., X n называют конъюнкцию X 1 1 & X 2 2 & … & X n n, где каждая переменная X i присутствует не более одного раза, i {0,1}. Обозначим: X i i = X i, если i = 1 X i i = X i, если i = 0 Предложение 3.1 X = 1, тогда и только тогда, если X =. a)пусть = 1, тогда вычислим X = X 1 = X. С другой стороны по условию X = 1. Откуда получаем, что X = 1 =. b)пусть = 0, тогда вычислим X = X 0 = X. С другой стороны по условию X = 1. Откуда получаем, что X = 1 и отсюда X = 0 =.

Теорема 3.1 Совершенная элементарная конъюнкция X 1 1 & X 2 2 & … & X n n = 1 тогда и только тогда, если X 1 = 1, X 2 = 2, …, X n = n. Определение 3.3 Совершенной элементарной конъюнкцией n-переменных X 1, X 2,..., X n называют конъюнкцию X 1 1 & X 2 2 & … & X n n, где каждая переменная X i присутствует точно один раз, i {0,1}. вычислим X 1 1 & X 2 2 & … & X n n, если X 1 = 1, X 2 = 2, …, X n = n, получим: 1 1 & 2 2 & … & n n = 1 & 1 & … & 1 = По предложению 3.1 = 1 для любого. С другой стороны, если хотя бы для одного i = 1, …, n : X i i, то 1 1 & … & i i & … & n n = 1 & … & 0 & … & 1 = По предложению 3.1 ( ) = 0 для любого. Доказательство:

Пример: пусть логическая функция имеет вид: V 1 = {(1, 0,1 )}. Замечание: если логическая функция может быть представлена в виде совершенной элементарной конъюнкции, то по совершенной элементарной конъюнкции можно найти область единиц логической функции V 1. f (X 1, X 2, X 3 ) = X 1 & X 2 &X 3 =, что равносильно = X 1 1 & X 2 0 & X 3 1, и по Теореме 3.1:

Определение 3.4 Конъюнктивной нормальной формой (КНФ) называют формулу, которая представляет собой конъюнкцию элементарных дизъюнкций. Пример: следующая логическая функция представлена в конъюнктивной нормальной форме: Каждая логическая функция представима в виде ДНФ и в виде КНФ, причем неоднозначно, т.е. для одной логической функции можно найти несколько различных ДНФ и КНФ. Замечание: Пример:

Определение 3.5 Элементарной дизъюнкцией n-переменных X 1, X 2,..., X n называют дизъюнкцию X 1 1 X 2 2 … X n n, где каждая переменная X i присутствует не более одного раза, i {0,1}. Определение 3.6 Совершенной элементарной дизъюнкцией n-переменных X 1, X 2,..., X n называют дизъюнкцию X 1 1 X 2 2 … X n n, где каждая переменная X i присутствует точно один раз, i {0,1}.

Теорема 3.2 Совершенная элементарная дизъюнкция X 1 1 X 2 2 … X n n = 0 тогда и только тогда, если X 1 1, X 2 2, … X n n. вычислим X 1 1 X 2 2 … X n n, если X 1 1, X 2 2, …, X n n, получим: … n n = 0 0 … 0 = С другой стороны, если хотя бы для одного i = 1, …, n : X i = i, то 1 1 … i i … n n = 0 … 1 … 0 = Доказательство: По предложению 3.1 ( ) = 0 для любого. По предложению 3.1 = 1 для любого.

V 0 = {(0, 0,1 )}. Замечание: если логическая функция может быть представлена в виде совершенной элементарной дизъюнкции, то по совершенной элементарной дизъюнкции можно найти область нулей логической функции V 0. Пример: пусть логическая функция имеет вид: =, что равносильно, и по Теореме 3.2:

Определение 3.7 Совершенной ДНФ (СДНФ) называют такую ДНФ, в которой длина каждой элементарной конъюнкции равна n (т.о. каждая элементарная конъюнкция содержит все аргументы логической функции, т.е. явлвется совершенной): X 1 11 & X 2 12 & … & X n 1n X 1 21 & X 2 22 & … & X n 2n … X 1 k1 & X 2 k2 & … & X n kn Пример: следующая логическая функция представлена в совершенной дизъюнктивной нормальной форме f (X 1, X 2, X 3 ) = X 1 &X 2 & X 3 X 1 & X 2 &X 3 X 1 &X 2 & X 3. Совершенной дизъюнктивной нормальной формой (СДНФ) называют формулу, которая представляет собой дизъюнкцию совершенных элементарных конъюнкций.

Доказательство: СДНФ = дизъюнкция совершенных элементарных конъюнкций = = X 1 11 & X 2 12 & … & X n 1n X 1 21 & X 2 22 & … & X n 2n... … X 1 k1 & X 2 k2 & … & X n kn = 1 тогда и только тогда, когда хотя бы одна совершенная элементарная конъюнкция равна 1, т.е. X 1 11 & X 2 12 & … & X n 1n = 1, X 1 21 & X 2 22 & … & X n 2n = 1,... X 1 k1 & X 2 k2 & … & X n kn = 1 X 1 = 11, X 2 = 12, …, X n = 1n, по Теореме 3.1 X 1 = 21, X 2 = 22, …, X n = 2n,... X 1 = k1, X 2 = k2, …, X n = kn, единственно возможные комплекты значений из области единиц, т.е. V 1 ={( 11, 12,…, 1n ), ( 21, 22,…, 2n ), …, ( k1, k2,…, kn )}.

Следствие 3.3.1: совершенные элементарные конъюнкции СДНФ логической функции находятся во взаимно-однозначном соответствии с двоичными векторами области единиц V 1 этой функции. Замечание: если логическая функция представлена в виде СДНФ, то по совершенным элементарным конъюнкциям можно найти область единиц логической функции V 1. Пример: пусть следующая логическая функция представлена в совершенной дизъюнктивной нормальной форме f (X 1, X 2, X 3 ) = X 1 &X 2 & X 3 X 1 & X 2 &X 3 X 1 &X 2 & X 3, что равносильно f (X 1, X 2, X 3 ) =X 1 0 &X 2 1 &X 3 0 X 1 1 &X 2 0 &X 3 1 X 1 1 &X 2 1 &X 3 0. И по Теореме 3.3: V 1 ={(0, 1, 0 ), (1, 0, 1), (1, 1, 0)}.

Определение 3.8 Совершенной КНФ (СКНФ) называют такую КНФ, в которой длина каждой элементарной дизъюнкции равна n (т.о. каждая элементарная дизъюнкция содержит все аргументы логической функции, т.е. явлвется совершенной): (X 1 11 X 2 12 … X n 1n ) & (X 1 21 X 2 22 … X n 2n ) &... … & (X 1 k1 X 2 k2 … X n kn ) Пример: следующая логическая функция представлена в совершенной конъюнктивной нормальной форме f (X 1, X 2, X 3 ) = ( X 1 X 2 X 3 ) & (X 1 X 2 X 3 ) Совершенной конъюнктивной нормальной формой (СКНФ) называют формулу, которая представляет собой конъюнкцию совершенных элементарных дизъюнкций.

Доказательство: СКНФ = конъюнкция совершенных элементарных дизъюнкций = = (X 1 11 X 2 12 … X n 1n ) & (X 1 21 X 2 22 … X n 2n ) &... … &( X 1 k1 X 2 k2 … X n kn ) = 0 тогда и только тогда, когда хотя бы одна совершенная элементарная дизъюнкция равна 0, т.е. X 1 11 X 2 12 … X n 1n = 0, X 1 21 X 2 22 … X n 2n = 0,... X 1 k1 X 2 k2 … X n kn = 0 X 1 11, X 2 12, …, X n 1n, по Теореме 3.2 X 1 21, X 2 22, …, X n 2n,... X 1 k1, X 2 k2, …, X n kn. Т.о. единственно возможные комплекты значений из области нулей V 0 ={(β 11, β 12,…, β 1n ), (β 21, β 22,…, β 2n ), …, (β k1, β k2,…, β kn )}, где ij ij для каждого i = 1, …, n и j = 1, …, n.

Следствие 3.4.1: совершенные элементарные дизъюнкции СКНФ логической функции находятся во взаимно- однозначном соответствии с двоичными векторами области нулей V 0 этой функции. Замечание: если логическая функция представлена в виде СКНФ, то по совершенным элементарным дизъюнкциям можно найти область нулей логической функции V 0. Пример: пусть следующая логическая функция представлена в совершенной конъюнктивной нормальной форме f (X 1, X 2, X 3 ) = ( X 1 X 2 X 3 ) & (X 1 X 2 X 3 ), что равносильно f (X 1, X 2, X 3 ) = (X 1 0 X 2 1 X 3 1 ) & (X 1 1 X 2 1 X 3 0 ). И по Теореме 3.4:V 0 ={(1, 0, 0 ), (0, 0, 1)}. Замечание: у каждой логической функции существует точно одна СДНФ и точно одна СКНФ.

Алгоритм приведения логической функции к СДНФ: 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится конъюнкция дизъюнкциий, то применить дистрибутивность 4.a) и перемножить скобки: ( ) & ( ) &...(... &... &...) (... &... &...)... 4.a) ДНФ 5. шаг: упростить по формулам 5. и шаг: для получения СДНФ добавить недостающие переменные т.о., что если в конъюнкции К отсутствует переменная Х, то для ее добавления по 4.a) К = К & (X X) = К & X К & X 7. шаг: сократить одинаковые конъюнкции по формуле 5. b). СДНФ

Пример: привести формулу к СДНФ и найти область единиц (( X 1 X 2 ) ( X 1 X 3 )) (( X 1 X 2 ) ( X 1 X 3 )) = ( ( X 1 X 2 ) ( X 1 X 3 ) ) = = ( X 1 X 2 ) & (X 1 X 3 ) = ( X 1 X 2 ) & (X 1 X 3 ) = = X 1 &X 1 X 1 &X 3 X 2 &X 1 X 2 &X 3 = X 1 &X 3 X 1 &X 2 X 2 &X 3 = добавляем переменные в ДНФ = X 1 &X 3 &(X 2 X 2 ) X 1 &X 2 &(X 3 X 3 ) X 2 &X 3 &(X 1 X 1 ) = = X 1 &X 3 &X 2 X 1 &X 3 & X 2 X 1 &X 2 &X 3 X 1 &X 2 & X 3 X 2 &X 3 &X 1 X 2 &X 3 & X 1 = X 1 &X 2 &X 3 X 1 & X 2 &X 3 X 1 &X 2 &X 3 X 1 &X 2 & X 3 8.a) 0 4.a) 6.f)6.f) Решение: 7.b) Х2Х2 Х3Х3 Х1Х1 5.b) СДНФ V 1 (X 1, X 2, X 3 ) ={(0, 1, 1 ), (0, 0, 1), (1, 1, 1), (1, 1, 0)}.

Алгоритм приведения логической функции к СКНФ: 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится дизъюнкция конъюнкциий, то применить дистрибутивность 4.b) и перемножить скобки: 4.b) КНФ 5. шаг: упростить по формулам 5. и шаг: для получения СКНФ добавить недостающие переменные т.о., что если в дизъюнкции Д отсутствует переменная Х, то для ее добавления по 4.b) Д = Д (X & X) = (Д X) & (Д X) 7. шаг: сократить одинаковые дизъюнкции по формуле 5. a). СКНФ ( ) & ( ) &...(... &... &...) (... &... &...)...

X 1 &X 2 X 1 & X 2 &X 3 Пример: привести формулу к СКНФ и найти область нулей Решение: X 1 &X 2 X 1 & X 2 &X 3 = ( X 1 X 1 ) & ( Х 1 X 2 ) & ( Х 1 X 3 ) & (Х 2 X 1 ) & & (Х 2 X 2 ) & (Х 2 X 3 ) = ( Х 1 X 2 ) & ( Х 1 X 3 ) & (Х 2 X 1 ) & (Х 2 X 3 ) = добавляем переменные в КНФ = ( Х 1 X 2 (Х 3 & X 3 )) & ( Х 1 X 3 (Х 2 & X 2 )) & (Х 2 X 1 (Х 3 & X 3 ))& & (Х 2 X 3 (Х 1 & X 1 )) = ( Х 1 X 2 Х 3 ) & ( Х 1 X 2 X 3 ) & & ( Х 1 X 3 Х 2 ) & ( Х 1 X 3 X 2 ) & (Х 2 X 1 Х 3 ) & & (Х 2 X 1 X 3 ) & (Х 2 X 3 Х 1 ) & (Х 2 X 3 X 1 ) = = ( Х 1 X 2 Х 3 )&( Х 1 X 2 X 3 )&( Х 1 X 2 Х 3 )&(Х 1 X 2 Х 3 )&(Х 1 X 2 X 3 ). ДНФ 4.b) 6.е)6.е) 6.е)6.е)1 1 Х3Х3 Х3Х3 Х2Х2 Х1Х1 5.а) СКНФ V 0 (X 1, X 2, X 3 ) ={(1, 1, 0 ), (1, 1, 1), (1, 0, 0), (0, 0, 0), (0, 0, 1)}.