Законы логики. Равносильные преобразования
1. Закон коммутативности
x y
y
x; x
y
y
x
2. Закон ассоциативности
;
3. Закон дистрибутивности
;
4. Закон Де Моргана
ù ( ù x
ù y ù (
ù x
ù y
5. Закон поглощения
x (x
y)
x x
(x
y)
x
x 0
0 x
0
x
x 1
x x
1
1
6. Закон исключения импликации
x y
ù x
y
7. Закон исключения эквивалентности
x y
(x
y)
(y
x)
8. Закон исключения двойного отрицания
ù ù x x
9. Закон идемпотентности
x x
x x
x
x
10. Закон исключения третьего
x ùx
1 x
ù x
0
Логические следствия.
Определение: Пусть А1, А2,…Аm, В-формулы алгебры высказывания. Формула В-логическое следствие формул А1, А2,…Аm, если при любом наборе истинностных значений, входящих в неё пропозициональных переменных, формула В получает значение истина всякий раз, когда каждая из формул А1, А2,…Аm, получает значение истина.
A
B
И говорят, что А1, А2…Аm влекут логически В.
C, B
C
D
Запятую заменяют конъюнкцией, а логическое следствие - импликацией.
((A B)
(A
C)
(B
(C
D)
Правило вывода в алгебре высказываний.
Определение логического следствия А1, А2…Аm В, тесно связано с понятием тавтология: из А1, А2…Аm
В тогда и только тогда, когда А1, А2…Аm
В является тавтологией.
Очень часто формулы логического следствия записывают: А1, А2,…,Аm
В
Данную формулу называют правилом вывода формулы В из формул А1, A2…Аm.
Данное правило вывода означает : если истинными будут все формулы А1, А2…Аm, то и формула В является истинной. Правила вывода являются теми логическими средствами, с помощью которых мы из одних предложений строим умозаключения о справедливости других предложений.
Итак, всякая тавтология вида А В определяет логическое следствие А
В и значит правило вывода
Рассмотрим примеры тавтологий и соответствующее им правило вывода:
F, (