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

2. Основы математической логики 2.1 Логика высказываний. Основные понятия и определения. Основными понятиями математической логики, с которыми мы будем постоянно оперировать, являются логические высказывания, высказывательные формы (или пропозициональные формулы), предикаты и кванторы. Высказывание - это предложение, которое либо истинно, либо ложно. Например, высказывание "Москва - столица России" является истинным, а "Волга впадает в Балтийское море" - ложным. Не всякое предложение является высказыванием. Логическими высказываниями являются утвердительные предложения, относительно которых можно говорить об истинности или ложности. Вопросительные и повелительные предложения не являются логическими высказываниями. Если предложение истинно, то его значение истинности равно 1, если ложно - то 0. По аналогии с элементарной алгеброй, где любое число является константой, высказывание является логической константой, величина которой равна 1 или 0.Предложение "х2 = 4" не является высказыванием, для того, чтобы имело смысл говорить об его истинности или ложности, необходимы допол­нительные сведения, в частности, какое число обозначено буквой "х", т.к. она может не обозначать конкретного числа, - а быть переменной, т.е. представлять элементы некоторого множества, например (-2. О, 2, 4).Каждому значению переменной соответствует либо истинное, либо ложное высказывание; например высказывания (-2)2 = 4, 22 =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 - последующий). Из определения импликации следует, что :1. Импликация с ложным антецедентом всегда истинна.2. Импликация с истинным консеквентом всегда истинна.3. Импликация ложна тогда и только тогда, когда ее антецендент истинный, а консеквент ложный.Принятое определение импликации соответствует употреблению союза "если... то" в предложении "Если будет хорошая погода, то я приду к тебе в гости", которое вы расцените как ложь в том случае, когда пого­да хорошая, а приятель к вам не придет.Вместе с тем определение импликации вынуждает считать истинным предложения как "Если 2х2=4, то Москва столица России"; "Если 2х2=5, то я самая красивая девушка России". Это связано с тем, что определениями логических операций смысл составляющих высказываний не учитывается, они рассматриваются как объекты, обладающие единственным свойством - быть истинными либо ложными.Рис. 2.9 диаграма Венна (импликация)^ Эквиваленция или равнозначность Эквивалвниией высказываний А и В называется высказывание, обозначаемое символом А  В (или ,), которое истинно тогда и только тогда, когда значения истинности высказываний А и В совпадают. (см. таблицу).Логическая операция, называемая эквивалентностью, соответствует союзу "тогда и только тогда, когда" и читается "А эквивалентно В", "Для того, чтобы А необходимо и достаточно, чтобы В".Когда мы говорим "А только тогда, когда В" то имеем в виду, что оба предложения А и В одновременно истинны, либо одновременно ложны. Например, говоря: "Я поеду в Ленинград тогда и только тогда, когда ты поедешь в Киев", мы утверждаем, что-либо произойдет и то и другое, либо ни того, ни другого. Можно доказать используя таблицу истинности, что для любых высказываний А и В высказывание (А  В) = 1 тогда и только тогда, когда (А  В) = 1 и (В  А) = 1.Это утверждение используется при доказательстве теорем вида А  В. Одним из способов доказательства истинности высказывания А  В является доказательство истинности высказывания А  В (необходимость) и истинности высказывания В  А (достаточность).Высказывания А и В называются равносильными., если (А  В) = 1 говорят, что формулы F1 и F2 равносильны, если их эквиваленция F1  F2 - тавтология (тождественно истинное высказывание). ^ Рис. 2.10 Диаграмма Венна (эквиваленция)Запись F1  F2 читается : "формула F1 равносильна формуле F2"А  В  (А  В)  (В  А)Равносильность есть отношение между формулами (также как равенст­во отношение между числами, параллельность - отношение между прямыми). Отношение равносильности обладает следующими свойствами:а) рефлективности F  Fб) симметричности: если F1 F2 то F2 F1в) транзитивности: если F1F2и F2 F3, то F1 F3Таким образом, в математической логике для записи более сложных высказываний используются следующие логические операции над простыми высказываниями:  НЕ & И  ИЛИ  влечет  совпадает.Логическое выражение служит для задания вычислительного процесса нахождения логического значения, подобно тому, как в математике арифметическое выражение служит для задания правил вычисления некоторого числового значения. Напомним, что логическое выражение может иметь только одно из двух возможных значений true (1) или false (0).Все рассмотренные логические операции иллюстрируются в сводной таблице ##, где булевские числа true и false заменены 1 и 0 соответственно.Порядок старшинства логических операций следующий: , &, , , .Для изменения порядка выполнения логических операций используются круглые скобки. В первую очередь выполняются операции в скобках, затем все остальные логические операции в порядке старшинства слева направо.^ 2.5 Вопросы для самопроверки. 1. В данных составных предложениях выделите составляющие их элементарные предложения и логические связки:а) диагонали ромба взаимно перпендикулярны и делят его углы пополам;б) треугольник является равносторонним тогда и только тогда, когда все его углы конгруэнтны.2. Определите значение истинности высказываний A, B, C, D, если:а) А  (2 * 2) = 4 – истинное высказывание;б) В  (2 * 2) = 4 – ложно;в) С  (2 * 2) = 5 – истинно;г) В  (2 * 2) = 5 – ложно;3. Изобразите на координатной плоскости множество точек, коор­динаты которых обращают следующие высказывательные формы в истинные высказывания :а) (х > 0)  (у > 0), б) (х > 0)  (у г) (х = 0)  (у = 0), д) (х = 0)  (у = 0), е) (х > 0)  (у > 0)ж) (х > 0)  (у = 0), з) (х > 0) (у 4. Сформулируйте и запишите в вида конъюнкции или дизъюнкции условие истинности каждого предложения :а) ab  0, б) ab = 0, в) а2 + b2 = 0, г) а / b = 0, д) | а | > 2, е) | а | 5. Следующие предложения запишите без знака отрицания :6. Определите значения истинности следующих высказываний :а) если 12 делится на 6, то 12 делится на 3;б) если 11 делится на 6, то 11 делится на 3;в) если 15 делится на 6, то 15 делится на 3;г) если 15 делится на 3. то 15 делится на 6;д) если Париж расположен на Темзе, то белые медведи живут в Африке;е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3;ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3;з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.7. Пусть через А обозначено высказывание "9 делится на З", а через В - высказывание "10 делится на З". Определите значения истин­ности следующих высказываний:; ; ; ; ; ; ; ; ; ; .8. Определите значение истинности высказываний A, B, C, D в предложениях, а, б, д, е из которых истинны, а в, г, ж, з – ложны:а) Если 4 нечетное число, то А;б) Если В, то 4 нечетное число;в) Если 4 четное число, то С;г) Если D, то 4 нечетное число;д) А  (2 е) В  (2 > 3);ж) С  (2 з) D  (2 > 3).9. Придумайте по два примера : а) истинной импликации с истинным антецедентом; б) истинной импликации с ложным консеквентом; в) ложной импликации; г) истинной эквивалентности; д) ложной эквива­лентности.10. Сформулируйте в виде импликации: "Диагонали ромба взаимно перпендикулярны", "Во всяком треугольнике сумма внутренних углов равна 180°".11. Найдется ли такой день недели, когда: а) утверждение "Если сегодня понедельник, то завтра пятница" истинно; б) "Если сегодня понедельник, то завтра вторник" ложно.12. Известно, что если число делится на 6, оно делится на 3 и 2. Сформулируйте это в виде импликации.