Колмогоров, Драгалин - Введение в математическую логику (947386), страница 15
Текст из файла (страница 15)
В самом деле, справа в определении фигурируют лишь формулы меньшей логической сложности, чем слева. Важной особенностью определейия истинности по сравнению с другими индуктивными определениями, до сих пор у нас встречавшимися, является то„что для выяснения истинности некоторой формулы необходимо исследовать бесконечное количество формул меньшей сложности. Так, для установления М~=)~хА следует убедиться, что имеет место М=А", для всех аенР„, в то время как область Р„может быть (и обыкновенно бывает) бесконечной. Аналогично, для установления М ~=Д хА следует показать существование аенР„, такого, что М 1==А",. Если Р„бесконечна, то этого .нельзя сделать, просто перебй рая все объекты из Р„.
Приходится провести некоторое теоретическое исследование. Это одна из причин особой сложности предиката истинности, источник многих замечательных свойств этого, понятия. Если формула содержит параметры, то истинность или ложность ее зависят от оценки ее параметров..При одной оценке параметров формула будет истинной в модели, при другой — ложной, Таким образом, в данной модели формула с параметрами задает.предикат от своих параметров в соответствии с нашим замыслом. В частном случае, когда формула замкнута, она определяет в М некоторае исткнностное значение. Таким образом, зрмкнутая формула задает конкретное истинное или ложное вьссказывакие, 6. Уточним теперь наше понимание логических связок Л, ~/, =», 1. Пусть, как и ранее, 1 означает «истина», О— 74 «ложь». Логические связки Л, '1/, ( ведут себя как операции в простейшей булевой решевке яз двух элементов (О, 1).
удобно ввести также производную логическую связку — эквивалентность — с помощью знакомого нам сокращения А ю В = (А =з В) Л (В =з А). АмВ А~/В ' АЛВ А В 1 о 1 1 1 1 о о о о ! Таким образом, если А и В истинны, то высказывание А~/В также истинно, т. е. мы понимаем А1/В как «по крайней мере А или В». Это так называемое «неразделительное нлн». В обыденном языке чаще употребляется «разделительное или» вЂ” «А или В, но не оба вместе», что в наших связках может быть записано примерно так: 1А1/В)Л 1 (АЛВ). Особую проблему составляет понимание импликации. Как понимать импликацию, если ее посылка ложна? Попутно заметим, что в нмпликации 'А:»В формула А называется 'посылкой (иногда — антецедентом), формула В— заключением (иногда — сукцедентом, иди . консеквентом).
В обыденной жизни сообщение А:»В, если заведомо известно, что А ложно, .не считается ни истинным, ни ложным; такое сообщение просто не имеет ценности, бессодержательно. Какое значение может яметь сообщение «если А, то В», если А ложно и, следовательно, вышеуказанное сообщение не может быть использовано для отыскания В? Если мы желаем иметь логику только с двумя истинностными значениями О и 1, то с этой точки зрения последние две строчки в таблице для лмпликации можно заполнить произвольным образом.
В целях лучшего соответствия с практикой обычных математических рассуждений, где часто приходится использовать импликацию как раз в ситуации, когда истннностное значение 'посылки неизвестно, в последних двух строках им. плнкации ставят истину. Так понимаемая импликация,называется материальной, именно она,и используется в математике, Эквивалентность истинна тогда и только тогда„когда оба ее члена имеют одинаковые истивностные значения. оба истинны нли,оба ложны. 7, Пусть формула А языка И составлена из формул А~ ..„А» с помощью логических связок /~, ~/,:э, ) без ис пользования кванторов. Кианторы могут входить лишь в со.
став самих формул Аь Тогда мы говорим, что формула А есть булеза комбинация формул Аь ..., А». Мы хотели бы полностью проанализировать, как зависитт истинность формулы А от истинности формул Аь, А» Такой анализ дает построение таблицы Куайна для формулы А. Построение таблицы начинается с того, что под каждой из формул Аь...,А, мы выписываем всевозможные комбинации нулей и единиц.
Возникает я столбцов из нулей и единиц, каждый столбец длиной 2'. Затем выполняем почленно все операции формулы, пока не получаем последний главный столбец таблицы. ' Операции выполняются,над столбцами. Вот пример составления таблицы Куайна для формулы — булевой комбинации формул А, В, С (главный столбец выделен): й) (В 1 1 О О 1 1 О .О 1 1 1 О ! 1 1 О О ! О 1 1 1 1 ! О О О О 1 1 1 1 1 ! 1 1. О О О О Из таблицы видно, что наша формула может быть ложна лишь в двух случаях: А ВС 1 11 1 01 Дальнейший анализ зависит уже от строения формул А, В,. С и от рассматриваемой модели. Может оказаться„напри-.
мер, что в рассматриваемой модели оба случая не реализу-' ются и, следовательно, наша формула истинна. Особенно интересен случай, когда главный столбец таблицы состоит лишь из единиц. Это свначает, что независимо от истинности составляющих формул Аь ..., А» рассматри-' ваемая формула, будет истинной (при любой оценке, в любой модели). Такую формулу мы назовем пропоэиг(иональной тавтологией. Упражнение.
Убедитесь, что следующая формула является пропозициональной тавтологией; А=В», А~/СэнВ~/С. $4. ПРИМЕТЫ ЯЗЫКОВ И МОДЕЛЕЙ 1. Рассмотрим язык элементарной арифметики Аг. Язык Аг содержит лишь один сорт объектов и, следовательно, один сорт переменных х, у, г, .... Аг содержит единственную константу, которую мы обозначим О, и три функциональных символа ), д, й, причем 1 — одноместный 'функциональный символ, д,' й — двуместные функциональные символы. Пример терма Аг: д(Ь(х, 0), д()(у), 1(1(0)))). Специально для языка Аг удобно, ввести обозначения: (г + г) й (г ) (7 г) = й (1, г), 57 =1(1). В этих обозначениях (с обычной экономией скобок) предыдущий терм запишется в виде х О+ (5у+550) Наконец, язык Аг содержит единственную двуместную преднкатную букву Р. Вместо Р(7 г) мы будем писать (7=г).
Атомарные формулы языка Аг мы будем называть формальными равенствами. Описание языка Аг закончено. Рассмотрим модель для Аг, которую мы назовем в. Носитель в есть множество натуральных чисел (это множество мы также обозначим через гэ). Константе 0 припишем значение О~а. Функциональным символам х+у, х у, 5х припишем функции сложения, умножения и прибавления единицы в Области натуральных чисел. Атомарная формула х=у выражает в гв совпадение натуРальных чисел, т. е.
гэ1= (п=пг) 4-"и и пг есть одно и то же натуральное число. Рписаиие модели 'гв закончено. 77 П р и,м е р ы. Терм (х+ у) . г+ 5х, оцененный посредство (~ ~ ~). задает оцененный терм (1+5) 3+81 ~и имеет в в значени 20. Этот же терм при оценке Я~) имеет вид (2+6) 4+о2 и имеет значение 35. Формула 3у(х+у=г) при оценке ~3 5) превращается в оцененную формулу Ду(3+у 5), которая истинна. При оценке Я) получим ложную формулу Ду(5+у=3), Некоторые формулы Аг истинны в а при любой оценке.
Такие формулы назовем арифметическими законами (язык а Аг). Например, таковы ~х+у=у+х, 1х=О=з3г(Бг=х), Вх=Ву=ох=у. Можно ввести сокращенные обозначения для формул Аг естественные с точки зрения интерпретации ап х~(у=юг(х+ а= у), х(у — х~(у Л 1х= у, ' (х — четно)=3 у(х = у+ у), (х)у) = ~х= ОЛйг(х г =у), (х — простое)= 1х = 0 Л 1х ='ВОЛ 'у'г ((г1х) ~ г = о 0 ~~ г = х). Чожно выразить некоторые высказывания в языке 1) 1ух((х — простое) =э ~ у((х(у) Л (у — простое) ) ) «ко зичество простых чисел бесконечно»; 2) ух3 у (х~уЛ(у — простое) Л(у+550 — простое) ) «количество простых чисел-близнецов бесконечно». Истинно или ложно это последнее высказывание — неизве- стно в настоящее время. 3) Принцип полной математической индукции также мо- жно выразить в Аг. А именно для каждой формулы А в е истинна формула А (О) Л 'фх (А (х);»А (5х) ),ифхА (х).
Более аккуратно, не употребляя неформального обозначения А(х), этот принцип можно записать в виде А "оЛ~ х(А~А'з,) =з ~хА. Заметим, что в .языке Аг для,каждой формулы А фор- мулируется свой принцип индукции, в языке нет возмож- ности сказать: «для всякой формулы А». Индукция форму- лируется в виде бесконечной серии формул — схемы акси- ом индукции. 2. Рассмотрим другую модель для Аг, которую мы обо- значим через й. Носитель этой модели есть множество й действительных чисел. Константе 0 соответствует О, симво- лам +,, 5 опять-таки, соответствуют сложение, умножение н прибавление единицы, но уже в области действительных чисел.
Формула х=у выражает совпадение действительных чисел. Формулы' Аг, истинные при любой оценке в и, назовем законами действительных чисел (языка Аг). Таковы, на- пример, формулы х+у=у+х, 5х=5у~х=у, 'Ч'х~ г(х+г=0), (к=О~~ у(х.у=50). Заметим, что здесь фигурируют и формулы, не являющиеся арифметическими законами. Понятие закона языка зависит от его интерпретации, его модели. Как говорят логики, это семантическое понятие.
В модели й естественны уже другие сокращенные обо- значения для формул. Например, с точки зрения й естест- венно ввести обозначение х<у=~г(х+г.г=у). Упражнение. Определите естественным образом мо- дель Х целых чисел для языка Аг, Как в этой моделя опре- делить хапуг (Указание: по известной теореме Лагранжа каждое, натуральное число представимо в виде суммы четы- рех квадратов.) 79 Часто язык рассматривают вместе с какой-либо одно выделенной моделью, которую называют подразумеваемо интерпретацией (естественной моделью, стандартной моделью) языка.
Для языка Аг стандартной моделью мы буде считать модель в.. Все выразительные возможности языка Аг, может быть и не видны с,первого взгляда. Например, может показаться стеснительным, что.в Аг есть сложение и умножение, но нет обозначения для функции 2". В действительности функция 2' (и весьма многие другие) может быть выражена в Аг в виде формулы, т. е. может быть простроена формула А(х, у) с двумя параметрами х и у, такая, что га ~А(т и) ~э-ог=2«. О теории определения числовых функций можно прочесть в более подробных курсах математической логики (см. список литературы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
