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

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

Основными понятиями математической логики, с которыми мы будем постоянно оперировать, являются логические высказывания, высказывательные формы (или пропозициональные формулы), предикаты и кванторы. Высказывание - это предложение, которое либо истинно, либо ложно. Например, высказывание "Москва - столица России" является истинным, а "Волга впадает в Балтийское море" - ложным. Не всякое предложение является высказыванием. Логическими высказываниями являются утвердительные предложения, относительно которых можно говорить об истинности или ложности. Вопросительные и повелительные предложения не являются логическими высказываниями. Если предложение истинно, то его значение истинности равно 1, если ложно - то 0. По аналогии с элементарной алгеброй, где любое число является константой, высказывание является логической константой, величина которой равна 1 или 0.

Предложение "х² = 4" не является высказыванием, для того, чтобы имело смысл говорить об его истинности или ложности, необходимы допол­нительные сведения, в частности, какое число обозначено буквой "х", т.к. она может не обозначать конкретного числа, - а быть переменной, т.е. представлять элементы некоторого множества, например (-2. О, 2, 4).

Каждому значению переменной соответствует либо истинное, либо ложное высказывание; например высказывания (-2)² = 4, 2² =4 истинны, остальные ложны.

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

Аналогом ПФ в элементарной алгебре являются алгебраические формулы или арифметические выражения.

2.2 Предикаты и кванторы

Рассмотрим высказывательную форму cosх=1. Каждому значению "х" на множестве действительных чисел эта форма ставит в соответствие высказывание и, тем самым, одно из значений истинности {0,1}. Так значению х = 0, соответствует истинное высказывание cos0 = 1, при х = 2 соответствует истинное высказывание cos2 = 1, вообще всякому значению х кратному 2х соответствует истинное высказывание, а всем остальным значениям ложные высказывания. Т.о. данная высказывательная форма задает отображение множества R действитель­ных чисел на множество {1, 0} или {и, л}, иначе говоря, задает функцию с областью определения R и множеством значений {1, 0}.

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

Произвольный элемент взятый из области определения функции назы­вается аргументом и обозначается “х”. Правило соответствия обозначае­тся F, т.о. запись у=F(х) означает, что х - аргумент, у - функция, F - правило соответствия.

Функция, область определения которой задана множеством М, а все значения которой, принадлежат множеству {1, 0} называется предикатом.

Пример 1: Если переменная “х” в высказывательной форме "Река х впадает в Каспийское море" принимает значение из множества М названий всевозможных рек, то эта форма задает предикат.

Из высказывательных форм можно получать высказывания не только подстановкой вместо переменных их значений, но и с помощью специальных слов: "всякий" (а также его синонимов "любой", "каждый") и "су­ществует" ("некоторые", "по меньшей мере один") например из высказывательной формы: "Число х делится на 7" можно получить ложное высказывание “Всякое число х делится на 7” и истинное высказывание "Существует число х, которое делится на 7".

Выражение "для всякого х" называется кванторам общности по переменной х (вместо х может быть любая другая переменная) и запи­сывается  х (Ф (х)).

Выражение, "существует х, такое что..." называется квантором существования по переменной х и обозначается  х (Ф(х)), что означает существует значение "х" такое, что Ф(х) при этом значении - истинное высказывание. Переход от формы Ф(х) к высказыванию  х (Ф(х)) или  х (Ф(х)) называется операцией квантификацией формы Ф(х). Будем называть переменную "х" в Ф(х) после применения к ней операции квантификации связанной переменной. В отличие от связанных переменных, переменные в первоначальном смысле слова называются свободными переменными.

2.3 Булевы функции, булевы константы.

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

Булевы функции могут быть заданы специальными таблицами истин­ности или аналитически в виде специальных высказывательных форм, называемых иногда булевыми формами.

Выражения, содержащие одну или несколько переменных (аргумен­тов), соединенных знаками логических операций, называются логическим формами. Высказывания, не содержащие ни одной переменной, называются константами. В логике, в отличие от арифметики, только две константы 0 - false и 1- true.

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

Булевыми функциями, называются предикаты, все аргументы которых определены на множестве {0, 1}, интерпретируемые как {ложь, ис­тина}.

Можно сказать, что понятие булевой функции является частным случаем понятия предиката. Отличие состоит лишь в том, что у булевой функции четко фиксирована как область определения {0, 1}, так и область значений функции {0, 1}, в то время как у предиката четко фиксирована только одна область значений {0, 1}, в то время как область определения задана произвольным множеством.

В свою очередь понятие предиката является частным случаем понятия функции, отличие состоит в том, что у предиката четко фиксирована область значений {0, 1}, а у функции это может быть вся числовая ось.

2.4 Основные логические связи.

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

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

Отрицание (логическая связь "не")

Записывается Р=Ā или в виде P= ¬A (Читается "Р есть не А"). Отрицанием называется сложное логическое высказывание Р, которое истинно, если А ложно и наоборот. Эта логическая связь может быть проиллюстрирована табл. 3.1, в которой показаны значения истинности сложного высказывания Р в зависимости от значения истинности составляющего его простого высказывания А. Логический элемент «не» в схемах управления часто называется таблица 2.1 схемах управления, часто называется инвертором. Условное обозначение инвертора показано на рис. 2.1. Также ниже (рис. 2.2) приведена диаграмма Венна.

Табл. 2. 1

Рис. 2.1 Условное обозначение инвертора

Рис. 2.2

Рис. 2.3 Диаграмма Венна (отрицание)

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

Заметим, что последовательное выполнение двух операций отрицания Ā приводит к исходному значению А.

Конъюнкция

Р = А  В; Р = А & В. (Читается Р есть А и В). Конъюнкция - сложное логическое высказывание, которое истинно только в случае истинности всех составляющих высказываний, в противном случае ложно. Эта логическая связь проиллюстрирована табл. 2.2.

Табл. 2. 2

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

Рис. 2.4 Условное обозначение логического элемента "и"

Рис. 2.5 Диаграмма Венна (конъюнкция)

З

Рис. 3.1 Условное обозначение инвертора

аметим, что A  0 = 0; A  Ā = 0; A  1 = A.

Дизъюнкция

Р = А  В (читается Р есть А или В). Дизъюнкция - это сложное логическое высказывание, которое ложно только в случае ложности всех составляющих высказываний, в противном случае истинно (vel - или (лат.)).

Дизъюнкция проиллюстрирована табл. 2.3.

Табл. 2. 3

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

Рис. 2.6 Условное обозначение логического элемента "ИЛИ"

Рис. 2.7

Рис. 2.8 Диаграмма Венна (дизъюнкция)

Заметим, что A  1 = 1; A  Ā = 1.

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

Импликация.

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

1. Если число n делится на 4, то оно делится на 2.

2. Если Иванов увлечен математикой, то Петров ничем не интересуется.

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

соответствует смыслу союза, "если... то" в первом предложении. В импликации А  В первый член А называется антецедентом (от лат. antecedens - предшествующий), а второй член В - консеквентом (от лат. consequens - последующий). Из определения импликации следует, что :