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

From

Alex Kozhushko ()

To

Dmitry Kovtun

Date

2002-12-04T11:20:40Z

Area

RU.ALGORITHMS

From: "Alex Kozhushko" <alxrie@sibmail.ru>

Добрый день, Дмитрий!

"Dmitry Kovtun" <dep_ovt@ordgok.com> wrote in message
news:asi5bm$1lka$1@mail.zp.ua...

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

> На бумаге с ручкой в руках для небольших формул это сделать не
> очень трудно, заглядывая в
> конспект и книгу начинаем преобразовывать формулы, сначала избавляясь
> от импликации и эквиваленции, а потом просматривая все правила для
> тождественных преобразований, выбираем подходящие для текущего состояния
> формулы.
>
> Напимер
> (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 в правую чтобы получить СКНФ...... затем куча преобразований .....
> вот собственно и не понятно как реализовать этот алгоритм
> чтобы машина из сложной формулы делела ее совершенную нормальную форму.

1. Предполагается, что формула - дерево, листья - атомы, прочие вершины (не
листья) содержат операторы. Если это не так - построить дерево по формуле.
2. Сначала преобразуете в КНФ - рекурсией по структуре формулы.
(а) Если формула - атом, то она уже в КНФ.
(б) Если формула - отрицание атома, то она уже в КНФ.
(и) Если формула - отрицание неатомарной формулы, то операнд нужно
преобразовать в КНФ (по этому же алгоритму), применить правило де Моргана,
результат опять преобразовать в КНФ.
(г) Если формула - дизъюнкция формул, каждый из операндов нужно
преобразовать в КНФ, воспользоваться распределительным законом. В результате
получим КНФ.
(д) Если формула - конъюнкция формул, то каждый из операндов нужно
преобразовать в КНФ. Конъюнкция КНФ, очевидно, является КНФ.
(е) Если формула - импликация, то каждый из операндов нужно преобразовать в
КНФ, затем по правилам (б) или (в) построить отрицание второго операнда, и
затем применить правило (г).

Этот алгоритм заведомо завершается для любой формулы.

3. Теперь преобразуем КНФ в СКНФ
Строим список атомов во всех сравниваемых формулах, циклом проходим по КНФ и
дополняем каждый член недостающими атомами.

4. Для удобства сравнения теперь имеет смысл упорядочить члены СКНФ.

С уважением,
Алексей


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)