Нормальные формы
Общие сведения
Нормальные формы в дискретной математике и математической логике представляют собой стандартизированный способ записи логических формул. Главной целью преобразования любой формулы в нормальную форму является ее упрощение и приведение к виду, позволяющему избежать построения громоздких таблиц истинности. Приведение формулы к нормальной форме дает возможность визуально и быстро определять ее базовые свойства, в частности, устанавливать, является ли формула тождественно истинной или тождественно ложной. В академической литературе применяются специфические системы обозначений для дополнительного упрощения записи. Например, вместо стандартного знака отрицания может использоваться написание единицы или нуля над переменной, где ноль обозначает отрицание, а единица утверждение, при этом знак конъюнкции часто опускается для компактности восприятия.
Теоретические основы
Возможность преобразования любой произвольной логической формулы в нормальную форму базируется на фундаментальных свойствах логических операций. Все возможные бинарные логические операции, которых насчитывается шестнадцать, могут быть выражены через базовую совокупность трех основных операций: конъюнкции, дизъюнкции и отрицания. Такие операции, как импликация или различные штрихи, устраняются путем равносильных преобразований и замены на комбинации базовых логических связок. Теоретический фундамент данных преобразований строго опирается на законы классической аристотелевской логики, имеющей бинарную природу. Фундаментальные законы, такие как закон исключенного третьего и закон непротиворечия, постулируют, что объект либо обладает свойством, либо не обладает им, и одновременное существование взаимоисключающих состояний невозможно.
Основные определения и свойства
Базовыми элементами для построения нормальных форм выступают литералы, которые определяются как логические переменные, взятые с утверждением или с отрицанием. Элементарная конъюнкция представляет собой формулу, состоящую исключительно из литералов, соединенных операцией конъюнкции, при этом одна и та же переменная может встречаться в ней многократно. Аналогичным образом, элементарная дизъюнкция является формулой, в которой литералы соединены исключительно операцией дизъюнкции. Дизъюнктивная нормальная форма определяется как дизъюнкция элементарных конъюнкций. Конъюнктивная нормальная форма, напротив, представляет собой конъюнкцию элементарных дизъюнкций. Особый класс составляют совершенные нормальные формы. Совершенная дизъюнктивная нормальная форма требует, чтобы каждая переменная логической функции входила в каждую элементарную конъюнкцию ровно один раз. Для совершенной конъюнктивной нормальной формы действует аналогичное правило: каждая переменная должна входить в каждую элементарную дизъюнкцию ровно один раз.
Практическое применение
На практике нормальные формы применяются для прямого вычисления тождественной истинности или тождественной ложности логических выражений. Конъюнктивная нормальная форма является тождественно истинной в том случае, если каждая элементарная дизъюнкция в ее составе содержит переменную вместе с ее отрицанием. Это базируется на принципе, согласно которому выражение, состоящее из переменной или ее отрицания, всегда принимает истинное значение. Дизъюнктивная нормальная форма признается тождественно ложной, если каждая элементарная конъюнкция одновременно включает переменную и ее отрицание, поскольку переменная не может быть истинной и ложной одновременно. Совершенные нормальные формы активно используются при построении логических формул на основе заданных таблиц истинности. Согласно теоремам алгебры логики, если булева функция не равна тождественно нулю, она всегда может быть представлена в виде совершенной дизъюнктивной нормальной формы. Если же функция не равна тождественно единице, ее можно представить в виде совершенной конъюнктивной нормальной формы.
Особенности и характеристики
Наряду с классическими дизъюнктивными и конъюнктивными формами, в дискретной математике выделяется представление функций в виде полинома Жегалкина. Полином Жегалкина представляет собой логическую формулу, элементы которой объединены знаком суммы по модулю два. Ключевой особенностью полинома Жегалкина является полное отсутствие операции отрицания, однако в его составе допускается использование констант. Любую булеву функцию можно преобразовать в полином Жегалкина с помощью равносильных преобразований, причем этот процесс часто осуществляется путем предварительного перевода функции в совершенную дизъюнктивную нормальную форму. Несмотря на то, что представления в виде полиномов Жегалкина зачастую оказываются более длинными и громоздкими по сравнению со стандартными нормальными формами, они предоставляют строгий математический аппарат для оценки истинности и ложности сложных логических функций.