ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ НОРМАЛЬНЫЕ ФОРМЫ

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

В логике предикатов употребляются еще предваренные нормальные формы и нормальные формы Сколема. Формулу наз. предваренной нормальной формой, если все кванторы, встречающиеся в ней, выписаны впереди, а

подкванторная часть имеет вид дизъюнктивной или конъюнктивной нормальной формы, напр.,

Для каждой ф-лы алгебры логики и логики предикатов существует эквивалентная ей (т. е. принимающая одинаковые с ней значения при одинаковых значениях переменных) нормальная форма. Формула наз. нормальной формой Сколема (по фамилии норв. математика Т. Сколема), если она имеет вид предваренной нормальной формы и все кванторы существования, если они есть, предшествуют всем кванторам общности. В логике предикатов не для всякой ф-лы существует эквивалентная нормальная форма Сколема, но для всякой ф-лы существует дедуктивно эквивалентная нормальная форма Сколема. Для исчисления предикатов понятия «эквивалентные формулы» и «дедуктивно эквивалентные формулы» не равнозначны. Две формулы 21 и дедуктивно эквивалентными, если из аксиом исчисления предикатов посредством правил вывода можно вывести и наоборот, из аксиом и формулы можно вывести Очевидно, что эквивалентные ф-лы являются дедуктивно эквивалентными, но не наоборот.

Л. в. н. ф. чрезвычайно удобны при постановке и решении различных проблем логики математической и ее приложений.

Лит.: Новиков П. С. Элементы математической логики. М., 1973. М. И. Кратко.