Компьютерная дискретная математика. Нормальные формы презентация

компьютерных наук
Кафедра ПО ЭВМ, ХНУРЭ

Компьютерная дискретная математика

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

f(x1,x2,…,xn) можно представить в следующей форме:

f(x1,…,xk,xk+1,…,xn)=
∨x1σ1∧x2σ2∧…∧xkσk∧f(σ1,σ2,…,σk,xk+1,…,xn)

(σ1,σ2,…,σk)

дизъюнкцию, которая берется по всем возможным наборам значений (σ1,σ2,…,σk) при любом k (1≤k≤n).

f(σ1,σ2,…,σk,xk+1,…,xn) представляет значение функции на интерпретации x1,x2,…,xn, когда вместо значений переменных x1,x2,…,xk, по которым ведется разложение, подставлены значения σ1,σ2,…,σk.

∨
(σ1,σ2,…,σk )

f(1,y,1,t) в формулу дизъюнктивного разложения

можно представить в следующей форме:
f(x1, x2, …, xn)=∨xiσi ∧f(x1, x2, …, xi-1, σi, xi+1, …, xn)

f(x1,x2,…,xn)≠0 можно представить в следующей форме:
f(x1,x2,…,xn) = ∨ x1σ1∧x2σ2∧… ∧xnσn
(σ1,σ2,…,σn)
f(σ1,σ2,…,σn) = 1

из интерпретаций:

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

дизъюнкции элементарных конъюнкций.
Примеры:

f(x, y,z)=

f(x, y,z)=

f(x, y,z)=

ДНФ

–

ДНФ

единицы (минтермом) функции f(x1,x2,…,xn), если f(σ1,σ2,…,σn)=1, то есть интерпретация, обращающая в единицу данную элементарную конъюнкцию, обращает в единицу и функцию f.

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

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

f(x, y,z)=

f(x, y,z)=

f(x, y,z)=

СДНФ

ДНФ

СДНФ

в виде конъюнкции конституент нуля данной функции.
Примеры

f(x, y,z)=

f(x, y,z)=

f(x, y,z)=

КНФ

СКНФ

СКНФ

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

(σ1,σ2,…,σn), на которых значение функции равно единице.
Записать конституенты единицы вида x1σ1∧x2σ2∧…∧xnσn, соответствующие отмеченным интерпретациям.
Получить СДНФ функции посредством соединения операцией дизъюнкции записанных конституент единицы.

для функций f13(x,y).

Функция f13(x,y)

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

функций f7(x,y) и f9(x,y).

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

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

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

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