Преобразование булевой формулы

Для преобразований из булевой формулы в форму, состоящую из записей первого и второго уровней, используется следующий порядок.

Булева формула F приводится к каноническому виду, т. е. раскрываются все скобки. Канонический вид преобразуется в запись второго уровня D заменой дизъюнкции запятой, конъюнкции – пробелом, а знака отрицания – добавлением префикса "не_" к высказыванию. Далее формула ¬F также приводится к каноническому виду. Канонический вид формулы ¬F также преобразуется в запись второго уровня N. Условия задачи, на основании принципа исключенного третьего, формулируются как "[D]=М И [N]=0".

При постановке вопроса, представляющего собой тоже булеву формулу V, истинность которой нужно узнать, необходимо для этой формулы получить аналогичным образом записи D и N, которые и ввести в качестве множеств для определения их размера.

Формула V будет истинной, если D не пусто, а N пусто. Формула V будет ложной (т. е. 'НЕ V' – истинно), если D пусто, а N не пусто. В любом другом случае формула V при заданных условиях F не разрешима.

Следует отметить, что необходимость приведения булевой формулы к каноническому виду связана исключительно с техническими проблемами, так как на втором уровне нет "скобок", аналогичных обычным скобкам, используемым на первом уровне. То есть, запись "шары красные, а также синие или черные" должна быть записана как "шар[красный (синий,черный)]", но поскольку на втором уровне нельзя использовать круглые скобки (недоработка программы), то это условие следует записать следующим образом: "шар[красный синий,красный черный]", т. е. шары красные и синие, или шары красные и черные. Здесь "или" - обычное, т. е. согласно условию могут быть одновременно шары всех трех цветов: красные, синие и черные.