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

Сентябрь 13, 2022

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

Содержание

2. Совершенная нормальная форма Среди множества эквивалентных формул, представляющих выбранную булеву функцию f, выделяется одна формула, которая
3. Обозначения x,σ∈B={0,1}
4. Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным Любую булеву функцию f(x1,x2,…,xn) можно представить в
5. Теорема о дизъюнктивном разложении функции Запись означает многократную дизъюнкцию, которая берется по всем возможным наборам значений
6. Пример Получить дизъюнктивное разложение функции по переменным x, z. Подставим f(0,y,0,t), f(0,y,1,t), f(1,y,0,t), f(1,y,1,t) в формулу
7. Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по одной переменной Любую булеву функцию f(x1,x2,…,xn) можно представить в следующей
8. Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по всем n переменным Любую булеву функцию f(x1,x2,…,xn)≠0 можно представить в
9. Пример Получить дизъюнктивное разложение функции по всем переменным. Определим значение функции на каждой из интерпретаций:
10. Определения и понятия Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых с отрицанием или без
11. Определения и понятия Дизъюнктивной нормальной формой (ДНФ) называется формула, представленная в виде дизъюнкции элементарных конъюнкций. Примеры:
12. Определения и понятия Элементарная конъюнкция x1σ1∧x2σ2∧… ∧xnσn называется конституентой единицы (минтермом) функции f(x1,x2,…,xn), если f(σ1,σ2,…,σn)=1, то
13. Свойства конституенты единицы Конституента единицы функции n переменных имеет вид x1σ1∧x2σ2∧…∧xnσn и соответствует интерпретации (σ1,σ2,…,σn). Конституента
14. Определение и понятия Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула, представленная в виде дизъюнкции
15. Определения и понятия Совершенной конъюнктивной нормальной формой (СКНФ) функции называется формула, представленная в виде конъюнкции конституент
16. Следствия из определений СДНФ и СКНФ булевых функций Для каждой булевой функции f(x1,x2,…,xn), не являющейся константой
17. Пример конституент 1 и конституент 0 x y z
18. Алгоритм перехода от таблицы истинности булевой функции к СДНФ Выделить все интерпретации (σ1,σ2,…,σn), на которых значение
19. Алгоритм перехода от таблицы истинности булевой функции к СДНФ. Пример Получить СДНФ для функций f13(x,y). Функция
20. Алгоритм перехода от таблицы истинности булевой функции к СКНФ Выделить все интерпретации (σ1,σ2,…,σn), на которых значение
21. Алгоритм перехода от таблицы истинности булевой функции к СКНФ Пример Получить СКНФ для функций f7(x,y) и
22. Алгоритм построения таблицы истинности функции, заданной СДНФ Построить таблицу истинности, содержащую 2n интерпретаций вида (σ1,σ2,…,σn). Отметить
23. Алгоритм перехода от произвольной формулы алгебры логики к СДНФ Исключить константы, используя законы действий с константами.
24. Алгоритм перехода от произвольной формулы алгебры логики к СДНФ. Продолжение Построить конституенты единицы функции, введением в
26. Скачать презентацию

Слайд 2

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

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

Слайд 3

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

Слайд 4

Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным
Любую булеву функцию

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)

Слайд 5

Теорема о дизъюнктивном разложении функции
Запись означает многократную дизъюнкцию, которая берется по

всем возможным наборам значений (σ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 )

Слайд 6

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

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

Слайд 7

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по одной переменной
Любую булеву функцию f(x1,x2,…,xn)

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

Слайд 8

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по всем n переменным
Любую булеву функцию

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

Слайд 9

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

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

Слайд 10

Определения и понятия
Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых

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

Слайд 11

Определения и понятия
Дизъюнктивной нормальной формой (ДНФ) называется формула, представленная в виде

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

f(x, y,z)=

ДНФ

–

ДНФ

Слайд 12

Определения и понятия
Элементарная конъюнкция x1σ1∧x2σ2∧… ∧xnσn называется конституентой единицы (минтермом) функции

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

Слайд 13

Свойства конституенты единицы
Конституента единицы функции n переменных имеет вид x1σ1∧x2σ2∧…∧xnσn и

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

Слайд 14

Определение и понятия
Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула,

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

f(x, y,z)=

СДНФ

ДНФ

СДНФ

Слайд 15

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

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

f(x, y,z)=

КНФ

СКНФ

Слайд 16

Следствия из определений СДНФ и СКНФ булевых функций
Для каждой булевой

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

Слайд 17

Пример конституент 1 и конституент 0
x
y
z

Слайд 18

Алгоритм перехода от таблицы истинности булевой функции к СДНФ
Выделить все интерпретации

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

Слайд 19

Алгоритм перехода от таблицы истинности булевой функции к СДНФ. Пример
Получить СДНФ

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

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

Слайд 20

Алгоритм перехода от таблицы истинности булевой функции к СКНФ
Выделить все интерпретации

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

Слайд 21

Алгоритм перехода от таблицы истинности булевой функции к СКНФ
Пример
Получить СКНФ для

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

Слайд 22

Алгоритм построения таблицы истинности функции, заданной СДНФ
Построить таблицу истинности, содержащую 2n

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

Слайд 23

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ
Исключить константы, используя

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

Слайд 24

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ. Продолжение
Построить конституенты

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

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

Содержание

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

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

Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменнымЛюбую булеву функцию

Теорема о дизъюнктивном разложении функцииЗапись означает многократную дизъюнкцию, которая берется по

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

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по одной переменнойЛюбую булеву функцию f(x1,x2,…,xn)

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по всем n переменнымЛюбую булеву функцию

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

Определения и понятия Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых

Определения и понятия Дизъюнктивной нормальной формой (ДНФ) называется формула, представленная в виде

Определения и понятияЭлементарная конъюнкция x1σ1∧x2σ2∧… ∧xnσn называется конституентой единицы (минтермом) функции

Свойства конституенты единицыКонституента единицы функции n переменных имеет вид x1σ1∧x2σ2∧…∧xnσn и

Определение и понятияСовершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула,

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

Следствия из определений СДНФ и СКНФ булевых функций Для каждой булевой

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

Алгоритм перехода от таблицы истинности булевой функции к СДНФВыделить все интерпретации

Алгоритм перехода от таблицы истинности булевой функции к СДНФ. ПримерПолучить СДНФ

Алгоритм перехода от таблицы истинности булевой функции к СКНФВыделить все интерпретации

Алгоритм перехода от таблицы истинности булевой функции к СКНФПримерПолучить СКНФ для

Алгоритм построения таблицы истинности функции, заданной СДНФПостроить таблицу истинности, содержащую 2n

Алгоритм перехода от произвольной формулы алгебры логики к СДНФИсключить константы, используя

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ. ПродолжениеПостроить конституенты

Похожие презентации

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

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

Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным
Любую булеву функцию

Теорема о дизъюнктивном разложении функции
Запись означает многократную дизъюнкцию, которая берется по

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

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по одной переменной
Любую булеву функцию f(x1,x2,…,xn)

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по всем n переменным
Любую булеву функцию

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

Определения и понятия
Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых

Определения и понятия
Дизъюнктивной нормальной формой (ДНФ) называется формула, представленная в виде

Определения и понятия
Элементарная конъюнкция x1σ1∧x2σ2∧… ∧xnσn называется конституентой единицы (минтермом) функции

Свойства конституенты единицы
Конституента единицы функции n переменных имеет вид x1σ1∧x2σ2∧…∧xnσn и

Определение и понятия
Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула,

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

Следствия из определений СДНФ и СКНФ булевых функций
Для каждой булевой

Пример конституент 1 и конституент 0
x
y
z

Алгоритм перехода от таблицы истинности булевой функции к СДНФ
Выделить все интерпретации

Алгоритм перехода от таблицы истинности булевой функции к СДНФ. Пример
Получить СДНФ

Алгоритм перехода от таблицы истинности булевой функции к СКНФ
Выделить все интерпретации

Алгоритм перехода от таблицы истинности булевой функции к СКНФ
Пример
Получить СКНФ для

Алгоритм построения таблицы истинности функции, заданной СДНФ
Построить таблицу истинности, содержащую 2n

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ
Исключить константы, используя

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ. Продолжение
Построить конституенты