Упростить ПФ

[Мироника]

Упростить ПФ, используя равносильные преобразования
$(X\leftrightarrow Y) \wedge (Y \vee Z) \to (Z \wedge X)$
Вот что получилось
$(\overline X \vee Y) \wedge (X \vee \overline Y) \wedge (Y \vee Z) \to (Z \wedge X)$
$(\overline {\overline X \vee Y) \wedge (X \vee \overline Y) \wedge (Y \vee Z)} \vee (Z \wedge X)$
$(\overline {\overline X \vee Y)} \vee \overline { (X \vee \overline Y)} \vee \overline {(Y \vee Z)} \vee (Z \wedge X)$
$( X \wedge \overline Y) \vee (\overline X \wedge Y) \vee (\overline Y \wedge \overline Z) \vee (Z \wedge X)$
Верно ли это? И что делать дальше?

[Мироника]

Можно ли как-то это еще упростить?

[Профессор Снэйп]

Ну а что значит "упростить"? Записать как можно короче? Так, по-моему, у Вас формула до "упрощения" выглядит проще, чем после

[Мироника]

Вот и мне так кажется. Но в задании сказано упростить. Что же делать?

[mserg]

Можно перебрать все возможные значения x,y и z и подобрать "на глаз" подходящую функцию.

Можно воспользоваться программами, которые подбирают функции по множеству данных. Например, программа Easy NP находит функции
z Xor y==>y Xor x
(y<=>z)Or(z<=>x)

Текст программы следующий:

Func f(x As Boolean, y As Boolean, z As Boolean) As Boolean =
  (x <=> y) And (y Or z) ==> (z And x)

Func fxyz(x As Boolean, y As Boolean, z As Boolean) As Boolean
  Operators {"Not 1", "Or 2", "And 2", "==> 2", "<=> 2", "Xor 2"}

Var Desc  = 
  Abs(fxyz(0,0,0)-f(0,0,0))+
  Abs(fxyz(0,0,1)-f(0,0,1))+
  Abs(fxyz(0,1,0)-f(0,1,0))+
  Abs(fxyz(0,1,1)-f(0,1,1))+
  Abs(fxyz(1,0,0)-f(1,0,0))+
  Abs(fxyz(1,0,1)-f(1,0,1))+
  Abs(fxyz(1,1,0)-f(1,1,0))+
  Abs(fxyz(1,1,1)-f(1,1,1))

Con Opt As
  Minimize((0.1+Desc)*Exp(0.01*SizeOf(fxyz)))

Зная ответ, проще подобрать равносильные преобразования...

[Sonic86]

СКНФ тоже проще выглядит:

$$(x \vee y \vee \bar z)(\bar x \vee \bar y \vee z)$$

-- Чт дек 23, 2010 16:37:18 --

Кстати, поскольку все функции бинарные, можно считать за меру сложности число переменных в формуле, при условии, что набор операций одинаков (и тогда число знаков операций на 1 меньше).
Хотя нет - еще отрицание не учел. Тогда брать число литералов.
У меня значит сложность 6 в $\{ \vee, \wedge \}$, исходная сложность - 6 в $\{ \vee, \wedge, \to, \leftrightarrow \}$, а преобразовали, до 8 в $\{ \vee, \wedge \}$

-- Чт дек 23, 2010 16:52:06 --

Можно конечно сделать финт: преобразовать СКНФ к виду, полученному Вами, а в контрольной записать все преобразования наоборот, вот препод-то обалдеет!
В Вики есть статья про упрощение СКНФ и СДНФ (например по правилам склеивания и поглощения). Видимо это здесь не поможет.