Эта тема в школьной информатике и математике (у некоторых она там) одна из самых "мутных", как мне кажется. Всё же, есть в омуте и добрые черти. Давайте немного поразбираемся во всём этом.
Классические алгоритмы
А таковых нет. Для нас пока нет. Есть таблицы истинности, законы алгебры логики, и многое другое.
А почему так?
Дело, как мне видится, в бесконечности вариантов, о которой я писал ранее. Алгебра логики, что приятно, относится не к обычной математике, а к дискретной, более того, в ней очень мало чисел. Конкретно 2 числа -"1" и "0". "Истина" и "Ложь", если хотите, "True" и "False". (Мне как-то приятнее с числами работать. ) Это говорит о том, что бесконечности у нас не будет, а будет огромное, но вполне конечное и осознаваемое количество путей.
Первоосновы
Алгебра логики - один из многих способов описать смысл с помощью формальных символов. Самое тяжёлое - отличить привычный смысл "по логике вещей" от алгебры логики. От этого и будем отталкиваться.
В алгебре логики есть действия, которые немного напоминают "обычные" математические, но определения у них другие. А, кстати, попробуйте дать определения (точнее, ответить на вопрос "что такое") обычным семи действиям - сложение, вычитание, умножение, деление, корень, степень, логарифм. Увидите, насколько это сложно. К тому же, многие действия можно рассматривать с разных сторон.
Так вот, о действиях логических. Сначала договоримся о правилах действий.
- За один раз можно выполнять только одно действие. Разрешается не записывать результат, а держать в уме, и выполнять следующее.
- При выполнении действий на место действия записывает его результат, а остальное переписывается без изменений, даже если лень писать.
- Каждое действие "знает" свою очередь, ему нельзя лезть вперёд, даже "только спросить". Выполнять действия в строгом порядке.
Эти правила, как две капли воды, походят на правила "обычных" действий в математике.
Часть первая: выполнение действий
Кроме листа бумаги (в клетку) мы воспользуемся таблицами истинности для действий. Надо немного пояснить, что это такое. Вот точно Вы во втором классе зубрили таблицу умножения, так? Точно так же есть таблица... сложения. И вычитания. А почему нет?
Таблицы истинности для логических действий очень походят на таблицу умножения, но записываются немного иначе. Связано это с тем, что таблица умножения содержит числа от 1 до 9, а таблица истинности только 0 и 1.
Найти эти таблицы можно в интернетах, я сюда выложу (откройте картинку в новом окне, чтобы держать перед глазами всё время, а лучше, если возможно, распечатайте)
Давайте будем разбираться, что с этим делать.
Пять таблиц, пять действий. Каждое имеет своё обозначение. Называются они:
- ¬ - Отрицание.
- /\ - Конъюнкция
- \/ - Дизъюнкция
- -> - Импликация
- <-> - Эквиваленция
И выполняются именно в таком порядке: Отрицание - Конъюнкция - Дизъюнкция - Импликация- Эквиваленция.
Как пользоваться таблицами истинности
Так же, как и в обычной математике действия записывают так: пишут два числа, а между ними рисуют знак:
Как выполнять действие? По таблице. В первом примере нам надо найти в таблице умножения столбец, где слева от знака умножения (точки) стоит цифра "9", а потом строку, в которой справа - цифра "2". Таблица умножения:
Правый нижний прямоугольник, вторая строка. В ней написано, что
"если слева от знака "·" стоит 9, справа 2, то результат умножения будет 18".
Я перерисую немного этот прямоугольник - в краткой форме.
В этот раз я использовал названия столбцов. Первый называется "A", второй "B", а третий "A · B". Читается таблица теперь чуть по-другому:
Если в записи "A·B" на месте буквы A стоит "9", а на месте буквы "B" стоит 2, то на месте всей записи "9 · 2" можно написать "18"
В этом смысле, знак равенства из первой, привычной таблицы, означает, что можно заменять как "9 · 2" на "18" , так и наоборот - "18" на "9 · 2" . Точно так же может выглядеть, например, таблица сложения.
Видите, что строки отличаются? Значит, разные действия дают разный результат. ("Во, автор Америку нам открыл!"). Как определяем, какую таблицу надо брать? По знаку действия. Знак у нас " · " - тогда таблицу для умножения.
Теперь ко второму примеру 1 \/ 0. Ищем таблицу с таким же знаком.
На месте буквы A стоит 1, а на месте буквы B стоит 0. Ищем такую строку, где в колонках именно такая ситуация. Это вторая строка. Значит всё выражение " 1 \/ 0 " мы можем заменить на (что в соответствующей колонке?) на 1.
Именно так выполняются действия.
Я так подробно написал про умножение, потому что многие выполняют его "на автомате", и не могут воссоздать процедуру использования таблицы, чтобы перенести её на новую таблицу для другого действия.
Можно было бы перерисовать, кстати, таблицу истинности в полной форме:
В случае умножения и сложения, в которых нужно уметь работать с числами, не входящими в зазубренную часть таблицы, приходится использовать хитрые способы, которые позволяют обойтись только малыми таблицами и их комбинациями (алгоритмы столбиков, уголков и пр.)
А в случае логических действий, в таблицы занесены ВСЕ возможные комбинации, и Вы не придумаете таких, которые выходят за рамки таблицы.
Потренируйтесь выполнять действия сами:
- выписывайте пример карандашом,
- по знаку находите нужную таблицу,
- по цифрам - строку,
- а потом конструкцию с действием стираете ластиком, а на её месте пишете результат, взятый из таблицы.
Вот Вам для тренировки:
Как поступать, когда у нас есть несколько действий?
Так же, как в математике - определять порядок действия. Для этого надо писать над каждым знаком действия его очередь. Примерно так:
1 -> 1 /\ 1 <-> ¬ 0
Считаем, сколько тут действий (по значкам) и определяем, что это за действия по списку:
- ¬ - Отрицание.
- /\ - Конъюнкция
- \/ - Дизъюнкция
- -> - Импликация
- <-> - Эквиваленция
Определили? Теперь над каждым надо написать его очередь.
конструкция, которая относится к первому действию - " ¬ 0 ". Мы должны стереть всё это ластиком и записать 1
После изменений у нас получится
Теперь что делать дальше? Стираем порядок действий - он у нас уже плохой, потому что цифра "1" стоит не над действием, а над числом - и пишем заново.
Начинаем сначала. Попробуйте уже сделать это самостоятельно.
Что делать, если есть несколько действий одного ранга?
Они выполняются по одному слева направо. Сначала самое левое, потом следующее и так далее. Исключение составляет ситуация с двойным отрицанием (оно по правилам должно писаться со скобками, но некоторые учителя пишут подряд).
И кстати, о скобках. Они нужны для того же, для чего и в обычной математике - чтобы в скобках действия делать вперёд.
Потренируйтесь сами. Сначала расставлять порядок действий, потом их выполнять. (ответы я дам в конце статьи)
Часть вторая: Преобразования
В некотором роде, выполнение действий - тоже преобразования. Самые примитивные, но тем не менее, так что можете считать, что уже о преобразованиях знаете достаточно.
Суть преобразований в замене одних действий другими.
Для чего это надо? Не важно, для чего. Мы просто можем это сделать потому что можем. Хотя, чаще всего, главная цель - облегчить вычисления (хотя, куда ещё облегчать-то). Для этого идут законы...
Законы
Что есть закон в смысле формулы? Запись вида "что-то = что-то_другое".
Позволяет полностью заменять запись "что-то" на запись "что-то_другое" и наоборот.
В формуле используются буквы. Это самое трудное. Вы должны определить, какие конструкции стоят на местах каких букв, иначе ничего не выйдет. Я бы делал это так.
Попробуем применить одну формулу к выражению
Перво наперво, надо определиться с действиями (они должны точно соответствовать либо левой, либо правой частям формулы (я их закрасил разными цветами на второй картинке). В выражении у меня есть отрицание и импликация. В формуле слева стоит только импликация, справа отрицание и дизъюнкция. Совпадений нет, но мы и не надеялись. Расставим порядок действий (везде) и посмотрим, чтобы совпадали последние действия.
Последнее действие в выражении совпадает с последними действиями в левой части формулы. Следовательно, мы имеем вид выражения "A -> B".
(определению вида выражений надо посвящать отдельную статью, здесь я ограничусь только этим)
Будем заменять левую часть формулы на правую (применять формулу слева направо)
Сейчас нам надо отдельно записать выражение и только левую часть формулы, чтобы определить, что стоит на месте буквы A, а что - на месте буквы B:
Определять это надо опять по знакам действий. В формуле буква A стоит слева от знака, значит, на месте буквы A стоит всё, что слева от знака импликации. Ну, то есть, "¬ 1". Аналогично с буквой B: там будет стоять "0".
Теперь нам надо взять чистый лист и записать новую форму (правую часть формулы) и буквозначение:
И последний шаг - вместо букв надо писать то, что у нас в обозначениях. ВАЖНО: действия вне букв писать как есть:
То, что у нас получилось в конце - и есть результат применения формулы к выражению. Обратите внимание: изменились действия, а числа остались те же самые. Иногда меняются даже числа - всё зависит от формулы. Вспомните формулу "основное свойство дроби": там вообще с одной стороны чисел меньше по штукам.
Итак, полная запись была бы, например, такой:
А учитель на доске кратко запишет вот как:
Таким же хитрым способом можно выполнять и преобразования более сложных выражений (нам пока недосуг) и даже - тсссс! - выражений в математике!
Составление таблиц истинности
является важным умением. По сути, если у Вас есть выражение с буквами (A, B, x, y, w, z и т.д.), то Вам надо посчитать его значение при всех возможных комбинациях, когда на месте букв стояли бы "0" или "1".
Возьмём выражение "A \/ ¬ B". В нём две буквы. Как на места букв можно расставить "0" или "1"? Например, вместо "A" поставить "0", а вместо "B" - "1". Тогда получится "0 \/ ¬ 1". Сможем вычислить? Безусловно! Только что же учились. Получится "1".
Это все варианты? Нет, ещё можно наоборот, вместо "A" поставить "1", а вместо "B" - "0". Тогда получится "1 \/ ¬ 0". Сможем опять вычислить? Результат будет, возможно, другой, но будет. Так вот, нам надо загнать все эти варианты в таблицу. Сначала так:
А теперь в краткой форме, с буквами (как в таблице умножения)
А если букв будет больше, например, будут три разные? То и таблица будет больше:
Это далеко не всё, что полезно знать об алгебре логики, но этого будет достаточно, чтобы сдать, к примеру, ЕГЭ. Мы рассмотрели не все действия (всего их 16), не все формулы (их куда больше), даже не все методы. Нам должно хватить. Примеров для преобразований и составления таблиц истинности я не даю, ибо они есть в учебниках и интернетах, а вот простых для вычислений что-то я не видел.
Ответы и решения
1 | 0
0 | 0
1 | 1
0 | 0
подробное решение:
PS
Получился такой учебник, хотя я-то как раз хотел сделать наоборот. Ну, что же, давайте работать с этим. Если что-то непонятно, и надо разъяснить подробнее, пишите в комментариях. Ставьте лайки, если нашли что-то новое для себя.