Всем привет!
Данный способ можно применять как "оружие последнего шанса", если вдруг никак не получается закончить решение "умными" логическими рассуждениями. Начнем сразу с примера (всего их будет 3, так что если лень читать подробный разбор — переходите сразу к примерам 2 и 3 ниже ну или к видео):
Пример 1
Логическая функция F задана выражением
((x ∧ w) ∨ (w ∧ z)) ≡ ((z → y) ∧ (y → x))
Дана частично заполненная таблица, содержащая неповторяющиеся строки полной таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
Исходим из того, что вы уже пробовали решать такие задания и имеете некоторый опыт работы с логическими операциями. Заметим только, что во второй и третьей строках есть пропущенные значения — на этих местах могут стоять либо 0 либо 1 — следовательно, для любой из этих строк подойдет как комбинация "1 0 0 0" так и "1 0 1 0".
Таблица у нас частичная, неплохо бы построить полную (чтобы выбрать из нее недостающие строки), не так ли?
Собственно с этого и начинается решение таких задач. Сразу отметим, что порядок строк в нашей полной таблице (которую мы построим чуть ниже) не будет соответствовать порядку строк во фрагменте задания (в задачах этого типа они переставлены специально). Говоря проще — первая строка в задании может быть хоть в середине хоть в конце полной таблицы истинности, да где угодно, аналогично остальные.
Чуть отвлечемся на общие рассуждения — есть три пути решения этой и подобных задач:
- Построить таблицу истинности в Excel для всех возможных комбинаций значений x, y, z и w. Таких комбинаций будет 16 (переменные могут принимать два значения 0 и 1, комбинация состоит из 4 переменных, значит количество их 2*2*2*2 = 2^4 = 16, согласно принципу умножения в комбинаторике). Т.е. в таблице будет 16 строк. Долго? Добавим, что вы должны еще неплохо знать логические функции в Excel да и вообще иметь общий навык его использования.
- Ручной метод — выполнить все то же самое на листочке, что также долго, но иногда даже быстрее, чем в Excel, при условии, что вы хорошо знаете логические операции и внимательны к скобкам.
- Программное решение — очевидно, самое быстрое (программа на Python позволяет получить таблицу всех комбинаций значений x, y, z и w всего пятью строчками), на нем и остановимся:
Такая конструкция называется вложенными циклами, для всех возможных x (а их всего два, как мы помним — 0 и 1), происходит перебор всех y (так же из 0 и 1), далее то же самое происходит для z и w. Обратите внимание, что оператор range в Python требует добавлять единичку к конечному значению диапазона, т.е. x in range(0,2) будет использовать значения не 0,1,2 а лишь 0 и 1. Порядок переменных в столбцах ответа — x,y,z,w (так же, как в циклах программы).
Как быстро и без ошибок добавить нашу логическую функцию в программу?
Напишите внутри последнего цикла условие if ( )==True:
Вставьте внутрь скобок вашу логическую функцию как есть ((x ∧ w) ∨ (w ∧ z)) ≡ ((z → y) ∧ (y → x)) и закомментируйте эту строку (Ctrl+/). Чуть ниже вставьте еще раз и замените математические символы на операторы Python, запустите и получите готовую программу и результат:
- ∧ (конъюнкция, логическое умножение) заменяется на and
- ∨ (дизъюнкция, логическое сложение) заменяется на or
- ≡ (эквиваленция, логическая равнозначность) заменяется на ==
- → (импликация) заменяется на <=
- ¬ (отрицание), заменяется на (not( )), например ¬A станет (not(A)). Обратите внимание, что отрицание и его аргумент я рекомендую всегда заключать в скобки, например ¬(A ∨ B) в Python запишется как (not(A or B)). Игнорирование скобок может привести к печальным ошибкам, хотя где-то вы можете встретить запись без них (при этом программы работают правильно).
Также само условие целиком ВСЕГДА заключайте в скобки (хотя, аналогично, где-то вы можете увидеть решения и без них и кто-то назовет их избыточными). Так вот, избыточные скобки — не ошибка, ставьте их в упомянутых случаях всегда (здесь мы не будем отвлекаться на особенности Python, об этом всегда можно почитать в других источниках, посвященных непосредственно языку).
Имея формулу перед глазами, сделать ошибку (или пропустить скобки) крайне сложно, жаль, что если задание на бумаге, это повторить не получится. Также могу порекомендовать при решении задач на Python копировать условие в окно редактора и отключать его комментарием, во-первых, условие всегда перед глазами, во-вторых, спустя время, не нужно будет ломать голову, что это за программа и для какой задачи она написана.
В результате выполнения программы мы увидим только те строки, которые соответствуют условию истинности логической функции ((x ∧ w) ∨ (w ∧ z)) ≡ ((z → y) ∧ (y → x)). Кстати, фрагмент "==True" в программе можно убрать из условия, по умолчанию Python сразу предполагает, что условие должно быть истинным (не забудьте оставить двоеточие). При этом внимательно читайте условие — в ряде задач логическая функция принимает ложные значения, тогда условие выглядит так: if (функция) == False:
А дальше самое интересное — несмотря на то, что мы очень быстро получили таблицу истинности (в отличие от ручного и Excel-методов), вывод о порядке переменных x,y,z и w предстоит также сделать аналитически, что-то вроде: "заметим, что только в одной строке три раза единица, значит это первая строка таблицы" или "очевидно, второй столбец соответствует x".
А что если ну вот никак не заметим и вообще не очевидно? Здесь и возникают самые большие трудности.
Попробуем обойти этот этап методом "тупого" перебора комбинаций типа "xyzw","xzyw","xzwy" и т.д. Какая-то из них верная, значит, в ней обязательно будут те же самые строки, что и в нашей таблице.
Бред, скажете вы, их 16 штук и в них легко запутаться (тем более, что мы их еще не составили). Но у нас под рукой Python, нажимаем Ctrl+N и в окне рядом пишем короткую программку в три строчки (можно в том же окне, просто временно закомментируйте предыдущую программу):
Как вы видите, программа выдала все возможные перестановки переменных x,y,z и w. Мы подключили модуль для комбинаторики itertools (не требует дополнительной установки и доступен везде, где есть Python), затем создали список перестановок строки "xyzw" функцией itertools. permutations() и циклом вывели его на экран. А дальше что? Опять вручную подставлять? Добавим слово "print" к выдаче программы и удалим апострофы (одинарные кавычки) из предыдущего результата функцией replace:
Скопируем результат из терминала в первую программу и закомментируем все строки, кроме первой, запустим программу:
Теперь "ручной" перебор уже не кажется таким страшным?) Последовательно запускаем, смотрим строки, соответствующие строкам таблицы в задании (в прямом порядке слева направо, именно так, как в задании), если их нет, переходим к следующему print, закомментировав предыдущий (напомню, комментарий быстро ставится и снимается комбинацией Ctrl+/). Искать лучше по одной полностью заданной строке, если она есть, смотрим другие.
Да, запустить придется максимум 16 раз (а может и меньше, если правильная комбинация выше, и да, это повод задуматься, проявить творческие способности и доработать программу для выдачи конечного результата сразу). При всем этом — что мешает подумать и аналитически определить одну из переменных, а затем просто перейти к той части списка, где она стоит на нужном месте? Ну а если уж не получается, то проверим все комбинации. В данной задаче при активной строчке print(y, z, w, x):
мы видим строку "1 0 1 1" (в точности соответствует нашей первой строке в таблице задания). Также есть строка "1 0 0 0" (подходит ко второй и третьей строке задания) и строка "1 0 1 0" (также подходит ко второй и третьей строкам). Еще раз напомню, что при поиске не нужно менять местами элементы строк, строки должны выглядеть в точности, как в таблице. Итак, правильный ответ — "yzwx".
На решение этим способом вряд ли уйдет более 10 минут (вместе с написанием программы, а она всегда примерно такая же — отличаться могут лишь условия и количество переменных). А вот если рассмотренный код из 10 строчек вам кажется сложным — то новости для вас только плохие — не думаю, что решение сдавать информатику было правильным, могу лишь посоветовать пересмотреть подход к подготовке.
В заключение решим еще пару задачек, на этот раз без подробных комментариев.
Пример 2
Логическая функция F задана выражением (¬y → (z ≡ w)) ∧ ((z → x) ≡ w). Ниже приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
Используем ту же самую программу, перепишем лишь условие:
При комбинации zwyx видим две строки: "1 1 0 1" и "0 1 1 1", в точности повторяющие строки в таблице задания, а для третьей строки подходит комбинация "0 1 1 0", поскольку искомая строка в таблице выглядит как "0 _ _ 0". Ответ — "zwyx".
Пример 3
Дан фрагмент таблицы истинности логической функции F
¬ (y → x) ∨ (z → w) ∨ ¬z
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Здесь мы видим, что при активной строке print(y, x, z, w) программа выдает три строчки, каждая из который может быть подставлена в таблицу:
"0 0 1 0" встанет в первую строчку "_ 0 _ _"
"0 1 1 0" во вторую строку "0 1 _ _"
"1 1 1 0" в третью строку "1 _ _ 0"
Следовательно, ответ — "yxzw". Но неужели не будет еще подходящих комбинаций? Можете проверить все остальные — их действительно больше не будет, решение единственное и верное.
Данный метод не потребуется, если вы и так неплохо решаете подобные задачи, но даже в этом случае он может пригодиться для проверки результата, достаточно подставить полученную вами комбинацию в последнюю строку исходной программы (без перебора вариантов).
Удачи!
P.S. Если интересна тема ЕГЭ по информатике — подписывайтесь, оставляйте комментарии, могу рассмотреть также "ручные" и Excel-решения этой темы и других, есть ряд примеров на Pascal (хотя никому не рекомендую решать на нем в 2023).