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

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

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

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

Теорема о приведении к КНФ. AB  A, находящаяся в КНФ. Bназывается КНФ А.

Доказательство: Аналогично теореме 1. Применяют обобщенные законы Де Моргана, чтобы привести операции отрицания к переменным. Применяют формулы дистрибутивности дизъюнкции относительно конъюнкции. A₃  A и находится в КНФ.
Найдем КНФ для функций:

х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₁(х₁, х₂, х₃)= (х₁х₂ ₃ ) ( х₁  x₃ ) ( ₁х₂x₃ ) ( ₁ ₃ )
f₂(х₁, х₂, х₃)= (х₁х₂ x₃) ( х₁  x₃ ) ( ₁х₂x₃ ) ( ₁x₃)

Тема 19. Неполностью определенные (частные) ПФ. Минимизация ПФ и неполностью определенных ПФ.