|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Kovtun 2:5020/400 03 Dec 2002 15:42:20
To : Alex Kozhushko
Subject : Re: логические преобразования
--------------------------------------------------------------------------------
> DK> Подскажите плз, алгоритм преобразования сложной формулы высказывания в
> СКHФ,
> DK> СДHФ методом тождественных преобразований.
> DK> В теории вроде как ясно. Имеем начальное положение (формула) и имеем
> целовое
> DK> положение (СКHФ, СДHФ этой формулы), также имеем набор правил (формулы
> 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,...]
> и т.д.
>
> Выполнение каждой операции соответствует некоторому тождественному
> преобразованию. Запоминаем, какое именно.
>
> (Удвоенные значки - операции над Д-Формулами, а не логические операции,
> которые обозначаются одиночными значками, в квадратных скобках - формулы,
в
> круглых - дизъюнкты)
>
> Преобразование в ДHФ:
> ДHФ(~F) = ~~ДHФ(F)
> ДHФ(F & G) = ДHФ(F) && ДHФ(G)
> и т.д.
> Каждый шаг - некоторое тождественное преобразование. Запоминаем его.
>
> ДHФ получили.
> Дальше, зная, что (x | y) = ( x | y | 0) = (x | y | (z&~z)) = (x | y | z )
&
> (x | y | ~z), дополняем дизъюнкты переменными для получения СДHФ.
> И упрощаем получившееся. (Опять же, тождественными преобразованиями).
>
> Теперь запомненные тождественные преобразования и есть искомый путь. Или
> требовалось нечто иное?
Добрый день Алексей.
Спасибо за ответ, однако у меняе есть некотроые вопросы.
Я не совсем понял ваши объяснения.
Попробую еще разъяснить суть проблемы.
Первое договоримся о обозначениях
P, Q, R, S - атомы формулы
'^' отрицание
'~' эквиваленция
'&' коньюнкция
'|' дизъюнкция
'-' импликация
'=' тождественное равенство
Hужно доказать являются ли формулы
(P-Q)-(P-R) и (P-(Q&R) равносильными, т.е. если
их СД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Ф...... затем куча преобразований .....
вот собственно и не понятно как реализовать этот алгоритм
чтобы машина из сложной формулы делела ее совершенную нормальную форму.
Спасибо.
С уважением,
Дмитрий
--- ifmail v.2.15dev5
* Origin: EXPRESS Radio Network (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
