Конспект_ОСНОВЫ ЛОГИКИ(3)(2). Решение логических задач. Учитель информатики Батракова Л. В
 Скачать 1.45 Mb.
|
|
x y z F z y x 0 1 1 0 z y x 1 0 0 0 z y x 1 0 1 0 В таблице, приведенной в задании, так же три строки, где F=0: ? ? ? F 0 0 1 0 1 0 1 0 1 1 0 0 Сравнивая столбцы этих таблиц, делаем выводы: a. во втором (синем) столбце таблицы задания находится y (одна единица), b. в первом (жёлтом) столбце таблицы задания находится z (в двух строках z=y), c. в последнем (зелёном) столбце таблицы задания находится x (где z=y, там x=¬y). Ответ: zyx Пример 5: Дан фрагмент таблицы истинности для выражения F: x1 x2 x3 x4 x5 F 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x1 не совпадает с F. Решение: Полная таблица истинности выражения с пятью переменными содержит 2 5 = 32 строки. В приведённой части таблицы в двух строках значение x1 совпадает с F, а в одной – не совпадает. Во всех оставшихся (неизвестных) 32 – 3 = 29 строках значения x1 и F могут не совпадать. Всего несовпадающих строк может быть 1 + 29 = 30. Ответ: 30 Пример 6: Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы: x1 x2 x3 x4 x5 x6 x7 x8 F 0 1 0 1 0 1 1 1 1 Каким выражением может быть F? Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 8 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 Решение: Перепишем выражения в более простой форме, заменив «И» ( ) на умножение и «ИЛИ» ( ) на сложение: 1) 8 7 6 5 4 3 2 1 x x x x x x x x 2) 8 7 6 5 4 3 2 1 x x x x x x x x 3) 8 7 6 5 4 3 2 1 x x x x x x x x 4) 8 7 6 5 4 3 2 1 x x x x x x x x В последнем столбце таблицы истинности видим две единицы, откуда сразу следует, что это не может быть цепочка операций «И» (конъюнкций), которая даёт только одну единицу; поэтому ответы 1 и 3 заведомо неверные. Анализируем первую строку таблицы истинности. В ней только два значения - 0 2 x и 1 8 x Для того, чтобы в результате в первой строке получить 0, необходимо, чтобы переменная 8 x входила в сумму с инверсией (тогда из 1 получится 0!), это условие выполняется для обоих оставшихся вариантов, 2 и 4. Кроме того, переменная 2 x должна входить в выражение без инверсии (иначе соответствующее слагаемое в первой строке равно 1, и это даст в результате 1). Этому условию не удовлетворяет выражение 4. Остается один возможный вариант – выражение 2. Ответ: 2 Пример 7: Каждое логическое выражение A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A B? Решение: Полная таблица истинности каждого выражения с пятью переменными содержит 2 5 = 32 строки. В каждой таблице по 4 единицы и по 28 (= 32 – 4) нуля. Выражение A B равно нулю тогда и только тогда, когда A = 0 или B = 1. Минимальное количество единиц в таблице истинности выражения A B будет тогда, когда там будет наибольшее число нулей, то есть в наибольшем количество строк одновременно A = 0 и B = 1. По условию A = 0 в 28 строках, и B = 1 в 4 строках, поэтому выражение A B может быть равно нулю не более чем в 4 строках, оставшиеся 32 – 4 = 28 могут быть равны 1. Ответ: 28 3. Определение, какое имя соответствует предложенному логическому условию. Решать такие задачи можно двумя способами: или на основании рассуждений, используя законы алгебры логики (вариант 1) или используя таблицу истинности (вариант 2). Пример: Какое из приведенных имен удовлетворяет логическому условию: ¬ (последняя буква гласная → первая буква согласная) /\ вторая буква согласная 1) ИРИНА 2) АРТЕМ 3) СТЕПАН 4) МАРИЯ Решение (вариант 1): Конъюнкция истинна, если оба утверждения истинны, т.е. утверждение «вторая буква согласная» - истинно и утверждение «¬ (последняя буква гласная → первая буква согласная)» - истинно. Так как последнее утверждение является отрицанием утверждения «(последняя буква гласная → первая буква согласная)», то оно должно быть ложным. Импликация ложна, если из истины следует ложь. Следовательно, если последняя буква гласная, то первая буква должна быть тоже гласной. Этому условию удовлетворяет слово – ИРИНА. Ответ: 1 Решение (вариант 2): Составим таблицу истинности: Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 9 Имя X1: последняя буква гласная X2: первая буква согласная X3: вторая буква согласная X4: X1 → X2 X5: ¬ X4 Результат: X5 /\ X3 ИРИНА 1 0 1 0 1 1 АРТЕМ 0 0 1 1 0 0 СТЕПАН 0 1 1 1 0 0 МАРИЯ 1 1 0 1 0 0 В таблице выделена строка, соответствующая правильному ответу. Вообще говоря, обнаружив, что условие выполняется уже для первого варианта, остальные варианты ответа можно не проверять. Ответ: 1 4. Определение числа, для которого истинно логическое высказывание. Здесь есть две группы задач: с вариантами ответов (из части А) и без вариантов ответа (из части В). В первом случае задачу можно решить, подставляя ответы в таблицу истинности (метод подстановки) или через преобразование выражения, используя законы алгебры логики. Пример (из части А): Для какого из указанных значений X истинно высказывание ¬((X > 2)→(X > 3))? 1) 1 2) 2 3) 3 4) 4 Решение 1 (прямая подстановка): X X > 2 X > 3 (X > 2)→(X > 3) ¬((X > 2)→(X > 3)) 1 0 0 1 0 2 0 0 1 0 3 1 0 0 1 4 1 1 1 0 Ответ: 3 Решение 2 (использование свойств импликации): 1) обозначим простые высказывания буквами: A = X > 2, B = X > 3 2) тогда исходное выражение можно переписать в виде ¬(A→B)=1 или A→B=0 3) импликация A→B ложна в одном единственном случае, когда A = 1 и B = 0; поэтому заданное выражение истинно для всех X, таких что X > 2 и X ≤ 3 4) из приведенных чисел только 3 удовлетворяет этому условию, Ответ: 3 Пример из части В: Каково наибольшее целое число X, при котором истинно высказывание (50 Решение: Импликация ложна, если посылка истинна, а следствие ложно. В остальных случаях импликация истинна. Пусть выражение 50 Импликация истинна. Наибольшее число – -8. Пусть выражение 50 Ответ: 7 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 10 5. Задачи с интервалами. Для решения этих задач используется метод визуального представления отрезков на числовой оси. Пример 1: На числовой прямой даны два отрезка: P = [14,34] и Q = [24, 44]. Выберите такой отрезок A, что формула ( x A) → ((x P) (x Q) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Если таких отрезков несколько, укажите тот, который имеет большую длину. 1) [15, 29] 2) [25, 29] 3) [35,39] 4) [49,55] Решение: Чтобы упростить выражение, обозначим отдельные высказывания буквами и отобразим интервалы P и Q на числовой оси голубым и фиолетовым цветами соответственно: A: x А, P: x P, Q: x Q Тогда: A → (P Q) Выражение R = (P Q) истинно для всех значений x, при которых P и Q равны (либо оба ложны, либо оба истинны). Отобразим область истинности выражения R = (P Q) на числовой оси жёлтым цветом: Импликация A → R истинна за исключением случая, когда A=1 и R=0, поэтому на полуотрезках [14,24] и [34,44], где R=0, выражение A должно быть обязательно ложно. Никаких других ограничений не накладывается. Из предложенных ответов этому условия соответствуют отрезки [25,29] и [49,55]. По условию задачи из них нужно выбрать самый длинный. Так как отрезок [25,29] имеет длину 4, а отрезок [49,55] – длину 6, поэтому выбираем отрезок [49, 55]. Ответ: 4 Пример 2: На числовой прямой даны три интервала: P = (10, 15), Q = [5, 20] и R = [15,25]. Выберите такой отрезок A, что выражения (x A) → (x P) и (x Q) → (x R) принимают различные значения при любых x. 1) [7, 20] 2) [2, 15] 3) [5,12] 4)[20, 25] Решение (способ 1, отрезки на числовой прямой): Обратите внимание, что интервал P – это открытый интервал. Это необходимо для того, чтобы можно было выполнить заданное условие в точках стыковки отрезков. Чтобы упростить понимание выражения, обозначим отдельные высказывания буквами: A: x А, P: x P, Q: x Q, R: x R перейдём к более простым обозначениям: P A Y , R Q Z Выразим импликации через операции «ИЛИ» и «НЕ»: P A P A Y , R Q R Q Z Заметим, что неизвестная величина A входит только в выражение Y 14 24 x P 44 Q 34 Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 11 Общая идея состоит в том, чтобы построить на числовой оси область истинности для полностью известного выражения R Q Z , а затем дополнить отрезок P до «обратной» области, в которой выражение Z ложно. Это «дополнение» будет соответствовать области A Построим область R Q Z – объединение отрезка R и области вне отрезка Q: Теперь рассмотрим область P (выделена голубым цветом) Чтобы выполнить заданное условие (противоположность значений P A Y и R Q Z при любых x), область истинности выражения P A Y должна совпадать с областью, где выражение Z ложно. Для этого выражение A должно «перекрыть» всю фиолетовую область (возможно, заходя в область P ), но не должно заходить в «жёлтую» область: Из предложенных вариантов ответов этим требованиям удовлетворяет только отрезок [5,12] (ответ 3) Ответ: 3 Решение (способ 2, таблицы истинности): Упростим выражения и введем те же обозначения, что и в первом способе решения. Обратим внимание, что если рассматривать все значения x на числовой прямой, то логические значения формул могут измениться только при переходе через граничные точки заданных промежутков. Эти точки (5, 10, 15, 20 и 25) разбивают числовую прямую на несколько интервалов, для каждого из которых можно определить логическое значение выражения R Q Z x P Q Q R R Q Z x < 5 0 0 1 0 5 < x < 10 0 1 0 0 10 < x < 15 1 1 0 0 15 < x < 20 0 1 0 1 20 < x < 25 0 0 1 1 x > 25 0 0 1 0 Для упрощения записи не будем рассматривать значения формул на концах отрезков, так как это не влияет на решение. По условию выражение R Q Z должно быть НЕ равно выражению P A Y при любых значениях x, отсюда можно найти, каким должно быть значение A для каждого интервала: x R Q Z P A Y P A x < 5 1 0 0 0 10 15 x 25 P 5 20 R Q 10 15 x 25 P 5 20 R Q 10 15 x 25 Q R 5 20 R Q Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’ Учитель информатики Батракова Л.В. 12 5 < x < 10 0 1 0 1 10 < x < 15 0 1 1 любое 15 < x < 20 1 0 0 0 20 < x < 25 1 0 0 0 x > 25 1 0 0 0 Таким образом, среди ответов нужно найти отрезок, который перекрывает отрезок [5,10] и, возможно, заходит внутрь отрезка [10,15]. Из предложенных вариантов ответов этим требованиям удовлетворяет только отрезок [5,12] (ответ 3). Ответ: 3 6. Решение задач на логику рассуждений. Обычно такие задачи решают, используя законы алгебры логики или составляя таблицы. Пример: Перед началом Турнира «Четырех» болельщики высказали следующие предположения по поводу своих кумиров: А) Макс победит, Билл – второй; В) Билл – третий, Ник – первый; С) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс ? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.) Решение 1 (метод рассуждений) 1) Есть «точная» информация, которая не подвергается сомнению - каждый из болельщиков оказался прав только в одном прогнозе. 2) Запишем высказывания болельщиков: 1. Макс победит, Билл – второй; 2. Билл – третий, Ник – первый; 3. Макс – последний, а первый – Джон. 3) Известно, что из двух высказываний каждого болельщика одно истинно, а другое – ложно. 4) Пусть первый болельщик угадал, что Макс победит, тогда третий болельщик ошибся в двух предположениях, а это не соответствует условию задачи. 5) Пусть первый болельщик угадал, что Билл занял второе место, тогда второй болельщик предсказал первое место Нику, следовательно, по предположению третьего, Макс занял последнее место, а Джон – третье. Отсюда имеем: Ник – 1, Билл – 2, Джон – 3 и Макс – 4 место. Ответ: НБДМ Решение2 (табличный метод): Таблицы позволяют не только наглядно представить условие задачи или ее ответ, но и в значительной степени помогают делать правильные логические выводы в ходе решения задачи. 1) Запишем высказывания трех болельщиков в форме таблицы (заголовок строки обозначает место в турнирной таблице): Первый болельщик Второй болельщик Третий болельщик 1 Макс Ник Джон 2 Билл 3 Билл 4 Макс 2) Считая, что два человека не могут оказаться на одном месте, начнем рассматривать эту таблицу с той строчки, где больше всего информации (в данном случае – с первой). 3) Предположим, что Макс действительно занял первое место, как и сказал первый болельщик, тогда: |