"Информатика. Базовый уровень", Босова Л.Л., Босова А.Ю.
Алгебра логики изучает высказывания, которые могут быть истинными или ложными, и операции над ними. Она помогает записывать условия коротко и точно, проверять сложные утверждения и разбирать, при каких значениях исходных высказываний результат будет истинным. Для этого используют значения 1 и 0, логические переменные, операции и таблицы истинности. Эти же идеи применяются в алгоритмах, программах и логических схемах.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Логическое высказывание — это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно. Например, предложение «Число 8 чётное» истинно, а «Число 8 нечётное» ложно. А вот вопрос «Который час?» нельзя оценить таким способом. Это определение нужно, чтобы отличать утверждения, с которыми работает логика, от вопросов и просьб.
Логическая переменная — обозначение высказывания, принимающее одно из двух значений: 0 или 1. Обычно высказывание обозначают заглавной латинской буквой, например A или B. Значение 1 соответствует истине, а 0 — лжи. Переменные позволяют не переписывать длинные утверждения и рассматривать их значения отдельно от словесной формулировки.
Логическая операция — действие над высказываниями, результатом которого становится новое высказывание. Например, к высказыванию можно присоединить отрицание или объединить его с другим с помощью «и» либо «или». Каждая операция подчиняется точному правилу, которое определяет истинность результата. Благодаря этому сложное рассуждение можно выполнить последовательно и проверить.
Логическое выражение строится из логических переменных и операций, а при заданных значениях переменных принимает значение 0 или 1. Например, ¬A ∨ B — выражение из двух переменных и двух операций. Его результат зависит от того, какие значения получили A и B. Понятие выражения нужно, чтобы записывать сложные условия компактно и затем вычислять их значение.
В алгебре логики высказывания рассматривают через два значения истинности, потому что исходный вопрос здесь один: верно утверждение или нет. Для удобства истину условно обозначают числом 1, а ложь — числом 0. Эти числа не показывают количество или величину, а служат короткими метками двух возможных состояний. Так становится проще задавать правила операций и выполнять вычисления.
Отрицание обозначают знаком ¬ и читают «не». Оно меняет истинностное значение на противоположное: если A = 1, то ¬A = 0, а если A = 0, то ¬A = 1. Это правило отражает смысл слов «неверно, что A». Например, если утверждение «Снег белый» истинно, его отрицание «Снег не белый» ложно.
Конъюнкцию A ∧ B читают «A и B»: результат истинен, только когда истинны оба высказывания. Так логическое «и» требует выполнения каждого условия. Дизъюнкцию A ∨ B читают «A или B»; она истинна, если истинно хотя бы одно высказывание, включая случай, когда истинны оба. В быту «или» иногда означает выбор ровно одного варианта, но в логике такое ограничение не подразумевается.
Сложные высказывания можно строить также с помощью импликации и эквиваленции. Импликация A → B читается «если A, то B»: A называют посылкой, а B — следствием; она ложна лишь при истинной посылке и ложном следствии. Эквиваленция A ↔ B читается «A тогда и только тогда, когда B» и истинна, если значения обеих частей совпадают. Эти операции дают возможность точно записывать условные утверждения и ситуации, где два условия равносильны.
Чтобы вычислить выражение, сначала учитывают скобки, а затем выполняют операции в принятом порядке; обычно сначала отрицание, потом конъюнкцию, дизъюнкцию, импликацию и эквиваленцию. Если выражение содержит несколько переменных, для каждой комбинации их значений вычисляют промежуточные части и итог. Все такие результаты записывают в таблицу истинности. Она нужна, чтобы не пропустить возможный набор и увидеть поведение выражения целиком.
| Операция | Обозначение | Чтение | Когда результат равен 1 |
|---|---|---|---|
| Отрицание | ¬A | Не A | Когда A = 0 |
| Конъюнкция | A ∧ B | A и B | Когда A = 1 и B = 1 |
| Дизъюнкция | A ∨ B | A или B | Когда A = 1 или B = 1, либо оба равны 1 |
| Импликация | A → B | Если A, то B | Во всех случаях, кроме A = 1 и B = 0 |
| Эквиваленция | A ↔ B | A тогда и только тогда, когда B | Когда A и B имеют одинаковые значения |
Чтобы пользоваться таблицей, сначала определите, какие части выражения соединены операциями, а затем найдите правило для каждой из них. Для сложного выражения вычисляйте промежуточные результаты по очереди, не переходя сразу к итоговому значению. Особое внимание уделяйте импликации: она ложна только в одном сочетании значений.
Задача 1. Для высказывания A: «Число 8 чётное» определите значение отрицания ¬A. Сначала выясним, верно ли исходное утверждение: число 8 делится на 2 без остатка. Затем применим правило отрицания, которое меняет значение на противоположное. Это позволяет не путать истинность исходного высказывания с истинностью его отрицания.
Ответ: ¬A = 0. Само утверждение о чётности числа 8 истинно, а утверждение «Число 8 нечётное» ложно.
Задача 2. При A = 1 и B = 0 найдите A ∧ B и A ∨ B. Для конъюнкции проверяем, истинны ли оба операнда; для дизъюнкции — истинно ли хотя бы одно. Здесь A истинно, но B ложно, поэтому условия для двух операций дают разные результаты. Сопоставление помогает увидеть, почему знаки ∧ и ∨ нельзя считать взаимозаменяемыми.
Ответ: A ∧ B = 0, A ∨ B = 1. Для проверки достаточно вспомнить: «и» требует истинности обеих частей, а «или» — хотя бы одной.
Задача 3. Постройте таблицу истинности выражения (A ∨ B) → ¬A. Переменных две, значит, нужно проверить четыре сочетания: 00, 01, 10 и 11. Сначала вычислим часть в скобках и отрицание A, а затем применим импликацию. Такой порядок сохраняет структуру выражения и не позволяет принять результат промежуточного действия за итоговый.
Ответ: таблица выражения имеет вид.
| A | B | A ∨ B | ¬A | (A ∨ B) → ¬A |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Ошибка — считать логическими высказываниями вопросы и побудительные предложения. У вопроса нет значения истинности, а просьбу или команду нельзя признать истинной либо ложной; такие формы иногда путают с утверждениями из-за их содержательности. Проверка простая: спросите себя, можно ли однозначно ответить «истинно» или «ложно». Если нельзя, перед вами не логическое высказывание.
Дизъюнкцию часто принимают за исключающее «или», то есть предполагают, что истинно должно быть ровно одно из двух высказываний. Такая трактовка знакома по бытовым ситуациям выбора, но в алгебре логики ∨ истинна и при двух истинных частях. Чтобы проверить себя, подставьте A = 1 и B = 1: значение A ∨ B равно 1.
Некоторые считают импликацию ложной во всех случаях, кроме истинности обеих частей. Это неверно: условие «если A, то B» нарушается только тогда, когда A истинно, а B ложно. Возможно, ошибку вызывает привычка воспринимать импликацию как обычную причинную связь. Для самопроверки найдите случай A = 0: при ложной посылке импликация по правилам логики истинна независимо от B.
Ещё одна ошибка — вычислять сложное выражение без учёта скобок и порядка операций. Тогда можно, например, выполнить дизъюнкцию раньше отрицания или неверно определить, какие части входят в импликацию. Чтобы проверить вычисление, выпишите промежуточные столбцы и обрабатывайте выражение от частей в скобках к целому. Сравните каждую строку с правилами операций, а не только итоговый столбец.
Для работы с алгеброй логики нужно уметь распознавать высказывания и отличать истинные утверждения от ложных. Если предложение нельзя оценить как истинное или ложное, ему нельзя напрямую присвоить значение 1 или 0. Новые знания становятся основой для записи более сложных условий и проверки их результата. Поэтому точное понимание высказывания предшествует изучению операций.
В программировании логические выражения задают условия, от которых зависит выбор действий и продолжение алгоритма. Объединяя условия операциями, можно описать, когда программа должна выполнить нужную команду. Те же правила применяются при анализе логических схем, где результат зависит от сигналов на входах. Таблица истинности позволяет проверить схему или условие для всех возможных сочетаний значений.
Какие предложения считаются логическими высказываниями?
Логическое высказывание — повествовательное предложение, для которого можно однозначно определить, истинно оно или ложно. Например, «Число 8 чётное» — высказывание. Вопросы и просьбы высказываниями не являются.
Чем логическая дизъюнкция отличается от исключающего «или»?
Логическая дизъюнкция, то есть «A или B», истинна, если истинно хотя бы одно из высказываний. Поэтому она остаётся истинной и тогда, когда истинны оба высказывания. Исключающее «или» допускает только один истинный вариант.
В каком случае импликация ложна?
Импликация A → B ложна только тогда, когда A истинно, а B ложно. Во всех остальных случаях она истинна. Здесь A называют посылкой, а B — следствием.
Как правильно составить таблицу истинности сложного выражения?
Сначала перечислите все возможные наборы значений переменных. Затем вычисляйте выражение по частям: учитывайте скобки и порядок операций, записывая промежуточные результаты в отдельные столбцы. Последний столбец покажет значение всего выражения для каждого набора.
Зачем алгебра логики нужна при программировании?
С её помощью записывают и проверяют условия, от которых зависит выполнение команд программы. Логические выражения помогают объединять несколько условий и разбирать все возможные случаи. Те же правила используются при анализе логических схем.
§ 18. Алгебра логики
