Размещено на http://www.allbest.ru/

2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет физико-математических и компьютерных наук

Кафедра математики

Контрольная работа на тему:

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

Выполнила:

Студентка 2 курса

группы МФ-2

Понамарева Виктория Сергеевна

Научный руководитель:

к. ф.-м. н., доцент

Ершова Александра Алексеевна

Липецк, 2014



Оглавление

Введение

§1. История возникновения математической логики

§2. Применение математической логики

§3. Математическая логика в технике

§4. Математическая логика в криптографии

§5. Математическая логика в программировании

Заключение

Список используемой литературы

математическое обозначение криптография логика программирование



Введение

Логика - это наука, изучающая формы и законы мышления, закономерности мыслительного процесса. Слово «логика» произошло от греческого logos, что означает слово, понятие, рассуждение, разум. Законы и правила формальной логики необходимо знать для построения правильных рассуждений.

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

Например, рассуждения «Все люди смертны. Сократ - человек.

Следовательно, Сократ смертен» и «Все металлы электропроводны. Медь - металл. С

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

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



§1. История возникновения математической логики

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

В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно» . Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав . При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.

Следует отметить, что идея использования двух символов для кодирования информации очень стара. Австралийские аборигены считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире.

После Лейбница исследования в этой области вели многие выдающиеся ученые, однако настоящий успех пришел здесь к английскому математику-самоучке Джорджу Булю (1815--1864), целеустремленность которого не знала границ. Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей».

Буль изобрел своеобразную алгебру - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.

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

Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

В XX веке огромную роль в развитии математической логики сыграл Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований самой математики. Наконец, в последние десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков, Гегель и многие другие).

Гегель (1770-1831) весьма иронично отзывался о законе противоречия и законе исключенного третьего. Последний он представлял, в частности, в такой форме: "Дух является зеленым или не является зеленым", и задавал "каверзный" вопрос: какое из этих двух утверждений истинно? Ответ на этот вопрос не представляет, однако, труда. Ни одно из двух утверждений: "Дух зеленый" и "Дух не зеленый" не является истинным, поскольку оба они бессмысленны. Закон исключенного третьего приложим только к осмысленным высказываниям. Только они могут быть истинными или ложными. Бессмысленное же не истинно и не ложно. Гегелевская критика логических законов опиралась, как это нередко бывает, на придание им того смысла, которого у них нет, и приписывание им тех функций, к которым они не имеют отношения. Случай с критикой закона исключенного третьего - один из примеров такого подхода. Критика закона исключенного третьего (Л.Бауэр) привела к созданию нового направления в логике - интуиционистской логики. В последней не принимается этот закон и отбрасываются все те способы рассуждения, которые с ним связаны. Среди отброшенных, например, оказывается доказательство путем приведения к противоречию, или абсурду.

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

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

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

Четвертый закон - закон достаточного основания

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

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

Достаточным, т. е. действительным, невымышленным основанием наших мыслей может являться индивидуальная практика. Действительно, истинность некоторых суждений подтверждается путем их непосредственного сопоставления с фактами действительности (Пример: "[Истинно, что]Идет дождь", "[Является ложью то, что]Я был в Акапулько"). Но личный опыт ограничен. Поэтому в реальной деятельности всегда приходится опираться на опыт других людей. Благодаря развитию научных знаний субъект использует в качестве оснований своих мыслей опыт предшественников, закрепленный в законах и аксиомах науки, в принципах и положениях, существующих в любой области человеческой деятельности. Для подтверждения какого-либо частного случая нет необходимости обращаться к его практической проверке, обосновывать его при помощи личного опыта. Если, например, мне известен закон Архимеда, то мне совсем не обязательно искать ванну с водой, чтобы, поместив туда предмет, выяснить, сколько он потерял в весе. Закон Архимеда будет достаточным основанием для подтверждения этого частного случая.

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

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

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

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

§2. Применение математической логики

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

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

Информатика - это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.

Строительство логических машин - интересная глава истории логики и кибернетики. В ней запечатлены первые проекты создания искусственного разума и первые споры о возможности этого. Идея логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики. В 1870 году английский философ и экономист Вильям Стэнли Джевонс построил в Манчестере “логическое пианино”, которое извлекало из алгебраически записанных посылок следствия, выделяя допустимые комбинации терминов. Это называют также разложением высказываний на конституанты. Важно отметить возможность практического применения логической машины для решения сложных логических задач.

Современные универсальные вычислительные машины являются вместе с тем логическими машинами. Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь “разумных автоматов” соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику.

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

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

§3. Математическая логика в технике

Роль логической обработки бинарных данных на современном этапе развития вычислительной техники существенно возросла. Это связано, в первую очередь, с созданием технически систем. реализующих в том или ином виде технологии получения и накопления знаний, моделированием отдельных интеллектуальных функций человека. Ядром таких систем являются мощные ЭВМ и вычислительные комплексы. Кроме того, существует большой класс прикладных задач, которые можно свести к решению логических задач, например, обработка и синтез изображений, транспортные задачи. Требуемая производительность вычислительных средств достигается путем распараллеливания и конвейеризации вычислительных процессов. Это реализуется, как правило, на основе сверхбольших интегральных, схем (СБИС). Однако технология СБИС и их структура предъявляет ряд специфических требований к алгоритмам, а именно: регулярность, параллельно - поточная организация вычислений, сверхлинейная операционная сложность (многократное использование каждого элемента входных данных), локальность связей вычислений, двумерность пространства реализации вычислений. Эти требования обусловливают необходимость решения проблемы эффективного “погружения” алгоритма в вычислительную среду, или, как еще принято говорить, - отображение алгоритма в архитектуру вычислительных средств. В настоящее время доказана ошибочность ранее широко распространенных взглядов, состоящих в том, что переход на параллельно -конвейерные архитектуры ЭВМ потребуют лишь небольшой модификации известных алгоритмов. Оказалось, что параллелилизм и конвейеризация вычислительных процессов требует разработки новых алгоритмов даже для тех задач, для которых существовали хорошо изученные и апробированные методы и алгоритмы решения, но ориентированные на последовательный принцип реализации. По прогнозам специалистов, в ближайшее десятилетие следует ожидать появления новых концепций построения вычислительных средств. Основанием для прогнозов являются результаты проводимых в настоящее время перспективных исследований, в частности, в области биочипов и органических переключающих элементов. Некоторые направления ставят своей целью создание схем в виде слоев органических молекул и пленок с высокоразвитой структурой. Это позволит, по мнению исследователей, “выращивать” компьютеры на основе генной инженерии и усилить аналогию между элементами технических систем и клетками мозга. Тем самым реальные очертания приобретают нейрокомпьютеры, которые имитируют интеллектуальные функции биологических объектов, в том числе человека. По-видимому, молекулярная электроника станет основой для создания ЭВМ шестого поколения. Все это объективно обусловливает интенсивные работы по методам синтезов алгоритмов обработки логических данных и их эффективному погружению в операционную среду бинарных элементов. Очевидно, что бинарные элементы и бинарные данные наиболее полно соответствуют друг другу в плане представления и обработки последних на таких элементах, если рассматривать их по отдельности. Действительно, положим, алгебра логики над числами (0,1) реализуется на бинарном элементе полном использовании его операционного ресурса. Другими словами, ставится вопрос об эффективности, а иногда вообще возможности реализации данного алгоритма на такой сети (структуре). В этом состоит суть погружения алгоритма в структуру.

§4. Математическая логика в криптографии

Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Общая схема защиты информации представлена на рисунке 2. Этап кодирования от ошибок основан на внесении в передаваемое сообщение избытка информации, достаточного для преодоления помех на линии связи. Например, допустим, передается последовательность символов типа “0” и “1”. При этом в сети связи с некоторой вероятностью могут происходить ошибки приема сигнала “0 “ вместо сигнала “1” или наоборот, тогда кодер на каждый символ ai сообщения передает пятью импульсами 00000, если ai -0 и наоборот. На приемном конце принимаемая последовательность импульсов разбивается по пять импульсов, называемая блоками. Если в принятом блоке содержится 2 и менее импульса 0, то принимается решение о том, что передавался символ ai-1. Таким образом, исходная вероятность ошибки будет значительно снижена. Более элегантные методы кодирования, которые при достаточной надежности позволяют вносить не такой большой избыток информации. Для выражения в информации требуется ввести некоторый алфавит, из которого будет состоять сообщение (конечные упорядоченные множества из этих символов). Обозначим через A - мощность выбранного алфавита. Будем также считать, что все множества информации или , что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять log₂ от числа всевозможных сообщений конечно. Тогда объем информации, падающий на один символ алфавита X=log₂a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log₂N=Log₂As=SX. Львиную долю криптоанализа составляют методы, построенные на вероятностном анализе криптограммы и предлагаемого исходного языка. Поскольку всякий обычный язык имеет избыток информации, причем неравномерно размешенных в словах , то буквы алфавита этого языка могут иметь устойчивые частные характеристики. Например, в английском языке - это часто повторяющая буква “e”, кроме того, частотными характеристиками могут быть буквосочетания и их комбинации. Общая схема криптосистемы с секретным ключом изображена на рисунке 3. Здесь Х - открытый текст, Y- шифр текста, K - ключ шифра, R - рандомизирующая последовательность.

§5. Математическая логика в программировании

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

Понятие функции было перенесено в языки программирования. В языке программирования, как правило, предусмотрен ряд встроенных функций, например sin, cos, sqrt и т.д. Кроме того, программист имеет возможность определять свои собственные функции. Они могут работать не только с вещественными числами, но и с различными типами данных, включающими обычно integer (целое), real (вещественное), boolean (булевское), character (строковое). Они могут также работать со структурами. В языках Паскаль, Алгол=68 и ПЛ/1 имеются, например, типы records (записи), arrays (массивы), lists (списки), files of records (файлы, состоящие из записей), а значениями функций могут быть указатели этих структур. Все это согласовано с понятием области определения, вне которой функция не определена. В языках программирования эта область задана обычно указанием типа данных, который является некоторым множеством величин. Так, в Паскале компилятор должен следить за тем, чтобы никакая функция не применялась к величине неподходящего типа, которая могла бы выйти за пределы области определения функции.

Функция многих аргументов. Теперь нужно обобщить определение, чтобы охватить функции многих аргументов. Для этого соберем n аргументов в упорядоченный набор, который будем рассматривать как один аргумент. Возьмем функцию вычитания diff(x.y). Трактуется ее как отображение пар <х,у> в целые числа. В виде множества упорядоченных пар ее можно записать следующим образом: diff = {<<5,3>, 2>. <<6,3>, 3>, <<4,5>, -1>...} Если бы вместо этого у нас была функция четырех аргументов h(x,y,z,w), то использовали бы отображение, определенное на четверках <x,y,z,w>. Этот прием используется и в программировании. Если необходимо уменьшить количество аргументов процедуры или функции (причем все они имеют один и тот же тип), то в Фортране можно записать эти значения в массив и передать в качестве параметра этот массив, а не отдельные значения. В более общем случае (например, в Паскале), когда аргументам разрешается иметь различные типы, можно передать в качестве параметра запись и хранить значения в виде отдельных компонент этой записи. В действительности набор, состоящий из n элементов в математике соответствует записи в программировании. Каждая из ее компонент берется из своей отдельной области, как и в случае записи. Единственное отличие состоит в том, что компонента определяется своим расположением (позицией), а не именем. Реляционная модель данных работает с множествами упорядоченных наборов, которые соответствуют файлам записей, хранящимся в машине. Также математическая логика используется и в других областях информатики - это в разработке в области моделирования и автоматизации интеллектуальных процедур - направление так называемого искусственного интеллекта.



Заключение

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



Список используемой литературы

1.Игошин, В.И. Математическая логика и теория алгоритмов [Текст] / В.И. Игошин. - М.: Академия, 2008. - 448 с.; с ил.

2.Стяжкин, Н.И. Формирование математической логики [Текст] / Н.И. Стяжкин. - М.: Наука, 1967. - 508 с.; с ил.

3.Марков, А.А. Элементы математической логики [Текст] / А.А. Марков. - М.: МГУ, 2004. - 310 с.; с ил.

4.Карри, Х.Б. Основания математической логики [Текст]/Х.Б. Карри. - М.: Мир, 1969. - 568 с.; с ил.

Размещено на Allbest.ru