авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ...»

-- [ Страница 2 ] --

Сформулируем некоторые теоремы, доказываемые в исчислении высказываний:

1) |– A A 2) A |– B A – введение импликации 3), A |– B |– A B – теорема дедукции 4) A |– B |– A B – следствие из теоремы дедукции (при Г=) 5) A B, B C |– A C – правило транзитивности 6) A ( B C ), B |– A C – правило сечения 7) |– A A 7) |– A A 8) |– A ( A B ) 9) |– ( B A) ( A B ) 9) ( B A) |– ( A B ) противопоставление обратному.

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

1. Правило подстановки (ms) Если формула B является частным случаем формулы A, то B непосредственно выводима из A. Другой вид формулировки правила подстановки: если E – выводимая формула, содержащая символ A (т.е. E(A)), то выводима формула E(B), E ( А) полученная из E заменой всех вхождений A на произвольную формулу B: т.е..

E ( В) 2. Правило modus ponens (mp). Если набор формул A,B,C является частным случаем набора формул A, AB, то формула C является непосредственно выводимой из формул A и B. Тогда доказанные правила могут стать новыми правилами вывода. Так, теорему 2 о введении импликации можно сделать новым правилом вывода: A |= B A (читается:

« B A непосредственно выводима из A»).

Сформулируем некоторые общие правила непосредственной выводимости |= и выводимости |–.

Правило 1. Общие свойства символа |=( |–):

а) при n1 A1,A2,…,An |=A1;

A1,A2,…,An |=A2, …, A1,A2,…,An|=An – из набора формул непосредственно выводима каждая;

б) если A1,A2,…,An |=C, то A1, A2,…, An, B1,…,Bm |=C, т.е. добавление “лишних” формул при сохранении непротиворечивости не влияет на выводимость;

в) если при m0 и n0 то A1,A2,…,Am |= B1,…, A1,A2,…,Am |= Bn и B1,B2,…, Bn |= C, то справедлива транзитивность непосредственной выводимости: A1,…, Am |=C.

Те же свойства справедливы для выводимости |–.

Правило 2 введения и удаления логических знаков:

Пусть A,B,C – произвольные высказывания. Обозначим Ф – конечный список формул, быть может, пустой. Правила введения и удаления логических знаков представим в виде таблицы (табл.7):

Табл.7. Правила введения и удаления логических знаков.

Правила введения Правила удаления Операция A,A B |– B (Ф,A |– B) (Ф |– AB) A,B |– A B A B |– A, A B |– B A |– A B Если Ф,A |– C и Ф,B |– C, то Ф, A B |– C Если Ф, A |– B и Ф, A|– В, то Ф |– А А |– A, A, А |– B (слабое удаление) AB, BA |– AB AB |– AB, AB |– BA С помощью этих правил можно доказать другие равносильности.

Пример 6. Докажем справедливость правила противопоставления обратного AB|– В А «пошагово» и проанализируем доказательство:

1) AB, В, A |– В – свойство 1a);

2) AB, В, A |– B – удаление;

3) AB, В |– А введение для шагов 1) и 2);

4) AB |– В А, введение для шага 3).

Правило 3 подстановки вместо элементарных формул:

Пусть B – некоторая формула, в которую входят элементарные формулы a1, …, an;

B – формула, полученная из B одновременной подстановкой формул A1, …, An вместо a1, …, an. Тогда, если |– B, то |– B.

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

Правило 4 о замене:

Пусть СA – формула, содержащее в качестве своей части формулу A, а СВ – формула, полученная из A заменой A на B. Тогда, если |– СA, то |– СB.

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

Логическое следование есть конечная алгоритмическая операция в отличие от логической выводимости.

С помощью подстановок в любых формулах A и B заменятся пропозициональными переменными, либо другими формулами, что не нарушает требований, предъявляемых к теории. При этом логические операции между формулами и переменными сохраняются.

Теорема (о полноте). Формула A доказуема тогда, и только тогда, когда она тождественно истинна.

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

Итак, всякая теорема исчисления высказываний является тождественно истинным высказыванием и, наоборот, всякая тождественно истинная формула является теоремой исчисления высказываний. Исчисление высказываний выполняет задачу порождения общелогических законов как тождественно истинных высказываний.

Пример 7. Доказать, что A |– A.

Доказательство. По теореме о дедукции, эта формула равносильна |– (A A).

Отсюда по теореме о полноте достаточно доказать, что |= (A A). Если для формулы A A составить таблицу истинности, то можно убедиться, что она формула тождественно истинна, и, следовательно, доказуема.

Если A |– B и B |– A, то считать формулы эквивалентными на множестве формул ИВ и писать AB или AB.

Теорема (о непротиворечивости). Исчисление высказываний непротиворечиво.

Множество формул Г называется противоречивым, если Г|– B B. Если Г – противоречивое множество формул, то его обозначают Г |–.

Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы. В частности, независимы схемы аксиом ИВ.

Т.о., теоремами теории T являются тавтологии, т.е. общезначимые формулы, и только они: |– A A – тавтология. Прямым следствием этой теоремы является формальная непротиворечивость и полнота теории T.

В построенной формальной теории T выводимы многие важные для практических целей формулы. Они получаются «перефразированием» теорем с добавлением дополнительных связок (которые называются так же, как и связки булевых переменных:

– дизъюнкция, – конъюнкция):

1) a|– ab, т.е. к заключению можно добавить другое высказывание с помощью дизъюнкции;

2) a, b|– ab;

3) ab |– a 4) ac, bc |– (ab)c – распределительный закон относительно дизъюнкции посылок;

5) ab, a b |– а ;

6) |– a а – закон исключенного третьего.

Для доказательства других тавтологий надо использовать аналитические правила выводов тавтологий через логические следствия.

Например, достаточно часто применяется теорема дедукции Ф,A |– B Ф |– A B, где Ф – список формул, A и B – отдельные формулы. Известный из школьного курса геометрии метод доказательства от противного можно сформулировать как правило исчисления высказываний (Г, A |– B и Г, A |– В ) ( Г А) – правило введения отрицания.

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

Для того, чтобы проверить, правильно ли сделан вывод в дедуктивных умозаключениях можно использовать математическую логику:

1) проверить справедливость заключения, сравнив его с соответствующим правилом;

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

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

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

Задача 1.

Необходимо проверить, правильно ли сделан вывод в умозаключении «Все студенты факультета информатики добросовестны в учебе или талантливы. Если они добросовестны, то систематически готовятся к занятиям. Поэтому, если студенты информатики не будут готовиться к занятиям, то они должны быть талантливы».

Решение: Введем обозначения:

A: «студенты- информатики талантливы»

B: «студенты- информатики добросовестно относятся к учебе».

C: «систематически готовятся к занятиям»

Тогда данное умозаключение примет вид формулы А В, В С ((AB),(BC)( С A) или или ((AB)(BC)( С A) С А Составим таблицу истинности для проверки справедливости этого умозаключения:

A B C AB BC (AB)(BC) С A (AB)(BC)( С A) С 111 1 1 1 0 1 110 1 0 0 1 1 101 1 1 1 0 1 100 1 1 1 1 1 011 1 1 1 0 1 010 1 0 0 1 0 001 0 1 0 0 1 000 0 1 0 1 0 Табл. Строки последнего столбца дали ответ на вопрос: умозаключение истинно при любых значениях пропозициональных переменных A, B, C.

Формулу можно было упростить, используя тождество р q p q. Тогда ((AB)(BC))( С A)=(AB)( В C)( С A)= ( А B )( B C ) (C А) А B B C C А А B BC C А А B BC C А B BC C = В С C 1. Значит, вывод верен.

4.3. Метод резолюций в ИВ. Два известных способа доказательства теорем в ИВ (семантический и синтаксический) достаточно громоздкие и трудоемкие. На практике для доказательства теорем применяют метод резолюций.

Пусть даны дизъюнкты D1 D1 A, D2 D2 A. Дизъюнкт D1 D2 называется резольвентой дизъюнктов D1 и D2 по литере A и обозначается через resA(D1;

D2).

Очевидно, res(A;

A )=0. У дизъюнктов D1 и D2, не содержащих контрарных литер, резольвент не существует.

Пример 8. Пусть D1 A B C, D2 A B F. Тогда resA(D1;

D2)= B C B F, а resB(D1;

D2)= A C A F, resC(D1;

D2) – не существует.

Если res (D1;

D2) – существует, то D1;

D2 |– res (D1;

D2).

Пусть S={D1,D2,…,Dm} – множество дизъюнктов. Последовательность формул A1,A2,…,An называется резолютивным выводом из S, если для каждой формулы Ai (i=1,2,…,n) выполняется одно из условий:

– Ai S;

– существует j, k i, такие, что Ai= res(Aj;

Ak).

Теорема (о полноте метода резолюций). Множество дизъюнктов S противоречиво в том, и только в том случае, когда существует результативный вывод из S, заканчивающийся символом 0.

Метод резолюций можно использовать для проверки выводимости некоторой формулы A из заданного множества формул A1, A2,…, An. Задача проверки выводимости A1,A2,…,An |– A сводится к проверке противоречивости множества дизъюнктов S={D1,D,…,Dm}, что равносильно существованию резолютивного вывода 0 из S.

Пример 9. Проверить методом резолюций соотношение A ( B C ), CD E, F DE |– A (B F).

Решение. Как известно, формула Ф выводима из множества формул Г тогда, и только тогда, когда противоречив набор формул.

1. Проверим на противоречивость множество формул S { A ( B C ), CD E, F DE, A ( B F )}. Для этого приведем все формулы из S к КНФ:

S { A B C, CD E, F DE, A B F } { A B C, C D E, ( F D )( F E ), ABF }.

2. Мы получили множество дизъюнктов S { A B C, C D E, F D, F E, A, B, F }.

3. Построим резолютивный вывод из S, заканчивающийся 0.

1) resA ( A B C, A) B C ;

2) resВ ( B C, B ) C ;

3) resD (C D E, F D ) C E F ;

4) resE (C E F, F E ) C F 5) resC (C, C F ) F ;

6) res ( F, F ) 0, что и требовалось получить.

Метод резолюций достаточен, для выявления возможной выполнимости заданного множества дизъюнктов S. Для этого надо во множество S включить все дизъюнкты, получающиеся при резолютивных выводах из S.

Из теоремы о полноте метода резолюций вытекает следствие:

Следствие: Если множество дизъюнктов S содержит резольвенты всех своих элементов, то S выполнимо тогда, и только тогда, когда 0 S.

К правилу резолюций двойственным является правило согласия. Пусть заданы K1 K1 A, K 2 K 2 A.Положим конъюнкты (элементарные конъюнкции):

res A ( K1, K 2 ) K1 K 2, res ( A, A) 1.

Пусть S={K1, K2,…,Km} – множество конъюнктов. Последовательность формул A1, A2, …, An называется выводом из S по правилу согласия, если для каждой формулы Ai (i=1,2,…,n) выполняется одно из условий:

– Ai S;

– существует j, k i, такие, что Ai= res ( Aj, Ak ).

Теорема. Множество конъюнктов S={K1, K2,…,Km} общезначимо (т.е. выполняется |= K1 K2,…, Km) тогда и только тогда, когда существует вывод из S по правилу согласия, заканчивающийся символом 1.

4.4. Дизъюнкты Хорна. Метод резолюций для хорновских дизъюнктов. В общем случае метод резолюций малоэффективен, т.к. количество переборов, необходимых для получения ответа, достаточно велико. Эффективен метод резолюций для специальных классов дизъюнктов. Дизъюнкт D называется хорновским, если он содержит не более одной позитивной литеры (символа). Так, хорновскими являются дизъюнкты:

A B C D, A B C D, A, D.

В общем случае для хорновский дизъюнкт имеет вид A1... An B, что равносильно формуле ( A1... An ) B или A1... An. Хорновский дизъюнкт вида A1... An B называется точным, где переменные A1,..., An называется фактами, а B – целью. Хорновский дизъюнкт вида A1... An называется негативным, дизъюнкт D=B – унитарным позитивным дизъюнктом.

Если задано множество хорновских дизъюнктов S, то для проверки его невыполнимости надо:

1) Выбрать в S унитарный позитивный дизъюнкт P и дизъюнкт D, содержащий P.

2) Заменить S на ( S \{D}) {res( D, P)}.

3) Процесс продолжать до тех пор, пока S не будет содержать 0 или не найдется дизъюнктов P и D указанного вида.

4) Если на заключительном этапе множество дизъюнктов будет содержать 0, то исходное множество противоречиво. В противном случае – непротиворечиво.

Пример 10. Проверить на противоречивость множество дизъюнктов S {P R T, Q, R, T P R, T Q, P Q R }.

Решение. Для доказательства противоречивости запишем эти дизъюнкты в таблицу и применим описанный алгоритм. Результат будем записывать в таблицу (табл.9), а литеры, используемые на каждом шаге – подчеркивать.

QR Номер P R T T PR TQ PQR шага R TP R T 1 Q P R T P R 2 Q R TP T PT P T 3 P Q R TP P 4 Табл.9.

Четвертый шаг дал 0 – резолютивный вывод из S. Значит, множество S невыполнимо.

Литература: [2], ч.4;

[3], гл.I, гл.III;

[4], гл.2;

[6], гл.5, 6;

[8], гл.10, 11;

[9], гл.12, 13;

[11], гл.1;

[12], гл.7.

Лекция № 5. Исчисление предикатов Язык исчисления предикатов. Приведение формул логики предикатов к клаузальной нормальной форме, их применение в математической логике для проверки истинности выводов. Метод резолюций в исчислении предикатов. Принцип логического программирования.

5.1. Язык исчисления предикатов. Формальная теория S=A,F,P,R называется исчислением предикатов (точнее говоря, исчислением предикатов первого порядка), если заданы:

1-2. Алфавит, термы и формулы ИП описаны в лекции 2 (стр. 12).

3. Аксиомы: а) аксиомы исчисления высказываний: P1: (A(BA));

P2: ((A(BC))((AB)(AC));

P3: ( B A )(( B A)B)));

б) кванторные: P4 : x A(x)A(y);

P5 : A(x) yA(y) A, A B 4. Правила вывода: R1: – modus ponens;

B A B( x) R2: – введение квантора общности;

A x B( x) A( x) B R3: – введение квантора существования.

x A( x) B Построенная формальная теория S описывает весьма общие объекты, поэтому надо ее интерпретировать в то, с чем можно работать.

5.2. Формулы ИП. Определение формулы лежит в основе так называемой логики предикатов первого порядка, в которой разрешается квантифицировать (связывать кванторами) только предметные переменные. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисления высказываний, а также большинство правил вывода умозаключений из классической логики. Поэтому язык логики предикатов даёт возможность анализировать рассуждения естественного языка, а также науки, делать выводы в различных формальных системах.

Так, высказывательная форма p Q ( x) q является формулой. В то же время х Р ( х) Q ( x) не будет формулой;

в формуле x P (x) переменная x связана квантором существования, тогда как в формуле Q(x) эта же переменная свободна.

5.3. Теоремы ИП. К числу основных равносильностей логики предикатов относят:

1. хР( х) х Р ( х) ;

2. хР( х) ( х) Р ( х) ;

3. хР( х) х Р ( х) ;

4. хР( х) х Р ( х) ;

5. х( Р ( х) Q ( x)) xP( x) xQ( x) ;

6. х( Р ( х) Q ( х)) хР ( х) хQ( х).

Пример 11. «Все металлы (M) – плавятся (П). Цинк (Ц) – металл. Значит, цинк плавится». Формализация в логике предикатов примет вид:

x ( M ( x) П ( х)) х ( Ц ( х) М ( х)) |– x ( Ц ( x) П ( х)). Снятие квантора общности:

x( M ( x) П ( х)) ( Ц ( х) М ( х)) ;

тогда на основании транзитивности импликации имеем ( Ц ( х) М ( х)), ( М ( х) П ( х)) |= Ц ( х) П ( х). Поэтому, вывод x ( Ц ( х) П ( х)) – обобщение по R2 – верен.

Символически общее отрицание принято записывать с помощью либо общей чертой, либо отрицанием самого квантора: для отрицания предложения x (Ф( х)) возможны записи x(Ф( х)), или x(Ф( х)), или (x (Ф( х))) : x(Ф( х)) x(Ф( x)) ;

для отрицания x(Ф( x)) аналогично: x(Ф( x)), или x(Ф( x)), или x(Ф( х)) : x(Ф( x)) x(Ф( х)).

Эти равносильности являются обоснованием метода построения отрицаний высказываний, содержащих кванторы: для построения отрицания высказываний, общности () содержащих квантор, достаточно заменить его на другой квантор существования () существования () и взять отрицание выражения, на которое этот квантор был общности () «навешан».

Для многоместных кванторов также применяется это правило: осуществляется последовательный перенос отрицания с кванторного слова на предложение, стоящее за квантором, а сам квантор заменяют на двойственный. Например, для формулы xyz ( R ( x, y, z )) построим отрицание:

xyz ( R ( x, y, z )) x(yz ( R ( x, y, z )) xy (z ( R ( x, y, z )) xyz ( R ( x, y, z )).

Как известно, операции конъюнкции и дизъюнкции двойственны. Поэтому для сложных высказываний, состоящих из простых, разделенных операциями конъюнкции и дизъюнкции, отрицание строится по следующему правилу. Все кванторы заменяют на, и наоборот, все связки и () заменяют на или (), и наоборот, а затем берут отрицание утверждения.

5.4. Метод резолюций в логике предикатов. В отличие от логики высказываний в логике предикатов имеется большое число интерпретаций каждой формулы. Поэтому их общезначимость или противоречивость невозможно доказать простой проверкой ее истинности (ложности) при всех возможных интерпретациях. Поскольку формула общезначима тогда и только тогда, когда ее отрицание противоречиво, то можно установить противоречивость отрицания данной формулы. Этот метод служит основой для большинства современных автоматических алгоритмов поиска доказательств.

Процедура поиска доказательств методом резолюций (предложил в 1965г. Дж.

Робинсон) фактически является процедурой опровержения: вместо доказательства общезначимости формулы доказывают, что отрицание формулы противоречиво. Правило вывода умозаключений в исчислении предикатов, используемое для вывода новой логической формулы из двух посылок, называется резолюцией. Метод резолюций позволяет получить максимально сильное следствие множества формул с помощью систематической процедуры последовательного построения логических следствий формулы. Метод резолюций есть правило присоединения к рассуждению, в состав которого входит два утверждения A B, A C их следствия – утверждения B C.

В логике предикатов для применения метода резолюций необходимо убрать все кванторы. Для этого существуют два способа:

1) вынос всех кванторов общности за скобки;

2) приведение к скулемовской форме, т.е. исключить все кванторы существования.

Отсюда метод резолюций в логике предикатов заключается в следующем:

0) задача – доказать общезначимость формулы:

1) перейти к формуле G F и взять ее отрицание:

2) исключить в G все кванторы существования;

3) вынести за скобки все кванторы общности, предварительно преобразовав связанные переменные с целью отличия их от свободных переменных и между собой;

получим G xy...z H ( x, y,..., z ) ;

4) представить H ( x, y,..., z ) в виде КНФ и применить к ней метод резолюций для высказываний.

Математические исследования показали, что все утверждения и доказательства классической математики можно выразить средствами исчисления предикатов. Поэтому справедлив тезис Черча: «Любое математическое утверждение может быть записано на языке исчисления предикатов, а любое математическое доказательство можно провести в рамках исчисления предикатов».

5.5. Общезначимость формул исчисления предикатов. Как известно, в логике (и предикатов, и высказываний) формула считается общезначимой тогда и только тогда, когда она выводима. Но если в логике высказываний мы можем процесс доказательства провести за конечное число шагов, и заранее знаем конечный результат, то в логике предикатов такой уверенности у нас нет. В исчислении предикатов доказано, что всякая выводимая формула исчисления предикатов тождественно истинна (т.е. общезначима), и наоборот. В настоящее время разработан ряд методов, позволяющих стандартизировать обоснование этих равносильностей. Но в отличие от логики высказываний, логика предикатов неразрешима, т.е. невозможно указать алгоритм установления истинного значения формул для многоместных предикатов (n1). Однако, логика одноместных предикатов, наиболее полно соответствующая логике исчисления высказываний, разрешима.

5.6. Принцип логического программирования. Язык логики предикатов, обогащенный дополнительными логическими средствами, дает возможность описывать большой круг задач методами логического программирования. Главным отличием логического программирования от « процедурных языков» является то, что программа не указывает как что-либо сделать для решения задачи, а описывает некоторые элементы и связи между ними, а также ставит цель, т.е. задает вопрос об этой системе. Это означает, что необходимо проверить истинность предложения в указанной системе или найти элемент, удовлетворяющий заданной формуле.

Литература: [2], ч.4;

[3], гл. IV;

[4], гл.2;

[6], гл.2;

[7], гл.7;

[8], гл.4;

[9], гл.10, 11;

[12], гл.2;

[13], гл.7.

Лекция № 6. Формализация понятия алгоритма. Рекурсивные функции.

Машина Тьюринга Понятие алгоритмической системы. Рекурсивные функции. Формализация, уточнение и обобщение понятия алгоритма. Машина Тьюринга и проблемы вычислимости. Тезис Черча.

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

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

Алгоритмический язык – это формализованный язык для однозначной записи алгоритмов. Алгоритмический процесс начинается с произвольного исходного данного из некоторой совокупности допустимых для данного алгоритма исходных данных. Он направлен для получения результата, полностью определяемого этими исходными данными. Алгоритмический процесс должен удовлетворять требованиям:

– дискретности, т.е. процесс состоит из дискретных шагов, на каждом шаге выполняется действие над промежуточными результатами, полученными на предыдущих шагах с целью получения очередного промежуточного результата;

– элементарности, т.е. действие алгоритма на каждом шаге должны быть максимально упрощены;

– детерминированности, т.е. каждый шаг однозначно определяется исходными данными и не зависит от случайностей;

– массовости, т.е. алгоритм вычисления функции должен применяться к любой задаче из заданного класса задач;

– результативности, т.е. алгоритм должен содержать условие остановки, которое обеспечивает завершение процесса поиска результата некоторого задания за конечное число шагов (конечное время) для любого значения аргумента.

Примеры вычислительных алгоритмов: умножение «столбиком», деление «уголком», прием дифференцирования сложных функций, прием перевода числа из десятичной формы записи в двоичную и др.

При построении точного понятия алгоритма применяется следующая схема:

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

имеется Функция, для которой алгоритм вычисления любого ее значения, не имеется вычислимой называется.

невычислимой 6.2. Рекурсивные и вычислимые функции. Не всегда удается задать функции с помощью формулы (аналитически). В отдельных случаях функцию необходимо задать с помощью индуктивного метода, т.е. рекурсивно (от лат. «возвращаюсь»).

Аксиома натуральных чисел: любое непустое подмножество натуральных чисел имеет минимальный элемент. Минимальный элемент самого множества обозначается и называется «единицей». Операцию «следования за» будем обозначать не штрихом, а привычно: +1, например, 3=2+1 (аналог 3=2').

Принцип индукции заключается в выполнении ряда условий:

Если для множества A справедливо: 1) 1 A;

2) если из kA следует k+1A – то A=.

Примеры рекурсивных функций:

1) f(n)=an. Эту функцию, определенную на множестве целых неотрицательных чисел, можно задать рекурсивно: f(0)=1;

f(k+1)= af(k). Действительно, f(k+1)= an+1= a an=af(k).

2) f(n)=n! = 1 2... (n 1) n. Т.к. современный компьютер пока не воспринимает многоточие, то используется рекурсивное задание этой функции f (0) 1,.

f (k ) k f (k 1), k 3) Последовательность Фибоначчи: (0),1,1,2,3,5,8,13,21,…, которая имеет особое значение, причем не только в математике, можно задать рекуррентно в виде функций F(n) для n : F (0) 1, F (1) 1, F (n) F (n -1) F (n - 2), n 2.

Идея формализации понятия алгоритма с помощью понятия «рекурсивные функции»

состоит в том, что выделяется класс базовых функций, а также класс функций, строящихся из базовых. Этот класс отождествляется с классом вычислимых функций.

1. Простейшие (базовые) рекурсивные функции. Назовем простейшими три вычислимых функции вида:

а) ноль-функция: О(x)=О, x ;

б) функция следования (функция Пеано) или S: S(x)= x+1, или x x 1, x, которая означает переход к следующему элементу заданного множества;

в) функция тождества, проектирующая функция или функция выделения аргумента n n J m : J m ( x1,..., xn ) xm, 1 m n.

2. Операция получения новой функции по имеющимся функциям. На основе простейших функций введем операторы, которые позволяют получать из базовых новые функции.

а) Оператор суперпозиции (подстановки). В основе этого оператора лежит способ вычисления, состоящий в том, что если известен способ вычисления f ( x1...xm ) и g ( x1...xn ) (функций, зависящих от своих наборов аргументов), то подстановка каждого набора значений g1 ( x1...xn )...g m ( x1...xn ) дает способ вычисления h=f(g(x)) как функции от x1...xn.

б) Оператор примитивной рекурсии. Операция получения новой функции из имеющихся двух функций через рекуррентную формулу f(n+1)=h(n,f(n)) основана на приеме вычисления функции натурального аргумента f(n+1) по уже известному значению f(n). В таком случае задается значение функции f(0), а по нему последовательно вычисляются f(1), f(2) и т.д. Такой процесс последовательного вычисления значения функции называется рекурсией.

Пусть заданы некоторые числовые частичные функции: n-местная функция g и (n+2)- местная функция h. Тогда (n+1)- местная частичная функция f «конструируется» из функций h и g с помощью оператора примитивной рекурсии f=R(g,h)по схеме:

f ( x1,..., xn, 0) g ( x1,..., xn ), k 0;

f(x1, x2,…,xn, y)= f ( x1,..., xn, k ) h( x1,..., xn, k 1, f ( x1,..., xn, k 1)), 1 k y, и называется примитивной рекурсией. Совокупность этих равенств для любых функций h и g однозначно определяет значение функции f.

Действие операции примитивной рекурсии заключается в выполнении цикла из y шагов, где аргумент k, 0 k y есть параметр цикла, функция g – начало цикла, функция f – тело цикла. Схема примитивной рекурсии образует некоторый индуктивный процесс построения функции h при котором на нулевом шаге используется функция g, а на каждом последующем шаге – значение функции f от аргументов x1,..., xn, номер y предыдущего шага и значение функции h, вычисленного на предыдущем шаге.

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

При помощи примитивно рекурсивных функций удалось конструктивно определить такие арифметические операции, как сложение и умножение натуральных чисел. Однако для получения операций вычитания и деления примитивно рекурсивных функций не достаточно: для этого необходимо вести еще одну операцию над базовыми функциями.

в) Оператор минимизации. Операция построения новой функции ( x), зависящей от n переменных, по известной f ( x1,..., xn, y ) согласно правилу ( x) min y | f ( x, y ) yN называется минимизацией.

Например, можно организовать поиск минимального корня уравнения либо решив его, либо путем перебора чисел y=0, y=1,…до первого, удовлетворяющего уравнению.

Функции, полученные из трех базовых функций при помощи применения конечного числа трех операций – суперпозиции, примитивной рекурсии и минимизации – называются частично рекурсивными.

Если частично рекурсивная функция определена всюду, то ее называют общерекурсивной. Так, примитивно рекурсивная функция является общерекурсивной.

Для каждой частично рекурсивной функции f существует вычислительный процесс, посредством которого любое натуральное число x перерабатывается в значение f(x). С помощью частично рекурсивных функций можно определить все арифметические операции. Т.о., всякая примитивно рекурсивная функция является вычислимой.

Тезис Черча. Класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

6.3. Примитивно рекурсивные предикаты. В математической логике предикаты вводят тогда, когда необходимо символически отобразить отношения между предметами. Как известно, предикат определен на некотором множестве предметов и принимает значения «истинно» (1) и «ложно» (0).

Рассмотрим предикаты, определенные на расширенном множестве натуральных чисел. Пусть P(x1,x2,…,xn) – n-местный предикат, определенный на множестве натуральных чисел. Функция P(x1,x2,…,xn) называется характеристической предиката,...,P, )) истинно, эта функция удовлетворяет условию:

функцией для если если если ((,..., ложно.

P x1 xn P(x1,x2,…,xn)= 1, P x1 xn 0, Предикат называется примитивно рекурсивным, если существует примитивно рекурсивная функция, представляющая этот предикат, т.е. его характеристическая функция примитивно рекурсивна. Если P1, P 2,…, P n примитивно рекурсивны, то любой предикат, полученный из них с помощью логических операций, примитивно рекурсивен.

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

разрешим вычислима Предикат, если характеристическая функция.

невычисима неразрешим Задача 1. Найдите функции g и h в рекурсивной формуле для двухместной функции f(x,y)=xy, если рекурсия проводится по переменной x.

Решение: Алгоритм решения:

1) Найдем функцию g(y)= f(0,y) (рекурсия проводится по переменой x): g(y)=0 y=0.

2) Подставим в функцию f(x,y) вместо x значение x+1: f(x+1,y)= (x+1) y= x y + y.

3) Выразим функцию f(x+1,y) через f(x,y), x, y: f(x+1,y) = f(x,y)+ y.

4) Найдем функцию h(x,y,z) из формулы f(x+1,y)= h(x,y, f(x,y)), заменив f(x,y) на z:

h(x,y,z)= z+ y.

Задача 2. Найдите функции g и h в рекурсивной формуле для трехместной функции f(x,y, z)=xy+ z, если рекурсия проводится по переменной y.

Решение: Алгоритм решения:

1) Найдем функцию g: g(x,z)=f(x,0,z) (т.к. рекурсия проводится по переменной z):

g(x,z)=f(x,0,z)= x0+ z= z.

2) Подставим в функцию f(x,y,z) вместо y значение y+1:

f(x,y+1,z)= x(y+1)+ z= xy+ z+ x.

3) Выразим функцию f(x,y+1,z) через f(x,y, z), x,y, z:

f(x,y+1,z) = (xy+ z)+ x= f(x,y, z)+ x.

4) Найдем функцию h(x,y,z,t) из формулы f(x,y+1,z)= h(x,y, z, f(x,y,z)), заменив f(x,y,z) на t:

h(x,y,z,t)= t+ x.

Задача 3. Примените оператор примитивной рекурсии к простейшим функциям g(x)= J1 ( x) x и h(x,y,z)= z =z+1 и постройте функцию f ( x, y ) R ( g, h), если рекурсия проводится по переменной y.

Решение: Конструируя функцию f ( x, y ) R ( g, h), составим примитивно рекурсивное описание функции f(x,y) по переменной y, применяя оператор примитивной рекурсии к функциям g(x)= J1 ( x) x и h(x,y,z)= z =z+1 по переменной y:

f(0,x)=g(x)=x, f(1,x)=h(x,1,f(0,x))= f(0,x)+1= x+1, f(2,x)=h(x,2,f(1,x))= f(1,x)+1= x+1+1= x+2, f(3,x)=h(x,3,f(2,x))= f(2,x)+1= x+2+1= x+3, f(4,x)=h(x,4,f(3,x))= f(3,x)+1=x+3+1= x+4,… f(y,x)=h(x,y,f(y-1,x))= f(y–1,x)+1= x+ (y–1)+1= x+ y.

Получена двухместная примитивно-рекурсивная функция сложения f(x,y) = x+ y, т.к.

она сконструирована из простейших функций с помощью применений конечного числа операторов примитивной рекурсии.

Задача 4. Примените оператор примитивной рекурсии к простейшей функции g(x)= и к примитивно-рекурсивной функции h(x,y,z)=x+y по переменной y, и постройте функцию f ( x, y ) R ( g, h), записав ее в аналитической форме.

Решение: Конструируя функцию f ( x, y ) R ( g, h), составим примитивно рекурсивное описание функции f(x,y) по переменной y:

f(0,x)=g(x)=0, f(1,x) = h(x,1,f(0,x))= x+ f(0,x)= x+0= x, f(2,x)=h(x,2,f(1,x))= x+f(1,x)= x+ x = 2x, f(3,x)=h(x,3,f(2,x))= x+ f(2,x)= x+ 2x=3x, f(4,x)=h(x,4,f(3,x))= x+ f(3,x)=x+3х= 4x, … f(y,x)=h(x,y,f(y-1,x))= x+ f(y–1,x)= x+ (y–1) x = xy.

Получена двухместная примитивно-рекурсивная функция умножения f(x,y) = x y, Задача 5. Примените оператор примитивной рекурсии к функциям g(x)=1 и h(x,y,z)=xy по переменной y, и постройте функцию f ( x, y ) R ( g, h), записав ее в аналитической форме.

Решение: Составим примитивно-рекурсивное описание функции f(x,y) по переменной y:

f(0,x)=g(x)=1, f(1,x) = h(x,1,f(0,x))= f(0,x) x = 1 x = x, f(2,x)=h(x,2,f(1,x))= f(1,x) x = x x = x 2, f(3,x)=h(x,3,f(2,x))= f(2,x) x = x 2 x = x 3, f(4,x)=h(x,4,f(3,x))= f(3,x) x = x 3 x = x 4, … f(y,x)=h(x,y,f(y-1,x))= f(y–1,x) x = x y-1 x = x y.

Получена двухместная примитивно-рекурсивная функция f(x,y) = x y.

6.4. Машина Тьюринга. Один из способов формализации понятий вычислимости и алгоритма состоит в рассмотрении некоторой идеализированной вычислительной машины (аналог реальной ЭВМ). Такая машина была предложена Аланом Тьюрингом в 1936 году.

Машина Тьюринга – гипотетическая вычислительная машина (автомат), используемая qi в качестве математической модели для уточнения понятия алгоритма как эффективного процесса... a jk... a jr a j1 a j вычисления. Идея Тьюринга заключалась в том, что «поручить» машине выполнять алгоритм как Рис. последовательность элементарных (простых) действий, присущих человеку при работе с информацией. Под такими элементарными операциями понимают: запись либо стирание одного символа, возвращение к ранее записанной информации, перенесение внимания с одного участка «ленты» (как символа бумаги) на другой. Алгоритм, задаваемый машиной Тьюринга, перерабатывает некоторые конструктивные объекты, которые можно кодировать словами некоторого алфавита.

В состав машины Тьюринга (МТ) входят пять компонентов:

1) управляющее устройство (УУ), способное принимать некоторое число состояний, соответствующих различным комбинациям состояний внутренних элементов ЭВМ (ячейки памяти, электронные схемы и пр.). УУ в каждый момент времени находится только в одном из состояний (рис.3);

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

3) считывающе-записывающее устройство (СЗУ) или «головка», которое обладает способностью в каждый момент работы машины выполнять элементарные операции:

«обозревать» одну ячейку ленты;

«считывать» букву, записанную в этой ячейке, стирать ее;

заносить на место считанной буквы любую другую из внешнего алфавита;

передвигаться вдоль ленты влево и вправо на одну ячейку;

4) алфавит;

МТ содержит три конечных непересекающихся алфавита – внутренний, внешний и алфавит сдвигов.

Внешний алфавит A – это множество букв A a1,..., an, n 1, дополненное пробелом (пустым словом, пустой клеткой), обозначаемым (или a0): A A – т.е. это те символы, которые непосредственно читаются и обрабатываются МТ Внутренний алфавит или алфавит состояний Q q0, q1,..., qm, m 1, где q1…qm – рабочие состояния, q0 – состояние остановки (возможно, отсутствующее), т.е.

заключительное состояние, попав в которое машина прекращает работать. Выделим в отдельное подмножество все рабочие состояния: Q Q \ {q0 } {q1,...qm }.

Алфавит сдвигов, обозначаемый S={L;

0;

R} (или S={л;

0;

п}, или S={-1;

0;

1}), указывающих направление сдвига СЗУ «влево», «на месте» и «вправо»

соответственно.

5) Программа машины – есть отображение : A Q A Q S, т.е. правило, ставящее в соответствие любой паре ( ai,qj) тройку (b,p,s)=П( ai,qj) (т.е. букву, состояние и сдвиг). Выражения П( ai,qj) (или П(i,j), или Пij) называются командами. Про пару a, q A Q говорят: «a наблюдается в состоянии q». Пусть машина находится в состоянии qj, а СЗУ считывает символ ai. Программа машины определяет, что нужно стереть ai, напечатать вместо него символ b, перейти в состояние p и сдвинуть головку влево или вправо, или оставить на месте.

Конфигурацией или машинным словом называется слово с отметкой, записанное на ленте с указанием обозреваемой СЗУ ячейки. Конечная последовательность команд называется программой машины. Т.к. A и Q конечны, и каждая команда зависит только от двух аргументов Пij, то программу удобно задать таблицей.

Машина T работает дискретно, на каждом шаге выполняется переход от одной конфигурации к другой. Вначале СЗУ обозревает первую ячейку МТ, машина находится в состоянии q1. УУ обращается к программе машины T и находит соответствующую клетку.

Пусть в ней тройка (a,qi,s). Буква a заносится УУ в обозреваемую ячейку, МТ переводится в состояние qj, а СЗУ совершает сдвиг на 1 ячейку право при s=+1 (R, п) или влево при s= 1 (L, л) или остается на месте при s=0.

Аналогично МТ работает на любом следующем шаге. Если на некотором шаге машина придет в состояние q0, то УУ останавливает машину, т.к. получена заключительная конфигурация. Полученное слово T(u) есть результат применения МТ к исходному слову (u), т.е. МТ переработала слово u в слово T(u). Говорят, что машина T применима к слову A, если машина, начав работу со словом A, остановится через конечное число шагов. Если при этом получается слово B, то пишут T ( A ) = B.

Говорят, что МТ не применима к слову u, если в процессе применения ее к слову она ни на каком шаге не приходит в заключительное состояние. В этом случае совокупность всех конфигураций в процессе бесконечной работы может быть как ограниченной (тогда она циклична: ситуация зацикливания), так и неограниченной. МТ считается применимой к множеству слов { Ai }, если она применима к каждому слову Ai.

При работе МТ возможны три случая:

1) Начальное слово обрабатывается МТ до ее остановки в завершающем состоянии q0.

Результат работы МТ – окончательное слово на ленте.

2) Машина не работает из-за отсутствия команды с требуемой левой частью, т.е. МТ находится не в завершающем состоянии.

3) МТ работает без остановки (бесконечно).

Функция называется вычислимой по Тьюрингу, если существует МТ, вычисляющая эту функцию.

Тезис Чёрча. Класс задач, решаемых в любой формальной алгоритмической модели, совпадает с классом задач, могут быть решены интуитивно алгоритмическими методами.

Тезисом Черча часто пользуются для сокращения доказательства теорем в теории алгоритмов: если в ходе рассуждений нужно установить, что некоторая функция вычислима по Тьюрингу, то используют вместо построения МТ «неформальную вычислительную процедуру».

Формализация, уточнение и обобщение понятия алгоритма могут осуществляться разными способами: с помощью понятий «рекурсивные функции», «машина Тьюринга», и др. Мы рассматриваем две эквивалентные модели вычислимости: рекурсивные функции и машину Тьюринга. Оказывается, различные формальные определения алгоритма эквивалентны между собой. Эквивалентность двух абстрактных моделей алгоритмов заключается в том, что любой класс проблем, которые можно решить с помощью моделей одного вида, можно также решить и с помощью моделей другого вида. Причем, все известные алгоритмы могут быть представлены в виде алгоритмов в точном смысле в рамках этих формализаций.

Тезис Чёрча-Тьюринга: Любой алгоритм в интуитивном смысле может быть представлен машиной Тьюринга. Т.о., формальные модели алгоритма достаточно полно представляют интуитивное его понимание, что важно с практической точки зрения. Это означает, что компьютеры различного уровня – от персональных до сверхмощных – эквивалентны относительно принципиальной возможности решения любых алгоритмических проблем.

Если при выполнении некоторой команды машины T из конфигурации K i получается конфигурация K j, то пишут T : K i K j. Если T : K i1 K i2... K in, то пишут T : K i1 K in. Если K1 – начальная, а K n – заключительная конфигурация, то пишут T : K1 | K n, а если машина T ни в какой момент времени не переходит в T : K1 |.

заключительное состояние), то пишут Последовательность конфигураций K i1, K i2, … есть протокол работы МТ. Выражение или подвыражение a n означает слово aa...a.

n Задача 1. Рассмотрим два протокола применения МТ с программой aq1 bq2 R;

bq1 aq2 R;

aq2 q0 ;

bq2 q1 L. Эту программу можно задать таблицей переходов и состояний:

q1 q a b q2 R q b a q2 R q1 L Рассмотрим две задачи.

а) Пусть для слова aa начальная конфигурация aq1 a. Тогда протокол имеет вид:

a q1 a 0)......

b a q 1)......

b a q 2)......

Ответ: aa |-- b a.

б) Пусть для слова ab начальная конфигурация aq1b. Тогда протокол имеет вид:

0)... a q1 b...

b b q 1)......

b q1 b 2)......

a b q.3).....

a q1 b 4)......

.......................

Пятая конфигурация протокола совпадает с первой (СЗУ в состоянии q1 на символе a слова a b ). Поскольку работа МТ детерминирована, следующая, шестая конфигурация совпадает со второй и т.д. Мы имеем зацикливание, т.е. МТ неприменима к начальной конфигурации aq1b. Ответ: a b |--.

Программу МТ можно задавать таблицей переходов: столбцы соответствуют состояниям управляющего устройства, а строки - символам внешнего алфавита;

в клетках таблицы записываются правые части соответствующих команд МТ.

Возможно также задание МТ графом (или диаграммой) переходов – ориентированным графом (V, X), где V - множество вершин, соответствующих каждому из qi возможных состояний МТ. Дуги графа соответствуют командам, т.е. клеткам таблицы переходов. Если на пересечении строки aj и столбца qi в таблице содержится al qk S то этой клетке соответствует дуга (qi, qk ), которой приписана упорядоченная пара (a j ;

al S ).

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

bS )...( air ;

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

bS ). В частности, граф, соответствующий таблице переходов в задаче 1 имеет вид (рис.4) (bL) (abR) abR q1 q q1 q (baR) a q Рис. Тезис Тьюринга. Всякий алгоритм может быть реализован машиной Тьюринга.

Задача 2 [2, пример 6.3]. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления.

Напомним, что, например, 710 |||||||1. Тогда необходимо построить машину, реализующую: T m +n m n. Тогда расширенным алфавитом будет A |,, 1 1 Проанализируем возможные состояния подобной машины, исходя из общей идеи, описанной в пункте а). Условимся составлять программы так, чтобы остановка происходила на первой букве результата:

– пусть основное рабочее состояние q1 (оно всегда существует, поскольку множество состояний не пусто): находясь в нем, машина каждый символ | копирует, а каждый символ + меняет на |, переводя головку на одну позицию вправо и не меняя состояние. Таким образом, | q1 | q1 R, q1 q1 R ;

– поскольку | q1... уже определен, нужно состояние (назовем его q2 ), которое должно «убить» последнюю |, заменив ее на, после чего головку нужно возвратить в начало, т.е. | q2... R. Тогда очевидно, что, находясь в состоянии q1 и встретив, машина Тьюринга должна перейти именно в состояние q2, скопировав и переведя головку на предваряющую ее последнюю |, таким образом, q1 q2 L – поскольку | q1... R и | q2... уже определены, нужно состояние (назовем его q3 ), которое перед завершением гонит головку в начало, просто копируя встречающиеся | (не выходя из этого состояния), пока не достигнет начальной, после чего остановится на первой |, т.е. перейдет в q0. Таким образом, | q3 | q3 L, q3 | q0 R. Очевидно, что именно в это состояние должна перейти машина после завершения q2 : | q2 q3 L.

Итак, машина реализуется следующей программой (табл.10, рис.5а):

q1 q2 q | | q1 R q3 L | q3 L + | q1 R q2L q0R Табл. R R L L R L q1 q q1 q L R R L q0 q L q0 q R R а) б) Рис.5 а) – граф переходов к задаче 2;

б) – граф переходов к задаче 3.

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове | | | | |. При записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

0)... | q1 | | | |... 8)... | | | | | q3...

1)... | | q1 | | |.. 9)... | | | | q3 |...

2)... | | q1 | | |... 10)... | | | q3 ||...

3)... | | | | q1 | |... 11)... | | q3 | | |...

4)... | | | | | q1 |... 12)... | q3 | | | |...

5)... | | | | | | q1... 13)... q3 | | | | |...

6)... | | | | | | q1... 14)... | q0 | | | |...

7)... | | | | | | q2...

Прокомментируем каждый шаг работы МТ.

0) Согласно первому замечанию, СЗУ установлено так, что обозревается первая буква | первого слагаемого. Согласно таблице с программой состояние q1 продвигает СЗУ вправо на одну букву, пропуская вперед (левее) вторую букву | первого слагаемого и сохраняя состояние q1.

1) Обозревая вторую букву | первого слагаемого при состоянии q1, СЗУ продвигается вправо на одну букву, пропуская вперед символ «+», сохраняя состояние q1.

2) Обозревая символ «+» при состоянии q1, СЗУ продвигается вправо на одну букву, пропуская вперед первую букву | второго слагаемого. При этом символ «+» заменяется новым символ | и сохраняется состояние q1. (Поэтому появилась шестая буква | ).

3) Обозревая первую букву | второго слагаемого при состоянии q1, СЗУ продвигается вправо на одну букву, пропуская вперед вторую букву | второго слагаемого, сохраняя состояние q1.

4) Обозревая вторую букву | второго слагаемого при состоянии q1, СЗУ продвигается вправо на одну букву, пропуская вперед третью букву | второго слагаемого, сохраняя состояние q1.

5) Обозревая третью букву | второго слагаемого при состоянии q1, СЗУ продвигается вправо на одну букву, пропуская вперед символ «», сохраняя состояние q1.

6) Обозревая символ «» при состоянии q1, программа сохраняет его, но продвигает СЗУ влево на одну букву и переводит состоянии q1 в состоянии q2. Т.о., символ «»

оказывается правее q2.

7) Обозревая букву | в состоянии q2 согласно программе, происходит замена этой буквы на символ «» и состояния q2 на q3, а СЗУ продвигается влево на одну букву. Т.о., вместо шести мы опять имеем пять букв |.

8) Обозревая букву | в состоянии q3, программа сохраняет это состояние и продвигает СЗУ влево на одну букву. Аналогично совершаются следующие 9) – 12) шаги алгоритма.

13) Обозревая символ «» при состоянии q3, программа сохраняет его, переходя в состояние q0. При этом СЗУ продвигается на одну букву вправо.

14) Т.о., устанавливается финальное состояние работы программы и получен ответ: пять букв |.

Задача 3 [2, пример 6.4]. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.


Решение: Для разпознавания исходных и скопированных | введем новой букву, служащую делимитатором, т.е. расширим исходный алфавит A до A |,. Тогда | A |,,. Программа такой машины имеет вид (табл.11, рис.5,б):

q1 q2 q | q1 R | q2 L | q3 R | q3 R q2 L q0 R | q2 L Табл. Применим полученную машину к слову | | : тогда на входе... | q1 |...

1)... | q1... 7)... q2 | |...

2)... q1... 8)... | q3 | |...

3)... q2... 9)... | q2 | | |...

4)... | q3... 10)... | q2 | | |...

5)... | q2 |... 11)... q2 | | | |...

6)... | q2 |... 12)... | q0 | | |...

Состояние q1 обеспечивает замену | на, состояние q2 обеспечивает поиск, предназначенных для замены на |, и остановку машины в случае, когда не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена на |.

Литература: [2], гл.6;

[3], гл.V;

[4], гл.5;

[5], гл.5;

[6], гл.4;

[7], гл.2, ч.3;

[8], ч.8;

[9], гл.12;

[10], гл.16-18;

[12], гл.4.

Лекция № 7. Основы нечеткой логики Темпоральная и модальная логики. Нечеткая логика. Нечеткая арифметика.

Введение понятий нечетких множеств и операций над ними. Нечеткая и лингвистическая переменные, функции принадлежности и методы их построения. Нечеткие числа и операции над ними.

Изучение формальных систем в виде исчислений высказываний и исчислений предикатов имеет очень важное значение, т.к согласно тезису Гильберта: «Любое математическое утверждение может быть записано на языке исчисления предикатов, а любое математическое доказательство можно провести в рамках исчисления предикатов».

Однако не всегда реальные “жизненные” ситуации дают нам задачи с точным аналитическим описанием их содержания. Так, задачи, не поддающиеся строгой формализации, привели к появлению новой математической дисциплины – неклассической логики. Для оценки степени истинности высказываний в естественном языке применяются специальные средства: наречия и обороты типа «очень», «в некоторой степени» и др. В математику такие обороты попали с возникновением неклассической логики и ее разновидностей.

7.1. Модальная логика. Модальная логика – это логика, в которой наряду с обычными высказываниями, встречаются модальные высказывания, содержащие понятия необходимости, возможности или им родственные, характеризующие степень достоверности суждений. Эти логические константы называют модальностями или модальными операторами. Понятие модальность происходит от латинского modus (способ, отношение), т.е. это способ понимания суждения об объекте, явлении или событии. Льюисом было установлено, что логическое следование тесно связано с понятиями необходимости и возможности.

Различают три типа модальности:

– модальности общего вида: «необходимо», возможно», «невозможно», «случайно»;

– модальности, связанные с характеристиками действий и поступками людей в обществе:

«обязательно», «разрешено», «запрещено», «безразлично» и др.;

– модальности, являющиеся характеристиками – «доказано», «не доказано», «верит», «убежден», «сомневается» и др.

Модальные понятия разных групп выполняют одну и ту же функцию: они уточняют связь, устанавливаемую в отдельном высказывании, конкретизируют ее. Правила их упот ребления определяются только этой функцией и не зависят от содержания высказываний.

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

Модальную логику можно трактовать математическими средствами. Для этого к исчислению высказываний добавляются новые одноместные связки – модальные операторы – необходимо и – возможно. Т.к. формулы-модальности и эквивалентны между собой, то в качестве основного берется один из этих модальных операторов, а другой выводится из аксиом.

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

Модальное исчисление I0 получается из исчисления высказываний – введением символа ;

– добавлением в формулы фразы «если – формула, то и – формула»;

– введением дополнительной схемы аксиомы ( ) |– ();

– введением дополнительного правила вывода (Г |– ) |= (Г |– ).

Модальное исчисление T получается из исчисления I0 добавлением схемы аксиом |–. Модальное исчисление S4 получается из исчисления T добавлением аксиомы |–.

Модальное исчисление S5 получается из исчисления T добавлением аксиомы |–.

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

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

Рассмотрение процессов, протекающих в реальном времени, требуют отказаться от двузначной логики. Так, высказывание «звучит песня» может быть истинным в начальный момент его произнесения, и ложным к его окончанию, т.к. песня уже закончилась.

Высказывания как таковые принадлежат к прошлому, несмотря на то, что они могут содержать модальный оператор будущего времени, например, «всегда будет так, что…».

В частности, временная логика Прайора (логика будущего) получается добавлением к логике высказываний новых символов – символов будущего F и G. Для любой формулы формула F понимается как «будет », а формула G понимается как «всегда будет ».

Между собой эти формулы связаны аксиомой: |– G F. К исчислению высказываний добавляются схемы аксиом:

F ( ) F F и F F |– F.

Возможность и необходимость определяются через F и G с помощью соотношений:

= F и = G.

7.3. Алгоритмические логики. Алгоритмические логики создаются с целью описания семантики языков программирования и включают формулы вида {}S{}. Эта формула означает, что если до выполнения оператора S было истинно, то после его выполнения будет истинно ».

В частности алгоритмическая логика Ч.Хоара определяет язык программирования через логическую систему аксиом и правил вывода для доказательства частичной правильности программ. Установлено, что определение семантики языка не в терминах выполнения программы, а в терминах доказательства ее правильности, упрощает процесс построения программы.

7.4. Нечеткая логика. Рассмотрим более подробно элементы нечеткой логики, благодаря которой появилась реальная возможность приближения математических рассуждений к тем принятым схемам, которые используют люди в процессе непосредственного общения.

1. Основные понятия. Нечеткая логика – многозначная логика, позволяющая учитывать для таких традиционных оценок, как да/нет, истинно/ложно, черное/белое промежуточные значения. Булева логика есть подмножество нечеткой логики, расширяющее ее возможности за счет включения неопределенности в логические выводы. Основное отличие нечеткой логики от классической заключается в том, что она оперирует не только значениями истинно/ложно, но и промежуточными, быть может, расплывчатыми и субъективными представлениями. Впервые термин нечеткая логика был введен американским профессором Лотфи Заде в 1965 году в работе «Нечеткие множества» в журнале «Информатика и управление».

Нечеткая логика представляет собой исчисление высказываний, у которого всякая пропозициональная переменная A интерпретируется некоторым значением P(A)=c (где c – элемент числового интервала [0,1], задающий степень четкости для переменной A.

В основе нечеткой логики лежит теория нечетких множеств (точнее – нечетких подмножеств данного множества), созданная как расширение традиционной теории множеств и унаследовавшая многие ее черты и особенности.

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

1) Множество E, которое содержит все рассматриваемые элементы.

2) Множество значений B, выступающих в качестве меры степени принадлежности некоторого элемента множеству E. В нечеткой логике в этом роли выступает действительный интервал [0;

1]. При этом нулевому значению соответствует тот факт, что A x элемент не принадлежит рассматриваемому нечеткому множеству, единица свидетельствует о том, что элемент совершенно определенно 0, принадлежит рассматриваемому нечеткому множеству. Промежуточные значения 0, интервала (0;

1) соответствуют вероятностной 0, оценке степени принадлежности отдельного элемента рассматриваемому нечеткому x x1 x2 x3 x4 x множеству.

Рис.5 Графическое задание, определяющее состав 3) Правило нечеткого множества нечеткого множества. В соответствии с этим правилом каждому элементу из множества E ставится в соответствие элемент из множества B.

Функцией принадлежности множеству E называется отображение A : E [0;

1], которое ставит в соответствие каждому элементу из множества E степень принадлежности ему. Пара A E, A называется нечетким множеством A. На одном и том же множестве различные функции принадлежности будут задавать различные нечеткие множества.

Четкая (детерминированная) принадлежность элемента x множеству E дается с помощью схемы:

xE 0, f ( x), x E, xE 1, 2. Способы задания нечеткого множества. Нечеткое подмножество A может быть задано аналитически, таблично и графически.

Пример 1. Пусть E ={x1, x2,…,x5}, M=[0;

1].

Зададим нечеткое подмножество A аналитически:

а) ( 1 ) 0, 2, ( 2 ) 0, 4, ( 3 )0, ( 4 ) 0,7, ( 5 ) 1 ;

б) А=0,2|х1+0,4|х2+0|х3+0,7|х4+1|х5;

в) A={0,2|х1;

0,4|х2;

0|х3;

0,7|х4;

1|х5};

г) A={ (х1,0.2);

(х2,0.4);

(х3,0);

(х4,0.7);

(х5, 1)};

Зададим нечеткое подмножество A таблично:


х1 х2 х3 х4 х 0,2 0,4 0 0,7 2. Зададим нечеткое подмножество A графически (рис.5):

Пример 2. Формализуем неточное определение понятия «ГОРЯЧИЙ ЧАЙ». В качестве X (область рассуждений) будет выступать шкала температуры в градусах Цельсия. Очевидно, что она изменяется от 0 до 100 градусов. Нечеткое множество для понятия «горячий чай» может выглядеть следующим образом:

C={0/0;

0/10;

0/20;

0,15/30;

0,30/40;

0,60/50;

0,70/60;

0,80/70;

0,90/80;

1/90;

1/100}.

Так, чай с температурой 70С принадлежит к множеству «горячий» со степенью принадлежности 0,80. Для одного человека чай при температуре 70С может оказаться горячим, для другого – не очень. В этом и проявляется нечеткость задания соответствующего множества.

3. Основные характеристики нечеткого множества. Носителем нечеткого множества A называется четкое множество A supp A таких элементов множества E, для которых A {x | ( x) 0}. Высотой нечеткого множества A называется величина sup ( x).

A A xE Нечеткое множество A называется нормальным, если sup A ( x) 1, т.е. верхняя граница xE его функции принадлежности равна 1. В противном случае оно называется субнормальным. Нечеткое множество называется пустым, если x E A ( x) 0. В заданном универсальном множестве E существует единственное пустое нечеткое множество. Непустое субнормальное нечеткое множество можно привести к нормальному A ( x) (нормализовать) по формуле A ( x). Множеством уровня или -срезом sup A ( x) xE нечеткого множества A называется четкое подмножество A E, определяемое по A {x | A ( x) }, где [0, 1]. Понятие множества уровня является формуле расширением понятия интервала. Точка перехода нечеткого множества A – это такой элемент x E, для которого A ( x) 0,5.

4. Логические операции над нечеткими множествами.

1) Включение A B. Пусть A и B – нечеткие подмножества на универсальном множестве E. Множество A содержится в B, если x E A ( x) B ( x). Говорят: «A содержится в B», или «B доминирует над A», или «нечеткое множество A является нечетким подмножеством B».

2) Равенство A = B. Нечеткие множества A и B равны, если x E : A ( x) B ( x).

3) Дополнение A B и B A. A и B – нечеткие подмножества, заданные на универсальном множестве E. A и B дополняют друг друга, если x E A ( x) 1 B ( x). В частности, A =A.

4) Пересечение двух нечетких множеств (нечеткое «И») A B – наибольшее нечеткое подмножество, содержащееся одновременно в A и B, с функцией принадлежности:

A B ( x) = min (A(x), B(x)).

5) Объединение двух нечетких множеств (нечеткое «ИЛИ») A B – наименьшее нечеткое подмножество, содержащееся как в A, так и B, с функцией принадлежности:

A B ( x) = max (A(x), B(x)).

6) Разность A B A B, с функцией принадлежности:

A–B(x)= A B ( x) =min (A(x), 1–B(x)).

7) Дизъюнктивная сумма A B ( A B ) ( B A) ( A B ) ( B A) с функцией принадлежности: A B ( x) max(min( A ( x),1 B ( x)), min(1 A ), B ( x)).

Пример 3. Пусть A={(x1,0.4),(x2,0.7),(x3,0.9)} и B={(x1,0.5),(x2,0.3),(x3,1)}.

Тогда 1) A = {(x1,0.6),(x2,0.3),( x3,0.1)} и B = {(x1,0.5), (x2,0.7), (x3,0)};

2) C = A B = { (x1,0.5), (x2,0.7), (,1)};

3) D = A B ={(x1,0.4),(x2,0.3), (, 0.9)};

4) A–B={(x1,0.4),(x2,0.7),(x3,0.9)} {(x1,0.5),(x2,0.7),(x3,0)}={(x1,0.4),(x2,0.7),(x3,0)}, 5)B–A = {(x1,0.5), (x2,0.7), (x3,0)} {(x1,0.6),(x2,0.3),(x3,0.1}={(x1,0.5),(x2,0.3),(x3,0.1)};

6) A B ={(x1,0.4),(x2,0.7),(x3,0)}{(x1,0.5),(x2,0.3),(x3,0.1)}= {(x1,0.5),(x2,0.7),(x3,0.1)}.

Свойства операций объединения и пересечения нечетких множеств во многом похожи на аналогичные свойства в теории множеств: выполняется коммутативность, ассоциативность, дистрибутивность, идемпотентность, операции с тривиальными подмножествами, законы де Моргана. В отличие от четких множеств, для нечетких множеств не выполняется закон исключенного третьего: A A E и A A.

Для наглядного представления о логических операциях над нечеткими множествами построим их функции принадлежности в системе координат на плоскости.

Пример 4. Пусть заданы графически два нечетких множества: A: «от 5 до 10»

(рис.6а) и B: «около 3» (рис.6б). Построить графически функцию принадлежности для логических операций над этими множествами.

Решение: Отложим на оси абсцисс значения x, а на оси ординат – значения функции принадлежности. Получим графики функций A B (рис. 6в), A B (рис. 6г), A (рис. 6д) а) б) A B Рис.6:

x x 0 5 10 0 A B A B A 1 1 x x x 0 3 5 10 0 3 5 10 0 5 в) г) д) 5. Алгебраические операции над нечеткими множествами.

Алгебраическое произведение. Произведение двух нечетких множеств A·B, заданных на одном и том же базовом множестве E, называется такое нечеткое множество F = A·B, функция принадлежности которого определяется по правилу x E: F ( x) A ( x) B ( x).

Алгебраическая сумма. Суммой двух нечетких множеств A и B, заданных на одном и том же базовом множестве E, называется нечеткое множество Н = A B, содержащее множества A и B, причем функция принадлежности определяется по правилу:

x E: H ( x) A ( x) B ( x) A ( x) B ( x).

Замечание. Операции умножения и суммирования нечетких множеств употребляются значительно реже, чем операции пересечения и объединения, поскольку для них не выполняются некоторые законы, в том числе распределительный, идемпотентности, исключенного третьего.

Возведение в степень. Пусть задано нечеткое множество A, заданное на базовом множестве E. Возведением в (неотрицательную) степень « » нечеткого множества A называется нечеткое множество K A,[ A ( x)].

Возведение нечеткого множества в квадрат является операцией концентрирования (уплотнения): (Рис.7).

Извлечение квадратного корня из нечетного множества, рассматриваемое как возведение в степень 0.5, является операцией A x растяжения:

1, Пример 6. Пусть A={0,4| x1+0,7| x2 +0,9|x3}, 0,5 A2 A A0,5 B=0,8| x1 +0,3| x2 +1|x3}.

Тогда F = A·B = {0,32| x1+0,21| x2 +0,9| x3 }, x Н = A B = {0,88| x1+0,79| x2 +1| x3 }, Рис.7. Операции концентрирования A и А = {0,16| x1+0,49| x2 +0,81| x3}, 0, А0,5 = {0,63| x1+0,84| x2 +0,95| x3}.

растяжения A нечеткого множества A.

Декартово (прямое) произведение нечетких множеств. Пусть А1, А2,…, Аn – нечеткое подмножества универсальных множеств E 1, E 2,…, En соответственно. Декартово (прямое) произведение A=А1 А2 … Аn нечетких множеств является нечетким Е=Е1 Е2 … Еn подмножеством множества с функцией принадлежности A ( x1, x2,..., xn ) min( A1 ( x1 ), A2 ( x2 ),..., An ( xn )).

Нечетким евклидовым расстоянием между двумя нечеткими множествами A= X, A и B= X, B, заданных на одном и том же множестве X, называется величина ( xi ) B ( xi ) e( A, B ) A i Ближайшим к данному нечеткому множеству A называется четкое множество A*, расположенное на наименьшем евклидовом расстоянии от A. Это множество определяется функцией принадлежности:

A ( x) 0,5;

0, A* ( x) 0 1, A ( x) 0, A ( x) 0,5;

1, Пример 7. Пусть заданы два множества:

A = {( |0,1), ( |0,3), ( |0,7), ( |0,8), ( |0,9), ( |1)} B = {( |0), ( |0), ( |0,6), ( |0,8), ( |1), ( |1)}.

Тогда e(АВ) = 0.346, а ближайшим к нечеткому множеству A является четкое множество A {x4, x5, x6, x7 }.

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

1) Треугольная функция принадлежности определяется тройкой чисел (a,b,c), ее значение в точке x вычисляется по выражению (Рис.8а):

bx 1 b a, a x b, xc A ( x) 1, b x c, cb 0, x [a, c].

Второе число b тройки a, b, c обычно называют модой или четким значением нечеткого треугольного числа. Числа a и c характеризуют степень «размытости» четкого числа.

2) Трапецеидальная функция принадлежности определяется четверкой чисел (a, b, c, d), ее значение в точке x вычисляется по выражению bx 1 b a, a x b, A ( x) 1, x c b x c,, c x d, d c x [a, d ].

0, Графическое представление этой функций принадлежности изображено на рис. 8б:

A x A x 1 a b c a b c d а) Треугольная функция б) Трапецеидальная принадлежности функция принадлежности Рис.8. Типовые кусочно-линейные функции принадлежности.

3) Функция принадлежности гауссова типа описывается формулой:

x c A ( x) exp и оперирует двумя параметрами: параметр c обозначает центр нечеткого множества, а параметр отвечает за крутизну функции. График представлен на рис. A x Рис.9. Гауссова функция принадлежности.

с 0 x 7. Нечеткие и лингвистические переменные. Формализация нечетких понятий и отношений естественного языка возможна на основе понятий нечеткой и лингвистической переменных. Зададим нечеткую и лингвистическую переменные как формальные системы по известным правилам построения формальных систем.

Нечеткой переменной называется кортеж X, E,C, где X – название переменной;

E – универсальное множество (область определения переменной X), C – нечеткое множество на E, описывающее нечеткое ограничение на значения переменной X (т.е. C ( x) для переменной X.

Множество C описывает семантику нечеткой переменной, его называют функцией совместимости нечеткой переменной. Переменная x является для X базовой переменной.

Множество C определяет ту степень, с которой элементу x соответствует значение C ( x).

Значения нечеткой переменной есть числа.

Пример 8. Нечеткая переменная X, именуемая «ЧЕЛОВЕК ВЫСОКОГО РОСТА».

Положим E = (170;

200), а C определим следующим образом:

200 C 1 1 0, 2 u 170 Лингвистическая переменная – набор (X,T(X),E,G,M) где X – название переменной, T(X) – терм, т.

е. множество значений лингвистической переменной, E – универсальное множество, G – синтаксическое правило, порождающее название для значений переменной, M – семантическое правило, которое ставит в соответствие переменной ее смысл. В настоящее время все большее распространение получает способ описания сложных систем с помощью лингвистических переменных, учитывающий не количественные, а качественные характеристики. Лингвистические переменные с заданной долей уверенности дают возможность поставить в соответствие качественным значениям их количественную интерпретацию. В основе понятия лингвистической переменной лежит понятие нечеткая переменная, обозначающее нечеткое множество, которому присвоено некоторое название.

Пример 9. Рассмотрим понятие «РОСТ ЧЕЛОВЕКА». Если рост ниже 150 см, то такого человека считают низкорослым, а выше 180 см – высоким. В зависимости от ситуаций и требований, человека с ростом в промежутке от 150 до 180 см могут считать и высоким, и низким с определенной долей вероятности. Поэтому нет четкой границы при делении людей на высоких и низких. Так, человек с ростом 175 см будет низким в команде волейболистов, но высоким среди акробатов.

Для задания лингвистической переменной «РОСТ ЧЕЛОВЕКА» необходимо рассмотреть возможности формализации ее составляющих. Для этого зададим:

1) Универсальное множество E, содержащее все возможные элементы, исходя из условия. В нашем примере это рост человека, например, в интервале (0;

300).

2) Множество значений, выступающее в качестве меры степени принадлежности некоторого элемента из E нечеткому подмножеству A. Промежуточные значения соответствуют определенной степени вероятности (принадлежности), что этот элемент принадлежит подмножеству.

Так, человек с ростом 175см будет входить в подмножество высоких людей со степенью принадлежности 1, а в подмножество низкорослых людей со степенью принадлежности 2. Однако человек с ростом 200см будет входить в подмножество высоких людей со степенью принадлежности 1=1, а в подмножество низкорослых людей со степенью принадлежности 2=0.

3) Правило, определяющее состав нечеткого множества, т.е. правило, по которому, каждому элементу из множества E ставится в соответствие элемент из множества B, иначе: определить отображение : E B.

В отличие от общепринятых, нечеткие множества обладают размытыми границами:

их элементы – лингвистические переменные – в служат качественными характеристиками объектов (высокий, умный, новый, большой, сильный и др.) Пример 10. Рассмотрим такое нечеткое понятие как «ЦЕНА АКЦИИ». Это и есть название лингвистической переменной. Сформируем для нее базовое терм-множество, которое будет состоять из трех нечетких переменных: «Низкая», «Умеренная», «Высокая»

и зададим область рассуждений в виде X=[1ОО;

200] (единиц). Построим функции принадлежности для каждого лингвистического терма базового терм-множества T.

Совокупность функций принадлежности для каждого терма базового терм множества T обычно изображаются вместе на одном графике. На рис.10 изображена лингвистическая переменная «ЦЕНА АКЦИИ».

A x Цена акции Умеренная Низкая Высокая 100,00 160,00 200, F 1 0, 00 F 2 0, 75 F 3 0, Рис.10 Описание лингвистической переменной «ЦЕНА АКЦИИ».

Лингвистическая переменная более высокого порядка, чем нечеткая переменная, т.к.

значениями лингвистической переменной являются нечеткие переменные. Количество термов в лингвистической переменной редко превышает 7. Различают числовые и нечисловые лингвистические переменные. Лингвистическая переменная называется числовой, если ее область определения E есть подмножество множества действительных чисел. Значение числовой лингвистической переменной называют нечеткими числами.

Пример 11. Нечисловые лингвистические переменные:

– «КРАСИВЫЙ», формализующая, например, понятие «красивый дом» со значениями «не очень красивый», «красивый», «очень-очень красивый» и т.п.;

– набор значений лингвистической переменной «КАЧЕСТВО»: {«низкое», «среднее», «хорошее», «высокое»}.

8. Нечеткие отношения. Пусть E=Е1 Е2 … Еn – декартово произведение n универсальных множеств Е1,Е2,…,Еn Нечеткое подмножество четкого множества называется n-арным нечетким отношением на Р :, где R X 1 X 2... X n Нечеткое отношение как и нечеткое множество можно задать с помощью его функции принадлежности M R : X 1 X 2... X n L, где L — это частично упорядоченное множество, в котором любое непустое подмножество имеет наибольшую нижнюю и наименьшую верхнюю грани и операции пересечения и объединения в L удовлетворяют законам дистрибутивности.

Величина есть мера того, что совокупность ( ) принадлежит отношению. Знак в данном случае обозначает объединение соответствующих одноточечных множеств ( ).

На практике чаще других используются бинарное нечеткое отношение, заданное на произведении двух множеств, например X и Y ( ):

Бинарное отношение может рассматриваться в качестве двухмерного предиката.

Примеры нечетких отношений: «расстояние в пространстве значительно больше 100м» тернарное отношение на множестве точек трехмерного пространства;

«X – дальний родственник Y» - бинарное отношение на множестве людей.

Нечеткие бинарные отношения удобно задавать в виде матрицы.

Пример 12. – нечеткое отношение «X значительно меньше Y», заданное на множествах Ex = (9,18,21) и Ey= (12,23,45) может быть задано матрицей:

12 23 9 0, 7 0,9 R2 18 0 0,3 21 0 0,1 0, Содержательно это означает, например, следующее: со степенью уверенности лишь 0,7 можно утверждать, что 9 значительно меньше 12;

18 значительно меньше 45 со степенью уверенности 1, а 21 значительно меньше 23 со степенью уверенности 0,1.

Нечеткому бинарному отношению можно поставить в соответствие нечеткий граф.

Нечетким графом G на множествах E1 и E2 называется такое нечеткое подмножество, что ( xi, yi ) E1 E2 : G ( xi, yi ) M, где M – множество принадлежностей элементов множества. Так, нечеткое отношение в примере 12 можно представить графически в виде графа, изображенного на рис.11,а.

В случае конечных или счетных универсальных множеств возможна интерпретация нечеткого отношения в виде взвешенного графа, в котором каждая пара вершин (x,y) из X Y соединяется ребром с весом R(x,y).

Пример 13. Пусть X={x1,x2, x3} Y={y1,y2,y3}. Тогда нечеткий граф, изображенный на рис.11,б, задает некоторое нечеткое отношение R X Y.

y1 y2 y x1 1 0 0, R2 x2 0,8 0, 6 x3 0,8 0,3 0, 0,7 x1 y 9 0, 0, 0, 0 0,3 x2 y 18 0 0, 1 0, 0, 0, 0, x3 y 21 45 0, 0, а) б) Рис.11.

Над нечеткими отношениями можно определить так же операции, что и над четкими отношениями.

Объединение R1 R2 и пересечение R1 R2 нечетких отношений определяются через задание функции принадлежности:

R1 R2 ( x, y ) R1 ( x, y ) R2 ( x, y ) и R1 R2 ( x, y ) R1 ( x, y ) R2 ( x, y ).

Алгебраическая сумма R1 R2 и алгебраическое произведение R1R2 двух отношений определяются через задание функции принадлежности:

R1 R2 ( x, y ) R1 ( x, y ) R2 ( x, y ) R1 ( x, y ) R2 ( x, y ) и R1 R2 ( x, y ) R1 ( x, y ) R2 ( x, y ).

Нечеткое множество A может рассматриваться как значение некоторой лингвистической переменной. Поскольку операции над нечеткими множествами определяются операциями над их функциями принадлежности, то при исследовании алгебраических свойств нечетких множеств, часто нечеткое множество отождествляют с его функцией принадлежности.

Значение степени принадлежности. Степень принадлежности может трактоваться по-разному в зависимости от задачи, в которой используется нечеткое множество.

Возможные трактовки степени принадлежности: степень соответствия понятию A, вероятность, возможность, полезность, истинность, правдоподобность, значение функции.

Для каждой трактовки степени принадлежности разработаны свои методы построения функций принадлежности.

Нечеткая логика: достоинства и недостатки. Для описания неопределенностей в задачах автоматического управления используются три метода:

– вероятностный (стохастический);

– использование нечеткой логики (fuzzy logic);

– хаотические системы.

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

Нечеткие числа, получаемые в результате «не вполне точных измерений», во многом аналогичны распределениям теории вероятностей. При возрастании точности, нечеткая логика приходит к стандартной, булевой. По сравнению с вероятностным методом, нечеткий метод позволяет резко сократить объем производимых вычислений, что приводит к увеличению быстродействия нечетких систем.

Недостатки нечетких систем: отсутствие стандартной методики конструирования нечетких систем, невозможность математического анализа нечетких систем существующими методами, применение нечеткого подхода по сравнению с вероятностным не приводит к повышению точности вычислений.

Литература: [5], гл.2;

[11], ч.5.

Лекция № 8. Сложность вычислений Алгоритмически неразрешимые проблемы. Представление об алгоритмически разрешимых и неразрешимых проблемах. Меры сложности алгоритмов. Легко и трудно разрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений. Эффективные алгоритмы.

Рассмотрим задачу проверки равенства двух булевых функций f(х1, х2,…, хn) и g(х1, х2,…, хn). Как известно, решение этой задачи заключается в составлении таблиц истинности для перебора всех вариантов возможных значений аргументов (1,2,…,n){0,1} для проверки 2n соотношений вида f(1,2,…, n)= g(1,2,…,n). Задачи такого вида называются переборными и сводятся к решению некоторой универсальной задачи.



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.