Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел. 7021-446, e-mail: belous@kture.Kharkov.ua Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, - презентация

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

2 Совершенная нормальная форма Среди множества эквивалентных формул, представляющих выбранную булеву функцию f, выделяется одна формула, которая называется совершенной нормальной формой функции f, имеет регламентированную логическую структуру и однозначно определяется по функции f. 2

3 Обозначения x,σ B={0,1} 3

4 Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным Любую булеву функцию f(x 1,x 2,…,x n ) можно представить в следующей форме: 4 f(x 1,…,x k,x k+1,…,x n )= x 1 1 x 2 2 … x k k f( 1, 2,…, k,x k+1,…,x n ) ( 1, 2,…, k )

5 Теорема о дизъюнктивном разложении функции Запись означает многократную дизъюнкцию, которая берется по всем возможным наборам значений ( 1, 2,…, k ) при любом k (1kn). f( 1, 2,…, k,x k+1,…,x n ) представляет значение функции на интерпретации x 1,x 2,…,x n, когда вместо значений переменных x 1,x 2,…,x k, по которым ведется разложение, подставлены значения 1, 2,…, k. 5 ( 1, 2,…, k )

6 Пример Получить дизъюнктивное разложение функции по переменным x, z. 6 Подставим f(0,y,0,t), f(0,y,1,t), f(1,y,0,t), f(1,y,1,t) в формулу дизъюнктивного разложения

7 Дизъюнктивное разложение булевой функции f(x 1,x 2,…,x n ) по одной переменной Любую булеву функцию f(x 1,x 2,…,x n ) можно представить в следующей форме: f(x 1, x 2, …, x n )= x i σ i f(x 1, x 2, …, x i-1, i, x i+1, …, x n ) 7

8 Дизъюнктивное разложение булевой функции f(x 1,x 2,…,x n ) по всем n переменным Любую булеву функцию f(x 1,x 2,…,x n ) 0 можно представить в следующей форме: f(x 1,x 2,…,x n ) = x 1 1 x 2 2 … x n n ( 1, 2,…, n ) f( 1, 2,…, n ) = 1 8

9 Пример Получить дизъюнктивное разложение функции по всем переменным. Определим значение функции на каждой из интерпретаций: 9

10 Определения и понятия Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается не более одного раза.Примеры Элементарными конъюнкциями для функции от одной переменной могут быть y,, двух переменных y, x трех переменных x z, x, x y z. 10

11 Определения и понятия Дизъюнктивной нормальной формой (ДНФ) называется формула, представленная в виде дизъюнкции элементарных конъюнкций.Примеры: 11 f(x, y,z)= ДНФ –

12 Определения и понятия Элементарная конъюнкция x 1 1 x 2 2 … x n n называется конституентой единицы (минтермом) функции f(x 1,x 2,…,x n ), если f( 1, 2,…, n )=1, то есть интерпретация, обращающая в единицу данную элементарную конъюнкцию, обращает в единицу и функцию f. 12

13 Свойства конституенты единицы Конституента единицы функции n переменных имеет вид x 1 1 x 2 2 … x n n и соответствует интерпретации ( 1, 2,…, n ). Конституента единицы обладает следующими свойствами: Конституента единицы равна единице только на соответствующей ей интерпретации. Конституента единицы однозначно определяется номером соответствующей ей интерпретации. Конъюнкция любого числа различных конституент единицы функции равна нулю. 13

14 Определение и понятия Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула, представленная в виде дизъюнкции конституент единицы данной функции.Примеры: 14 f(x, y,z)= СДНФ ДНФ СДНФ

15 Определения и понятия Совершенной конъюнктивной нормальной формой (СКНФ) функции называется формула, представленная в виде конъюнкции конституент нуля данной функции.Примеры 15 f(x, y,z)= КНФ СКНФ

16 Следствия из определений СДНФ и СКНФ булевых функций Для каждой булевой функции f(x 1,x 2,…,x n ), не являющейся константой нуля, существует представление в виде СДНФ. Для каждой булевой функции f(x 1,x 2,…,x n ), не являющейся константой единицы, существует представление в виде СКНФ. Две различные булевы функции не могут иметь одинаковые СДНФ или СКНФ. Для каждой булевой функции f(x 1,x 2,…,x n ) существует представление в виде формулы булевой алгебры, содержащей только операции дизъюнкции, конъюнкции и отрицания. 16

17 Пример конституент 1 и конституент 0 17 xyz

18 Алгоритм перехода от таблицы истинности булевой функции к СДНФ Выделить все интерпретации ( 1, 2,…, n ), на которых значение функции равно единице. Записать конституенты единицы вида x 1 1 x 2 2 … x n n, соответствующие отмеченным интерпретациям. Получить СДНФ функции посредством соединения операцией дизъюнкции записанных конституент единицы. 18

19 Алгоритм перехода от таблицы истинности булевой функции к СДНФ. Пример Получить СДНФ для функций f 13 (x,y). f 8 (x,y) xy f 13 (x,y) Функция f 13 (x,y)

20 Алгоритм перехода от таблицы истинности булевой функции к СКНФ 1.Выделить все интерпретации ( 1, 2,…, n ), на которых значение функции равно нулю 2.Записать конституенты нуля вида, соответствующие выделенным интерпретациям. 3.Записав конъюнкцию конституент нуля, получить СКНФ функции. 20

21 Алгоритм перехода от таблицы истинности булевой функции к СКНФ Пример Получить СКНФ для функций f 7 (x,y) и f 9 (x,y). f 9 (x,y) xy f 7 (x,y)

22 Алгоритм построения таблицы истинности функции, заданной СДНФ 1.Построить таблицу истинности, содержащую 2 n интерпретаций вида ( 1, 2,…, n ). 2.Отметить в таблице истинности все интерпретации ( 1, 2,…, n ), соответствующие конституентам единицы вида из заданной СДНФ. 3.Напротив выделенных интерпретаций в столбец значения функции записать единицы. 4.Напротив оставшихся интерпретаций в столбец значения функции записать нули. 22

23 Алгоритм перехода от произвольной формулы алгебры логики к СДНФ 1.Исключить константы, используя законы действий с константами. 2.Опустить знаки отрицания непосредственно на переменные, используя законы де Моргана. 3.Используя дистрибутивный закон, раскрыть скобки. К полученным элементарным конъюнкциям применить законы идемпотентности и противоречия, упростить их и привести подобные. Результатом выполнения указанных действий является получение ДНФ булевой функции. 23

24 Алгоритм перехода от произвольной формулы алгебры логики к СДНФ. Продолжение 4.Построить конституенты единицы функции, введением в каждую элементарную конъюнкцию недостающих переменных, используя закон исключенного третьего. 5.С помощью дистрибутивного закона раскрыть скобки и привести подобные, используя закон идемпотентности 6.Полученная формула соответствует СДНФ функции. 24

25 Примеры Пример 1. Переход от СДНФ к таблице истинности Пример 2. Переход от СКНФ к таблице истинности 25