Учебное пособие по математической логике для студентов заочного отделения




НазваниеУчебное пособие по математической логике для студентов заочного отделения
страница5/5
Дата публикации28.08.2013
Размер0.96 Mb.
ТипУчебное пособие
skachate.ru > Математика > Учебное пособие
1   2   3   4   5

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

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

^ Логическое следование логики предикатов.

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

.

Правило удаления кантора общности (правило универсальной конкретизации):

.

Правило введения квантора существования (правило экзистенциального обобщения):

.

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

^ Проблема разрешимости для общезначимости и выполнимости формул логики предикатов.

В логике предикатов, в отличие от алгебры высказываний, не существует алгоритма, позволяющего для каждой формулы определить, будет ли она выполнимой или общезначимой. Это было доказано в 1936 году американским математиком А. Чёрчем. Проблема разрешимости в логике предикатов допускает решение лишь для некоторых частных видов формул. Задача о выполнимости или общезначимости формул логики предикатов на конечном множестве сводится к задаче о выполнимости или тождественной истинности алгебры высказываний, которая разрешима.

^ Применение логики предикатов к логико-математической практике.

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

Определение предела последовательности “Число называется пределом последовательности , если для всякого положительного числа существует такое натуральное число , что для всякого натурального , большего , ” на языке логики предикатов записывается так:

.

Короче это можно записать так:

.

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

.

Теоремы математики допускают формулировки в виде условных предложений. Часто в теореме можно выделить три части: условие теоремы – предикат , заданный на множестве , заключение теоремы – предикат , заданный на множестве , разъяснительная часть, описывающая множества объектов, о которых идет речь в теореме. Строение теоремы может быть таким: “Если любой элемент из множества обладает свойством , то он обладает свойством ”. Теорема формулируется так: . Например, теорема о конечных приращениях (теорема Лагранжа) гласит: “Если непрерывна на и дифференцируема на , то найдется на такая точка , что .” Пусть предикат выражает свойство функции быть непрерывной на и дифференцируемой на , а . Тогда теорема Лагранжа может быть сформулирована так: .
^ 5. Формализованное исчисление предикатов
Задача формализованного исчисления предикатов та же, что и формализованного исчисления высказываний – дать аксиоматическую теорию совокупности всех общезначимых формул (тавтологий) логики предикатов, то есть изучить способы вывода (доказательства) всех таких формул, исходя из выбранной системы аксиом и с использованием выбранных правил вывода. Здесь приводится краткое описание этого исчисления.

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

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

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

1) если – предикатная буква, – термы, то – формула, при этом все вхождений переменных в эту формул называются свободными;

2) если – формулы, то формулами являются – тоже формулы;

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

4) никаких других формул нет.

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

Система аксиом исчисления предикатов состоит из двух групп: первая – это аксиомы исчисления высказываний ИВ, а вторая включает следующие аксиомы:

PA1 ;

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

Правила вывода. К правилу вывода MP из исчисления высказываний добавляются еще два правила вывода:

-правило, или правило обобщения ;

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

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

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

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

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

Формальная теория есть теория множества всех своих моделей, поэтому она семантически (то есть по смыслу) непротиворечива, если и только если , то есть существует хотя бы одна ее содержательная модель (интерпретация). Исчисление предикатов семантически непротиворечиво.

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

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

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

Ни одна из аксиом исчисления предикатов не выводима из других. Это означает, что система аксиом исчисления предикатов независима.
^ 6. Логика, опыт и интуиция
В заключение нужно признать, что, хотя логика необходима для познания реального мира, она все же недостаточна. Логика связывает факты, которые дает опыт, эксперимент. Но для построения теории необходим еще и набор аксиом. Аксиомы не могут быть получены только логикой – они не могут (по определению) быть доказаны.

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

Возникает естественный вопрос: как выбрать эти новые аксиомы, если они невыводимы?

Великий голландский философ Б.Спиноза учил, что существуют три пути (способа) познания: а) интуитивный, б) логический и в) чувственный. При этом первый – высший, а третий – низший. Но интуиция по Спинозе – это не мгновенное озарение (таково обыденное понимание этого слова), а целостное усмотрение истины, вытекающее из всех знаний познающего субъекта, несводимое к логике. Нельзя логически доказать, что А.С. Пушкин – великий поэт, тем не менее мы это хорошо знаем.

А. Эйнштейн (который хорошо знал и понимал учение Б. Спинозы) говорил, что аксиомы – свободное творение человеческого сознания и вводятся интуитивно, без опоры на логику. Из аксиом логически выводятся теоремы, из них – другие теоремы, и если теория имеет отношение к реальному миру, из этих теорем делаются выводы о свойствах реального мира. Если оказывается, что на самом деле эти свойства – другие, то теория опровергается. Но если все выводы теории согласуются с опытом, это еще не означает, вообще говоря, истинности теории. Мы знаем, что импликация при истинном истинна независимо от . Известно, что Карно свою правильную формулу для предельного значения коэффициента полезного действия теплового действия получил из совершенно неправильных теоретических представлений. Система Коперника вначале хуже соответствовала наблюдательным данным, чем система Птоломея. Вывод о приемлемости новой теории есть тоже интуитивное умозаключение, и, следовательно, может быть в дальнейшем опровергнут.
^ 7. Варианты контрольных работ
Каждый вариант содержит 9 заданий.

  1. Доказать равенство множеств.

  2. Построить таблицу истинности для логической функции .

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

  4. Упростить выражение для функции .

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

  6. Найти полином Жегалкина для функции с заданным номером.

  7. Доказать секвенцию табличным методом.

  8. Доказать тавтологию методом резолюций.

  9. Проанализировать вывод секвенции.


Вариант 1.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7)

2) 5) 8)

3) 6) 9)
Вариант 2.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7)

2) 5)

3) 6)
Вариант 3.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7)

2) 5) 8)

3) 6) 9)
Вариант 4.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7) .

2) 5)

3) 6)
Вариант 5.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7)

2) 5)

3) 6)
Вариант 6.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 4) 7)

2) 5) 8)

3) 6)
Вариант 7.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) – теорема 5) 9)

2) 6) 10)

3) 7) 11) .

4) 4) 8)
Вариант 8.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 5)

2) 6)

3) 7)

4) 8)
Вариант 9.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 5)

2) 6)

3) 7)

4) 8)
Вариант 10.

1.

2.

3. .

4. .

5. . 6) .

7. .

8. .

9. 1) 5)

2) 6)

3) 7)

4) 8)

Рекомендуемая литература


  1. В. А. Лексаченко. Логика, множества, вероятность. ГУАП. Учебное пособие.

  2. В. И. Игошин. Математическая логика и теория алгоритмов. М. ACADEMIA 2004.

3. В. И. Игошин. Задачник-практикум по математической логике. М. 1986.

  1. С. Д. Шапорев. Математическая логика. Курс лекций и практических занятий. 2007.


Дополнительная литература


  1. Р. Пенроуз. Новый ум короля. О компьютерах, мышлении и законах физики. В серии “Синергетика: от прошлого к будущему”. УРСС. М. 2005.

  2. Р. М. Смаллиан. Как же называется эта книга? М. 2007.

3. А. А. Ивин. Искусство правильно мыслить. М. 1990.


1   2   3   4   5

Похожие:

Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по ботанике для студентов 3 курса заочного отделения...
Учебное пособие предназначено для самостоятельной работы студентов 3 курса заочного отделения фармацевтического факультета. Пособие...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы...
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по фармацевтической химии для студентов 4 курса заочного...
Авторы учебного пособия для студентов 4 курса заочного отделения фармацевтического факультета «Общие и частные методы анализа лекарственных...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие содержит характеристику основных разделов фармацевтической...
В пособии приведена рабочая программа по фармацевтической химии для студентов заочного отделения, даны рекомендации по её освоению...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы студентов
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconРекомендации о разработке методических указаний и контрольных заданий...
Разработчик: методист заочного учебного отделения высшего профессионального образования С. С. Кудрявцева
Учебное пособие по математической логике для студентов заочного отделения iconСамостоятельная работа, часов
Смолова Л. М. Химия. Рабочая программа, методические указания, элементы теории, вопросы для самопроверки и контрольные задания для...
Учебное пособие по математической логике для студентов заочного отделения iconКонтрольная работа №2 по английскому языку для студентов заочного...
Данное пособие можно взять в библиотеке Политехнического колледжа или получить в электронном виде. Также необходимо изучить материалы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница