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

Вопросы с тегом
3 ответа

Логика высказываний и доказательства

Я пытаюсь доказать приведенный ниже случай для домашнего задания, и я работал над ним часами, но все же не повезло. r) -> p -> q -> r"> Любые предложения или комментарии относительно того, что я делаю неправильно?
17 фев '16 в 03:21
1 ответ

Подтверждение ответа API

Допустим, у меня есть доступ к API погоды https. Допустим, я запрашиваю его состояние работоспособности в четверг 17/08/2017 23:30 и API отвечает ОК (простой ОК http код). Как клиент, я должен доказать в будущем, что служба действительно ответила мн…
17 авг '17 в 12:27
1 ответ

Как вы используете индукцию с тактикой / Изара в Изабель /HOL?

Я пытаюсь понять, почему каждый из приведенных ниже примеров работает или не работает, и более абстрактно, как индукция взаимодействует с тактикой против Изара. Я работаю над 4.3 в Программировании и проверке в Isabelle/HOL (декабрь 2016) для Window…
03 сен '17 в 14:56
1 ответ

Доказательство ассоциативности Nats vs. Lists

Я сравниваю доказательства ассоциативности для Nats и Lists. Доказательство на списках идет по индукции lemma append_assoc [simp]: "(xs @ ys) @ zs = xs @ (ys @ zs)" by (induct xs) auto Но доказательство на Натса lemma nat_add_assoc: "(m + n) + k = m…
27 фев '18 в 19:15
4 ответа

Почему (a | b) эквивалентно a - (a & b) + b?

Я искал способ сделать BITOR() с базой данных Oracle и натолкнулся на предложение просто использовать вместо него BITAND(), заменив BITOR(a,b) на a + b - BITAND(a,b). Я проверил это вручную несколько раз и убедился, что оно работает для всех двоичны…
21 окт '09 в 23:43
1 ответ

Доказательство Биг-Тета нотации

Здравствуйте, я старался изо всех сил, чтобы понять биг-тета, и теперь я получил основную концепцию доказательств для Big-Oh и Big-Omega, но я не смог найти и пример, который близок к моему упражнению, потому что я не могу сделать доказательство том…
28 мар '11 в 20:44
1 ответ

Как доказать комбинацию асимптотических обозначений?

Я думаю, что хорошо понимаю, что означают обозначения Big O, omega и theta и как доказать, является ли функция одной из них. Я не понимаю, как доказать их комбинацию, как в проблеме. Может ли кто-нибудь объяснить это мне? Θ (n) + O (n ^ 3) = O (n ^ …
20 янв '17 в 15:55
1 ответ

Рассмотрим числа 1,2,...,1000. Покажите, что среди любых 501 из них существуют два числа, так что одно делит другое.

Я сталкивался с этим вопросом в книге Матушека и Несетрила "Приглашение к дискретной математике". Я новичок в подобных проблемах. Я подошел к этой проблеме следующим образом: два числа, выбранные среди любых 501 чисел, состоят из делителя и дивиденд…
06 янв '16 в 05:13
0 ответов

Доказательство правильности алгоритма максимального подмассива грубой силы

Я пытаюсь доказать правильность версии грубой силы проблемы максимального подмассива, приведенной ниже: def max_subarray_bf(lst): left = 0 right = 0 max = lst[0] for i in range(len(lst)): current_sum=0 for j in range(i, len(lst)): current_sum+=lst[j…
20 фев '18 в 22:15
1 ответ

Как доказать предусловие Ada/SPARK для функции, встроенной в двойной цикл

Я пытаюсь доказать, что предварительное условие "prepend" выполняется во время выполнения программы ниже. Предварительное условие: Length (Container) < Container.Capacity Мои попытки доказать это приведены в коде ниже в форме прагм. Я могу доказа…
12 ноя '17 в 00:05
2 ответа

Доказывая некоторые законы монады на монаду ошибки, которую я написал

Итак, я создал отдельную монаду об ошибках, и мне было интересно, как мне доказать несколько законов монады для нее. Если кто-то захочет найти время, чтобы помочь мне, это будет очень цениться. Спасибо! И вот мой код: data Error a = Ok a | Error Str…
07 мар '11 в 00:41
1 ответ

Помощь при выводе типа в OCaml

Как бы я продолжил с доказательством того, что эти две функции хорошо напечатаны? Я немного растерялся с этим вопросом. let rec reduce f lst u = match lst with | [] -> u | (h::t) -> f h (reduce f t u) let rec forall2 p l1 l2 = match (l1,l2) wi…
18 окт '17 в 00:08
1 ответ

Доказательства Z3: всегда ли правила гипотез и лемм четко вложены?

Быстрый вопрос: В доказательстве Z3 (например, 4.3.2) правило "гипотезы" вводит локальное допущение, которое в конечном итоге отбрасывается правилом "леммы". Являются ли правила "гипотезы" и "леммы" всегда чисто вложенными, означая, что можно сопост…
28 апр '15 в 18:47
1 ответ

Разбиение натуральных чисел на множества

Как мне доказать следующий вопрос Докажите, что в любом разбиении N9 (первых девяти натуральных чисел) на три набора будет хотя бы один набор, произведение чисел которого больше или равно 72.
25 апр '17 в 07:06
0 ответов

Худший случай для стабильных совпадений

В проблеме стабильного сопоставления я пытаюсь сгенерировать списки предпочтений для худшего случая. Я наткнулся на статью, в которой говорится, что это худший случай для n=5 m1: w1 w2 w3 w4 w5 m2: w2 w3 w4 w1 w5 m3: w3 w4 w1 w2 w5 m4: w4 w1 w2 w3 w…
03 апр '16 в 04:44
3 ответа

Докажи это! не находится в O(n^p) для любого постоянного натурального числа p

Как я могу доказать, что п! не в O(n^p) для любого постоянного натурального числа p? И есть (n k)(n выбрать k) в O(n^p) для всех k?
07 ноя '10 в 00:53