Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 В отличие от ученых из других научных сфер, математики часто не задумываются о практическом применении того или иного знания. Обычно они ставят теоретические вопросы и находят ответы на них.

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

3 Как и математика, логика зачастую не имеет практического применения - например, сложно представить практическое применение форм в логике, которые мы изучим сегодня.

4 Тем не менее пропустить эту тему нельзя. Формы позволят решать задачи минимизации булевых функций и оптимизации на графах, которые мы будем рассматривать в других курсах по математике.

5 <h2>Формы в логике</h2>

6 Ранее в курсе мы научились определять истинность формул двумя способами:

7 <ul><li>Через таблицу истинности</li>

8 <li>Через доказательство с помощьюmodus ponens</li>

9 </ul>Эти способы помогают нам доказать общезначимые формулы. Попробуем усложнить задачу и проверить, можно ли доказать общезначимую формулу из аксиом. Чтобы это сделать, нам нужно обратиться к нормальной форме.

10 В математической логике формулы могутиметь нормальную форму- это значит, что их можно приводить к простейшему виду с помощью эквивалентных преобразований. Другими словами, каждую формулу можно привести к нормальной форме - и тогда нам будет проще доказывать.

11 В этом уроке мы изучим четыре типа нормальных форм:

12 <ul><li>Дизъюнктивная нормальная форма (ДНФ)</li>

13 <li>Полная дизъюнктивная нормальная форма (ПДНФ)</li>

14 <li>Конъюнктивная нормальная форма (КНФ)</li>

15 <li>Полная конъюнктивная нормальная форма (ПКНФ)</li>

16 </ul>В разных источниках полные формы иногда называют совершенными: тогда используются сокращения СДНФ и СКНФ. Между полными и совершенными формами нет никакой разницы - это один и тот же термин.

17 <h3>Дизъюнктивная нормальная форма (ДНФ)</h3>

18 Дизъюнктивная нормальная форма (ДНФ)- это нормализация логической формулы в булевой математике. Любую логическую формулу можно преобразовать в ДНФ. При этом изначальная формула и ее ДНФ будут эквивалентны.

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

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

21 Логическая формула находится в дизъюнктивной нормальной форме только при таких условиях: если существует чередование одной или нескольких конъюнкций одного или нескольких литералов.

22 Есть еще несколько способов получить дизъюнктивную нормальную форму для логических формул:

23 <ul><li>Метод таблицы истинности</li>

24 <li>Метод деревьев истинности</li>

25 <li>Таблица логических эквивалентностей</li>

26 </ul>Дизъюнктивная нормальная форма помогает автоматически доказывать теоремы. Это один из важных процессов в разработке и верификации интегральных схем, а еще в теории искусственного интеллекта.

27 <h3>Полная дизъюнктивная нормальная форма (ПДНФ)</h3>

28 У ДНФ есть еще и полная версия.Полная дизъюнктивная нормальная форма- это формула ДНФ, в которой все задействованные переменные представлены только один раз в каждом предложении.

29 Обратите внимание, что у функции может быть только одна ПДНФ. Это упрощает доказательство и снижает вероятность ошибок. Если есть всего один верный ответ, его намного легче проверить.

30 ПДНФ относится к сумме произведений. Например:

31 <ul><li>P, Q, R - переменные</li>

32 <li>(P ∧ ¬Q ∧ ¬R) ∨ (P ∧ ¬Q ∧ R) ∨ ( ¬P ∧ ¬Q ∧ ¬R) - пример выражения в ПДНФ</li>

33 <li>∨ - основной оператор (сумма)</li>

34 </ul>Чтобы не запутаться, рассмотрим основное отличие между ДНФ и ПДНФ:

35 <ul><li>ДНФ- длина всех переменных в выражении может быть разной</li>

36 <li>ПДНФ- длина всех переменных в выражении должна быть одинаковой</li>

37 </ul>Посмотрим на еще двух примерах:

38 <ul><li>Выражение в ДНФ, которое не считается ПДНФ из-за разной длины переменных:</li>

39 </ul><ul><li>Выражение в ДНФ и ПДНФ одновременно:</li>

40 </ul>(P ∧ ` ¬Q ∧ R) ∨ ( ¬P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R)

41 <h3>Конъюнктивная нормальная форма (КНФ)</h3>

42 В логике есть терминклауза(иликлаузула) - это формальная запись доказываемого предложения. Введем это понятие, чтобы отличать объектные высказывания от субъектных.

43 Для начала вспомним, что в булевой алгебре сложение и умножение - это симметричные операции. Это значит, что всегда можно интерпретировать сложение как умножение, а умножение как сложение. Потому и существует КНФ - форма, симметричная для ДНФ. Как и ДНФ, КНФ полезна для автоматизированного доказательства теорем.

44 Конъюнктивная нормальная форма (КНФ)- это подход к булевой логике, который выражает формулы в виде конъюнкции клаузул с оператором AND или OR. Каждая клауза соединена конъюнкцией (оператором AND) и при этом должна либо быть литералом, либо содержать дизъюнкцию (оператор OR).

45 Другими словами, конъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из произведения элементарных произведений. Например:

46 В конъюнктивной нормальной форме высказывания в булевой логике представляют собой конъюнкцию клаузул с клаузулами дизъюнкции. Проще говоря, высказывание - это серия OR, соединенных AND, как в примере ниже:

47 (A OR B) AND (C OR D) (A OR B) AND (¬C OR B)

48 <h3>Полная конъюнктивная нормальная форма (ПКНФ)</h3>

49 ПКНФ относится к продукту сумм. Например:

50 <ul><li>P, Q, R - переменные</li>

51 <li>((P ∨ ¬Q ∨ ¬R) ∧ (P ∨ ¬Q ∨ R) ∧ ( ¬P ∨ ¬Q ∨ ¬R) - пример выражения в ПКНФ</li>

52 <li>∧ - это основной оператор (произведение)</li>

53 </ul>Снова рассмотрим основные отличия между формами:

54 <ul><li>КНФ- длина всех переменных в выражении может быть разной</li>

55 <li>ПКНФ- длина всех переменных в выражении должна быть одинаковой</li>

56 </ul>Например:

57 <ul><li>Выражение в КНФ, но не в ПКНФ: (P ∨ ¬Q∨ R)∧( ¬P∨ Q ∨ R)∧(P ∨ Q).</li>

58 <li>Выражение в КНФ и ПКНФ одновременно: (P ∨ ¬Q∨ R)∧( ¬P∨ Q ∨ R)∧(P ∨ Q ∨ ¬R).</li>

59 </ul><h2>Выводы</h2>

60 В этом уроке мы изучили основные свойства ПКНФ и ПДНФ:

61 <ol><li>Каждая ПДНФ или ПКНФ соответствует уникальному булеву выражению и наоборот.</li>

62 <li>Если X и Y - два булевых выражения, то X эквивалентно Y только тогда, когда ПДНФ(X) = ПДНФ(Y) или ПКНФ(X) = ПКНФ(Y).</li>

63 <li>Если ПКНФ имеет m членов и ПДНФ имеет n членов, то количество переменных в булевом выражении log₂(m ⋅ n).</li>

64 </ol>