Визначення. Формули і над називаються еквівалентними, якщо відповідні їм функції і рівні, т. Е.. Запис буде означати, що формули і еквівалентні.
Наведемо список еквівалентностей (тотожностей), що характеризують властивості деякого безлічі елементарних функцій (головним чином безлічі).
Позначимо через будь-яку з функцій. . . Істотно тільки, щоб символ в тотожність мав один і той же зміст.
1. Функція має властивість асоціативності:
2. Функція має властивість коммутативности:
3. Для кон'юнкції і диз'юнкції виконуються дистрибутивні закони:
4. Мають місце наступні співвідношення між запереченням, кон'юнкція і диз'юнкція:
5. Виконуються такі властивості кон'юнкції і диз'юнкції:
1. З метою спрощення запису формул домовимося, що операція сильніше операції. т. е. якщо немає дужок, то спочатку виконується операція. а потім . Наприклад, запис означає.
2. В силу закону асоціативності для можна замість формул. користуватися виразом. яке не є формулою, але може бути перетворено в неї шляхом розстановки дужок, причому функціональні властивості не змінюються, як би не розставляли дужки.
Іноді будемо використовувати наступну форму запису:
Надалі, використовуючи зауваження 1 і 2, будемо вживати не формули, а вираження, що відрізняються від формул тим, що в них подекуди пропущені дужки. Ці вирази також іноді називатимемо формулами.
Визначення. Функція. рівна. називається двоїстої функцією до функції.
Таблиця для двоїстої функції виходить з таблиці для функції інвертуванням (т. Е. Заміною 0 на 1 і 1 на 0) стовпчика функції і його перевертанням (таблиця 1).