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

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

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

3 Доказательство: Определение 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 =.

4 Теорема 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 для любого. Доказательство:

5 Пример: пусть логическая функция имеет вид: 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:

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

7 Определение 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}.

8 Теорема 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 для любого.

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

10 Определение 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. Совершенной дизъюнктивной нормальной формой (СДНФ) называют формулу, которая представляет собой дизъюнкцию совершенных элементарных конъюнкций.

11 Доказательство: СДНФ = дизъюнкция совершенных элементарных конъюнкций = = 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 )}.

12 Следствие 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)}.

13 Определение 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 ) Совершенной конъюнктивной нормальной формой (СКНФ) называют формулу, которая представляет собой конъюнкцию совершенных элементарных дизъюнкций.

14 Доказательство: СКНФ = конъюнкция совершенных элементарных дизъюнкций = = (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.

15 Следствие 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)}. Замечание: у каждой логической функции существует точно одна СДНФ и точно одна СКНФ.

16 Алгоритм приведения логической функции к СДНФ: 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). СДНФ

17 Пример: привести формулу к СДНФ и найти область единиц (( 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)}.

18 Алгоритм приведения логической функции к СКНФ: 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). СКНФ ( ) & ( ) &...(... &... &...) (... &... &...)...

19 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)}.