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