Математический анализ логики. Раздел I

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

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

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

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

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

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

Отрицание

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

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

В языках формальных теорий отрицание называется особая унарная пропозициональная связка, используемая для образования из одной формулы другой, более сложной. Для обозначений отрицание обычно используются символы «отрицание», «-» или «-- 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), называется орто-отрицание Если в соответствующем исчислении принимается аксиома дистрибутивности для конъюнкции и дизъюнкции, то орто-отрицание называется отрицание Буля, или классическим отрицанием.

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

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

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

Конъюнкция

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

Дизъюнкция

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

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

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

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

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

Импликация

Импликация двух логических высказываний 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 Гёделъ доказал невозможность полной аксиоматизации достаточно развитых научных теорий (напр., арифметики натуральных чисел), что свидетельствовало об ограниченности аксиоматического метода. Основные принципы аксиоматические методы были подвергнуты критике сторонниками интуиционизма и конструктивного направления.

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

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

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

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

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

Тема № 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». В классической логике высказываний формула -А истинна тогда и только тогда, когда формула А ложна.

Фактически указанное выше традиционное понимание внешнего (пропозиционального) отрицания может быть выражено через систему следующих требований: (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 - разобщение, обособление), в широком смысле - сложное высказывание, образованное из двух или более предложений с помощью союза «или», выражающего альтернативность, или выбор.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

Будет посвящён основам математической логики, которая представляет собой не только отдельный раздел математики, но и имеет огромное значение при изучении всей вышки (да и не только вышки) . «Существует и единственно», «из этого следует это», «необходимое условие», «достаточность», «тогда и только тогда» – знакомые обороты, не правда ли? И это не просто «дежурные» штампы, которыми можно пренебречь – это устойчивые выражения, обладающие строгим смыслом , с которым мы и познакомимся в данной статье. Кроме того, материал будет полезен начинающим изучать непосредственно математическую логику – я рассмотрю её базу: высказывания и действия над ними, формулы, основные законы + некоторые практические задачи. И, конечно же, вы узнаете очень важное, а местами и весьма забавное отличие матлогики от нашей «обычной» логики. Начинаем закладывать фундамент:

Высказывания и высказывательные формы

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

– данная запись (не путать с модулем !) говорит нам о том, что высказывание истинно ;
– а эта запись – о том, что высказывание ложно .

Например:

– черепахи не летают;
– Луна квадратная;
– дважды два будет два;
– пять больше, чем три.

Совершенно понятно, что высказывания и истинны : ,
а высказывания и – ложны :

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

Вы не подскажете, как пройти в библиотеку ?
Пойдём в баню!

Очевидно, что здесь не идёт речи об истине или лжи. Как не идёт о них речи и в случае неопределённости либо неполной информации:

Завтра Петя сдаст экзамен – даже если он всё выучил, то не факт, что сдаст; и наоборот – если ничего не знает, то может и сдаст «на шару».

…да ладно, Петь, не переживай – сдашь =)

– а тут мы не знаем, чему равно «эн», поэтому это тоже не высказывание.

Однако последнее предложение можно доопределить до высказывания, а точнее, до высказывательной формы , указав дополнительную информацию об «эн». Как правило, высказывательные формы записываются с так называемыми кванторами . Их два:

– квантор общности (перевёрнутая буква A – от англ. All) понимается и читается как «для всех», «для любого (ой) (ых) »;

– квантор существования (развёрнутая буква E – от англ. Exist) понимается и читается как «существует».

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

– а вот это высказывательная форма уже истинна , как истинно и, например, такое утверждение:
…ну а что, разве существует натуральное число, которое меньше, чем –10?

Предостерегаю вас от опрометчивого использования данного квантора, ибо «для любого» может на поверку оказаться вовсе и «не для любого».

Внимание! Если вам что-то не понятно в обозначениях, пожалуйста, вернитесь к уроку о множествах .

– существует натуральное число , которое больше двух. Истина …и, главное, не поспоришь =)

– Ложь

Нередко кванторы «работают в одной упряжке»:

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

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

1) Существование объекта, удовлетворяющего определённым критериям. В этой части обосновывается сам факт его существования.

2) Единственность данного объекта. Этот пункт доказывается, как правило, методом от противного , т.е. предполагается, что существует 2-й объект с точно такими же характеристиками и далее это предположение опровергается.

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

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

Кстати, а что такое вообще теорема? Логическую суть этого страшного слова мы узнаем очень скоро….

Логические операции (действия над высказываниями)

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

отрицание высказывания;

конъюнкция или логическое умножение высказываний;

дизъюнкция или логическое сложение высказываний.

По порядку:

1) Отрицание высказывания

НЕ и символ

Отрицанием высказывания называется высказывание (читается «не а») , которое ложно , если истинно, и истинно – если ложно:

Так, например, высказывание – черепахи не летают истинно: ,
а его отрицание – черепахи летают если хорошенько пнуть – ложно: ;

высказывание – дважды два будет два ложно: ,
а его отрицание – неверно, что дважды два будет два – истинно: .

Кстати, не нужно смеяться над примером с черепахами;) садисты

Удачной физической моделью данной операции является обычная лампочка и выключатель:

свет включен – логическая единица или истина,
свет выключили – логический ноль или ложь.

2) Конъюнкция (логическое умножение высказываний)

Данной операции соответствует логическая связка И и символ либо

Конъюнкцией (читается «а и бэ») , которое истинно в том и только том случае, когда истинны оба высказывания и :

Данная операция тоже встречается сплошь и рядом. Вернёмся к нашему герою с первой парты: предположим, что Петя получает допуск к экзамену по высшей математике, если сдаёт курсовую работу и зачёт по теме. Рассмотрим следующие высказывания:
– Петя сдал курсовую работу ;
– Петя сдал зачёт .

Заметьте, что в отличие от формулировки «Петя завтра сдаст» здесь уже в любой момент времени можно сказать, истина это или ложь.

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

И очень своевременно пришёл мне в голову отличный математический пример: знак системы соединяет входящие в неё уравнения/неравенства как раз по правилу И . Так, например, запись двух линейных уравнений в систему подразумевает то, что мы должны найти ТАКИЕ корни (если они существуют) , которые удовлетворяют и первому и второму уравнению.

Рассматриваемая логическая операция распространяется и на большее количество высказываний. Условно говоря, если в системе 5 уравнений, то её корни (в случае их существования) должны удовлетворять и 1-му и 2-му и 3-му и 4-му и 5-му уравнению данной системы.

И в заключение пункта вновь обратимся к доморощенной электротехнике: конъюнктивное правило хорошо моделирует выключатель в комнате и рубильник на электрическом щитке в подъезде (последовательное подключение). Рассмотрим высказывания:

– выключатель в комнате включен ;

– рубильник в подъезде включен .

Наверное, все уже поняли, что конъюнкция читается самым что ни на есть естественным образом:
– выключатель в комнате включен и рубильник в подъезде включен.

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

Давайте присоединим ещё одно высказывание:
– рубильник на подстанции включен .

Аналогично: конъюнкция будет истинна тогда и только тогда, когда . Здесь, к слову, уже будет 7 различных вариантов разрыва цепи.

3) Дизъюнкция (логическое сложение высказываний)

Этой операции соответствует логическая связка ИЛИ и символ

Дизъюнкцией высказываний и называют высказывание (читается «а или бэ») , которое ложно в том и только том случае, когда ложны оба высказывания и :

Предположим, что в экзаменационном билете по высшей математике 2 вопроса и студент сдаёт экзамен, если ответит хотя бы на один вопрос. Рассмотрим следующие высказывания:
– Петя ответил на 1-й вопрос ;
– Петя ответил на 2-й вопрос .

Дизъюнктивная запись читается просто и понятно: Петя ответил на 1-й или 2-й вопрос и подразумевает три истинных исхода (см. таблицу) . При этом экзамен Пётр не сдаст в единственном случае – если «запорет» оба вопроса:

Следует отметить, что союз «или» мы очень часто понимаем как «исключающее или», и, более того – его зачастую так и нужно понимать! Из той же фразы о сдаче экзамена человек, скорее всего, сделает вывод, что Петя ответил только на 1-й или только на 2-й вопрос. Однако рассматриваемое ИЛИ – это не обывательское «или».

Операция логического сложения также применима для трёх и бОльшего количества высказываний. Некоторые лояльные преподаватели задают 10-15 вопросов и ставят экзамен, если студент хоть что-то знает =) Иными словами, логическое ИЛИ скрывает за собой связку «хотя бы на один» (и она вовсе не означает, что СТРОГО на один!).

Ну и давайте отвлечёмся от бытового электричества: подавляющее большинство сайтов Интернета расположены на профессиональных серверах, которые снабжаются, как правило, двумя блоками питания. В электротехнике это называется параллельным подключением, которое как раз и моделирует правило ИЛИ – сервер работает, если исправен хотя бы один блок питания. Оборудование, кстати, поддерживает «горячую» замену, т.е. сгоревший БП можно заменить, не выключая сервер. Такая же история с жёсткими дисками – они дублируются в так называемом RAID-массиве , и более того, сам Дата-центр, где находятся серверы, обычно запитывается двумя независимыми электролиниями + дизель-генератор на всякий случай. Эти меры позволяют обеспечить максимальный аптайм сайтов.

И коль скоро речь зашла о компьютерах, то они… базируются на рассмотренных логических операциях! Это кажется невероятным, но задумаемся – а что вообще могут «понимать» эти «железки»? А понимать они могут следующее:

в проводе есть ток – это логическая единица ;
провод обесточен – это логический ноль .

Именно данный факт первопричина того, что в основе измерения объёма информации лежит степень двойки:
и т.д.

Простейшим «компьютером» является… обычный выключатель – он хранит информацию в 1 бит (истину или ложь в указанном выше смысле). Центральный же процессор современного компьютера насчитывает сотни миллионов (!) транзисторов, и самое сложное программное обеспечение, самая «навороченная игра» раскладывается на множество нулей и единиц, которые обрабатываются с помощью элементарных логических операций!

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

Импликация и логическое следствие.
Необходимое условие. Достаточное условие

До боли знакомые обороты: «следовательно», «из этого следует это», «если, то» и т.п.

Импликацией высказываний (посылка) и (следствие) называют высказывание , которое ложно в единственном случае – когда истинно, а – ложно:

Фундаментальный смысл операции таков (читаем и просматриваем таблицу сверху вниз) :

из истины может следовать только истина и не может следовать ложь ;

изо лжи может следовать всё, что угодно (две нижние строчки) , при этом:

истинность посылки является достаточным условием для истинности заключения ,

а истинность заключения – является необходимым условием для истинности посылки .

Разбираемся на конкретном примере:

Составим импликацию высказываний – идёт дождь и – на улице сыро :

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

Если же дождя нет , то на улице может быть как сухо :

так и сыро :
(например, по причине того, что растаял снег) .

А теперь ВДУМЫВАЕМСЯ в эти «штампованные» слова необходимость и достаточность :

Дождь является достаточным условием для того, чтобы на улице было сыро, и с другой стороны, сырость на улице необходима дляпредположения о том, что прошёл дождь (ибо если сухо – то дождя точно не было) .

Обратная же импликация нелегальна: – сырости на улице ещё не достаточно для обоснования факта дождя, и, кроме того, дождь ведь не является НЕОБХОДИМОЙ причиной сырости (т.к., например, может пройти и растаять град) .

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

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

– Чтобы научиться выполнять арифметические действия достаточно окончить 9 классов . Но это не является условием необходимым – считать может научить и бабушка, причём ещё в детском саду.

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

– Для допуска к экзамену по высшей математике Пете необходимо отчитаться по курсовой работе . Но этого не достаточно – потому что ещё нужно сдать зачёт.

– Для того чтобы вся группа получила зачёт достаточно занести преподавателю ящик коньяка . И здесь, как нетрудно предположить, отпадает необходимость что-либо учить =) Но, обратите внимание, подготовка вовсе не возбраняется;)

Бывают ли условия необходимые и в то же время достаточные? Конечно! И очень скоро мы до них доберёмся. А сейчас об одном важном принципе матлогики:

Математическая логика формальна

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

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

– если Луна квадратная, то ;
– если пингвины ходят в валенках, то черепахи носят шлёпанцы .

А что? – по таблице оба высказывания истинны!

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

И ещё один очень важный момент : импликацию часто обозначают значком (тоже читается «следовательно», «из этого следует это» ), который мы также используем в ходе решения задач, доказательств теорем и т.д. И здесь речь идёт о совпадении обозначений – то, что мы используем в «обычных» математических выкладках, строго говоря, не является импликацией. В чём отличие? Когда мы решаем задачу и пишем, что («из а следует бэ») , то полагаем высказывание заведомо истинным , и более того, выводим из него другую истину . В математической логике это называется логическим следствием . Обычно следствие подлежит обоснованию, и поэтому при оформлении работ всегда старайтесь пояснять, какие аксиомы, теоремы, решённые задачи и т.д. вы использовали для того или иного вывода.

Теорема по своей сути тоже представляет собой логическое следствие: её условие опирается на истинные посылки (аксиомы, ранее доказанные теоремы и т.д.) . Доказательство же устанавливает истинность следствия , причём в этом процессе не могут использоваться ложные рассуждения.

Недоказанная теорема называется гипотезой , и варианта тут два: либо она выводит из истины истину и представляет собой теорему, либо гипотеза невернА, т.е. из множества истинных посылок следует «не бэ»: . В случае опровержения получается тривиальный вывод наподобие «гипотеза Ивана Петрова неверная» , но и это, бывает, дорогого стОит – дерзайте , уважаемые читатели!

Рассмотрим в качестве примера, конечно, не мегатеорему, но утверждение, которое требует пусть простого, но обоснования. Хотя и его не будет =) =):

– число делится на 4 ;
– число делится на 2 .

Очевидно, что следствие истинно , то есть из того, что число делится на 4, следует и его делимость на 2. И, соответственно, противоположное заключение – есть ложь:

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

Для логических следствий также в ходу понятия необходимости и достаточности , скопирую пару строк сверху:

истинность посылки – это достаточное условие для истинности заключения ,

истинность заключения – это необходимое условие для истинности посылки .

В нашем случае:

Делимость числа на 4 является достаточным условием для того, чтобы оно делилось на 2. И с другой стороны, делимость числа на 2 является необходимым условием делимости на 4.

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

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

Особенность эквиваленции состоит в том, что имеет место либо и то и другое , либо ничего , например:

Петя занимается штангой тогда и только тогда, когда Маша танцует на столе

Это значит, что либо Петя занимается штангой и Маша танцует на столе, либо они оба лежат на диване Пётр, ты заслужил! =) Такие вот дружные Петя и Маша. Теперь вроде бы похожая фраза без «тогда и только тогда»:

Петя занимается штангой, когда Маша танцует на столе

Но смысл несколько поменялся: здесь можно предположить, что Петя, бывает, тягает штангу и без Маши, и другой стороны, Маше «до лампочки», качается ли во время её танца Петя.

Вот в чём сила необходимого и достаточного условия! – оно объединяет и дисциплинирует =)

…хотел я для прикола распределить роли наоборот, но затем передумал… всё-таки нельзя такое пропагандировать =)

К слову, о дисциплине – рациональный подход как раз и предполагает необходимость и достаточность – когда человек для достижения какой-либо цели делает ровно столько, сколько нужно, и не больше. Это, конечно, бывает скучно в обычной жизни, но всячески приветствуется в математических рассуждениях, которые нас уже заждались:

Треугольник является равносторонним тогда и только тогда, когда у него равные углы

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

Данный пункт – это собственно и есть теорема Пифагора, формулировка которой нам знакома ещё со школы: «Если треугольник прямоугольный, то ».

2) На втором шаге обосновывается достаточность :
– здесь надо доказать, что справедливость равенства достаточна для того, чтобы треугольник был прямоугольным.

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

Связей по схеме «тогда и только тогда» в математике очень много, и я только что привёл стандартную схему их доказательства. И, конечно же, всегда анализируйте, что означают «необходимо»

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

Кроме того, я открою вам секрет успешного изучения математической логики;)

Введение

Учебные вопросы:

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

Основные операции алгебры высказываний.

Законы и следствия булевой алгебры.

Заключение

Введение

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

1. Понятия и определения математической логики.

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

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

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

Математическая логика изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода , с использованием языка математики.

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

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

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

Выделяют следующие отношения понятий по объему:

тождество или совпадение объемов, означающее, что объем одного понятия равен объему другого понятия;

подчинение или включение объемов: объем одного из понятий полностью включен в объем другого;

исключение объемов - случай, в котором нет ни одного признака, который бы находился в двух объемах;

пересечение или частичное совпадение объемов;

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

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

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

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

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

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

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

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

В естественном языке высказывания выражаются повествовательными предложениями. Восклицательные и вопросительные предложения высказываниями не являются.

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

Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.

Высказывание, состоящее из простых высказываний, называются составным (сложным).

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:

А = {Аристотель - основоположник логики},

В = {На яблонях растут бананы}.

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: «Сумма углов треугольника равна 180 градусов» устанавливается геометрией, причем - в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным.

Истинному высказыванию ставится в соответствие 1, ложному - 0. Таким образом, А = 1, В = 0.

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

Введение

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

БУЛЬ или БУЛ, а также БУУЛ, Джордж (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.

Математический анализ логики. Раздел I

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

Высказывания и высказывательные формы

Логические операции (действия над высказываниями)

1) Отрицание высказывания

2) Конъюнкция (логическое умножение высказываний)

3) Дизъюнкция (логическое сложение высказываний)

Импликация и логическое следствие. Необходимое условие. Достаточное условие

1. Понятия и определения математической логики.

Импликация и логическое следствие.
Необходимое условие. Достаточное условие