Отнт. А. Ю. Босова Москва бином. Лаборатория знаний 10 класс Базовый уровень Учебник
 Скачать 6.18 Mb.
|
|
§18 Из имеющихся высказываний можно строить новые высказывания. Для этого используются логические связки — слова и словосочетания не, и, или, если …, то, тогда и только тогда и др. Высказывания, образованные из других высказываний, называются составными (сложными. Высказывание, никакая часть которого не является высказыванием, называется элементарным (простым). Например, из двух простых высказываний Алгебра логики является основой строения логических схем компьютеров и Алгебра логики служит математической основой решения сложных логических задач можно получить составное высказывание Алгебра логики является основой строения логических схем компьютеров и служит математической основой решения сложных логических задач». Обоснование истинности или ложности элементарных высказываний не является задачей алгебры логики. Эти вопросы решаются теми науками, к сфере которых относятся элементарные высказывания. Такое сужение интересов позволяет обозначать высказывания символическими именами (например, A, B, C). Так, если обозначить элементарное высказывание Джордж Буль — основоположник алгебры логики именем A, а элементарное высказывание «2 + 2 = 5» именем B, то составное высказывание Джордж Буль — основоположник алгебры логики, и 2 + 2 = 5» можно записать как «A и B». Здесь A, B — логические переменные, и — логическая связка. Логическая переменная — это переменная, которая обозначает любое высказывание и может принимать логические значения истина или «ложь». Для логических значений истина и ложь могут использоваться следующие обозначения: Истина Ложь И Л true false да нет 0 Глава 4. теория множеств и алгебра логики Истинность или ложность составных высказываний зависит от истинности или ложности образующих их высказываний и определённой трактовки связок (логических операций над высказываниями Логические операции Логическая операция полностью может быть описана таблицей истинности, указывающей, какие значения принимает составное высказывание при всех возможных значениях образующих его элементарных высказываний. Из курса информатики основной школы вам известны логические операции отрицание, конъюнкция и дизъюнкция. Их таблицы истинности представлены ниже. Конъюнкция Дизъюнкция Отрицание A В A и B A A A или B A A 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны, называется конъюнкцией или логическим умножением. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны, называется дизъюнкцией или логическим сложением. Логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному, называется отрицанием или инверсией. При построении отрицания простого высказывания используется оборот неверно, что или к сказуемому добавляется частица не в высказывании, содержащем слово все, это слово заменяется на некоторые и наоборот алгебра логики §18 Рассмотрим несколько новых логических операций. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся ложным тогда и только тогда, когда первое высказывание (посылка) истинно, а второе (следствие) — ложно, называется импликацией или логическим следованием. Операция импликации обозначается символом É→ и задаётся следующей таблицей истинности: A B А → В 0 1 0 1 1 1 0 0 1 1 В разговорной речи импликации соответствуют предложения, содержащие связку если …, то. Эту связку мы используем тогда, когда хотим показать наличие причинно-следственной связи, иначе говоря, зависимость одного события от другого. Например, пусть некоторый человек сказал Если завтра будет хорошая погода, то я пойду гулять. Ясно, что человек окажется лжецом лишь в том случае, если погода действительно будет хорошей, а гулять он не пойдёт. Если же погода будет плохой, то, независимо оттого, пойдёт он гулять или нет, во лжи его нельзя обвинить обещание пойти гулять он давал лишь при условии, что погода будет хорошей. Результат операции импликации, как и других логических операций, определяется истинностью или ложностью логических переменных, а не наличием причинно-следственных связей между высказываниями. Например, абсурдное с житейской точки зрения высказывание Если 2 > 3, то существуют ведьмы является истинным сточки зрения алгебры логики. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда только одно из двух высказываний истинно, называется строгой (исключающей) дизъюнкцией Глава 4. теория множеств и алгебра логики Строгая дизъюнкция обозначается символом ⊕ и задаётся следующей таблицей истинности: А В А ⊕ В 0 0 0 1 1 1 0 1 1 1 В русском языке строгой (разделительной) дизъюнкции соответствует связка либо. В отличие от обычной дизъюнкции связка или) в высказывании, содержащем строгую дизъюнкцию, мы утверждаем, что произойдёт только одно событие. Например, высказывая утверждение На сегодняшнем матче Петя сидит на трибуне А либо на трибуне Б, мы считаем, что Петя сидит либо только на трибуне А, либо только на трибуне Б, и что сидеть одновременно на двух трибунах Петя не может. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным, когда оба исходных высказывания истинны или оба исходных высказывания ложны, называется экви- валенцией или равнозначностью. В логике эквиваленция обозначается символом É↔ и задаётся следующей таблицей истинности: А В А↔ В 0 1 0 1 0 1 0 0 1 1 В разговорной речи для выражения взаимной обусловленности используется связка тогда и только тогда, когда, а в математике необходимо и достаточно алгебра логики §18 Рассмотрим высказывание Денис пойдёт в бассейн тогда и только тогда, когда он выучит уроки. Это высказывание истинно (договорённость соблюдается, если истинны оба элементарных высказывания (Денис пойдёт в бассейн, Денис выучит уроки. Высказывание истинно (договор нность не нарушается) ив том случае, если оба элементарных высказывания ложны (Денис не пойдёт в бассейн, Денис не выучит уроки. Если же одно из двух высказываний ложно Денис пойдёт в бассейн, хотя и не выучит уроки, Денис выучит уроки, ноне пойдёт в бассейн, то договорённость нарушается, и составное высказывание становится ложным. А сейчас посмотрите внимательно на таблицы истинности строгой дизъюнкции и эквиваленции: если на некотором наборе логических переменных результатом строгой дизъюнкции является истина, тона этом же наборе результатом эквиваленции всегда будет ложь, и наоборот. Можно сделать выводы операция эквиваленции есть отрицание операции строгой дизъюнкции (A ↔ B = A B ⊕ ); • операция строгой дизъюнкции есть отрицание операции эк- виваленции (A ⊕ В = A B ↔ На сегодняшний день в алгебре логики не существует унифицированной символики для обозначения логических операций. В таблице 4.1 представлены логические операции и их наиболее распространённые обозначения, используемые как в алгебре логики, таки в некоторых языках программирования. Здесь же приведены речевые обороты, соответствующие логическим операциям. Таблица Логические операции и их обозначения Операция Обозначение Речевой оборот Отрицание (инверсия, логическое НЕ, A, НЕ A, not Не, неверно, что» Конъюнкция (логическое умножение, логическое И ∧ B, A & B, A · B, AB, A И B, A and И, как …, таки, вместе с, но, хотя, а Дизъюнкция (логическое сложение, логическое ИЛИ ∨ B, A + B, A | B, A ИЛИ B, A or Или, или …, или …, или оба вместе Глава 4. теория множеств и алгебра логики Операция Обозначение Речевой оборот Строгая дизъюнкция исключающая дизъюнкция, исключающее ИЛИ ⊕ B, A xor Либо …, либо, только … или только» Импликация (логическое следование →É B, A ⇒ Если …, то, из … следует, «влечёт» Эквиваленция (эквивалентность, равнозначность Эквивалентно, равносильно, необходимо и достаточно, тогда и только тогда, когда» Операция отрицания выполняется над одним операндом. Такие операции называются одноместными или унарными. Все остальные логические операции, представленные в таблице 4.1, выполняются над двумя операндами и называются двуместными или бинарными Логические выражения Составное логическое высказывание можно представить в видело- гического выражения (формулы, состоящего из логических констант (0, 1), логических переменных, знаков логических операций и скобок. Для логического выражения справедливо 1) всякая логическая переменная, а также логические константы (0, 1) есть логическое выражение 2) если A — логическое выражение, то и A — логическое выражение) если A и B — выражения, то, связанные любой бинарной операцией, они также представляют собой логическое выражение. При преобразовании или вычислении значения логического выражения логические операции выполняются в соответствии сих приоритетом 1) отрицание 2) конъюнкция 3) дизъюнкция, строгая дизъюнкция 4) импликация, эквиваленция. Окончание табл. 4.1 алгебра логики §18 Операции одного приоритета выполняются в порядке их следования, слева направо. Как ив арифметике, скобки меняют порядок выполнения операций. Пример 1. Выясним, какие из приведённых слов удовлетворяют логическому условию (первая буква согласная →É вторая буква согласная) & (последняя буква гласная É→ предпоследняя буква гласная 1) ОЗОН 2) ИГРА 3) МАФИЯ 4) ТРЕНАЖ. Вычислим значение логического выражения для каждого изданных слов 1) (0 É→ 1) & (0 É→ 1) = 1 & 1 = 1; 2) (0 É→ 1) & (1 É→ 0) = 1 & 0 = 0; 3) (1 É→ 0) & (1 É→ 1) = 0 & 1 = 0; 4) (1 É→ 1) & (0 É→ 1) = 1 & 1 = Итак, заданному условию удовлетворяют первое и четвёртое слова. Решение логического уравнения — это один или несколько наборов значений логических переменных, при которых логическое уравнение становится истинным выражением. Пример 2. Решим логическое уравнение (A É→ C) ∨ (( B C ∨ ) & A) ∨ D = Дизъюнкция ложна в томи только в том случае, когда ложно каждое из образующих её высказываний. Иными словами, наше уравнение соответствует системе уравнений C A D 0 0 0 ; ( ) Таким образом, значение переменной D уже найдено. Импликация равна нулю в единственном случае — когда из истины следует ложь. Иначе говоря, в нашем случае A = 1 и C = Подставим найденные значения переменных в уравнение ( B C ∨ ) & A = 0. Получим ( B ∨ 0 ) & 1 = 0 или B = 0, те Ответ A = 1, B = 1, С = 0, D = 0. Глава 4. теория множеств и алгебра логики Логические уравнения могут иметь не одно, а несколько и даже очень много решений. Зачастую требуется, не выписывая все решения уравнения, указать их количество. Пример 3. Выясним, сколько различных решений имеет логическое уравнение (A & B & C ) ∨ ( B & C & D) = Дизъюнкция истинна, если истинно хотя бы одно из образующих её высказываний. Решение данного логического уравнения равносильно совокупности, состоящей из двух уравнений & 1 Первое равенство будет выполняться только при A = 1, B = 1 и C = 0. Поскольку D в этом уравнении не задействовано, оно может принимать любое из двух значений (0 или 1). Таким образом, всего первое уравнение имеет 2 решения. Самостоятельно выясните, сколько решений имеет второе уравнение (из совокупности двух уравнений). Сколько решений имеет исходное уравнение? Пример 4. Выясним, сколько решений имеет очень простое с виду логическое уравнение x 1 & x 2 → x 3 & x 4 = 1. Введём замену переменных. Пусть t 1 = x 1 & x 2 , t 2 = x 3 & Тогда исходное уравнение примет вид t 1 → t 2 = На t 1 никаких ограничений нет, эта переменная может принимать значения 0 и 1. Импликация равна 0 только в случае, когда из истины (1) следует ложь (0). Исключим этот вариант. Построим дерево решений, представив на нём значения переменных и t 2 при которых t 1 → t 2 = Получаем для t 1 и t 2 три набора значений 00, 01, 11. Первая двоичная цифра в каждом из этих трёх наборов — результат выражения x 1 & x 2 , вторая — x 3 & x 4 . Рассмотрим первый набор существует три набора x 1 и x 2 таких, что x 1 & x 2 = 0, другими алгебра логики §18 словами, первый 0 мы можем получить тремя способами. Второй 0 в этом наборе мы также можем получить тремя способами. Из курсов информатики и математики основной школы вам известно одно из основных правил комбинаторики — правило умножения. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n · m способами. Согласно правилу умножения, пару 00 можно получить 3 · 3 = 9 способами. Что касается пары 01, то первый 0 мы можем получить тремя способами, а для получения 1 существует единственный вариант при x 3 = 1 и x 4 = 1). Следовательно, есть ещё три набора переменных x 1 , x 2 , x 3 , x 4 , являющихся решением исходного уравнения. Самостоятельно доведите решение этой задачи до конца предикаты и их множества истинности Равенства, неравенства и другие предложения, содержащие переменные, высказываниями не являются, но они становятся высказываниями при замене переменной каким-нибудь конкретным значением. Например, предложение x < 12 становится истинным высказыванием при x = 5 (5 < 12 — истина) и ложным при x = 15 (15 < 12 — ложь. Предложения такого рода называют высказывательными формами или предикатами. Предикат — это утверждение, содержащее одну или несколько пе- ременных. Выделим некоторый предикат P(x) и рассмотрим множество всевозможных объектов I, к которым он относится, — область определения предиката. Можно выделить такое подмножество P множества I, что на всех его элементах предикат P(x) будет превращаться в истинное высказывание. Определённое таким образом P называется множеством истинности предиката Рассмотрим множество учеников некоторого класса. Известно, что в этом классе два отличника — Иван и Саша. Предикат Он отличник будет истинным высказыванием только по отношению к этим двум учениками ложным по отношению ко всем остальным Глава 4. теория множеств и алгебра логики Предикаты позволяют задать множество, не перечисляя всех его элементов. Например, множество истинности предиката множество отрицательных чисел множество истинности предиката P(x, y) = (x 2 + y 2 = 1) — множество точек окружности единичного радиуса с центром вначале координат. Следует отметить, что многие задания, выполняемые вами на уроках математики, прямо связаны с предикатами. Например, стандартное задание Решить квадратное уравнение x 2 – 3x + 2 = 0» фактически означает требование найти множество истинности предиката P(x) = (x 2 – 3x + 2 = Из имеющихся предикатов с помощью логических операций можно строить новые предикаты. Пусть A и B соответственно являются множествами истинности предикатов A(x) и B(x). Тогда пересечение множеств A и B будет являться множеством истинности для предиката A(x) & B(x), а объединение множеств A и B будет множеством истинности для предиката A(x) ∨ Пример 5. Найдём все целые числа z, превращающие предикат в истинное высказывание. Другими словами, требуется найти множество истинности предиката P(z), заданного на множестве целых чисел ℤ. Предикат P(z) состоит из двух предикатов, соединённых операцией конъюнкции P(z) = A(z) & B(z). Рассмотрим каждый из них в отдельности. Множеством истинности предиката A(z) = (z > 5) являются целые числа 6, 7, 8 и т. д. Множеством истинности предиката B(z) = (z – 2 < 15) являются все целые числа, меньшие Множество истинности исходного предиката — пересечение общие элементы) множеств истинности образующих его предикатов, Его мощность |P| = 11. алгебра логики §18 Пример 6. Рассмотрим предикат (50 < x 2 ) É→ (50 > (x + 1) 2 ), определённый на множестве целых чисел. Найдём множество истинности этого предиката. Зачастую задания такого рода формулируют несколько иначе. Например, так Найдите все целые числа x, для которых истинно высказывание+ Проанализируем отдельно каждый из элементарных предикатов) и (50 > (x + 1) 2 ), решив соответствующие неравенства истинно для всех целых x ∈ ]–∞; –8] ∪ [8; +∞[; 50 > (x + 1) 2 истинно для всех целых x ∈ [–8; Определим значение исходного предиката на каждом из полученных подмножеств, причём отдельно рассмотрим значение x = –8 (оно попадает в два подмножества) и значение x = 7 (оно не попадает нив одно подмножество Z 50 < x 2 50 > (x + 1) 2 (50 < x 2 ) → (50 > (x + 1) 2 ) ]–∞; –9] 1 0 0 –8 1 1 1 [–7; 6] 0 1 1 7 0 0 1 [8; +∞[ 1 Итак, множеством истинности исходного предиката являются целые числа, принадлежащие отрезку [–8; 7]. Наименьшим элементом этого множества является число –8, наибольшим — число 7; мощность множества равна самое ГЛаВное Высказывание — это предложение, в отношении которого можно сказать, истинно оно или ложно. Высказывания, образованные из других высказываний, называются составными сложными. Высказывание, никакая часть которого не является высказыванием, называется элементарным (простым. Истинность или ложность составных высказываний зависит Глава 4. теория множеств и алгебра логики от истинности или ложности образующих их высказываний и определённой трактовки связок (логических операций над вы- сказываниями). Логическая операция полностью может быть описана таблицей истинности, указывающей, какие значения принимает составное высказывание при всех возможных значениях образующих его элементарных высказываний. Логические переменные Логические операции Отрицание Конъюнкция Дизъюнкция Импликация Строгая дизъюнкция Эквиваленция A B A A & B A ∨ B A → B A ⊕ B A ↔ B 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 Составное логическое высказывание можно представить в виде логического выражения (формулы, состоящего из логических констант (0, 1), логических переменных, знаков логических операций и скобок. Логические операции имеют следующий приоритет 1) отрицание 2) конъюнкция 3) дизъюнкция, строгая дизъюнкция 4) импликация, эквиваленция. Операции одного приоритета выполняются в порядке их следования, слева направо. Скобки меняют порядок выполнения опе- раций. Предикат — это утверждение, содержащее одну или несколько переменных. Из имеющихся предикатов с помощью логических операций можно строить новые предикаты алгебра логики |