1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 3
Текст из файла (страница 3)
Исчисления, формализующие основныеконструкции«наивной,>теориимножеств,оказались стольбогатыми, что любое теоретико-множественное рассуждение, встречающеесяв реальной математической практике, можно формально воспроизвестив этих исчислениях. Естественной <,расплатой,> за это богатство былообнаружение К. Гёделем эффектов неполноты и даже непополнимоститаких исчислений.Напутипостроениясемантикиестественныхилиформальныхязыков нас поджидают также большие трудности. Так, простодушное убеждение, что каждой повествовательной фразе русского языкаможно правдоподобным (или, по крайней мере, непротиворечивым)образом приписать значение истинности, опровергается так называемым «парадоксом лжеца».
Некто говорит: <,Фраза, которую я сейчаспроизношу, ложна». Попробуем выяснить, правду сказал этот человекили солгал. Если пред.положить, что он сказал правду, то из смыслафразы получается, что он солгал.Если он солгал, то из того, чтофраза ложна, получаем, что он сказал правду. Этот парадокс лежитв основе ряда замечательных теорем математической логики (теоремо неполноте и о неопределимости истинности в системе).История создания и развития математической логики является самостоятельным предметом и ей не будет уделено внимания в этой книге, за исключением приведенных выше заведомо неполных указанийнекоторых имен и обстоятельств.В заключение настоящего введения нужно отметить, что современная математическая логика представляет собой обширный и разветвленный раздел математики, источником проблем для которого нарядусвнутренними еепроблемами служат как философские проблемыоснований математики и логики, так и проблемы, возникающие в других разделах математики (алгебра, анализ, теоретическая кибернетика,программирование и др.).Глава1ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ§ 1.1.Множества и словаПод буквой мы понимаем знак, который рассматривается как целый, т.
е. знак, части которого нас не интересуют. Букву будем называть также символом.1)Про две данные (например, написанные)буквы мы можем говорить, что они одинаковы или что они различны.Например, все строчные буквы <<а>> в данной книге считаем одинаковыми. Одинаковыми мы считаем также все строчные буквы «а>> в некотором рукописном тексте, хотя одинаковость двух букв в этом случаеустановить трудней, чем в предыдущем.
Будет предполагаться, что длярассматриваемых двух конкретных букв мы всегда можем установитьих одинаковость или различие. Если буквы а1 и а2 одинаковы, то будемписать а1=а2.Абстракция отождествления одинаковых букв дает нам понятиеабстрактной буквы.В дальнейшем о двух одинаковых конкретныхбуквах а1 и а2 мы будем говорить как об одной и той же (абстрактной)букве а. При этом каждая из этих двух конкретных букв будет называться представителем абстрактной буквы а.2)Совокупность Х некоторых объектов, которые будут называтьсяэлементами Х, назовем множеством1)3).Иногда слово <<буква>> будет иметь и обычный смысл, например, «латинская буква,>, «строчная буква,>.2)Следует при этом различать абстрактную букву, обозначаемую символом а, и сам символ а, который является обозначением или именем упомянутойабстрактной буквы.3)Как отмечалось во введении, такое определение, вообще говоря, можетпривести к противоречию.
Однако это не должно пугать читателя, так каксуществование всех рассматриваемых в этой книге множеств можно вывестив рамках формальной системы, описанной в§ 2.6,в которой невозможно прямопровести ни одно известное «парадоксальное,> рассуждение о множествах.Гл.14Если а1.Исчисление высказыванийэлемент множества Х, то пишем а Е Х. Если любой-элемент множества Х является элементом множества У, то множество Х называется подмножеством множества У и обозначается этотак: Х ~У.Если для множеств Х и У имеем Х ~ У и У~ Х, то будемсчитать множества Х и У равными и писать Х= У.Таким образом,множество полностью определено своими элементами. В частности,существует только одно множество, не содержащее ни одного элемента.Такое множество будем называть пустым и обозначать символом 13.Если для множества Х не имеет место а Е Х, то будем писать а ф.
Х.Буквамип, р,i, j, k, l, m,возможно с индексами, будемr, s,обозначать натуральные числа. Множество всех натуральных чиселбудем обозначать буквой u.1. Если а, Е Х,... , ап Е Х, то будем писать- множество, а,, ... , ап Е Х и любой элемент Хравен одному из а,, ... , ап, то Х называем конечным множеством ипишем Х ={а,, ... , ап}. 1) Если ср(а) - некоторое условие на объект а,а Х - множество, то через {а Е Х / ср(а)} или {а/ ср(а),а Е Х}а,,...
, апЕ Х. Если Хобозначаем множество, содержащее в качестве элементов те и толькоте элементы а Е Х, которые удовлетворяют условию ср(а). Например,{пЕ u.1 / п=2k для некоторого k Еu.1}является множеством всехчетных натуральных чисел.Множество абстрактных букв называется алфавитом. Букву, являющуюся элементом алфавита А, будем называть буквой алфавита А.Конечный ряд написанных друг за другом конкретных букв называется конкретным словом. В частности, каждая конкретная букваявляется конкретным словом. Если каждая из букв конкретного слова о: является представителем некоторой буквы алфавита А, то будемговорить, что о: является словом в алфавите А.
Мы допускаем такжеслучай, когда слово о: не содержит ни одной конкретной буквы. Такоесловобудемназыватьпустым ирить, что два конкретных слова а,и писать а,... ап =Ь1... Ьk,если пслова считаем равными. Если а,из п букв а,,... , апобозначать через Л.... ап=kи а,=... ап -Будем говои Ь,... Ьk алфавита А равны,Ь,, ...
, ап = Ьп. Все пустыеконкретное слово, состоящееалфавита А, то число п называется длиной этогослова. Длиной пустого слова будет число О.Применяя абстракцию отождествления, будем говорить о двух равных конкретных словах о: 1 , 0:2 как об одном и том же (абстрактном)слове о:. При этом эти два конкретных слова будем называть представителями слова а. Из определения равенства конкретных словполучаем, что абстрактное слово о: можно определить как конечныйряд абстрактных букв такой, что каждый представитель слова о: есть1)Отметим, что при этом попарное различие элементов а 1 ,полагается. В частности,{0} = {0, 0, 0}.••• ,an не пред§/./.Множества и слова15ряд представителей соответствующих абстрактных букв.
Количествоабстрактных букв в этом ряду будем называть длиной абстрактногослова а. Пустое абстрактное слово будем обозначать той же буквой Л,что и конкретные пустые слова./3Для абстрактных слов о: иопределяем абстрактное слово о:/3как такое абстрактное слово, все представители которого получаютсяприписыванием к некоторому представителю слова о: некоторого представителя слова/3.Абстрактное словоабстрактных слов о: и(3;0:/3будем называть соединениемабстрактное слово о: будем называть началомслова о:(3.
Аналогично определяется соединениеСЛОВ О:1,0:1 ... O:nабстрактных... , O:n.В дальнейшем под словом мы понимаем абстрактное слово. Очевидно, что для любых слов о:,Словоесли о:(3(3имеем Ло:=о:Л=о: и о:Л/З=о:(3.алфавита А называется подсловом слова о: алфавита А,= 1 /38для некоторых слов1 , 8.В частности, любое началослова о: будет подсловом о:. Может оказаться, что о:=для различных словниях подслова(31,,1.1 (38и о:=,1/381В этом случае говорим о различных вхождев о:.
Таким образом, вхождением подсловао: называется слово(3 вместе сподслова (3 в слово(3в словоместом его расположения в слове о:.о: можно изображать так: 1 * (3 * 8,* - символ, не принадлежащий алфавиту А. В частности, еслио: = 1 (38 = 11 (38 1 и 1 =/:. ,1, то мы имеем два различных вхождения1 * (3 * 8 и 11 * (3 * 8 1 подслова (3 в слово о:. Если для вхождения,о * (3 * 80 подслова (3 в о: слово ,о слово 80) имеет наименьшуюдлину среди всех слов 1 (слов 8), для которых о:= 1 /38, то ,о* /3 * 80называется первым (последним) вхождением (3 в о:.Вхождениегде(Вхождением буквы а в слово а называется вхождение в о: слова,состоящего из одной буквы а. Если существует вхождение буквы а* *в слово о:, то говорим, что буква а входит в а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
