Методичка

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

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

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

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

·Если А – формула, то □А, ◊А, ∆А – формулы. Дадим словесную трактовку модальным операторам:

·□А – необходимо; □А истинно тогда и только тогда, когда А необходимо истинно, или абсолютно истинно, или предполагается , что А истинно, или А истинно во всех возможных мирах;

·◊А – возможно; ◊А истинно, если А может оказаться истинным, или А условно истинно, или разрешается, чтобы было истинным, или противоположное к А неизвестно, или если А истинно в некотором возможном мире табл.1.

Таблица 1

Трактовка оператора □А	Трактовка оператора ◊А
Необходимо, что А	Возможно, что А
Всегда будет истинно, что А	Иногда будет истинно, что А
Требуется, чтобы А	Разрешается , чтобы А
Предполагается, что А	Противоположное к А не
	предполагается
Любое выполнение	Существует такое
программы дает результат А	выполнение программы, которое
	дает результат А

91

Многозначная логика

Классическая бинарная логика с двумя значениями – истина и ложь – является самой элементарной. В этой логике истина и ложь образуют два четких множества высказываний. При этом в классической логике любое высказывание является элементом хотя бы одного из этих множеств (закон исключенного третьего). При этом любое высказывание не может быть элементом сразу двух этих множеств (закон противоречия).Чтобы внести в классическую логику элементы модальности «возможно» следует ввести дополнительный класс высказываний. Впервые многозначность предложил польский математик Ян Лукасевич (1878-1956). Введем следующие обозначения:

1.Невозможность (ложное высказывание) обозначим 0;

2.Возможность (нейтральное высказывание ) обозначим 1или ◊;

3.Необходимость (истинное высказывание) обозначим 2 или □. Рассмотрим логическое отрицание в системе Лукасевича табл.2.

Таблица 2

F	⌐ F
0	2
1	1
2	0

Заметим, что в логике Лукасевича закон исключенного третьего не выполняется. Действительно 1 1 2.

Конъюнкция и дизъюнкция вычисляются по следующим формулам:

А В=max (А,В) ; А В=min (А,В).

Логика Лукасевича может быть интерпретирована в современных информационных системах следующим образом:

истинно А – подтверждено в базе данных;

ложно А –А явно отрицается в базе данных;

не определено – ничего не сказано об А в базе данных.

Пороговая логика

В 1943 году Уоррен Мак-Каллок и Уолтер Питтс [27] предложили формальную модель нейрона (нервной клетки мозга) как переключающей функции {0,1}ⁿ {0,1} в виде логической схемы, имеющей конечное число двоичных входов и один двоичный выход. Каждый вход X1 учитывается в нейроне с некоторым приписанным ему весом W1. Нейрон возбуждается, если суммарное взвешенное возбуждение его выходов не меньше некоторого порога срабатывания Ө. иными словами выход нейрона равен 1, если ∑ W1 *X1 ≥ Ө.

С изменением порога и весов входов логические функции, реализуемые этим нейроном, изменяются. Рассмотрим формальный нейрон с двумя входами {x1, x2}, изображенный на рис. 7.1. суммарное возбуждение ∑ для этой схемы рассчитывается так: ∑=w1*x1+w2*x2. Пусть w1=w2=1; тогда

92

∑=x1+x2. Если Ө=1, эта схема реализует дизъюнкцию x1&x2; при Ө=2 она реализует конъюнкцию x1&x2.

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

Для набора < 0,0 >,∑= w1*x1+w2*x2=0 < Ө (поскольку 0&0=0); Для набора < 0,1 >, ∑=w1*x1+w2*x2=w2 < Ө (поскольку 0&1=0); Для набора < 1,0 >, ∑=w1*x1+w2*x2=w1 < Ө (поскольку 1&0=0);

Для набора < 0,0 >, ∑=w1*x1+w2*x2=w1+w2 ≥ Ө (поскольку 1&1=1).

Х1
Ө	w1
X2	w	y

Рис.7.1 Пример формального нейрона.

Очевидно, что этой системе неравенств удовлетворяет решение Ө=2,w1=w2=1.

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

0 < Ө (поскольку 0 + 0 =0);

w2 ≥ Ө (поскольку 0 + 1 =1);

w1 ≥ Ө (поскольку 1+ 0 =1); w1+w2 < Ө (поскольку 1+ 1 =0).

Из второго и третьего неравенства имеем w1+w2 ≥ Ө + Ө и, учитывая последнее неравенство, Ө >w1+w2 ≥ Ө + Ө. это однако, противоречит первому неравенству Ө>0.

7.3 Темпоральные и алгоритмические логики.

Временные или темпоральные логики - это модальные логики, которые получаются добавлением к логике высказываний новых символов [2], отражающих свойства времени. Временная логика Прайора – это логика будущего. Она содержит новый символ F, который называется символом будущего , и новый символ G. При этом для любой формулы формула F интерпретируется как « будет », а формула G читается, как « всегда будет» и связана с формулой F следующей аксиомой

93

├G ↔ F

Кроме того, к исчислению высказываний добавляются схемы аксиом

F( ) F F FF ├ F

Леммон предложил минимальную временную логику, основанную на модальностях Р - «было» и F –«будет». Предложенное им исчисление добавляет к исчислению высказываний аксиомы

F ( ) ├ (F F )P ( ) ├ (P P )

Во временной логике фон Вригта к исчислению высказываний добавляется бинарная связка Т, позволяющая по формулам и строить формулу ( Т ), которая читается, как « сейчас происходит событие , а затем, т.е. в следующий момент времени, происходит событие ». Время в этой темпоральной логике дискретно и линейно упорядочено. Алгоритмические логики создаются с целью описания семантики языков программирования и включают формулы вида { } S { }, которые интерпретируются как «если до выполнения оператора S было истинно , то после выполнения оператора будет истинно .

Эти логики были изобретены Р.У. Флойдом (1967 г.), Ч. Хоаром (1969 г.) и представителями польской логической школы А. Сальвиницким и др.

На базе работы Хоара проводились исследования в области аксиоматических определений языков программирования. Появилось много работ по аксиоматизации различных конструкций: от оператора присваивания до различных форм циклов. В 1973 г. Были сформулированы правила доказательства правильности для большинства конструкций языка Паскаль. В 1975 г. была построена автоматическая система верификации для языка Паскаль, основанная на аксиомах и правилах вывода.

7.4Вопросы для самопроверки

1.Дать классификацию неклассических логик. 2.Что называется нечетким множеством. 3.Что называется нечетким высказыванием.

4.Определить степень истинности отрицания нечеткого высказывания.

5.Определить степень истинности конъюнкции нечетких высказываний.

6.Определить степень истинности дизъюнкции нечетких высказываний.

7.Дать формулу для определения степени истинности импликации

нечетких высказываний.

8.Дать определение модальной логики.

9.Дать определение темпоральной и алгоритмической логики.

10.Дать определение многозначной логики.

11.Определить степень истинности дизъюнкции высказываний в логике Лукасевича.

12.Определить степень истинности конъюнкции высказываний в логике Лукасевича.

94

Литература

1.Аляев Ю.А. Дискретная математика и математическая логика: учебник. -М.: Финансы и статистика, 2006. -368с.

2.Ашинянц Р.А. Логические методы в искусственном интеллекте.

М.: МГАПИ, 1996.- 201 с.

3.Асанов М.О., Баранский В.А.,Расин В.В.

Дискретная математика: графы, матроиды, алгоритмы.

М.:Лань, 2010.-368 с.

4.Белоусов А.И. Дискретная математика: Учебник для вузов. М.: Изд-во МГТУ им. И.Э. Баумана, 2001. – 744 с.

5.Бабичева И.В. Дискретная математика. Контролирующие материалы к тестированию. М.: Лань, 2013. – 160 с.

6.Глухов М.М., Козлитин О.А., Шапошников В.А. Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов. М.: Лань,2008, 112 с.

7.Глухов М.М., Шишков А.П. Математическая логика. Дискретные функции. Теория алгоритмов. СПб.: Лань, 2012.-418 с.

8.Гринченков Д.В.Математическая логика и теория алгоритмов для программистов. М.: Кнорус, 2010. – 365 с.

9.Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. –М .:Наука. Физматлит, 2000.-544 с.

10.Игошин В.И. Математическая логика и теория алгоритмов. Учебное пособие для вузов. -М.: Издательский центр

«Академия», 2004.-448 с.

11.Иванов В.А. Математические основы теории оптимального и логического управления. М.: МГТУ им. Баумана, 2011. – 599 с.

12.Ивлев Ю.В. Логика: Учебник для вузов. -М.: Логос, 2001.-272 с. 13.Карпов В.Г., Мощенский В.А. Дискретная математика.- Минск:

Высшая школа, 1977.-256 с.

14.Колмогоров А.Н., Драгалин А.Т. Математическая логика.

М.:КомКнига, 2006. – 240 с.

15.Коршунов Ю.М. Математические основы кибернетики. - М.: Энергоатомиздат, 1987. – 496 с.

16. Крупский В.Н. Математическая логика и теория алгоритмов. М.:

Лань, 2013. – 416 с.

17.Кузнецов О.П. Дискретная математика для инженера.

М.: Лань, 2010 . -400 с.

18.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.- М.: ФИЗМАТЛИТ,

2001.- 256 с.

95

19.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. СПб.:Издательство Лань, 2009. 288с.

20. Мальцев И.А. Дискретная математика. М.: Лань,2011. – 304 с. 21.Москинова Г.И. Дискретная математика для менеджера в

примерах и упражнениях. М.: Логос, 2002. – 240 с. 22.Никольская И.Л. Математическая логика. – М.: Высшая школа,

1981. – 128 с.

23.Новиков Ф.А. Дискретная математика для программистов. –

СПб.: Питер,2009. – 384 с.: ил. ISBN 5-272-00183-4.

24. Певзнер Л.Д. Практикум по математическим основам теории систем. М.: Лань, 2013. – 400 с.

25.Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – Издание 2-е, исправленное. – СПб: Невский диалект, 2000г. – 240 с.

26.Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. Учебник, М.: Инфра-М, 2004.-224 с.

27.Теория автоматов / Карпов Ю.Г. – СПб.: Питер, 2003. – 208 с.

28.Шапорев С.Д. Математическая логика. Курс лекций и практических занятий.- СПб.: БХВ –Петербург, 2005.-416 с.

29.Шевелев Ю.П. Дискретная математика. М.: Лань,2011. – 608 с.

30.Шевелев Ю.П., Писаренко Л.А., Шевелев М.Ю. Сборник задач по дискретной математике (для практических занятий в группах).

М.: Лпнь, 2014. – 528 с.

31.Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств СПб.: Лань, 2011.-432 с.

32.Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. М.:Физматлит, 2004. – 128 с.

33.Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера 2005.- 400 с.

34.Яблонский С.В. Введение в дискретную математику.- М.: Высшая школа, 2001.-384 с.

35.http://distance.ru/4stud/umk/logic/logic12.html

96