Как включить алгоритм Куайна-Маккласки с составным шаблоном спецификации


Я хочу включить алгоритм Куайна–Маккласки с композитным шаблоном спецификации.

Во-первых, давайте рассмотрим основы, шаблон спецификации в C#:

public interface ISpecification
{
    bool IsSatisfiedBy(object candidate);
    ISpecification And(ISpecification other);
    ISpecification Or(ISpecification other);
    ISpecification Not();
}

 public abstract class CompositeSpecification : ISpecification 
 {
    public abstract bool IsSatisfiedBy(object candidate);

    public ISpecification And(ISpecification other) 
    {
        return new AndSpecification(this, other);
    }

    public ISpecification Or(ISpecification other) 
    {
        return new OrSpecification(this, other);
    }

    public ISpecification Not() 
    {
       return new NotSpecification(this);
    }
}

public class AndSpecification : CompositeSpecification 
{
    private ISpecification One;
    private ISpecification Other;

    public AndSpecification(ISpecification x, ISpecification y) 
    {
        One = x;
        Other = y;
    }

    public override bool IsSatisfiedBy(object candidate) 
    {
        return One.IsSatisfiedBy(candidate) && Other.IsSatisfiedBy(candidate);
    }
}

public class OrSpecification : CompositeSpecification
{
    private ISpecification One;
    private ISpecification Other;

    public OrSpecification(ISpecification x, ISpecification y) 
    {
        One = x;
        Other = y;
    }

    public override bool IsSatisfiedBy(object candidate) 
    {
        return One.IsSatisfiedBy(candidate) || Other.IsSatisfiedBy(candidate);
    }
}

public class NotSpecification : CompositeSpecification 
{
    private ISpecification Wrapped;

    public NotSpecification(ISpecification x) 
    {
        Wrapped = x;
    }

    public override bool IsSatisfiedBy(object candidate) 
    {
        return !Wrapped.IsSatisfiedBy(candidate);
    }
}

Теперь предположим, что у меня есть MacroSpecification и некоторые MicroSpecifications:

public class MacroSpecification : CompositeSpecification
{
    MicroSpecification1 Spec1 = new MicroSpecification1();
    MicroSpecification2 Spec2 = new MicroSpecification2();
    MicroSpecification3 Spec3 = new MicroSpecification3();
    MicroSpecification4 Spec4 = new MicroSpecification4();
    public override bool IsSatisfiedBy (object candidate)
    {
        if (candidate is int)
        {
            return Spec1.And(Spec2).And(Spec3).And(Spec4).IsSatisfiedBy(candidate);
        }
    }
}

public class MicroSpecification1 : CompositeSpecification
{
    public override bool IsSatisfiedBy (object candidate)
    {
        if (candidate is int)
        {
            return (candidate > 100);
        }
        return false;
    }
}

public class MicroSpecification2 : CompositeSpecification
{
    public override bool IsSatisfiedBy (object candidate)
    {
        if (candidate is int)
        {
            return (candidate > 300);
        }
        return false;
    }
}

public class MicroSpecification3 : CompositeSpecification
{
    public override bool IsSatisfiedBy (object candidate)
    {
        if (candidate is int)
        {
            return (candidate < 1000000);
        }
        return false;
    }
}

public class MicroSpecification4 : CompositeSpecification
{
    public override bool IsSatisfiedBy (object candidate)
    {
        if (candidate is int)
        {
            return (candidate < 500000);
        }
        return false;
    }
}

Я действительно нужна только MicroSpecification4 и MicroSpecification2 для упрощенной, эквивалентный метод MacroSpecification IsSatisfiedBy.

Итак, мой вопрос в том, есть ли способ использовать Куайн-Маккласки, чтобы упростить макроспецификацию IsSatisfiedBy заявление от четырех спецификаций до двух спецификаций (или что-то эквивалентное)?

Было бы неплохо дать композитную спецификацию шаблону (и без потери общности) шаблонных конструкций вообще какой-то"интеллект".

1 2

1 ответ:

Вы не можете использовать Куайн-Маккласки, чтобы сделать это упрощение, потому что упрощение, которое вы ищете, требует, чтобы было известно, что MicroSpecification2 => MicroSpecification1 и что MicroSpecification4 => MicroSpecification3. Q-M применяется только для упрощения уравнений независимых булевых переменных.

Вы можете переписать свои спецификации в терминах последних 20 битов candidate, а затем использовать Q-M для упрощения результирующего хаоса уравнений в 22 булевых переменных: 20 младших битов candidate; один булев, который является истинным, если любой из этих двух битов является истинным. оставшиеся биты в candidate задаются, и единственное булево значение, которое является истинным, если candidate равно int. Полученное упрощение было бы подходящим для проектирования микросхем, но, вероятно, не для какой-либо другой цели. Извиняюсь.