Равносильность формул

1. A ≡A (закон тождества);
2. A&0 ≡ 0;
3. A∨0 ≡A;
4. A&1 ≡ A;
5. A∨ 1 ≡ 1;
6. ¬(¬A) ≡A (закон двойного отрицания);
7. A & (¬ A) ≡ 0 (закон логического противоречия);
8. A ∨ (¬ A) ≡1 (закон исключенного третьего);
9. A & A ≡A (идемпотентность конъюнкции);
10. A ∨A≡A (идемпотентность дизъюнкции);
11. A & B ≡B& A (коммутативность конъюнкции);
12. A ∨B ≡B∨ A (коммутативность дизъюнкции);
13. A & (B & C) ≡ (A & B) & C (ассоциативность конъюнкции);
14. A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C (ассоциативность дизъюнкции);
Основные эквивалентные соотношения

15. A & (B ∨ C) ≡ (A & B) ∨ (A & C) (дистрибутивность конъюнкции относительно дизъюнкции);
16. A ∨ (B & C) ≡ (A ∨ B) & (A ∨ C) (дистрибутивность дизъюнкции относительно конъюнкции);
17. A &(A ∨B) ≡ A (первый закон поглощения);
18. A ∨ (A & B) ≡A (второй закон поглощения);
19. ¬ (A & B) ≡¬ A ∨¬ B (первый закон де Моргана);
20. ¬ (A ∨ B) ≡¬ A &¬ B (второй закон де Моргана);
21. A ≡ (A & B) ∨ (A &¬ B) (первый закон расщепления);
22. A ≡(A ∨ B)&( A ∨¬ B) (второй закон расщепления);
23. A → B ≡¬B→¬ A (закон контрапозиции);
24. A → B ≡¬ A v B = ¬ (A &¬ B);
25. A ~ B ≡ (¬ A ∨B)&(¬ B ∨ A) = (A & B) ∨( ¬ A &¬ B);
26. A ⊕ B = (A &¬ B) ∨ (¬ A & B);
27. A ∨ B = ¬ A → B = ¬ (¬ A &¬ B);
28. A & B = ¬ (A→¬ B) = ¬ (¬ A∨¬ B).
Основные эквивалентные соотношения

Эквивалентным (или тождественным) преобразованием некоторой формулы называют переход (по определенным прави­лам) к любой формуле, эквивалентной данной.
Например, применяют правило подстановки формулы F вместо переменной A . При подстановке формулы F вместо переменной A все вхождения переменной A в исходное соотношение должны быть одновременно заменены формулой F. Это правило замены применяется к эквивалентным соотношениям для получения новых эквивалентных соотношений.
Правило замены позволяет, используя известные эквивалентные соотношения, получать формулы, эквивалентные данной.
Существует понятие подформула — это часть формулы, которая сама является формулой.
Если некоторая формула F содержит F1 в качестве подформулы, то можно заменить F1 на эквивалентную ей F2.
Полученная с помощью такой замены новая формула G эквивалентна исходной формуле F
Эквивалентные соотношения

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

СХЕМЫ РАССУЖДЕНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Тавтологии можно получать из некоторого набора аксиом, с помощью правил вывода.
Эту задачу решает исчисление высказываний. Кроме 11 аксиом используется одно правило вывода МР утверждающий модус (modus ponens)
Каковы бы не были не были формулы А, В, С , для них существуют 11 аксиом исчисления высказываний.
1. А→(В→А)
2. (А→(В→С))→((А→В)→(А→С))
3. (А∧В)→А
4. (А∧В)→В
5. А→(В→(А∧В))
6. А→(А∨В)
7. В→(А∨В)
8. (А→С)→((В→С)→(А∨В→С))
9. ¬А→(А→В)
10. (А→В)→((А→ ¬В)→ ¬А)
11. А∨ ¬А

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Выводом в исчислении высказываний называют конечную последовательность формул, каждая из которых есть аксиома или получается из них по правилу МР.
Пример 1
р→(q→р)
Это выражение является аналогом аксиомы 1. А→(В→А)
В котором А заменено на р, а В заменено на q.
Пример 2
(р→(q→p))→((р→q)→(р→p))
Это выражение является аналогом аксиомы
2. (А→(В→С))→((А→В)→(А→С))
В котором А заменено на р, а В заменено на q, C заменено на р

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Теорема. Всякая теорема исчисления высказываний есть тавтология.
Проверим это для самой длинной аксиомы 2
2. (А→(В→С))→((А→В)→(А→С)) (а2) или П→З
Для того чтобы формула (а2) была ложной (не тавтологией) посылка П (А→(В→С)) должна быть истиной, а заключение З ((А→В)→(А→С)) ложным.
Чтобы заключение было ложным необходимо (А→В) =1, (А→С)=0. Последнее означает А=1 С=0 (в1)
Получаем А, (А→В), (А→(В→С) - истина
Из этого следует В, (В→С) - истина
Из этого следует С – истина (в2)
Выводы (в1) и (в2) есть противоречие, следовательно формула (а2) не бывает ложной

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

.