12. Элементы алгебры логики

Формальная логика. Высказывания и их виды

Слово «логика» происходит от греческого «логос» — «рассуждение, мысль, разум, смысл». Логика нужна нам не только для решения головоломок, математических задач и в целом во время обучения в школе. Логика сопутствует нам всё время на бытовом уровне. Мы применяем её для оценки последствий своих действий:

• Стоит ли выполнить дополнительное домашнее задание, чтобы повысить оценку?

• Если пойти по этой улице, будет ли путь короче?

Применяем логику и для аргументации своих слов: объясняя родителям, почему получили так много троек, или же доказывая другу, почему этот фильм лучше.

Логикой интересовались ещё со времен Древней Греции. Аристотель, один из виднейших мыслителей того времени, достаточно долго изучал вопросы, которые касаются логики. Это в конечном итоге привело его к созданию науки, которую позже стали называть формальной логикой. Суть её состоит в том, что она описывает обобщённые понятия, оперирует структурой высказываний, а не их конкретным содержанием.

Чтобы понять, что это означает, разберём пример. Скорее всего, вы слышали выражение «третьего не дано», то есть что-либо или есть, или его нет. Это как раз один из законов формальной логики — закон исключённого третьего.

Записать его можно так: верно либо «А», либо «не А». Причём под «А» может пониматься любое высказывание. Часы или идут, или не идут. Флаг либо красный, либо не красный. Третьего не дано. Причём в рамках формальной логики мы не работаем непосредственно с содержанием. То есть мы не уточняем:

• Какой это оттенок красного на флаге? Считается ли он красным или нет?

• Если на красном флаге есть синий круг, то можно ли назвать флаг красным?

Этими вопросами формальная логика не занимается.

Стоит отметить, что именно на законе исключённого третьего основан один из популярных математических методов — метод доказательства «от противного». Подробнее о нём вы можете узнать в ответвлении.

Метод доказательства «от противного»

Суть метода доказательства «от противного» заключается в следующем. Пусть нужно доказать, что утверждение «А» истинное. Тогда достаточно доказать, что «не А» — ложное. Действительно, из «А» и «не А» одно точно должно быть истинным. То самое «третьего не дано». Если докажем, что «не А» не является истинным (то есть ложно), то из этого сразу следует, что истинным будет утверждение «А».

Сам метод используют так:

• Предположим, что утверждение «не А» истинное.

• Исходя из этого предположения, получим какое-то противоречие.

• Из этого следует, что «не А» — ложное, тогда «А» — истинное.

Разберём на классическом примере. Нужно доказать, что число— иррациональное. Это и будет нашим утверждением «А». Предположим обратное: что это рациональное число. Используя математические преобразования, можно получить противоречие. Подробнее об этом — в уроке «Виды чисел». Следовательно, утверждение «не А» — ложное. Значит, утверждение «А» — верное, то есть— иррациональное число.

В повседневной жизни метод «от противного» тоже работает, но нужно быть аккуратными с формулировкой обратного утверждения. Иначе получим неверные выводы.

Например, мы хотим доказать, что все лебеди белые. Предположим, что верно обратное утверждение — «все лебеди не белые». Но мы точно видели белых лебедей, получаем противоречие. Значит, истинно первое утверждение.

Нашли ошибку в рассуждениях? Обратите внимание на обратное утверждение. Оно построено неправильно. Корректным было бы следующее утверждение: существует хотя бы один не белый лебедь. И вот это обратное утверждение уже верно. Значит, исходное утверждение — «все лебеди белые» — неверно.

Существуют и другие законы: закон отрицания и закон непротиворечия, например. Все они основываются на высказываниях. Высказывания — это фундамент формальной логики. Высказывание определяется как повествовательное предложение, которое содержит истинное или ложное утверждение. К примеру, «Земля плоская» — это повествовательное предложение с ложным утверждением, это пример ложного высказывания. А фраза «После воскресенья всегда идёт понедельник» явно имеет истинный смысл, то есть это истинное высказывание.

Про вопросительные и побудительные предложения мы не можем сказать, истинны они или нет. В них нет утверждений. Поэтому определение ограничивается повествовательными предложениями. А фразы «Смотрите, кто пришёл» или «Который час?» не являются высказываниями.

Кроме того, не про любое повествовательное предложение можно однозначно сказать, истинное оно или ложное. Например, про фразу «Днём светит солнце» нельзя точно сказать, истинная она или нет. В один день может быть солнечно — тогда вроде бы истинная; в другой день — пасмурно, тогда ложная. Если бы фраза звучала как «Днём всегда светит солнце», то можно было бы сказать, что это ложное утверждение, так как иногда днём бывает пасмурно. С другой стороны, можно сказать, что солнце светит всегда, даже когда у нас ночь, — ведь сама звезда явно не гаснет.

Поскольку о таких предложениях нельзя однозначно сказать, истинны утверждения или нет, их обычно не относят к высказываниям.

Вернёмся к примерам высказываний. «Земля плоская», «После воскресенья всегда идёт понедельник» — это примеры простых высказываний. Если мы объединим их с помощью логической связки, то получим сложное высказывание. Например: «Земля плоская, и после воскресенья всегда идёт понедельник».

Отличить их друг от друга очень просто: если высказывание можно разбить на несколько меньших высказываний, значит, высказывание сложное. Если нельзя — то простое.

Понятно, что истинность или ложность сложного высказывания будет определяться истинностью или ложностью входящих в него простых высказываний. Как именно, мы поговорим на следующем уроке, когда будем разбирать таблицы истинности.

Отметим ещё одну классификацию высказываний. Их делят на общие, частные и единичные. Общие обычно начинаются со слов «всякий», «все», «всё», «каждый» и тому подобных. Для таких высказываний доказать истинность достаточно сложно. Поскольку если есть хотя бы один объект, не соответствующий высказыванию, высказывание в итоге становится ложным. Такие высказывания обычно проще опровергать, чем доказывать, — достаточно привести контрпример.

Рассмотрим утверждение: «Все статуи созданы из мрамора». Конечно, в мировой скульптуре известны и гипсовые, и бронзовые статуи, поэтому высказывание является ложным.

Частное высказывание сводится к более узкому кругу и обычно начинается со слов «некоторые», «несколько» и тому подобных. Доказывать данные высказывания проще, поскольку для истинности потребуется 2–3 объекта, удовлетворяющих условию. К примеру, «Некоторые статуи созданы из мрамора». А вот опровергнуть такое высказывание сложнее — ведь нужно доказать, что нет ни одной статуи из мрамора (по сути, доказать общее высказывание).

Единичные высказывания ещё больше сужают круг. В них речь идёт уже о конкретном объекте. К примеру, «Самолёт рейса КУ–797 летает только по маршруту Москва — Владивосток».

Алгебра логики и её элементы

Алгебра логики берёт своё начало в XIX веке. Её создателем является Джордж Буль. Суть алгебры логики состоит в том, что переменные могут принимать только два значения, а именно «истинно» или «ложно» (или 1 или 0 соответственно). 

Эту алгебру ещё называют булевой — по имени её создателя. А сами переменные называют булевыми (или логическими) переменными.

Простое высказывание в алгебре логики можно обозначить некой переменной: A, B, C. А сложное высказывание можно построить из этих переменных и связок между ними.

Эти связки называются логическими операциями. Самыми простыми из них являются три операции: И, ИЛИ и НЕ.

Операция «И» обозначается символом «амперсанд»: &. Хотя могут использоваться и другие символы, указанные далее, или не использоваться вовсе. То есть высказывание «А и B» можно записать следующими способами: A & B, A ˄ B, A × B, A * B, AB.

Последние три способа записи, скорее всего, напомнили вам о записи умножения. И действительно, операция «И» — это логическое умножение, которое, в принципе, не отличается от традиционного арифметического умножения. Ведь сложное высказывание «А и В» будет истинным в том и только том случае, когда и А, и В истинные: 1 * 1 = 1.

Если же хотя бы один из множителей равен 0, то и произведение будет равно 0. То есть если ложно хотя бы одно из двух простых высказываний, то и сложное утверждение будет ложным.

С этой операцией вы уже сталкивались в курсе алгебры, рассматривая систему уравнений. Как вы помните, верным решением системы будет только то, которое будет являться корнем и первого, и второго уравнения (и других уравнений, если они есть).

Рассмотрим пример высказывания: «Самолёт может летать И был создан в Древнем Египте». Первое высказывание является истинным, а второе — ложным. Значит, сложное высказывание будет ложным. На языке алгебры логики запишем так: A — это высказывание «Самолёт может летать». B — это высказывание «Самолёт создан в Древнем Египте». A = 1, B = 0, тогда A * B = 0.

Операция «ИЛИ» — это операция логического сложения, которое почти не отличается от арифметического. Обычно обозначается известным нам символом «+», хотя также может использоваться и обозначение «Ú».

Чтобы выражение «А или В» было истинным, достаточно, чтобы хотя бы одна из переменных была истинной: 0 + 1 = 1, 1 + 0 = 1.

Если обе переменные будут истинными, результат тоже будет истинным: 1 + 1 = 1. Этим и отличается сложение в булевой алгебре от обычного сложения. В обычном сложении мы бы получили 2, но в алгебре логики нет значения 2.

Операция «ИЛИ» также могла вам встречаться в курсе алгебры, когда вы рассматривали совокупность уравнений. В ней верными решениями являются те, которые являются корнями хотя бы одного из уравнений системы.

Рассмотрим пример высказывания: «Самолёт может летать ИЛИ был создан в Древнем Египте». Первое высказывание является истинным, а второе — ложным. При этом сложное высказывание является истинным, поскольку первое высказывание является истинным. На языке алгебры логики запишем так: A — это высказывание «Самолёт может летать». B — это высказывание «Самолёт создан в Древнем Египте». A = 1, B = 0, тогда A + B = 1.

Операция «НЕ» отличается от двух предыдущих. Во-первых, она применяется для одной переменной, а не для двух. Операция «НЕ», применённая к истинному высказыванию, даёт ложное высказывание. И наоборот: применяя операцию к ложному высказыванию, получим истинное высказывание. Обычно обозначается чертой над переменной или знаком «¬» перед переменной.

Во-вторых, операция не имеет аналогий в обычной алгебре. Можно провести параллель со знаком «минус» перед выражением, но это будет неверно. Знак «минус», поставленный перед числом 5, даёт нам лишь противоположное число –5. А операция «¬5» скорее означает «все числа, кроме 5».

Разберём пример высказывания. Обозначим как А высказывание «Самолёт летит во Владивосток». Пусть это утверждение верное: А = 1. Тогда высказывание «НЕ А» будет «Самолёт НЕ летит во Владивосток». Соответственно, оно ложное. На языке алгебры логики запишем: ¬А = 0.

Операция НЕ в алгебре логики

Примем во внимание, что «НЕ» можно использовать практически в любом участке высказывания. Тогда уже знакомое нам высказывание «Самолёт летит во Владивосток» можно преобразовать по-разному: «Самолёт НЕ летит во Владивосток», «НЕ самолёт летит во Владивосток», «Самолёт летит НЕ во Владивосток».

Как видите, при использовании одной и той же операции в разных частях высказывания формируются новые высказывания, отличные по смыслу. Получается, операция «НЕ» является неоднозначной? Нет, это не так.

Объяснение кроется в том, что применение «НЕ» в предложении и применение операции «НЕ» в алгебре логики — это разные вещи.

Ставя «НЕ» в разные части предложения, мы действительно получаем разный смысл. Но применяя операцию «НЕ» к высказыванию, мы имеем в виду, что событие «Самолёт летит во Владивосток» не происходит. И это однозначно. Если мы упростим эту формулировку, то в русском языке наиболее близкой по смыслу будет именно «Самолёт НЕ летит во Владивосток».

Диаграммы Эйлера — Венна

Для наглядного представления логических переменных и логических операций удобно использовать диаграммы Эйлера — Венна. В них используются круги и их пересечения.

Леонард Эйлер развил ранее изобретённый Лейбницем метод изображения множеств и предложил использовать круги для изображения высказываний и для решения логических задач.

На рисунке 7 множество В является подмножеством А, а множество А не пересекается с множеством С.

В дальнейшем указанный графический метод был развит Джоном Венном в труде «Символическая логика», в результате чего подобный способ визуализации информации назвали диаграммами Эйлера — Венна.

Основной их идеей является то, что любое высказывание в рамках круга является истинным, а всё, что находится за рамками круга на плоскости, — ложным. Иными словами, это визуализация логической операции НЕ.

Возьмём для примера уже рассмотренное высказывание «Самолёт летит во Владивосток». Изобразим его как круг, обозначив переменной Х. Всё, что не будет входить в этот круг, — это «НЕ Х», иными словами — «Самолёт НЕ летит во Владивосток».

Другой идеей является то, что если мы имеем два высказывания или более, то они обозначаются разными кругами. Для удобства лучше изобразить их разными цветами.

Теперь попробуем визуализировать уже известные нам операции «И» и «ИЛИ». Начнём с логического И. Возьмём высказывания: «Эта футболка красная» (высказывание Х) и «У этой футболки короткие рукава» (высказывание Y).

Только в случае, если оба выражения истинны, сложное выражение «Эта футболка красная, И у неё короткие рукава» является истинным.

Высказывания X и Y истинны внутри своих кругов. Тогда их пересечение будет указывать на область, где они оба истинны. Обозначим это пересечение жёлтым цветом — оно и будет указывать, где истинно сложное выражение «X и Y».

Перейдём к операции логическое «ИЛИ». Возьмём те же высказывания. Результатом использования логического «ИЛИ» будет сложное высказывание «Эта футболка красная или с короткими рукавами». Оно будет истинным для всех красных футболок (вне зависимости от длины рукава). Высказывание будет истинным и для всех футболок с коротким рукавом (вне зависимости от цвета). Получаем объединение этих кругов, оно и будет указывать, где истинно сложное высказывание «X или Y».

Мы разобрали диаграммы на примерах простых логических операций. Но их можно применять и для визуализации других операций, а также для более сложных логических выражений. Но этим мы займёмся на следующем уроке.

На этом урок окончен, спасибо за внимание!

Список литературы

1. Информатика. 8 класс: учебник / Л. Л. Босова, А. Ю. Босова. — М. : Просвещение, 2023.

Домашнее задание

1. Что такое высказывание с точки зрения формальной логики?

2. Как в алгебре логики обозначают простые высказывания?

3. Какие логические связки используются в сложных высказываниях?

4. Какой смысл имеет логическая операция НЕ?

5. Изобразите с помощью диаграмм Эйлера — Венна высказывания:

• Мальчики учатся в 8 классе и любят спорт.

• Девочки любят художественную или спортивную гимнастику.

• Ученики не собирают гербарий.

Список использованных источников

Рис. 1, 2. Изображения используются согласно лицензии Shutterstock / FOTODOM

Рис. 3. Источник: wikimedia.org / название: Uncropped sunburst over Earth / атрибуция: public domain, автор: NASA

Рис. 4. Источник: pixabay.com / автор: GDJ / код изображения: 5689128

Рис. 5, 7, 9–13. Иллюстратор Бумастрова А. В.

Рис. 6. Источник: wikimedia.org / название: Leonhard Euler (1707–1783) / атрибуция: public domain, музей: Deutsches Museum, автор: Jakob Emanuel Handmann

Рис. 8. Источник: wikimedia.org / название: John Venn before being elected to the Royal Society in 1883 / атрибуция: public domain, автор: unknown (Maull & Fox. studio)