|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Kozhushko 2:5020/400 03 Dec 2002 14:23:24
To : Dmitry Kovtun
Subject : Re: логические преобразования
--------------------------------------------------------------------------------
Добрый день, Дмитрий!
"Dmitry Kovtun" <dep_ovt@ordgok.com> wrote in message
news:ashsp5$qbd$1@mail.zp.ua...
DK> Вопрос следующего характера.
DK> Подскажите плз, алгоритм преобразования сложной формулы высказывания в
СКHФ,
DK> СДHФ методом тождественных преобразований.
DK> В теории вроде как ясно. Имеем начальное положение (формула) и имеем
целовое
DK> положение (СКHФ, СДHФ этой формулы), также имеем набор правил (формулы
DK> тождественного преобразования), теперь в пространстве состояний нужно
найти
DK> путь. Hо вот как это реализовать практически???
А в чем сложности?
Буква - это Переменная или ~Переменная
Дизъюнкт - список Букв
Д-Формула - список Дизъюнктов
Операции над Д-Формулами:
~~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Ф.
И упрощаем получившееся. (Опять же, тождественными преобразованиями).
Теперь запомненные тождественные преобразования и есть искомый путь. Или
требовалось нечто иное?
Для СКHФ - аналогично.
С уважением,
Алексей
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: логические преобразования 
