Формулы и их равносильности. Основные равносильности алгебры высказываний.

Всюду далее под переменным высказыванием будем понимать специальную переменную величину, которая может принимать только два значения: И или Л. Символы И и Л (и только они) будут обозначать постоянные высказывания; т. к. любое постоянное высказывание принимает лишь одно из этих значений; т. о. в отличие от предыдущего пункта далее все прописные латинские буквы (включая и первые: А, В, …) будут обозначать переменные высказывания. Введём понятие формулы алгебры высказываний.

Определение. 1). Каждое постоянное высказывание (И, Л) и каждое переменное высказывание (А, В, …,Y, Z) есть формулы алгебры высказываний. 2). Если a и b - формулы алгебры высказываний, то (a&b), (a b), (aÞb), (aÛb),(Øa) также – формулы алгебры высказываний. 3). Перечисленные в пунктах 1) и 2) выражения и только они являются формулами алгебры высказываний.

Примеры. 1). ((АÚВ)ÞС), ((АÙ )Û(СÞD)), ((АÚ )ÞС) - формулы алгебры высказываний. 2). ÙВ), АÚ, (ВÞС - не являются формулами.

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

а) опускать внешние скобки в записи формул;

б) не заключать в скобки формулу или её часть, находящуюся под знаком отрицания;

в) считать, что каждая из операций последовательности: &, Ú, Þ, Û связывает сильнее, чем любая из последующих, и выполнять операции в порядке убывания силы, если скобки не предписывают противное.

Следуя этому правилу, например, формулу (((`АÙВ)ÚС)ÞD) можно записать проще

`А ÙВÚСÞD. Каждому набору значений переменных, входящих в данную формулу, соответствует единственное значение самой формулы (либо И либо Л). Например, если в формуле ÙВÚСÞD переменные А, В, С, D принимают соответственно значения И, Л, Л, И, то формула примет значение`ИÙЛÚЛÞИ º ЛÙЛÚЛÞИ º ЛÚЛÞИ º ЛÞИ º И.

Определение. Две формулы a и b называются равносильными, если они принимают одинаковые значения при каждом наборе значений переменных, входящих в a и b.

Символ a º b означает, что формула a равносильна формуле b.

Теорема. Отношение равносильности формул обладает свойствами:

1). Каждая формула равносильна сама себе: a º a (свойство рефлексивности).

2). Если a º b, то b º a (свойство симметричности).

3). Если a º b и b º g, то a º g (свойство транзитивности).

Доказательство непосредственно вытекает из определения. Три приведённых свойства означают, что отношение равносильности является отношением эквивалентности.

Теорема. Для любых переменных высказываний А, В, С справедливы равносильности:

1). (АÚВ)ÚС º АÚ(ВÚС); 1)` (АÙВ) ÙС º АÙ (ВÙС) (ассоциативность операций Ù и Ú);

2). АÚВ º ВÚА; 2)` АÙВ º ВÙА (коммутативность операций Ù и Ú);

3). АÚ(ВÙС) º(АÚВ)Ù(АÚС); 3)` АÙ(ВÚС) º(АÙВ)Ú(ВÙС) (дистрибутивность дизъюнкции относительно конъюнкции (3)) и конъюнкции относительно дизъюнкции (3)`);

4). АÚЛ º А; 4).` АÙИ º А;

5). АÚИ º И; 5)` АÙЛ º Л;

6). АÚА º А; 6)` АÙА º А (идемпотентность дизъюнкции и конъюнкции);

7). Ø(ØА) º А (закон двойного отрицания);

8). `Л º И; 8)` `И º Л;

9). АÚВ º`А Ù`В; 9)` АÙВ º`А Ú`В (теоремы А. де Моргана).

Доказательство каждой из этих равносильностей можно провести с помощью таблиц истинности. Докажем, например, 9):

Четвёртый и седьмой столбцы таблицы совпадают. Это показывает, что при каждом наборе значений переменных А и В формулы Ø(АÚВ) и (ØА)Ù(ØВ) принимают соответственно одинаковые значения, т.е., по определению, являются равносильными.

Как видим, алгебра высказываний, как и алгебра множеств, является булевой алгеброй.

Если в любой из равносильностей последней теоремы любое переменное высказывание заменить всюду и одинаково одной и той же формулой, то получим новую равносильность. Например, первая теорема де Моргана после замены А на a и В на b даёт равносильность Ø(aÚb) º (Øa)Ù(Øb), где a и b - произвольные формулы.

Далее. Заменяя в любой формуле любую её часть равносильной этой части формулой, получим формулу, равносильную данной. При этом предполагается, что эта часть формулы сама должна быть формулой. Возьмём, например, формулу СÞØ(АÚВ). Согласно последней теореме Ø(АÚВ) º (ØА)Ù(ØВ). Поэтому, выполнив указанную выше замену, имеем равносильность С ÞØ(АÚВ) º С Þ (ØА)Ù(ØВ).