Математическая логика с примерами решения и образцами выполнения

Оглавление:

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

Алгебра высказываний

Под высказыванием понимаем всякое утверждение (повествовательное предложение), про которое всегда определенно и объективно можно сказать, является оно истинным или ложным. Например, «5-3 = 2» или «В неделе семь дней» — истинные высказывания, а «5 > 8» или «В русском языке 35 букв» — ложные высказывания. Синонимами слова «высказывания» можно считать: логическое высказывание, булевское выражение, суждение, утверждение и т.п. Фразы: «Ура!», «Который час?» — не являются высказываниями.

Если высказывание истинное, то ему предписывается значение «истина» (другие обозначения: «1», «ДА» , «И», «+», «true»). Ложному высказыванию предписывается значение «ложь» (другие обозначения: «О», «НЕТ», «Л», «-«, «false»). Совокупность возможных значений высказывания образует множество истинности {0,1} и {И,Л}.

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

Логические операции

Операции над высказываниями задают в виде таблиц, называемых таблицами истинности.

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

Для каждого высказывания А может быть сформировано новое высказывание Математическая логика отрицание высказывания А, которое истинно, когда А ложно, и ложно, когда А истинно. Символ соответствует логическому союзу «не». читается «не А» или «не верно, что А». Отрицание — одноместная (или унарная) операция. Последующие операции — двухместные (или бинарные). Например, если Математическая логика истинное высказывание, то ложное высказывание (отрицание А), или если в комнате холодно», в комнате не холодно». Отметим, что высказывание «в комнате жарко» не является отрицанием В.

Конъюнкция высказываний

Конъюнкцией высказываний А и В называется высказывание Математическая логика которое истинно только в том случае, когда и А, и В одновременно истинны. Выражение читается «А и В». Пример: пусть делится на делится на 4″. Тогда формула Математическая логика имеет смысл: «12 делится на 3 и на 4».

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

имеет значение «истина», если Математическая логика истинны. Во всех других случаях эта конъюнкция имеет значение «ложь». Пусть, например, отец старше сына Мурманск севернее Смоленска». Тогда высказывание Математическая логика («8=3 и отец старше сына, и

Мурманск севернее Смоленска») — ложное высказывание. В то время как Математическая логика и отец старше сына, и Мурманск севернее Смоленска» — истинное высказывание.

Дизъюнкция высказываний

Дизъюнкцией высказываний А и В называется высказывание Математическая логика которое ложно только тогда, когда и А, и В ложны одновременно. Дизъюнкция имеет значение «истина», если хотя бы одно из высказываний, входящее в дизъюнкцию, является истинным. Выражение Математическая логика читается «А или В». Пусть Тогда

Операцию дизъюнкции можно определить для нескольких высказываний как связку высказываний, объединенных союзом «или»,

В этом случае высказывание А истинно, если истинно хотя бы одно из высказываний, входящих в связку.

Импликация высказываний

Импликацией высказываний А и В называется высказывание Математическая логика которое ложно только в том случае, когда А — истинно, а В — ложно. Во всех других случаях импликация имеет значение «истина». Символ соответствует логическому союзу: «если А, то В». Например, А — «целое число делится на 4, то оно делится на 2». Для иллюстрации содержательного смысла импликации рассмотрим следующий пример: А Математическая логика «папа завтра получит премию», В «папа завтра купит сыну велосипед». Тогда импликация может быть сформулирована так: «если папа завтра получит премию, то купит сыну велосипед».

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

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

Эквивалентностью высказываний А и В называется высказывание Математическая логика которое истинно, когда высказывания и А, и В оба истинны или оба. ложны. Символ логической эквивалентности соответствует связке «тогда и только тогда». Пример. Пусть А Математическая логика «число З является четным», В «число является четным». Высказывание «число З является четным тогда и только тогда, когда -четное число» есть эквивалентность высказываний А и В. Эквивалентность высказываний может быть задана следующей таблицей истинности:

Замечание. Характерной особенностью операций над высказываниями является введение логических союзов с точно определенным смыслом, не допускающим никакой двусмысленности в толковании этих символов. Таким образом, математическая логика применима не для любых высказываний, а только для таких, которые допуск кают четкую оценку в двоичной системе «истина — ложь». Для преодоления такого рода ограничений в рамках нечеткой математики разрабатывается нечеткая логика.

Если в выражении встречаются различные логические операции, то в качестве естественного порядка (выполняемого поочередно слева направо) используется следующая последовательность: Математическая логика Это означает, что сначала выполняются операции отрицания, затем конъюнкции и т. д. Для нарушения порядка служат скобки. Рассмотрим пример. Пусть высказывания А и В имеют значения «истина», а высказывания С и Б — «ложь». Тогда формула Математическая логика имеет значение «ложь», т.к.:

Введя скобки, получим формулу Математическая логика которая уже имеет другое значение — «истина». Действительно:

Если в выражении присутствуют арифметические операции, операции сравнения и логические операции, то порядок старшинства операций следующий:

• сначала выполняются арифметические операции (порядок старшинства арифметических операций: первыми выполняются все операции умножения и деления, потом операции сложения и вычитания);
• затем — операции и операции сравнения (в том порядке, в каком они встречаются в выражении):
• наконец, логические операции, причем первой везде выполняется операция отрицания, затем конъюнкции, потом дизъюнкции и т. д.

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

Например, множество точек А, заштрихованное на рис. 1.16, может быть задано следующей формулой:

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

Булевы функции

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

выражает функцию от переменных А, В и С.

Такого рода функции называются булевыми, а их аргументы — булевыми переменными. Аргументы булевых функций могут представлять собой, сокращенные обозначения некоторых конкретных высказываний. Тогда функция обозначает сокращенную запись некоторого сложного высказывания. Например, Математическая логика делится на 3», С ? «Мурманск севернее Смоленска». В этом случае «если делится на 3 и Мурманск севернее Смоленска». Сравните с известной формулой физики Математическая логика где m — масса тела, а — его ускорение, а F — сила, вызвавшая это ускорение. Буквы в булевых функциях могут выступать в качестве переменных. Подставляя вместо них любые высказывания, можно по формуле вычислить соответствующее значение функции. Действительно, если в формуле Математическая логика «истина», Y — «ложь», Z — «истина», то — «истина». Если же Z будет иметь ложное значение, то поменяет значение на противоположное и будет «ложью».

Целый ряд булевых функций обладает тем свойством, что они принимают одни и те же значения при любых значениях истинности аргументов. Такие формулы называются тождественно истинными. Например, при любых X и Y истинны формулы Математическая логика Тождественно ложные функции при любых значениях аргументов имеют значение «ложь». Так формулы всегда имеют значение «ложь».

Наиболее важные тождественно истинные формулы получили название Основные законы математической логики.

Основные законы математической логики

1.Коммутативность

2.Ассоциативность

3.Дистрибутивность

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

5.Закон поглощения

6.Закон идемпотентности

8.Закон противоречия

9.Закон исключения третьего

10.Закон двойного отрицания

Пример:

Упростить выражение, используя тождественны преобразования

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

Основные методы доказательств

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

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

Метод цепочек импликаций

Метод цепочек импликаций состоит в том, что из посылки А страивается цепочка из Математическая логика -импликаций, последним высказыванием в которой является заключение теоремы В, т. е.

В основе этого метода лежит закон цепного высказывания или закон силлогизма Математическая логика

Метод от противного

Метод от противного. Используя этот метод, вместо доказательства прямого следствия «из А следует В» доказывают, что из «не В» следует «не А». Этот метод основан на законе контрапозиций, имеющем следующий вид:

Метод необходимого и достаточного

Метод необходимого и достаточного. Теорема формулируется так: «Чтобы имело место А, необходимо и достаточно выполнение В». Доказательство такого вида теоремы распадается на две части:

а) доказывается, что если имеет место А, то справедливо В (В необходимо для А);

б) если имеет место В, то имеет место и А (В достаточно для А).

Доказательство таким методом базируется на законе тавтологии:

Алгебра предикатов

Предикатом Математическая логика заданным на множествах

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

Рассмотрим примеры, Математическая логика одноместный предикат на множестве комплексных чисел, при этом, например, если истинное высказывание, а

положив Математическая логика получим «ложь». Выражение «X — брат Y» — двухместный предикат, заданный на множестве людей. Здесь термы X и Y указывают места, на которые нужна поставить имена двух людей, чтобы получить правильно построенное высказывание. Очевидно, что X — лицо мужского пола, а Y может выбираться из всего множества людей.

Всякий предикат Математическая логика определяет отношение R, такое, что тогда и только тогда, когда «истина». В этом случае говорят, что отношение R задается областью истинности предиката Математическая логика . Например, отношение «расстояние на плоскости между точками больше величины 1″ можно задать предикатом

Если в Математическая логика -местный предикат на место одного из термов подставить определенный элемент из соответствующего множества, то предикат станет местным. Заменив все термы на конкретные значения из предметной области предиката, получим 0 — местный предикат, т. е. высказывание. Например, «Х- брат Y» — двухместный предикат, «X — брат Маши» — одноместный предикат, «Саша — брат Маши» — высказывание.

Логические операции над предикатами

Отрицание предиката

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

Например, предикат « Математическая логика — четное число» есть отрицание предиката «— нечетное число» на множестве целых чисел.

Конъюнкция предикатов

Пусть на множествах Математическая логика заданы два — местных предиката и . Конъюнкцией этих предикатов называется предикат

который истинен для одних и тех же кортежей только тогда, когда оба предиката — и Математическая логика и истинны.

Например, конъюнкция предикатов Математическая логика где вещественные числа, определяет предикат «точки правой половины единичного круга» (см. рис. 1.17а).

Дизъюнкция предикатов

Дизъюнкция предикатов Математическая логика и есть новый предикат который имеет значение «ложь» для тех и только тех кортежей из для которых оба предиката — и и — имеют значение «ложь». На рис. 1.17 6 иллюстрируется дизъюнкция предиката Математическая логика (заштрихованная область).

Импликация предикатов

Импликация предикатов Математическая логика и есть новый предикат который имеет значение «ложь» для тех и только тех кортежей из для которых предикат имеет значение «истина», а предикат Математическая логика имеет значение «ложь».

Например, импликация « Математическая логика делится на 4″ —» » делится на 2″ есть предикат: «если делится на 4, то делится на 2″.

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

Эквивалентность предикатов Математическая логика и есть новый предикат который имеет значение «истина» для тех и только тех кортежей из для которых предикат и предикат имеют одинаковые значение или оба «истина» или оба «ложь». Два предиката, заданные на одних и тех же множествах, называются равносильными, если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью. Например, эквивалентность предикатов Математическая логика делится на 6» и делится на 2 и делится на 3» есть предикат «если делится на 6, то делится на 2 и на 3». Предикаты логически эквивалентны.

Наряду с логическими операциями важную роль играют операции, называемые кванторами. Квантор всеобщности есть операция, которая предикат Математическая логика превращает в высказывание: «все обладают свойством ». Знак квантора всеобщности Он заменяет фразы: «для всех», «каждый», «любой» и т.п. Обозначение Математическая логика читается так: «для всех таких, что Р от ». Например, вещественное число», есть предикат « — положительное число». Тогда есть высказывание «каждое число — положительно». Это ложное высказывание. Если же Математическая логика — любое натуральное число то есть выражение: «каждое натуральное число — положительно» — истинное высказывание. Квантор всеобщности есть обобщение серии конъюнкций единичных высказываний. Пусть М — множество очков, которое может выпасть при бросании игральной кости, т. е. Математическая логика предикат: «при бросании игральной кости один раз выпадает очков», где . Применение квантора всеобщности позволяет вместо сложного высказывания Математическая логика записать равносильное ему компактное высказывание : «при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел».

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

Квантор существования есть операция, которая предикат Математическая логика превращает в высказывание: «существует хотя бы один

из М, обладающий свойством Математическая логика ». Знак квантора существования Он заменяет фразы: «существует хотя бы один», «найдется», «некоторый» и т.п. Обозначение читается так: «существует хотя бы один Математическая логика такой, что Р от ». Например, — предикат: « — студент», где — элемент множества жителей Москвы. Тогда выражение есть высказывание «хотя бы один житель Москвы является студентом». Квантор существования есть обобщение серии дизъюнкций единичных высказываний. Если задано множество Математическая логика и на нем определен предикат

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

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

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

Рассмотрим пример. На множестве чисел задан двухместный предикат Математическая логика число делится на число ». Связывая одну переменную, можно получить следующие одноместные предикаты:

Математическая логика «каждое число делится на » — ложь;

Математическая логика «существует число, которое делится на » — истина;

Математическая логика «число делится на любое число» — ложь;

Математическая логика «существует число, на которое делится » — истина.

Связывая обе переменные данного предиката, получим высказывания:

Математическая логика «каждое число делится на любое число» -ложное высказывание,

Математическая логика «существует число, на которое делится любое число» — истина, т.к. такое число есть 1,

Математическая логика «существует число, которое делится на любое число» — ложное высказывание,

Математическая логика «существует число, которое делится на какое-нибудь число» — истинное высказывание.

Решение заданий и задач по предметам:

Дополнительные лекции по высшей математике: