Какие новые высказывания можно с их помощью построить?
	Как следует определять их истинность?

Вот тут-то мы сразу и облегчим себе задачу, отвечая на поставленные вопросы.

Точно так же, как поступают в алгебре, рассуждая о числах, то есть вводят символы а, b, c, ... и подразумевают под каждым из них  любое число, поступим теперь и мы: введём символы  А, В, С,..., P, Q, R,..., X, Y, Z, означающие любое элементарное высказывание. Теперь их можно трактовать как переменные, принимающие только два значения: "истинно" и "ложно"; их мы тоже обозначим кратко: И и Л.

ОТВЕТ НА ПЕРВЫЙ ВОПРОС: ПОСТРОЕНИЕ СЛОЖНЫХ ВЫСКАЗЫВАНИЙ

Исходя из разговорной практики, мы знаем, что, имея высказывания А и В, можно ещё построить высказывания:

не А (неверно, что А)

А и В

А или В

если А, то В (из А следует В)

А только и только тогда, когда В  (А эквивалентно В, А тождественно В)

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

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

¬ A  для "не А".

A&B  для "А и В"

AVB  для "А или В"

A->B  для "если А, то В"

A~B для "А эквивалентно В"

(¬ A)VB

((A^B)->B)->С

и т.д. Заметим, что без скобок, означающих порядок применения связок, нам было бы трудно по символьной записи восстановить, какова же была цепь рассуждений. Следовательно, скобки являются необходимыми для записи сложных высказываний. Они объясняют нам процесс построения произвольного сложного высказывания из более простых. Такие записи получили название формул логики высказываний.

Чтобы процесс формализации был законченным, следует указать точные

Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы связок, то есть правильно ли построено сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе строится более длинная формула с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы сводится к выделению всех её частей.

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

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

Вы заметили, как много скобок появляется при попытке записать обычные высказывания с помощью формул? Скобочный "частокол" затрудняет чтение формул. Вспомним, что в формуле школьной алгебры число скобок сокращается за счёт определённых приёмов. Например, деление чисел можно записывать, устраивая "многоэтажные" выражения, вводя в рассмотрение числитель и знаменатель дроби. Очень часто применяется метод старшинства операций: возведение в степень старше умножения, а умножение старше сложения в том смысле, что в бесскобочной записи а·b + c принято всегда первым выполнить умножение, а затем сложение. Лишь когда мы отклоняемся от установленного порядка выполнения операций, необходимо указать его, проставив скобки. Например, а·(b + c) сигнализирует о том, что сначала нужно выполнить младшую операцию (сложение), а потом старшую (умножение). Точно так же в логике высказываний были приняты соглашения о старшинстве логических связок: считается, что сильнее всех связывает высказывания связка   "не", за ней идут "и", "или", "если...,то..." и, наконец, связка равносильности "... тогда и только тогда, когда...".

Опираясь на принцип старшинства логических связок, можно правильно прочитать и выражения с меньшим числом скобок, чем этого требуют правила построения формул, и даже бесскобочные: например, AVB^C  говорит о том, что B^C было построено раньше, а затем соединено с А младшей связкой V.

ОТВЕТ НА ВТОРОЙ ВОПРОС: ОПРЕДЕЛЕНИЕ ИСТИННОСТИ СЛОЖНЫХ ВЫСКАЗЫВАНИЙ

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

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

Высказывание "не А" обычно понимается так: если А истинно, то  "не А" - ложно, и наоборот, то есть всегда значение А противоположно значению "не А".   Изобразим описанную картину таблицей:

Такая таблица называется таблицей истинности связки. Она отражает все ситуации влияния значений элементарной переменной на значение сложного высказывания.

Для связки " и" картина выглядит сложнее, так как она связывает два сведения воедино. В житейском смысле мы понимаем высказывание "На улице дует ветер и идёт дождь" как истинное в том и только в том случае, когда оба события "дует ветер" и "идёт дождь"  имеют место одновременно, в остальных случаях оно ложно. Такому пониманию соответствует принятая в ЛВ таблица истинности:

Мы видим, что различных комбинаций возможных значений логических переменных (элементарных высказываний) А и В уже четыре. В дальнейшем дело принципиально не ограничивается определённым количеством логических переменных: их может быть и пять, и сто, любое конечное число. Например, при логическом анализе работы мощных энергосистем ведётся анализ сотен, тысяч электричеких цепей, и элементарными являются высказывания "ток в такой-то цепи есть" либо "тока в такой-то цепи нет". Как тогда перебирать возможные наборы значений логических переменных для таблицы истинности? Как учесть все из них и в то же время не запутаться? Сколько их вообще? Поэтому сразу обратим внимание, что в таблице истинности связки A^B наборы значений двух переменных записаны с учётом определённого принципа, по которому работает счётчик электроэнергии. Мы так и назовём этот принцип - счётчиковый.

А сейчас построим таблицу истинности для логической связки "или". С ней дело обстоит ещё сложнее. Дело в том, что при анализе всевозможных "или"-конструкций в обычной речи выясняется, что существуют разные "или". Пословица "Пан - или пропал" имеет в виду так называемое "разделительное ИЛИ", когда наличие одной альтернативы исключает другую, а вот высказывание "То ли дождик, то ли снег" носит другой оттенок. Ведь возможна погодная ситуация, когда снег и дождь наблюдаются одновременно. Следовательно, мы скажем правду в трёх случаях: когда на улице только дождь, когда только снег, наконец, когда имеет место и то, и другое. И только в одном случае этот "прогноз" неверен: когда ни дождя, ни снега не выпало. Тогда в речи употреблено "соединительное ИЛИ".   Оно и было принято на воружение математической логикой. Таким образом, таблица истинности для связки "или" имеет вид:

Опираясь на житейский смысл связки "Если А, то В", также не совсем очевидно, какой же таблицей истинности трактовать поведение связки. Ведь в логике высказываний мы договорились рассматривать элементарные высказывания только как принимающие значения И либо Л, без анализа их внуренней структуры, тем более без учёта, имеется ли между ними причинно-следственная связь. Таким образом, высказывание "Если дважды два пять, то существуют ведьмы" вполне имеет право на рассмотрение в ЛВ. Как же вычислять для него значение истинности? Рассмотрим аналогию с технологическим циклом производства. Пусть А - посылка, В - заключение связки. Связка работает правильно, если из истинной посылки следует истинное заключение. Мы также не можем "грешить" на работу связки, когда посылка ложна (из некачественного сырья может получиться и плохое, и хорошее изделие, технологический цикл нельзя в этом случае винить, точно так же из ложной посылки можно как следствие вывести и истинное высказывание, и ложное). Только в случае, когда из истинной посылки получается ложное следствие, мы утверждаем, что связка следования сработала неверно.Таким образом, получаем очередную таблицу истинности:

Наконец, приведём таблицу истинности для последней логической связки "А эквивалентно В". С этой связкой как раз всё легко и просто: по смыслу высказывания ясно, что оно выражает факт, что А и В одновременно принимают одинаковые значения:

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

Из примеров 9 и 10 видно, что все формулы ЛВ делятся на три класса: тождественно ложные, тождественно истинные и не принимающие постоянного значения при изменении элементарных высказываний - выполнимые. Кроме того, мы убедились, что по каждой формуле строится единственная таблица истинности. Встаёт вопрос: а не могут ли различные формулы иметь одинаковые таблицы истинности? Иными словами: могут ли различные по форме сложные высказывания тем не менее быть одинаковыми по смыслу? Опыт обычных неформальных рассуждений подтвердждает, что это так, поскольку само высказывание "А тогда и только тогда, когда В" не могло бы иначе возникнуть.

Так мы приходим к третьему фундаментальному вопросу:

	как проверить, являются ли две различных формулы логики высказываний равносильными?

ОТВЕТ НА ТРЕТИЙ ВОПРОС: ПРОВЕРКА РАВНОСИЛЬНОСТИ ФОРМУЛ ЛВ

Напрашивается самый простой из способов: если две формулы построены из одних и тех же переменных, сравниваем их таблицы истинности, выписываемые для одинаково упорядоченных по счётчиковому принципу наборов значений переменных. Если заключительные столбцы этих таблиц (наборы значений формул) совпадают, они, конечно же, равносильны. Тогда факт равносильности формул Ф1  и Ф2  можно кратко выразить записью Ф1 = Ф2  .

Только сразу же отметим, что проверку на равносильность можно проводить для любых двух формул ЛВ. Это довольно тонкий момент. Казалось бы: зачем сравнивать на равносильность формулы АVВ и ((АVB)VC)^(AVB) ? Ясно, что смысл их различный: ведь во второй формуле больше логических переменных используется для её построения?

Но оказывается, не все логические переменные, используемые для конструирования формулы, имеют одинаковый статус! Если таблица истинности показывает, что изменение значения переменной А при любом наборе постоянных значений остальных переменных никак не влияет на значение всей формулы, то эта переменная входит в формулу фиктивно, и может быть исключена в том смысле, что существует формула, выражающая тот же смысл, но не содержащая переменной А! Однако разбираться с вопросом, какие переменные в формуле фиктивны, а какие нет, гораздо проще, не проводя громоздкий анализ таблиц истинности, а применяя аппарат основных равносильностей, которые справедливы в ЛВ. Для установления же основных равносильностей в самом деле не остаётся ничего иного, как сравнение таблиц истинности формул.

Проведём несколько таких сравнений.

СРАВНЕНИЕ 1. Рассмотрим высказывание (A->B)^(B->А)

Строим таблицу истинности, подробную, с учётом всех частей формулы.

Теперь упростим таблицу, выбросив все вспомогательные столбцы.

Из таблицы видно, что это высказывание истинно именно в тех случаях, когда значения  А и В одинаковы. Но ведь именно так ведёт себя и связка A~B ! Вывод: A~B = (A->B)^(B->А)

А поскольку и простые логические переменные, и сложные формулы принимают всегда значения И либо Л, то на самом деле справедлива более общая равносильность:

                                                 (Ф1 )~(Ф2 ) = ((Ф1 )->(Ф2 ))^((Ф2 )->(Ф1 ))

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

СРАВНЕНИЕ 2. Рассмотрим высказывание ¬ A V B . Построив для него окончательную таблицу истинности, получим:

Но ведь это таблица, отражающая картину поведения уже знакомой связки A->B ! Вывод очевиден:

¬ A V B = A->B

И, конечно же, справедлива более общая равносильность

(¬(Ф1 ))V(Ф2 ) = (Ф1 )->(Ф2 )

А это означает, что и связка следования не обязательна для построения формул, выражающих смысл сложных высказываний: можно её исключить, всякий раз заменяя следование на равносильную конструкцию, содержащую только знаки связок "отрицание" и "или". В частности, можно заметить, что связка эквивалентности равносильна высказыванию, содержащему только три связки:  ¬  V ^ . Таким образом, эти логические связки являются основными, а остальные - вспомогательными.

Далее мы рассмотрим таблицу основных равносильностей. Каждое её соотношение можно проверить так же, как мы сделали только что в СРАВНЕНИИ 1 и СРАВНЕНИИ 2.

Поговорим о том, почему в комментариях в основным равносильностям встречаются слова "логическое сложение", "логическое умножение", "логическая единица" и "логический нуль". Очевидно сходство операции ^ c числовым умножением, если И заменить на 1, а Л  - на 0:

0^0 = 0

0^1=1^0=0

1^A = A для любого А.

Поведение же операции V очень напоминает обычное сложение чисел:

0V0 = 0

0V1 = 1

0VA = A для всякого А.

Поэтому за связкой ^ закрепилось название "логическое умножение", а связку V часто называют "логическим сложением", И считается "логической единицей", Л - "логическим нулём".

Однако полного сходства логических операций с числовыми всё-таки нет. Своеобразие их состоит в том, что в отличие от одного распределительного закона в числовой алгебре, в логике высказываний их два : и распределительный закон умножения по отношению к сложению (снятие скобок), и распределительный закон сложения по отношению к умножению (введение скобок). Кроме того, законы двойственности говорят от том, что логические сложение и умножение являются "перевёртышами": отрицание результата логического умножения А и В даёт совпадает с результатом логического сложения отрицаний А и В, и наоборот. Из-за перечисленных свойств связки ^, V были названы двойственными друг другу.

Отношение равносильности для формул ЛВ похоже на отношение равенства величин в числовой алгебре: если Ф1  = Ф2  , а Ф2  = Ф3 , то  Ф1  = Ф3 . Тогда, пользуясь основными равносильностями, можно мыслить себе процесс проверки равносильности так: если удается с помощью применения основных равносильностей преобразовать Ф1  и Ф3  к одной и той же формуле Ф2  , то эти формулы равносильны.

А что значит применить основную равносильность? Это значит: опознать в рассматриваемой формуле правую часть равносильности и заменить на левую, либо наоборот. Причём опознать не буквально, а по принципу подобия: если в формуле есть конструкция (Ф ) V(Ф), то ясно, что из равносильности АVА=А следует, что вместо (Ф ) V(Ф) можно подставить Ф , полученная при этом новая формула имеет такую же таблицу истинности, как и прежняя.

Между понятием равносильности и логической связкой эквивалентности можно заметить тесную связь: если формулы Ф1  = Ф2 (равносильны), то формула (Ф1 )~(Ф2 ) является тождественно истинной, и наоборот, если доказано, что (Ф1 )~(Ф2 ) тождественно истинна, то Ф1 =Ф2  : они всегда принимают одинаковые значения при заданных значениях входящих в них элементарных высказываний.

Таким образом, проверить, являются ли две формулы ЛВ Ф1  и Ф2 равносильными, можно ещё одним способом: определяя,  является ли тождественно истинной формула (Ф1 )~(Ф2 ).

Описанная задача приводит к постановке следующего, важнейшего вопроса логики высказываний:

	Существует ли единый алгоритм, позволяющий проверить для любой формулы ЛВ, является ли она тождественно истинной?