МАТЕМАТИЧЕСКАЯ ЛОГИКА
теоретическая логика, символическая логика,- раздел математики, посвященный изучению математич. доказательств и вопросов оснований математики.
Исторический очерк. Идея построения универсального языка для всей математики и формализации на базе такого языка математич. доказательств выдвигалась в 17 в. Г. Лейбницем (G. Leibniz). Но только в сер. 19 в. появились первые научные работы по алгебраизации аристотелевод логики [Дж. Буль (G. Boole, 1847) и О. де Морган (A. de Morgan, 1858)]. После того как Г. Фреге (G. Frege, 1879) и Ч. Пирс (С. Peirce, 1885) ввели в язык алгебры логики предикаты, предметные переменные и кванторы, возникла реальная возможность применить этот язык к вопросам оснований математики.
С другой стороны, создание в 19 в. неевклидовой геометрии сильно поколебало уверенность математиков в абсолютной надежности геометрич. интуиции, на к-рой была основана . Сомнениям в надежности геометрич. интуиции способствовало также то, что в результате развития исчисления бесконечно малых математики натолкнулись на неожиданные примеры всюду непрерывных функций без производных. Появилась потребность отделить понятие действительного числа от неясного понятия "величины", к-рое было основано на геометрич. интуиции. Эта задача была решена разными путями в работах К. Вейерштрасса (К. Weierstrab, P. Дедекинда (R. Dedekind) и Г. Кантора (G. Cantor). Они показали возможность "арифметизации" анализа и теории функций, в результате чего в качестве фундамента всей классич. математики стала рассматриваться целых чисел. Затем была предпринята аксиоматизация арифметики [Р. Дедекинд (1888) и Дж. Пеано (G. Реаnо, 1891)]. При этом Дж. Пеано создал более удобную символику для логич. языка. Пвзже этот язык был усовершенствован в совместном труде Б. Рассела (В. Russell) и А. Уайтхеда (A. Whitehead) "Принципы математики" (1910), где была предпринята попытка сведения всей математики к логике.
Но эта попытка не увенчалась успехом, т. к. оказалось невозможным вывести из чисто логич. аксиом существование бесконечных множеств. Хотя логистич. Фреге - Рассела в основаниях математики так и не достигла своей главной цели - сведения математики к логике, в их работах был создан богатый логич. аппарат, без к-рого оформление М. л. как полноценной математич. дисциплины было бы невозможно.
На рубеже 19-20 вв. были обнаружены антиномии,
связанные с основными понятиями теории множеств. Наиболее сильное впечатление на современников произвела опубликованная в 1903 Рассела. Пусть Месть всех таких множеств, каждое из к-рых не является своим собственным элементом. Легко убедиться, что Мявляется своим элементом тогда и только тогда, когда Мне является своим элементом. Конечно, можно пытаться выйти из создавшегося противоречия, сделав заключение, что такого множества Мне бывает. Однако, если не может существовать множество, состоящее в точности из всех элементов, удовлетворяющих такому четко определенному условию, к-рое мы имеем в приведенном выше определении множества М,
то где гарантия того, что в нашей повседневной работе мы не столкнемся с множествами, к-рые также не могут существовать? И каким, вообще, условиям должно удовлетворять определение множества для того, чтобы оно существовало? Ясно было одно: нужно как-то ограничить канторовскую теорию множеств.
Л. Брауэр (L. Brouwer, 1908) выступил против применения правил классич. логики к бесконечным множествам. В выдвинутой им интуиционистской программе предлагалось отказаться от рассмотрения абстракции актуальной бесконечности,
т. е. бесконечных множеств как завершенных совокупностей! Допуская существование сколь угодно больших натуральных чисел, интуиционисты выступают против рассмотрения натурального ряда как завершенного множества. Они считают, что в математике всякое существования того или иного объекта должно быть конструктивным, т. е. должно сопровождаться построением этого объекта. Если предположение о том, что искомый не существует, приведено к противоречию, то это, по мнению интуиционистов, не может рассматриваться как доказательство существования. Особой критике со стороны интупционистов подвергся исключенного
третьего закон.
Ввиду того, что этот закон первоначально рассматривался применительно к конечным множествам и, учитывая, что многие свойства конечных множеств не выполняются для бесконечных множеств (напр., что всякая собственная часть меньше целого), интуиционисты считают неправомерным применение этого закона к бесконечным множествам. Так, напр., чтобы утверждать, что проблема Ферма имеет положительное или имеет отрицательное решение, интуиционист должен указать соответствующее решение этой проблемы. А пока проблема Ферма не решена, эта считается неправомерной. Такое же требование предъявляется к пониманию всякой дизъюнкции. Это требование интуиционистов может создать затруднения и в случае рассмотрения задач, связанных с конечными множествами. Представим себе, что кто-то, закрыв глаза, достает из урны, в к-рой имеются три черных и три белых шара, и тут же бросает этот шар обратно. Если никто не видел этот шар, то мы не имеем возможности узнать, какого он был цвета. Однако вряд ли можно всерьез оспаривать утверждения, что этот шар был либо черного, либо белого цвета.
Интуиционисты построили свою математику, имеющую интересные своеобразные особенности. Но она оказалась более сложной и громоздкой, чем классич. . Положительный вклад интуиционистов в исследование вопросов оснований математики выразился в том, что они еще раз решительным образом подчеркнули различие между конструктивным и неконструктивным в математике, они провели тщательный анализ многих трудностей, с к-рыми столкнулась математика в своем развитии, и тем самым способствовали их преодолению.
Д. Гильберт (D. Hilbert, см. добавления VII-X в ) наметил другой преодоления трудностей, возникших в основаниях математики на рубеже 19-20 вв. Этот путь, основанный на применении аксиоматич. метода рассмотрения формальных моделей, содержательной математики и на исследовании вопросов непротиворечивости таких моделей надежными финитными средствами, получил в математике название финитизма Гильберта. Признавая ненадежность геометрич. интуиции, Д. Гильберт прежде всего предпринимает тщательный пересмотр евклидовой геометрии, освобождая ее от обращения к интуиции. Результатом такой переработки явились его "Основания геометрии" (1899).
Вопросы непротиворечивости различных теорий по существу рассматривались и до Д. Гильберта. Так, построенная Ф. Клейном (F. Klein, 1871) проективная неевклидовой геометрии Лобачевского сводит вопрос о непротиворечивости геометрии Лобачевского к непротиворечивости евклидовой геометрии. Непротиворечивость евклидовой геометрии аналогично можно свести к непротиворечивости анализа, т. е. теории действительных чисел. Однако не видно было, какими средствами можно строить модели анализа и арифметики для доказательства их непротиворечивости. Заслуга Д. Гильберта состоит в том, что он указал прямой путь для исследования этого вопроса. Непротиворечивость данной теории означает, что в ней не может быть получено , т. е. не может быть доказано нек-рое утверждение Аи его Д. Гильберт предложил представить рассматриваемую теорию в виде формальной аксиоматич. системы, в к-рой будут выводимы все те и только те утверждения, к-рые являются теоремами нашей теории. Тогда для доказательства непротиворечивости достаточно установить невыводимость в рассматриваемой теории нек-рых утверждений. Таким образом, математич. , непротиворечивость к-рой мы хотим доказать, становится предметом изучения нек-рой математич. науки, к-рую Д. Гильберт назвал метаматематикой, или теорией доказательств.
Д. Гильберт писал, что парадоксы теории множеств вызваны не законом исключенного третьего, а "скорее тем, что математики пользуются недопустимыми и бессмысленными образованиями понятий, к-рые в моей теории доказательств исключаются сами собой. ...Отнять у математиков закон исключенного третьего - это то же, что забрать у астрономов телескоп или запретить боксерам использовать кулаки" (см. с. 383). Д. Гильберт предлагает различать "действительные" и "идеальные" предложения классич. математики. Первые имеют содержательный смысл, а вторые не обязаны иметь содержательный смысл. Предложения, соответствующие употреблению актуальной бесконечности, идеальны. Идеальные предложения присоединяются к действительным для того, чтобы простые правила логики были применимы и к рассуждениям о бесконечных множествах. Это существенно упрощает структуру всей теории подобно тому, как при рассмотрении проективной геометрии на плоскости добавляется бесконечно удаленная , пересекающая любые две в нек-рой точке.
Выдвинутая Д. Гильбертом программа обоснования математики и его энтузиазм вдохновили современников на интенсивную разработку аксиоматического метода. Именно с предпринятой в начале 20 в. Д. Гильбертом и его последователями разработкой теории доказательств на базе развитого в работах Г. Фреге, Дж. Пеано и Б. Рассела логич. языка следует связывать становление М. л. как самостоятельной математич. дисциплины.
Предмет и основные разделы математической логики, связь с другими областями математики.
Предмет современной М. л. разнообразен. Прежде всего следует отметить исследование логич. и логико-математич. исчислений, из к-рых основным является классич. предикатов. Еще в 1930 К. Гёдель (К. Godel) доказал теорему о полноте исчисления предикатов, согласно к-рой множество всех чисто логич. утверждений математики совпадает с множеством всех выводимых в исчислении предикатов формул (см. Гёделя о полноте
).
Эта теорема показала, что исчисление предикатов является той логич. системой, на базе к-рой можно формализовать математику. На базе исчисления предикатов строятся различные логико-математич. теории (см. Логико-математические исчисления
),
представляющие собой формализацию содержательных математич. теорий - арифметики, анализа, теории множеств, теории групп и др. Наряду с элементарными теориями
рассматриваются также теории высших порядков, в к-рых допускаются также кванторы по предикатам, предикаты от предикатов и т. д. Традиционными вопросами, к-рые исследуются для тех или иных формальных логич. систем, являются исследования структуры выводов в этих системах, тех или иных формул, вопросы непротиворечивости и полноты рассматриваемых систем.
Доказанная в 1931 Гёделя теорема о неполноте
арифметики поколебала оптимистич. надежды Д. Гильберта на полное решение вопросов оснований математики на указанном пути. Согласно этой теореме, если , содержащая арифметику, непротиворечива, то утверждение о ее непротиворечивости, выразимое в этой системе, не может быть доказано средствами, формализуемыми в ней. Это означает, что с вопросами оснований математики дело обстоит не так просто, как хотелось или казалось Д. Гильберту вначале. Но уже К. Гёдель заметил, что непротиворечивость арифметики можно доказывать, пользуясь достаточно надежными конструктивными средствами, хотя и выходящими за рамки средств, формализуемых в арифметике. Аналогичные доказательства непротиворечивости арифметики были получены Г. Генценом (G. Gentzen, 1936) и П. С. Новиковым (1943).
В результате анализа канторовской теории множеств и связанных с ней парадоксов были построены различные системы аксиоматической теории множеств,
в к-рых принимается то или иное ограничение на образование множеств, чтобы исключить возникновение известных антиномий. В этих аксиоматич. системах могут быть развиты довольно обширные разделы математики. Вопрос о непротиворечивости достаточно богатых аксиоматич. систем теории множеств остается открытым. Из наиболее значительных результатов, полученных в аксиоматич. теории множеств, следует отметить результат К. Гёделя о непротиворечивости континуум-гипотезы
и выбора аксиомы
в системе Бернайса - Гёделя (1939) и результат П. Коэна (P. Cohen, 1963) о независимости этих аксиом от аксиом системы Цермело-Френкеля ZF. Отметим, что эти две системы аксиом и ZF равнонепротиворечивы. Для доказательства своих результатов К. Гёдель ввел важное понятие конструктивного множества (см. Конструктивное по Гёдeлю множество
).и показал существование модели системы состоящей из таких множеств. Метод К. Гёделя был использован П. С. Новиковым для доказательства непротиворечивости нек-рых других утверждений дескриптивной теории множеств (1951). Для построения моделей теории множеств ZF, в к-рых выполняются отрицания континуум-гипотезы или аксиомы выбора, П. Коэн ввел так наз. вынуждения метод,
к-рый впоследствии был усовершенствован и стал основным методом построения моделей теории множеств, удовлетворяющих тем или иным свойствам.
Одним из наиболее замечательных достижений М. л. явилась разработка понятия общерекурсивной функции
и формулировка Чёрча тезиса,
утверждающего, что понятие общерекурсивной функции является уточнением интуитивного понятия алгоритма.
Из других эквивалентных уточнений понятия алгоритма наибольшее распространение получили понятия Тьюринга машины
и нормального алгорифма
Маркова. По существу вся математика связана с теми или иными алгоритмами. Но только после уточнения понятия алгоритма появилась возможность обнаружить существование неразрешимых алгоритмических проблем
в математике. Неразрешимые алгоритмич. проблемы были обнаружены во многих разделах математики ( , теория чисел, теория вероятностей и др.), причем оказалось, что они могут быть связаны с очень распространенными и фундаментальными понятиями математики. Исследование алгоритмич. проблем в той или иной области математики, как правило, сопровождается проникновением идей и методов М. л. в эту , что приводит к решению также и других проблем, уже не имеющих алгоритмич. характера.
Разработка точного понятия алгоритма дала возможность уточнить понятие эффективности и развивать на базе такого уточнения конструктивное в математике (см. Конструктивная математика
),
воплотившее в себе нек-рые черты интуиционистского направления, но существенно отличающееся от последнего. Были созданы основы конструктивного анализа, конструктивной топологии, конструктивной теории вероятностей и др.
В самой теории алгоритмов можно выделить исследования в области рекурсивной арифметики, куда входят различные классификации рекурсивных и рекурсивно-перечислимых множеств, степени неразрешимости рекурсивно-перечислимых множеств, исследования сложности записи алгоритмов и сложности алгоритмич. вычислений (по времени и по зоне, см. Алгоритма слож
ность
). Обширным развивающимся разделом теории алгоритмов является теория нумераций.
Как отмечалось выше, аксиоматич. метод оказал большое влияние на развитие многих разделов математики. Особенно значительным было проникновение этого метода в алгебру. Так, на стыке М. л. и алгебры возникла общая теория алгебраических систем,
или моделей теория.
Это направление было заложено в работах А. И. Мальцева, А. Тарского (A. Tarski) и их учеников. Здесь можно отметить исследования по элементарным теориям классов моделей, в частности вопросы разрешимости этих теорий, аксиоматизируемость классов моделей, моделей, вопросы категоричности и полноты классов моделей.
Важное место в теории моделей занимает исследование нестандартных моделей арифметики и анализа. Еще на заре развития дифференциального исчисления в работах Г. Лейбница (G. Leibniz) и И. Ньютона (I. Newton) бесконечно малые и бесконечно большие величины рассматривались как числа. Позже появилось понятие переменной величины, и математики отказались от употребления бесконечно малых чисел, к-рых отличен от нуля и меньше любого положительного действительного числа, т. к. их употребление потребовало бы отказа от аксиомы Архимеда. И только через три столетия в результате развития методов М. л. удалось установить, что (нестандартный) анализ с бесконечно малыми и бесконечно большими числами непротиворечив относительно обычного (стандартного) анализа действительных чисел.
Не обошлась без влияния аксиоматич. метода и интуиционистская математика. Так, еще в 1930 А. Рейтинг (A. Heyting) ввел в рассмотрение формальные системы интуиционистской логики
высказываний и предикатов (конструктивные исчисления высказываний и предикатов). Позже были введены формальные системы интуиционистского анализа (см., напр., ). Многие исследования по интуиционистской логике и математике имеют дело с формальными системами. Подвергались специальному изучению также так наз. промежуточные логики
(или суперинтуиционистские), т. е. логики, лежащие между классической и интуиционистской логиками. Понятие реализуемости формул по Клини представляет одну из попыток интерпретировать понятие интуиционистской истинности с точки зрения классич. математики. Однако оказалось, что не всякая реализуемая исчисления высказываний выводима в интуиционистском (конструктивном) исчислении высказываний.
Подверглась формализации также и модальная логика.
Однако, несмотря на наличие большого числа работ по формальным системам модальной логики и по их семантике (Крипке модели
),
можно сказать, что здесь происходит процесс накопления пока еще разрозненных фактов.
М. л. имеет большое прикладное значение; с каждым годом растет глубокое проникновение идей и методов М. л. в кибернетику, в вычислительную математику, в структурную лингвистику.
Лит.
: Гильберт Д., Б е р н а й с П., Основания математики. Логические исчисления и формализация арифметики, пер. с нем., М., 1979; К л и н и С. К., Введение в метаматематику, пер. с англ., М., 1957; Мендельсон Э., Введение в математическую логику, пер. сангл., 2 изд., М., 1976; Новиков П. С., Элементы математической логики, 2 изд., М., 1973; Е р ш о в Ю. Л., Палютин Е. А., Математическая логика, М., 1979; Ш е н ф и л д Д. Р., Математическая логика, пер. с англ., М., 1975; Н о в и к о в П. С., Конструктивная математическая логика с точки зрения классической, М., 1977; К л и н и С. К., В е с л и Р., Основания интуиционистской математики с точки зрения теории рекурсивных функций, пер. с англ., М., 1978; Гильберт Д., Основания геометрик, пер. с нем., М., 1948; Френкель А.-А., Бар-Хиллел И., Основания теории множеств, пер. с англ., М., 1966; Математика XIX века. Математическая логика. Алгебра. Теория чисел. Теория вероятностей, М., 1978; Mostowski A., Thirty years of foundational studies, Hels., 1965.
См. также лит. при статьях об отдельных разделах М. л.
С. И.
Адян.
Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .
Синонимы :Смотреть что такое "МАТЕМАТИЧЕСКАЯ ЛОГИКА" в других словарях:
Одно из названий современной логики, пришедшей во втор. пол. 19 нач. 20 в. на смену традиционной логике. В качестве др. названия современного этапа в развитии науки логики используется также термин символическая логика. Определение… … Философская энциклопедия
«Если все вороны черные, то все нечерные предметы – не вороны». Это высказывание несомненно истинно, и, чтобы утверждать это, не нужно быть знатоком птиц. Точно так же не нужно быть специалистом в теории чисел, чтобы сказать, что если все совершенные числа четны, то все нечетные числа несовершенны. Мы привели примеры утверждений, истинных независимо от смысла входящих в них понятий (вороны, черные, совершенные, четные) – истинных уже в силу самой своей формы. Изучение такого рода утверждений входит в задачу логики. Более общо: логика изучает правильные способы рассуждений – такие способы рассуждений, которые приводят к верным результатам в тех случаях, когда верны исходные посылки.
Предметом математической логики служат в основном рассуждения. При их изучении она пользуется математическими методами. Разъясним сказанное.
Математики строят и развивают математические теории, дают определения, доказывают теоремы и т.п. Специалисты по математической логике, наблюдая за этим, анализируют, как математики это делают и что при этом получается. Образно говоря, соотношение между математикой и математической логикой похоже на соотношение между концертом и теорией музыки. Можно сказать, что математическая логика изучает основания математики, принципы построения математических теорий.
«Книга философии – это то, что всегда раскрыто перед нашими глазами, но так как она написана иными буквами, чем буквы нашего алфавита, то она не может быть прочитана всеми буквами этой книги являются треугольники, круги, шары, конусы, пирамиды и другие математические фигуры, очень пригодные для чтения ее». Г. Галилей
Установив, что изучает математическая логика, перейдем к тому, как она это делает. Нам уже известно, что она пользуется математическими методами. Объясним, что это значит. Как применяются математические методы, например, в физике? Строится математическая модель рассматриваемого физического процесса, отражающая какие-то его существенные свойства. Математические методы могут применяться не только в физике, но и в других науках. Например, применение математических методов в биологии состоит в построении математических моделей биологических процессов. Можно строить математические модели и для процесса развития математических теорий. Это и делает математическая логика.
Как устроена математическая теория? Она содержит какие-то утверждения. Некоторые из них принимаются без доказательств, другие удается доказать (в этом случае утверждения называют теоремами). Значение слов «утверждение» и «доказательство» в повседневной практике весьма расплывчато. Поэтому если мы хотим строить математическую модель, то первым делом нужно уточнить эти понятия, т.е. построить их формальные аналоги в нашей модели. Для этого математические логики придумали специальные формальные языки, предназначенные для записи математических утверждений. Утверждения, записанные на формальных языках, называют формулами, чтобы отличить их от предложений естественных языков. Построив формальный язык, мы получаем возможность записывать некоторые математические утверждения в виде формул. Этого, разумеется, еще не достаточно. Нам нужно уметь записывать формально не только утверждения, но и доказательства. Для этого математические логики придумали формальный аналог понятия «доказательство» - понятие вывода (доказательства, записанного на формальном языке). Формальным аналогом понятия «теорема» является понятие «выводимая формула» (т.е. формула, имеющая вывод). Формальный язык вместе с правилами построения выводов называется формальной системой.
Какие требования естественно предъявлять к формальной системе? Мы хотим, чтобы она была как можно более похожа на «живую», неформальную математику. Для этого нужно, чтобы все интересующие нас содержательные утверждения (или, по крайней мере, большая их часть) могли быть «переведены на формальный язык», т.е. записаны в виде формул этой системы. Кроме того, нужно, чтобы неформальные доказательства можно было перевести в выводы соответствующих формул.
В настоящее время построены вполне удовлетворительные модели (формализации) большинства математических теорий. Наиболее важны формальная арифметика и аксиоматическая теория множеств. Формальная арифметика предназначается для формализации рассуждений о натуральных числах, а аксиоматическая теория множеств – о множествах.
Основным предметом математической логики, таким образом, является построение и изучение формальных систем. Центральным результатом здесь является доказанная в 1931 г. австрийским математиком К. Геделем теорема о неполноте, утверждающая, что для любой «достаточно разумной» формальной системы существуют неразрешимые в ней предложения, т.е. такие формулы , что ни сама формула , ни ее отрицание не имеют вывода. Если отождествить формальную систему с соответствующей областью математики, то можно сказать, что в любой «достаточно разумной» области математики есть утверждения, которые нельзя ни доказать, ни опровергнуть. Мы не можем здесь точно сказать, что именно требуется от «достаточно разумной» формальной системы; отметим лишь, что большинство формальных систем (в том числе формальная арифметика и аксиоматическая теория множеств) удовлетворяют этим требованиям. На примере теоремы о неполноте мы видим, какую пользу приносит построение формальной системы: мы получаем возможность доказать, что какие-то утверждения недоказуемы!
Изучение формальных систем привело к возникновению многих важных направлений в современной математической логике. Назовем некоторые из них. Теория моделей исследует вопрос о том, как можно придать «смысл» выражениям формальных языков и что при этом получается. Теория доказательств изучает свойства выводов в формальных системах. Важнейшим разделом логики, который сейчас уже можно рассматривать как самостоятельную дисциплину, является теория алгоритмов.
Многие знаки, придуманные логиками для построения формальных систем, постепенно вошли в общее употребление. К ним относятся логические связки (конъюнкция, «и»), (дизъюнкция, «или»), (импликация, «если... то...»), (отрицание, «неверно, что») и так называемые кванторы (всеобщности, «для всех») и (существования, «существует»). Смысл логических связок, помимо указанных в скобках названий, разъясняется так называемыми таблицами истинности. Эти таблицы показывают, будет ли сложное утверждение, составленное с помощью логических связок из простых, истинно (И) или ложно (Л) в зависимости от истинности его составных частей. Приведем их.
Например,
пятый столбец показывает, что утверждение может быть ложно, только если истинно, а ложно. С помощью
этих таблиц можно составить таблицу истинности и для более сложных утверждений,
например для утверждения 
.
|
|
|
||||
Составив ее, мы увидим, что это утверждение (шестой столбец) всегда истинно, независимо от истинности утверждений и (например, утверждение «
которые получаются, если подставить вместо утверждение « – ворона», а вместо - « – черная» или вместо - « – совершенные», а вместо - « – четные».
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет физико-математических и компьютерных наук
Кафедра математики
Контрольная работа на тему:
«История развития математической логики»
Выполнила:
Студентка 2 курса
группы МФ-2
Понамарева Виктория Сергеевна
Научный руководитель:
к. ф.-м. н., доцент
Ершова Александра Алексеевна
Липецк, 2014
Введение
§1. История возникновения математической логики
§2. Применение математической логики
§3. Математическая логика в технике
§4. Математическая логика в криптографии
§5. Математическая логика в программировании
Заключение
Список используемой литературы
математическое обозначение криптография логика программирование
Введение
Логика <#"center">§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 - мощность выбранного алфавита. Будем также считать, что все множества информации или, что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять log2 от числа всевозможных сообщений конечно. Тогда объем информации, падающий на один символ алфавита X=log2a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log2N=Log2As=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), то использовали бы отображение, определенное на четверках
Заключение
Математическая логика немало способствовала бурному развитию информационных технологий в XX веке, но из ее поля зрения выпало понятие "суждение", которое появилось в логике еще во времена Аристотеля и на котором, как на фундаменте, держится логическая основа естественного языка. Такое упущение отнюдь не способствовало развитию логической культуры общества и у многих даже породило иллюзию, что компьютеры способны мыслить не хуже самого человека. Многих даже не смущает то обстоятельство, что на фоне всеобщей компьютеризации в преддверии третьего тысячелетия логические нелепости в пределах самой науки (я уж не говорю о политике, законотворческой деятельности и о псевдонауке) встречаются даже чаще, чем в конце XIX века. И для того, чтобы понять суть этих нелепостей, нет необходимости обращаться к сложным математическим структурам с многоместными отношениями и рекурсивными функциями, которые применяются в математической логике. Оказывается, для понимания и анализа этих нелепостей вполне достаточно применить намного более простую математическую структуру суждения, которая не только не противоречит математическим основам современной логики, но в чем-то дополняет и расширяет их.
Список используемой литературы
1.Игошин, В.И. Математическая логика и теория алгоритмов [Текст] / В.И. Игошин. - М.: Академия, 2008. - 448 с.; с ил.
Стяжкин, Н.И. Формирование математической логики [Текст] / Н.И. Стяжкин. - М.: Наука, 1967. - 508 с.; с ил.
Марков, А.А. Элементы математической логики [Текст] / А.А. Марков. - М.: МГУ, 2004. - 310 с.; с ил.
Карри, Х.Б. Основания математической логики [Текст]/Х.Б. Карри. - М.: Мир, 1969. - 568 с.; с ил.
Репетиторство
Нужна помощь по изучению какой-либы темы?
Наши специалисты проконсультируют или окажут репетиторские услуги по интересующей вас тематике.
Отправь заявку
с указанием темы прямо сейчас, чтобы узнать о возможности получения консультации.
В современном мире мы все чаще используем разнообразные машины и гаджеты. И не только тогда, когда необходимо применить буквально нечеловеческую силу: переместить груз, поднять его на высоту, вырыть длинную и глубокую траншею и т. д. Автомобили сегодня собирают роботы, еду готовят мультиварки, а элементарные арифметические расчеты производят калькуляторы. Все чаще мы слышим выражение «булева алгебра». Пожалуй, пришло время разобраться в роли человека в создании роботов и умении машин решать не только математические, но и
Логика
В переводе с греческого логика - это упорядоченная система мышления, которая создает взаимосвязи между заданными условиями и позволяет делать умозаключения, основываясь на предпосылках и предположениях. Довольно часто мы спрашиваем друг друга: «Логично?» Полученный ответ подтверждает наши предположения либо критикует ход мысли. Но процесс не останавливается: мы продолжаем рассуждать.
Порой количество условий (вводных) настолько велико, а взаимосвязи между ними столь запутанны и сложны, что человеческий мозг не в состоянии «переварить» все сразу. Может понадобиться не один месяц (неделя, год) для понимания происходящего. Но современная жизнь не дает нам таких временных интервалов на принятие решений. И мы прибегаем к помощи компьютеров. И вот тут-то и появляется алгебра логики, со своими законами и свойствами. Загрузив все исходные данные, мы позволяем компьютеру распознать все взаимосвязи, исключить противоречия и найти удовлетворительное решение.
Математика и логика
Известнейший Готфрид Вильгельм Лейбниц сформулировал понятие «математическая логика», задачи которой были доступны для понимания только узкому кругу ученых. Особого интереса это направление не вызывало, и до середины XIX века о математической логике знали немногие.
Большой интерес в научных сообществах вызвал спор, в котором англичанин Джордж Буль заявил о своем намерении создать раздел математики, не имеющий абсолютно никакого практического применения. Как мы помним из истории, в это время активно развивалось промышленное производство, разрабатывались всевозможные вспомогательные машины и станки, т. е. все научные открытия имели практическую направленность.
Забегая вперед, скажем, что булева алгебра - самая используемая в современном мире часть математики. Так что спор свой Буль проиграл.
Джордж Буль
Сама личность автора заслуживает отдельного внимания. Даже учитывая то, что в прошлом люди взрослели раньше нас, все равно нельзя не отметить, что в 16 лет Дж. Буль преподавал в деревенской школе, а к 20 годам открыл собственную школу в Линкольне. Математик отлично владел пятью иностранными языками, а в свободное время зачитывался работами Ньютона и Лагранжа. И все это - о сыне простого рабочего!
В 1839 году Буль впервые послал свои научные работы в Кембриджский математический журнал. Ученому исполнилось 24 года. Работы Буля настолько заинтересовали членов Королевского научного общества, что в 1844 году он получил медаль за вклад в развитие Еще несколько опубликованных работ, в которых были описаны элементы математической логики, позволили молодому математику занять пост профессора в колледже графства Корк. Напомним, что у самого Буля образования не было.
Идея
В принципе, булева алгебра очень проста. Существуют выражения), которые, с точки зрения математики, можно определить только двумя словами: «истина» или «ложь». Например, весной деревья расцветают - истина, летом идет снег - ложь. Вся прелесть этой математики заключается в том, что нет строгой необходимости использовать только числа. Для алгебры суждений вполне подходят любые высказывания с однозначным смыслом.
Таким образом, алгебра логики может быть использована буквально везде: в составлении расписаний и написании инструкций, анализе противоречивой информации о событиях и определении последовательности действий. Самое главное - понять, что совершенно неважно, как мы определили истинность или ложность высказывания. От этих «как» и «почему» нужно абстрагироваться. Значение имеет только констатация факта: истина-ложь.
Безусловно, для программирования важны функции алгебры логики, которые записываются соответствующими знаками и символами. И выучить их - это значит освоить новый иностранный язык. Нет ничего невозможного.
Основные понятия и определения
Не вдаваясь в глубины, разберемся с терминологией. Итак, булева алгебра предполагает наличие:
- высказываний;
- логических операций;
- функций и законов.
Высказывания - любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон - самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».
Все высказывания должны носить однозначный характер, но они могут быть элементарными и составными. Последние используют логические связки. Т. е. в алгебре суждений составные высказывания образуются сложением элементарных посредством логических операций.
Операции булевой алгебры
Мы уже помним, что операции в алгебре суждений - логические. Подобно тому, как алгебра чисел использует арифметические операции для сложения, вычитания или сравнения чисел, элементы математической логики позволяют составить сложные высказывания, дать отрицание или вычислить конечный результат.
Логические операции для формализации и простоты записываются формулами, привычными для нас в арифметике. Свойства булевой алгебры дают возможность записывать уравнения и вычислять неизвестные. обычно записывают с помощью таблицы истинности. Её столбцы определяют элементы вычислений и операцию, которая над ними производится, а строки показывают результат вычислений.
Основные логические действия
Самыми распространенными в булевой алгебре операциями являются отрицание (НЕ) и логические И и ИЛИ. Так можно описать практически все действия в алгебре суждений. Изучим подробнее каждую из трех операций.
Отрицание (не) применяется только к одному элементу (операнду). Поэтому операцию отрицания называют унарной. Для записи понятия «не А» используют такие символы: ¬A, A¯¯¯ или!A. В табличной форме это выглядит так:
Для функции отрицания характерно такое утверждение: если А истинно, то Б - ложно. Например, Луна вращается вокруг Земли - истина; Земля вращается вокруг Луны - ложь.
Логические умножение и сложение
Логическое И называют операцией конъюнкции. Что это значит? Во-первых, что применить ее можно к двум операндам, т. е. И - бинарная операция. Во-вторых, что только в случае истинности обоих операндов (и А, и Б) истинно и само выражение. Пословица «Терпение и труд все перетрут» предполагает, что только оба фактора помогут человеку справиться со сложностями.
Для записи используются символы: A∧Б, A⋅Б или A&&Б.
Конъюнкция аналогична умножению в арифметике. Иногда так и говорят - логическое умножение. Если перемножить элементы таблицы по строкам, мы получим результат, аналогичный логическому размышлению.
Дизъюнкцией называют операцию логического ИЛИ. Она принимает значение истинности тогда, когда хотя бы одно из (или А, или Б). Записывается это так: A∨Б, A+Б или A||Б. Таблицы истинности для этих операций такие:
Дизъюнкция подобна арифметическому сложению. Операция логического сложения имеет только одно ограничение: 1+1=1. Но мы же помним, что в цифровом формате математическая логика ограничена 0 и 1 (где 1 - истина, 0 - ложь). Например, утверждение «в музее можно увидеть шедевр или встретить интересного собеседника» означает, что можно посмотреть произведения искусства, а можно познакомиться с интересным человеком. В то же время, не исключен вариант одновременного свершения обоих событий.
Функции и законы
Итак, мы уже знаем, какие логические операции использует булева алгебра. Функции описывают все свойства элементов математической логики и позволяют упрощать сложные составные условия задач. Самым понятным и простым кажется свойство отказа от производных операций. Под производными понимаются исключающее ИЛИ, импликация и эквивалентность. Поскольку мы ознакомились только с основными операциями, то и свойства рассмотрим тоже только их.
Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли. Формулой это запишется так:
(A∧Б)∧В=A∧(Б∧В)=A∧Б∧В,
(A∨Б)∨В=A∨(Б∨В)=A∨Б∨В.
Как видим, это свойственно не только конъюнкции, но и дизъюнкции.
Коммутативность утверждает, что результат конъюнкции или дизъюнкции не зависит от того, какой элемент рассматривался вначале:
A∧Б=Б∧A; A∨Б=Б∨A.
Дистрибутивность позволяет раскрывать скобки в сложных логических выражениях. Правила схожи с раскрытием скобок при умножении и сложении в алгебре:
A∧(Б∨В)=A∧Б∨A∧В; A∨Б∧В=(A∨Б)∧(A∨В).
Свойства единицы и нуля , которые могут быть одним из операндов, также аналогичны алгебраическим умножению на ноль или единицу и сложению с единицей:
A∧0=0,A∧1=A; A∨0=A,A∨1=1.
Идемпотентность говорит нам о том, что если относительно двух равных операндов результат операции оказывается аналогичным, то можно «выбросить» лишние усложняющие ход рассуждений операнды. И конъюнкция, и дизъюнкция являются идемпотентными операциями.
Б∧Б=Б; Б∨Б=Б.
Поглощение также позволяет нам упрощать уравнения. Поглощение утверждает, что когда к выражению с одним операндом применяется другая операция с этим же элементом, результатом оказывается операнд из поглощающей операции.
A∧Б∨Б=Б; (A∨Б)∧Б=Б.
Последовательность операций
Последовательность операций имеет немаловажное значение. Собственно, как и для алгебры, существует приоритетность функций, которые использует булева алгебра. Формулы могут упрощаться только при условии соблюдения значимости операций. Ранжируя от самых значимых до незначительных, получим такую последовательность:
1. Отрицание.
2. Конъюнкция.
3. Дизъюнкция, исключающее ИЛИ.
4. Импликация, эквивалентность.
Как видим, только отрицание и конъюнкция не имеют равных приоритетов. А приоритет дизъюнкции и исключающего ИЛИ равны, также как и приоритеты импликации и эквивалентности.
Функции импликации и эквивалентности
Как мы уже говорили, помимо основных логических операций математическая логика и теория алгоритмов использует производные. Чаще всего применяются импликация и эквивалентность.
Импликация, или логическое следование - это высказывание, в котором одно действие является условием, а другое - следствием его выполнения. Иными словами, это предложение с предлогами «если... то». «Любишь кататься, люби и саночки возить». Т. е. для катания необходимо затянуть санки на горку. Если же нет желания съехать с горы, то и санки таскать не приходится. Записывается это так: A→Б или A⇒Б.
Эквивалентность предполагает, что результирующее действие наступает только в том случае, когда истиной являются оба операнда. Например, ночь сменяется днем тогда (и только тогда), когда солнце встает из-за горизонта. На языке математической логики это утверждение записывается так: A≡Б, A⇔Б, A==Б.
Другие законы булевой алгебры
Алгебра суждений развивается, и многие заинтересовавшиеся ученые сформулировали новые законы. Наиболее известными считаются постулаты шотландского математика О. де Моргана. Он заметил и дал определение таким свойствам, как тесное отрицание, дополнение и двойное отрицание.
Тесное отрицание предполагает, что перед скобкой нет ни одного отрицания: не (А или Б)= не А или НЕ Б.
Когда операнд отрицается, независимо от своего значения, говорят о дополнении :
Б∧¬Б=0; Б∨¬Б=1.
И, наконец, двойное отрицание само себя компенсирует. Т.е. перед операндом либо исчезает отрицание, либо остается только одно.
Как решать тесты
Математическая логика подразумевает упрощение заданных уравнений. Так же, как и в алгебре, необходимо сначала максимально облегчить условие (избавиться от сложных вводных и операций с ними), а затем приступить к поиску верного ответа.
Что же сделать для упрощения? Преобразовать все производные операции в простые. Затем раскрыть все скобки (или наоборот, вынести за скобки, чтобы сократить этот элемент). Следующим действием должно стать применение свойств булевой алгебры на практике (поглощение, свойства нуля и единицы и т. д).
В конечном итоге уравнение должно состоять из минимального количества неизвестных, объединенных простыми операциями. Легче всего искать решение, если добиться большого количества тесных отрицаний. Тогда ответ всплывет как бы сам собой.
Введение
Учебные вопросы:
Понятия и определения математической логики.
Основные операции алгебры высказываний.
Законы и следствия булевой алгебры.
Заключение
Введение
Теоретической основой построения ЭВМ служат специальные математические дисциплины. Одной из них является алгебра логики, или булева алгебра (Дж. Буль - английский математик XIX в., основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их проектирования и оптимизации.
1. Понятия и определения математической логики.
Логика - наука, изучающая законы и формы мышления; учение о способах рассуждений и доказательств.
Математическая логика (теоретическая логика, символическая логика) - раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен». Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика - вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков)». Это определение соответствует определению С. К. Клини: математическая логика - это «логика, развиваемая с помощью математических методов». Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы». Все эти определения не противоречат, а дополняют друг друга.
Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие - нет.
Математическая логика изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода , с использованием языка математики.
Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Основными формами абстрактного мышления являются понятия, суждения и умозаключения.
Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов. Понятия в языке выражаются словами.
Объем понятия - множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.
Выделяют следующие отношения понятий по объему:
тождество или совпадение объемов, означающее, что объем одного понятия равен объему другого понятия;
подчинение или включение объемов: объем одного из понятий полностью включен в объем другого;
исключение объемов - случай, в котором нет ни одного признака, который бы находился в двух объемах;
пересечение или частичное совпадение объемов;
соподчинение объемов - случай, когда объемы двух понятий, исключающие друг друга, входят в объем третьего.
Суждение - это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.
Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, мы по определенным правилам вывода получаем суждение-заключение.
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами.
Алгебра логики (алгебра высказываний, булева алгебра 1 ) - раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается (т. н. бинарная или двоичная логика, в отличие от, например, троичной логики), что высказывания могут быть только истинными или ложными.
Примеры алгебр: алгебра натуральных чисел, алгебра рациональных чисел, алгебра многочленов, алгебра векторов, алгебра матриц, алгебра множеств и т.д. Объектами алгебры логики или булевой алгебры являются высказывания.
Высказывание - это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.
Всякое высказывание или истинно , или ложно ; быть одновременно и тем и другим оно не может.
В естественном языке высказывания выражаются повествовательными предложениями. Восклицательные и вопросительные предложения высказываниями не являются.
Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства.
Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.
Высказывание, состоящее из простых высказываний, называются составным (сложным).
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = {Аристотель - основоположник логики},
В = {На яблонях растут бананы}.
Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: «Сумма углов треугольника равна 180 градусов» устанавливается геометрией, причем - в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным.
Истинному высказыванию ставится в соответствие 1, ложному - 0. Таким образом, А = 1, В = 0.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт - истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
