| Математическая логика и теория алгоритмов
Лектор: А. Л. Семенов
Лекция 1
Введение 1
Задача математической логики и теории алгоритмов 1
Математические результаты математической логики и теории алгоритмов 2
Современная цивилизация и роль МЛиТА 2
Построение математики. Теория множеств 5
Программа математического исследования математической деятельности - Гильберт 9
Общая идея 9
Итоги Программы Гильберта 12
Язык и аксиомы теории множеств. I. Примеры 12
Логические символы и их смысл (семантика) 12
Примеры аксиом существования множеств 13
Введение
Задача математической логики и теории алгоритмов
Задача, решаемая математической логикой и теорией алгоритмов – построить систему математических определений и теорем, позволяющих математически описывать и исследовать следующие виды деятельности человека:
Доказательство теорем и определение математических понятий
Описание отношений между математическими объектами
Получение следствий из экспериментально установленных утверждений, из гипотез и т. п.
Проектирование устройств (механических, электронных и т. д.) с заданными свойствами и функциями.
Создание и выполнение формальных предписаний (описание и применение алгоритмов и программ)
Установление соответствия между описанием требуемого результата и алгоритмом, предназначенным для достижения этого результата (доказательство правильности)
Математическая логика и теория алгоритмов дают (математические, точные) критерии правильности для перечисленных видов деятельности.
Математические результаты математической логики и теории алгоритмов
Занимаясь указанным исследованием, мы получим и результаты, относящиеся к:
Множествам и отношениям, которые можно описать на том или ином языке
Множествам доказуемых формул
Множествам истинных формул (имеется фундаментальная разница с п. 2)
Множествам математических структур, в которых истинны формулы из заданного множества
Классам функций, которые вычисляются алгоритмами
Существованию алгоритма, выясняющего истинность или доказуемость формул
Сложности вычислений
Сложности объектов
и т. д.
Современная цивилизация и роль МЛиТА
Существенный прогресс в развитии человечества связан с созданием машин для обработки материальных объектов, получения и передачи энергии (используемой этими машинами), средств транспорта, освещения и т. д.
В течение столетий у людей возникала идея о создании машин для работы не с материей и энергией, а с информационными объектами. Более того, такие машины создавались и даже успешно работали, например, машина, позволяющая выполнять арифметические действия – арифмометр (Б. Паскаль).
В первой половине XX века было дано общее описание того, какие возможны способы формальной переработки информации человеком. К середине XX века были открыты физические принципы, сделавшие реальным создание устройств, которые могут хранить очень много информации и очень быстро ее обрабатывать. Были созданы универсальные устройства – компьютеры, которые могут делать все то, что формализовано может делать человек, но гораздо быстрее, чем человек.
При совсем общем взгляде можно сказать, что математическая логика дает фундамент для теоретической математики, а теория алгоритмов – для вычислительной практики (использования компьютеров). Более детальное рассмотрение показывает, однако, что многие достижения математической логики нашли приложения в разработке и применении информационных технологий, а алгоритмические рассмотрения существенны и в различных разделах чистой математики.
Вехи истории
Важными моментами в становлении современных представлений о том, что представляют собой математические доказательства и вычисления, стали достижения немецких математиков конца XIX - начала XX вв.
Особую важность имело выступление Давида Гильберта (23.01.1862 - 14.01.1943) на II Международном конгрессе математиков (Париж, 1900). Там он сформулировал 23 т. н. Проблемы Гильберта – важнейших для математики того времени и для развития математики в XX в. Некоторые из проблем Гильберта представляли собой вопрос о выяснении истинности конкретного математического утверждения, другие можно назвать скорее предложением осуществить какую-либо программу исследований.
Проблемы I, II, X из списка Гильберта относятся к предмету математической логики и теории алгоритмов.
Из семи математических Проблем тысячелетия первая также относится к нашему предмету (ее не было среди Проблем Гильберта).
В курсе будут обсуждаться упомянутые выше проблемы из области математической логики и теории алгоритмов и современный взгляд на них.
Организационные замечания
Авторы курса считают, что лучший способ изучить математику и стать математиком – это делать математику самому. Под математиками мы здесь понимаем всех, для кого существенной частью их профессиональной деятельности (а для многих – и всей жизни) является работа с математическими объектами с использованием математических способов деятельности. Существенная часть деятельности в сфере информационных технологий, например, устроена именно так. Под «деланием математики» мы имеем в виду решение задач, при этом, в первую очередь , не таких, какие больше всего решают в школе, или в курсе математического анализа на первом курсе университета. Мы имеем в виду задачи, где нужно придумать что-то новое. Конечно, при освоении новой области математики многие из этих задач должны быть простыми и давно решенными, но они не отличаются принципиально от задач, которые приходится решать профессиональному математику и программисту.
Задачи того сорта, о котором мы сейчас говорим, будут формулироваться и на лекциях, и на упражнениях по курсу. Не все формулируемые задачи будут совсем простыми. Более того: некоторые из них решены в математике совсем недавно, будут и такие, которые еще не решены, и такие, которые вовсе не имеют решения (но порешать которые – полезно).
Мы предлагаем вам заниматься решением задач во время всего изучения курса и обсуждать их со своим преподавателем (и, конечно, между собой). Это:
Поможет вам лучше понимать содержание лекций и всей математической области, к которой относится курс
Лучше подготовиться к экзамену и частично его «сдать» (решение задач по ходу курса вам «зачтется» на экзамене, подробнее вам расскажут ваши преподаватели)
Попробовать себя в перспективной области математики и, возможно, выбрать ее для своей специализации в Университете, что может оказаться полезным для Вашей работы после университета.
Еще одним местом, где решаются задачи и обсуждаются их решения, является Просеминар по математической логике и информатике для студентов младших курсов. Там, наряду с простыми задачами, позволяющими понять суть дела, вам сразу будут предлагаться и сложные, и еще не решенные.
Материалы очередной лекции будут выкладываться в интернете на сайте http://lpcs.math.msu.su/vml2013/
Кроме них, с содержанием курса можно познакомиться по книгам:
Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, изд. МЦНМО (mccme.ru)
И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов,
которые также есть в интернете.
Наконец, последнее. Одним из прикладных результатов математической логики и теории алгоритмов является автоматизация различных компонентов математической деятельности. В частности , автоматизации поддается проверка математических доказательств некоторых видов. Область такой автоматизации, естественно, постоянно расширяется за счет развития самих алгоритмов автоматизации, большего понимания математиками, как эти алгоритмы применять, накопления опыта и роста вычислительных возможностей. Сегодня наиболее популярной и эффективной вычислительной средой для автоматизации проверки доказательств является Coq. Наша кафедра ведет практикум по Coq, где можно научиться эту среду применять, представить себе ее возможности и ограничения.
Построение математики. Теория множеств
Современное построение математики, в частности то, как ее изучают в университетах, основано на теории множеств. Сейчас мы напомним некоторые базовые понятия этой теории.
Для задания множеств часто используются фигурные скобки. Внутри них можно поместить все элементы задаваемого множества: {2, 14, 5.4} или особым образом его описать: {x|x – действительное число и sin(x)>0}.
Мы используем следующие обозначения для операций над множествами: принадлежность элемента множеству ∊,
включение множеств ⊂ , объединение ∪, пересечение ∩, разность \.
Пусть у нас имеются два объекта x
,y
. Упорядоченной парой x; y
> называется объект, по которому однозначно восстанавливаются x
, y
, иначе говоря:
x;y
> = x′;y
′> → (
x
= x
′ y
= y
′).
Произведением x
X y
двух множеств x
и
y
называется множество всех упорядоченных пар
u; v
>, где u
∊
x
и
v
∊
y
.
Аналогично, определяются упорядоченные n
–ки объектов и n
-ая степень x
n
множества x
. Можно договориться, что x
1 – это x
.
Отношением между множествами x
, y
называется любое подмножество их произведения x
X
y
.
n
-местным отношением на множестве x
называется любое подмножество n
–ой степени этого множества.
Отношение f
между x
и
y
называется функцией из x
в y
, если из совпадения первых компонентов любых двух элементов отношения f
вытекает совпадение вторых.
Областью определения функции называется множество первых ее компонентов.
Если область определения функции из x
в y
совпадает с x
, то говорят, что функция отображает x
в y
и пишут f
:
x
→ y
. Множество всех функций, отображающих x
в y
,
обозначается
y
x
.
Функция f
:
x
→ y
называется биекцией между
x
и y
, или биекцией из
x
в y
, или изоморфизмом x
и y
, если из совпадения вторых компонентов элементов f
вытекает совпадение первых, и, кроме того, вторые элементы f
образуют все множество y
. Изоморфные множества называются также равномощными.
Множество называется счетным, если оно равномощно натуральному ряду.
Задача. Доказать, что всякое подмножество натурального ряда равномощно или его начальному отрезку (что то же самое – некоторому его элементу) или всему натуральному ряду.
Сформулированное в последней задаче элементарное наблюдение – что часть может быть изоморфна целому, вероятно, кажется студентам второго курса тривиальным. Но оно было одним из первых открытий теории множеств.
Конечные множества можно сравнивать по величине. Если одно изоморфно подмножеству другого, то в нем меньше элементов. В случае бесконечных множеств это не так. Эта ситуация была описана Галилео Галилеем в следующем диалоге, который мы приводим с сокращением:
Беседы
и
математические
доказательства,
касающиеся двух новых
отраслей науки,
относящихся
к
механике
и
местному движению,
синьора
Галилео Галилея Линчео, философа и первого математика светлейшего великого герцога тосканского
Сальвиати. …количество всех чисел вместе - квадратов и не квадратов - больше, нежели одних только квадратов; не так ли?
Симпличио. Ничего не могу возразить против этого.
Сальвиати. Квадратов столько же, сколько существует корней, так как каждый квадрат имеет свой корень и каждый корень свой квадрат; ни один квадрат не может иметь более одного корня и ни один корень более одного квадрата.
Сагредо. Что же нужно сделать, чтобы найти выход из такого положения ?
Сальвиати. Я не вижу возможности никакого другого решения, как признать, что свойства равенства, а также большей и меньшей величины, не имеют места там, где дело идет о бесконечности, и применимы только к конечным количествам. Поэтому, когда синьор Симпличио предлагает мне неравные линии и спрашивает меня, как может быть, чтобы в большей из них не содержалось большего количества точек, чем в меньшей, то я отвечаю ему, что их там не больше, не меньше и не одинаковое количество, но бесконечное множество в каждой.
Однако и среди бесконечных множеств некоторый порядок все-таки есть, как показывает следующая теорема, также объявленная без доказательства Кантором и вскоре доказанная другими немецкими математиками.
Теорема Кантора – Бернштейна. Пусть существует биекция между множеством A
и подмножеством множества B
, а также биекция между множеством B
и подмножеством множества A
. Тогда множества A
и B
– равномощны.
Задача. Доказать Теорему Кантора – Бернштейна.
Задача. Можно ли сравнить любые множества по мощности, то есть, верно ли, что для любых A
и B
, или A
равномощно подмножеству B
, или B
равномощно подмножеству
A
?
Среди функций мы выделяем свойства
– функции, принимающие только значения 0 и 1. Всякое свойство задает отношение – множество элементов, на которых ее значение – 1. Любая функция f
:
x
→ B называется характеристической
(на x
). Заметим, что в наших обозначениях и соглашениях B={0,1}=2. Таким образом, множество всех характеристических функций на x
получает обозначение B x
или 2 x
.
Задача. Построить изоморфизм между множеством характеристических функций на x
и множеством подмножеств множества x
.
Задача. Доказать, что множество подмножеств любого множества ему не изоморфно.
Идея решения [Диагональ Кантора]. Пусть изоморфизм G
:
x
→ 2 x
существует. Рассмотрим для каждого элемента y
из нашего множества x
соответствующее ему подмножество G
(y
). Можем ли мы из элементов x
собрать подмножество C
, которое отличалось бы от множества G
(y
) «на элементе y
»
? Или, что то же самое, как построить одну характеристическую функцию f
C
, которая отличалась бы от характеристической функции множества G
(y
) «в точке y
»
при всяком y
?
Если x
- множество натуральных чисел, то доказательство приобретает ясную графическую форму. Будем называть число y
, которое переходит в характеристическую функцию f
, номером функции f
.
Аргумент
№ функции
|
0
|
1
|
2
|
3
|
4
|
…
|
0
|
1
|
0
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0
|
1
|
0
|
|
2
|
1
|
0
|
0
|
1
|
1
|
|
3
|
0
|
0
|
0
|
1
|
0
|
|
4
|
0
|
1
|
0
|
1
|
0
|
|
………
В этой таблице в строке с номером n
выписана характеристическая функция с номером n
. В таблице нет функции, получающейся из ее диагонали сменой 1 на 0 и 0 на 1 (операцией отрицания).
Задача
. Доказать, что множество действительных чисел равномощно множеству подмножеств натурального ряда.
Программа математического исследования математической деятельности - Гильберт
Общая идея
Давиду Гильберту принадлежит представление о математике, как области математически описываемой деятельности, осознание важности исследований математической деятельности средствами самой математики, представление программы таких исследований – Программы Гильберта.
Программы Гильберта исследования математики можно представить следующим образом:
Математика может быть представлена как система
аксиом – утверждений, которые мы принимаем за истинные и
правила доказательства – получения новых утверждений.
Практика математической деятельности должна убеждать нас в том, что выбранная система позволяет строить все нужные доказательства. В идеале может так случиться , что всякое математическое утверждение можно доказать или опровергнуть с помощью этой системы. (Это свойство называется полнотой
.)
Некоторые математические доказательства являются «особенно надежными и убедительными». К ним относятся, например, арифметические вычисления. Используя только их, можно убедиться в том, что выбранная для математики система не позволяет получить противоречий. (Это свойство называется непротиворечивостью
.) Более того, могло бы оказаться, что и полноту математики можно также доказать с помощью простых, понятных и убедительных рассуждений.
Полезность свойства полноты ясна. Как правило, пытаясь доказать какое-то математическое утверждение, мы параллельно ищем и его опровержение. Хотелось бы быть уверенными, что такая деятельность в конце концов приведет к результату и дело тут «только» в наших способностях и времени. Гильберт считал: «Это убеждение в разрешимости каждой математической проблемы является для нас большим подспорьем в работе; мы слышим внутри себя постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления; ибо в математике не существует Ignorabimus!»
Заметим, что свойство непротиворечивости куда более существенно. Априори можно было бы представить себе научную теорию, в которой противоречие находится где-то на периферии и относится к каким-то несущественным вопросам. Однако, устройство всех основных систем математического доказательства таково, что доказуемость одного противоречия (например, того, что произведение каких-то двух очень больших чисел равно какому-то третьему и еще другому – четвертому) немедленно приводит к доказуемости любого математического утверждения. Противоречие нельзя «локализовать».
Первые шаги в достижении целей Программы Гильберта были сделаны еще до ее формулирования. Более того, Программа логически вытекала из них. Вот эти шаги.
Доказательства. Логика.
В конце XIX века стало ясно, как нужно формализовать систему рассуждений. Эта формализация получила свое завершение в работах Готлоба Фреге (8.11.1848 - 26.07.1925).
Теория множеств.
Еще одним достижением математики конца XIX века стало понимание того, что вся математика может быть единообразно представлена в терминах множеств (так, как это делается в современных математических курсах и мы напоминали выше). Это было сделано в работах Георга Кантора (3.03.1845 - 6.01.1918).
Таким образом, оставалось только выбрать подходящую систему аксиом и дальше идти по пути доказательства непротиворечивости и полноты. Надежда на получение таких доказательств простыми и надежными средствами была связана со следующим. Использование аксиом и правил доказательства выглядит довольно простым процессом работы с формулами. Сами формулы – это несложные объекты, цепочки символов. Математика представляется игрой, вроде, например, шахмат. Предположим, что нам нужно доказать, что какая-то позиция в шахматах невозможна. В принципе – это, конечно, можно сделать, перебрав всевозможные шахматные партии. Но можно представить себе и более простые рассуждения, основанные, например, на том, что фигур на поле не добавляется, что слоны бывают белопольные, а бывают чернопольные, и т. д. Такие рассуждения, скорее всего, не будут использовать действительные числа, интегралы и еще более сложные математические объекты.
Система аксиом для теории множеств
была, в основном, построена в течение первых десятилетий XX века, первая формулировка, близкая к современной, принадлежала Эрнсту Цермело (27.7.1871 ‒ 21.5.1953) и была им опубликована в 1908 году.
Итоги Программы Гильберта
Что же произошло с Программой Гильберта в дальнейшем? Мы сейчас коротко это сформулируем, а в дальнейшем курсе объясним подробнее.
С одной стороны, Программа была успешно реализована:
Аксиоматическая теория множеств является основанием современной математики.
В частности, в тридцатые годы сформировалась группа математиков под коллективным псевдонимом Н. Бурбаки. Максимум ее творческой активности пришелся на 1950 – 60-е гг. Эта группа последовательно и систематически представила существенную часть современной математики, как построенную на базе теории множеств.
В то же время Программа фундаментально провалилась:
Математика – не полна и не может быть полной.
Непротиворечивость математики невозможно установить не только какими-то надежными убедительными средствами.
Это установил Курт Гедель (28.04.1906 – 14.01.1978) в 1930-е годы.
Язык и аксиомы теории множеств.
I
. Примеры
Формулирование системы доказательств в математике (теории множеств) мы начинаем с описания логического языка.
Логические символы и их смысл (семантика)
Логические значения: символы И (истина), Л (ложь), или символы 1, 0.
Множество из двух символов 0 и 1 будем обозначать B.
Логические операции:
(не, отрицание), (и, конъюнкция), (или, дизъюнкция), → (следует, импликация), ≡ (эквивалентность), применяются к символам 1 (И) и 0 (Л) и результат их применения описан следующей таблицей:
A
|
B
|
A
|
AB
|
AB
|
A
→ B
|
A
≡ B
|
|
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
Кванторы
, с которыми вы тоже, конечно, знакомы - x
(существует x
),
y
(для любого y
)
Примеры аксиом существования множеств
Ряд аксиом Теории множеств представляет собой утверждения о существовании множеств, в том числе – образованных из других множеств.
Чтобы говорить о множествах, в частности, чтобы сформулировать относящиеся к ним аксиомы, надо добавить к логическим символам символы, относящиеся к теории множеств. Как записать, что x
– пустое множество, то есть множество, у которого нет элементов? Например, так:
y
(
y
∊
x
) (для всякого
y
неверно, что y
принадлежит x
)
Нам понадобился символ принадлежности ∊. Внесем его в алфавит нашего языка.
Чтобы нам было о чем разговаривать, хорошо было бы быть уверенным в существовании хотя бы одного множества. Давайте начнем с пустого (Ø):
x
y
(
y
∊
x
) [Аксиома пустого множества.]
Мы хотим определить какие-то конкретные множества, свойства множеств и т. д. Хотим ввести для них обозначения.
Будем считать нулем пустое множество.
Как получить следующее число из числа n
? Добавим ко всем элементам n
еще само n
. То есть, будем считать элементами следующего за n
числа все элементы из n
и еще n
. Все полученные элементы образуют множество N
:
1 – это {0}
2 – это {0,1}= {0,{0}}
Задача
. Сколько элементов в числе (множестве) 5? А в множестве n
?
Существование таким образом построенного натурального ряда гарантируется следующей аксиомой. Для удобства понимания мы разбили ее на части и комментируем (в квадратных скобках) эти части:
s
(u
(u
∊
s
v
(v
∊
u
))
[в качестве
s
можно взять натуральный ряд
N
; в нем найдется
u
- ноль]
u
(u
∊
s
→ [
для
всякого
u
из
s
]
v
(v
∊
s
[найдется
v
из
s
,
]
w
(w
∊
v
≡ (w
∊
u
w
=
u
)))))
[следующее за
u
] [
Аксиома бесконечности]
Однако этой аксиоме может удовлетворять не только натуральный ряд, но и другие множества
Задача
. Какие, например?
Задача
. Как описать в точности построенный нами натуральный ряд?
В математических построениях используются операции над множествами. Идя по уже начатому пути, мы должны добавлять аксиомы, гарантирующие существование результатов этих операций. Вот еще один пример:
usv
(w
(w
∊
v
→w
∊
u
) ≡
v
∊
s
) [Аксиома степени]
Задача
. Проверить, что последняя формула содержательно означает существование множества всех подмножеств любого заданного множества.
Конечно, нам понадобится, например и множество, являющееся пересечением двух данных, и т. д.
Выше мы начали постепенно строить множества. Ясно, как продолжить этот путь, например, построить множество целых чисел, затем - рациональных, как множество пар целых с некоторым отношением эквивалентности на нем, затем – множество действительных чисел и т. д. |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.
Подобные документы
Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.
курс лекций , добавлен 08.08.2011
Основные формы мышления: понятия, суждения, умозаключения. Сочинение Джорджа Буля, в котором подробно исследовалась логическая алгебра. Значение истинности (т.е. истинность или ложность) высказывания. Логические операции инверсии (отрицания) и конъюнкции.
презентация , добавлен 14.12.2016
Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.
лекция , добавлен 01.12.2009
История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.
презентация , добавлен 22.02.2014
Квадратные матрицы и определители. Координатное линейное пространство. Исследование системы линейных уравнений. Алгебра матриц: их сложение и умножение. Геометрическое изображение комплексных чисел и их тригонометрическая форма. Теорема Лапласа и базис.
учебное пособие , добавлен 02.03.2009
Основное понятие теории положительных (натуральных) чисел. Развитие стенографии для операций арифметики. Символический язык для делимости. Свойства и алгебра сравнений. Возведение сравнений в степень. Повторное возведение в квадрат. Малая теорема Ферма.
презентация , добавлен 04.06.2014
Системы цифровой обработки информации. Понятие алгебры Буля. Обозначения логических операций: дизъюнкция, конъюнкция, инверсия, импликация, эквивалентность. Законы и тождества алгебры Буля. Логические основы ЭВМ. Преобразование структурных формул.
презентация , добавлен 11.10.2014
Математическая логика и теория алгоритмов – Курс лекций
Введение.
Назначение .
Данный курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для постановки и решения задач в области информатики, для корректного понимания ограничений, возникающих при создании вычислительных структур, алгоритмов и программ обработки информации.
Новые разделы курса дискретной математики, хотя и реализованы в виде учебных программ и циклов лекций, пока не существуют в виде монографий, по крайней мере, на русском языке, так как курс дискретной математики для технических вузов ориентирован на старые прикладные задачи, которые приходилось решать инженерам. В частности в математической логике это была минимизация логических схем, которая сегодня потеряла актуальность.
Интересно отметить, что теория синтеза логических схем, пройдя почти полный "биологический цикл" на глазах одного поколения исследователей, представляет собой весьма поучительный пример того, как сильно подвержены моральному старению отрасли технических наук, слабо связанные с фундаментальной наукой. Ещё 10 лет назад все технические журналы были заполнены статьями по минимизации и синтезу логических схем. Большинство методов минимизации, разработанных учёными, сейчас забыты и не востребованы практикой. А те идеи, которые в то время считались сугубо теоретическими, нашли практическое применение в современной технике. Например, нечёткая логика, сети Петри и теория алгоритмов выдержали проверку временем и находят широкое применение в различных областях кибернетики и программирования, таких как системное программирование, сложность вычисления и искусственный интеллект.
И теория алгоритмов стала центральным разделом дискретной математики. Однако в отличие от большинства монографий на русском языке в курсе лекций эти вопросы изложены как средство решения практических, инженерных задач.
Как известно, по истечении каждого десятилетия элементная база компьютеров, операционные системы, средства доступа и сами программы меняются коренным образом. Однако структуры и алгоритмы, лежащие в их основе, остаются неизменными в течение гораздо большего времени. Эти основы стали закладываться тысячелетия назад, когда разработана формальная логика и разработаны первые алгоритмы.
Математическая логика и теория алгоритмов традиционно относятся к фундаментальной науке и считаются мало связанными с практикой и трудными для понимания. Действительно, когда Дж. Буль создал математический аппарат булевой алгебры, он долго не находил практического применения, однако в 20-ом столетии именно этот математический аппарат позволил спроектировать все узлы ЭВМ. Следовательно, первый из этих предрассудков успешно опровергается развитием вычислительной техники.
Что же касается предрассудка о трудности понимания этой дисциплины, то он в значительной степени происходит оттого, что книги по математической логике и теории алгоритмов написаны математиками для математиков.
Сейчас, когда возможности вычислительной техники многократно возросли, а самих персональных компьютеров значительно больше, чем людей, умеющих их эффективно использовать, понимание того, что можно и что нельзя сделать с помощью современной вычислительной техники приобретает исключительное значение.
Именно общая теория алгоритмов показала, что есть задачи неразрешимые ни при каком увеличении мощности вычислительных средств, а её бурно развивающаяся ветвь - теория сложности вычислений постепенно приводит к пониманию того, что бывают задачи разрешимые, но объективно-сложные, причём сложность их может оказаться в некотором смысле абсолютной, т.е. практически недоступной для современных ЭВМ.
В данном курсе ставились следующие задачи:
1. Изложить все рассматриваемые вопросы по возможности как можно более просто, но не проще чем это требуется для специалиста высшей квалификации.
2. Практические проблемы проектирования и анализа информационных систем являются отправной точкой, а формальный аппарат – средством систематического решения этих проблем. По нашему глубокому убеждению, студент – это не сосуд, который надо наполнить, а факел, который надо зажечь.
3. Каждый раздел курса содержит вопросы для самопроверки. Для усвоения данного курса студент обязан ответить на все эти вопросы.
В результате освоения данного курса студент на основе ясного понимания соответствующих теоретических разделов должен уметь:
Реализовывать простейший вид логического преобразования информации в произвольном базисе логических функций;
Выделять в доказательных рассуждениях естественного языка логическую структуру, строить схемы формальных доказательств и проверять их правильность.
1.2 Логические представления
Логические представления -
описание исследуемой системы, процесса, явления в виде совокупности сложных высказываний,
составленных из простых (элементарных) высказываний
и логических связок
между ними. Логические представления и их составляющие характеризуются определенными свойствами и набором допустимых преобразований над ними (операций, правил вывода и т.п.), реализующих разработанные в формальной (математической) логике правильные методы рассуждений - законы логики.
Способы (правила) формального представления высказываний, построения новых высказываний из имеющихся с помощью логически правильных преобразований, а также способы (методы) установления истинности или ложности высказываний изучаются в математической логике.
Современная математическая логика включает два основных раздела: логику высказываний
и охватывающую ее логику предикатов
(рис. 1.1), для построения которых существуют два подхода (языка), образующих два варианта формальной логики: алгебру логики
и логические исчисления.
Между основными понятиями этих языков формальной логики имеет место взаимно однозначное соответствие. Их изоморфизм обеспечивается в конечном итоге единством , лежащих в основе допустимых преобразований.
Рис. 1.1
Основными объектами традиционных разделов логики являются высказывания.
Высказывание -
повествовательное предложение (утверждение, суждение), о
котором имеет смысл говорить, что оно истинно
или ложно.
Все научные знания (законы и явления физики, химии, биологии и др., математические теоремы и т.п.), события повседневной жизни, ситуации, возникающие в экономике и процессах управления, формулируются в виде высказываний. Повелительные и вопросительные предложения не являются высказываниями.
Примеры высказываний: "Дважды два - четыре", "Мы живем в XXI веке", "Рубль - российская валюта", "Алеша - брат Олега", "Операции объединения, пересечения и дополнения являются булевыми операциями над множествами", "Человек смертен", "От перестановки мест слагаемых сумма не меняется", "Сегодня понедельник", "Если идет дождь, вам следует взять зонт".
Для того чтобы далее оперировать этими предложениями как высказываниями, мы обязаны знать относительно каждого из них, истинно оно или ложно, т.е. знать их истинностное значение (истинность).
Заметим, что в ряде случаев истинность или ложность высказывания зависит от того, какую конкретную реальность (систему, процесс, явление) мы пытаемся с его помощью описать. В таком случае говорят, что данное высказывание истинно (или ложно) в данной интерпретации (контексте). Далее предполагаем, что контекст задан и высказывание имеет определенное истинностное значение.
1.3 История развитая математической логики
Логика как наука сформировалась в 4 в. до н.э. Ее создал греческий ученый Аристотель.
Слово «логика» происходит от греческого "логос", что с одной стороны означает "слово" или "изложение", а с другой мышление. В толковом словаре Ожегова С.И. сказано: "Логика наука о законах мышления и его формах".
В 17 в. немецкий ученый Лейбниц задумал создать новую науку, которая была бы «искусством исчисления истины».
В этой логике, по мысли Лейбница, каждому высказыванию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников,не получила распространения и развития и осталась гениальной догадкой.
Только в середине 19 в. ирландский математик Джордж Буль воплотил идею Лейбница.В 1854 году им была написана работа "Исследование законов мышления" (Investigation the laws of thought), которая заложила основы алгебры логики, в которой действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а высказывания. На языке булевой алгебры можно описать рассуждения и "вычислить" их результаты. Однако ею охватываются далеко не все рассуждения, а лишь определенный тип их,
поэтому алгебру Буля считают исчислением высказываний.
Алгебра логики Буля явилась зародышем новой науки – математической логики. В отличии от нее, логику Аристотеля называют традиционной формальной логикой. В названии "математическая логика" отражены две особенности этой науки: во-первых, математическая логика - это логика, использующая язык и методы математики; во-вторых, математическая логика вызвана к жизни потребностями математики.
В конце 19 в. созданная Георгом Кантором теория множеств представлялась надежным фундаментом для всей математики, в том числе и математической логики, по крайней, мере, для исчисления высказываний (алгебры Буля),т.к. оказалось, что алгебра Кантора (теория множеств) изоморфна алгебре Буля.
Математическая логика сама стала областью математики, поначалу казавшейся в высшей степени абстрактной и бесконечно далекой от практических приложений. Однако эта область недолго оставалась уделом "чистых" математиков. В начале 20 в. (1910 г.) русский ученый Эренфест П.С. указал на возможность применения аппарата булевой алгебры в телефонной связи для описания переключательных цепей. В 1938-1940 г. почти одновременно появились работы советского ученого Шестакова В. И., американского ученого Шеннона и японских ученых Накасимы и Хакадзавы о применении математической логики в цифровой технике. Первая монография, посвященная использованию математической логики при проектировании цифровой аппаратуры, была опубликована в СССР советским ученым Гавриловым М.А. в 1950 г. Чрезвычайно важна роль математической логики в развитии современной микропроцессорной техники: она используется в проектировании аппаратных средств ЭВМ, в разработке всех языков программирования и в конструировании дискретных устройств автоматики.
Большой вклад в развитие математической логики сделали ученые разных стран: профессор Казанского Университета Порецкий П.С., де-Морган, Пирс, Тьюринг, Колмогоров А.Н., Гейдель К. и др.
1.4 Вопросы для самопроверки.
1. Сформулируйте задачи курса
Education in Great Britain - Образование в Великобритании (5), устная тема по английскому языку с переводом
Иван петрович павлов, открытия
Мария значение имени - характер и судьба