§ 2.1. Высказывания и логические связки

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

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

Главное слово в определении — «однозначно». Предложение «Москва — столица Российской Федерации» истинно. Предложение «Ten is greater than three» записано по-английски, но язык роли не играет: оно тоже истинно. Предложение «Число 17 делится на 2» ложно. Все три — высказывания. Высказыванием его делает не правдивость, а то, что у вопроса «истина это или ложь?» есть единственный ответ. Истина и ложь — два значения, которые может принимать высказывание, и третьего алгебра логики не признаёт.

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

Но и повествовательное предложение годится не всегда. Возьмём фразу «Я сейчас говорю неправду». Допустим, она истинна, — тогда говорящий действительно лжёт, и фраза ложна. Допустим, она ложна, — тогда говорящий сказал правду, и фраза истинна. Любой выбор ведёт к противоречию, однозначного значения у фразы нет, и высказыванием она не считается. Другой случай — оценка: «Шахматы — самая увлекательная игра на свете». Один с этим согласится, другой нет, и общего для всех способа проверить такое суждение не существует. Это тоже не высказывание. Порядок проверки собран на рис. 1: сначала смотрим на вид предложения, потом ищем в нём переменную и только затем спрашиваем, можно ли однозначно назвать его истинным или ложным.

Высказывания строят и из знаков формальных языков — математики, физики, химии. «Fe — металл» — истинное высказывание. «Площадь квадрата со стороной a равна 4 · a» — ложное: 4 · a — это периметр, а площадь равна a · a. Числовое выражение само по себе, например «5 + 8» или «XI − IV», ничего не утверждает: это просто запись числа. Но если соединить два выражения знаком равенства или неравенства, получится высказывание. «5 + 8 > 12» истинно, «XI − IV = 6» ложно, потому что одиннадцать без четырёх — семь.

Особый случай — предложения с переменными. «X > 7» говорит о неизвестном числе, и пока значение X не задано, судить об истинности нельзя. Подставим X = 10 — получится истинное высказывание «10 > 7». Подставим X = 7 — получится ложное «7 > 7», ведь число не больше самого себя. Такие предложения называют высказывательными формами.

Высказывательная форма — это повествовательное предложение, в котором есть хотя бы одна переменная и которое превращается в высказывание, когда вместо всех переменных подставлены конкретные значения.