Дипломированного специалиста

МГАПИ

 

УТВЕРЖДАЮ

 

Проректор по УР

____________ Соколов В.В.

«___» ___________ 2002 г.

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению контрольных заданий и лабораторных работ

по дисциплине

«Математическая логика и теория алгоритмов»

 

 

Рекомендуется для направления подготовки

Дипломированного специалиста

Информатика и вычислительная техника»

Специальности – 22.02.00.

Автоматизированные системы обработки

Информации и управления.

 

 

Москва 2002

АННОТАЦИЯ

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

 

 

Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.

Рецензент:

Рассмотрено и одобрено на заседании кафедры ИТ-7

" __" ____________2002 г. Зав. кафедрой __________О.М. Петров

Ответственный от кафедры за выпуск учебно-методических материалов

доц. Правоторова Н.А.

СОДЕРЖАНИЕ

Введение

Тема 1. Логика высказываний

1.1. Определение высказывания

1.2. Операции над высказываниями. Алгебра высказываний

1.3. Формулы логики высказываний. Равносильность формул

1.4. Запись сложного высказывания в виде формулы логики высказываний

1.5. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости

1.6. Формализация рассуждений. Правильные рассуждения

Тема 2. Логика предикатов

2.1. Определение предиката. Кванторы

2.2. Формулы логики предикатов. Равносильность формул

2.3. Приведенные и нормальные формулы

2.4. Выражение суждения в виде формулы логики предикатов

2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость

Тема 3. Формальные аксиоматические теории (исчисления)

3.1. Принципы построения формальных теорий

3.2. Исчисление высказываний

3.3. Исчисление предикатов

3.4. Автоматическое доказательство теорем. Метод резолюций.

Тема 4. Нечеткая логика

4.1. Нечеткие множества

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

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

Тема 5 Алгоритмы

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

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

5.3. Вычислимые по Тьюрингу функции

Указания к выполнению лабораторных работ

Контрольные задания по курсу “Математическая логика и теория алгоритмов”

Список литературы

Краткие сведения о математиках

 

ВВЕДЕНИЕ

Логика - одна из самых древних наук. Как самостоятельная наука логика оформилась в трудах греческого ученого Аристотеля ( 384 – 322 г. до н. э.) и стала впоследствии называться формальной или Аристотелевой логикой.

С момента своего возникновения и в течение многих веков логика рассматривалась как часть философии. Математическая логика возникла на стыке двух наук: традиционной или философской логики и математики.

Идея построения логики на математической основе была впервые выдвинута Лейбницем (1646 – 1716). Окончательно как раздел математики математическая логика сформировалась в работах Д. Буля (1815 – 1864), Г. Фреге (1848 – 1925), Б. Рассела (1872 – 1970), Д. Гильберта (1862 – 1943).

Математическая логика используется при решении трех групп задач.

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

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

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

 

ТЕМА 1. ЛОГИКА ВЫСКАЗЫВАНИЙ

 

Определение высказывания

Определение 1.1. Высказыванием называется повествовательное языковоепредложение, относительно которого можно сказать истинно оно или ложно.

Пример 1.1.

Следующие утверждения являются высказываниями:

а) Москву основал Юрий Долгорукий.

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

в) 2 2 = 5.

Высказывания а) и б) истинны, а высказывание с) ложно.

Пример 1.2.

Следующие утверждения не являются высказываниями:

а) a + b = 2.

б) Математика – интересный предмет.

В логике высказываний нас интересует не суть высказывания, а его истинность или ложность. Мы говорим, что существуют два истинностных значения: истина и ложь (И и Л). Двухэлементное множество {И, Л} есть множество истинностных значений. Высказывания будем обозначать большими буквами: A, B, C, X, Y,.. Выражение А = И означает, что высказывание А истинно, а X = Л означает, что высказывание X ложно.

 

Тождественно-истинные и тождественно-ложные формулы. Проблема

Разрешимости

Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.

Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.

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

Теорема 1.1 . Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в любую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание.

Теорема 1.2 . Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в любую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание.

Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной.

Пример 1.13.

Доказать, что формула F = (А É B) É ((C V А) É (C V B)) является тождественно-истинной.

Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(АÉ B) É ((CVА) É (CVB)) º Ø (АÉ B) V ((CVА) É (CVB)) º (А& Ø B) V Ø (CVА) V (CV B) º (А& Ø B) V (Ø C& Ø А) V (CVB) º (А VØ C)& (АV Ø А) & (Ø BVØ C) & (Ø B VØ А) V (CVB) º (АVØ C)& (Ø BVØ C)& (Ø BVØ А)V(CVB) º (АVØ CVCVB)& (Ø BVØ CVCVB)& (Ø BVØ АVCVB).

В первую дизъюнкцию входят C и Ø C. Во вторую – B и Ø B, C и Ø C. в третью – B и Ø B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.14.

Установить, является ли тождественно-истинной данная формула логики высказываний: f(A, B) = (А& (АÉ B)) É B.

1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А& (АÉ B)) É B º (А& (Ø АVB) É B º Ø (А& (Ø АVB) É B º Ø АVØ (Ø (АVB)VB º Ø АV(А& B)VB º (Ø АVB)VА& Ø B º (Ø АVBVА)& (Ø АVB Ø B).

В первую дизъюнкцию входят A и Ø A. Во вторую – B и Ø B, поэтому формула является тождественно истинной, f(A, B) º И.

2) Составим таблицу истинности f(A, B) (таблица 1.6):

Таблица 1.6

А B	АÉ B	А& (АÉ B)	(А& (АÉ B))É B
Л Л Л И И Л И И	И И Л И	Л Л Л И	И И И И

 

Из таблицы 1.6 видно, что f(A, B) º И.

 

ТЕМА 2. ЛОГИКА ПРЕДИКАТОВ

 

Исчисление высказываний

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

1 Символы исчисления высказываний включают в себя: а) знаки логических операций Ø, É; б) буквы X_i с целыми положительными индексами i; в) скобки и запятую – (, ).

2. Формулами исчисления высказываний являются:

а) все переменные X_i;

б) если A и B – формулы, то Ø A – формула и A É B – формула.

Хотя для исчисления высказываний выбраны только два логических символа Ø и É и только два типа формул Ø A и A É B, можно с помощью следующих известных равносильностей ввести и другие логические символы и формулы:

A & B º Ø (A É Ø B);

A V B º Ø A É B;

A ~ B º Ø (( A É B) É Ø ( B É A )).

3. Аксиомы исчисления высказываний. Существуют различные системы аксиом исчисления высказываний, обладающие свойствами непротиворечивости, независимости и полноты. Будем использовать следующую систему аксиом:

А1. A É (B É A);

А2. (A É (B É C)) É ((A É B) É (A É C));

А3. (Ø B É Ø A) É ((Ø B É A) É B).

Непосредственной проверкой можно убедиться, что аксиомы есть тождественно-истинные формулы. Например, для аксиомы А1:

A É (B É A) º Ø A V Ø B V A º И.

4. Правило вывода в исчислении высказываний одно – modus ponens (m. p.) – правило заключения:

, или A, AÉ B „ B.

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

Пример 3.1.

Если в правиле modus ponens переменную B заменить формулой A& B, получим правило вывода

.

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

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

Пример 3.2.

Построим вывод формулы A„ B É A.

(1) A – гипотеза;

(2) A É (B É A) – аксиома А1;

(3) – из (1) и (2) по m. p.

Очевидно, что любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: . Равносильность A É B º Ø B É Ø A порождает закон контрапозиции: .

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

1. Введение конъюнкции: .

2. Удаление конъюнкции: и .

3. Отрицание конъюнкции: .

4. Введение дизъюнкции: и .

5. Удаление дизъюнкции: и .

6. Отрицание дизъюнкции: .

7. Введение импликации: .

8. Удаление импликации: (m. p.) и .

9. Отрицание импликации: .

10. Введение эквивалентности: .

11. Удаление эквивалентности: и .

12. Введение отрицания: .

13. Удаление отрицания: .

14. Закон контрапозиции: .

Для построения выводов в исчислении высказываний полезной оказывается следующая теорема.

Теорема дедукции (без доказательства) . Пусть Г – множество формул, A и B – формулы, и имеет место вывод: Г, A „ B. Тогда имеет место следующий вывод: Г „ A É B.

Таким образом, если нужно вывести формулу вида A É B из множества формул (возможно, пустого), можно использовать дополнительное допущение A.

Важным следствием теоремы дедукции является правило силлогизма (дается без доказательства):

Правило силлогизма (транзитивный вывод) .

A É B, B É C „ AÉ C.

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

Пример 3.3.

а) Обосновать вывод A É (B É C), A& B „ C.

(1) A É (B É C) – гипотеза;

(2) A& B – гипотеза;

(3) A – из (2) и правила удаления конъюнкции;

(4) B É C – из (1), (3) и m. p.

(5) B – из (2) и правила удаления конъюнкции;

(6) C – из (4), (5) и m. p.

б) Обосновать правильность следующего рассуждения, построив вывод:

Если число целое, то оно рациональное, Если число рациональное, то оно действительное. Число целое. Значит, оно действительное.

Сначала формализуем наше рассуждение, введя следующие высказывания:

A = “число целое”.

B = “число рациональное”.

C = “число действительное”.

Нужно построить следующий вывод: A É B, B É C, A „ C.

Построим этот вывод.

(1) A É B – гипотеза;

(2) B É C – гипотеза;

(3) A – гипотеза;

(4) A É C – из (1) и (2) по правилу силлогизма;

(5) C – из (3) и (4) по m. p.

в) Обосновать правильность следующего рассуждения, построив вывод:

Если бы Иван был умнее Петра, он решил бы эту задачу. Иван не решил эту задачу. Значит, он не умнее Петра.

Формализуем наше рассуждение, введя следующие высказывания:

A = “Иван умнее Петра”.

B = “Иван решил эту задачу”.

Построим следующий вывод: A É B, Ø B „ Ø A.

(1) A É B – гипотеза;

(2) Ø B – гипотеза;

(3) Ø B É Ø A – из (1) по закону контрапозиции;

(4) Ø A – из (3) и (2) по m. p.

 

Исчисление предикатов

Исчисление предикатов определяется следующим образом.

1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x₁, x₂, …, x_n, …; б) символы предметных констант a₁, a₂, …, a_n, …; в) символы или имена предикатов A , A , …A , …; г) символы или имена функций f , f , …f , …; д) знаки логических операций Ø, É; е) символы кванторов ", $; ж) скобки и запятую – (, ),.

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

2. Понятие формулы исчисления предикатов определяется в два этапа [4].

1) Термы:

а) предметные переменные x₁, x₂, …, x_n, ... и константы a₁, a₂, …, a_n, …;

б) если fⁿ – имя функции, а t₁, t₂, …, t_n – термы, то fⁿ(t₁, t₂, …, t_n) – тоже терм.

2) Формулы:

а) если Aⁿ – имя предиката, а t₁, t₂, …, t_n – термы, то Aⁿ(t₁, t₂, …, t_n) – формула; все вхождения переменных в формулу Aⁿ(t₁, t₂, …, t_n) являются свободными;

б) если A(x) – формула, содержащая свободное вхождение переменной x, то выражения с кванторами " xA(x), $xA(x) – формулы;

в) если A и B – формулы, то Ø A, AÉ B – формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

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

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

Подстановка терма y в формулу A(x) называется правильной, если и только если:

а) y является предметной константой;

б) у является предметной переменной, и все вхождения y, полученные в результате подстановки, оказываются свободными в полученной в результате подстановки формуле. Например, в формулу " y(P(x, y) É Q(x)) вместо x можно подставить либо константу a: " y(P(a, y) É Q(a)), либо переменную z: " y(P(z, y) É Q(z)), но нельзя подставить переменную y, так как после подстановки получим формулу: " y(P(y, y) É Q(y)), в которой переменная y оказывается связанной.

3. Аксиомы исчисления предикатов.

А1. A É (B É A).

А2. (A É (B É C)) É ((A É B) É (A É C)).

А3. (Ø B É Ø A) É ((Ø B É Ø A) É B).

А4. " xA(x) É A(y), где формула A(x) не содержит переменной y.

А5. A(x) É $yA(y), где формула A(x) не содержит переменной y.

4. Правил вывода в исчислении предикатов четыре:

П1 – modus ponens (m. p.) – правило заключения:

;

П2 – правило связывания квантором общности:

, где формула B не содержит переменной x;

П3– правило связывания квантором существования:

, где формула B не содержит переменной x;

П4 – правило переименования связанной переменной. Связанную переменную в формуле A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A. Например, для формулы " xF(x) É $xG(x) применяя правило переименования, получим формулу " yF(y) É $zG(z).

Для правил П2 и П3 условие, что формула B не содержит переменной x, является существенным. Это подтверждает следующий пример.

Пример 3.4.

Даны два предиката: B(x) = " x делится на 6"; A(x) = " x делится на 3".

Тогда B(x) É A(x) = " Если x делится на 6, то x делится на 3" = И для всех x.

Однако B(x) É " xA(x) = " Если x делится на 6, то все x делятся на 3" не всегда истинно. Таким образом, применение правила П2 неправомерно, если B зависит от x.

Если же к формуле B(x) É A(x) применить правило П3, то получим $xB(x) É A(x). После применения правила П2 получим $xB(x) É " xA(x) = " Если некоторые x делится на 6, то все x делятся на 3" = Л. Таким образом, применение правила П3 также неправомерно, если B зависит от x.

Для исчисления предикатов верны правила вывода 1 – 14 исчисления высказываний (раздел 3.2).

Дополнительные правила вывода для исчисления предикатов следующие:

1. Введение квантора общности: , где A(y) – результат правильной подстановки переменной y вместо x в A(x).

 

2. Удаление квантора общности: , где A(y) – результат правильной подстановки терма y вместо x в A(x).

3. Отрицание квантора общности: .

4. Введение квантора существования: , где A(y) – результат правильной подстановки терма y вместо x в A(x).

5. Удаление квантора существования: , где A(x) – результат правильной подстановки переменной x вместо y в A(y).

6. Отрицание квантора существования: .

Верна также теорема дедукции. Если Г – множество формул, A и B – формулы, и Г, A „ B. Тогда Г „ A É B.

Сформулируем без доказательства важные утверждения для исчисления предикатов

Теорема 3.1. Аксиомы исчисления предикатов – общезначимые формулы.

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

Пример 3.5.

Обосновать правильность рассуждения, построив вывод.

а) Всякое нечетное натуральное число является разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел

Пусть M – множество натуральных чисел. Введем предикаты:

A(x) = “x – нечетное число”.

B(x) – “x – разность квадратов двух чисел”.

Требуется построить вывод:

" x(A(x) É B(x)), A(5) „ B(5).

Построим вывод.

(1) " x(A(x) É B(x)) – гипотеза;

(2) A(5) – гипотеза;

(3) A(5) É B(5) – из (1) и удаления ";

(4) B (5) – из (2) и (3) по m. p.

б) Все словари полезны. Все полезные книги высоко ценятся. Следовательно, все словари высоко ценятся.

Сначала формализуем наше рассуждение, введя следующие предикаты:

A(x) = “x – словарь”.

B(x) = “x – полезен”.

C(x) = “x высоко ценится”.

Требуется построить следующий вывод:

" x(A(x) É B(x)), " x(B(x) É C(x)) „ " x(A(x) É C(x)).

Построим этот вывод.

(1) " x(A(x) É B(x)) – гипотеза;

(2) " x(B(x) É C(x)) - гипотеза;

(3) A(y) É B(y) – из (1) и удаления ";

(4) B(y) É C(y) – из (2) и удаления ";

(5) A(y) É C(y) – из (3) и (4) по правилу силлогизма;

(6) " x(A(x) É C(x)) – из (5) и введения ".

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

Формализуем наше рассуждение, введя следующие предикаты:

A(x) = “x – совершеннолетний”.

B(x) = “x находится в здравом уме”.

C(x) = “x допущен к голосованию”.

Введем константу d, обозначающую имя " Джон".

Требуется построить следующий вывод:

" x(A(x)& B(x) É C(x)), Ø C(d)) „ Ø A(d) V Ø B(d).

Построим этот вывод.

(1) " x(A(x)& B(x) É C(x)) - гипотеза;

(2) Ø C(d)) - гипотеза;

(3) A(d)& B(d) É C(d) - из (1) и удаления ";

(4) Ø C(d)) É Ø (A(d)& B(d)) – из (3) и правила контрапозиции;

(5) Ø C(d)) É Ø A(d) V Ø B(d) – из (4) и отрицания конъюнкции;

(7) Ø A(d) V Ø B(d) – из (2) и (5) по m. p.

(8)

ТЕМА 4. НЕЧЕТКАЯ ЛОГИКА

Нечеткие множества

 

В 1965 году американский математик Лотфи Заде (L. Zade) опубликовал статью “Нечеткие множества” (“Fuzzy sets”). Было дано новое определение понятия множества, предназначенное для описания сложных плохо определенных систем, в которых наряду с количественными данными присутствуют неоднозначные, субъективные, качественные данные

Понятие множества лежит в основе всех математических конструкций, и статья Заде породила новое научное направление. Произошло “раздвоение” математики, появились нечеткие функции, нечеткие отношения, нечеткие уравнения, нечеткая логика и т. д. Эти понятия широко используются в экспертных системах, системах искусственного интеллекта. Изложим основные понятия нечетких множеств.

Определение 4.1. Нечетким множеством на множестве X назовем пару (X, m_A), где m_A(x) – функция, каждое значение которой m_A(x) Î [0, 1] интерпретируется как степень принадлежности точки xÎ X множеству . Функция m_A – называется функцией принадлежности множества .

Для обычного четкого множества A можно положить

m_A(x) =

Таким образом, обычное множество является частным случаем нечеткого множества.

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

Пример 4.1.

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

Пусть X = {1, 2, 3, …, n, …} – множество натуральных чисел, а функция m_A(x) задана таблицей:

 

x	1 2 3 4 5 6 7 8 9 10 …
mA(x)	0 0, 1 0, 6 0, 8 1 1 0, 9 0, 7 0, 2 0 …

 

Аналогично можно ввести понятия " много", " мало", " около 100", " почти 20", и т.д.

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

Пример 4.2.

Пусть X = (0, ¥ ) – множество положительных чисел, а функция m_A(x) задана формулой:

m_A(x) =

График этой функции изображен на рис. 4.1.

Рис. 4.1

 

Если переменную x интерпретировать как возраст, то нечеткое множество соответствует понятию " старый". Аналогично можно ввести понятия " молодой", " средних лет" и т. д.

Пример 4.3.

Переменная " расстояние" принимает обычно числовые значения. Однако в предложениях естественного языка она может фигурировать как лингвистическая со значениями: " малое", " большое", " среднее", " около 5 км" и т. д. Каждое значение описывается нечетким множеством. Пусть речь идет о поездках на такси по городу. В качестве универсального множества X можно взять отрезок [0, 100] км и задать функцию принадлежности значений так, как показано на рис. 4.2.

Рис.4.2

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

Определение 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, то нечеткие формулы и называются нечетко неравносильными..

12345678Следующая ⇒

Поделиться: