Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

При этом имеет место следующая взаимосвязь: выражение Й является тождественно истинным тогда н только тогда, когда ЧЯ является тоя:дественно ложным; далее, дизъюнкция является тождественно лоя«ной тогда и только тогда, когда тождественно ложен каждый ее член. Следует, однако, заметить, что диэъюнкция может оказаться тождественно истинной и в том случае, когда ви один из ее членов не является тождественно истинны»ь Простейшим примером такого рода является двзъюпкция А~/ 1А. С помощью нашего метода распознавания мы теперь для любых двух заданных выражевпй 21 и 93 можем вьшснить, заменимо ли кислое нз внх посредством другого.

В самом деле, М тогда и только тогда заменимо посредством й), когда для всех наборов значепяй входящих в оти выражения переменных оно принимает то же самое значение, что и Й, т. е. когда вырая«ение Я 2) является тождественно истинным. Но при помощи имеющегося у нас метода мы всегда сможем ответить на вопрос о том, имеет место данный случаи ила я е нет.

б. Совершенная нормальная форма; распоанавание заменимост«', примеры, Рассмотренный способ распознавания заменимости яглпсося, конечно, не очень удобным. Но эту проверку мы ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ 86 !Рл, гп '1еогия истннностных Функций 81 сможем осущсствить еще и другим путем, подвергнув конъюнктивную и дизъюнктивную нормальные формы дальнейшей специалиаации. Мы и без того будем вынуждены заняться этим, так как и коныонктивная и дизъюнктивная нормальные формы определяются совершенно неоднозначным образом. Например, конъ|онктивная нормальная форма (~А ~ В) б1 (~В ~ С) й (чС ~ А) представляет ту же самую истинностную функцию, что и конъюнктнвная нормальная форма (А 11/ 1В)А.(В~/ )С)А-(С ~/ 1А).

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

Сообра»кение, наиболее простым способом ведущее нас к нормировке желаемого вида, заключаются в следующем. Истинностная функция, зависящая от аргументов А„..., А„, определяется так, что каждому набору истинностных значений аргументов вновь сопоставляется некоторое истинностное значение. Каждый набор истинностных значений аргументов может быть представлен л-членной конъюнкцией, у которой 1-й ее член (1 < 1 ~( и) представляет собой либо А н либо 1А, в зависимости от того, какое значение — «истина» или «ложь» — принимает в этом наборе аргумент Ае Действительно, построенная таким образом конъюнкция на рассматриваемом наборе значений принимает значение «истина», а на остальных наборах — значение «ложые Мы будем говорить, что эта конъюнкция и р е д с т а вл я е т рассматриваемый набор значений аргументов.

Легко видеть, что рассматриваемая нами истинностная функция представляется дизъюнкцией конъюнкций, представляющих те наборы значений переменных, на которых наша истинностная функция принимает значение «истина>. Таким образом, для каждой истинностной функции, зависящей от аргументов А„..., А„и принимающей по крайней мере на одном наборе их значений значение «истина» (т. е. не являющейся тождественно ложной), мы получим некоторую пред- ставляющую ее дизъюнктивную нормальяую форму; и если мы установим для аргументов функции определенный порядок, который сохраним затем и в конъюнкциях, представляющих наборы их значений, то эта нормальная форма с точностью до порядка ее дизъюнктивных членов будет определена однозначно. Например, для истинностной функции А В, рассматриваемой как функция от аргументов А, В и С, действуя описанным образом, мы получим диэъюнктивную нормальную форму (А бс В бс С) ~ (А А В А- ~ С) ~ (Ч А А ~ В б1 С) ~ (Ч А бс ~ В А ~ С).

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

(В этом смысле мы можем говорить об однозначно определенной совершенной дизъюнктивной нормальной фо рме.) Отсюда, в частности, следует, что всякая истинпостная функция заданных аргументов А, В,... может быть представлена при помощи связок ос, ~/ и 1. (Разумеется, сказанное справедливо и для тон«дественно ложной функции, которая может быть представлена посредством выражения А бс 1 А.) Число различных истинностных функций, зависящих от аргументов А„..., А„, совпадает с числом различных (в указанном смысле слова) построенных из этих переменных совершенных дизьюнктивных нормальных форм, если мы согласимся считать, что пульчленная дизъюнкция представляет тождественно ложную Функцию.

Каждая из этих нормальных форм представляет собой некоторую поддизъюнкцию той («полной») дизъюнкции, которая содержит в качестве дизъюнктивных членов конъюнкции, представляющие все наборы значений аргументов, и которая представляет тождественно истинную функцию. Эта полная дизъюнкция состоит из 2" членов, и число ее поддизъюнкций (включая и нульчленную) равно 2' . Это и есть число различных истннностных функций, зависящих от аргументов А,,..., А„. Следует еще отметить, что по совершенной дизъюнктивной нормальной форме моя<но построить совершенную дизъюнктивную Нормальную форму для ол»рицания рассматриваемой истинностной Функции, взяв дизъюнкцию, дополнительную к исходной, т. е.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ 88 [ГЛ, Н1 ТЕОРИЯ ИСТНННОСТНЫХ ФУНКЦ11И в 1) дизъюнкцию, состоящую из всех тех представляющих конъюнкций, которые в исходной дизъюпкции не встречаются. Двойственным аналогом совершенной дизъюнктивной нормальной формы является совершенная нонъюнклвивная нормальная форлва, у которой по сравнению с формой, рассмотренной выше, знаки & и )/ меняются ролями. Исходя из совершенной дизъюнктивной нормальной формы для какой-либо истинпостной функции, мы можем получить совершенную конъюнктивеую нормальную форму для ее отрицания, построив отрицание походной нормальной формы и применив правила 2б) для преобразования отрицаний дизъюнкций и конъюнкций'). Совершенную дизъюнктивную или конъюнктиввую нормальную форму заданного выражения логики высказываний мы всегда можем получить, построив сначала описанным ранее способом какую-либо конъюнктивпую, соответственно диэъюнктивную нормальную форму, а затем преобразовав ее с помощью правил 1а), б) и За), б) ') в совершенную нормальную форму.

Пронллюстрируем этот метод на следующих двух примерах. Предположим, что пам требуется представить в виде совершенной конъюнктивной нормальной формы кстинностную функцию А как функцию двух переменных А и В. Заменим, согласно нравилу Зб), А посредством А в/ (В & ) В). Применив закон дистрибутивности, мы получим выравкение (А )/ В) &(А ~/ ~В), которое и представляет собой искомую совершенлую нормальную форму. Одновременно это выражение является совершенной коньюнктивпой нормальной формой и для А & (А в/ В), откуда ыы усматриваем, что 2! & (2! 'в/ л)) всегда заменимо посредством у!.

Двойственным образом мы могли бы получить длл выражения А, рассматриваемого как функция от переменных А и В, совершенную дизъюнктивную нормальную форму (А & В) )/ (А & ) В). А отсюда в свою очередь получается, что И вв/ (9! & 6) всегда заменимо посредством г!. Рассмотрим теперь выражение (А -в- ) В) С. Ранее ') мы получили для него дизыонктивную нормальнук> форму ( )А&С) в/(1В&С) Ч (А&В& 1С). в) Сы.

с. 79. в) Сы. с. 84. Чтобы получить из нее совершенную дизъюнктивпую иормальнувв форму, применим к первым двум членам дизъюнкции правило За); заменим ) А & С посредством ( )А & С) &(В ~/ )В), а затем, по второму закону дистрпбутивности (производя одновременно перестановку ковъюиктивных членов),— посредством (~А& В& С) в/ ( 3А & 1В&С); аналогичным образом ) В & С преобразуется в (А & ~ В & С) вв/ (~А &.

) В & С). Выполнив в нашем первоначальном выраявении эти преобразования и вычеркнув по правилу 1а) повторяющийся диэъюнктивный член ) А & ) В & С, мы получим для рассматриваемого нами выражения следующую совершенную дпэъюнктивную нормальную форму: (А & В & )С) вв/ (А & ) В & С) )/ () А & В & С) )/ ()А & )В & С). От этой совершенной дизъюнктивной нормальной формы мы можем следующим образом перейти к совершенной ковъюнктивной нормальной форме. Возьмем двойное отрицание этой формы. К однократноыу отрицанию прпмеенм упоминавшееся выше замечание о том, что отрицание согершевной днзъюнктивной нормальной формы представляется дополнительной дизъюнкцией.

Это даст наы для однократного отрицания следующее вырви,ение: (А & В & С) ~/ (А & ) В & ) С) вв/ () А & В & ) С) )/ ( ) А & ) В & ) С). Затем мы возьмем отрицание этого выражения и, применив правила 2б), получим совершенную коныовктивпвю нормальную форму ()А ~/ )В ~/ )С) & ()А )/ В ~/ С) &(А в/ )В вв/ С) & (А )/ В Ч С). Теперь с помощью совершенных нормальных форм мы получе11 простой способ для выяснения вопроса о том, представляют ли два заданных вввралвепия г! и Й одну и ту же нстинностную функцию. Этот способ заключается в следующем. Сначала мы выписываем в каком-нибудь порядке все переменные, входящие в Я и в В, а затем строим для 9! и для е), рассматривал их как функции всех указанных переменных, их совершенные дизъюнктивные или совершенные конъюнктивные нормальные формы. Я и вн взаимно заменимы тогда и только тогда, когда рассматриваемая нормальная форма у Й является той же самой, что и у Й.

Характеристики

Список файлов книги