Форми на представяне на функции на алгебрата на логиката

Основните понятия, залегнали в представянето на булеви функции в различни форми, са понятията елементарен конюнкция и елементарна дизюнкция.

Елементарна връзка е логическият продукт на произволен краен брой различни булеви променливи, взети със или без знак за инверсия.

Например логически изрази като x1x2x3, x1x4, x1x2x4 са елементарни съюзи, а изрази като x1x2x3, x1x4, x1x2x4 не са елементарни съюзи.

Елементарна дизюнкция е логическата сума на произволен краен брой различни булеви променливи, взети със или без знак за инверсия

Пример за логически израз, който е елементарна дизюнкция, е x1 + x2 + x3, x1 + x4, x1 + x2 + x4, а изрази като x1 + x2 + x3, x1 + x4, x1 + x2 + x4 не са елементарни дизюнкции.

Дизюнктивна нормална форма (DNF) на булева функция е дизюнкция на краен брой елементарни съединения.

Броят на променливите, включени в елементарна връзка, определя ранг тази връзка.

Перфектен DNF (SDNF) на логическа функция от n аргументи е DNF, в който всички съединения имат ранг n. SDNF се записва според таблицата на истината според правилото: за всеки набор от променливи, за които булевата функция приема единична стойност, се записва съединение от ранг n и всички тези съединения се комбинират дизюнктивно; променлива има знак за инверсия, ако има нулева стойност в съответния набор.

Най-общо това може да се напише, както следва:

алгебрата

Наричат ​​се и елементарни съюзи, образуващи SDNF съставни части (компоненти) единици (minterm), тъй като те съответстват на множества, за които функцията приема стойност, равна на единица.

Конюнктивната нормална форма (CNF) на булева функция е конюнкцията на краен брой елементарни дизюнкции.

Перфектен CNF (SKNF) на логическа функция от n аргументи е CNF, в който всички дизюнкции имат ранг n. SKNF е написано според таблицата на истината според правилото: за всеки набор от променливи, върху които булевата функция приема нулева стойност, се записва дизюнкция на ранг n и всички тези дизюнкции се комбинират конюнктивно; променлива има знак за инверсия, ако има единична стойност в съответния набор.