Алгоритм упрощения:
- Заменить операции ⊕, →, ↔ на их выражения через И, ИЛИ и НЕ:
- A ⊕ B = (A·¬B) + (¬A·B)
- A → B = ¬A + B
- A ↔ B = (A·B) + (¬A·¬B)
- Раскрыть инверсию сложных выражений по формулам де Моргана:
- ¬(A+B) = ¬A·¬B
- ¬(A·B) = ¬A+¬B
- Используя законы логики, упрощать выражение, стараясь применять закон исключённого третьего.
Пример упрощения: (A → B) → (¬A + B)
1. Заменяем импликацию: ¬(¬A + B) + (¬A + B)
2. Применяем формулу де Моргана: (A·¬B) + (¬A + B)
3. Используем законы логики: (A·¬B) + ¬A + B
4. Применяем распределительный закон: (A + ¬A + B)·(¬B + ¬A + B)
5. Используем закон исключённого третьего: (1 + B)·(1 + ¬A) = 1·1 = 1
Результат: выражение тождественно истинно.