4. Двойственность; конъюнктивная и дизъюнктивная нормальные формы; тождественно истинные выражения; распознающая процедура.

Так теория истинностных функций ведет нас к некоему исчислению высказываний. Чтобы составить себе систематическое

представление об этом исчислении, мы рассмотрим ряд общих вопросов, касающихся правил замены.

Прежде всего бросается в глаза, что в правилах 1—3 конъюнкция и дизъюнкция фигурируют совершенно симметричным образом, так что система этих правил не изменится, если всюду поменять местами. Выраженная в этом факте «двойственность» объясняется тем, что конъюнкция и дизъюнкция как истинностные функции находятся в таком отношении друг к другу, что одна из них получается из другой, если в значениях аргументов и функций «истину» и «ложь» всюду поменять местами. В этом легко убедиться, сравнив таблицы для

Для алгебры логики, которая отражает аналогию между исчислением высказываний и алгеброй, получающейся на базе правил замены 1-й группы, эта двойственность влечет за собой тот факт, что для нас оказывается безразличным вопрос о том, какую именно из связок следует рассматривать как сумму, а какую — как произведение. В самом деле, здесь, в исчислении высказываний, у нас имеются два закона дистрибутивности. Преобладающая в литературе точка зрения на конъюнкцию как на «логическое произведение», а на дизъюнкцию как на «логическую сумму» соответствует точке зрения объемной (экстенсиональной) логики, в то время как с точки зрения содержательной (интенсиональной) логики естественным является как раз обратное сопоставление.

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

Прежде всего, правила 4-й группы позволяют нам удалить знаки Затем повторным применением правил 2-й группы мы можем добиться того, чтобы знак отрицания стоял только перед отдельными переменными и чтобы более не встречалось повторяющихся отрицаний. Теперь с помощью правил 1б) и 1в) мы можем убрать скобки, «выполнив умножения» в смысле того или другого из двух имеющихся у нас законов дистрибутивности. В зависимости от того, какой закон дистрибутивности мы применим — первый или второй, — получится конъюнктивная или дизъюнктивная нормальная форма.

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

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

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

Применение правил 4-й группы дает

Выражение

стоящее во вторых скобках, согласно правилу 26) дает

и, по 2а),

так что в целом мы получаем

Отсюда, применив первый закон дистрибутивности и опустив ненужные скобки, мы получаем выражение

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

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

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

Достаточность этого условия легко получается из того, что выражение

тождественно принимает значение «истина». Необходимость его усматривается следующим образом. Для того чтобы конъюнкция была тождественно истинной, должен быть тождественно истинным каждый ее член. Таким образом, у тождественно истинной конъюнктивной нормальной формы должна быть тождественно истинной и каждая из ее простых дизъюнкций. А для того, чтобы простая дизъюнкция была тождественно истинной, хотя бы одна переменная должна встречаться в ней как с отрицанием, так и без него; действительно, если бы каждая переменная фигурировала либо только со знаком отрицания, либо только без знака отрицания, то дизъюнкция получила бы значение «ложь», если бы мы всем переменным без знака отрицания приписали значение «ложь», а всем переменным со знаком отрицания — значение «истина».

У рассмотренного метода распознавания имеется двойственный аналог: совершенно аналогичным образом с помощью дизъюнктивной нормальной формы мы для произвольного выражения можем решить вопрос о том. принимает ли оно значение «ложь» при любом распределенип значений переменных, т. е. является ли оно тождественно ложным.

При этом имеет место следующая взаимосвязь: выражение является тождественно истинным тогда и только тогда, когда является тождественно ложным; далее, дизъюнкция является тождественно ложной тогда и только тогда, когда тождественно ложен каждый ее член.

Следует, однако, заметить, что дизъюнкция может оказаться тождественно истинной и в том случае, когда ни один из ее членов не является тождественно истинным. Простейшим примером такого рода является дизъюнкция

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