1.3 Нормальные формы

Метод нуля и единицы удовлетворительно работает, пока дело касается формул, содержащих не более трех-четырех переменных. Однако, когда их число возрастает, применение этого метода существенно осложняется: при шести переменных таблица истинности формулы состоит из 64 строк, при 10 она уже разрастается до 1024. Между тем, теория должна располагать методикой, позволяющей определять семантические значения в принципе даже при неограниченном числе переменных. Приходится поэтому искать дополнительные методы разрешения. К числу таковых относится сведение к так называемым нормальным формам[[Если этот раздел покажется трудным, то его можно не изучать. На уяснение последующего материала это не повлияет.]. Когда это достигается, то тогда по одной лишь структуре формулы удается определить ее семантику. Правда, при этом устанавливается только тип формулы: дает ли она при всех наборах переменных только истинные высказывания или только ложные, или среди них есть то и другое.

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

К элементарным конъюнкциям относятся выражения вида

Здесь под a_i понимается любое высказывание.

Так, формула не является элементарной конъюнкцией, поскольку в ней есть отрицание над скобкой. Элементарная конъюнкция допускает отрицания только над переменными. Примечательной особенностью таких формул является то, что содержащаяся в них мысль может быть истинной только при условии, что все до единого простые суждения, совокупность которых ее выражает, являются истинными; достаточно вставить хотя бы один ложный конъюнкт, и все выражение станет обязательно ложным, сколько бы там ни содержалось помимо него истинных высказываний в качестве конъюнктов. Причем в такой интерпретации элементарных конъюнкций нет никакой натяжки или упрощения. В практической деятельности мы именно так и относимся к какой-либо информации, если она изложена как соединение через союз “и” нескольких предложений. Допустим, у нас имеется утверждение: “Вводится дополнительный налог на импорт изделий из стекла, хрусталя, фарфора, фаянса, майолики”. И если бы включение сюда, скажем, майолики оказалось неправильным, то значит всю информацию надо было бы признать ложной. Не в том, конечно, дело, что ложность в одном пункте превращает и остальные в ложные. Нет, каждое в отдельности суждение может оставаться истинным, однако вся информация в целом содержит изъян, следовательно, может из-за этого порождать ошибки. В этом смысле и только в этом, то есть взятое целиком, а не в отдельных своих компонентах, сложное конъюнктивное высказывание является ложным, когда ложным оказывается хотя бы один из его простых составляющих.

Отсюда вытекает очень важное в практическом отношении следствие: к элементарной конъюнкции можно присоединять неограниченное число истинных высказываний, а также можно их из нее убирать. Семантическое значение формулы не изменится, оно будет определяться теми конъюнктами, которые имелись в ней до введения или остались после удаления какой-то части: есть среди них хоть один ложный конъюнкт - все выражение ложно, нет - оно истинно. Это можно записать в виде такой формулы:

где 1 представляет собой любое истинное высказывание или формулу, среди множества семантических значений которой имеется только одно - “истина” и нет другого.

И еще одно не менее примечательное свойство: когда в элементарной конъюнкции содержится хотя бы одна пара, состоящая из переменной и ее отрицания, то тогда вся формула при любых значениях переменных образует только ложные утверждения. Это нетрудно понять, так как в этом случае в ней обязательно имеется хотя бы одна переменная, имеющая значение “ложь”. А этого, как уже сказано, достаточно, чтобы и вся формула образовывала только ложные высказывания.

Элементарные дизъюнкции строятся подобным же образом (переменная a_i тоже означает любое высказывание):

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

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

Наличие в элементарной дизъюнкции хотя бы одной переменной вместе с ее отрицанием приводит к тому, что в ней всегда обязательно содержится как минимум одна переменная со значением “истина”. Поэтому такая формула обязательно будет давать только истинные высказывания, какие бы наборы переменных мы ни брали.

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

где A, B, C, ...Z являются элементарными дизъюнкциями. Она, как видим, сходна с элементарной конъюнкцией, но каждый конъюнкт в свою очередь представляет собой элементарную дизъюнкцию. Так, формула

представляет собой конъюнктивную нормальную форму (КНФ).

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

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

A, B, C,... Z - элементарные конъюнкции. Так, к дизъюнктивным нормальным формам относится такая формула:

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