Вопросы с тегами [theorem-proving]

0

голосов
0

ответ
7

Просмотры

Coq won't reduce expression involving decision procedure

Я использую Coq версии 8.8.1 и для жизни меня я не могу понять, почему он не будет оценивать значение следующего вычисления. Требовать Импорт Coq.Lists.List. Импорт Coq.Lists.List.ListNotations. Требовать Импорт Coq.Classes.EquivDec. Требовать Импорт Coq.Init.Nat. Требовать Импорт Coq.Arith.EqNat. Требовать Импорт Coq.Lists.ListSet. Требовать Импорт Coq.Bool.Bool. Индуктивный термин: Set: = | вар: физ -> термин | п: физ -> термин -> термин. Схема равенство на срок. Fixpoint uf_find (х: термин) (УФС: набор (набор термин)): опция (набор термин): = ПОИСКПОЗ UFS с | нет [] => None | эм :: UFS' => матч (set_In_dec term_eq_dec х э) с | левый _ => Некоторые эм | конец конец правой _ => uf_find х UFS. Вычислить uf_find (VAR) 3 ноль. (* Почему ISN» T это полностью снижается? *) Вычислить uf_find (вар 3) (против ноль ноль). Аналогичная функция с term_eq_dec вместо этого работает просто отлично: Fixpoint has_succ (х: физ) (л: термин списка): термин варианта: = матч л с | нет [] => None | ч :: л '=> матч term_eq_dec (вар (S х)) ч с | левый _ => Некоторая ч | правый _ => has_succ х»конец конец. Вычислить has_succ 3 [(Var 2); (Вар 1); (Вар 4)].
Akay
1

голосов
1

ответ
60

Просмотры

Перевод с переводчиком HOL для TAC_PROOF с THENL

Шаги в скобках THENL работать правильно, если я печатаю их последовательно в интерпретатор HOL. Но когда я объединить их с помощью TAC_PROOF THENL, я получаю сообщение об ошибке. Я думаю, я понимаю разницу между THEN и THENL (все подзадачи против одной подцели). Но я не могу найти синтаксис для различения между 2 начальных подзадач. DISJ1_TAC и RES_TAC должны применяться только к subgoal1. Хотя DISJ2_TAC и RES_TAC должны применяться только к subgoal2. Как я могу это исправить? Val constructiveDilemmaRule = TAC_PROOF (([], ``! PQRS. (р ==> д) / \ (г ==> s) ==> р \ / г ==> д \ / s``), REPEAT STRIP_TAC THENL [DISJ1_TAC ТОГДА RES_TAC] THENL [DISJ2_TAC, RES_TAC]);
hackerCMU
1

голосов
0

ответ
115

Просмотры

Автоматически, специализирующаяся гипотезу Coq

В доказательствах, если я Проведем индукцию по аргументу, который не является окончательным, я получаю универсально quanitified индукции гипотез. Я считаю себя неоднократно писать тактику, как это: соответствие цели с | [Н: FORALL (esub: выражение) (х: exprvar) (Tsub т: Т) (gamma_: Гамма), (internalType gamma_ theta_ d esub Tsub?) -> (internalType (gamma_evar х Tsub :: gamma_)? ? theta_ д и др) -> internalType gamma_ theta_ д (esubst_expr esub х е) т, esub:???? выраж, xvar: exprvar, Tsub: Т, т: Т, gamma_: Гамма, H1: internalType gamma_ Тета ? d esub XSUB, H2:??? internalType (?? gamma_evar xvar Tsub :: gamma_) Theta d е т | - _] То есть, я ищу индукции, и аргументы, которые унифицировать с ним специализироваться его. Я тогда специализируюсь (гипотезы arg1 arg2 ...) Это выглядит как шаблонные, но я держу, чтобы писать другую версию для каждой леммы я использую это на. Есть ли способ: сделать это автоматически? сделать это автоматически, только для индукционных гипотез? (Так что мы не увязнуть в бесконечных циклах применения каждого аргумента каждую функцию возможной)
jmite
1

голосов
1

ответ
41

Просмотры

Смарт шаблон конструктор при доказательстве с Изабеллой

При изучении главы 3 бетона семантике мой инструктор, что некоторые упоминалось функции были построены с использованием смарт-шаблона конструктора и заявил, что эта модель была выгодна для доказательства теорем. Я гугл умных конструкторов, и они, как представляются, используются в таких языках, как Haskell, с которым я не знаком с. Кроме того, существует не так много ссылок смарта-конструкторов в доказательстве теорем. Итак, что умный шаблон конструктора в Изабелле, и как она может помочь доказательству теорем? Может быть, вы даже можете это объяснить главе 3 книги ...
Javier
1

голосов
1

ответ
671

Просмотры

использование рода в Z3

Может кто-нибудь помочь, чтобы узнать, как использовать «для всех» правильно Z3, Ive искал в документации, но я не смог найти информацию. То, что я пытаюсь сделать это в «Foo» мне нужно сказать в Z3 что-то эквивалент «пусть (и, г) работоспособным (т) в {(утверждать ((и, г) пользователей) (утверждают ( г, т) в роли))}»то, что я не знаю, как сделать первый элемент в работоспособном, чтобы утверждать, что в пользователях, а затем второй элемент утверждать, что в роли. (Объявлять сортировки Task) (объявление сортировки Роль) (объявление сортировки пользователя) (объявлять-весело Runnable (Task) (Роль пользователя)) (объявлять-прикольную завивку (Task Роли) Bool) (декларирует-весело пользователей (Role пользователя ) Bool) (утверждать (FORALL (т Task)) (Foo)) (чек-сат) (получить-модель)
user3723800
1

голосов
1

ответ
55

Просмотры

Поведение применить тактику, когда цель и применяется термин матч

Предположим, что мы имеем ABC: Опору Учитывая контекст с H:. A -> B -> C и одна цель A -> B -> C, то почему можно применить H, чтобы завершить доказательство, решение текущих и единственная цель ? Я думал применить тактику создает новую цель для каждого из аргументов термина применяется должен его заключение матча (или быть unifiable с) текущей целью.
ScarletAmaranth
1

голосов
1

ответ
47

Просмотры

Почему Z3 не может доказать / признать, что `is_int` замкнут относительно некоторых операций?

Например, следующее время запроса из: (объявлять-Const й Реальной) (объявлять-Const у Реального) (утверждают (is_int х)) (утверждают (is_int у)) (утверждают (не (is_int (+ х)))) (чек-сат) насколько я читал, Real Z3 являются математическими реалами, а не машина онов с тонкой семантикой. Есть ли какие-либо проблемы в допущении, что некоторые операции сохраняют is_int?
Phil
1

голосов
2

ответ
203

Просмотры

Заменить подвыражения в равенстве доказательства в Идриса

В качестве упражнения в Идриса я пытаюсь доказать это свойство: multCancel: (а: Nat) -> (б: Nat) -> (с: Nat) -> (S а) * Ь = (S а) * C - > Ь = с, я пришел к выводу, что в качестве itermediate шага, мне нужно, чтобы доказать что-то вроде этого: lemma1: {х: Nat} -> {у: Nat} -> {г: Nat} -> (х + х) + (х * г) = (у + у) + (у * г) -> (х * (S (S г))) = (у * (S (S г))) lemma1 {х = х } {у = у} {г = г} ч.р.ф. = TODO конечно, я уже доказал, что: plusDouble: (а: Nat) -> (а + а) = а * 2 plusDouble а = переписывают multCommutative 2 в переписать plusZeroRightNeutral а в Refl Поэтому я считаю, мне нужно в основном только для замены (х + х) (х * 2), а затем ссылаться на дистрибутивности, чтобы доказать lemma1. Я не знаю, как сделать эту замену. Я думал, что я мог бы просто сделать что-то вроде переписывания plusDouble х в ... Но, видимо, выиграл» т работу, потому что Подвыражение я хочу заменить в ПРФ и в воротах. Есть ли какой-нибудь общий подход к этому? Или то, что вы рекомендовали бы в данном конкретном случае?
user1747134
1

голосов
1

ответ
54

Просмотры

Как определить выражение переводчик?

Я определил 2 почти одинаковые языки (Foo и бар): теория SimpTr импортирует Основное начинают type_synonym VNAME = "строка" type_synonym 'а окр = "VNAME ⇒' вариант" Тип данных foo_exp = FooBConst BOOL | FooIConst INT | FooLet VNAME foo_exp foo_exp | FooVar VNAME | FooAnd foo_exp foo_exp тип данных bar_exp = BarBConst BOOL | BarIConst INT | Barlet VNAME bar_exp bar_exp | BarVar VNAME | BarAnd bar_exp bar_exp тривиального семантику: Тип данных foo_val = FooBValue BOOL | FooIValue INT тип данных bar_val = BarBValue BOOL | BarIValue INT type_synonym foo_env = "foo_val ENV" type_synonym bar_env = "bar_val ENV" индуктивный foo_big_step :: "foo_exp × foo_env ⇒ foo_val ⇒ BOOL" (инфикс "⇒f" 55) где "(FooBConst с, е) ⇒f FooBValue с" | «(FooIConst с, 50] 50), где "Γ ⊢f FooBConst с: FooBType" | "Γ ⊢f FooIConst с: FooIType" | "Γ ⊢f INIT: τ⇩1 ⟹ Γ (var↦τ⇩1) ⊢f тела: τ ⟹ Γ ⊢f FooLet вар инициализации тела: т" | "Γ вар = Некоторые τ ⟹ Γ ⊢f FooVar вар: τ" | "Γ ⊢fa: BTYPE ⟹ Γ ⊢fb: BTYPE ⟹ Γ ⊢f FooAnd аб: BTYPE" индуктивный bar_typing :: "bar_tenv ⇒ bar_exp ⇒ ⇒ bar_type BOOL" ( "(1_ / ⊢b / (_ / _))" [50,0,50] 50), где "Γ ⊢b BarBConst с: BarBType" | "Γ ⊢b BarIConst с: BarIType" | "Γ ⊢b INIT: τ⇩1 ⟹ Γ (var↦τ⇩1) ⊢b тела: τ ⟹ Γ ⊢b Barlet вар инициализации тела: т" | "Γ вар = Некоторые τ ⟹ Γ ⊢b BarVar вар: τ" | "Γ ⊢ba: BTYPE ⟹ Γ ⊢bb: BTYPE ⟹ Γ ⊢b BarAnd аб: BTYPE" inductive_cases [элим]: "Γ ⊢f FooBConst с: τ" "Γ ⊢f FooIConst с: τ" " Я думаю, что FooToBar должен быть более сложным. Она должна включать в себя также своем роде выражение среды или переменного отображение. Не могли бы вы предложить лучшую подпись для FooToBar? Я думаю, что такой переводчиком является тривиальной вещью, но я не могу найти любой учебник, описывающий его.
Denis
1

голосов
1

ответ
109

Просмотры

Wrong Typeclass Instance used in Coq Proof

Я пытаюсь выполнить следующее доказательство, основанное на конечных картах, как это определено в CoqExtLib. Тем не менее, у меня проблема, когда экземпляр RelDec появляется в доказательстве, отличается, например, что я думаю, объявляется. Требовать Импорт ExtLib.Data.Map.FMapAList. Требовать ExtLib.Structures.Sets. Модуль DSET: = ExtLib.Structures.Sets. Требовать ExtLib.Structures.Maps. Модуль Карта: = ExtLib.Structures.Maps. Требовать Импорт ExtLib.Data.Nat. Требовать Импорт Coq.Lists.List. Определение Карта киловольты:. = Крен к v Определение ОЕ = физ. Определение сигма: Тип: = (Карта LOC физ). Лемма not_in_sigma: FORALL (LL ': LOC) (е: физ) (с: сигма), LL' -> Map.lookup л ((л», е) :: з) = Map.lookup л ы. интро. Симпл. утверждают (RelDec.rel_dec LL '= верно -> L = L'). поза (ExtLib.Core.RelDec.rel_dec_correct LL» ) Насколько я. уничтожить я. (* Я: = RelDec.rel_dec_correct LL «: RelDec.rel_dec LL» = верно л> = л '*) Как вы можете видеть, я пытаюсь использовать тот факт, что rel_dec должен оценить ложь, если ее два входа не являются равны. Это, кажется, в соответствии с определением, данным в ExtLib.Data.Nat: Global Instance RelDec_eq: RelDec (@eq физ): = {rel_dec: = EqNat.beq_nat}. Тем не менее, в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? RelDec.rel_dec LL «= верно л> = л» *) Как вы можете видеть, я пытаюсь использовать тот факт, что rel_dec должен оценить ложь, если ее два входа не равны. Это, кажется, в соответствии с определением, данным в ExtLib.Data.Nat: Global Instance RelDec_eq: RelDec (@eq физ): = {rel_dec: = EqNat.beq_nat}. Тем не менее, в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? RelDec.rel_dec LL «= верно л> = л» *) Как вы можете видеть, я пытаюсь использовать тот факт, что rel_dec должен оценить ложь, если ее два входа не равны. Это, кажется, в соответствии с определением, данным в ExtLib.Data.Nat: Global Instance RelDec_eq: RelDec (@eq физ): = {rel_dec: = EqNat.beq_nat}. Тем не менее, в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? м пытаются использовать тот факт, что rel_dec должен оценить ложь, если ее два входа не равен. Это, кажется, в соответствии с определением, данным в ExtLib.Data.Nat: Global Instance RelDec_eq: RelDec (@eq физ): = {rel_dec: = EqNat.beq_nat}. Тем не менее, в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? м пытаются использовать тот факт, что rel_dec должен оценить ложь, если ее два входа не равен. Это, кажется, в соответствии с определением, данным в ExtLib.Data.Nat: Global Instance RelDec_eq: RelDec (@eq физ): = {rel_dec: = EqNat.beq_nat}. Тем не менее, в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем? в коде я показал выше, он использует> = вместо = как отношение, что конечное отображение параметризованных на, так что я не могу применить теорему rel_dec_correct. Почему это происходит? Как экземпляр для RelDec выбирают? Есть ли что-то особенное, что нужно сделать при доказательстве теоремы о типах квалифицированы классами типов? Как я могу получить версию rel_dec_correct, которая относится к равенству, не более, чем?
jmite
1

голосов
1

ответ
82

Просмотры

В Изабелле, что же угловые скобки и двойные звездочки означают?

Я пытаюсь понять некоторые Isabelle коды, и есть некоторый синтаксис, я не понимаю. Я не видел их в учебники, в том числе два в комплекте с распределением, «Программирование и Доказывание в Isabelle / HOL» Isabelle2017 и «Isabelle / Изар Reference Manual». Дело в том, что они символы, в сочетании с очень малой базой пользователей Изабеллы, означает, что ответ довольно не-Google-состояние. Первый высокие угловые скобки ⟨⟩, а второй является двойной звездочкой **, которая делает в выходной консоли как ∧ * (что заметно отличается от ASCII ^). Вот пример; лемму pre_fifth_pure [упр]: «тройные чистые неудачи (а ** B ** с ** ** d ⟨P⟩) трески сообщение = (P ⟶ тройные чистые неудачи (а ** B ** С ** г) трески пост )»угловые скобки всегда, кажется, окружают предложение. Определение тройной функции означает, что (а ** B ** с ** г) имеет тип state_element множество ⇒ BOOL, где state_element является только конъюнкцией кучи конструкторов; Тип данных state_element = StackHeightElm "нац" | StackElm «НАТ * W256» ... (* 20 строк как этот *) Являются ли эти две части синтаксиса связаны? Как мог (а ** б ** с ** d) функция? Почему это может иметь разное количество вещей, разграниченные звездами? Является ли это как-то пользовательский определенный синтаксис? Тайны изобилуют. (* 20 строк как этот *) Являются ли эти две части синтаксиса связаны? Как мог (а ** б ** с ** d) функция? Почему это может иметь разное количество вещей, разграниченные звездами? Является ли это как-то пользовательский определенный синтаксис? Тайны изобилуют. (* 20 строк как этот *) Являются ли эти две части синтаксиса связаны? Как мог (а ** б ** с ** d) функция? Почему это может иметь разное количество вещей, разграниченные звездами? Является ли это как-то пользовательский определенный синтаксис? Тайны изобилуют.
Alex Altair
1

голосов
1

ответ
50

Просмотры

VerifiedFunctor - prove map (map g) x = x

Я пытаюсь доказать утверждение о интерфейсе VerifiedFunctor (функтор, какой метод карты уважающей идентичности и состав): интерфейс Функтора F => VerifiedFunctor (F: Type -> Type), где functorIdentity: {а: Тип} -> (г: а -> а) -> ((v: а) -> г.в. = v) -> (х:. метрономы) -> карта Gx = х Вот утверждение (которое логически говорит, что отображение карты для двух заданных функторов также уважает личность ): functorIdentityCompose: (VerifiedFunctor f1, VerifiedFunctor f2) => (г: а -> а) -> ((об: а) -> Gv = v) -> (х: f2 (f1 а)) -> карта ( карта г) = х functorIdentityCompose fnId ИУП = functorIdentity (карта fnId) (functorIdentity fnId ИУП) Тем не менее, я получаю следующее сообщение об ошибке: Тип несоответствия между (х: f1 а) ->карта fnId х = х (тип functorIdentity fnId ИУП) и (v: метрономы) -> карта fnId v = v (ожидаемый тип) В частности: Несоответствие типов между f1 а и фа я попытался указать все неявные аргументы: functorIdentityCompose: (VerifiedFunctor f1, VerifiedFunctor f2) => {а: Тип} -> {f1: Тип -> Тип} -> {f2: Тип -> Тип} -> (г: а -> а) -> ((об: а) -> Gv = v) -> (х: f2 (f1 а)) -> отображение {F = f2} {а = f1 а} {Ь = f1 а} (отображение {F = f1} {а = а} { Ь = а} г) = х ... Но есть другая ошибка: При проверке аргумента FUNC функционировать Prelude.Functor.map: не удается найти реализацию для Functor F15 Так любые идеи, что здесь не так, и как доказать это утверждение ?т найти реализацию для Functor F15 Поэтому любые идеи, что здесь не так, и как доказать это утверждение?
stop-cran
1

голосов
1

ответ
0

Просмотры

Isabelle 2017 - начало работы

Я пытаюсь научиться использовать Isabelle / хол. Я подумал: «Эй, учебник написан некоторые из людей, которые разработали это было бы здорово», и так посмотрел на https://isabelle.in.tum.de/doc/tutorial.pdf, который имеет дату публикации августа 15, 2018. в попытке работать с помощью примеров, хотя, я считаю, такие вещи, как это в тексте: «классический Isabelle пользовательский интерфейс Proof Общие / Emacs Дэвид Aspinall Данная книга очень мало говорит о Proof Генеральный, который имеет свою собственную. документация." (Страницы III) «Если что-то странное происходит, мы рекомендуем вам задать Изабеллу, чтобы отобразить всю информацию о типе через Proof пункт меню Общих Isabelle> Настройка> Показать Types (см. 1.5 для более подробной информации).» (Страница 5) Проблема заключается в том, что Proof General появляется больше не работать с Изабеллой (см Isabelle2016 и доказательство общего). Я'
John
1

голосов
1

ответ
0

Просмотры

Тестирование, если доказательство звука в Идриса

Я пытаюсь написать тестовый код, чтобы проверить, если plusComm: (а: Nat) -> (б: Nat) -> а + Ь = Ь + а на самом деле доказывает + Ь = Ь + а на натуральные числа, т.е. код не поддельный с использованием типизированных отверстий, постулат, believe_me, assert_total и т.д. в частности, если доказательство сфальсифицировано какой-то образом, я хочу, чтобы программа не в состоянии в одном из трех способов: ошибки компиляции ошибки времени выполнения, например, Segfault Run -время бесконечный цикл Если эти варианты не представляется возможным, я открыт для анализа исходного кода в качестве последнего средства (для моих целей, которые должны быть записаны в Идриса тоже). Я слышал о Language.Reflection, но я не уверен, если это правильный инструмент здесь. Приведенный ниже код является одна попытка, которая не удалась, поскольку proofEval даже не смотрит на фактическое значение, переданное: plusComm: (а: Nat) -> (Ь: Nat) -> а + Ь = Ь + а plusComm аб = plusComm proofEval? : {а: ти} -> (а = Ь) -> ти proofEval {а = а} _ = основной: IO () основные = сделать putStrLn "! Составитель успешно" печати (proofEval (plusComm 1 2)), приведенные выше, при компиляции и запуска, производят следующий вывод и завершает работу без ошибок. Составитель успешно! 3
Bubbler
1

голосов
1

ответ
0

Просмотры

How to proceed with this Coq Proof?

У меня возникли проблемы с моим Coq доказательства и надеясь на помощь и руководство. У меня есть часть моего определения ниже: Индуктивный Архитектура: Set: = | Create_Architecture (Arch_Name: строка) (MyComponents: список компонентов) (MyConnections: список разъемов) с ... с разъемом: Set: = | Create_Connector (Con_Name: строка) (клиент: Компонент) (сервер: компонент) «Компонент термин должен быть клиент или сервер соединения, но не оба» Я хочу сказать, что Я придумал следующие как представление выше в Coq (на основе моего определения выше): (ForAll кона: коннекторы, ForAll с: Компонент, В коне (MyConnections х) -> (с = (клиентом кон) / \ с (сервер кон)) \ / (с (клиент кон) / \ с = (сервер жулик))) Тем не менее, я не уверен, что это правильно (это?), а когда я к доказательству , Я застреваю в точке 5 подзадачи кон: Разъем C: Компонент Н0: Connection1 = кон ______________________________________ (1/5) с = HotelRes типа HotelRes действительно компонент (в данном случае, HotelRes является клиентом соединения), однако , так как это не в наборе предположений, я не могу использовать что-то вроде точной или авто тактики. Как я мог бы продолжить такое доказательство?
zdot
1

голосов
1

ответ
140

Просмотры

Образец равномерно из множества удовлетворяющих присвоений в Z3

Есть ли способ использовать теорему прувер Z3 к образцу равномерно из множества удовлетворяющих заданий? Если нет, то ближе система Z3, которая имеет такую ​​возможность?
Andreas
1

голосов
1

ответ
103

Просмотры

Сокращение количества используемых положений, используя доказательства цели в Z3

Я экспериментировал с оптимизацией использования Z3 для доказательства фактов о теории первого порядка. В настоящее время я определяю теорию первого порядка в Python, заземлить кванторы там и отправить все пункты вместе с отрицанием доказательства цели на Z3. У меня есть следующая мысль, что я надеюсь, что может оптимизировать результат: Я только хочу, чтобы отправить формулы в теории к Z3, которые имеют отношение к цели доказательства. Я не буду обсуждать эту концепцию в деталях, но я думаю, что интуиция проста: моя теория является конъюнкцией формул, и я только хочу, чтобы отправить конъюнктивные, которые возможно могут повлиять на значение истинности доказательства цели. Мой вопрос заключается в следующем: это может привести к повышению эффективности, или же Z3 уже используют подобный метод? Я думаю, нет, потому что я не думаю, что Z3 всегда предполагает, что последнее утверждение является доказательством цели,
marczoid
1

голосов
1

ответ
104

Просмотры

Изабелль матрица арифметика: det_linear_row_setsum в библиотеке с различными обозначениями

Я недавно начал использовать теорему прувер Isabelle. Как я хочу, чтобы доказать еще одну лемму, я хотел бы использовать другое обозначение, чем используемый в «det_linear_row_setsum» лемма, которую можно найти в библиотеке HOL. Более конкретно, я хотел бы использовать «х IJ обозначения» вместо «χ я». Я пытался сформулировать эквивалентное выражение в течение некоторого времени, но не мог понять его еще. (* ОРИГИНАЛ лемму из библиотеки *) (* от HOL / Multivariate_Analysis / Determinants.thy *) леммы det_linear_row_setsum: Fs предполагает: "конечное S" показывает «Det ((χ я, если I = к, то setsum (ах) S еще CI. ) :: 'а :: comm_ring_1 ^ п ^ п) = setsum (точках Aj. Det ((χ я., если я = к, то Aij еще CI) ::' а ^ 'п ^' п)) S»доказательство (водворять правило:
mrsteve
1

голосов
1

ответ
212

Просмотры

Установление, что тип записи принадлежит к данному классу

Я сделал тип записи называемого графом, и я определил подходящий «является подграфом» отношений. Я хотел бы показать, что множество графиков вместе с подграфом относительно формы заказа, т.е. является экземпляром класса Ord. Но я не могу заставить его работать. Вот мой минимальный рабочий пример: теория Джон импортирует Основной начать typedecl узел запись графика = узлы :: «набор узлов» края :: «(узел × узла) набор» определение подграф :: «график ⇒ ⇒ графика BOOL» (инфикс «⊑ "50), где "G ⊑ H ≡ узлов G ⊆ узлов H ∧ ребра G ⊆ кромки H" лемма "(БОЛЬШОЕ H. H ⊑ G) = G" упс конца я получаю сообщение об ошибке: Тип объединение не удалось: нет Тип Arity graph_ext: : ог»Я пытался печатать такие вещи, как экземпляр граф :: Ord и создание экземпляра graph_ext :: Ord, но ничего не похоже на работу.
John Wickerson
1

голосов
1

ответ
336

Просмотры

Coq - Ошибка при устранении или

Я не знаю, почему, но в Coq, пытаясь доказать спецификацию программы я получаю сообщение об ошибке при попытке устранить или гипотезу,: Ошибка: Не удается найти устранение комбинатора or_rec, устранение индуктивного определения Logic.or на своего рода Набор, вероятно, не допускается. Это теорема я хочу доказать: Определение nat_div_mod: FORALL аб: физ, а не (Ь = 0) -> {ор: физ * физ | Р аб дг}. Это цель и контекст, когда происходит ошибка: а: физ Ъ: физ Н: б 0 Iha: {дг: физ * физ | P аб ор} х: физ * физ H2: P ABX H0: SND х <Ь - 1 \ / SND х> = Ь - 1 ______________________________________ {дг: физ * физ | P (S а) б ор} Перед этой теоремой, у меня есть это определение и этот импорт: Определение P (абы: физ) (ор: физ * физ): Опора: = ... (* спецификация DIV / мода *) Требуется Импорт Omega. Требовать Импорт Mult. Я получаю предыдущую ошибку, когда я пытаюсь использовать эту тактику: ELIM H0. Я действительно не знаю, что может быть причиной этого.
gonzaw
1

голосов
1

ответ
119

Просмотры

splitAt equality in Agda

How can someone prove this equality ≡splitAt : {α : Level} {A : Set α} {l₁ l₂ : Nat} -> (xs₁ : Vec A l₁) -> (xs₂ : Vec A l₂) -> (xs₁ , xs₂ , refl) ≡ splitAt l₁ (xs₁ ++ xs₂) ? The base case is obvious ≡splitAt [] xs₂ = refl But then ≡splitAt (x ∷ xs₁) xs₂ gives Goal: (x ∷ xs₁ , xs₂ , refl) ≡ (splitAt (suc .n) (x ∷ xs₁ ++ xs₂) | splitAt .n (xs₁ ++ xs₂)) This ≡splitAt (x ∷ xs₁) xs₂ with ≡splitAt xs₁ xs₂ ... | refl = {!!} throws an error: "Refuse to solve heterogeneous constraint refl...". And this ≡splitAt {l₁ = suc l₁} (x ∷ xs₁) xs₂ with splitAt l₁ (xs₁ ++ xs₂) ... | (xs₁' , xs₂' , refl) throws an error: "xs₁ != xs₁' of type Vec A l₁...". I wrote this definition: ++≡++ : {α : Level} {A : Set α} {l₁ l₂ : Nat} -> (xs₁ : Vec A l₁) -> (xs₂ : Vec A l₂) -> (xs₁' : Vec A l₁) -> (xs₂' : Vec A l₂) -> xs₁ ++ xs₂ ≡ xs₁' ++ xs₂' ++≡++ _ _ _ _ = {!!} but don't know, how to use it. Maybe there is some source, from where i can learn more about with-expressions? Thanks.
user3237465
1

голосов
1

ответ
38

Просмотры

Что такое GroupScope?

Во всех Coq кодов в ssreflect есть это утверждение Import GroupScope. Что такое GroupScope? Если это другой файл, где я могу скачать его из?
Sai Ganesh Muthuraman
1

голосов
1

ответ
101

Просмотры

Haskell сделать рецепт терпит неудачу для Paradox доказательства теорем с использованием GHC

Я пытаюсь установить теорему парадокс прувер получены из здесь. Когда я бегу Makefile это команда, которая работает: GHC -optl -static -lstdc ++ -I ../ Instantiate -I ../ MINISAT / ток базы ../minisat/current-base/Solver.or ../ MINISAT / ток базы / Prop.or ../instantiate/MiniSatWrapper.or ../instantiate/MiniSatInstantiateClause.or -fglasgow-exts -O2 -static -threaded -main-это Paradox.Main.main --make Paradox.Main -о парадокс И это приводит к нескольким ошибкам так: Flags.hs: 52: 8: не удалось найти модуль «Char» Используйте -v, чтобы увидеть список файлов искали. для различных модулей, включая, но не ограничиваясь Чаре, CPUTime, IO. Сообщение окончательной ошибки Makefile: 38: рецепт цели «paradox.exe» потерпел неудачу марки: *** [paradox.exe] Ошибка 1 Не знаю Haskell, и я очень опытный с GNU сделать, но я пытаюсь установить этот пакет для проекта и достаточно неясный не быть упакованы для моих ОС (я бег Arch Linux). Насколько я знаю, он не упакован для любой операционной системы, поэтому необходимо установить из источника. Насколько я могу сказать, что проблема начинается со следующим сообщением об ошибке: на командной строке: Внимание: -fglasgow-exts осуждается: Использование отдельных расширения вместо Я использую версию GHC, представленную в хранилище пакетов Arch Linux: пакет ссылка
Kit
1

голосов
1

ответ
79

Просмотры

Является ли время поиска Z3 чувствительным к формуле порядка?

Во многих языках программирования, ветвление эффективности зависит от порядка, в которой предусмотрены положения. Например, в Python, если р или д: произрастет в, если заявление, как только р истинно, так что, как правило, хорошая идея, чтобы обеспечить вычислительно легкие пункты первой. Я интересно, если то же самое верно для выполнимости проверки в Z3. Другими словами, существует ли какое-либо различие между проверки и (P, Q) и А (Q, P), при условии, что одна из формул является значительно более сложным, чем другой?
user287393
1

голосов
1

ответ
142

Просмотры

Использование массива в Z3PY

Я использую z3 для моего исследования и у меня есть следующие проблемы. Я анализирую модель выполнимой формулы, которая содержит массивы, но я не понимаю, результатов модели. Для exemplo, у меня есть две переменные «pkgcounter» и «rxlen», и два предложения p1 и p2. Моя цель состоит в том, чтобы выяснить, есть ли модель, которая удовлетворяет оба предложения. pkgcounter = Array ( 'pkgcounter', IntSort (), BitVecSort (8)) rxlen = Array ( 'rxlen', IntSort (), BitVecSort (8)) с = Solver () р1 = (pkgcounter <rxlen) р2 = (pkgcounter == rxlen) s.add (р1, р2), если s.check () == сидел: печать s.model () результатом является следующая модель: [rxlen = [остальное -> 0], pkgcounter = [остальное - > 0], K 0 = [еще -> 0]] Может кто-нибудь помочь мне интерпретировать этот результат? Потому что, если rxlen и pkgcounter имеют все поля, равные нулю, то предложение p1 не имеют модели.
Georgia
1

голосов
1

ответ
90

Просмотры

Получение принципа сильной индукции в Coq

Предположим следующее: Индуктивный бункер: Set: = Z | О. Fixpoint выдумка (п: физ): список бен: = матч п с | 0 => [Z] | S к => матч к с | 0 => [O] | S к «=> выдумка к» ++ выдумка к конец конец. Я хотел бы показать: Теорема fib_first: FORALL п, Nat.Even п -> п> 3 -> существует ж, выдумка п = Z :: ш. Однако, выполняя индукцией по п, я получаю действительно бесполезный индуктивной гипотезы фиксируя п, о том, что IH: Nat.Even п -> п> 3 -> существует ш: список бен, выдумка п = Z :: ш. То, что я бы в идеале иметь следующий: IH: FORALL п: физ, Nat.Even п -> п> 3 -> существует ш: список бен, выдумка п = Z :: ш. Естественно, я не могу предположить, оригинальное предложение, но он чувствует, как мне нужно, чтобы доказать что-то более сильное, возможно? Моя идея для индуктивных рассуждений будет возможным за счет расширения F п = F п-2. F п-1, мы знаем, F п-2 даже тогда и только тогда F п четно, и так как ни один из F п-2 или F п-1 пуст, мы можем показать подстрока короче, поэтому достаточно для индукции - как можно выразить это в Coq?
AntlerM
1

голосов
1

ответ
89

Просмотры

Кок не генерирует индукции

Я получил решение следующей теоремы, как показано ниже: Требовать Импорт Coq.Lists.List. Импорт ListNotations. Индуктивный суффикс {X: Тип}: список X -> Список X -> Prop: = | suffix_end: FORALL хз, суффикс хз хз | suffix_step: FORALL х Xs Ю.С., суффикс хз О -> суффикс (х :: хз) YS. Теорема suffix_app (X: Type) (хз YS: список X): суффикс хз YS -> существует, Ws, хз = WS ++ YS. Доказательство. индукционная 1 в [| х XSP YSP вс [ZS zeq]]. - существует []. рефлексивность. - в настоящее время существует (х :: ZS); переписать zeq. QED. Я пытался быстро скопировать его на другой машине и попытался его таким образом: Теорема suffix_app (X: Type) (хз YS: список X): суффикс хз YS -> существует, Ws, хз = WS ++ YS. Доказательство. индукция 1. - существует []. рефлексивность. - (* Застрял здесь *!) Прервать. т.е. без «как» п. Тем не мение, Я застреваю в связи с автоматическим названием эквивалента «zeq» не генерируется по причинам, которые я не могу работать вне. Почему не (автоматически переименовывается) эквивалент «zeq», порожденным Coq во втором случае здесь?
Sean Frötkék
1

голосов
1

ответ
204

Просмотры

Как шаблон матч на Prop когда доказав в Coq без устранения на тип

Я пытаюсь доказать, что хвост отсортированный список сортируется в Coq, используя шаблону вместо тактики: требовать импорта Coq.Sorting.Sorted. Определение tail_also_sorted {А: Проп} {Р: отношение А} {ч: {A}, т: список А} (Н: Сорт R (H :: гр)): Сортировано R, T: = Н матч в отсортированном _ (ч: : т) вернуться Sorted _ т с | Sorted_nil _ => Sorted_nil R | Sorted_cons rest_sorted _ => rest_sorted конец. Это не может, однако, с: Ошибка: Неправильное устранение «H» в индуктивного типа «отсортированных»: возвращаемый тип имеет своего рода «Тип» в то время как она должна быть «Опора». Устранение индуктивного объекта рода Prop не допускается предиката СНП типа, потому что доказательства могут быть устранены только строить доказательства. Я подозреваю, что это возможно в основном исчислению, как следующие Lean коды типа проверки и Lean также построена на CIC: индуктивный {α параметр отсортировано: Тип} [decidable_linear_order α]: Список α -> Prop | is_sorted_zero: параметр отсортировано [] | is_sorted_one: ∀ (х: α), параметр отсортировано [х] | is_sorted_many: ∀ {х: а} {YS: список а}, х <у -> (у параметра отсортировано :: YS) -> параметра отсортировано (х :: у :: YS) лемма tail_also_sorted {α: Тип} [decidable_linear_order & alpha;] : ∀ {ч: α} {т: список α}, параметр отсортировано (ч :: гр) -> т параметр отсортировано | _ [] _: = Is_sorted.is_sorted_zero | _ (у :: YS) (is_sorted.is_sorted_many _ rest_sorted): = rest_sorted параметр отсортировано (у :: YS) -> параметр отсортировано (х :: у :: YS) леммы tail_also_sorted {α: Тип} [decidable_linear_order α]: ∀ {ч: α} {т: список α}, параметр отсортировано (ч :: гр ) -> т параметр отсортировано | _ [] _: = Is_sorted.is_sorted_zero | _ (у :: YS) (is_sorted.is_sorted_many _ rest_sorted): = rest_sorted параметр отсортировано (у :: YS) -> параметр отсортировано (х :: у :: YS) леммы tail_also_sorted {α: Тип} [decidable_linear_order α]: ∀ {ч: α} {т: список α}, параметр отсортировано (ч :: гр ) -> т параметр отсортировано | _ [] _: = Is_sorted.is_sorted_zero | _ (у :: YS) (is_sorted.is_sorted_many _ rest_sorted): = rest_sorted
LogicChains
1

голосов
1

ответ
149

Просмотры

Decidable equality in Agda with less than n^2 cases?

У меня есть тип данных для AST из программирования LANGAUGE, что я хотел бы рассуждать об этом, но есть около 10 различных Конструкторы для AST. Данные Term: Установить, где UnitTerm: Срок VarTerm: Var -> Срок ... SeqTerm: Срок -> Срок -> Срок Я пытаюсь написать функцию, которая имеет разрешимый равенство синтаксических деревьев этого языка. В теории это просто: нет ничего слишком сложно, это только простые данные хранятся в АСТ. Проблема заключается в том, что писать такую ​​функцию, кажется, требуют около 100 случаев: для каждого конструктора, есть 10 случаев. eqDecide: (х: Term) -> (у: Term) -> Декабрь (х ≡ у) eqDecide UnitTerm UnitTerm = да REFL eqDecide UnitTerm (VarTerm х) = Generic.no (λ ()) ... eqDecide UnitTerm (SeqTerm t1 t2) = Generic. нет (λ ()) EqDecide (VarTerm х) = UnitTerm Generic.no (λ ()) ... Проблема заключается в том, есть связка избыточных случаев. После первого матча картины, где совпадают конструкторы, в идеале я мог бы сравниться с подчеркиванием, так как не возможно другой конструктор не может объединить, но это не кажется, что я могу сделать это. Я пытался и не использовать эту библиотеку, чтобы получить равенство: Я бегу в проблемы со строгой положительности, а также получить некоторые общие ошибки, которые я довольно трудно отлаживать. Прелюдия Agda также имеет некоторое средство для этого, но выглядит довольно незрелыми, и отсутствуют некоторые вещи, которые мне нужно из стандартной библиотеки. Как люди разрешима равенство на практике? Есть ли они смирятся с этим и просто написать все 100 случаев, или есть хитрость я м не хватает? Является ли это просто место, где новизна языка показывает до конца?
jmite
1

голосов
1

ответ
63

Просмотры

Как написать определение не зависимого от продукта с использованием типа Pi в Lean?

Я работаю через главу 7 - Индуктивные Типы «Теорема Доказывания в Lean». Я хотел бы знать, как написать определение зависимого не зависимый от продукта в более развернутой или «примитивной» форме. Похоже, что определение, данное в учебнике автоматически выводит некоторые детали: индуктивный prod1 (α: Тип и) (β: Тип v) | тк: α → β → prod1 Некоторые эксперименты позволяют заполнить подробно индуктивный prod2 (& alpha;: Тип и) (& beta;: Тип V): Тип (макс УФ) | тк: α → β → prod2 Однако дать определение в полной мере расширения формы, используя типы Pi не в typecheck: индуктивный prod3: П (а: Тип и) (β: Тип V), тип (макс ультрафиолетовый) | тк: α → β → prod3 Что такое правильный способ написания prod3? Наконец, заключается в следующем эквивалентное определение для prod1 и prod2, т.е. может тип проверки всегда подразумевать правильный тип вселенной для а и р? Индуктивный prod4 (α: Тип) (β: Тип) | тк: α → β → prod4
Adam Kurkiewicz
1

голосов
1

ответ
68

Просмотры

Из множества включения установить равенство в постном

Учитывая доказательство множества включения и его обратный, я хотел бы быть в состоянии показать, что два множества равны. Например, я знаю, как доказать следующее утверждение, и его обратное: открытое множество Вселенной у переменной elem_type: Тип переменной U A: установить elem_type переменная B: установить elem_type Защиту set_deMorgan_incl: A ∩ B ⊆ set.compl ((set.compl A) ∪ (set.compl B)): = Сожалеем Учитывая эти два включения доказательства, как я докажу установить равенство, то есть четкости set_deMorgan_eq: A ∩ B = set.compl ((set.compl A) ∪ (B set.compl )): = извините
Adam Kurkiewicz
1

голосов
1

ответ
100

Просмотры

Сложность применения доказательства в Идриса

I am attempting to prove a property over one of my defined data types as follows: reverseProof' : (inputBlock : Block iType iSize iInputs) -> (ind : Fin rSize) -> (rInputs : Vect rSize Ty) -> (receiveBlock : Block rType rSize rInputs) -> (prf : index ind rInputs = iType) -> (newInsert : MaybeBlockty iType) -> (HVect (replaceAt ind (MaybeBlockty iType) (map MaybeBlockty rInputs))) -> (HVect (map MaybeBlockty rInputs)) In attempting to prove this I am trying to use an earlier proved fact that: replaceAtProof' : (xs : Vect n a) -> (i : Fin n) -> (f : a -> b) -> ((index i xs) = x) -> (replaceAt i (f x) (map f xs)) = (map f xs) I was hoping that simply attempting to rewrite the appropriate expression in reverseAtProof' would achieve this, however when attempting to rewrite as follows: reverseProof' inputBlock ind rInputs receiveBlock prf newInsert x = rewrite replaceAtProof' rInputs ind MaybeBlockty prf in x I get the error as below: When checking right hand side of reverseProof' with expected type HVect (map MaybeBlockty rInputs) rewriting replaceAt ind (Maybe (len : Nat ** tyList : Vect len Ty ** Block iType len tyList)) (Data.Vect.Vect n implementation of Prelude.Functor.Functor, method map MaybeBlockty rInputs) to Data.Vect.Vect n implementation of Prelude.Functor.Functor, method map MaybeBlockty rInputs did not change type HVect (Data.Vect.Vect n implementation of Prelude.Functor.Functor, method map MaybeBlockty rInputs) I read this error as saying that it could not apply the attempted rewrite as it could not find the specified pattern within x. This would appear to be because the compiler reduces the definition of MaybeBlockty iType to be Maybe (len : Nat ** tyList : Vect len Ty ** Block iType len tyList) :EDIT as is the definition of MaybeBlockty Is there any way for me to prevent this from occurring so that the given rewrite will apply, or am I misreading the given error?
proverIdr
1

голосов
1

ответ
68

Просмотры

Обосновывая принцип взрыва в Agda

Поскольку Agda является интуиционистской один имеет постулировать закон исключенного третьего. Но, насколько я знаю, интуиционизм принимает экс Falso quodlibet или принцип взрыва (теорему, что все вытекает из абсурдности). Как можно доказать этот постулат: данные ⊥: Установить, где постулат ехр: ∀ {п} {х: Set п} → ⊥ → х
prover
2

голосов
0

ответ
15

Просмотры

Идрис: Докажите комплексные числа умножения ассоциативно

Я хотел бы, чтобы проверить экземпляр кольца для Data.Complex.Complex т при условии, конечно, т также кольцо. Это было легко до абелевой группы, но с экземпляром то кольцо странное происходит: VerifiedRing т => VerifiedRing (комплекс т), где ringOpIsAssociative (л: + Li) (с + Сl) (г + п)? = VerifiedRing_rhs_1 Теперь Идрис делает некоторое расширение самостоятельно и отверстие получить следующий вид: (л (сг обратный (ХИ п)), инверсный (Li (с п CI г))): + (л (с ри či г) Li (кр обратный (Х п))) = ((АЯ обратный (Li CI)) г обратный ((л CI Li с) п)) + ((АЯ обратным (Li CI)) п (л ДИ Li с) г) Я понять, что для доказательства равенства мне нужно пропустить некоторые скобки. Поэтому я начинаю с первым на: перезаписать ringOpIsDistributiveR л (сг) (обратный (Х п)) в VerifiedRing_rhs1 На что Идрис отвечает, что: (С п CI г))) ... Обратите внимание, что тип после не изменился тип отличается, чем один предполагалось ранее. Я в растерянности, чтобы понять, почему это меняет и почему переписывание не работает, если это, конечно, должно быть. Обратите внимание, что тип после не изменился тип отличается, чем один предполагалось ранее. Я в растерянности, чтобы понять, почему это меняет и почему переписывание не работает, если это, конечно, должно быть. Обратите внимание, что тип после не изменился тип отличается, чем один предполагалось ранее. Я в растерянности, чтобы понять, почему это меняет и почему переписывание не работает, если это, конечно, должно быть.
Sventimir
1

голосов
1

ответ
84

Просмотры

Построение доказательств для функции принятия решения в Идриса

Я пытаюсь создать функцию решения для типа, представляющих два последовательных элементов в модульном пространстве. (Этот код является производным от этого превосходного ответа на предыдущий мой вопрос.) PreceedsN данные: Nat -> Nat -> Nat -> Типа где PreceedsS: {автоматического PRF: S A `LT` м} -> PreceedsN м (S а) PreceedsZ: {автоматического PRF: S а = т} -> PreceedsN ма Z doesPreceedN: (м: Нат) -> (а: Нат) -> (б: Нат) -> Декабрь (PreceedsN MAB) doesPreceedN MAB с (S A `cmp` м) doesPreceedN (S A + S D) AB | CmpLT д с (S A `decEq` б) doesPreceedN (S A + S, D) AB | CmpLT d | Да ч.р.ф. = Да бис doesPreceedN (S а + S d) абы? | CmpLT d | ? Нет противопоказаний = Нет bNotSa doesPreceedN (S м) мб | CmpEQ с (б `decEq` 0) doesPreceedN (S м) м Z | CmpEQ | Да PRF = Да PreceedsZ doesPreceedN (S м) мб | CmpEQ | Нет противопоказаний = Нет saIsmAndbIsNotZ doesPreceedN (S м) (т + (S d)) б? | CmpGT d = Нет? SaCannotBeGTm Я сделал все возможное, но я не настолько еще знающие построить необходимые доказательства на своих собственных, особенно доказательств противного. Не могли бы вы ходить со мной через как заполнить одно или несколько отверстий в коде выше? Кроме того, если вы используете какие-либо полезные инструменты, как абсурдные, невозможные или тактик,
Etherian
1

голосов
1

ответ
160

Просмотры

Coq: Non-список структур данных, живущих в наборе?

Если у меня есть следующие строки: Определение Foo: Set: = список физ. то я компилируется без проблем. Однако предположим, что я хочу сделать то же самое с Coq.Lists.ListSet, библиотека, представляющая конечные множества в виде списка: (* Раздел first_definitions переменной A:.. Определение типа ListSet: = список A. *) Определение Bar: Set: = ListSet туземный Я получаю следующее сообщение об ошибке: Термин «ListSet нац» имеет тип «Type» в то время, как ожидается, имеют тип «Set» (вселенная несогласованности). Есть ли способ, чтобы «бросить» ListSet так, что он живет в наборе вместо типа? то есть, если я знаю, что я собираюсь использовать ListSet с параметрами типа Set, есть способ сделать это жить в Set иерархии какое-то образом? Почему ошибка случается для ListSet, но не для списка, когда ListSet определяется как список? Примечание: Фактический тип называется множество, но я Ве переименовали в ListSet, чтобы избежать путаницы с сортировки набора. EDIT: = заменены: =
jmite
1

голосов
1

ответ
125

Просмотры

Почему заявление Булева логика должна быть в КНФ (CNF)

Большинство вещей, которые я видел на обработку логических формул логики говорит первый, чтобы преобразовать его в КНФ или ДНФ форме. Википедия говорит, что это «полезно в автоматическом доказательстве», но не намного больше. Хочет знать, почему необходимо выполнить этот шаг, какой аспект этого в настоящее время воспользовались, в котором алгоритм и т.д., не зная больше, кажется, что некоторый стандартный алгоритм бы уже воспользовался этой функцией, то все последующие документы будут иметь Об этом заявил в качестве требования. Но, возможно, это не нужно.
Lance Pollard
1

голосов
1

ответ
121

Просмотры

Ltac: сделать что-то другое в каждой цели

У меня есть доказательства сценарий, где я изучает несколько случаев, и это в настоящее время довольно медленно, так как у меня есть целый ряд стратегий для решения задач, и я стараюсь каждый из них в каждом конкретном случае. Я знаю, что мне нужно применить определенную тактику в некоторых случаях, но я не уверен в том, как это сделать. Вот что у меня сейчас: индукционные е; интро; поза (bool_dec (is_v_of_expr е1)) в качестве VE1; уничтожение ve1; [> Thing1 | вещь 2]. который дает ошибку Неверная количество голов (ожидается 26 тактик, было дано 2). Я пытаюсь сделать thing1 в первом голе от самоуничтожения и thing2 второй гол от самоуничтожения, для каждого случая, порожденного индукции. Проблема заключается в том, индукция генерирует 13 подцелей, каждый из которых разбиваются на 2 пути деструктора. Локальный селектор [> thing1 | thing2] пытается соответствовать всем подцели, а не только те, полученные от конкретного самоуничтожения. Как я могу секвенирование тактика, так что деструктор выполняется на каждом отдельном случае, порожденной индукцией, то thing1 запускается на первое Разрушит сгенерированные цели и thing2 запускается на второй генерируемой цели, для каждого индукционного случае.
jmite
1

голосов
5

ответ
340

Просмотры

очередь парный приоритет

У меня есть набор элементов а и набор B, каждый с соответствующим числовым приоритетом, где каждый А может соответствовать некоторым или всем B и наоборот, и мой основной цикл в основном состоит из: Возьмите лучшее A и B в приоритетном порядке, и делать вещи с A и B. наиболее очевидным способом сделать это с одной приоритетной очередью (A, B) пар, но если есть 100 000 элементов а и 100,000 Б, то множество O (N ^ 2) пара выигранного «т помещается в памяти (и диск слишком медленно). Еще одна возможность для каждого А, петля через каждый B. Однако это означает, что глобальный приоритет упорядочения на А только, и мне действительно нужно иметь приоритет обоих компонентов во внимание. (Приложение доказательства теорем, где указанные выше параметры называются алгоритмом пара и данный раздел алгоритмом соответственно; недостатки каждого из них известны, но я убежище» т нашли каких-либо ссылок на хорошее решение.) Некоторые виды приоритетной очереди два слоя будет казаться указанной, но не ясно, как сделать это без использования либо O (N ^ 2) памяти или O (N ^ 2) время в худшем дело. Есть известный способ сделать это? Пояснение: каждый А должен быть обработан со всей соответствующей B, а не только один.
rwallace
1

голосов
1

ответ
1.8k

Просмотры

Где узнать о z3 теореме Доказывающего API, для C ++?

Я хочу научиться Z3 API-интерфейсов для C ++ и как использовать их в программе C ++. Я пытался найти учебник, но не мог. Где я могу узнать, что из? Любой учебник или что-то? Благодарю.
user2347029

Просмотр дополнительных вопросов