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

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

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

Теорема о дизъюнктивном разложении функции 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 )

Теорема о дизъюнктивном разложении функции Запись означает многократную дизъюнкцию, которая берется по всем возможным наборам значений ( 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 )

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

Дизъюнктивное разложение булевой функции 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

Дизъюнктивное разложение булевой функции 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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