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

л и	р	q<</-p;
Al)	p-q-i p\
Aj)	' p-< p - p \
A4)	(p	q)r< p - ( q -	r);
AS)	p<	q) • (g - r )4	(p^ /),
Л6)	( f X
A7)	p ■(p-t q) *q.

Правила вывода следующие.

ледтных друг другу выражения взаимозаменяемы.

Р2. Вместо любы* переменных р, q. г,.. можно подставить про­ дольную формулу.

РЗ. Введение коныонкиин из А. Я выводится А-В.

Р4. Modus pures со строгой импликацией: из А и А-< В

F.cjsh добапигь к аксиомам системыS! аксиому А8) о(р*<?)ч Фр,

то получается система S2 Льюиса, которая считается системой стро­ гой иыиликпиин. Льюисом были предложены н другие системы мо-

Отмстиы, 'п-п в классической логике, например, m лжн следует, что угодно. Это иногда противоречит нашему содержательному, прак­ тическому пониманию логического следования Для устранения этого парадокса материальной импликаиии Льюис и создал свои системы са строгой импликацией. Но появились парадоксы н для строгоЯ импликации. Для исключения парадоксов строгой имгаикации Ф. В. Аккерман построил свою систему мпдо.юнойлогики.

Кром« систем Льюиса и Аккермана, существуют системы Лукпсевича и некоторые другие.

На втором этапе развития современной модальной логики били построены так называемые семантики возможных миров. Основным понятием в них является понятие возможного мира. Под возможным миром понимается мыслимое положение дел или возможный ход раз-

211

Верьминуте пккушеИОудвсчастливтеперь!

ОмярХгАям

§ 7. Временные (темпоральные) логика

Временные (пшшоральпые) лотки вводят ПОНЯТИЯ «быяоя,

(«есть», «Судет» («рдльше», «одновременно», «позже») и считается, что истинностное яначение высказывании может быть разным в раз­ личные моменты времени, Например, «евмолег «гтит» истинно во все те моменты времени, когда самолет летит, и ложно во все те, копи

Отрицание высказывания истинно во все те времена, когда сама высказывание ложно, и ломе во вое те времена, кегли само утвевждекне истинно.

в которое истинно каждое m этих выовааывгитй, п ложно вл всякое другое врем*.

Остальные операцииопределяютсячерезотрицание нконъюнкцию. К высказываниям могут быть применены тамке, так называе­ мые, временные операторы - Р и F. Оператор F образует будущее время: Tq читается «будет иметь место случай, что qn или «будет до

(слабос будущее).

Используа Р иF, определяю! сильное прошлое и будущее;

def

Ид = ~Р~д - всегдабыло <?(сильное прошлое);

212

Oq = ~F~q - всегда Будетq (сшьное будущее),

Последние покати» сходны с принимаемыми и мпдальной лоп'- кг понятиями необходимости а воэыожносэи.

Отметим, --по первые системы темпоральной логики были по­ строены А. Прайором в 1454 и предназначались для реконструкции понятий возможности и необходимости.

Первая логика аренгчи, построенная Прайором, представляет собой пропозициональное исчисление, дополненное формулой Fq («будет qn), следующими аксиомами:

A I)Flp^q)BFpvFq\

А2) FFpDFp

и правилами ныаода:

R1)F [ GA,

КХ) (АЩ ]■ (FAsFB).

Зтя системя прелнашачалась для решения вполне огтредвленной задачи - реконструкции иредставлмшй Диодора иг Меоад о возможности и необходимости. Диодор определял возможнее как то, что или является, или через некоторое время будет ИСТИННЫМ; невозможное - как то, что не является и никогда не будет истинным; и необходимое - как то, что иявляется, и всегда будет истинным,

U няст.ищ“е время построены различные темпоральные логи­ ки, оперирующие понятиями проголое, наетоашее н будущее. Кроме того, выявлено, что временные логики и модальные логики взаимо-

§ 3. Вопросы п темы зля самопроверки

4. Что общего в гренэиачнык логиках и двузначной логике1? Какие различия между Ними?

5.	Многозначная (/i-значная) логика Поста.
6.	Многозначна* (Лг-знячнал) логика Лукаееаича. Бесконечно-
знауные логики, пример введенияопераций в них.
	Понятие нечеткогомножества.
8.	Нелегкие высказыванияммакеимннныестирании надними.
9.	Понятие о лингвистической нечеткойлогике.
10.	Модальная логика.

1 i. Временные (темпоральные) логики,

§ 9. Упражнения

Рассмотрим £-эначную (4 i 2) логиху Поста, где, как уже указы­ валось, имеется множество высказываний (переменных), каждое я:ч которых может принимать одно из значений 0,1,2.....Л-1. На атом множестве высказыванийвведены операции:

1)х =д+1(mod к} - циклическое отрицание или отрицание По­ ста, здесь + - слсияние по модулю к: выражение .г будем обозначать (вдайной работе) также через I*;

2)iVi=fc—1-х- отрииаНигЛук&севича.

eMHX“ W’ m-0,1.... i-l.

функция h.U) называется иногда характеристической функцией

иобозначается mki*;

4)i&^-min(.t у)-конъюнкция;

5)xv v) -дизъюнкция;

6)& у- хху (mod £}- произведение по модулюА;

7)х+у-х+у (mod к) - суммапо модулюк,

Вупражнениях 1-10 предполагается чтозадана к-значхая {кг!) логика Поста.

1. Выяснить, вылолккютсн ли следующие соотношения: a) V(«e)-*; 6)VU)^t, в) (i»v)

2. Выяснить, выполняются ли следующие соотношения: а) Сюу) +-1у*&.у: б) W(lx-iy>"(.V*)-KA‘3');

В)1М1**Ъ)И№ МЪ).

3. Доказать, что каждая-функлия/Гх|...,J :„) ^-знатной (te2) ло­

гики Поста представима в виде:
^ , ) = - flv д	.
где дизъюнкция берется по	всевозможным наборам значений
{01,1¾....,а„) переменных	Правил часть такого представле­

ния функции называется совершенной диэътнктиниой нормальной формой (с.д.н.ф.).

А. Построитьс.лн.ф. для следующих функций: k~V, 0)1 хгъу, к-2: ъ) .VI, /г-5.

5. Выяснить, полнали следующая система функций:

{О, 1,2.....i- l,/](*), АО), МО,..., М О , x&y,.xvyj.

5(*)“ 1+ шах {х+а}.

7.Выяснить, образуют ли полную систему следующие систе­ мы функций:

1){я, 1 *, Ш . AM, «*).... hyb), х&У, xvy), здесь

и(0< ий Ы ) -любое целое неотрицательное число, но превосходящее

2)<1, А'х Ь(х), /,(*). а д , ..., /,.,(*), х&.у, ivy};

3){0,1*, .<•%, rvy}.

8.Построить е.д.и.ф. для следующих функция:

в)х->у,к=3.

б)jv(1 *&)>), 4-3.

215

9. Выяснить имеют пн местосоотношения:

а) х-у-х-хку; б) (№)-(Ь'у)-у-х; в) x-y~(x&yi-y.

a)»<(y^г)=(IX^}+(I>a),^=2.•	6) ху.{}'*г)^(хху)-Цху;), *=3.
11.Постройте таблицы истинности s логиках I* н L<Дукасевича
для следующих выражений:	б) .t&'l х\
a)*v'k
b)х'Л~\х&у)\	г)
д) х&(1ryy);	e)xvlwil*.

12. Пусть для нечетких гюдмножесгвA", 3* и С*, определенных на универсальном множестве £/^[0,10], их функции принадлежности

равны соотвегсгвенно:
^ ,(х)=Т+7‘	и

Запишите в аналитическом виде и нарисуйте графики функций принадлежности для следующихнечетких подмножеств:

а) А*, В*. С*;	б) А*иВ* AKJ С*;
в)Я*иС*, ,4*оЯ*иС*;	г)А*ъВ', А*пС*-,
д)[A’n B ’)vC--,	е}А*г С *.

13. Нечеткие подмноавсгваЛ* 2* и С* на универсальном мно­ жестве ?>[0;сс) заданыих функциямипринадлежности соответственно:

"-“ ■ТТТо? “- “ -[н-к-Г" '

Упорядочите по включениюнечеткие подмножветва.4* В \ и С*.

14.Докажите, чтодля нечетких подмноягесгв А*, й* и С*, с вве­ денными операциями дополнения, сИтьедикенкя и пересечения, выполНИКчсязаконы: а) дистрибутивности; б)да Морг.шв; в)поглощения.

15.Пустг. нечеткие подмножества А“ и Я* заданы с помощью таблиц в §3, Запишите в виде {5.6) следующие нечеткие подмно-

ilA K jS * б)/*п Я \ в)А\>/В"г>7*)- г) I ' u й*.

Глава 6. ТЕОРИЯ АЛГОРИТМОВ

Теория алгоритмов является одной из ветвей (разделов) математической логики. Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Основания математики, алгебра, геоме<рии и анализ остаются и сегодня одной из основных облаотай приложения теории алгоритмов. Другая область ее приложения возникла в 40 -к годях XX в. в связи с созданием быстродействующих вычислительных машин. Наконец, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики к философии.

Вытснгкеийяоск, носохраняймед. ЧпъьтПр;-.та»

§1. Неформальное понятие алгоритма

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

задач некоторого данноготипа.

Прос|ейшими алгоритмами являются правила, по которым выполняется та или другая из четырех арифметических операций в десятичной системе счисления. Само сло&о алгоритм (алгорифм)

происходит от иметги узбекского м&тамагнка Аль-Хорезми*, который в IX веке систематизировал правилаарифметических операций.

Рассмотрим правки сложения целых чисел в десятичной системе счислевия. Этот алгоротм перерабатывает выражение, записанное с использованием цифр 0,1,...,9. Результатов является выражение, записанное с помощью цифр 0,1,...,9. Таким образом, имеем п|)оиелуру преобразования некоторых символьных входов (цифр, означающих мшаемые) в определенные символьные выходы (цифры, означающие еумму). Аналогичная ситуация имеет место и для остальных арифметических операций. В общем случае понятно, что алгоритм есть преобразование каких-то зходов, записанных с помощью некоторых символов, в выходы, записанные тоже с по­ мощью символов. Грубо говоря, алгоритм - это цетврминированшя процедура, которую можно применять клюбому элементу некоторою

через конечное числодействий (шагов) соответствующий симвпльнь'Л

Существенными чертами неформального понятия алгоритма оказываются следующие.

1- алгоритм задается как набор инструкция конечных размеров, т. е. его можно олисягь конечным набором слов и специальных символов;

2 - имеется вычислитель, например человек, который умеет обращаться с инструкциямии производить вычисления;

3 - алгоритм имеет некотороечисло входных данных, 4 - имеется возможность дли выделения, запоминания и повто-

5 - ДЛЯ каждого данного входа вычисление (преобразование входа) пронзаодится по данным инструкциям;

6 - е помошыо алгоритма получается одно или несколько

Легко заметить аналогию с цифровыми вычислительными

С>гме1им, что алгоритм обладает также свойством массовое™, i.e. он применяется цля решениг мхожестиа однотипных задач, й не одной задачи. Т-Ьпример, правила сложения чисел позволяют произаодшъсложение любыхдейсгеитсльныхчнссл.

процесс применения алгоригая к входам (решение задачи е поиощью алгоритма) яаляегся механическим, i.e. процедура преобразования входов не требует для своего осуществления никакой изобрета­ тельности,

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

И.Гсге(Фауст)

§2. Алфавит. Слова, Алгоритм в алфавите. Вполне эквивалентные алгоритмы

Ллфмитон называете» всякое непустое конечное множество символов, а сами символыалфавита называются бутами

219

мою о алфавите В является также словом и в алфавите Л, абряшое верна не всегда.

Кудем говорить, что аюао Р яходшп и слово Q, если

где Л и Р-2 любые, мокет быгъ и пустые слова. Слово Р моют входить в слово Q несколько раз, первым вхилсдвнием будем счишь

Под алгоритмам яалфавитеА понимается алгоритм, окодамки выходами которого являются слова в алфавите А Таким образом, алгоритм В алфавит? А представляет собой потенциально осущест­ вимое прсоСраюсаниг словв данномалфавитеА.

Алгоритм	обсаничзюпя заглавными жирными буквами
(А, В, С,-..).
Пусть Р -	слово в алфавите Л. Говорят, что алгоритм А.
применим к слову	вели применение его к слову Р приводит чера
конечное число шагов к некоторому слову Q. При этом слово Q

обозначается через А{Р). Если процесс переработки (преобразоваяи) слова Р бесконечен, то считается, =гго алгоритм не применим к зтому слову.

Два алгоритма4 и В в одном и том же алфавите С называются

вполне жеившептнти валфавитей (II £ С), еслидля любого слова

Р в алфавите D оба алгоритма либо не применимы к Р, ли5о применимы и их результаты совпадают; 4(F) = В[Р). То, что алгоритмы A v B вполне эквивалентны в алфавите D, обозначается следующим образом:

W*о О: A(P)iB(P).

§ 3. Нормальпый алгоритм (алгоритм А, А. Маркова)

Опыт изучения и применения математики показывает, что ке известные алгоритмы можно разбить на простейшие шпги - элемск-