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

с) А рмгстес В; ■«■) еслиА, то В и обратно.

8. Составьте списки выражений, которые чогут 5ыть ss символами: a)"U; ti)AScB', в)А ’5; г)A^B; я)АяВ.

9. Явл:	а проп
а)&А;	6)
8)((''QV« ,	г) ((('lQ=?fl3=B);
д) 0*=(Т4));	J) ('(TdrtO)»'?
10. а) Пусть значение пропозициональной формы (AsBj есть И.

Что можно сказать о значениях пропозициональных форм (.4=(1 В)) и ((«)-Я)7

б) Пусть значение	пропозициональной формы (Л=Я) есть JJ.
Чтоможно сказать о значащ* (4^1 В)) и ((“Й>й|?
И. Hatha значат* А, В, С, если;
а) (\/1£Я)У=Л-:		б) (V=»(l В))гИ;
в) ( (Х л Ш ^ У г^ гЛ ,		г) {А„(ЛАВ))-/?;
д)((4&Д).('й«С))=/7;		е) А=В&СчА-Л;
ж) U0lA&B))*C)‘li,		з) [ЩА&Иу.>С)-АгЛ,
\(Cv(l4))=J/;		*LMv(lc))-J:
И) г (А-В)-Л,		к) r({[A&I!)-X:)ssAJ=Pf,
•(iv O -Л;		|(,М 1£))=Л;
яН (А=>С\В))-Л,		м )|(А=)С)-Л,
\({А&П)=0=И,		\(АШ)=И.
11. Состаиьтг таблиц!,! иетшпювти для следующих пролоаииио-
мльнькформ:
i) (А-,(В^А}),	6) (Мгэ(г^.С))-,(М^В;=.Ы=?0));
»)(((15)=>й))^(((1Д)=>Л)=»В)); г)((.4^>BJ=>Q;
.>0 <А=*1*=>С))\		е) <М=>«-((1 fl=>(U)));
*) a A ^ v i O m m		ю «л=>.в>«14>=^т .

!3. Укажите, какно нз пропозициональных форм упражне­

нии !2 являются тавтологиями и какиа противоречиями.

14.Доказать, что вели 4 - тавгэлогияГто тавтологиями являют­ ся (AvB) и {Й=>А), гдий - произвольная пропозииканаллная форма.

15.Для данных пропсиш[детальных фирм составить таблицы истинности. Определить, для которых из них истинностные значении всей формы можно записать 6ai промежуточны* выкладок (используйте результатызадачи 14):

a) ((A=>A)vBy,	б) (C^(AsA))\
в) (А=>(МУу:	г) ЦА=,А)=,АУ,
д) (Л=>Ц=А)У,	е) ({{Am A'eiYM A^Aiy,
ж) (((c:&D)v^&fi))^(flv(lBj));	э) (,U'AMU)))&{CwUv(IC)))y,
и) ((0еЛ)&{С^.С)&(Л'>(1 1 )));	к) |[(Л&Й)й(Л&/<))v(lЛЛД)),.

16. Составить таблицу истинности для истинностной функции, чаздсяисей от трех переменных, если известно, что функция истинна

а) все переменные принимают одинаковые значения; б) истинны значения большинства переменных этой функции;

в) истинно значение одного и только одного из ее переменных; г) каждая переменная принимает значение, отличное от значе­

ния соседней переменной.

17. 1). Записать в сокращенной виде. т. е но возможности опус­ тив скобки.

а)(«M)=KBv<lC>}M(3fc<MlВ»>:

5) ((Mv(l

ч) ((/io£)^(C:S(lq));

г) (((M>S)&(S^TQ )>M);

д) Ш =»(1Л)И В))чСЩА^В)У,

е) (/=>(&»(СэО))).

42

2). В приведенных далее сокращенных записях пропозицио­ нальных форм яосстакоиить опущенные скобки:

а) АгВ\АОЫ=>'А',

б) 1 й»Я=СеС&£); в)Л=Я=Лу1£&Л; rj Л=>Й:=Лл&£уС;

д) AsH^r>Cv\i(i\ BvA\

в) A&lSJCstA^AvAiB.

13. Найти простейшие (содержащие минимально возможипе число пкожлашй пропозициональных букв) равносильные пропояициоиапьныг формыдля нщнких пропозициоиалмшх форм:

a)ASL(AVB)VA&.B-,	б)М4&Й;
a) livAStB:
д}1л&(ЛуВ);	t)AvA.\/ASLA&B8cC\
ж) A&/&.HvB^Ab.e-/BvA&4&C;	3)(^v(Mlt])v( Й&(1 fry(O);
	K)/I&Sv(C=5C);
	m)A^ASA=^A=>A.
19. 3«коны де Моргана для	п переменных можно записать

Для п~2 эти равносильности доказаны (например, с помощью таблицы истинности). Доказан, их для любого и индукцией па числу

20.Докамчъ. что AvB&CSiD равносильно

{AvB)&{AvQSc{AvD).

2\. Доказать, чтоЛу(& £,) равносильно & (/ivS,).

43

22.Доказать, чти/!&( ./ /),) равносильно v (^М )

23.Запишите Л=» I (Й=>С) без csnxn =>. Запишите ответ так, чюбы связка I не стоялапередогабкамв

24.Запишиче (В^С)^]4 5ез связки =«. Запишите результат вформе, не содержащей 1 перед скобками,

25.Запишите каждую из следующих пропозигионалышк форм

без пропозициональной связки = , а окончательный результат баз

пропозициональнойсвязки 1. стоящей передскобками:

а> (Лу1 Я)=С;

б) (^-^)=.(15==.14¾

о) {А=,К)^>{ЛкВ=>А).

26.Выразите А^з{2^С) баз =г, = и отрицания, стоящих перед скобками.

27.Для пропозициональной формы "U vB vt найдите рапно­

сильнуюей форму, содержащую толькосвязку =*.

28.Для пропозициональной формы ^vflvC найдите шесть рав­ носильных гй форм, содержащихтолько связки 1,

29.Для пропозициональной флрмц (ЛзЗ)=С найти равносиль­

ную, содержащую: а) только связки 1, v ; б)' только связки 1, &;

30.Дляпропозициональной формыA^S=>CнаЯтиравносильную, содержащую: а)тмько связки1.v; б)только связки!,&.

31.Найти простейшие равносильные пропозициональные фор­ мыдля заданных пропозициональных, форм:

a)AvA&B&C&D:	6) Aklfoli-//!;
в) (livflO&BvB,	г) (jtoB*C)=5vTft
д) AvA&B&B&iDvAvA);	е) AvA&H&.B&B^8kC&AvA;
ж)АгАзА;	3)АаЛяЛшЛ:
и)А^А^А^Л ; ,	к)АЩА=*Л)=>А',
л)A=>(Ar?,(A^iA)).

32. Для пропозициональной формы A=t-e&-C найти равносиль-

о) ТОЛЬКО СВЯЗКИ 1,35.

33. Упростить, насколько это кьмюкно:

a) {Ave'/Q&,[AvBv]C);						б) (CvD-Л Е)&Ci&.(4vlDvl Е );
в	D)	A E & D & C)		;
д)						*)^v(/v"U)v(CvlC)vC;
ж) C&[\^CvD)&ESi(E'AВ),						з)C& V/C//1vS;
к	)	c	&	t c	&	f i ) ;

n).^e&CVfi&CS;^v4=>8vl8; M) flwl SvC&flwli"U.

34.Доказать, что C8*smi v недсетаточко для выражения любой ИСТИННОСТНОЙ ФункЦП]I.

35.Доказать, что каждая из пар связок (=>, v), (&, ■) не является достаточной для выражениилюбой истинностной функции.

36.Показать, что для выражения любой истинностной функции

=>в) ;связки ■ г); связок v ,

37.Следующие прппшициоиальиые фирмы привести к д.н.ф.

ик.н.ф.:

а)Л»((,4=В)=>В);
б)	({A-B)MC-r/))&.((MQ-( CSLD))\
в) (Л=>В)-((А&Ср>ШС)),
г)

д) ({А\^ВуЛ/.=>С))-ть(А-Ы1А'-1С\)

38. Для заданных пропознцнокальшхформ:

!) найдите д.н.ф., к.н.ф.; 2) выясните, является ли заданная фор­ ма выполнимой; 3)иайджес.д.н.ф и с.к.н.ф.:

S)A MBV C;		б) Ы=>].£/)&С;
в	1А*АъА*В)&) .С',	т) (A=>A=>A=,H)vC;
д) Лв.4=Я/С;		е)(А=.Б)^С=>~\А.

Глава 2. ЛОГИКА ПРЕДИКАТОВ

§ I. Понятие предиката

Логика предикатов представляет собой развитие логики выска­ зываний. Она содержит в себе ясю логину высказываний, т.е. элемен­ тарные высказывания, рассматриваемые как величины, которые при­ нимают значения Илибо Л. Но помимо этого, язык логики предикатов вводит в рассмотрение утверждения, отнесенные к предметам, т.е. производится бопее детальный анализ предложений. Рассмотрение логики предикатов вызвано тем, что логика высказывая™ не позволя­ ет моделировать рассуждения вс« видов, в частности, рассуждении с использованием понятий «каждый», «некоторый». Отметин, что ло­ гика предикатов тоже ке охватывает всевозможных случаев рассуж-

дечий. например, когда нужна исследовать рассуждения, истинность зсоторых зависит от вреиенк, или вводягеи понятия «должно быть» и «может быть» ит.п. (подробнее в га. 5).

Пусть Ж - некоторое множество предмгтов, а\,аь ~ какие-то определенные предметы (элементы) и-i этого множества. Тогда череч А[а,) будем обозначать некогорое высказывание о предмете <Ji, п через Atdj ) - то же высказывание о предмегг а?. Например, если Ж есть множество всех натуральных чисел и Я|=3, и2=8, то А(а,) может Обозначать высказывание "3 - простое число". то1да Л(аг) Судет

Как и в логике высказываний, будем рассматривать эти выска­ зывания только с той тошен зрения, что они представляютлибо истину (И), либо ложь (J7). При этом значения высказывания А{а|) и А(аЦ могут быть разными либо нет в зависимости от выбранных предметов а-, и aj. Следовательно, в отличие от логики высказываний будем считать, mu значения И иЛ ставятся в соответствие определен­ ным предметам или группампредметов.

Если »с не будем фиксировать элемент, например, рассмотрим А(х), гдеi - любой элемент и$ flf, то получим некоторое предложение, которое становится высказыванием, когда х замешено определенным элементом из М. Например, если Л является множеством всех Haiyральных ’мсел, то А(х) мажет обочначать "л •• приетое числа". Уть предложение становится высказыванием, если х закенть числом, на­ пример, "1 - простое число", "4 - простое число". При этом получаем выикаэмзааия, которые кстикнн, либо ложны. Следовательно, А(:) nopoauaei фушщию, область определения которой есть чножесгво И, а область значеннй - множество {И, Л). Огмешм (еще раз), что А(х) становится высказыланием при замене х фиксированным (определен-

Предложения, в которых Имеются две и более переменных, бу­ дем обозначать, например, А(х,у), 5(едг) и т. п. При этом х,у, г про­ бегают все множество Ж, э.А(х,у), Дед,г) при фиксированных х,у, г

47

становятся высказываниями, следовательно, принимают значение И либо Д. Например, пусть М есть множество всех действительных чи­ сел. Рассмотрим предложение: "*делится нацело м у . Если вместод: и у подставить конкретные числа из й, получите.» высказывание истинное либо ложное. Так, при i”6, >“ 3 высказывание "6 делится нацело на 3" - истинное, а при *“5, у=1 высказывание "5 делите* нацело ка 7"-ложное. Рассмотренное предюжение "i делится нацело на у" можно обозначь, например, через С<х,>-). Такого типа предло­ жения, порождающие функции одного или нескольких переменных, будем считатьпредикатами.

нне об элементах некоторого заданного множества % которое (пред­ ложение) становится высказыванием, если все переменные в нем за­ менить фиксированными элементами из Ж; высказывание тоже будем считать предикатом - нуяьместиым предикатам. Часто вместо "предикат от п переменных" говорят "п-местныйпредикат".

Упражвекне. Пусть на множестве % состоящем из т элемен­ тов, задан З-иестный предикат Л(:у,г). Сколько выска-швакий об элементах Ж можно получить, фиксируя переменные предиката

Введем операции над предикатами. ПустьА(х\ В(х) - заданные на Ж предикаты. Вудеч считать, что ”U(x) то*е определяет предикат на Ж, причем при каждом фиксированном х-Ь значение вы­ сказывания "к(4) противоположно значению высказывание Л(Ь). Так же будем обраговывать из предикатов А(х), В(х) новые предихаты с помощью операций &, v, =>, s, Например, A{:)St3(ii) обозначает пре­ дикат, который при фиксированном Х'Ь превращается в сложное вы­ сказывание A(b)&.R(b), образованное га высказываний А(Ь) и 8(b) со­ единением их связкой *. Точно также будем образовывать новые предикат из произвольных многоместных предикатов. Например, /)(х,у)эС(г,}|^) обозначает предикат, который при фнксир5ванных переменных: х=а, у° b, :-с (o,i,ce Ж) превращается в высказывание ^(e.b)=>C(a,fj,c). образованное изявух высказыванийА[а,Ь) и С(а,Ь,с) соединением их евнкой

§ 2. Кванторы

Введем специальные обозначения. Пусть Ж - ынгмсество, Р(х) - определенный иа М одноместный предикат. Тогда выражение tfxP(x) читается: "для всех! Дд:)" или "для зсехх выполняется Р(:г)", или "для литого х а д " , или "для каждого *?(*)".

Под выражением "VxP(:0" будем подразумевать высказывание истинное, когда ?(*) истинно для каждого х из Ж н ложное - в про­ тивном случае. Симвил \/х называвit» квантором всеобщности.

Выражение ЗхР(х) читается: "существует х такте, что Plxj" или "хота бы дла одного х Р(*)", или "для некоторого (некоторых) х Р(х)". Под выражением "3x?(t)" будем подразумевать высказывание, кото­ рое истинно, если Р(х) принимает значение И хотя бы для одного значения переменной хе % и ложно, если Р{х) для acts значений переменной х принимает значение Л. Символ I t назыэаегся кванто­ ром сущестошчя. Квантор I t будем называть двойственным

кквантору Vs, и наоборот.

Влитературе применяются и другие обозначение, Так, вместо

ЧжР{х) пишут АхР(х) или Л,Р{х), а вместо 1сР(>) пишут VxP(x) или

V^iX), или ИхР(х).

Введенные обозначения позволяют записывать предложения в символической форке, которая оказывается более удобной для анализа и логических действии над этими предложениями. При символизаций языка требуется определенная аккуратность и правильное понимание контекста. В естественной языке частослово "все" опусхается. Например, предложение "рыбы дышат жабрами" означает, что все рыбы дышат жабрами или что каждая рыба дышит жабрамк. Поэтику при символизации необходимо ввести кяпнтор пбшипста. Таким образом, гели положить дня множества живых су­ ществ, что Д(*) означает "х - рьйа", a G(r) - "х дышит жабрами", то имеем V^№)=»G(x)>

Но в то же время не в каждом случав вггречающиеся а предло­ жениях слова "все" понимакхгса как "каждый". Например, предпоже-

ние "пег песчинки образуют кучи пуска" не огкача<я, что каждая пес­ чинка образует кучи песка, следовательно, при символизации нельзя употреблять квантор Vx, как ЭТОсделано g предыдущемпримере.

Вязыке слово "все" имегг два значении: "любой, каждый"

и"все вместе". Квантор Чх применяется для первого значения.

Из сложенного следует, «то "УлР{х)4 спужт обозначением для

следующих высказываний:

для всехх выполняется (имеет место) ?(*); для каждого х выполняется(имеетместо) Р(х); для любого х выполняется (имеет место) Р(х);

для произвольного х выполняется (имеет место) Р{х), каково бы ни билог, выполняется (имеет мест) Р(х).

В языке слово "некоторый", так же ш и "все", часто опускается.

Например, предложение "люда побывали на Луне" означает, что некото­ рые люди побывалинаЛуне,

Символическая запись ЪхГ(х), как мы знаем, означает, чго для

мести PU). В естественном же языке слово "некоторый" иногда употребляют в смысле "не все". Когда говорят "некоторые сту­ денты отличники", подразумевают, что некоторые, но не все студенты отличники. Следовательно, имеется в аилу: "неверно, что все студен­ ты отличники, но некоторые - отличники". Тогда, если С(х) означает "х - студент", 0(я) означает "х-отличник", получим:

(1Уа(ОД =>«*))) &Э ПОДЛОМ).

Итяк, слово "некоторый" имеет два значения: первое - "некоторый, но может быть и все", второе - "некоторый, но не все". Символ 3* обозначает первое. Следовательно, запись 3хР(х)

служит обозначение»! для следующих высказываний, для некоторых.! (имеетместо)P(jr); существуетх, для кпороги Р(ху, найдется х, для когорого Р(с),

хотя бы для одного* (верно) Р(*);

J0