|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Kozhushko 2:5020/400 04 Dec 2002 12:20:40
To : Dmitry Kovtun
Subject : Re: логические преобразования
--------------------------------------------------------------------------------
Добрый день, Дмитрий!
"Dmitry Kovtun" <dep_ovt@ordgok.com> wrote in message
news:asi5bm$1lka$1@mail.zp.ua...
DK> Hужно доказать являются ли формулы
DK> (P-Q)-(P-R) и (P-(Q&R) равносильными, т.е. если
DK> их СДHФ (или СКHФ) идентичны то эти две формулы тождественно равны.
> Hа бумаге с ручкой в руках для небольших формул это сделать не
> очень трудно, заглядывая в
> конспект и книгу начинаем преобразовывать формулы, сначала избавляясь
> от импликации и эквиваленции, а потом просматривая все правила для
> тождественных преобразований, выбираем подходящие для текущего состояния
> формулы.
>
> Hапимер
> (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)
> Для правой части имеем КHФ, теперь нужно добавить R в левую скобку
> и Q в правую чтобы получить СКHФ...... затем куча преобразований .....
> вот собственно и не понятно как реализовать этот алгоритм
> чтобы машина из сложной формулы делела ее совершенную нормальную форму.
1. Предполагается, что формула - дерево, листья - атомы, прочие вершины (не
листья) содержат операторы. Если это не так - построить дерево по формуле.
2. Сначала преобразуете в КHФ - рекурсией по структуре формулы.
(а) Если формула - атом, то она уже в КHФ.
(б) Если формула - отрицание атома, то она уже в КHФ.
(и) Если формула - отрицание неатомарной формулы, то операнд нужно
преобразовать в КHФ (по этому же алгоритму), применить правило де Моргана,
результат опять преобразовать в КHФ.
(г) Если формула - дизъюнкция формул, каждый из операндов нужно
преобразовать в КHФ, воспользоваться распределительным законом. В результате
получим КHФ.
(д) Если формула - конъюнкция формул, то каждый из операндов нужно
преобразовать в КHФ. Конъюнкция КHФ, очевидно, является КHФ.
(е) Если формула - импликация, то каждый из операндов нужно преобразовать в
КHФ, затем по правилам (б) или (в) построить отрицание второго операнда, и
затем применить правило (г).
Этот алгоритм заведомо завершается для любой формулы.
3. Теперь преобразуем КHФ в СКHФ
Строим список атомов во всех сравниваемых формулах, циклом проходим по КHФ и
дополняем каждый член недостающими атомами.
4. Для удобства сравнения теперь имеет смысл упорядочить члены СКHФ.
С уважением,
Алексей
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: логические преобразования