Некоторые основные логические символы Формальная или символическая логика

Некоторые основные логические символы. Формальная, или символическая, логика.


 математика характерно широкое использование символики, которая, до сути, является аппаратом формальной логики. Формальная, или символическая, логика — это специальный метод познания структуры мышления. Такой разработанный аппарат используют везде. В математике многие важные положения удается записывать в виде символов. Запись логических рассуждений в символах придает доказательствам более краткий, простой вид. Формальная логика оперирует высказываниями (из них, кстати, состоит и наша речь). Высказыванием называют предложение, относительно которого имеет смысл утверждать, что оно истинно или ложно. Пример 1.3. „Москва — столица России**, „Петров И.И. — студент МГТУ ", х2+у2 = 1, х € R — высказывания; х2 -2х + + У2 — не является высказыванием. # Соединяя простые высказывания словами „и", „или", „не", „если ..., то", мы получаем более сложные высказывания, которые определяют нашу речь. В математике эти слова называют логическими связками, в формальной логике они соответствуют основным логическим символам, на которых мы кратко и остановимся. 1. Конъюнкцией pAq высказываний р и q называют высказывание, которое истинно тогда и только тогда, когда оба высказывания (и р, и q) истинны. Логический симвЪл конъюнкции А заменяет в речи союз „и". Конъюнкцию обозначают также р & q. 2. Дизъюнкцией pW q высказываний р и q называют высказывание, которое ложно в том и только в том случае, когда оба высказывания ложны, а истинно, когда хотя бы одно из них (р или q) истинно. Логический символ дизъюнкции V в речи заменяет слово „или". 3. Импликацией р => q высказываний р и q называют высказывание, которое ложно тогда и только тогда, когда р истинно, a q — ложно. Логический символ импликации => используют при указании на последствия некоторого факта. Он заменяет слова „если ..., то". Можно также читать „р влечет qu. 4. Логический символ эквиваленции & означает, что высказывание р q истинно тогда и только тогда, когда оба высказывания р и q истинны или оба высказывания ложны. Этот символ заменяет в речи слово „равносильно". 5. Отрицанием высказывания р называют высказывание —»р, которое истинно, если р ложно, и ложно, когда р истинно. Логический символ -» в речи заменяет слово „не". Для сокращения и уточнения записи высказываний вводят два знака V и 3, называемых соотвеНекоторые основные логические символы. Формальная, или символическая, логика. тственно кванторами общности и существования. Выражение „для всякого элемента х множества Еи записывают в виде Vs 6 Е. Эта запись означает, что утверждение, следующее за ней, будет выполнено для произвольного элемента множества Е. Запись V&i, «2» хп€Е означает: „каковы бы ни были элементы xi, 32, хп множества Еи. Выражение „существует по крайней мере один элемент множества Е, такой, что ..." заг писывают Зх £ Е: ... Все, что следует за этой записью, выпол- дается хотя бы для одного элемента множества Е. Наоборот, $х е Е: ... означает, что все следующее далее не выполняется ни для одного элемента из Е. Выражение „ существует один и только один элемент из Е, такой, что ...u записывают в виде Э!ж € Е: ... Запись Зх\} хз, хп € Е: ... означает: ясуществуют такие элементы х\у а?2» •••» я» множества Е, что ...ц. Введенными символами удобно пользоваться, например, при определении операций над множествами. Так, AUB :<*{х: (х € А) V (х € В)}, АПВ :*>{х: {х € А) Л (ж € В)}, А\В :*>{х: {х € А) Л (х g В)}, А :<${х: (ж €Й)Л(х£ Л)}, где символ означает эквивалентность по определению. Связь теории множеств и формальной логики достаточно широка. Исследованием этой связи впервые занимался английский математик Джордж Буль (1815-1864), работы которого положили начало одному из важнейших направлений современной алгебры, называемому булевой алгеброй. Ясно, что взятие дополнения тесно связано с отрицанием высказывания, операции объединены и пересечения множеств — с дизъюнкцией и конъюнкцией высказываний соответственно, включение подмножества в множество — с импликацией, а равенство множеств — с эквиваленцией высказываний. В силу этой связи с помощью теории множеств можно решать некоторые логические задачи. Пример 1.4. Рассмотрим набор высказываний: 1) животные, которых не видно в темноте, серы; 2) соседи не любят тех, кто не дает им спать; 3) кто кредко спит, громко храпит; 4) соседи любят животных, которых видно в темноте; 5) все слоны крепко спят; 6) кто громко храпит, не дает спать соседям. Эти высказывания можно перевести на язык теории множеств, если ввести следующие обозначения: А - множество тех, кто будит соседей; В - множество тех, кто крепко спит; С - множество тех, кто громко храпит; D - множество животных, которых видно в темноте; Е - множество слонов; F - множество тех, кого любят соседи; G - множество тех, кто серые. Высказывание 1) означает, что элементы, не лежащие в D) содержатся в G, т.е. 1) D С G. Остальные высказывания принимают вид: 2) Л С F; 3) £ С С; 4) D С F; 5) Е С В; б)ССЛ. Взяв дополнения множеств D и F, из 4) согласно принципу двойственности получим F С D и затем соединим все выскаг зывания в цепочку ECCCACFCDCG. Из этой цепочки (с учетом свойства транзитивности символа включения) следует, что ECGy т.е. все слоны серы. # Рассмотренные логические символы и кванторы существования и общности широко используют математики для записи предложений, в которых они, по сути, воплощают плоды своего творчества. Эти предложения представляют собой устанавливающие свойства математических объектов теоремы, леммы, утверждения и следствия из них, а также различные формулы. Однако следует отметить, что часть предложений приходится все же выражать словами. Любая теорема состоит, вообще говоря, в задании некоторого свойства Л, называемого условием, из которого выводят свойство Ву называемое заключением. Коротко теорему пА влечет Ви записывают в виде А В и говорят, что А является достаточным условием для Б, а Б — необходимым условием для А. Тогда обратная теорема имеет вид В А (возможна запись при помощи обратной импликации А <= В), но справедливость прямой теоремы еще не гарантирует справедливости обратной ей теоремы. Если справедливы данная тедрема и обратная ей, то свойства А я В эквивалентны, и такую теорему можно записать в виде А о В. Эта запись соответствует фразам: „Для того, чтобы Л, необходимо и достаточно, чтобы В", „А тогда и только тогда, когда Ви или „А, если и только если Ви. Ясно, что в этих фразах А и В можно поменять местами. Утверждение, противоположное утверждению А} записывают -^Л, что соответствует словам „не Аи. Если в символьную запись утверждения А входят кванторы 3, V и условие Р, то при построении символьной записи противоположного утверждения -*А квантор 3 заменяют на V, квантор V — на 3, а условие Р заменяют на условие -»Р. Пример 1.6. Рассмотрим утверждение Зх € Е: Р (существует элемент х множества Е, обладающий свойством Р) и построим его отрицание. Если это утверждение неверно, то указанного элемента не существует, т.е. для каждого х € Е свойство Р не выполняется, или -.(За: 6 Е: Р) = Vx € Е: -.Р. Теперь построим отрицание утверждения Vx 6 Е: Р (для каждого элемента х множества Е имеет место свойство Р). Если данное утверждение неверно, то свойство Р имеет место не для каждого элемента указанного множества, т.е. существует хотя бы один элемент х € Е, не обладающий этим свойством, или -.(УхбЕ: Р) = Зх€Я: -чР. # Доказательство предложения представляет собой проводимое по определенным правилам рассуждение, в котором для обоснования сформулированного предложения используют определения, аксиомы и ранее доказанные предложения. Примеры доказательств свойств абсолютных значений действительных чисел приведены доше (см. 1.3), а первого из соотношений свойства дистрибутивности операций объединения и пересечения и первого из законов де Моргана (1.7) — в 1.4. Одним из используемых приемов является метод доказательства от противного. Для доказательства таким методом теоремы А => В предполагают, что верно -«В. Если рассуждения приводят к тому, что при таком предположении условие А невыполнимо, т.е. возникает противоречие, то теорему считают доказанной. Пример 1.6. Используем метод доказательства от противного, чтобы убедиться в справедливости второго закона де Моргана (1.7) AC\B = AUB. Если это равенство верно, то каждый элемент х € А П В должен принадлежать и A U В, т.е. х € A U В. Предположим противное: s £ AUB. Тогда по принципу двойственности (см. 1.4) х € АПВ, т.е. х ^ АПВ, а это противоречит исходному условию х € А П В, что доказывает справедливость импликации высказываний х€ АГ\В=>хе лив. Наоборот, каждый элемент х 6 A U В должен принадлежать и Л Г) В, т.е. х € А О В. Снова предположим противное: х £ i АП В, т.е. х £ АП В, или (хбА)Л(хбВ). Тогда (х£А)Л Л (х £ В) и х £ AUB, а это опять противоречит принятому условию х £ A U В, что доказывает справедливость обратной импликации высказываний х€ АПВ«=х€ AUB. Некоторые основные логические символы. Формальная, или символическая, логика. В итоге справедливость второй формулы (1.7) доказана полностью. # При доказательстве предложений, справедливых для произвольного натурального числа п G N, иногда применяют метод математической индукции: непосредственной проверкой устанавливают справедливость предложения для нескольких первых значений п (n= 1, 2, ...), а затем предполагают, что оно верно для п = к} и если из этого предположения следует справедливость данного предложения для п = к -f 1, то его считают доказанным для всех п € N. Пример 1.7. Докажем справедливость формулы «П = «1 (1.8) для суммы первых п членов геометрической прогрессии 0|, a2 = aitf, a3 = alq2) an = aign_1 со знаменателем прогрессии q ^ 1. Ясно, что формула верна для п= 1 и п = 2. Предположим, что она верна и для п = к, т.е. Некоторые основные логические символы. Формальная, или символическая, логика. Если в (1.9) обозначить к +1 = п, то снова придем к (1.8), что доказывает справедливость этой формулы.