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

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

Алфавит логики высказываний содержит следующие символы: высказывания (иначе называемые высказывательными переменными); логические символы &, , и ~; скобки (и), которые меняют порядок выполнения логических операций. Любой набор символов алфавита (даже бессмысленный) называется словом. Формулы – это подмножество слов.

Формулы A и B (A B) равносильны, если они зависят от одного и того же списка переменных и на любой оценке списка их значения совпадают. Другими словами, формулы равносильны, если совпадают их таблицы истинности. 1). А В В А коммутативность

2). А А А идемпотентность

3). А (В С) (А В) С ассоциативность

4). А В В А коммутативность

5). А А А идемпотентность

6). А (В С) ( А В) Сассоциативность

7) А (В С) ( А В) (А С) дистрибутивность относительно

8) А (В С) ( А В) (А С) дистрибутивность относительно

9). А (А В) А первый закон поглощения

10). А (А В) А второй закон поглощения

11). А А снятие двойного отрицания

12). (А В) А В первый закон Моргана

13). (А В) А В второй закон Моргана

14). А ( А В) (А В) первая формула расщепления

15). А ( А В) (А В) вторая формула расщепления

Приведём правило равносильных преобразований, с помощью которого можно переходить от одних равносильностей к другим. Пусть A B и C – произвольная формула. Тогда A B, A&C B&C, A C B C, A C B C, C A C B, A~C B~C.