Re: логические преобразования

From

Dmitry Kovtun ()

To

Alex Kozhushko

Date

2002-12-03T14:42:20Z

Area

RU.ALGORITHMS

From: "Dmitry Kovtun" <dep_ovt@ordgok.com>

> DK> Подскажите плз, алгоритм преобразования сложной формулы высказывания в
> СКНФ,
> DK> СДНФ методом тождественных преобразований.
> DK> В теории вроде как ясно. Имеем начальное положение (формула) и имеем
> целовое
> DK> положение (СКНФ, СДНФ этой формулы), также имеем набор правил (формулы
> DK> тождественного преобразования), теперь в пространстве состояний нужно
> найти
> Буква - это Переменная или ~Переменная
> Дизъюнкт - список Букв
> Д-Формула - список Дизъюнктов
>
> Операции над Д-Формулами:
> ~~A = ~A
> ~~(A, B, ... ) = (~A) & (~B) & ...
> ~~[D1,D2,...] = ~~[D1] && ~~[D2] && ...
> (A1, B1, ...) && (A2, B2, ...) = [(A1, B1), (A1,B2), (B1,A2), (B2,A2),
...]
> [D11,D12,...] && [D21,D22,...] = [D11 && D21, D11 && D21, D12 && D21, D12
&
> D22, ...]
> [D11,D12,...] || [D21,D22,...] = [D11,D12,...,D21,D22,...]
> и т.д.
>
> Выполнение каждой операции соответствует некоторому тождественному
> преобразованию. Запоминаем, какое именно.
>
> (Удвоенные значки - операции над Д-Формулами, а не логические операции,
> которые обозначаются одиночными значками, в квадратных скобках - формулы,
в
> круглых - дизъюнкты)
>
> Преобразование в ДНФ:
> ДНФ(~F) = ~~ДНФ(F)
> ДНФ(F & G) = ДНФ(F) && ДНФ(G)
> и т.д.
> Каждый шаг - некоторое тождественное преобразование. Запоминаем его.
>
> ДНФ получили.
> Дальше, зная, что (x | y) = ( x | y | 0) = (x | y | (z&~z)) = (x | y | z )
&
> (x | y | ~z), дополняем дизъюнкты переменными для получения СДНФ.
> И упрощаем получившееся. (Опять же, тождественными преобразованиями).
>
> Теперь запомненные тождественные преобразования и есть искомый путь. Или
> требовалось нечто иное?

Добрый день Алексей.
Спасибо за ответ, однако у меняе есть некотроые вопросы.
Я не совсем понял ваши объяснения.
Попробую еще разъяснить суть проблемы.
Первое договоримся о обозначениях

P, Q, R, S - атомы формулы

'^' отрицание
'~' эквиваленция
'&' коньюнкция
'|' дизъюнкция
'-' импликация
'=' тождественное равенство

Нужно доказать являются ли формулы
(P-Q)-(P-R) и (P-(Q&R) равносильными, т.е. если
их СДНФ (или СКНФ) идентичны то эти две формулы тождественно равны.

На бумаге с ручкой в руках для небольших формул это сделать не
очень трудно, заглядывая в
конспект и книгу начинаем преобразовывать формулы, сначала избавляясь
от импликации и эквиваленции, а потом просматривая все правила для
тождественных преобразований, выбираем подходящие для текущего состояния
формулы.

Напимер
(P-Q)-(P-R)=(P-(Q&R)
(^P|Q)-(^P|R)=(^P|Q&R)
^(^P|Q)|(^P|R)=(^P|Q)&(^P|R)
(P|^Q)|(^P|R)=(^P|Q)&(^P|R)
Для правой части имеем КНФ, теперь нужно добавить R в левую скобку
и Q в правую чтобы получить СКНФ...... затем куча преобразований .....
вот собственно и не понятно как реализовать этот алгоритм
чтобы машина из сложной формулы делела ее совершенную нормальную форму.
Спасибо.
С уважением,
Дмитрий





--- ifmail v.2.15dev5
 * Origin: EXPRESS Radio Network (2:5020/400)