Как привести формулу к виду КНФ?

Question

[Михаил]

Дана задача, привести формулу к виду КНФ. С точки зрения булевой алгебры вопросов не возникает, все логично и ясно, но вот с приведением данной задачи в плоскость реализации на любом ЯП - возникают вопросы. Гугл выдаёт результаты на таблицы истинности в качестве решения, а в задании необходимо вывести формулу приведенную к виду КНФ. Может кто-то подкинет каких-либо решений. Я что-то уже неделю гугл мучаю, но вот решений хотя бы близких к требуемому заданию - не нахожу.

ЗЫ: предлагать гугл в помощь не надо. Спасибо! За ранее очень преблагодарен.

Answer 1

[Mrrl]

Считать значение формулы при заданных значениях переменных научились? Если да - перебираете все наборы значений (a_1,...,a_n) (их всего 2^n), считаете для каждого значение формулы, и если получился 0 - добавляете в формулу очередную дизъюнкцию ((x_1 xor a_1) or (x_2 xor a_2) or ... or (x_n xor a_n)).

Comments

[Михаил]

Не совсем вас понял.

[Mrrl]

Михаил: Тогда расскажите, что на входе (если речь про ЯП, значит это строка - в каком формате?), что хотите получить и в каком виде (желательно, с примером), что уже умеете.

[Михаил]

На входе мы имеем строку с формулой вида: x( A(x)y( B(y)))(B(x)A(x)) пардон, не могу вывести значки кванторов и импликаторов, а на выходе должны получить тоже строку, но уже после операций по приведению к виду КНФ.

[Mrrl]

Михаил: Так напишите строку не со значками, а со словами. И обязательно с желаемым результатом - КНФ с кванторами это для меня что-то новое.

Answer 2

[Николай]

КНФ строится по табице истинности простым проходом по строкам таблицы. Так что задача сводится к нахождению таблицы истинности. Построить таблицу истинности можно двумя путями: 1. Привести формулу к виду, содержащему только дизъюнкции и конъюнкции - затем просто вычислить. 2. Написать разбор формулы: например построение дерева по формуле и последующее вычисление значения выражения. Можно посмотреть примеры решения задачи с арифметическим калькулятором и немного поменять. Случайно не было ли условий, какого вида могут быть входящие формулы? Это бы могло упростить построение

Answer 3

[SeptiM]

Мне кажется, вы просто не поняли, что такое КНФ.

Вот пусть у нас есть булева функция f. Она зависит от n переменных x1, x2, ..., xn. Переменным можно сделать 2^n различных подстановок. На одних подстановках функция возвращает 1, на других -- 0. Хотим это как-то закодировать булевой формулой.

Есть два типичных способа это сделать. Первый -- описать все подстановки, дающие 1 -- ДНФ. Второй -- описать все подстановки, дающие 0 -- КНФ. Нам нужно второе.

Посмотрим на КНФ. Это конъюнкция дизъюнкций, например такая:
(not x1 or x2) and (x1 or not x2 or x3).
То, что записано в скобках можно переписать чуть понятней:
(x1 = 0 or x2 = 1) and (x1 = 1 or x2 = 0 or x3 = 1).
Теперь, можно воспользоваться логикой, математической =), и еще раз переписать:
(not (x1 = 1 and x2 = 0)) and (not (x1 = 0 and x2 = 1 and x3 = 0)).
Что говорит последняя формула? Что функция дает единицу, если подстановка не содержит паттерна (x1 = 1 и x2 = 0) или (x1 = 0 и x2 = 1 и x3 = 0).

Итого, перебираем все подстановки, на которых функция дает 0, записываем такие подстановки в заперещенные паттерны, а потом просто записываем их в КНФ, как я описал выше.