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

From

Alex Kozhushko ()

To

Dmitry Kovtun

Date

2002-12-03T13:23:24Z

Area

RU.ALGORITHMS

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

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

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

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

Теперь запомненные тождественные преобразования и есть искомый путь. Или
требовалось нечто иное?

Для СКНФ - аналогично.

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





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