Глава что такое комбинаторика. Основные проблемы изучения комбинаторики

Задача о тождественной истинности ДНФ. Дана дизъюнктивная нормальная форма  от булевых переменных x₁, x₂, …, x_n. Непривычное для булевых величин обозначение x^ следует понимать как x¹ = x, x^-1 =x, x⁰ = 1. Таким образом, массив параметров _ji содержит информацию о том, входит ли i-тая переменная в j-тую элементарную конъюнкцию, и если входит, то c инверсией или без.
Требуется дать ответ, существует ли набор значений переменных x₁, x₂, …, x_n, при котором значение ДНФ равно 0, или же данная ДНФ является тождественно истинной, т.е. всегда равна 1.
Это задача поиска, ее решение завершается, если найден хотя бы один план, на котором ДНФ принимает значение 0.
Используя законы Де Моргана, нетрудно сформулировать двойственную задачу: дана конъюнктивная нормальная форма, требуется определить, существует ли набор значений переменных x₁, x₂, …, x_n, при котором значение КНФ равно 1. Эту задачу принято называть задачей о выполнимости КНФ. Как будет показано далее, задача о выполнимости играет важную роль в теории вычислительной сложности.
Задача о 8 ферзях. На шахматной доске размером 88 требуется расставить 8 ферзей так, чтобы они не били друг друга (т.е. никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали).
Это задача поиска, если требуется найти хотя бы одну расстановку, либо задача перечисления, если нужно найти все возможные расстановки. В отличие от всех предыдущих примеров, задача не имеет никаких параметров. Это не семейство задач, а одна конкретная задача. Разумеется, она давно решена, число различных расстановок равно 92.
При желании можно параметризовать задачу, рассмотрев расстановку k ферзей на прямоугольной доске nm.