Описание тега proof

Вопросы с тегом
Математическое доказательство - это любой математический аргумент, который демонстрирует истинность математического утверждения. Неформальные доказательства обычно представляются на естественном языке и признаются верными консенсусом; формальные доказательства обычно представляются символически и могут быть проверены механически. "Доказательства" могут быть действительными или недействительными; только первый вид представляет собой фактическое доказательство, тогда как второй тип обычно относится к ошибочной попытке доказательства.
1 ответ

Почему этот код SBV останавливается перед достижением установленного мной лимита?

У меня есть эта теорема (не уверен, что это правильное слово), и я хочу получить все решения. pairCube limit = do m <- natural exists "m" n <- natural exists "n" a <- natural exists "a" constrain $ m^3 .== n^2 constrain $ m .< limit retu…
08 дек '15 в 18:01
2 ответа

Как мой профессор придумал рекурсивный случай в этом анализе алгоритма?

Мой профессор дал нам следующее объяснение рекурсивного алгоритма для нахождения перестановок набора чисел: Когда у него есть (T(m+1), n-1)), откуда это? Почему это m + 1 и n-1? Я действительно не понимаю, откуда это.
15 окт '13 в 15:01
1 ответ

Агда: Вектор Членство в Stdlib? (А как научить стдлиб вообще)

Я имею дело со строками в Агде, и у меня есть их вектор. Мне нужно проверить, встречается ли данная строка в векторе (как часть проверки, является ли переменная свободной или связанной в выражении, в теории PL, которую я делаю wprk). Я все еще пытаю…
06 мар '17 в 19:05
1 ответ

Пересечение двух разрешимых по Тьюрингу языков разрешимо по Тьюрингу

Докажите, что пересечение двух языков, разрешимых по Тьюрингу, разрешимо по Тьюрингу. (Учитывая алгоритмы для выбора каждого языка, опишите алгоритм, чтобы определить, принадлежит ли строка к пересечению.) Я знаю, что язык является разрешимым по Тью…
05 дек '15 в 20:30
1 ответ

Big Oh и Omega доказательство сложности обозначений

Докажите, что n3 не находится в O (n2) Докажите, что n3 не входит в OMEGA (n4)
27 фев '14 в 04:49
1 ответ

Решение уравнения с использованием обобщения основной теоремы

Я прошу помощи в объяснении, как работает доказательство. Я видел примеры этого, но мне трудно понять это. Докажите следующее Решение уравнения T (n) = aT (n / b) + Θ (nk logp n), где a ≥ 1, b> 1, p ≥ 0 T (n) = O (nlogb a), если a> bk T (n) = O (nk …
29 ноя '16 в 05:07
1 ответ

Elim гипотеза двойного отрицания в Coq Proof Assistant?

Может ли кто-нибудь объяснить мне, почему мы должны доказать ~A после elim Ha.? Перед "элим ха" 1 subgoals A : Prop Ha : ~ ~ A ______________________________________(1/1) A После 1 subgoals A : Prop Ha : ~ ~ A ______________________________________(…
02 июн '14 в 13:44
1 ответ

Определение интервальной функции в Coq

Я пытаюсь определить функцию в Coq, называемую интервалом, которая с учетом двух натуральных чисел вычисляет список всех натуральных чисел между этими двумя. Однако мое определение не является примитивно-рекурсивным. Вот мой код: Require Coq.Program…
13 ноя '15 в 12:05
1 ответ

Знание, когда доказательство в стиле Изара действительно в Изабель

Я работаю над упражнением, пытаясь выучить язык изар. У меня есть следующий скрипт для леммы о списках. lemma "EX ys zs. xs = ys @ zs ∧ (length ys = length zs ∨ length ys = length zs + 1)" proof - show ?thesis by blast (* L *) qed Кажется, Изабель п…
11 янв '19 в 22:56
1 ответ

Простое доказательство потока единиц в Coq

Взяв код из CPDT, я хотел бы доказать свойство для легкого потока ones, которые всегда возвращаются 1, CoFixpoint ones : Stream Z := Cons 1 ones. Также из CPDT я использую эту функцию для получения списка из потока: Fixpoint approx A (s:Stream A) (n…
22 окт '14 в 21:21
1 ответ

Доказывая Агде, что мы говорим об одном и том же

Я пытаюсь доказать противоречие, но сталкиваюсь с проблемой, пытающейся доказать Agda, что тип домена сигмы, возвращаемый <>-wt-inv та же сигма, что и в предыдущем доказательстве. Я ожидаю, что доказательство uniq-типа должно помочь мне там, н…
07 апр '15 в 19:13
1 ответ

Ищет похожие известные проблемы

Я пытаюсь доказать компьютерную сложность этой задачи оптимизации:Для заданного связного графа G = (V, E) и множества S ⊊ V. Найдите связный подграф G'= (V', E '), который: Min f(G') Min |V'| Подчинить: S ⊊ V’ V’ ⊆ V Это выглядит как обобщение задач…
15 ноя '12 в 17:15
1 ответ

Learning coq, не уверен, что означает ошибка NNPP

Так что я только начал изучать coq (и это пока слишком далеко), и я пытаюсь сделать базовое доказательство, и я довольно потерян, нашел некоторую помощь до сих пор, но я думаю, что я должен делать coq выдает ошибку. Итак, в моей части редактора у ме…
27 фев '19 в 02:40
2 ответа

Доказательство, включающее развертывание двух рекурсивных функций в COQ

Я начал изучать Coq и пытаюсь доказать что-то, что кажется довольно простым: если список содержит x, то число экземпляров x в этом списке будет> 0. Я определил функции contains и count следующим образом: Fixpoint contains (n: nat) (l: list nat) : Pr…
17 апр '17 в 13:08
1 ответ

Трехсторонняя и двухсторонняя сортировка без потери общности?

Итак, я изучаю трехстороннюю сортировку слиянием и задаюсь вопросом об отсутствии потери общности. давайте предположим, что у нас есть массив A'со степенью 3 элемента и A со степенью любой константы. Вот мой вопрос Почему предположение о том, что n(…
01 фев '19 в 04:44
1 ответ

Показывает f(n) = O(f(n) + g(n))?

Мне было интересно, что доказательство для следующего сравнения Big-O: f (n) является O(f(n) + g(n))) Я понимаю, что мы могли бы использовать: f (n) ≤ константа * (f(n) + g(n)) Но я не знаю, как это сделать. Как насчет случая, когда мы заменяем big-…
18 сен '13 в 19:24
1 ответ

Доказательство - Coq - Нужна ли индукция?

У меня есть сценарий, в котором я хочу доказать лемму, включающую ряд строковых переменных и переменных списка. Возможно, для этого нужна "индукция", но кто-нибудь может мне помочь доказать лемму, приведенную ниже. Если остальной код нужен, я тоже м…
18 июн '12 в 08:49
2 ответа

Как решить задачи с неверными типами равенства в Coq?

Мои сценарии проверки дают мне глупые равенства типа nat = bool или жеnat = list unit который мне нужно использовать для решения противоречивых целей. В обычной математике это было бы тривиально. Данные наборы bool := { true, false } а такжеnat := {…
01 сен '12 в 01:59
1 ответ

Есть ли недостатки в моем алгоритме Greedy?

Мне было просто интересно, если бы вы могли увидеть какие-либо недостатки или проблемы с моим алгоритмом Жадность, который я придумал, чтобы решить эту проблему. Проблема в: Они набор сотрудников Каждый сотрудник имеет одну рабочую смену, которая пр…
19 фев '13 в 03:11
1 ответ

Доказательство того, что бинарное дерево с n листьями имеет высоту не менее log n

Мне удалось создать доказательство, которое показывает, что максимальное количество узлов в дереве равно n = 2^(h+1) - 1, и логически я знаю, что высота двоичного дерева равна log n (могу нарисовать его) чтобы увидеть) но у меня возникли проблемы с …
22 авг '17 в 12:16