Ш.И._Галиев_МЛ_и_ТА_2004

и Л=>3. Требустса н&йта вес логические следсганя згих форм. Для лиги составляем конъюнкцию данных форм: А<ЦАгэВ] и находим

равносильную	с.к.н.ф.; (.AvBWAv1 S)&(1 AvB) Искомые следст­
вия суть:
AvB', а ЛВ\ 1 А-/В\ ШЬЩА~ЛВ\-А: Mv-?)&(l^vS)- S; {A-J \
S)&(\A^B)~A=B\		B)&0AVB)-ALB.
a)AHlB ' В,	Ъ)4~ В 1/f;	sJ/IsS, В=Г\А, А; г)Л=>3, 'l5—"U;
о)		BvC,	а, вы:-, 6) Ъ=>Д fi-C, 1С=>А

Логическое следствие налетается простой следствием, если оно является элементарной суммой, кс содержащей повторяющихся сла­ гаемых, а также не является тавтологией и является минимальней, т.». после отбрасывания какого-нибудь из ее членов перестает бытьлоги­ ческим следствием ит данных форм. Так, в разобранном примере про­ стыми следствиями us А иА~В являются следстеис А и следствий В. Конъюнкция меж просты* следствий данной формы А оказывается сокращенной к.н.ф,

7.Найте все простые следствия дня пропозициональных форы

задачи ¢.

8.Для заданных посылок найти асе-их простые следствия. (Ука-

г)А=ЛВ.АчС, 1(£&С);		6) (X&S)=»1С, В, С,
в) (AvS)&C, Й=»1С;		г) АвП. Л^С'А В;
д)Л=В,	1в^С, В.

Рассмотрим пркмер исполыованвп сокращенных к.н.ф. В со­ вершении некоторого поступка подозревается только одно из четырех лид: 7/1, JI2, 111 и М . .71 утверждает, что поступок совершил jl2; JT2

шал этого поступка, и //4 тоже говорит, что он мого ппсп'пка не со­ вершал. Кто же совершил поступок, если известно, что только одно из этих утверждений истинно?

13)

Через А, 3. С и D обозначим соответственновысказывания «по­ ступок совершил Л1, Л2, Л3 и Л4». Тогда условие, что поступок мог совершить только один из четыре*, запишется в виде пропозицио­

нальной формы:
-4=I w & b ) * V * q * V s d o &	\ т т	\ CSLD).
которая означает, что никакие два из	четырех	высказываний

не могут быть оба истинными. Заявление каждого из четыре* означа­ ет: В, Д 1 С и ! D. Но так кпк истинно только одно из ни*, то, значит, никакие два из этих заявлений ке являются одновременно истинными. Это условие запишете*в следующемвкое:

B=\atiD)&. l(D&lc)& 1|1d&!c)& YIc&Id).

Берем конъюнкцию посылок А и В, находим дла ЛИВ сокра­ щенную к.аф.: 1 BSL |£&С&Ы, котори означагг, что высказывании А, В, Г>лсикнн1,а высказываниеС: «ПоступоксояерштЛЗ»- истинно.

9 Используя условия из рассмотренного примера, узнать, к совершил поступок, если известно, что только один т нихлжет.

10.С помощью метода резолюций доказан, чю следующ

множестводизъюнктов невыполнимо: 1/V i (2vi?, fV& QvR, 1R.

доказать, что следующее множество дизъютггов невыполнимо:

a) PvQ-sR.		1/VJ? lf l 1ft	6)PvQ, ^Q■,P, lPvfi. 1Л
12.	Пусть S ~{P,Q,R,W, 1 Pvl g v U v l W). Сколько резольве
будет порождено из S методой васышенпя уровнл яо того, как будет
ПОЛучеН [Г/СТОЙ ДИ4ЪЮНК1')
13 Длл 5 ={Р,е,ЛЖ. 1 PV IQ A R -.A Щ получил пустой дизъ­
юнкт, используялок-резолкцию.
14.Для ^ ={ Pvgvft 1 Pv./!,			1Q, 1 R\ получить пустой дазь-
icihkt, используялок-резолюциго.
15. Найти сколемовские стандартные формы для следующих
формул:			б) ^Sy4s(P(Ky) =>Q{xj));
а) ЭхУ^гШх.у)
в) V	*	3 =>й(*.г»;	г)=>«*,*»;

132

16. Найти сколемоясхке стандартные формыдля следующих

формул:
<0 ЗхЭ«Уг?(д;.у)		5) V*GM =эЭ*Р(х>;
э] '/z'/yiltf.Ptx.yi&m:'» =»3vg(xy,v)):		г)	=>3^G(*.>B;
A) Э*у>(*)	a] 3x('i(3yP(*,j}) =(3z0(r)=«(i)));

ж) V \l^ !P (y iy,;)k(3uQlxu) =s3vC(y,u))).

17. Определить,унифицируемо ли калошели из следующих

множеств:
a){P {d ).m h		б! № ? № )) } ;
B){P(a),P№))>;		r)(f(e,*)P(e,e)};
д)	Р(х.у)},	е) Ш в).гМ ), СОчО):

ж) {?{*,!,У), Л В Д Ч ?(Я,»,И)}.

1В.Найт общийунификатордляследующегомножестваформул:

{Р(ахШ )),Нф)А^}))

19. Дано множество формуя: №(Р<*)г*(б(.<)ММ)), =*(?(*№))).

Методам резолюций вмистггь, будет пи формула Эг(5(дг)&Д(х)) логическим следствием из заданного множества формул.

20 Дано множество дизъюнкт

{Р(о), 5(о). Ma.y)vpfyl lP(*)v'ta, >W v 1ОД, fc)v ii(t)vfi(^)>, lEWv^)vCWx))(.

Лок-резолюиисй показать, что данное множество дизъюнктов

21. Дано множсстао формул:

{ЗЧР(х)& V> (ЙМ=»Л(ду»), '1КР(*)^№у) ^ Ш ) ) } - Методом резолюции выямште, будет ли формула

V^QIxj^ IS(i)) логическим следствием из заданного мкожестаа формул.

22. Методом резолюций показачь, что формула V*(3^(y)fiЩх,>))=. =!*№)&%*»)

является логическим следствием формулы V>(S(y)»C(^)).

133

23. С помощью метла резолюций установить, правильны следующие силлогизмы (модусы) Аристотеля: Barbari, ferio, Baroco. Напомним, что гласные, участвующие в приведениях названию сил* логизмов, определяют вед силлогизма(см. § 11),

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

та т проиллюстрироватьдиаграммами Эйлера-Венка:

1)некоторые Л суть В Ни одно Зне есть не С. Следовательно, некоторые А суть С;

2)все А суть 8. Ни один С не есть не В Следовательно, ни один Сне ест, А;

2)	некоторые Л сутьне В. Всс не С сутьВ. Сдсдоаателыю, не

торые^ суть С;

4)все А суть В. Ни один С не есть Д Следовательно, все А суть не С;

5)некоторые не В суть не А. Ни одно не В не есть С. Следова­ тельно, некоторые м л сутьне £.

Глаия 4. ДЕДУКТИВНЫЕ ТЕОРИИ

§ }. Понятие об эффективных н полуэффектпвных процессах (методах)

Пусть имеем элементы некоторого класса ОА, чисть из которых «ожбт обладать некоторым свойствам U. Будем считать, что задан эффективный процесс (метод), если: 1) есть предписание, опреде­ ляющее последовательность лрепбразовакий, которые надо применять одном дру!нм кэлемент} из И; 2) еслиэлемента из Жзадан, предпи­ сание однозначно опреаечяет такую последоэптелыюсть преобразова­ ний, что за конечное число шагов выясняем, обладает х свойством U

Таким образом, если задан эффективный процесс, то для любого элемента из 9Лза конечное число шагов выясняем, обладагг заданный элемент свойством Uили нот,

В отличие от эффективного процесса по.чуэффвктивньш процеьсоп считается некоторая ирпцедура, которая не всегда позволяет для произвольного элемента г щ Я за конечное число шагоп выяс­ нить, обладает х свойством U ага нет. Точнее будем считать, что задан полузффектившй процесс (метод), если выполняется указанное

условие 1), а вместо 2) - следующее условие1если элемент х из W

задан, предписание однозначно определяет такую последовательность преобразований, что если* облапаетсвойством и, то за конечное чис­ ло шагов это выясняем, если же >не обладает свойством U. то, воз­ можно, мы не сможемотовыяснитьзаконечное число шогов,

Припер эффективной процедуры. Пусть 5И={!>2,3,...}. Число я может быть квадратом какого-либо числа из М, назовем зто свойством

V.Эффективной процедурой для выяснения, обладаетли элемент * ич

М свойством L', может бытьследующая. Берем числа 1,2._jc и, возво­ дя их в квадраты, смотрим - равна оних либо нет. Очевидно, что та-

шагов-обладастд: свойством [/либо нет.

Теперь рассмотрим пример полуэффекгианай процедуры. Рассмотрим известный процесс мнпечекия квадратного корня

нэ положительных действительных чисел:

	л/328 —13.1...
28	I 228
361	I	400
1	!	361

Ясно, что если для заданного числа а число -Jo является рацио­ нальным, то рано или поздно заметам период. Еслиже -Je us является рациональным числом, то, сколько бы долю ни продолжались эта вычисления, мы не сможем на их основе сказать, будет когда-нибудь период или нет, т е. является \'а рациональным или нет. Таким обра­ зом, Эта процедура (Гудет полуэффективной процедурой для выясне­ ния рациональности -]п.

126

§ 2. Дедуктивные теории

Дедукция (от летейского dsductic-выведение)-форма мышле­ ния, когда заключение выводите* чисто логическим путем (т.е. по правиламлогики) го некоторых Даяны* посылок.

Индукция (от латинского inductioнаведение) - форма мышле­ ния, посредством которой от некоторых фактов млн истинных выска­ зываний переходят к некотороишнотезе(общему утверждению).

Примерыдедуктивных рассуждений.

1.Все люди смертны. Сократ - человек. Следовательно, Сократ смертен.

2.5' 3, 3>1, следовательно. 5>1.

Примерыиндуктивных рассуждений.

J. График функции>>-2*+3 - прямая, графикфупкшчу=Зд:+1 - прямая, следовательно, функции вида у-кхлЬ имеют графиком Пря­ мую. Полученная здесь гипотезаоказывается истинной.

2. Рассмотрим предположениеФерма, что число/г =2.1 +1 явля­ ется простымдня всех п. Прик-ОЛ,2,3,4 получим, чтор равно 3, 5, 17, 257, 65537 и все они простые числа. Но Эйлер показал, что для л=5 р - 4 294 967 297 и это число яштястсг составным (делится на 611). Следовательно, это предположение Ферма неверно.

3 Возг.меч формулу Эйлера Л->!-х-г4!. При каждом * -1,2,3,...,39 число N является простым, следовательно, числа N (ука­ занного вида) являются простыми. Сформулированная здесь гипотеза иевдрш. например, при1=-40 число iV-41*, следовательно, оно не явля­ ется простым.

Таким образом, заключение, полученное дедуктивным спосо­ бом, уже не нуждается в доказательств. Заключение, полученное ин­ дуктивным способом, требует дсквштепьгтва его истинности. Будем

137

рассматривать дедуктивные методы. Ваедем понятие дедуктивной теории.

Дедуктивная теория считается заданной, если эдан язык этой теории и из множества правильно построенных выражений (предло-

зом множество теорем. Подробнее: дедуктивная теория считается

1)задан алфавит и правила образования выражений (слов)

I)заданы правила образования формул пива (правильн построенных выражений);

3)из множества всех формулязыка выделено некоторым деду тивным способом (который будет описай) подмножество Г, элементы которого будем называтьтеоремами. В зависимости от того, как мша-

дедуктивные теории.

ПодмножествоТможетзапинатьсяодкимизследующихспособов I. Задаются аксиомы и конечное числогтраеии выводов:

а) Н5 мгюжестаа формул (правильно построенных выражений)

чами (аксиом может бытькакконечноечисло, так и бесконечное); б) задастся конечное число правил выводов, используя которые,

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

Если :еоремы заданы указанным образом, т,е. гаданием аксиом

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

ете*формаажшаксиоыоктееноб теориейилиформальным (погичс-

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

Аксиомы не доказываются не потому, 'то могут не беказыдаться, в потому что немогутSum*, докюаны.

2. Задаются только аксиомы, а правила выпила считаются из-

а) из множества формул (правильно построенных выражений) выделяется птдчпожестпп -|, элемента потерею вызываются акеиоМамн 1аксиом можетбыть какконечное число, так ибесконечное);

б) правила вывода (методы доказательства) теорем считаются известными из опыта изучения математики.

При таком задании теорем дедуктивнойтеории говорим, что задана полуформальном аксиоматическая теория

3. Аксиом нет, а задастся только конечное число правил выво­ дов, с иомишыо которых и получают теоречы. Тахую дедуктивную

Случай, когда кет аксиом и пет правил вывода, не расематрчва-

Прниеиаа одни из указанных способов задания теорем, будем получать множества теорсч Т\, Т; и Т-, соотв&гстаенно. Сразу возни­ кают вопросы: когда эти множества Ти Ti, и Г. совпадает? Когда не­ которые из Г;, или Т„ или Т\ дедукгнвной теории В совпадают или покрывают класс "истинных" формул теории Ви при условии ^впа­ дения для В п Ви алфавитов и формул. Эти вопросы оказываются не Bcei;wпростыми нв рамкахэтогокурса затрагиваются незначительно.

§3. Свойсгвадсдукгявныхтеорий

Выберем один из трех способов задания теорем дедуктивной

Может оказаться, что множество теорем Г покрывает все мно­ жеств формул (правильно построенных выражений) теории. Иначе, это означает, 'гго доказуема лгобая формула (правильно построенное выражение) и если в теории сеть отрицание, го из доказуемости какой-то формулы тут же следует доказуемость ее отрицания. Следооггелкно, в этом случав доказуем какой-то факт и его отрицание. Ясно, что теории, а которых можно доказать что угодно, не пред­ ставляют интерес.

Дедуктивные теории, в которых множество теорем покрывает асе множество формул (правильно построенных выражений), нааиваKntJ пршаооречиоыми, в противном случае - непротиворечивыми.

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

Пусть множеетпо теорем Г яияете» частью, не совпадающей и всем множеством формул Ф (правильно пострс-гнных выражений), i.e. наша дедуктивная теория непротиворечива Тома можно уже интересоваться, а какую часть Ф занимают теоремь. Для этого ваодап свойство полноты теории. Свойство пошиты дедуктивной теории характеризует достаточность теорем для каких-то целей. В зависимо­ сти от того, для каких целей должна быть достатотао теорем, будем * дальнейшем вводитьразличные понятия полная,!.

Рассмотренные свойст*а - непротиворечивость и полнота, яв­ ляются важнейшими свойствами дедуктивной ]еории. Кроме этих свойств, имеется и ряд другу* свойств. Рассмотрим euis два свойства дедуктивной теории.

Лезшисимосгнь аксиом теории. Отдельная аксиома дедуктивной теории называется независимой, если эту аксиому нельзя вывести в этой теории иг остальных аксиом. Система аксиом называется неза­ висимой. есликаждую изчихислшя яывветя т остальных.

Разрешимость теории. Дедуктивная теории называется разре­

шимой, если а зтой теории понятие теоремы эффективно, т.е. сущест­

вуетПравило (метод), позволяющеедня произвольной формулы зако­

нечное числодействий выяснить, является она теоремой или нет.

140