Выражение отношения подтипа между типами подчисления в Z3
Вопрос
Как лучше всего выразить связь между типами подсчета в Z3?
В частности, я хочу сделать что -то вроде следующего:
(declare-datatypes () ((Animal Eagle Snake Scorpion)))
а затем создайте новый подтип:
(declare-datatypes () ((Mammal Cat Rat Bat)))
так что утверждение о том, что существует 4 различных константа животного типа, является сидящим, но утверждение о том, что существует 4 различных константа типа млекопитающего, является невыполненным.
Решение
Z3 не имеет прямой поддержки отношений подтипа (подборка). Я вижу два способа моделировать их в Z3.
Например, у вас может быть сортировка перечисления Animal
это содержит всех животных. Затем вы определяете предикаты, такие как: is-mammal
, is-reptile
, так далее.
Вот сценарий, который использует этот подход:
(set-option :produce-models true)
(declare-datatypes () ((Animal Eagle Snake Scorpion Cat Rat Man)))
(define-fun is-mammal ((x Animal)) Bool
(or (= x Cat) (= x Rat) (= x Man)))
(declare-const a1 Animal)
(declare-const a2 Animal)
(declare-const a3 Animal)
(declare-const a4 Animal)
(assert (distinct a1 a2 a3 a4))
(check-sat)
; sat
(get-model)
; now, we constraint a1, a2, a3 and a4 to be mammals.
(assert (is-mammal a1))
(assert (is-mammal a2))
(assert (is-mammal a3))
(assert (is-mammal a4))
(check-sat)
; unsat
Другое решение использует DataTypes для определения сортов перечисления и сортов союза. То есть мы объявляем один датт для каждого класса животных: MammalType
, ReptileType
, и т. д. каждый из них является типом перечисления. Затем мы объявляем union
тип данных: AnimalType
Анкет Этот дат данных содержит конструктор для каждого класса животных: Mammal
, Reptile
, и т. д. Z3 автоматически создает предикат is-[constructor-name]
(распознавание) Для каждого конструктора: is-Mammal
, is-Reptile
, и т. д. мы называем аксессов как "Animal2class": Animal2Mammal
, Animal2Reptile
, и т. д. вы можете найти больше информации о данных дата на http://rise4fun.com/z3/tutorial/guideАнкет Вот скрипт с использованием этого кодирования:
(set-option :produce-models true)
(declare-datatypes () ((AveType Eagle Sparrow)))
(declare-datatypes () ((ReptileType Snake)))
(declare-datatypes () ((ArachnidType Scorpion Spider)))
(declare-datatypes () ((MammalType Cat Rat Man)))
(declare-datatypes () ((AnimalType
(Ave (Animal2Ave AveType))
(Reptile (Animal2Reptile ReptileType))
(Arachnid (Animal2Arachnid ArachnidType))
(Mammal (Animal2Mammal MammalType)))))
(declare-const a1 AnimalType)
(declare-const a2 AnimalType)
(declare-const a3 AnimalType)
(declare-const a4 AnimalType)
(assert (distinct a1 a2 a3 a4))
(check-sat)
; sat
(get-model)
; now, we constraint a1, a2, a3 and a4 to be mammals.
(assert (is-Mammal a1))
(assert (is-Mammal a2))
(assert (is-Mammal a3))
(assert (is-Mammal a4))
(check-sat)
; unsat