лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 33 из 40

Дизъюнктивная нормальная форма.

Элементарной конъюнкцией называется такая формула A, которая является конъюнкцией, возможно одночленной, переменных и их отрицаний. Говорят, что формула A находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией, возможно одночленной, элементарных конъюнкций. ДНФ: A = x₁  · x₂  x₁ · .

Теорема о приведении формулы к ДНФ. AB, находящаяся в ДНФ, что A  B. Bназывается ДНФ А.

Доказательство: В качестве доказательства приводят алгоритм построения ДНФ формулы А.

1. С помощью основных равносильностей, которые позволяют устранить операции импликации и эквивалентности, строят . При этом А₁ не содержит операций импликации и эквивалентности.

Основные равносильности:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8)

2. От А₁ переходят к А₂, в которой отрицание только перед переменной 1) A₁  A

2)

Полученная А₂ равносильна А и состоит из многочисленных конъюнкций и дизъюнкций. К А₂ применяют формулу дистрибутивности конъюнкции относительно дизъюнкции. Получим А₃, находящуюся в дизъюнктивной нормальной форме.

Рассмотрим конъюнкцию х₁^σ, х₂^σ2, ... , х_n^σn (1).

Конъюнкция (1) называется конституентной единицей.

Теорема. f(х₁, х₂,…, х_n) может быть представлена в виде дизъюнкций конституент 1. На любом наборе f(х₁, х₂,…, х_n)=1 будет равна 1 и только одна конституента. Дизъюнкция конституент равна 1, если 1 равна хотя бы 1 конституента.

Пример

х1	х2	х3	f1(х1, х2, х3)	f2(х1, х2, х3)
0	0	0	1	0
0	0	1	0	0
0	1	0	0	1
0	1	1	1	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

f₁(х₁, х₂, х₃)= _{1 3}  ₁ x₂ x₃ x₁ x₃x₁x_{2 3}.

f₂(х₁, х₂, х₃)= ₁x_{2 3}  ₁ x₂ x₃ x₁ x₃x₁x₂х₃.

Всякую конъюнкцию переменных функций функций, взятых с отрицанием, называют элементарной дизъюнкцией. Дизъюнкцию элементарных конъюнкций называют дизъюнктивной элементарной формой.