Практические приложения алгебры высказываний
1.2 Равносильные формулы алгебры высказываний
Две формулы алгебры высказываний А и В называются равносильными или эквивалентными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.
Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.
Например, равносильны формулы:
Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.
Например, тожественно истинны формулы
Формула А называется тождественно ложной (или противоречием), если она принимает значение 0 при всех значениях входящих в нее высказываний.
Например, тождественно ложна формула .
Формула А называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.
Например, выполнима формула .
Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.
Между понятиями равносильности и операцией существует следующая связь: если формулы А и В равносильны, то формула АВ - тавтология, и обратно, если формула АВ - тавтология, то формулы А и В равносильны.
Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.
1.Равносильности алгебры Буля:
1.Закон двойного отрицания:
2. Коммутативность:
3. Ассоциативность:
4. Дистрибутивность & относительно:
5. Дистрибутивность относительно &:
6. Законы де Моргана:
7. Законы поглашения:
8. Законы идемпотентности:
9. Свойства констант:
10. Закон противоречия:
11. Закон исключения третьего:
2. Равносильности, выражающие одни логические операции через другие:
12.
13.
14.
15.
16.
17.