Конспект_ОСНОВЫ ЛОГИКИ(3)(2). Решение логических задач. Учитель информатики Батракова Л. В
 Скачать 1.45 Mb.
|
|
Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 13 3.1. Второй и третий болельщики ошиблись, поставив на первое место Ника и Джона; 3.2. С учетом главного условия задачи, получается, что третий болельщик угадал во втором случае, и Макс будет на четвертом месте, но данное утверждение противоречит начальному предположению, следовательно, Макс должен быть не на первом месте, а на четвертом, как сказал третий болельщик: Первый болельщик Второй болельщик Третий болельщик 1 Макс Ник Джон 2 Билл 3 Билл 4 Макс 3.3. Имеем, что в первом прогнозе первый болельщик ошибся, то есть он угадал, что Билл занял второе место: Первый болельщик Второй болельщик Третий болельщик 1 Макс Ник Джон 2 Билл 3 Билл 4 Макс 3.4. Так как Билл – второй, он не может быть на третьем месте, поэтому из прогноза второго болельщика следует, что Ник – первый: Первый болельщик Второй болельщик Третий болельщик 1 Макс Ник Джон 2 Билл 3 Билл 4 Макс 3.5. Определимся с Джоном – ему досталось единственное свободное третье место: Первый болельщик Второй болельщик Третий болельщик 1 Макс Ник Джон 2 Билл Джон 3 Билл 4 Макс Получаем окончательный список победителей: Ник, Билл, Джон, Макс. Ответ: НБДМ 6. Решение задач на запросы к серверу. При вводе какого-то слова (например, принтер) в запросе поисковой системы означает, что пользователь ищет Web-страницы, на которых встречается это слово. Операция «И» всегда ограничивает поиск, то есть, в ответ на запрос принтер И сканер поисковый сервер выдаст меньше страниц, чем на запрос принтер, потому что будет искать страницы, на которых есть оба этих слова одновременно. Операция «ИЛИ» всегда расширяет поиск, то есть, в ответ на запрос принтер ИЛИ сканер поисковый сервер выдаст больше страниц, чем на запрос принтер, потому что будет искать страницы, на которых есть хотя бы одно из этих слов (или оба одновременно). Если в запросе вводится фраза в кавычках, поисковый сервер ищет страницы, на которых есть в точности эта фраза, а не просто отдельные слова. Взятие словосочетания в кавычки ограничивает поиск, то есть, в ответ на запрос " принтер сканер" поисковый сервер выдаст меньше страниц, чем на запрос принтер сканер, потому что будет искать только те страницы, на которых эти слова стоят одно за другим. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». Пример 1: В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. 1) принтеры & сканеры & продажа 2) принтеры & сканеры Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 14 3) принтеры | сканеры 4) принтеры | сканеры | продажа Решение (вариант 1, рассуждение с использованием свойств операций «И» и «ИЛИ»): 1) меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа) 2) на втором месте – второй запрос (одновременно принтеры и сканеры) 3) далее – третий запрос (принтеры или сканеры) 4) четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа) Ответ: 1234 Решение (вариант 2, через таблицы истинности): 1) каждое из условий можно рассматривать как сложное высказывание 2) обозначим отдельные простые высказывания буквами: A: принтеры (на странице есть слово «принтеры») B: сканеры C: продажа 3) запишем все выражения-запросы через логические операции C B A X 1 , B A X 2 , B A X 3 , C B A X 4 4) здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 2 3 всевозможных комбинаций этих логических значений 5) выражение C B A X 1 равно 1 (истинно) только при 1 C B A , в остальных случаях – равно 0 (ложно) 6) выражение B A X 2 равно 1 только при 1 B A , в остальных случаях – равно 0 7) выражение B A X 3 равно 0 только при 0 B A , в остальных случаях – равно 1 8) выражение C B A X 4 равно 0 только при 0 C B A , в остальных случаях – 1 9) запишем результаты пп. 5-8 в виде таблицы истинности A B C C B A X 1 B A X 2 B A X 3 C B A X 4 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 10) по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов 11) область, где 1 2 X , включает в себя всю область, где 1 1 X и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая 12) аналогично делаем вывод, что область 1 3 X включает всю область 1 2 X и расширяет ее, а область 1 4 X – это расширение области 1 3 X Ответ: 1234 Решение (вариант 3, через диаграммы Эйлера-Венна): 1) запишем все ответы через логические операции C B A X 1 , B A X 2 , B A X 3 , C B A X 4 2) покажем области, определяемые этими выражениями, на диаграмме с тремя областями Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 15 3) сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!) Ответ: 1234 Пример 2: В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц (тыс.) пирожное | выпечка 14200 пирожное 9700 пирожное & выпечка 5100 Сколько страниц (в тысячах) будет найдено по запросу выпечка Решение: По запросу пирожное | выпечка выдается множество страниц, в которых встречаются или одно слово или другое. По запросу пирожное & выпечка выдается множество страниц, в которых встречаются оба слова вместе. По запросам пирожное и выпечка выдается множество страниц, в которых встречается только данное слово. На рисунке показаны диаграммы Эйлера- Венна по данным запросам. Следовательно, чтобы получить количество страниц, найденных по запросу выпечка надо выполнить следующие вычисления: 14200 +5100 – 9700=9600 Ответ: 9600 Задачи для тренировки (часть 1) 1. Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C). 1) ¬A \/ ¬B \/ ¬C 2) A /\ ¬B /\ ¬C 3) A /\ B /\ ¬C 4) A /\ ¬B /\ C 2. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: X Y Z F 1 0 0 1 0 0 0 1 1 1 1 0 Какое выражение соответствует F? 1) ¬X /\ ¬Y /\ ¬Z 2) X /\ Y /\ Z 3) X \/ Y \/ Z 4) ¬X \/ ¬Y \/ ¬Z 3. Дан фрагмент таблицы истинности выражения F. A B С C B A X 1 A B С B A X 2 A B С B A X 3 A B С C B A X 4 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 16 x1 x2 x3 x4 x5 x6 x7 F 1 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 Какое выражение соответствует F? 1) ¬x1 x2 ¬x3 x4 x5 ¬x6 ¬x7 2) ¬x1 x2 ¬x3 x4 ¬x5 ¬x6 x7 3) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7 4) x1 ¬x2 x3 ¬x4 ¬x5 x6 ¬x7 4. Дано логическое выражение, зависящее от 6 логических переменных: X 1 ¬X 2 X 3 ¬X 4 X 5 X 6 Сколько существует различных наборов значений переменных, при которых выражение истинно? 1) 1 2) 2 3) 63 4) 64 5. Логическая функция F задаётся выражением (¬z) x x y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z? ? ? ? F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. 6. Дан фрагмент таблицы истинности для выражения F: x1 x2 x3 x4 x5 x6 F 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 1 Укажите минимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x1 совпадает с F. 7. Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы: x1 x2 x3 x4 x5 x6 x7 x8 F 0 1 1 1 0 0 1 1 0 Каким выражением может быть F? 1) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7 ¬x8 2) x1 x2 x3 ¬x4 ¬x5 ¬x6 ¬x7 ¬x8 3) x1 ¬x2 ¬x3 x4 x5 ¬x6 ¬x7 x8 4) x1 ¬x2 x3 ¬x4 ¬x5 ¬x6 ¬x7 ¬x8 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 17 8. Каждое логическое выражение A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A B? 9. Какое из приведённых имен удовлетворяет логическому условию: (первая буква согласная → вторая буква согласная) /\ (предпоследняя буква гласная → последняя буква гласная)? 1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ 10. Для какого из указанных значений X ложно высказывание ¬((X > 3) \/ (X<3))→(X < 1)? 1) 1 2) 2 3) 3 4) 4 11. Каково наименьшее целое число X, при котором истинно высказывание: ((X>7) \/ (X<7)) –>(X>8)? 12. На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x А) → (x P) ) \/ (x Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. 1) [0, 3] 2) [3, 11] 3) [11, 15] 4)[15, 17] 13. На числовой прямой даны три интервала: P = (5, 10), Q = [10, 20] и R = [25,40]. Выберите такой отрезок A, что выражения (x A) → (x P) и (x Q) → (x R) тождественно равны, то есть принимают одинаковые значения при любом значении переменной х. 1) [7, 20] 2) [2, 12] 3) [10,25] 4)[20, 30] 14. Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы: Володя: «Это сделал Саша». Аня: «Володя лжет!». Егор: «Маша разбила». Саша: «Аня говорит неправду!» Рома: «Разбила либо Маша, либо Нина…». Маша: «Это я разбила!» Нина: «Маша не разбивала!» Коля: «Ни Маша, ни Нина этого не делали». Олег: «Нина не разбивала!» Кто разбил окно, если известно, что из этих девяти высказываний истинны только три? Ответ запишите в виде первой буквы имени. 15. В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Крейсер | Линкор 7000 Крейсер 4800 Линкор 4500 Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор ? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. 16. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: Запрос Количество страниц (тыс.) 1 мезозой 50 2 кроманьонец 60 3 неандерталец 70 4 мезозой | кроманьонец 80 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 18 5 мезозой | неандерталец 100 6 неандерталец & (мезозой | кроманьонец) 20 Сколько страниц (в тысячах) будет найдено по запросу: кроманьонец & (мезозой | неандерталец) Часть 2. Множества в задачах на логику Здесь рассматриваются задачи с использованием множеств. Множество можно задать перечислением его элементов или с помощью логического выражения (условия), которое истинно для каждого элемента множества и ложно для всех элементов, не входящих во множество. В любой задаче можно выделить некоторое «универсальное» множество, в которое входят все объекты , рассматриваемые в задаче. В качестве такого универсального множества может быть выбрано, например: - множество точек числовой прямой, - множество точек, принадлежащих отрезку, - множество всех натуральных чисел, которые делятся на некоторое число, - какое-то другое множество. Основные операции над множествами: - дополнение (до выбранного универсального множества) - пересечение - объединение. Пусть A – это некоторое множество. Через A обозначают дополнение множества A до универсального множества, которое рассматривается в задаче. Например, если A – это множество точек, принадлежащих отрезку, то A - множество точек не принадлежащих этому отрезку (здесь универсальное множество - это множество всех точек числовой оси). Если A – множество натуральных чисел, которые делятся на некоторое число а, то A - это множество натуральных чисел, которые не делятся на а (здесь универсальное множество – это множество всех натуральных чисел). Операции с множествами тесно связаны с логическими операциями. Операции пересечения и объединения множеств будем обозначать так же, как и операции логического умножения и сложения. Через A · B обозначим пересечение множеств A и B, то есть все элементы, которые входят одновременно в A и B, а через A + B - объединение множеств A и B, то есть все элементы, которые входят хотя бы в одно из двух множеств. Многие задачи ЕГЭ на математическую логику сводятся к двум базовым задачам, в которых надо найти дополнение какого-то множества. Задача 1. Каким должно быть множество A для того , чтобы множество A+B совпадало с универсальным множеством? Решение: Очевидно, что можно выбрать в качестве решения B - дополнение множества B до универсального множества . Множество A min = B - это минимальное множество, которое является решением задачи. Кроме того, решением будет и любое множество, включающее B , т.елюбое А такое, что A ≥ B или , используя обозначения теории множеств, A B . Заметим, что множество A+B, которое по условию задачи должно совпадать с универсальным множеством, определяется логическим выражением A+B.Это выражение может быть преобразовано, с учетом свойств импликации, к форме B →A. Переход от условия A+B=1 к условию B →A =1 в некоторых случаях упрощает решение задачи. Задача 2. Каким должно быть множество A для того , чтобы множество A +B совпадало с универсальным множеством? Решение: В этом случае получаем A ≥ B , откуда следует, чтоA ≤ B, т.е. множество A должно быть подмножеством множества B (A B). Тогда максимальное множество A, которое является решением задачи , совпадает с B. Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 19 Множество A max = B - это максимальное множество, которое является решением задачи. В некоторых случаях случаях задача упрощается, если заменить условие A +B=1, определяющее множество A +B, на эквивалентное условие A→B=1 или B → A =1. Вывод: Конкретную задачу на множества и математическую логику нужно попытаться привести к форме Задачи1 или Задачи2 , а затем использовать готовое решение. Рассмотрим ряд задач на данную тему. 1. Задачи на отрезки Задача 1.На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что формула )) ( )) ( ) ((( ) ( P x A x Q x P x тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Решение: Для того, чтобы упростить понимание выражения, обозначим отдельные высказывания буквами A: x А, P: x P, Q: x Q Выражение примет вид: ) ( P A Q P Раскрываем обе импликации по формуле B A B A : P A Q P A Q P P A Q P ) ( Теперь используем закон де Моргана B A B A : P A Q Сразу видно, что отрезок A должен перекрыть область на числовой оси, которая не входит в область P Q : По рисунку видно, что не перекрыт только отрезок [40;60] (он выделен жёлтым цветом), его длина – 20, это и есть правильный ответ. Ответ: 20 Задача 2. На числовой прямой даны два отрезка: P = [10,20] и Q = [25, 55]. Определите наибольшую возможную длину отрезка A, при котором формула: ( x A) → ((x P) (x Q) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Решение: Для того, чтобы упростить понимание выражения, обозначим отдельные высказывания буквами: A: x А, P: x P, Q: x Q Выражение примет вид: A → (P + Q) Раскроем импликацию через операции НЕ и ИЛИ ( B A B A ): Q P A Q P A ) ( Для того, чтобы выражение было истинно при всех x, нужно, чтобы A было истинно там, где ложно Q P (жёлтая область на рисунке) 40 x P 77 Q 60 37 P Q Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 20 Поскольку области истинности P и Q разделены, максимальный отрезок, где A может быть истинно (и, соответственно, A ложно) – это наибольший из отрезков P и Q , то есть отрезок [25,55], имеющий длину 30. Ответ: 30 2. Задачи на множества чисел Задача 1. Элементами множества А являются натуральные числа. Известно, что выражение: (x {2, 4, 6, 8, 10, 12}) → (((x {4, 8, 12, 116}) ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12})) истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A. Решение: Заметим, что в задаче, кроме множества A, используются еще два множества: P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116} Для того, чтобы упростить понимание выражения, обозначим отдельные высказывания буквами: A: x А, P: x P, Q: x Q Перепишем выражение: ) ( P A Q P Раскрываем обе импликации по формуле B A B A : P A Q P A Q P P A Q P ) ( Теперь используем закон де Моргана B A B A : P A Q Поскольку это выражение должно быть равно 1, то A должно быть истинным везде, где ложно P Q Тогда минимальное допустимое множество A – это P Q P Q min A (по закону де Моргана) Переходим ко множествам Q = {4, 8, 12, 116} и P = {2, 4, 6, 8, 10, 12}. Тогда P Q – это все натуральные числа, которые входят одновременно в Q и P , они выделены жёлтым цветом: {4, 8, 12} Именно эти числа и должны быть «перекрыты» множеством А min , поэтому минимальный состав множества A – это А min = {4, 8, 12}, сумма этих чисел равна 24. Ответ: 24 Задача 2.Элементами множеств А, P и Q являются натуральные числа, причём P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20} и Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }. Известно, что выражение: ((x A) → ¬(x P)) (¬(x Q) → ¬(x A)) истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов множества A. Решение: Для того, чтобы упростить понимание выражения, обозначим отдельные высказывания буквами: A= (x А), P=( x P), Q=( x Q) Перепишем выражение: (A P )∙( Q A ). Используя свойство импликации B A B A и закон поглощения A+A∙B=A получаем: (A P )∙( Q A )=( A + P )∙(Q+ A )= A ∙Q+ P ∙ A + A = A + P ∙Q. Задача сведена к базовой Задаче2, где B= P ∙Q. Ее решение: A max = P ∙Q - это пересечение множеств P и Q, т.е. все элемены, которые входят в Q и не входят в P : A max ={3, 9, 15, 21, 24, 27, 30} Количество элементов этого множества равно 7. Ответ: 7 10 20 x P 55 Q 25 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 21 3. Задачи на делимость В следующих задачахДЕЛ(n, m) обозначаетутверждение «натуральное число n делится без остатка на натуральное число m». Обозначим через D N =(x D N ), A=(x D A ). Задача 1. Для какого наибольшего натурального числа А формула: ¬ДЕЛ(x, А) (ДЕЛ(x, 6) ¬ДЕЛ(x, 4)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Решение: Истинным для всех x должно быть выражение: ) ( 4 6 D D A Упростим это выражение, раскрыв импликацию по правилу B A B A : 4 6 4 6 ) ( D D A D D A . Мы свели задачу к базовой Задаче1, где 4 6 D D B Ее решение : 4 6 4 6 min D D D D D A – это множество всех чисел, которые делятся одновременно на 4 и 6 (все числа, кратные 4 и 6), то есть, 12, 24, 36 и т.д. (заметим, что 12 – это наименьшее общее кратное чисел 4 и 6). Для того, чтобы перекрыть эти числа, можно выбрать в качестве A любой делитель числа 12, то есть, 1, 2, 3, 4, 6 или 12. Но при уменьшении A соответствующее множество D A расширяется. Например, для A=1 множество D A включает все натуральные числа, а не только кратные 12. Поэтому максимальному A соответствует минимальное множество D A . Брать значение A большее, чем 12, нельзя, потому что в соответствующее множество D A войдут не все элементы множества D 6 · D 4 (например, не войдет число 12). Наибольшее из этих чисел – 12. Ответ: 12 Задача 2. Для какого наибольшего натурального числа А формула: ¬ДЕЛ(x, А) (¬ДЕЛ(x, 21) ¬ ДЕЛ(x, 35)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Решение: Запишем формулу из условия в наших обозначениях. Истинным для всех x должно быть выражение: 1 ) ( 35 21 D D A Раскроем импликацию по правилу B A B A : 35 21 35 21 ) ( D D A D D A Мы свели задачу к базовой Задаче1, где B= 35 21 D D . Ее решение: D Amin 35 21 35 21 D D D D - это множество чисел, которые делятся на 21 или на 35. Множество D Amin , точно соответствующее выражению с помощью одной операции ДЕЛ получить невозможно. Заметим, что любое множество D A , где A – какой-нибудь общий делитель 21 и 35, содержит D Amin (все числа, делящиеся на 21 или на 35). Смотри рисунок 1. Так как 7 – это наибольший общий делитель этих чисел, то множество D7 – это минимальное множество, которое включает D Amin (напоминаем, что чем больше A, тем меньше множество D A ). Заметим, что каждое из множеств D 35 и D 21 входит в множество D 7 . Объединение D 35 + D 21 тоже входит в D 7 . Смотри рисунок 2. Поэтому наибольшее значение A равно 7. Ответ: 7 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 22 Рисунок 1 Рисунок 2 Задача 3. Для какого наименьшего натурального числа А формула: ДЕЛ(x, А) (ДЕЛ(x, 21) + ДЕЛ(x, 35)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Решение: Запишем формулу из условия в наших обозначениях: 1 ) ( 35 21 D D A Раскроем импликацию по правилу B A B A : 35 21 35 21 ) ( D D A D D A Мы свели задачу к базовой Задаче2, где B= 35 21 D D . Ее решение: D Amax 35 21 D D - это множество чисел, которые делятся на 21 или на 35. Получить такое множество, точно соответствующее выражению, с помощью функции ДЕЛ невозможно. Нужное нам множество должно входить во множество 35 21 D D , например, совпадая с одним из множеств D 35 или D 21 , или располагаясь внутри любого из них, что возможно, если использовать делители, кратные 21 или 35. В качестве A можно выбрать число 21 или 35, т.к. D 21 ≤D 21 +D 35 и D 35 ≤D 21 +D 35 . А вот числа, меньшие, чем 21 выбирать нельзя, т.к. в этом случае множество DA не будет подмножеством D 21 +D 35 . Например , при выборе A=7 множество D 7 содержит числа 7, 14, 28 и др., которые не делятся ни на 21 ни на 35. В задании требуется найти НАИМЕНЬШЕЕ значение, этому условию соответствует 21. Ответ: 21 Задача 4. Для какого наименьшего натурального числа А формула: ДЕЛ(x, А) (¬ДЕЛ(x, 21) + ДЕЛ(x, 35)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Решение: Запишем формулу из условия в наших обозначениях: 1 ) ( 35 21 D D A Раскроем импликацию по правилу B A B A : 35 21 35 21 ) ( D D A D D A Мы свели задачу к базовой Задаче2, где B= 35 21 D D . Ее решение: D Amax = 35 21 D D - это множество чисел, которые не делятся неа 21, плюс множество чисел, которые делятся на 35. Пока достаточно тяжело сказать, какое значение A надо выбрать. Удобнее преобразовать выражение к такой форме: 35 21 D D A =(A· D 21 ) D 35 . Это означает, что, если число делится на A и делится на 21, то оно делится и на 35. Если натуральное число x делится на A, то его можно записать в виде x=A· k для некоторого натурального k. Аналогично, если x делится на 21, то x=21· m для некоторого натурального m, а если оно делится на 35, то x=35· q. Представим числа 21 и 35 в виде произведения простых сомножителей: 21= 3· 7, 35= 5· 7. Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 23 Таким образом, при любом значении k число x = A· k = 3 · 7 · m должно делиться на 35 = 5 · 7. Для этого нужно с помощью сомножителя A добавить в произведение A · k = =3 · 7 · m недостающий сомножитель 5, который есть среди простых сомножителей числа 35, но отсутствует среди простых сомножителей числа 21. Этого будет достаточно, чтобы обеспечить делимость числа A· k = 3 · 7 · m на 35, поскольку сомножитель 7 там уже есть. Заметим, что в качестве A можно взять любое число, кратное 5, но минимально возможное значение – это 5. Ответ: 5 3.Задачи на побитовые операции В следующих задачах выражение M&K обозначает поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Введем следующие обозначения: обозначим через D N множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение: D N = {x: x & N ≠ 0}. введем условия: D N =(x D N ), A = (x D A ). Задача 1. Определите наименьшее натуральное число A, такое, что выражение: (x & 53≠0) ((x & 41=0) (x & A≠0)) Тождественно истинно? Решение: Преобразуем исходное выражение, используя свойство импликации B A B A : D 53 ( 41 D A) = (D 53 (D 41 +A) = A + 53 D +D 41 . Таким образом, мы пришли к базовой Задаче1, где B = 53 D +D 41. Ее решение: 41 min 53 41 53 A D D D D D Минимальное множество D Amin определяется одновременным выполнением двух условий: x & 53≠0 и x & 41=0 Рассмотрим, что означают эти условия. Условие x & 53≠0 означает выполнение побитовой конъюнкции (операция «И») над соответствующими битами чисел x и 53, т.е. 53 выполняет роль маски. Запишем число 53 в двоичной системе счисления: 53 = 32 + 16 + 4 + 1 =2 5 + 2 4 + 2 2 + 2 0 = 110101 2 В двоичном коде числа 53 будут равны 1 только биты с номерами 0, 2, 4 и 5. После выполнения побитовой операции «И» сохраняются только те биты числа x, для которых соответствующие биты маски равны 1, остальные, соответствующие нулевым битам маски – обнуляются. Номер бита 5 4 3 2 1 0 53 = 1 1 0 1 0 1 x = a b c d e f x & 53 = a b 0 d 0 f Поэтому: Условие x & 53≠0 означает, что среди битов {5, 4, 2, 0}числа x есть ненулевые; Условие x & 53=0 означает, что биты {5, 4, 2, 0}числа x нулевые. Итак, условие D 53 обозначает, что среди битов {5, 4, 2, 0} числа x есть ненулевые. Условие x & 41=0. Запишем число 41 в двоичной системе счисления: 41 = 32 + 8 + 1 =2 5 + 2 3 + 2 0 = 101001 2 Выполнение условия 41 D означает, что биты {5, 3, 0} числа x - нулевые. Следовательно, если выполняется условие 41 53 D D , определяющее нужное нам множество, то среди битов {4, 2} числа x есть ненулевые. Для всех таких чисел x & 53≠0, где A может быть любым числом, у которого биты 4 и 2 равны 1. Минимальное из таких чисел равно: 2 4 + 2 2 =16 + 4 = 20. Возможен несколько другой подход, при котором логическое выражение сводится к импликации, содержащей A в правой части: A + 53 D +D 41 = 41 53 D D ( 41 53 D D ) A. Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 24 Одновременное выполнение условий D 53 и 53 D означает, что: среди битов {5, 4, 2, 0} числа x есть ненулевые; все биты {5, 3, 0} числа x нулевые. Следовательно, среди битов {4, 2} числа x есть ненулевые. Это минимальное множество определяется условием x & 53≠0, где: A = 2 4 + 2 2 =16 + 4 = 20. Подходят также любые другие значения A, в которых биты {4, 2} равны 1, но все они больше, чем 20. (По условию задачи надо найти наименьшее натуральное число A.) Ответ: 20 Задача 2. Определите наибольшее натуральное число A, такое что выражение: (x & A 0) ((x & 20 = 0) (x & 5 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? Решение: перепишем исходное выражение и преобразуем его, используя свойство импликации B A B A : A ( 20 D D 5 ) = A + ( 20 D D 5 ) = A + D 20 + D 5 . Таким образом, мы пришли к базовой Задаче2, где B = D 20 + D 5 . Ее решение: D Amax = D 20 + D 5 . Максимальное множество определяется выполнением одного из двух условий: x & 20 0 или x & 5 0. Представим числа 20 и 5 в двоичной системе счисления: 20 = 16 + 4 = 2 4 + 2 2 = 10100 2 , 5 = 4 + 1 = 2 2 + 2 0 = 101 2 Как следует из решения предыдущей задачи : условие x & 20 0 означает, что среди битов {4, 2} числа x есть ненулевые; условие x & 5 0 означает, что среди битов {2, 0} числа x есть ненулевые. Объединение этих множеств - это множество чисел, в двоичной записи которых среди битов {4, 2, 0} есть ненулевые. Это максимальное множество определяется условием x & A 0, где: A = 2 4 + 2 2 + 2 0 = 16 + 4 + 1 = 21. Заметим, что заданное условие выполняется и для других значений A, в которых все биты, кроме битов {4, 2, 0}, равны нулю. Например, для A = 4. Но все эти значения меньше, чем 21. Возможен несколько другой подход, при котором логическое выражение сводится к импликации, содержащей A в правой части: A + D 20 + D 5 = 5 20 D D A = 20 D · 5 D A Посмотрим, что следует из одновременного выполнения условий 20 D и 5 D : условие x & 20 = 0 означает, что биты {4, 2} числа x нулевые; условие x & 5 = 0 означает, что биты {2, 0} числа x нулевые. Отсюда следует, что биты {4, 2, 0} числа x нулевые. В результате поразрядной конъюнкции эти биты значения A обнулятся, поэтому они могут быть равны 1, и при этом выражение A останется истинно. Если же какие-то другие биты числа A будут равны 1, то результат будет зависеть от x, потому что соответствующие биты значения x могут быть также равны 1, и в этом случае выражение A будет ложно. Следовательно, максимальное значение A, при котором выполняется условие задачи, равно: A = 2 4 + 2 2 + 2 0 = 16 + 4 + 1 = 21. Ответ: 21 4. Задача на битовые цепочки Задача. Пусть P – множество всех 8-битовых цепочек, начинающихся с 1, Q – множество всех 8-битовых цепочек, оканчивающихся на 000, а A – некоторое множество произвольных 8-битовых цепочек. Сколько Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 25 элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение ¬(x A) (¬(x P) (x Q)) Решение: Введём обозначения: A: x А, P: x P, Q: x Q Запишем условие в виде: ) ( Q P A Раскроем импликацию по формуле: B A B A : Q P A Q P A ) ( Мы получили базовую Задачу1, где B = Q P Ее решение: Q P Q P A min Это множество, состоящее из всех элементов множества P, не входящих во множество Q, то есть все 8- битовые цепочки, которые начинаются с 1 и оканчиваются не на 000. Поскольку всего битов 8, структура всех таких цепочек имеет вид 1****???, где * обозначает любой из двух символов (0 или 1) , а ??? – трёхбитное окончание, не совпадающее с 000. Всего может быть 2 3 = 8 комбинаций из трёх битов, одно из них, 000, запрещено для окончания, поэтому остаётся еще 7 разрешённых вариантов. Общее количество подходящих цепочек находим по правилам комбинаторики, перемножив количество вариантов для каждой части цепочки (1 для первого бита, по 2 для следующих четырёх и 7 для трёхбитного окончания): 1 · 2 · 2 · 2 · 2 · 7 = 112 Ответ: 112 Задачи для тренировки (часть 2) 1. На числовой прямой даны два отрезка: P = [5; 30] и Q = [14;23]. Укажите наибольшую возможную длину такого отрезка A, что формула ) ( )) ( ) (( A x Q x P x тождественно истинна, то есть принимает значение 1 при любом значении переменной х. 2. На числовой прямой даны два отрезка: D = [15; 40] и C = [21; 63]. Укажите наименьшую возможную длину такого отрезка A, что формула (x ∈ D) → ((¬(x ∈ C) /\ ¬(x ∈ A)) → ¬(x ∈ D)) истинна (то есть принимает значение 1 при любом значении переменной х). 3. Элементами множества А являются натуральные числа. Известно, что выражение ¬(x {1, 2, 3, 4, 5, 6}) (¬(x {3, 6, 9, 12, 15}) → (x A)) истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A. 4. Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}. Известно, что выражение: ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A)) истинно (т.е. принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов в множестве A. 5. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула: (¬ДЕЛ(x, А) ДЕЛ(x, 21)) ДЕЛ(x, 14) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 26 6. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула: (ДЕЛ(x, А) ¬ДЕЛ(x, 15)) (ДЕЛ(x, 18) ДЕЛ(x, 15)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? 7. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение: (X & 94 0) ((X & 21 = 0) (X & A 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? 8. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение: (X & A 0) ((X & 56 = 0) (X &20 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)? 9. Пусть P – множество всех 8-битовых цепочек, начинающихся с 11, Q – множество всех 8-битовых цепочек, оканчивающихся на 0, а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение: ¬(x A) ( (x P) ¬(x Q) ) ? 10. Пусть P – множество всех 8-битовых цепочек, начинающихся с 11, Q – множество всех 8-битовых цепочек, оканчивающихся на 0, а A – некоторое множество произвольных 8-битовых цепочек. Сколько элементов содержит минимальное множество A, при котором для любой 8-битовой цепочки x истинно выражение ¬(x A) (¬(x P) ¬(x Q) ) ? |