Обычные формы

Обычные формы — в математике и информатике способ представления математических выражений, логических формул, графов или других структур данных, при котором они приводятся к единому стандартному виду. Обычные формы используются для упрощения анализа, сравнения, минимизации и оптимизации объектов, а также для обеспечения однозначности их записи. В зависимости от области применения различают обычные формы для логических выражений (дизъюнктивные и конъюнктивные), для графов (канонические формы), для чисел (стандартная форма записи) и для баз данных (нормальные формы).

История

Понятие обычной формы восходит к работам по математической логике XIX века. Джордж Буль в своих трудах «Математический анализ логики» (1847) и «Исследование законов мышления» (1854) заложил основы булевой алгебры, в которой впервые были формализованы дизъюнктивные и конъюнктивные нормальные формы. В 1920-х годах Эмиль Пост и другие логики развили теорию нормальных форм для исчисления высказываний.

В середине XX века, с развитием компьютерных наук, обычные формы стали применяться в теории автоматов, компиляторах и базах данных. Эдгар Кодд в 1970 году предложил реляционную модель данных и ввёл понятие нормальных форм (первая, вторая, третья и т. д.) для устранения избыточности и аномалий при операциях с данными. В теории графов канонические формы стали использоваться для проверки изоморфизма графов и их классификации.

Классификация обычных форм

Обычные формы классифицируются по области применения и типу объектов, которые они нормализуют.

Логические обычные формы

В булевой алгебре и цифровой логике выделяют две основные обычные формы:

• Дизъюнктивная нормальная форма (ДНФ) — логическое выражение, представленное в виде дизъюнкции (логического «ИЛИ») одного или нескольких конъюнктов (логических «И»). Каждый конъюнкт содержит литералы (переменные или их отрицания). Пример: \((x \land y) \lor (\lnot x \land z)\).
• Конъюнктивная нормальная форма (КНФ) — логическое выражение, представленное в виде конъюнкции (логического «И») одного или нескольких дизъюнктов (логических «ИЛИ»). Пример: \((x \lor y) \land (\lnot x \lor z)\).

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

Нормальные формы в базах данных

В реляционных базах данных нормальные формы (НФ) определяют требования к структуре таблиц для минимизации избыточности и аномалий обновления. Основные нормальные формы:

• Первая нормальная форма (1НФ) — каждая ячейка таблицы содержит только атомарное (неделимое) значение, а все записи в столбце имеют одинаковый тип данных.
• Вторая нормальная форма (2НФ) — таблица находится в 1НФ, и каждый неключевой атрибут функционально полно зависит от первичного ключа (отсутствие частичной зависимости).
• Третья нормальная форма (3НФ) — таблица находится в 2НФ, и каждый неключевой атрибут нетранзитивно зависит от первичного ключа (отсутствие транзитивной зависимости).
• Нормальная форма Бойса — Кодда (НФБК) — усиленная версия 3НФ, в которой каждая детерминанта является потенциальным ключом.
• Четвёртая нормальная форма (4НФ) — таблица находится в НФБК и не содержит многозначных зависимостей, не являющихся функциональными.
• Пятая нормальная форма (5НФ) — таблица находится в 4НФ и не содержит зависимостей соединения, не являющихся ключевыми.

Нормальные формы применяются при проектировании баз данных для обеспечения целостности и эффективности запросов.

Канонические формы в теории графов

В теории графов обычные формы (канонические) используются для однозначного представления графов с точностью до изоморфизма. Примеры:

• Каноническая форма графа — уникальная нумерация вершин, при которой матрица смежности или список рёбер принимает стандартный вид. Алгоритмы вычисления канонической формы (например, алгоритм Маккея) применяются для проверки изоморфизма графов.
• Нормальная форма дерева — для корневых деревьев существует каноническая форма, основанная на лексикографическом порядке поддеревьев. Используется в комбинаторике и биоинформатике для классификации филогенетических деревьев.

Стандартная форма записи чисел

В математике и физике обычная форма (стандартная, или научная) используется для записи очень больших или очень малых чисел. Число представляется в виде \(a \times 10^n\), где \(1 \leq |a| < 10\) и \(n\) — целое число. Например, \(3,14 \times 10^5\) (стандартная форма числа 314000). Эта форма упрощает сравнение и арифметические операции с числами разного порядка.

Применение обычных форм

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

В цифровой электронике

В проектировании цифровых схем ДНФ и КНФ используются для синтеза комбинационных логических схем. Алгоритмы минимизации (например, карты Карно или метод Куайна — Мак-Класки) позволяют уменьшить количество логических элементов, что снижает стоимость и энергопотребление устройств.

В компиляторах и верификации

В компиляторах обычные формы применяются для оптимизации кода. Например, приведение выражений к нормальной форме позволяет обнаруживать общие подвыражения и устранять избыточные вычисления. В верификации программ и аппаратуры КНФ используется для кодирования задач выполнимости (SAT), которые решаются SAT-солверами для проверки корректности схем.

В базах данных

Нормальные формы являются основой реляционного проектирования. Приведение таблиц к 3НФ или НФБК позволяет избежать аномалий вставки, обновления и удаления данных, а также уменьшить объём хранимой информации за счёт устранения дублирования.

В теории алгоритмов и графов

Канонические формы графов используются в задачах распознавания изоморфизма, в химической информатике для представления молекулярных структур (например, SMILES — каноническая форма записи молекул), а также в анализе социальных сетей.

Критика и ограничения

Несмотря на широкое применение, обычные формы имеют ограничения. В логике приведение выражений к ДНФ или КНФ может привести к экспоненциальному росту размера формулы (проблема взрыва). В базах данных строгая нормализация может увеличить количество таблиц и усложнить запросы, что иногда снижает производительность. В теории графов вычисление канонической формы для больших графов может быть вычислительно сложным (NP-трудным в общем случае). Поэтому на практике часто используют приближённые или эвристические методы.

Интересные факты

• В 1970-х годах для решения задачи выполнимости в КНФ был разработан алгоритм DPLL (Дэвис — Патнем — Ловленд — Логеман), ставший основой современных SAT-солверов.
• В реляционных базах данных существует более десяти нормальных форм, включая доменно-ключевую нормальную форму (ДКНФ) и шестую нормальную форму (6НФ), используемую в темпоральных базах данных.
• Каноническая форма графа применяется в программе nauty (nauty and Traces), которая используется для генерации и классификации графов в математических исследованиях.

Источники

• Буль, Дж. «Математический анализ логики» (1847).
• Кодд, Э. Ф. «A Relational Model of Data for Large Shared Data Banks» (1970).
• Маккей, Б. Д. «Practical Graph Isomorphism» (1981).
• Хопкрофт, Дж., Мотвани, Р., Ульман, Дж. «Введение в теорию автоматов, языков и вычислений» (2001).
• Кнут, Д. Э. «Искусство программирования», том 4А (2011).