Анотація: Еквівалентність булевих формул. Основні еквівалентності (закони логіки). Еквівалентні перетворення формул. Принцип заміни еквівалентних. Диз'юнктивні і кон'юнктівние нормальні форми (ДНФ і КНФ). Вчинені ДНФ і КНФ. Скорочені ДНФ і їх побудова методом Блейка. Багаточлени Жегалкина і їх побудова за допомогою еквівалентних перетворень формул і методом невизначених коефіцієнтів за таблицями
Еквівалентність булевих формул
Визначення 4.1. Булеві формули і називаються еквівалентними. якщо відповідні їм функції і рівні.
Позначення:. Еквівалентні формули називають також тотожно рівними, а вираження виду логічними тотожністю.
Основні еквівалентності (тотожності)
Таким чином, еквівалентні формули є різними завданнями однієї і тієї ж булевої функції. Нижче ми наводимо ряд пар еквівалентних формул (тотожностей), що відображають істотні властивості логічних операцій і важливі співвідношення між різними операціями. Вони часто дозволяють знаходити для булевих функцій за одними задає їх формулами більш прості формули. Більшість з наведених тотожностей мають власні імена. Часто їх називають законами логіки.
Нехай - це одна з функцій. Для цих трьох функцій виконані наступні дві еквівалентності (закони асоціативності і коммутативности).