Отнт. А. Ю. Босова Москва бином. Лаборатория знаний 10 класс Базовый уровень Учебник
 Скачать 6.18 Mb.
|
|
§18 Вопросы и задания 1. Изданных предложений выберите те, которые являются высказываниями. Обоснуйте свой выбор) Как пройти в библиотеку) Коля спросил Который час) Картины Пикассо слишком абстрактны) Компьютеры могут быть построены только на основе двоичной системы счисления 2. Из каждых трёх выберите два высказывания, являющихся отрицаниями друг друга) «1999 < 2000», «1999 > 2000», «1999 ≤ 2000»; 2) Петя решил все задания контрольной работы, Петя не решил все задания контрольной работы, Петя решил не все задания контрольной работы) Луна — спутник Земли, Неверно, что Луна — спутник Земли, Неверно, что Луна не является спутником Земли) Прямая a не параллельна прямой c», Прямая a перпендикулярна прямой c», Прямые a и c не пересекаются считаем, что прямые a и c лежат водной плоскости) Мишень поражена первым выстрелом, Мишень поражена не первым выстрелом, Неверно, что мишень поражена не первым выстрелом 3. Рассмотрите следующие элементарные высказывания A = Река Днепр впадает в Черное море, В = «45 — простое число, С = Вена — столица Австрии, D = «0 — натуральное число Определите, какие из них истинные, а какие ложные Составьте сложные высказывания, применяя каждый раз только одну из пяти логических операций (¬, &, ∨, É→, É↔) к высказываниям A, В, Си. Сколько новых высказываний можно получить с помощью отрицания (инверсии Конъюнкции Дизъюнкции Импликации Эквиваленции? Сколько всего новых высказываний можно получить Сколько среди них будет истинных 4. Представьте каждую пословицу в виде сложного логического высказывания, построенного на основе простых высказываний. Ответ обоснуйте при помощи таблиц истинности. 1) На вкуси цвет товарищей нет) Если долго мучиться, что-нибудь получится Глава 4. теория множеств и алгебра логики) Не зная брода, не суйся вводу) Тяжело в ученье, легко в бою) Тоне беда, что во ржи лебеда, то беда, что ни ржи, ни лебеды) Где тонко, там и рвется. 7) Или грудь в крестах, или голова в кустах. 8) За двумя зайцами погонишься — ни одного не поймаешь) И волки сыты, и овцы целы 5. Подберите вместо А, В, С, D такие высказывания, чтобы полученные сложные высказывания имели смысла) если (А или В и Сто б) если (не Аи не В, то (С или в) (А или В) тогда и только тогда, когда Сине. Вычислите) 1 ∨ Х & 0; 2) Х & Х & 1; 3) 0 & Х ∨ 0; 4) 0 ∨ X & X. 7. Сколько из приведённых чисел Z удовлетворяют логическому условию ((Z кратно 4) ∨ (Z кратно 5)) É→ (Z кратно 6)? 1) 4; 2) 6; 3) 7; 4) 12. 8. Найдите все целые числа Z, для которых истинно высказывание. Какие из высказываний А, В, С должны быть истинны и какие ложны, чтобы были ложны следующие высказывания? а) (( A ∨ В) & B) É→ б) A B & É↔ 1. 10. Даны три числа в различных системах счисления А = 23 10 , В = 23 8 , С = А Переведите А, В и Св двоичную систему счисления ивы- полните поразрядно логические операции (А ∨ В) & С. Ответ дайте в десятичной системе счисления. Логическое отрицание восьмиразрядного двоичного числа, записанное в десятичной системе счисления, равно 217. Определите исходное число в десятичной системе счисления. Определите логическое произведение и логическую сумму всех двоичных чисел в диапазоне от 16 10 до 22 10 , включая таблицы истинности §19 границы. Ответ запишите в восьмеричной системе счисления. Сколько различных решений имеет логическое уравнение) (A ∨ B ∨ C) & ( B & C & D) = 1; 2) (A ∨ B ∨ C)∨( B & C & D) = 0; 3) (A É→ C)∨(B & A)∨(D É→ B & C) = 0; 4) (A & B & C)É→ ( C & D) = 1. 14. Сколько решений имеет логическое уравнение x 1 & x 2 ∨ x 3 & x 4 = 1? 15. Изобразите в декартовой прямоугольной системе координат множества истинности для следующих предикатов) P(x, y) = (y ≥ x) & (y + x ≥ 0) & (y ≤ б) P(x, y) = (|x| ≤ 1) & (|y| ≤ в) P(x, y) = (x 2 + y 2 ≤ 4) & (x 2 + y 2 ≥ 1). 16. Предикат ((8x – 6) < 75) →É (x (x – 1) > 65) определён на множестве целых чисел. Найдите его множество истинности. Укажите наибольшее целое число x, при котором предикат превращается в ложное высказывание таблицы истинности построение таблиц истинности Таблицу значений, которые принимает логическое выражение при всех сочетаниях значений (наборах) входящих в него переменных, называют таблицей истинности логического выражения. Для того чтобы построить таблицу истинности логического выражения, достаточно 1) определить число строк таблицы m = 2 n , где n — число переменных в логическом выражении 2) определить число столбцов таблицы как сумму чисел логических переменных и логических операций в логическом выражении Глава 4. теория множеств и алгебра логики 3) установить последовательность выполнения логических операций с учётом скобок и приоритетов операций 4) заполнить строку с заголовками столбцов таблицы истинности, занеся вне имена логических переменных и номера выполняемых логических операций 5) выписать наборы входных переменных с учётом того, что они представляют собой ряд целых разрядных двоичных чисел от 0 до 2 n – 1; 6) провести заполнение таблицы истинности по столбцам, выполняя логические операции. Пример 1. Построим таблицу истинности для логического выражения В этом выражении две логические переменные и пять логических операций. Всего в таблице истинности будет пять строк (2 2 плюс строка заголовков) и 7 столбцов. Начнём заполнять таблицу истинности с учётом следующего порядка выполнения логических операций сначала выполняются операции отрицания (в порядке следования, затем операции конъюнкции (в порядке следования, последней выполняется дизъюнкция 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 Обратите внимание на последний столбец, содержащий конечный результат. Какой из рассмотренных логических операций он соответствует таблицы истинности §19 Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными или эквивалентными, если для всех наборов входящих в них переменных значения выражений в таблицах истинности совпадают. Таблица истинности, построенная в предыдущем примере, доказывает равносильность выражений A & B ∨ A & B и A É↔ Можно записать A & B ∨ A & B = A ↔É С помощью таблиц истинности докажите равносильность выражений и А ∨ Функцию от n переменных, аргументы которой и сама функция принимают только два значения — 0 и 1, называют логической функцией. Таблица истинности может рассматриваться как способ задания логической функции анализ таблиц истинности Рассмотрим несколько примеров. Пример 2. Известен фрагмент таблицы истинности для логического выражения F, содержащего логические переменные А, В и С. А В С F 1 0 1 0 1 1 0 1 1 1 1 Сколько из приведённых ниже логических выражений соответствуют этому фрагменту а) (A СВ б) (A В) & (C É→A); в) (A В СВ С г) (A В) С ∨A É→В). Ответить на поставленный вопрос можно, вычислив значение каждого логического выражения на каждом заданном наборе переменных и сравнив его с имеющимся значением F. Глава 4. теория множеств и алгебра логики а) Логическое выражение (A ∨ С) & B соответствует данному фрагменту таблицы истинности: А В С (А ∨ СВ 1 1 1 1 (1 ∨ 1) & 1 = 1 & 1 = 1 1 б) Логическое выражение (A ∨ Вне соответствует данному фрагменту таблицы истинности, т. к. уже на первом наборе значение рассматриваемого логического выражения не совпадает со значением F. Проведение дальнейших вычислений не имеет смысла. A В С (A ∨ В) & (C → A) F 1 0 1 (1 ∨ 0) & (1→ 1) = 1 & 1 = 1 0 1 1 0 1 1 1 1 1 в) Логическое выражение (A & В ∨ СВ Сне соответствует данному фрагменту таблицы истинности: A В С (A & В ∨ СВ С 0 1 (1 & 0 ∨ 1) & (0→ 1 & 1) = 1 & 1 = 1 0 1 1 0 1 1 1 1 1 г) Логическое выражение (A →É В) ∨ (СВ) соответствует данному фрагменту таблицы истинности: A В С (A → В СВ 1→ 1) = 1 1 таблицы истинности §19 Итак, имеется два логических выражения, соответствующих заданному фрагменту таблицы истинности. Можно ли утверждать, что в результате решения задачи мы нашли логическое выражение Пример 3. Логическая функция F задаётся выражением ∨ y ∨ z ) & ( x ∨ Ниже приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F истинна 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 Определим, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, В исходном логическом выражении задействовано три логические переменные. Полная таблица истинности для этого выражения должна состоять из 8 (2 3 ) строк. Наборам переменных, на которых логическое выражение истинно, соответствуют десятичные числа 0, 2, 3, 4 и Следовательно, наборам переменных, на которых логическое выражение ложно, должны соответствовать десятичные числа 1, 5 и 6 (их двоичные коды 001, 101 и 110). Построим по этим данным вторую часть таблицы истинности 0 1 0 1 0 1 0 1 1 0 Теперь выясним, при каких значениях x, y, z логическое выражение ложно (x ∨ y ∨ z ) & ( x ∨ y) = 0. Логическое произ- Глава 4. теория множеств и алгебра логики ведение ложно, если хотя бы один из операндов равен нулю. Таким образом, мы имеем две дизъюнкции, каждая из которых должна быть ложной. Это возможно только в случае равенства нулю каждого из операндов, входящих в дизъюнкцию. Подберём подходящие значения x, y и z, заполняя следующую таблицу y∨ z 0 x∨ Первая дизъюнкция равна нулю на наборе 011. Для равенства нулю второй дизъюнкции требуется, чтобы x = 1, y = 0, а z может быть и 0, и 1. x y z F x∨ y∨ z 0 1 1 0 x∨ y 1 0 0 0 1 0 1 Сравним эту таблицу с восстановленным нами фрагментом исходной таблицы истинности, предварительно подсчитав, сколько раз каждая переменная принимает единичное значение. Восстановленный фрагмент Таблица со значениями, y и z ? ? ? F x y z F 0 0 1 0 x∨ y∨ z 0 1 1 0 1 0 1 0 x∨ y 1 0 0 0 1 1 0 0 1 0 1 0 2 1 2 Переменная y принимает единичное значение только один раз. Следовательно, ей соответствует второй столбец исходной таблицы. Из таблицы со значениями x, y и z следует, что при y = 1: x = 0, а z = 1. Следовательно, переменной z соответствует первый столбец, а переменной x — третий столбец исходной таблицы таблицы истинности §19 Убедиться в правильности полученного ответа можно, полностью заполнив следующую таблицу = x ∨ y ∨ z B = x ∨ y A & B F 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 самое ГЛаВное Таблицу значений, которые принимает логическое выражение при всех сочетаниях значений (наборах) входящих в него переменных, называют таблицей истинности логического выражения. Истинность логического выражения можно доказать путём построения его таблицы истинности. Функцию от n переменных, аргументы которой и сама функция принимают только два значения — 0 и 1, называют логической функцией. Таблица истинности может рассматриваться как способ задания логической функции. Вопросы и задания 1. Что представляет собой таблица истинности 2. Составлена таблица истинности для логического выражения, содержащего n переменных. Известно m — количество строк, в которых выражение принимает значение 0. Требуется выяснить, в скольких случаях логическое выражение примет значение 1 при следующих значениях n и m: 1) n = 6, m = 15; 2) n = 7, m = 100; 3) n = 10, m = 500. Глава 4. теория множеств и алгебра логики 3. Постройте таблицы истинности для следующих логических выражений) (A →É В) É↔ (A & В) (A →É B) →É ((A →É B ) →É A ); 3) (A →É (C →É В) →É (В ∨ C). 4. Рассмотрите два составных высказывания F 1 = Если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3»; • F 2 = Если одно слагаемое делится на 3, а другое слагаемое не делится на 3, то сумма не делится на 3». Формализуйте эти высказывания, постройте таблицы истинности для каждого из полученных выражений и убедитесь, что результирующие столбцы совпадают 5. Логическое выражение, являющееся истинным при любом наборе входящих в него переменных, называется тождественно истинным. Убедитесь, что следующие логические выражения являются тождественно истинными) A →É (В →É A); 2) (A →É B ) →É (В →É A ); 3) (A & C →É B) →É (C →É (A ∨ B →É B & C)). 6. Какое из приведённых логических выражений равносильно выражению (A →É С) & (B →É C)? 1) A & B →É C; 2) A →É B →É C; 3) A ∨ B →É C; 4) A ↔ B →É C. 7. Известен фрагмент таблицы истинности для логического выражения, содержащего логические переменные A, B и С. А B C F 0 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 Какое из приведённых далее логических выражений соответствуют этому фрагменту преобразование логических выражений §20 а) A & СВ б) (A ∨ В) & (C →É в) (A & В ∨ СВ С); г) ( B A → )∨ (С ∨ A →É В); д) ни одна из указанных формул 8. Логическая функция F задаётся выражением & B & C )∨ (A & B & C)∨ (A & B & C ). Ниже приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F ложна 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 Какому столбцу таблицы истинности функции F соответствует каждая из переменных A, В, С преобразование логических выражений Способ определения истинности логического выражения путём построения его таблицы истинности становится неудобным при увеличении количества логических переменных, т. к. за счёт существенного увеличения числа строк таблицы становятся громоздкими. В таких случаях выполняются преобразования логических выражений в равносильные. Для этого используют свойства логических операций, которые иначе называют законами алгебры логики Глава 4. теория множеств и алгебра логики основные законы алгебры логики Приведём основные законы алгебры логики 1. Переместительные (коммутативные) законы & B = B & A; A ∨ B = B ∨ A. 2. Сочетательные (ассоциативные) законы & B) & C = A & (B & C); (A ∨ B)∨ C = A ∨ (B ∨ C). 3. Распределительные (дистрибутивные) законы & (B ∨ C) = (A & B) ∨ (A & C); A ∨ (B & C) = (A ∨ B) & (A ∨ C). 4. Законы идемпотентности (отсутствия степеней и коэффициентов. Закон противоречия & A = 0. 6. Закон исключённого третьего ∨ A = 1. 7. Закон двойного отрицания = A. 8. Законы работы с константами ∨ 1 = 1; A ∨ 0 = A; A & 1 = A; A & 0 = 0. 9. Законы де Моргана = A ∨ B ; A B ∨ = A & B . 10. Законы поглощения & (A ∨ B) = A; A ∨ (A & B) = Справедливость законов можно доказать построением таблиц истинности. Пример 1. Упростим логическое выражение A & B & C ∨ A & B & C Последовательно применим дистрибутивный закон и закон исключённого третьего & B & C ∨ A & B & C = A & B & (C ∨ C ) = A & B & 1 = A & B. преобразование логических выражений §20 Пример 2. Упростим логическое выражение (A ∨ B) & (A ∨ B ∨ C) & (A ∨ B ∨ C ). (A ∨ B) & (A ∨ B ∨ C) & (A ∨ B ∨ C ) = (A ∨ B) & (0∨ C ∨ C ) = = (A ∨ B) & 1 = A ∨ Аналогичные законы выполняются для операций объединения, пересечения и дополнения множеств. Например ∪(B ∩ C) = (A ∪ B)∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B)∪(A ∩ C), A ∩ B = A ∪ B; A ∪ B = A ∩ Пробуйте самостоятельно доказать один из этих законов с помощью кругов Эйлера. Пример 3. На числовой прямой даны отрезки В = [2; 12] и C = [7; 18]. Каким должен быть отрезок A, чтобы предикат (x ∈ A) ∨ ((x ∈ B) → (x ∈ C)) становился истинным высказыванием при любых значениях Преобразуем исходное выражение, избавившись от импликации) = = (x ∈ A) ∨ ( x B ∈ ) ∨ (x ∈ C). A, В и С — множества. Для них можем записать A ∪ B ∪ С = Известно, что A ∪ A = Будем считать, что A = B ∪ C. Тогда A = B C ∪ = B ∩ C , причём это минимально возможное множество Множество B — это отрезок [2; Множество C — это промежутки ]–∞; 7[ и ]18; +Изобразим это графически: Пересечением этих множеств будет служить промежуток [2; 7[. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий. Чему равна минимальная длина отрезка A? Укажите ещё несколько вариантов множества A. Глава 4. теория множеств и алгебра логики Пример 4. Для какого наименьшего неотрицательного целого десятичного числа a выражение (x & 28 ≠ 0 ∨ x & 45 ≠ 0) → (x & 17 = 0 → x & a ≠ тождественно истинно (те. принимает значение 1 при любом неотрицательном целом значении десятичной переменной x)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел. Прежде всего, вспомним, что представляет собой поразрядная конъюнкция двух целых десятичных чисел, например 27 и 22. 27 = 11011 2 , 22 = 10110 2 27 & 22 = 11011 & 10110 = 10010 2 = 18 10 & 1 1 0 1 1 1 0 1 1 0 1 0 0 1 Обратите внимание на то, что если в некотором бите хотя бы одного сомножителя есть 0, то 0 есть ив этом бите результата, а 1 в результате получается только тогда, когда в соответствующих битах каждого сомножителя есть 1. Введём обозначения) = (x & 28 ≠ 0), N(x) = (x & 45 ≠ 0), K(x) = (x & 17 = 0), A(x) = (x & a ≠ Перепишем исходное выражение в наших обозначениях) ∨ N(x)) → (K(x) → Преобразуем полученное выражение) ∨ N(x)) → (K(x) → A(x)) = M x N x ( ) ( ) ∨ ∨ K x ( ) ∨ A(x) = = ( ( ) ( ))& ( ) M x N x K x ∨ ∨ Рассмотрим предикат M(x) = (x & 28 ≠ 0). В числе 28 = 11100 й, й и й биты содержат единицы, ай и й — нули. Следовательно, множеством истинности этого предиката являются такие числа x, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и й, и й, и й биты числа x нулевые, то высказывание x & 28 ≠ 0 будет ложным. Рассмотрим предикат N(x) = (x & 45 ≠ 0). В числе 45 = 101101 й, й, й и й биты содержат единицы, й и й — нули. преобразование логических выражений |