Операции с нечеткими множествами

 

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

Пусть и – два нечетких множества с функциями принадлежности m_A(x) и m_B(x).

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

Табл. 4. 1

Операции	Лингвистический смысл	Формула для mC(x)
Пересечение = Ç Объединение = È   Дополнение   Концентрация   Размывание	и     или     не   очень   не очень	min(mA(x), mB(x))   max(mA(x), mB(x)).     1 – mA(x)   [mA(x)]2   [mA(x)]1/2

 

Нечеткое множество называется пустым, если m_A(x) = 0 для всех xÎ X.

Пример 4.4.

Пусть X – множество студентов, – множество пожилых людей. Множество – пустое, m_A(x) = 0 для всех xÎ X, так как пожилых студентов, вообще говоря, не бывает.

Введенные для нечетких множеств операции позволяют конструировать сложные понятия из простых: очень много, не старше и не моложе и т. д. По аналогии с четкими множествами определяется отношение включения множества в множество , а именно является подмножеством тогда и только тогда, когда m_A(x) £ m_B(x) для всех xÎ X.

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

Нечеткие высказывания

Определение 4.2. Нечетким высказыванием называется высказывание , степень истинности которого m( ) можно оценить числом из интервала [0, 1], m( ) Î [0, 1]. Если m( ) = 0, 5, то высказывание называется индиффирентным.

Определение 4.3. Нечеткой высказывательной переменной называется нечеткое высказывапние , степень истинности которого может меняться в интервале [0, 1].

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

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

1. Отрицание нечеткого высказывания:

 =1– . (4.1)

2. Конъюнкция нечетких высказываний:

& =min( , ). (4.2)

3. Дизъюнкция нечетких высказываний:

V =max( , ). (4.3)

4. Импликация нечетких высказываний:

 =max(1– , ). (4.4)

5. Эквивалентность нечетких высказываний:

~ = min (max (1 – , ), max ( , 1 – )). (4.5)

Старшинство операций принято в поядке1) – 5).

Пример 4.5.

Найти степень истинности высказывания

= ( V ) ~ (    & )) при = 0, 8; = 0, 3.

Порядок действий определяется старшинством операций и скобками.

1. & = min(0, 8; 0, 3) = 0, 3.

2. (    & ) = max (1 – 0, 8; 0, 3) = 0, 3.

3. V = max (0, 8; 0, 3) = 0, 8.

4. = min (max (1 – 0, 8; 0, 3), max (0, 8; 1 – 0, 3)) = min(0, 3; 0, 8) = 0, 3.

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

Определение 4.4. Нечеткой логической формулой называется:

а) любая нечеткая высказывательная переменная;

б) если и – нечеткие логические формулы, то  , & , V ,  , ~ – тоже нечеткие логические формулы.

Определение 4.5. Пусть ( ₁, ₂, …, _n) и ( ₁, ₂, …, _n) – две нечеткие логические формулы. Степенью равносильности формул и называется величина

m( , )= { (a₁, a₂, …, a_n)~ (a₁, a₂, …, a_n)} (4.6)

Здесь логические операции конъюнкции и эквивалентности имеют смысл, определенный выше для логических операций над нечеткими высказываниями, причем конъюнкция берется по всем наборам степеней истинности (a₁, a₂, …, a_n) нечетких переменных ( ₁, ₂, …, _n).

Множество всех наборов степеней истинности (a₁, a₂, …, a_n) нечетких переменных ( ₁, ₂, …, _n) назовем полной областью определения Cⁿ. Очевидно, что множество Cⁿ имеет мощность континнуума в отличие от двузначной логики высказываний, где число всех наборов переменнх конечно и равно 2ⁿ.

Если m( , ) = 0, 5, то нечеткие формулы и называются индиффирентными.

Если m( , ) > 0, 5, то нечеткие формулы и называются нечетко равносильными.

Если m( , ) < 0, 5, то нечеткие формулы и называются нечетко неравносильными..

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

( , ) = 1 – m( , ).

Пример 4.6

Определить степень равносильности формул.

=   ,   =   &    при условии, что и  прнимают значения степеней истинности из множества {0, 1; 0, 2}. Перечислим все возможные наборы значений и 

A₁ = {0, 1; 0, 1}; A₂ = {0, 1; 0, 2}; A₃ = {0, 2; 0, 1}; A₄ = {0, 2; 0, 2}.

Запишем формулы и с учетом (4.1), (4.2), (4.4):

=      max (1 – , ); =   &        1 – &     1 – min( , ).

Вычислим формулы и на каждом из четырех наборов A₁ – A₄:

₁ = max (1 – 0, 1; 0.1) = 0, 9.

₂ = max (1 – 0, 1; 0, 2) = 0, 9.

₃ = max (1 – 0, 2; 0, 1) = 0, 8.

₄ = max (1 – 0, 2; 0, 2) = 0, 8.

₁ = 1 – min( 0, 1; 0.1) = 0, 9.

₂ = 1 – min(0, 1; 0, 2) = 0, 9.

₃ = 1 – min(0, 2; 0, 1) = 0, 9.

₄ = 1 – min (0, 2; 0, 2) = 0, 8.

Вычислим теперь степень равносильности формул и в соответствии с (4.6):

Для этого сначала вычислим (a₁, a₂, …, a_n) ~ (a₁, a₂, …, a_n)} для всех наборов A₁ – A₄:

В соответствии с (4.5) имеем

~ = min (max (1 – , ), max ( , 1 – )).

Поэтому

₁ ~ ₁ = min (max (1 – 0, 9; 0, 9), max (0, 9; 1 –0, 9)) = 0, 9.

₂ ~ ₂ = min (max (1 – 0, 9; 0, 9), max (0, 9; 1 –0, 9)) = 0, 9.

₃ ~ ₃ = min (max (1 – 0, 8; 0, 9), max (0, 8; 1 –0, 9)) = 0, 8.

₄ ~ ₄ = min (max (1 – 0, 8; 0, 8), max (0, 8; 1 –0, 8)) = 0, 8.

Окончательно по (4.6) получим

m( , ) = { (a₁, a₂, …, a_n) ~ (a₁, a₂, …, a_n)} = 0, 9& 0, 9& 0, 8& 0, 8 = min(0, 9; 0, 9; 0, 8; 0, 8) = 0, 8.

Формулы и нечетко равносильны.

На других наборах степеней истинности нечетких переменных и формулы и могут быть нечетко неравносильны.

Определение 4.7. Пусть ( ₁, ₂, …, _n) и ( ₁, ₂, …, _n) – две нечеткие логические формулы, рассмотренные на некотором множестве M изменения нечетких переменных ₁, ₂, …, _n. Областью нечеткой равносильности формул и называется подмножество множества M, на котором формулы и нечетко равносильны.

Пример 4.7.

Вернемся к примеру 4.7. Для этого примера множество M состоит из девяти наборов:

M = {{0, 1; 0, 1}; {0, 1; 0, 2}; {0, 2; 0, 1}; {0, 2; 0, 2}}.

На каждом наборе формулы и нечетко равносильны, так как m( , ) > 0, 5. Поэтому областью нечеткой равносильности будет все множество M.

Определение 4.8. Если формула ( ₁, ₂, …, _n) на всех наборах переменных ₁, ₂, …, _n из некоторого множества M имеет степень истинности большую или равную 0, 5, то она будет на нем нечетко истинной. Обозначается это так: = .

Определение 4.9. Если формула ( ₁, ₂, …, _n) на всех наборах переменных ₁, ₂, …, _n из некоторого множества M имеет степень истинности меньшую или равную 0, 5, то она будет на нем нечетко ложной. Обозначается это так: = .

Пример 4.8.

Покажем, что V  = и &  = для всех значений нечеткой переменной :

0 £ £ 1.

Учитывая (4, 1), (4.2), (4. 3), имеем

V  = max ( ,  ) = max ( , 1 – ) ³ 0, 5.

&  = min( ,  ) = min( , 1 – ) £ 0, 5.

Нечеткие предикаты

Определение 4.10. Нечетким предикатом (x₁, x₂, ..., x_n) называется нечеткая формула, переменные которой определены на некотором множестве М, x₁, x₂, ..., x_n M, а сама она принимает значения из интервала [0, 1].

Нечеткий предикат от n переменных называется n-местным нечетким предикатом. Нечеткое высказывание , задаваемое степенью истинности m( ) Î [0, 1] является одноместным нечетким предикатом..

Пример 4.9.

Пусть М = {0, 1, 2, 3}. Зададим нечеткий предикат следующим образом: (x, y) = xy/9. Его значения определяются следующим образом: (0, y) = (x, 0) = 0; (1, 1) = 1/9; (1, 2) = (2, 1) = 2/9; (2, 2) = 4/9; (1, 3) = (3, 1) = 1/3; (2, 3) = (3, 2) = 2/3; (3, 3) = 1;

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

(x₁, x₂, ..., x_n) = (x₁, x₂, ..., x_n) = (x₁, x₂, ..., x_n).

(x₁, x₂, ..., x_n) = (x₁, x₂, ..., x_n) = (x₁, x₂, ..., x_n).

Пример 4.10.

Найдем значения степени истинности формул (x, 1) и (x, 1) для примера 4.9:

(x, 1) = min{ (0, 1); (1, 1); (2, 1); (3, 1)} = min{0; 1/9; 2/9; 1/3} = 0.

(x, 1) = max { (0, 1); (1, 1); (2, 1); (3, 1)} = max {0; 1/9; 2/9; 1/3} = 1/3.

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

 

 

ТЕМА 5. АЛГОРИТМЫ

5.1. Определение алгоритма

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

1. Сортировка массива чисел в порядке возрастания.

2. Вычисление таблицы значений булевой функции, заданной формулой.

3. Вычисление чисел Фибоначчи по рекуррентному соотношению.

4. Решение системы линейных алгебраических уравнений методом исключения Гаусса.

Основные требования к алгоритмам

1. Алгоритм применяется к исходным данным и дает результаты. Кроме того, в процессе работы алгоритма могут появляться промежуточные данные. Итак, каждый алгоритм имеет дело с данными: исходными, промежуточными и выходными. Данными могут быть числа, векторы, матрицы, массивы, формулы, рисунки (в графических системах).

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

3. Алгоритм состоит из отдельных элементарных шагов или действий. Причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных действий – система команд ЭВМ.

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

5. Алгоритм должен удовлетворять требованию результативности, т. е. остановки после конечного числа шагов. В таком случае говорят, что алгоритм сходится.

Любая практическая задача требует предварительного задания исходных данных. Как правило, можно задать некоторое характерное число n. Например, для задачи сортировки массива чисел по возрастанию n – число чисел в массиве, для задачи решения системы линейных уравнений n – число уравнений. Характерное число задачи определяет размерность задачи как величину массива исходных данных.

С ростом характерного числа размерность задачи возрастает. Введем понятие скорости роста для функций, зависящих от целочисленного параметра n.

Определение 5.1. Функции f(n) и g(n) имеют одинаковую скорость роста, если при достаточно больших n, начиная с некоторого n₀, выполняется условие:

C₁g(n) £ f(n) £ C₂g(n),

где C₁, C₂ – некоторые константы.

Определение 5.2. Скорость роста функции f(n) ограничена снизу скоростью роста функции g(n), если при достаточно больших n, начиная с некоторого n₀, выполняется условие:

C₁g(n) £ f(n),

где C₁ – некоторая константа.

Определение 5.3. Скорость роста функции f(n) ограничена сверху скоростью роста функции g(n), если при достаточно больших n, начиная с некоторого n₀, выполняется условие:

f(n) £ C₂g(n),

где C₂ – некоторая константа.

Определение 5.4. Скорость роста функции f(n) больше скорости роста функции g(n), если для любой сколь угодно большой константы C₂ существует некоторое n₀, начиная с которого выполняется условие:

f(n) ³ C₂g(n).

Для того чтобы более наглядно представить скорости роста функций, их сравнивают со скоростями роста хорошо известных функций. В качестве таковых чаще всего используют степенные функции n^a. При a = 1 скорость роста функции n^a называют линейной, при a = 2 – квадратичной, при a = 3 – кубической и т. д. Скорость роста вида n^a называют полиномиальной. Очевидно, что при возрастании a скорость роста тоже увеличивается. Для некоторых функций скорости роста превосходят в пределе при n ® ¥ любую полиномиальную скорость. Такими функциями являются, например, 2ⁿ, eⁿ, n!. Скорости такого типа называют экспоненциальными.

Обозначим через r(n) скорость роста размерности задачи. В задаче вычисления таблицы значений булевой функции n переменных скорость роста определяется таблицей значений переменных. Так как различных наборов переменных 2ⁿ, а каждый набор состоит из n символов, то размерность задачи равна n2ⁿ и скорость роста будет экспоненциальной. В задаче решения системы линейных алгебраических уравнений методом исключения Гаусса наиболее быстро растет число элементов матрицы системы уравнений размером n ´ n. Поэтому скорость роста размерности этой задачи будет квадратичной, r(n) = n².

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

Рассмотрим время реализации алгоритма – время счета.

Пусть при выполнении некоторого алгоритма выполняются элементарные операции t₁, t₂, …, t_k (арифметические, логические и другие). Среднее время выполнения этих операций обозначим через t₁, t₂, …, t_k. По аналогии с размерностью задачи введем понятие скорости роста числа выполняемых операций в зависимости от характерного числа n. Обозначим их для операций t₁, t₂, …, t_k через g₁(n), g₂(n), …, g_k(n). Без доказательства приведем следующее утверждение.

При n ® ¥ скорость роста общего времени счета T(n) равна максимальной из скоростей роста числа элементарных операций g₁(n), g₂(n), …, g_k(n) независимо от среднего времени их выполнения t₁, t₂, …, t_k.

Определение 5.5. Скорость роста общего времени счета T(n) называется вычислительной сложностью или просто сложностью алгоритма.

Обозначим сложность алгоритма через f(n). В зависимости от сложности все алгоритмы делятся на несколько классов.

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

Пример 5.1.

Рассмотрим задачу определения максимального элемента в массиве из n чисел. Поскольку число операций сравнения постоянно и равно n – 1, сложность алгоритма f(n) = n.

Определение 5.7. Экспоненциальными называются алгоритмы, сложность которых при возрастании n превышает полином любой степени.

В примерах 5.2 и 5.3 точные алгоритмы имеют экспоненциальную точность.

Пример 5.2.

Рассмотрим задачу коммивояжёра. Необходимо обойти n городов и вернуться в исходный пункт, так чтобы суммарный путь был минимальным. Количество всех возможных вариантов обхода равно 0.5n! Следовательно, сложность точного решения, основанного на переборе всех вариантов, равна f(n) = n!

Пример 5.3.

Рассмотрим задачу вычисления конъюнктивной нормальной формы (КНФ) булевой функции n переменных. Количество всех наборов переменных равно 2ⁿ. Количество всех операций при переборе всех дизъюнкций пропорционально n2ⁿ, Следовательно, сложность алгоритма f(n) = n2ⁿ.

Экспоненциальные алгоритмы практически могут быть реализованы только при малых значениях n (обычно при n < 10).

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

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

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

Машина Тьюринга

 

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

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

Первые работы по уточнению понятия алгоритм появились в 1936 – 1937 годах. Это были работы Тьюринга, Поста, Маркова, Чёрча. Было предложено несколько определений понятия алгоритм. Впоследствии было показано, что все они равносильны.

Одной из первых и весьма удачных попыток дать точный математический эквивалент интуитивного представления об алгоритме было введение понятия машины Тьюринга в 1937 году, за 9 лет до появления первой ЭВМ.

Машина Тьюринга – абстрактная машина. Это математическая модель идеализированного вычислительного устройства.

Машина Тьюринга состоит из ленты и управляющего устройства со считывающей и записывающей головки (каретки) (рис. 5.1).

 

 

Рис. 5.1

 

Лента жестко закреплена слева и бесконечна справа. Иногда считают, что лента не ограничена справа и слева. Лента разделена на ячейки, которые нумеруются натуральными числами 1, 2, ….

В каждую ячейку ленты заносятся символы внешнего алфавита машины Тьюринга

A={a₀, a₁,...a_n}. (5.1)

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

Головка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, то стоит против некоторой ячейки ленты; говорят, что головка обозревает эту ячейку.

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

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

Q={q₀, q₁,...q_m}. (5.2)

Множество Q называется внутренним алфавитом машины Тьюринга или алфавитом внутренних состояний.

Словом называется последовательность W = a_i1, a_i2, …, a_is символов, записанных в ячейках ленты, где a_i1 – символ, находящийся в самой левой непустой ячейке, а a_is – символ, находящийся в самой правой непустой ячейке. Количество символов s в слове называется длиной слова.

Пусть в некоторый момент времени t на ленте записано слово W, управляющее устройство находится в состоянии q_i, а каретка – напротив символа a_im слова W. Конфигурацией машины в момент времени t называется последовательность K = a_i1, …, a_{i(m – 1)}, q_i, a_im …, a_is. Конфигурации в начале и в конце работы называют соответственно начальной и заключительной.

Пример 5.4.

Пусть на ленте записано слово abcde, управляющее устройство находится в состоянии q_i и каретка стоит против символа d. Конфигурация в этом случае запишется так:

abcq_ide.

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

Если управляющее устройство в некоторый момент времени находится в состоянии q_i, обозревается символ a_j, в следующий момент времени записывается символ a_r, управляющее устройство переходит в состояние q_k, и каретка сдвигается, то говорят, что машина выполняет команду

a_jq_i®a_rSq_k, (5.3)

где S – сдвиг, S = L, если сдвиг влево, S = R, если сдвиг вправо, S = C, если каретка остается на месте.

Совокупность всех команд, которые может выполнить машина, называется ее программой. Условие однозначности требует, чтобы для любого j и любого i имеется только одна команда вида (5.3). Каждая машина Тьюринга полностью определяется своим алфавитом, внутренними состояниями и программой.

⇐ Предыдущая12345678

Поделиться: