АЛГЕБРА ЛОГИКИ Лекция 2
План: Высказывания и высказывательные формы. Логические операции. Формулы логики высказывания. Логическая равносильность. Логическое следование. Нормальные формы формул. Булевы функции. Предикаты.
Высказыванием называется любое повествовательное предложение, которому можно приписать истинностное значение (т.е. либо истина (И - 1), либо ложь (Л -0). Например: «Январь – зимний месяц» – И, «Земля имеет форму куба» – Л.
Предложения, которые содержат хотя бы одну переменную и становятся высказываниями при подстановке вместо всех переменных их значений, называются высказывательными формами. Например, «Утром я встретила соседей»; «Утром я встретила соседей из X квартиры»; «Утром я встретила соседей из 20 квартиры».
Преобразование высказывательных форм в высказывания может быть осуществлено употреблением слов «любой» («каждый», «всякий») или «существует» («некоторые», «по крайней мере один»). Например, «Студенты пришли на экзамен» – высказывательная форма; «Все студенты пришли на экзамен», «Каждый студенты на экзамене получил оценку» – высказывания.
Высказывание, представляющее собой одно утверждение (истинное или ложное), называется элементарным высказыванием. Высказывание, образованное из элементарных с помощью логических связок, называется составным (или сложным). Образование составного высказывания из элементарных называется логической операцией.
Отрицание Логическая операция, соответствующая логической связке «не» («Неверно, что») называется отрицанием. Отрицание высказывания X обозначается или ¬Х.
Конъюнкция Логическая операция, соответствующая союзу «и» (или близким по смыслу союзам «а» и «но»), называется конъюнкцией. В результате конъюнкции получается высказывание, истинное тогда и только тогда, когда оба элементарных высказывания X и У истинны.
Дизъюнкция Логическая операция, соответствующая союзу «или», называется дизъюнкцией. В результате этой операции образуется высказывание, ложное тогда и только тогда, когда оба составных высказывания ложны.
Союз «или» употребляется в смыслах: 1.Неразделительном. Например, в предложении «Для посещения врача надо взять талон или записаться по телефону». Понятно, что если вы одновременно возьмете талон и запишитесь, вас примут. 2.Разделительном. Например, «Сегодня меня пригласили в театр или в кино». Очевидно, что какое–то место останется не посещенным.
Дизъюнкция Дизъюнкция – это неразделительное «или».
Импликация Логическая операция, имеющая вид «если X, то Y», называется импликацией. Высказывание X именуется посылкой (или антецедентом – предшествующим по–латыни), Y – заключением (или консеквентом – последующим). В результате импликации получается высказывание, ложное тогда и только тогда, когда посылка истинна, а заключение ложно.
Импликация Логическими операциями никак не учитывается смысл высказываний; они рассматриваются как объекты, обладающие единственным свойством – быть истинными и ложными. Например, фраза «Если курение полезно, то крокодилы летают» считается истинной, хотя оба элементарных высказывания, ее составляющие, – ложны.
Эквиваленция Логическая операция, соответствующая сложному союзу «тогда и только тогда, когда», «в том и только в том случае», «если и только если», называется эквиваленцией. В результате этой операции образуется высказывание, истинное тогда и только тогда, когда оба составляющих его элементарных высказывания истинны или оба ложны.
Эквиваленция Психолог может оказывать квалифицированную помощь тогда и только тогда, когда он получит диплом об окончании вуза Приоритеты: отрицание; конъюкция; дизъюнкция; импликация; эквиваленция.
Для того чтобы из высказывания получить формулу, надо: выделить все элементарные высказывания и логические связки, образующие данное составное высказывание; заменить их соответствующими буквами и символами; расставить скобки в соответствии со смыслом данного высказывания.
Например, есть предложение: «Если выучить теорию и решить контрольные задания, то хорошая оценка на экзамене обеспечена». Обозначим: X – «выучить теорию», Y – «решить контрольные задания», Z – «хорошая оценка обеспечена». Формула для этого высказывания выглядит: (X Y)Z.
Способ вычисления истинности формул Пусть формула имеет вид:
Формулы F 1 и F 2 называются равносильными (обозначение F 1 = F 2 ), если при любых одинаковых истинностных значениях входящих в них переменных они принимают одинаковые значения истинности. Вместо термина «равносильность» можно использовать термин «логическая эквивалентность». Равносильность устанавливается сравнением таблиц истинности формул.
Основные равносильности
Закон тождества говорит, что высказывание не меняет своего истинностного значения на протяжении всего рассуждения, в котором это высказывание встречается. Закон противоречия устанавливает, что никакое высказывание не может быть истинным одновременно со своим отрицанием. Закон исключенного третьего утверждает, что для каждого высказывания имеются лишь две возможности: высказывание истинно или ложно, третьего не дано. Закон снятия двойного отрицания отмечает, что отрицать отрицание какого–либо высказывания – то же, что утверждать это высказывание.
Закон идемпотентности говорит, что конъюнкция одинаковых высказываний равносильна одному из них; аналогично дизъюнкция одинаковых высказываний равносильна одному высказыванию. Закон коммутативности показывает, что и в конъюнкции, и в дизъюнкции высказывания можно менять местами. Закон ассоциативности устанавливает правила объединения высказываний в конъюнкциях и дизъюнкциях в группы с помощью скобок. Закон дистрибутивности объясняет правила раскрытия скобок и говорит, что по отношению к дистрибутивности конъюнкция и дизъюнкция совершенно «равноправны».
Законы Де Моргана звучат так: «Отрицание конъюнкции равносильно дизъюнкции отрицаний; отрицание дизъюнкции равносильно конъюнкции отрицаний». Законы сочленения переменной с константой показывают, что получится в результате, если конъюнктивно или дизъюнктивно к переменной присоединить логическую константу (И или Л). Закон поглощения и закон склеивания предлагают комбинации, очень удобные при решении логических задач. Замена импликации дает возможность выразить импликацию через дизъюнкцию и отрицание либо через конъюнкцию и отрицание.
Пусть некоторое утверждение имеет вид импликации XY. Например, «Если вы замкнутый и мнительный человек (X), то люди не стремятся к контакту с вами (Y)». Предложение XY называется прямым (исходным) утверждением, предложение YX – обратным утверждением, – противоположным, a – обратно противоположным. Если импликация XY истинна, то утверждение XY называется теоремой, X называется достаточным условием для Y, а Y – необходимым условием для X или следствием X; говорят, что в этом случае имеет место логическое следование YX.
Истинность X гарантирует истинность Y, а ложность X ни о чем не говорит. Ложность Y гарантирует невыполнение условия, а истинность Y ничего не говорит об истинности X. На основе равносильностей сложные выражения приводятся к более простому виду – так называемой дизъюнктивной (или конъюнктивной) нормальной форме (сокращенно: д.н.ф. и к.н.ф.).
Дизъюнктивная нормальная форма представляет собой дизъюнкцию конъюнкций переменных и их отрицаний либо конъюнкцию самих переменных. Например, – д.н.ф. Конъюнктивной нормальной формой называется конъюнкция дизъюнкций переменных и их отрицаний либо дизъюнкция самих переменных. Например, – к.н.ф. Теорема 1. Любую формулу (любое высказывание) можно привести к д.н.ф. Теорема 2. Любая формула может быть представлена в к.н.ф.
Булевы функции Если множество значений функции представляет собой двухэлементное множество {И,Л}, то такие функции называются булевыми функциями.
Булевы функции представляются в двух видах: совершенной дизъюнктивной нормальной (с.д.н.ф.). Характерным для нее является то, что каждый дизъюнктивный член является произведением всех исходных переменных (с отрицанием или без него). совершенной конъюнктивной нормальной (с.к.н.ф.) и является конъюнкцией дизъюнкций, содержащих все исходные переменные (с отрицанием или без него).
Предикаты Функция, все значения которой принадлежат множеству {И,Л}, называется предикатом. Буквы Р, R и т.д., обозначающие предикаты, называются предикатными символами.
Способы задания предикатов: с помощью высказывательной формы с помощью формулы, т. е. заданием интерпретации предикатного символа с помощью таблицы. Такой способ годится только для предикатов, область определения которых – конечное множество. Областью определения предиката может быть любое множество. Если же предикат при каком–нибудь наборе входящих переменных теряет смысл, то принято считать, что этому набору соответствует значение Л.
Если предикат содержит одну переменную, он называется одноместным, если две переменные – двухместным и т. д. Предикат с n различными переменными называется n-местным предикатом. Упорядоченной n-кой («энкой») называется совокупность n не обязательно различных объектов вместе с заданным порядком их расположения. Две упорядоченные n-ки считаются равными, если их компоненты и порядок их расположения совпадают. Например, (Темпалгин, Пенталгин, Анальгин) и (Пенталгин, Темпалгин, Анальгин) – различные упорядоченные тройки.
Предикату Р, заданному на множестве М, соответствует подмножество этого множества, состоящее из тех и только тех элементов М, которым соответствует значение И предиката Р. Это подмножество М называется множеством истинности предиката Р. Множество истинности предиката Р обозначается через Р*. При этом Р* М. Если множество истинности совпадает со всей областью определения предиката, то такой предикат называется тождественно истинным. Если же множество истинности пусто, предикат называется тождественно ложным.
Множество элементов, обладающих свойством Р, называют объемом данного свойства. Рассмотрим некоторое непустое множество U. Пусть на этом множестве задано свойство Р, т. е. выделено подмножество Р* U; тогда имеем разбиение U на два подмножества: Р* и U\P*. Такое разбиение называется классификацией множества U по основанию Р. Второе подмножество (U\P*) характеризуется свойством, отрицающим Р(х), т.е. свойством
Правила классификации пересечение любых двух классов пусто; объединение всех классов равно множеству, элементы которого классифицируются. С помощью одноместного предиката удобно выражать свойства, а многоместными предикатами выражаются отношения.
Кванторы Если Р(х) означает, что х обладает свойством Р, то посредством обозначает утверждение «Для всякого объекта х свойство Р выполнено» или «Все х обладают свойством Р». Запись будет означать, что «существует х, обладающий свойством Р». квантор всеобщности – квантор существования –
Никакое высказывание не может быть истинным одновременно со своим отрицанием – это закон 1.противоречия 2.коммутативности 3.ассоциативности 4.дистрибутивности
Литература Ганичева А. Математика для психологов. М.: Аспект-пресс, 2005 Павлушков И.В. Основы высшей математики и математической статистики. М.: ГЭОТАР-Медиа,2007 Журбенко Л. Математика в примерах и задачах. М.: Инфра-М,2009