1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 4
Текст из файла (страница 4)
Пусть 1 (3 8 вхождение слова (3 в о:. Если о:' = 1 /3' 8 для некоторого слова /3', тобудем говорить, что слово о:' получается из о: заменой вхождения1* /3 * 8 подслова /3на слово /3'.Ряд Х1, ... , Xn некоторых объектовXi, i Е { 1, ... , п}, будем на- длинойэтой последовательности. Объекты Xi, i Е {1, ... , п}, будут называтьсячленами или элементами последовательности Х1, ...
, Xn. Мы предзывать последовательностью или кортежем, а число пполагаем,чтопозаписипоследовательностиеечленыиихпорядоквосстанавливаются однозначно. Для этого нам необходимо разделятьчлены последовательности, например, с помощью запятой. Если пто ряд Х 1, ... ,Xn= О,будем считать пустой последовательностью и обозначать его тем же символом 0, что и пустое множество. Иногдапоследовательность Х1, ... , Xn будем обозначать через (Х1, ... , Xn).Если Х 1 , ••• , Xn - множества, то множество всех кортежей (а 1 , .•.
, an),Гл.16где а1 Е Х1,Х1... , ап/.Исчисление высказыванийЕ Хп, будем обозначать через Х1 х= Х2 = ... = Хп, то множество Х1х Х2 х......х Хп. Еслих Хп будем обозначатьтакже через Х 1 . Последовательность из двух (трех и т. д.) членовбудем называть парой (тройкой и т. д.). Последовательность из п элементов будем называть п-кой.Отображениемfмножества Х в множество У называется соответствие, сопоставляющее каждому элементу а Е Х элементназываемый значением отображенияfражениемножества Хмножеством { (а,f(a))вfмножество УЕ Х х УJ(a)однозначно определяется[ а Е Х}.
Это множество (называемоеиногда графиком Л мы будем отождествлять с отображениемотображение Х в У, то пишемf -всякое отображениена Х, а пff : хп -+ Хf:Х-+ У. Если Х-f.Еслимножество, тобудем называть п-местной операциейместностью операции-Е У,на элементе а. Ясно, что отобf.Еслиf:У-+ Х и У~ хп, тобудет называться частичной п-местной операцией на Х с областьюопределения У.Для того чтобы задать множество Х, достаточно указать, для какихобъектов а истинно отношение а Е Х. Поэтому следующие выражениябудут однозначно определять по двум множествам Х и У новые множества Хn У,ХU У и Х \ У, называемые соответственно пересечением,объединением и разностью множеств Х и У:а) а Е ХnУб) а Е ХUY {::::::}в) а Е Х\(а Е Х и а Е У);{::::::}У(а Е Х или а Е У);{::::::} (аПредложениеl. l.
l.Е Х и а ф. У).Операции пересечения и объединения удовлетворяют следующим равенствам для любых множеств Х, УиZ:la)XnY=YnX}= YUXlб)XUY2а)Хnx= х}2б)ХUХ =Хза) (Х n У) n-коммутативность;идемпотентность;z = х n (У n Z)}= Х U (У U Z)3 б) (Х U У) U z- ассоциативность;4 а) Х n (У u Z) = (Х n У) u (Х n Z)}4 б) Х u (У n Z) = (Х u У) n (Х U Z) -дистрибутивность.Проверка этих равенств не представляет труда. Докажем, например,46.Пусть элемент а принадлежит левой части равенства. Тогдаа Е Х или а Е Уn Z,поэтому а Е ХUУи а Е ХU Z,т. е. а принадле-§ 1.2.Язык исчисления высказыванийжит правой части. Если а Е ХUУи а Е ХU Z,17то а Е Х или а Е УСледовательно, а принадлежит левой части равенстваЕсли Хn Z.О(46).множество, то множество всех его подмножеств будем-называть множеством-степенью Х и обозначать через Р(Х).ПустьнепустоеJ -множествоU Xiмножества. ОбъединениемiЕJ,идляXiiЕи пересечением ПJ - некоторыеXi множеств Xi,iEJiEJбудем называть множества, определенные следующим образом:а ЕU Xi -<==>(а ЕXi для некоторого i Е J),iEJа Е ПXi -<==> (а Е Xi для всех i Е J).iEJuх и nхДля множества х черезственно множества{аIа Ебудут обозначаться соответЬ для некоторого Ь Е Х} и{аIа ЕЬ длявсех Ь Е Х}.Упражнения1.Сколько различных вхождений имеет пустое слово Л в словодлины п?2.Показать, что число различных поделав слова а длины п неn(n + 1)2превышает3.Для каких слов а длины п число различных поделав а равноn(n+ 1)24.+ 1.+р.Пусть множества Хо,...
, Xn+Iявляются подмножествами некоторого множества У. Обозначим черезмножество У\XiXi.Показать, чтоа)UXi=П Xi; б) П Xi= UXi; в)Хо ПХ1 =Хо\ (Хо \Х1).i~n§ 1.2.Опр БудемЯзык исчисления высказыванийговорить, что задано исчислениеI,если заданы следующиечетыре множества:а) алфавитA(I);E(I)б) множествослов алфавитавыражений исчисленияв) множествоAx(I)R(I)называемое множествомвыражений исчисленияством аксиом исчисленияг) множествоA(I),I;I,называемое множеI;правил вывода исчисленияI.Гл.18Исчисление высказываний/.·Правило вывода в этой книге будет записываться так:S1, ...
,SnsПри этомS1, ... , Snного исчисления,симость. Схемыибудут некоторыми схемами выражений данSвыражающимиих определенную структурнуюзавибудут называться посылками, а схемаS1, ... , SnS -заключением данного правила. Число п называется местностью данного правила; п-местное правило будем называть также п-посылочнымправилом.Если конкретные выражения Ф 1 , ••• , Фn и Ф удовлетворяют структурным условиям данного правила, выраженные схемамииS,S1, ... , Snто записьфбудет называться применением данного правила, а выражение Фрезультатом применения этого правила к выражениям Ф1,что Ф получается из Ф1,ОпрПаруражений...
, ФnисчисленияE(I)А(/1) ~ А(/2) иисчисленияпо этому правилу вывода.12E(I1)1,будем называть языком исчисленияПусть даны два исчисленияL(I).даноисчисление~E(I),то1,ний или теорем исчисленияI111 и 12. Если~ Е(/2), то будем говорить, что языкявляется расширением языкаи обозначать это так: L(/2 ) ~ L(/1).T(I)-или(A(J), E(I)), состоящую из алфавита A(I) и множества выи обозначать черезЕсли... , ФnL(/2)11,исчисленияL(I1)1)множестводоказуемыхвыражеопределяется как наименьший класссодержащий множество аксиом исчисления1и обладающий следующим свойством:(*)Опресли выражение Ф является результатом применения некоторогоправила р Е R(I) к выражениям Ф 1 , ••. , Фn Е T(I), то Ф Е T(I).
2)Высказыванием в русском языке мы называем повествовательноепредложение,прокотороеможноутверждать,ложно. Например, высказывание <<водаистинно,авысказывание<<все-нечетныечтооноистинноилипродукт горения водорода>>натуральныечисла простые,>ложно. Из высказываний А, В в русском языке мы можем образовыватьболее сложные высказывания такие, как <<А и В,>, «А или В,>, «неверно,что А~, <<если А, то В,>.
Если мы знаем, истинно или ложно каждоеиз высказываний А, В, то мы можем определить, истинны или ложны1)Это обозначение не совсем согласуется с уже введенным обозначениемвключения для множеств, однако оно удобно и путаницы не вызывает.2)..,В дальнейшем нам будет удобнее работать с равносильным, но болееконструктивным определением множества теорем исчисления.Язык исчисления высказываний§ 1.2.19выписанные выше сложные высказывания. Например, если А истинно,а В ложно, то высказывание «если А, то В;; ложно.
Однако иногдамы можем утверждать об истинности сложного высказывания, не зная,истинны или ложны высказывания, из которых оно составлено. Например, каковы бы ни были высказывания А и В, высказывание «неверно,что А, или если В, то А,> всегда истинно. В этом случае говорим, чтосхема <<Неверно, что А, или если В, то А;; тождественно истинна.
Однойиз основных задач исчисления высказываний, к изучению которогомы приступаем, является описание тождественно истинных схем. Дляэтого придется заменить русский язык формальным языком, которыйне допускает двусмысленностей.ОпрАлфавит исчисления высказываний, которое будем обозначатьчерез ИВ, состоит из трех групп символов.1.Пропозициональные переменные:Qo, Q1, ... , Qп, ... ,где п-натуральное число.2.Логические символы или связки: импликация-, конъюнкция/\,дизъюнкция V, отрицаниеконстанта3.~,символ следованияf-,логическаяJ.Вспомогательные символы: левая скобка(,правая скобка),запятая,.Определение.
Формулой ИВ назовем слово алфавита ИВ, удовлетворяющее следующему индуктивному (по длине слова) определению.1.Пропозициональные переменные и логическая константа являются формулами (будем называть их элементарными или атомарными).2.Если Ф и Ф-формулы, то (Ф/\Ф), (Ф V Ф), (Ф-Ф) и ~Ф-формулы.Из определения следует, что(Qo /\ Q1) V Qo -не формула (нетвнешних скобок).
Однако в целях сокращения записи мы часто будемопускать внешние скобки. Таким образом,щенной записью формулы((Qo /\ Q1)V(Qo /\ Q1) V QoQo).будет сокраВ дальнейшем формулы исчисления высказываний будут обозначаться буквами Ф, Ф, Х, а пропозициональные переменныеми Р,R,причем Ф, Ф, Х, Р,Опр ПодформулойR-буквамогут иметь индексы.Ф формулы Ф ИВ будем называть подслово Ф, являющееся формулой ИВ.Докажем теперь утверждение об однозначности разложения формулы ИВ.Предложение1.2.1.Всякая неатомарная формула Ф ИВ представима в одном и только одном из следующих видов: (Ф(ФV Х),Фи Х.(Ф-/\ Х);Х) или ~Ф для однозначно определенных формулГл.201.Исчисление высказыванийДля доказательства предложения установим сначала один технический факт.ЛемЛемма1.2.2.Если Ф иW-формулы ИВ и Фначало-W,тоW.Ф=До к аз ат ел ь ст в о.
Доказывать лемму будем индукцией по длинеформулы Ф. Если Ф атомарна, то ив противном случаеW начинаетсяФ не может быть началомW.W должнабыть атомарной, так каксо скобки или с символаПусть Ф не атомарна и имеет вид ·ф', тогда·w',•и тогда= W.Следовательно, ФW должна иметь видпричем, как нетрудно усмотреть из определения формулы, Ф' иW'должны быть формулами. Кроме того, Ф' является, очевидно, началомW'.Индукционное предположение дает Ф'= W'и, следовательно, Ф== ·Ф' = ·w' = w.Пусть Ф имеет вид (ФотФ1), где Фо и Ф1из символов-формулы ИВ, т -один/\, V или -. Тогда W начинается со скобки ( и поэтомуможет быть представлена в виде (Woт'W1), гдеWoиформулыW1 -и т' - один из символов /\, V или -- Так как (ФотФ1) являетсяначалом (Woт'W 1 ), то слово Фо будет началом слова Woт'W1, Wo - тоженачало этого слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
