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