Математическая логика глубина вхождения. Булева алгебра. Алгебра логики. Элементы математической логики. Понятия и определения математической логики

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра: «ФИЛОСОФИЯ»


По дисциплине: «ЛОГИКА»

Тема № 31: «Математическая логика: предмет, структура и основные принципы операций»


Выполнил:

студент 1 курса

дневного факультета ИТ-7

шифр зачетки 120177ИТ

Прытков Юрий Сергеевич

Проверил:

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

Блажко Николай Ильич


Москва - 2012 г.



Введение

Математическая логика

Предмет математической логики

Основные принципы операций

Отрицание

Конъюнкция

Дизъюнкция

Импликация

Эквивалентность

Кванторное высказывание

Кванторное с квантором всеобщности

Кванторное с квантором существования

Аксиоматический метод

Заключение


Введение


Логика возникла в культуре Древней Греции. Первое дошедшее до нас сочинение по логике - «Аналитики» Аристотеля (384-322 гг. до н.э.). Формальная логика просуществовала без серьёзных изменений более двадцати столетий. БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) - английский математик, который считается основоположником математической логики.

Развитие математики выявило недостаточность Аристотелевой логики и потребовало дальнейшего её развития. Независимо развивалась буддистская логика, но достоянием европейской науки она стала недавно, поэтому математическая логика берет начало из логики Аристотеля. Математическая логика является наукой о законах математического мышления. Предметом математической логики являются математические теории в целом, которые изучаются с помощью математических языков. При этом в первую очередь интересуются вопросами непротиворечивости математических теорий, их развязности и полноты.

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


Математическая логика


В аксиоматическом построении математической теории предварительно выбирается некоторая система неопределяемых понятий и отношения между ними. Эти понятия и отношения называются основными. Далее без доказательства принимаются основные положения рассматриваемой теории - аксиомы. Всё дальнейшее содержание теории выводится логически из аксиом. Впервые аксиоматическое построение математической теории было предпринято Евклидом в построении геометрии. Изложение этой теории в Началах не безупречно. Евклид здесь пытается дать определение исходных понятий (точки, прямой, плоскости). В доказательстве теорем используются нигде явно не сформулированные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость, хотя истинность всех положений теории не вызывает сомнений.

Отметим, что такой подход к аксиоматическому построению теории оставался единственным до XIX века. Большую роль в изменении такого подхода сыграли работы Н. И. Лобачевского (1792-1856). Лобачевский впервые в явном виде высказал убеждения в невозможности доказательства пятого постулата Евклида и подкрепил это убеждение созданием новой геометрии. Позже немецкий математик Ф. Клейн (1849-1925) доказал непротиворечивость геометрии Лобачевского, чем фактически была доказана и невозможность доказательства пятого постулата Евклида. Так возникли и были решены в работах Н. И. Лобачевского и Ф. Клейна впервые в истории математики проблемы невозможности доказательства и непротиворечивости в аксиоматической теории. Непротиворечивость аксиоматической теории является одним из основных требований, предъявляемых к системе аксиом данной теории. Она означает, что из данной системы аксиом нельзя логическим путём вывести два противоречивых друг другу утверждения.

Доказательство непротиворечивости аксиоматических теорий можно осуществить различными методами. Одним из них является МЕТОД МОДЕЛИРОВАНИЯ или ИНТЕРПРЕТАЦИЙ. Здесь в качестве основных понятий и отношений выбираются элементы некоторого множества и отношения между ними, а затем проверяется, будут ли выполняться для выбранных понятий и отношений аксиомы данной теории, то есть строится модель для данной теории. Так, аналитическая геометрия является арифметической интерпретацией геометрии Евклида. Ясно, что метод моделирования сводит вопрос о непротиворечивости одной теории к проблеме непротиворечивости другой теории. Большинство интерпретаций для математических теорий (и, в частности, для арифметики) строится на базе теории множеств. Однако в конце XIX века в теории множеств были обнаружены противоречия (парадоксы теории множеств). Ярким примером такого парадокса является парадокс Б. Рассела. Разобьем все мыслимые множества на два класса. Назовём множество нормальным, если оно не содержит себя в качестве своего элемента и ненормальным в противном случае. Например, множество всех книг - нормальное множество, а множество всех мыслимых вещей - ненормальное множество. Пусть L - множество всех нормальных множеств. К какому классу относится множество L? Если L - нормальное множество, то L Î L, т.е. содержится в классе нормальных множеств, но тогда оно содержит себя в качестве своего элемента, и поэтому ненормально. Если L - ненормальное множество, то L Ï L, т.е. не содержится среди нормальных множеств, но тогда L не содержит себя в качестве своего элемента, и потому оно нормально. Таким образом, понятие нормального множества приводит к противоречию.

Попытки устранить противоречия в теории множеств привели ЦЕРМЕЛО к необходимости построить аксиоматическую теорию множеств. Последующие видоизменения и усовершенствования этой теории привели к созданию современной теории множеств. Однако средства этой аксиоматической теории не позволяют доказать её непротиворечивость. Другие методы обоснования математики были развиты Д. ГИЛБЕРТОМ (1862-1943) и его школой. Они основываются на построении математических теорий как синтаксических теорий, в которых все аксиомы записываются формулами в некотором алфавите и точно указываются правила вывода одних формул из других, т.е. в теорию как составная часть входит математическая логика.

Таким образом, математическая теория, непротиворечивость которой требовалось доказать, стала предметом другой математической теории, которую Гилберт назвал МЕТАМАТЕМАТИКОЙ, или ТЕОРИЕЙ ДОКАЗАТЕЛЬСТВ. В связи с этим возникает задача построения синтаксической, т.е. формализованной аксиоматической теории самой математической логики. Выбирая по-разному системы аксиом и правила вывода одних формул из других, получают различные синтаксические логические теории. Каждую из них называют ЛОГИЧЕСКИМ ИСЧИСЛЕНИЕМ.


Предмет математической логики


Основная идея математической логики - формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания - математические. Таким образом, математическая логика, по-существу, - наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство"". Действительно, ``доказательные"" (иначе говоря, дедуктивные) рассуждения - единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим"" процессом переписывания текста (формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями. Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл"") и чётко разделяют синтаксис и семантику. Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система"". Мы будем использовать синоним этого термина - ``исчисление"" (используются ещё термины ``формальная теория"" и ``аксиоматика""). Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.

Формальная система определена, если:

Задан алфавит (множество символов, используемых для построения формул).

Выделено множество формул, называемых аксиомами. Это - стартовые точки в выводах.

Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.


Основные принципы операций


Отрицание


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

Внешнее отрицание (пропозициональное) служит для образования сложного высказывания из другого (не обязательно простого) высказывания. В нем утверждается отсутствие положения дел, описываемого в отрицаемом высказывании. Традиционно отрицательное высказывание считается истинным, если, и только если, отрицаемое высказывание ложно. В естественном языке отрицание обычно выражается оборотом «неверно, что», за которым следует отрицаемое высказывание.

В языках формальных теорий отрицание называется особая унарная пропозициональная связка, используемая для образования из одной формулы другой, более сложной. Для обозначений отрицание обычно используются символы «\отрицание», «-» или «- 1». В классической логике высказываний формула -А истинна тогда и только тогда, когда формула А ложна.

Однако в неклассической логике отрицание может не обладать всеми свойствами классического отрицания. В этой связи возникает вполне закономерный вопрос о минимальном наборе свойств, которому должна удовлетворять некоторая унарная операция, чтобы ее можно было считать отрицанием, а также о принципах классификации различных отрицаниях в неклассических формальных теориях (см.: Dunn J.M. and Hardegree G.M.Algebraic Methods in Philosophical Logic. Oxford, 2001).

Фактически указанное выше традиционное понимание внешнего (пропозиционального) отрицания может быть выражено через систему следующих требований: (I) Если А - истинно (ложно), то не-А - ложно (истинно); (II) Если не-А - истинно (ложно), то А - ложно (истинно). Формально требования (I) и (II) могут быть выражены через условие (1) А р-iB=>B (= -, А, называемое «конструктивная контрапозиция». Отрицание, удовлетворяющее условию (1), принято называть минимальным отрицанием. Однако оказывается, что условие (1) можно разложить на два более слабых условия: (2) А (= В=>-,В р-Аи(3)А(= - 1 - А, известных, соответственно, как «контрапозиция» и «введение двойного отрицания». В результате появляется возможность выявить подминимальное отрицание, удовлетворяющее условию (2), но не удовлетворяющее условию (3). Естественно сформулировать условие, обратное (3) и формализующее принцип «снятие двойного отрицания»: (4) -. - А = А. Минимальное отрицание (т.е. удовлетворяющее условию (1) или условиям (2) и (3) вместе), для которого выполняется условие (4), называется отрицание де Моргана. Минимальное отрицание, удовлетворяющее дополнительному свойству (5): Если А - В, то для любого С верно, что А р С («свойство абсурдности»), - называется интуиционистским отрицанием. Можно сформулировать принцип (6), двойственный принципу абсурдности: Если В |=Аи-S р А, то для любого С верно, что С р А. Удовлетворяющее этому принципу отрицания. представляет собой разновидность отрицания в паранепротиворечивой логике. Наконец, отрицание де Моргана (свойства (2), (3), (4)), для которого выполняется (5) или (6), называется орто-отрицание Если в соответствующем исчислении принимается аксиома дистрибутивности для конъюнкции и дизъюнкции, то орто-отрицание называется отрицание Буля, или классическим отрицанием.

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

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

Терминное отрицание используется для образования негативных терминов. Оно выражается через приставку «не» или близкие ей по смыслу («Все неспелые яблоки - зеленые»).


Конъюнкция


Конъюнкция двух логических высказываний - логическое высказывание, истинное только тогда, когда они одновременно истинны (от лат. conjunctio - союз, связь), в широком смысле - сложное высказывание, образованное с помощью союза «и». В принципе можно говорить о конъюнкции бесконечного числа высказываний (например, о конъюнкции всех истинных предложений математики). В логике конъюнкцией называют логическую связку (операцию, функцию; обозначают: &,); образованное с её помощью сложное высказывание истинно только при условии одинаковой истинности его составляющих. В классической логике высказываний конъюнкция вместе с отрицанием составляют функционально-полную систему пропозициональных связок. Это означает, что через них можно определить любую другую пропозициональную связку. Одним из свойств конъюнкции является коммутативность (т. е. эквивалентность А & В и В & А). Однако, иногда, говорят о некоммутативной, т. е. упорядоченной конъюнкции (примером высказывания с такой конъюнкции может служить: «Ямщик свистнул, и лошади поскакали»).


Дизъюнкция


Дизъюнкция двух логических высказываний - логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно

(от лат. disjunctio - разобщение, обособление), в широком смысле - сложное высказывание, образованное из двух или более предложений с помощью союза «или», выражающего альтернативность, или выбор.

В символической логике дизъюнкцией называют логическую связку (операцию, функцию), образующую из предложений А и В сложное высказывание, обозначаемое обычно как А V В, которое является истинным при истинности по крайней мере одного из двух дизъюнктивных членов: <#"justify">Импликация


Импликация двух логических высказываний A и B - логическое высказывание, ложное только тогда, когда B ложно, а A истинно (от лат. implicatio - сплетение, от implico - тесно связываю) - логическая связка, соответствующая грамматической конструкции «если.., то...», с помощью которой из двух простых высказываний образуется сложное высказывание. В импликативном высказывании различают антецедент (основание) - высказывание, идущее после слова «если», и консеквент (следствие) - высказывание, идущее за словом «то». Импликативное высказывание представляет в языке логики условное высказывание обычного языка. Последнее играет особую роль, как в повседневных, так и в научных рассуждениях, основной его функцией является обоснование одного путем ссылки на нечто другое.

Выражаемую условным высказыванием связь обосновывающего и обосновываемого трудно охарактеризовать в общем виде, и только иногда природа ее относительно ясна. Эта связь может быть, в частности, связью логического следования, имеющей место между посылками и заключением правильного умозаключения («Если все живые многоклеточные существа смертны и медуза является таким существом, то она смертна»). Связь может представлять собой закон природы («Если тело подвергнуть трению, оно начнет нагреваться») или причинную связь («Если Луна в новолуние находится в узле своей орбиты, наступает солнечное затмение»). Рассматриваемая связь может иметь также характер социальной закономерности, правила, традиции и т.п. («Если меняется экономика, меняется и политика», «Если обещание дано, оно должно быть выполнено»).

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

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

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

Материальная импликация - одна из основных связок классической логики. Определяется она таким образом: импликация ложна только в случае истинности антецедента и ложности консеквента и истинна во всех остальных случаях. Условное высказывание «Если А, то В» предполагает некоторую реальную связь между тем, о чем говорится в А и В; выражение «А материально имплицирует В» такой связи не предполагает.

Строгая импликация определяется через модальное понятие (логической) невозможности: «А строго имплицирует В» означает «Невозможно, чтобы А было истинно, а В ложно».

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


Эквивалентность


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

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

Рассмотрение классов эквивалентности в качестве новых объектов представляет собой один из основных способов порождения (введения) абстрактных понятий в логико-математических (и вообще естественно-научных) теориях. Так, считая эквивалентными дроби a/b и c/d с целыми числителями и знаменателями, если ad=bc, вводят в рассмотрение рациональные числа как классы эквивалентных дробей; считая эквивалентными множества, между которыми можно установить взаимно-однозначное соответствие, вводят понятие мощности (кардинального числа) множества (как класс эквивалентных между собой множеств); считая эквивалентными два куска вещества, вступающие в равных условиях в одинаковые химических реакции, приходят к абстрактному понятию химического состава и т.п.

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


Кванторное высказывание


Кванторное с квантором всеобщности.

Кванторное логическое высказывание с квантором всеобщности ("xA(x)) - логическое высказывание, истинное только тогда, когда для каждого объекта x из заданной совокупности высказывание A(x) истинно.

Кванторное с квантором существования.

Кванторное логическое высказывание с квантором существования ($xA(x)) - логическое высказывание, истинное только тогда, когда в заданной совокупности существует объект x, такой, что высказывание A(x) истинно.


Структура математической логики


Раздел «математическая логика» состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка). Аксиоматический метод построения - первый шаг на пути к формализации теории. Большинство задач, рассматриваемых в математической логике, состоит в доказательстве некоторых утверждений. Математическая логика имеет много разветвлений. Она применяет табличное построение логики высказываний, использует специальный язык символов и формулы логики высказываний.


Неформальный аксиоматический метод


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

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

Первоначальное, данное Евклидом, аксиоматическое построение геометрии отличалось дедуктивным характером изложения, при котором в основу клались определения (пояснения) и аксиомы (очевидные утверждения). Из них, опираясь на здравый смысл и очевидность, выводились следствия. При этом в выводе неявно иногда использовались не зафиксированные в аксиомах предположения геометрия, характера, особенно относящиеся к движению в пространстве и взаимному расположению прямых и точек. Впоследствии были выявлены геометрия, понятия и регламентирующие их употребление аксиомы, неявно используемые Евклидом и его последователями. При этом возникал вопрос: действительно ли выявлены все аксиомы. Руководящий принцип для решения этого вопроса сформулировал Д. Гильберт (D. Hilbert): "Следует добиться того, чтобы с равным успехом можно было говорить вместо точек, прямых и плоскостей о столах, стульях и пивных кружках". Если доказательство не теряет доказательной силы после такой замены, то действительно все используемые в этом доказательстве специальные предположения зафиксированы в аксиомах. Достигаемая при таком подходе степень формализации представляет собой уровень формализации, характерный для неформального аксиоматического метода. Эталоном здесь может служить классический труд Д. Гильберта "Основания геометрии" .

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

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

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


Аксиоматический метод


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

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


Заключение


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


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

математическая логика высказывание конъюнкция

Интернет-ресурс: #"justify">1.


Репетиторство

Нужна помощь по изучению какой-либы темы?

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

Одно из названий современной логики, пришедшей во втор. пол. 19 нач. 20 в. на смену традиционной логике. В качестве др. названия современного этапа в развитии науки логики используется также термин символическая логика. Определение… … Философская энциклопедия

математическая логика - ЛОГИКА СИМВОЛИЧЕСКАЯ, математическая логика, теоретическая логика область логики, в которой логические выводы исследуются посредством логических исчислений на основе строгого символического языка. Термин «Л. с.» был, по видимому, впервые… … Энциклопедия эпистемологии и философии науки

МАТЕМАТИЧЕСКАЯ ЛОГИКА - Ее еще называют символической логикой. М. л. это та же самая Аристотелева силлогистическая логика, но только громоздкие словесные выводы заменены в ней математической символикой. Этим достигается, во первых, краткость, во вторых, ясность, в… … Энциклопедия культурологии

МАТЕМАТИЧЕСКАЯ ЛОГИКА - МАТЕМАТИЧЕСКАЯ логика, дедуктивная логика, использующая математические методы исследования способов рассуждений (выводов); математическая теория дедуктивных способов рассуждений … Современная энциклопедия

МАТЕМАТИЧЕСКАЯ ЛОГИКА - дедуктивная логика, включающая математические методы исследования способов рассуждений (выводов); математическая теория дедуктивных способов рассуждений. Математической логикой называют также логику, которой пользуются в математике … Большой Энциклопедический словарь

МАТЕМАТИЧЕСКАЯ ЛОГИКА - (символическая логика), аналитический раздел логики, результат применения математических методов к проблемам классической логики. Рассматривает понятия, которые могут быть истинными или ложными, связь между понятиями и оперирование ими, включая… … Научно-технический энциклопедический словарь

МАТЕМАТИЧЕСКАЯ ЛОГИКА - один из ведущих разделов современной логики и математики. Сформировался в 19 20 ст. как реализация идеи о возможности записать все исходные допущения на языке знаков, аналогичных математическим и тем самым заменить рассуждения вычислениями.… … Новейший философский словарь

математическая логика - сущ., кол во синонимов: 1 логистика (9) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

математическая логика - — Тематики электросвязь, основные понятия EN mathematical logic … Справочник технического переводчика

МАТЕМАТИЧЕСКАЯ ЛОГИКА - теоретическая логика, символическая логика, раздел математики, посвященный изучению математич. доказательств и вопросов оснований математики. Исторический очерк. Идея построения универсального языка для всей математики и формализации на базе… … Математическая энциклопедия

Книги

  • Математическая логика , Ершов Юрий Леонидович, Палютин Евгений Андреевич. В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории… Купить за 1447 грн (только Украина)
  • Математическая логика , Ершов Ю.Л.. В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории…

«Если все вороны черные, то все нечерные предметы – не вороны». Это высказывание несомненно истинно, и, чтобы утверждать это, не нужно быть знатоком птиц. Точно так же не нужно быть специалистом в теории чисел, чтобы сказать, что если все совершенные числа четны, то все нечетные числа несовершенны. Мы привели примеры утверждений, истинных независимо от смысла входящих в них понятий (вороны, черные, совершенные, четные) – истинных уже в силу самой своей формы. Изучение такого рода утверждений входит в задачу логики. Более общо: логика изучает правильные способы рассуждений – такие способы рассуждений, которые приводят к верным результатам в тех случаях, когда верны исходные посылки.

Предметом математической логики служат в основном рассуждения. При их изучении она пользуется математическими методами. Разъясним сказанное.

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

«Книга философии – это то, что всегда раскрыто перед нашими глазами, но так как она написана иными буквами, чем буквы нашего алфавита, то она не может быть прочитана всеми буквами этой книги являются треугольники, круги, шары, конусы, пирамиды и другие математические фигуры, очень пригодные для чтения ее». Г. Галилей

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

Как устроена математическая теория? Она содержит какие-то утверждения. Некоторые из них принимаются без доказательств, другие удается доказать (в этом случае утверждения называют теоремами). Значение слов «утверждение» и «доказательство» в повседневной практике весьма расплывчато. Поэтому если мы хотим строить математическую модель, то первым делом нужно уточнить эти понятия, т.е. построить их формальные аналоги в нашей модели. Для этого математические логики придумали специальные формальные языки, предназначенные для записи математических утверждений. Утверждения, записанные на формальных языках, называют формулами, чтобы отличить их от предложений естественных языков. Построив формальный язык, мы получаем возможность записывать некоторые математические утверждения в виде формул. Этого, разумеется, еще не достаточно. Нам нужно уметь записывать формально не только утверждения, но и доказательства. Для этого математические логики придумали формальный аналог понятия «доказательство» - понятие вывода (доказательства, записанного на формальном языке). Формальным аналогом понятия «теорема» является понятие «выводимая формула» (т.е. формула, имеющая вывод). Формальный язык вместе с правилами построения выводов называется формальной системой.

Какие требования естественно предъявлять к формальной системе? Мы хотим, чтобы она была как можно более похожа на «живую», неформальную математику. Для этого нужно, чтобы все интересующие нас содержательные утверждения (или, по крайней мере, большая их часть) могли быть «переведены на формальный язык», т.е. записаны в виде формул этой системы. Кроме того, нужно, чтобы неформальные доказательства можно было перевести в выводы соответствующих формул.

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

Основным предметом математической логики, таким образом, является построение и изучение формальных систем. Центральным результатом здесь является доказанная в 1931 г. австрийским математиком К. Геделем теорема о неполноте, утверждающая, что для любой «достаточно разумной» формальной системы существуют неразрешимые в ней предложения, т.е. такие формулы , что ни сама формула , ни ее отрицание не имеют вывода. Если отождествить формальную систему с соответствующей областью математики, то можно сказать, что в любой «достаточно разумной» области математики есть утверждения, которые нельзя ни доказать, ни опровергнуть. Мы не можем здесь точно сказать, что именно требуется от «достаточно разумной» формальной системы; отметим лишь, что большинство формальных систем (в том числе формальная арифметика и аксиоматическая теория множеств) удовлетворяют этим требованиям. На примере теоремы о неполноте мы видим, какую пользу приносит построение формальной системы: мы получаем возможность доказать, что какие-то утверждения недоказуемы!

Изучение формальных систем привело к возникновению многих важных направлений в современной математической логике. Назовем некоторые из них. Теория моделей исследует вопрос о том, как можно придать «смысл» выражениям формальных языков и что при этом получается. Теория доказательств изучает свойства выводов в формальных системах. Важнейшим разделом логики, который сейчас уже можно рассматривать как самостоятельную дисциплину, является теория алгоритмов.

Многие знаки, придуманные логиками для построения формальных систем, постепенно вошли в общее употребление. К ним относятся логические связки (конъюнкция, «и»), (дизъюнкция, «или»), (импликация, «если... то...»), (отрицание, «неверно, что») и так называемые кванторы (всеобщности, «для всех») и (существования, «существует»). Смысл логических связок, помимо указанных в скобках названий, разъясняется так называемыми таблицами истинности. Эти таблицы показывают, будет ли сложное утверждение, составленное с помощью логических связок из простых, истинно (И) или ложно (Л) в зависимости от истинности его составных частей. Приведем их.

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

Составив ее, мы увидим, что это утверждение (шестой столбец) всегда истинно, независимо от истинности утверждений и (например, утверждение «

которые получаются, если подставить вместо утверждение « – ворона», а вместо - « – черная» или вместо - « – совершенные», а вместо - « – четные».

Введение

Тема контрольной работы «Математическая логика».

БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который считается основоположником математической логики.

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

Формализация рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.

Интенсивно математическая логика начала развиваться в 50-е годы XX века в связи с бурным развитием цифровой техники.

1. Элементы математической логика

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

Высказывание – есть предложение, которое может быть либо истинно, либо ложно.

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

Предикат – логическая функция от п переменных, которая принимает значения истинности или ложности.

Исчисление предикатов – раздел математической логики, объектом которого является дальнейшее изучение и обобщение исчисления высказываний.

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

1.1 Основные понятия алгебры логики

Алгебра логики – раздел математической логики, изучающий логические операции над высказываниями.

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

1 (истина) 0 (ложь).

Каждой логической операции соответствует функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0.

Такие функции называются логическими или булевыми, или функциями алгебры логики (ФАЛ). При этом логическая (булева) переменная x может принимать только два значения:

.

Таким образом,

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

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

(&, ·), ~, – (), и имеет место таблица истинности:
x~y
0 0 0 0 1 1 1
0 1 0 1 1 1 0
1 0 0 1 0 0 0
1 1 1 1 1 0 1

Это табличный способ задания ФАЛ. Наряду с ними применяется задание функций с помощью формул в языке, содержащем переменные x , y , …, z (возможно индексированные) и символы некоторых конкретных функций – аналитический способ задания ФАЛ.

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

~, –. Формулы этого языка определяются следующим образом:

1) все переменные есть формулы;

2) если P и Q – формулы, то

P ~ Q , - фор-мулы.

Например, выражение

~ - формула. Если переменным x , y , z придать значения из двоичного набора 0, 1 и провести вычисления в соответствии с операциями, указанными в формуле, то получим значение 0 или 1.

Говорят, что формула реализует функцию. Так формула

~ реализует функцию h (x , y , z ):
x y z h (x, y, z )
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Пусть P и Q – формулы, которые реализуют функции f (x 1 , x 2 , …, x n ) и g (x 1 , x 2 , …, x n ). Формулы равны: P = Q , если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.

Приведем законы и тождества, определяющие операции

– и их связь с операциями , ~:

1. Идемпотентность конъюнкции и дизъюнкции:

.

2. Коммутативность конъюнкции и дизъюнкции:

.

3. Ассоциативность конъюнкции и дизъюнкции:

.

4. Дистрибутивность конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции:


.

5. Двойное отрицание:

.

6. Законы де Моргана:

=, =.

7. Склеивание:

.

8. Поглощение

.

9. Действия с константами 0 и 1.

современная математическая модель формальной логики как науки о правильном рассуждении. По меткому выражению русского логика Порецкого, математическая логика суть логика по предмету и математика - по методу решения своих проблем. Систематическая разработка математической логики началась с работ Больцано, Фреге, Рассела и Витгенштейна. Суть этой логики и рассмотрении большинства логических категорий (понятие, предикат, суждение, умозаключение, вывод, доказательство) как логических функций, областью значения которых являются истинностные значения. Как логические функции истолковываются и все логические операторы (термины «Все», «Существует», «Некоторые», «Один», «Ниодин», «и», «или», «если, то», «тождественно», «возможно», «необходимо» и т. д. и т. п.). Все логические функции задаются, в конечном счете, табличным способом с помощью всевозможных сочетаний введенного числа истинностных значений на «входе» и «выходе» этих функций. Так, например, логическое отношение «если, то...» моделируется с помощью функции =), называемой материальной импликацией.

Отличное определение

Неполное определение ↓

МАТЕМАТИЧЕСКАЯ ЛОГИКА

логика, развившаяся в точную науку, применяющую математич. методы, или, согласно П. С. Порецкому, логика по предмету, математика по методам. Идея построения М. л. высказывалась впервые Лейбницем. Но лишь в 19 в. в соч. Буля "Математический анализ логики" (G."Boole, "The mathematical analysis of logic", 1847) была начата систематич. разработка этой науки. Дальнейшее развитие М. л. в значит. мере стимулировалось потребностями математики, ставившей логич. проблемы, для решения к-рых старые средства классич. формальной логики были непригодны. Одной из этих проблем явилась проблема недоказуемости 5-го постулата Эвклида в геометрии. Эта проблема связана с аксиоматическим методом, являющимся наиболее распространенным способом логич. систематизации математики. Он требует точной формулировки основных, принимаемых без доказательства положений развертываемой теории – т.н. а к с и о м, из к-рых все дальнейшее ее содержание логически выводится. Математич. теории, развиваемые т.о., наз. а к с и о м а т и ч е с к и м и. Классич. прототипом такого построения математич. теории является эвклидово построение геометрии. В связи со всякой аксиоматич. теорией естественно возникает ряд логич. проблем. В частности, возникает проблема л о г и ч е с к о й н е з а в и с и м о с т и аксиом данной теории, состоящая в установлении того, что ни одна из аксиом теории не может быть чисто логически выведена из остальных аксиом. Для эвклидовой геометрии в течение двух тысячелетий оставался открытым вопрос о логич. независимости 5-го постулата Эвклида. Было предпринято много тщетных попыток вывести его из остальных аксиом эвклидовой геометрии, пока, наконец, в работах Н. И. Лобачевского не было впервые в явной форме высказано убеждение в невозможности осуществить такой вывод. Это убеждение было подкреплено Лобачевским построением новой геометрии, в корне отличной от эвклидовой. В геометрии Лобачевского, тщательно разработанной ее творцом, не обнаруживалось противоречий; это вселяло уверенность в том, что противоречия и вообще не могут возникнуть, как бы далеко ни было продвинуто выведение следствий из аксиом новой геометрии. Впоследствии нем. математиком Ф. Клейном было доказано, что п р о т и в о р е ч и я не могут возникнуть в геометрии Лобачевского, если они не могут возникнуть в эвклидовой г е о м е т р и и (см. Метод аксиоматический). Так возникли и были частично решены исторически первые проблемы "недоказуемости" и непротиворечивости в аксиоматич. теориях. Точная постановка таких проблем, их рассмотрение как проблем математических требуют уточнения понятия доказательства. Всякое математич. доказательство состоит в последовательном применении тех или иных логич. средств к исходным положениям. Но логич. средства не представляют собой чего-то абсолютного, раз навсегда установленного. Они вырабатывались многовековой человеческой практикой; "...практическая деятельность человека миллиарды раз должна была приводить сознание человека к повторению разных логических фигур, д а б ы эти фигуры м о г л и получить значение а к с и о м" (Ленин В. И., Соч., т. 38, с. 181–82). Человеческая практика является, однако, на каждом историч. этапе ограниченной, а объем ее все время растет. Логич. средства, удовлетворительно отражавшие человеческое мышление на данном этапе или в данной области, могут уже оказаться неподходящими на след. этапе или в др. области. Тогда в зависимости от изменения содержания рассматриваемого предмета изменяется и способ его рассмотрения – изменяются логич. средства. Это в особенности относится к математике с ее далеко идущими многостепенными абстракциями. Здесь бессмысленно говорить о логич. средствах как о чем-то данном в своей совокупности, как о чем-то абсолютном. Зато имеет смысл рассмотрение логич. средств, применяемых в той же или иной конкретной обстановке, встречающейся в математике. Их установление для к.-л. аксиоматич. теории и составляет искомое уточнение понятия доказательства для этой теории. Важность этого уточнения для развития математики выявилась в особенности за последнее время. Разрабатывая множеств теорию, ученые столкнулись с рядом трудных проблем, в частности с проблемой о мощности континуума, выдвинутой Г. Кантором (1883), к к-рой до 1939 не было найдено удовлетворит. подходов. Др. проблемы, столь же упорно не поддававшиеся решению, встретились в дескриптивной теории множеств, разрабатываемой сов. математиками. Постепенно выяснилось, что трудность этих проблем является логической, что она связана с неполной выявленностью применяемых логич. средств и аксиом и что единств. путем к ее преодолению является уточнение тех и других. Выяснилось, т.о., что разрешение этих задач требует привлечения М. л., к-рая, следовательно, является наукой, необходимой для развития математики. В наст. время надежды, возлагавшиеся на М. л. в связи с этими проблемами, уже оправдали себя. В отношении проблемы континуума очень существенный результат был получен К. Геделем (1939), доказавшим непротиворечивость обобщенной континуум-гипотезы Кантора с аксиомами теории множеств при условии, что эти последние непротиворечивы. В отношении же ряда трудных проблем дескриптивной теории множеств важные результаты получены П. С. Новиковым (1951). Уточнение понятий доказательства в аксиоматич. теории является важным этапом ее развития. Теории, прошедшие этот этап, т.е. аксиоматич. теории с установленными логич. средствами, называют д е д у к т и в н ы м и т е о р и я м и. Лишь для них допускают точную формулировку интересующие математиков проблемы доказуемости и непротиворечивости в аксиоматич. теориях. Для решения этих проблем в совр. М. л. применяется метод формализации доказательств. Идея метода формализации доказательств принадлежит нем. математику Д. Гильберту. Проведение этой идеи стало возможным благодаря предшествовавшей разработке М. л. Булем, Порецким, Шредером, Фреге, Пеано и др. В наст. время метод формализации доказательств является мощным орудием исследования в проблемах обоснования математики. Применение метода формализации бывает обычно связано с выделением логич. части рассматриваемой дедуктивной теории. Эта логич. часть, оформляемая, как и вся теория, в виде нек-рого исчисления, т.е. системы формализованных аксиом и формальных правил вывода, может быть рассматриваема как самостоятельное целое. Простейшим из логич. исчислений являются исчисления высказываний, классическое и конструктивное. Формальное различие двух исчислений высказываний отражает глубокое различие в их истолкованиях, касающееся смысла пропозициональных переменных и логич. связок (см. Интуиционизм, Исчисление задач, Логика высказываний). Наиболее широко используемым при построении дедуктивных математич. теорий является в наст. время классич. предикатов исчисление, представляющее собой развитие и уточнение классич. теории суждений Аристотеля и вместе с тем соответствующее теоретико-множеств. системе абстракций. Конструктивное исчисление предикатов относится к классич. исчислению предикатов так же, как конструктивное исчисление высказываний к классич. исчислению высказываний. Самое существенное из расхождений между этими двумя исчислениями предикатов связано с истолкованием в них частных, или экзистенциальных, суждений. В то время как в конструктивном исчислении предикатов такие суждения истолковываются как утверждения о возможности определ. конструкций и считаются установленными лишь при указании этих конструкций, в классич. исчислении предикатов экзистенциальные суждения обычно трактуются в отрыве от конструктивных возможностей как некие "чистые" утверждения о существовании (см. Конструктивное направление). Более удовлетворительное истолкование экзистен-циальных суждений классич. исчисления предикатов, увязывающее определ. образом это исчисление с конструктивным исчислением предикатов, было открыто А. Н. Колмогоровым в 1925. В математике логич. исчисления применяются в сочетании со специфич. аксиомами развертываемых дедуктивных теорий. Напр., теорию натуральных чисел можно строить, объединяя аксиомы Пеано для арифметики с исчислением предикатов (классическим или конструктивным). Применяемое при этом объединение логич. символики с математической не только позволяет оформлять математич. теории в виде исчислений, но и может являться ключом к уточнению смысла математич. предложений. В наст. время сов. математиком Н. А. Шаниным разработаны точные правила конструктивного истолкования математич. суждений, охватывающие широкие области математики. Применение этих правил становится возможным лишь после того, как рассматриваемое суждение записано на надлежащем точном логико-математич. языке. В результате применения правил истолкования может выявиться конструктивная задача, связываемая с данным суждением. Это, однако, происходит не всегда: не со всяким математич. предложением обязательно связывается конструктивная задача. С исчислениями связаны следующие понятия и идеи. Об исчислении говорят, что оно непротиворечиво, если в нем не выводима никакая формула вида U вместе с формулой U (где есть знак отрицания). Задача установления непротиворечивости применяемых в математике исчислений является одной из гл. задач М. л. В наст. время эта задача решена лишь в весьма огранич. объеме. Употребляются разл. понятия п о л н о т ы исчисления. Имея в виду охват той или иной содержательно определенной области математики, считают исчисление полным относительно этой области, если в нем выводима всякая формула, выражающая верное утверждение из этой области. Другое понятие полноты исчисления связано с требованием доставлять либо доказательство, либо опровержение для всякого предложения, формулируемого в исчислении. Первостепенное значение в связи с этими понятиями имеет теорема Геделя–Россера, утверждающая несовместимость требования полноты с требованиями непротиворечивости для весьма широкого класса исчислений. Согласно теореме Геделя–Россера, никакое непротиворечивое исчисление из этого класса не может быть полным относительно арифметики: для всякого такого исчисления может быть построено верное арифметич. утверждение, формализуемое, но не выводимое в этом исчислении (см. Метатеория). Эта теорема, не снижая значения М. л. как мощного организующего средства в науке, в корне убивает надежды на эту дисциплину как на нечто способное осуществить всеобщий охват математики в рамках одной дедуктивной теории. Надежды такого рода высказывались мн. учеными, в том числе Гильбертом – главным представителем формализма в математике – направления, пытавшегося свести всю математику к манипуляциям с формулами по определенным раз навсегда установленным правилам. Результат Геделя и Россера нанес этому направлению сокрушительный удар. В силу их теоремы, даже такая сравнительно элементарная часть математики, как арифметика натуральных чисел, не может быть охвачена одной дедуктивной теорией. М. л. органически связана с кибернетикой, в частности с теорией релейно-контактных схем и автоматов, машинной математикой и лингвистикой математической. Приложения М. л. к релейно-контактным схемам основаны на том, что всякая двухполюсная релейно- контактная схема в след. смысле м о д е л и р у е т нек-рую формулу U классич. исчисления высказываний. Если схема управляется n реле, то столько же различных пропозициональных переменных содержит U, и, если обозначить через bi, суждение "Реле номер i сработало", то цепь будет тогда и только тогда замкнута, когда будет верен результат подстановки суждений b1, ..., bn вместо соответствующих логич. переменных в U. Построение такой моделируемой формулы, описывающей "условия работы" схемы, оказывается особенно простым для т.н. ?-с х е м, получаемых исходя из элементарных одноконтактных цепей путем параллельных и последовательных соединений. Это связано с тем, что параллельное и последовательное соединения цепей моделируют, соответственно, дизъюнкцию и конъюнкцию суждений. Действительно, цепь, полученная путем параллельного (последовательного) соединения цепей Ц1 и Ц2, тогда и только тогда замкнута, когда замкнута цепь Ц1 или (и) замкнута цепь Ц2. Применение исчисления высказываний к релейно-контактным схемам открыло плодотворный подход к важным проблемам совр. техники. Вместе с тем эта связь теории с практикой привела к постановке и частичному решению мн. новых и трудных проблем М. л., к числу к-рых в первую очередь относится т.н. проблема м и н и м и з а ц и и, состоящая в разыскании эффективных методов нахождения простейшей формулы, равносильной данной формуле. Релейно-контактные схемы являются частным случаем управляющих схем, применяемых в совр. автоматах. Управляющие схемы иных типов, в частности, схемы из электронных ламп или полупроводниковых элементов, имеющие еще большее практич. значение, также могут быть разрабатываемы с помощью М. л., к-рая доставляет адекватные средства как для анализа, так и для синтеза таких схем. Язык М. л. оказался также применимым в теории программирования, создаваемой в наст. время в связи с развитием машинной математики. Наконец, созданный в М. л. аппарат исчислений оказался применимым в математической лингвистике, изучающей язык математич. методами. Одной из осн. проблем этой науки является точная формулировка правил грамматики рассматриваемого языка, т.е. точное определение того, что следует понимать под "грамматически правильной фразой этого языка". Как показал амер. ученый Хомский, есть все основания искать решение этой задачи в следующем виде: строится нек-рое исчисление, и грамматически правильными фразами объявляются выражения, составленные из знаков алфавита данного языка и выводимые в этом исчислении. Работы в этом направлении продолжаются. См. также Алгебра логики, Конструктивная логика, Логика комбинаторная, Логика классов, Логическое исчисление, Модальная логика и лит. при этих статьях. А. Марков. Москва.