Читали тему (1): Анонимы (1)
Читали форум (3): Анонимы (3)
|
|
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Привет коты! В продолжение Найдите д.н.ф. и к.н.ф. для : Необходимо реализовать следующее. Input (ДНФ) Код: sql 1. (в задании предполагается что "+" - это логическое OR, а восклицательный знак - это инверсия) Outpus (минимальная форма): Код: sql 1. Можно брать метод Квайна или Квайна-Макласски. Primary Goal: Реализация на любом языке. Главное чтоб были сорцы и было понятно. Secondary Goal #1: Потестировать скорость на большом числе аргументов (16 - 32). Secondary Goal #2: Попробовать эвристики о которых говорил exp98. Цитирую его Случайный метод: от простого к сложному отжигом, роевым, генетическим ... пока таблица не станет хэммингово близкой к нужной. Затем доработать напильником, мож что и получится. Эффективность этого способа мне не известна. Тестовые данные Здась https://www.sql.ru/forum/1134172/tyapnichnyy-koi-8r можно взять больше тестовых данных. Например таблицу koi8-unicode16. Если ковертить обратно от unicode-русских букв то получается 14 аргументов в каждом минитерме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2021, 01:20 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
результат должен быть в виде ДНФ? и почему вторничный, если уже среда? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2021, 16:19 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Начал писать пост во вторник. Да. Результат в СДНФ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2021, 17:53 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Не упоминайте мене в суе. Возможно, сейчас напишу крамолу. Эта формула мне представляется из класса P . Автоматика и телемеханика, 1995, выпуск 2, с. 111–124 "Новые классы КНФ, с полиномиально распознаваемым свойством выполнимости" Б.А.Кулик АннотацияНа основе методов алгебры кортежей [1] разработан алгоритм решения задачи ВЫПОЛНИМОСТЬ КНФ. Доказано, что для класса "плотных" КНФ, у которых "пустые" переменные, не включенные в дизъюнкты, распределены равномерно с вероятностью не более 1/3, сложность этого алгоритма в среднем полиномиальна. Рассмотрены варианты выигрышной стратегии этого алгоритма, позволяющие расширить класс КНФ с полиномиально распознаваемым свойством выполнимости ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.12.2021, 23:09 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Буду упоминать. Это usecase нашего форума. Так что, не обижайся. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 10:09 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Ну и зря. Какхозяин своего слова могу его и обратно взять. Но всё же, пока на бумажке, набросал даже ещё не эскиз прототипа алгоритма, скорее некий пробник, посмотреть, имеет ли смысл дёргаться. Скоро не обещаю, нууу м.б. в выхи. Идея простая, наращивать формулу с нуля - какая получится. Для применения с не очень длинными формулами. Без эвристик. Набросок схемы примерно такой. For ........... Наращивать "как бы конкатенацией" с нуля формулу в зависимости от 3-х случайных зачений: z1 - номер очередной переменной (х1, х2 или х3) z2 - сотрицанием или без z3 - с какой связкой присоединяется к предудущей формуле " & " / " V " Вычислить текущий вектор истиностных значений и сравнить с входным. Откат текущей итерации, если близость уменьшилась. Условие прекращении цикла End For Примерно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 15:30 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Если считать близость как расстояние хемминга, то может быть один или группа битиков перепрыгивает или меняют своё место формально улучшая будущий расклад, но наша формула не видит улучшений. Тоесть метрика Хемминга наверное не очень чувствительна к улучшениям. Может брать какой-то другой критерий? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 15:53 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 Идея простая, наращивать формулу с нуля - какая получится. Для применения с не очень длинными формулами. Без эвристик. Набросок схемы примерно такой. For ........... Наращивать "как бы конкатенацией" с нуля формулу в зависимости от 3-х случайных зачений: Тут даже самый первый ход не понятен. Вот формула !x!y!z + !xy!z + x!y!z + x!yz + xy!z Как наращивать? Можно хотя-бы "прошагать" с тобой первые 2 итерации цикла? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 16:37 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Во-первых, это всего лишь эксперимент, не известно к чему приведущий. Поэтому рекомендаций не даю. Во-вторых, исходная формула нужна только, чтоб вычислить вектор её значений. Наращивать от нуля, вот же написано, три (пока 3) случайные величины: авторz1 - номер очередной переменной (х1, х2 или х3) z2 - с отрицанием или без z3 - "&" или "V" Сначала буду держать такой последовательный массив для отладки. А вообще, в символьном виде наращивание может выглядеть так (здесь пробел вместо умнож). Код: plaintext Проблем много. Метрика, собссно новая длина, критерий остановки. И конечно же как допилить. Проблему новой длины я сначала прозевал, да. Если в обратную сторону, т.е. от начальной формулы к более короткой, конкретных мыслей нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 18:48 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
"Автоматизацией Квайна" занимались с шестидесятых годов до 80-х прошлого века. Потом это стало не актуально. Сегодня можно найти тексты программ "Квайна" практически на любом языке программирования. В предыдущем обсуждении булевых функций, ссылка на которое дано в первом сообщении, был задан вопрос о критериях минимизации. Без ответа на этот вопрос минимизация теряет смысл. Для программистов это может быть стандартный критерий: наименьшее количество переменных в записи функции и операций над ними. Для схемотехников - это отсутствие гонок; минимальное количество логических элементов, желательно одного типа; минимальное число корпусов микросхем, . . . Здесь, кроме минимизации логических функций, появляется понятие "факторизация булевых функций". Сегодня большинство логических схем реализуются на ПЛМ (программируемых логических матрицах). Здесь булева функция должна быть представлена в ДНФ и критерием оптимизации является площадь ПЛМ, занимаемая этой функцией. Чем меньше, тем лучше, но не забыть бы при этом о гонках. Да, еще есть ситуации, когда для реализации всех необходимых логических функций одной ПЛМ не хватает, тогда к минимизации может добавиться понятие "декомпозиция булевых функций". Кстати говоря, рассматривать логические функции, зависящие более чем от 7 переменных, скорее всего, не имеет смысла, так они находятся за гранью человеческого восприятия. Поскольку от минимизации ДНФ не уйти, а карты Карно хороши для функций, зависящих не более чем от 4-х переменных, в следующем сообщении еще раз рассмотрим алгоритм Квайна. Постараемся обойтись только самыми простыми законами алгебры логики, чтобы потом не дорабатывать результат драчёвым напильником. Тем более, что ТС уже пятилетку говорит об этом алгоритме, но все еще не добрался до его реализации. В Союзе пятилетку обычно выполняли за три года. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 18:48 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
До программной реализации алгоритма Квайна еще очень далеко, сначала нужно понять, в чем же он состоит. Я уже рассмотрел его в сообщении 22406820 . Сейчас подробнее рассмотрим применение этого алгоритма к предложенной ТС функции !x!y!z + !xy!z + x!y!z + x!yz + xy!z. Каждое "слагаемое" в СДНФ называется конституентой единицы (в СКНФ каждое "произведение" называется конституентой нуля), если контекст понятен, то просто говорят конституента. Конституенту можно представить набором нулей и единиц. Если некоторая переменная входит в конституенту с отрицанием, то вместо нее в наборе пишем 0, в противном случае – 1. Например конституента !x!y!z записывается как набор 000, а конституента !xy!z – 010. Операция склеивания этих двух конституент: Код: plaintext 1. 2. Представим исходную функцию (СДНФ) в виде набора конституент (столбик 1). Наборы пронумеруем. Проведем все склейки (в скобках через черточку указаны номера наборов, из которых получена импликанта, а сами эти наборы отметим плюсиком): Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Код: plaintext 1. 2. 3. 4. 5. Поскольку больше склеивать нечего, то процесс нахождения простых импликант закончен. 3. На этом этапе находится покрытие исходной функции найденными простыми импликантами. Очевидно, что две найденные простые импликанты покрывают исходную булеву функцию. Осталось записать ответ F(x, y, z) = x¬y \/ ¬z или в нотации ТС: F(x, y, z) = x!y + !z. Перебор можно уменьшить, если помнить, что могут склеиваться только конституенты, отличающиеся только в одном "разряде". Поэтому конституенту 1 из исходного набора нет смысла сравнивать с конституентами 4 и 5. Собственно - это и весь алгоритм Квайна с его улучшениями. Т.е. все улучшения сводятся к сокращению числа перебора двоичных наборов. Теперь можно перейти к реализации этого метода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 18:52 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Что касается выбора структуры данных, то это массив. Каждый набор может быть представлен массивом, в котором каждый элемент может принимать значения 0, 1, *. Тогда массив наборов будет представлять СДНФ логической функции. Достоинства такого представления логической функции в простоте операций склеивания, а недостатком излишнее потребление памяти. Попробуем взять в качестве одного набора одно целое число и манипулировать битами этого числа. Для представления одной переменной потребуется два бита: 1 0 - биты числа 0 0 - представляют не х1 0 1 - представляют х1 1 * - представляют склейку по переменной х1, в этом контексте знак * обозначает, что значение бита может быть любым и не имеет значения. Для отметки будем использовать знак числа. Число отрицательное говорит о том, что этот набор был склеен с другим набором. Для 32-битного числа можно задать до 15 булевых переменных. Функции будет представлять массив целых чисел. Пример склейки ¬x¬y \/ ¬xy = ¬x. Биты 3 и 2 будут представлять переменную x, а биты 1 и 0 – переменную y. Код: plaintext 1. 2. 3. 4. 5. Алгоритм: 1. Записываем СДНФ в первый массив, а второй очищаем. 2. Каждый элемент первого массива сравниваем со всеми другими элементами этого массива, кроме себя с собой, на возможность их склейки. Возможности сокращения перебора я привел в предыдущем сообщении. Если элементы удовлетворяют условиям сравнения (склеиваются), то отмечаем их изменением знака числа и формируем из них одно число (склейку), которое записываем во второй массив. 3. Запоминаем неотмеченные элементы первого массива и после этого заменяем значение первого массива значением второго массива. Второй массив очищаем. 4. Повторяем пункты 2 и 3 пока есть склеиваемые элементы. 5. Запомненные неотмеченные элементы и будут простыми импликантами. Теперь нужно найти покрытие исходной функции импликантами в соответствии с выбранным критерием. В литературе описано несколько алгоритмов решения этой задачи. Собственно алгоритм Квайна заканчивается нахождением простых импликант, поэтому этот этап я не рассматриваю. Осталось описать функцию сравнения наборов на предмет склейки и можно будет переходить к программированию на выбранном языке. Но у меня сегодня уже иссякли силы для продолжения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 18:58 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l ...В Союзе пятилетку обычно выполняли за три года. Wlr, такие простыни надо бы прятать в спойлеры. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 18:58 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
А ещё я забыл сказать, что если много переменных, то по моей методе на каждой итерации растущей формулы, надо вычислять новый вектор значений для всех 2^ p комбинаций из p переменных. Т.о., если длина формулы сравнима с 2^p, то алгоритм заведомо экспоненциальный. Что не очень устраивает. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 20:23 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l В предыдущем обсуждении булевых функций, ссылка на которое дано в первом сообщении, был задан вопрос о критериях минимизации. Без ответа на этот вопрос минимизация теряет смысл. Для программистов это может быть стандартный критерий: наименьшее количество переменных в записи функции и операций над ними. Это - форум программистов. Поэтому будем искать наименьшее количество переменных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 20:53 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l Поскольку от минимизации ДНФ не уйти, а карты Карно хороши для функций, зависящих не более чем от 4-х переменных, в следующем сообщении еще раз рассмотрим алгоритм Квайна. Постараемся обойтись только самыми простыми законами алгебры логики, чтобы потом не дорабатывать результат драчёвым напильником. Тем более, что ТС уже пятилетку говорит об этом алгоритме, но все еще не добрался до его реализации. В Союзе пятилетку обычно выполняли за три года. 1) К чорту Карно. 2) Да ТС - большой бездельник. Я тут делаю +100. Но как говорил красавчик, начальник милиции всего Махачкалы - "и тем не менее..." ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 20:59 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l Кстати говоря, рассматривать логические функции, зависящие более чем от 7 переменных, скорее всего, не имеет смысла, так они находятся за гранью человеческого восприятия. В топике нас не будет интересовать человеческое восприятие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 21:05 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l Что касается выбора структуры данных, то это массив В своей реализации я хотел уйти от битов. И просто перейти к использованию списков символов. Или к деревьям. Но .. лучше начать со списков. Wlr-lПопробуем взять в качестве одного набора одно целое число и манипулировать битами этого числа. Для представления одной переменной потребуется два бита: 1 0 - биты числа 0 0 - представляют не х1 0 1 - представляют х1 1 * - представляют склейку по переменной х1, в этом контексте знак * обозначает, что значение бита может быть любым и не имеет значения. Игры с кубитами или с иммитацией символа asterisk "*" кажутся мне не очень актуальными применительно к решению задачи которая в пределе двигается к экспоненциальной. Памяти у нас сегодня достаточно чтоб не обращать внимание на биты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.12.2021, 22:46 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Остальные молчат)), так хоть я немножко добавлю. Сляпал черновичок проги по алгоритму случайного подбора, что выше. Только без откатов и без условия окончания, чтобы только посмотреть варианты. Ограничился 15 итерациями в каждом запуске (соответственно 15 переменных с повторениями). Запускал прогу несколько раз, пока не встретил в конце distance=2. На этом и закончил. Скажу точнее. Массив значений distance(k) , где k - итерация, заканчивался числами ... 2 3 3. Значит на 14-й итерации надобыло делать откат. Вот что получилось. Исходные данные. Получить ф-цию ДНФ: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. Результат случайного наращивания (всего 15 итераций, 14-15-ые откат, осталось 13 переменных, distance=2) x3 + ~x1 ~x2 + x3 + ~x2 ~x2 ~x3 ~x1 + x1 ~x3 + ~x3 + x1 + ~x2 [+x3 + ~x3] После ручной оптимизации (~Y + X ~Z ) = ( 1, 1, 0, 0, 1, 1, 1, 0 ), distance=2 Далее по задумке в ход идёт напильник. Тут разные лёгкие пути, но ф-ла сократилась и видно по таблице глазами, что последние 4 набора значений совпали с тебуемым. Осталось допилить для первых 4х наборов. И видно, что тут достаточно инвертировать 2-3й наборы, причём получить в 1-4м наборах зависимость ~x3. Самая уж короткая таким путём может и не получится, но в этом частном случае есть надежда, что всё же итог будет короче. Обобщать сказанное на все функции слишком рано. P.S. Пишу тильду (~) вместо "!", чтобы было лучше видно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.12.2021, 20:53 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Кстати допилить можно и так. Для примера. Формулу (~Y + X ~Z ) 1) ...*Х домножить 2) ... + ~(X ~Z)= ... + ~X +Z = прибавить отрицание 2-го слагаемого == аннулирование 3) ... + Z Если не ошибся, получим искомый рез-т (X ~Y + Z). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.12.2021, 21:11 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Боюсь спросить. Почему, когда говорят, сколько штук различных дизъюнктов(слагаемых) всего может быть в ДНФ, называют 2^ 3 ^N ? В Яблонском, Мендельсоне ... Мне кажется, что немножко меньше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2021, 19:56 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Так случилось, что сам и разобрался. Просто внимательно прочитал очевидное место в Яблонском. Из-за сомнений я разрывался между 2-мя подходами к ответу. Теперь однозначно речь идёт об ощем числе различных наборов конъюнкций (да и дизъюнкций тоже), а пустой набор явно обзывается как "1". Число отображений {x1 x2 ...} --> {xk ~xk пусто} = 3^n ровно. Соответственно всего логических ф-ций как и было указано. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2021, 16:27 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Насчёт своих экмпериментов со случайными формулами. Вывод про концепцию негативный. Много их не проводил. Первичные допустимые формулы не использовал. Рассмотрел только 2 исходных ф-ции. Для 3-х переменных оказалось мало интересным. Для 4-х переменных взял исходный вектор с 3-мя нулями (из 16 возможных). И результаты случайных подстановок не порадовали. Ну да, различие в 3-х координатах находилось быстро, в пределах 5-15 итераций. Но что такое были эти 3 различия? Это полностью "1"-ый вектор! Хоть стой, хоть падай. В рез-те "допиливание" ни чем не лучше начала от типовой СДНФ. Для 4-х переменных получались векторы <> "1" с 3-мя отличиями, но хорошо, когда "допилить" надо 0 до 1, а когда 1 до 0, то уже не лучше стандартной КНФ. 2 отличия находились при >100, или даже >400 итераций, а дальнейшая работа та же самая, что и выше. Во всяком случае если эти "3 или 2 отличия" << 2^n. Соображения с корреляциями могут помогать, но не превращаются в формальную методику. Короче говоря, не получилось простым навалом надёжно наворотить хороший случайный вектор. Если без откатов, то доходишь до тупика. Если делать откат, то необходим полноценный поиск с возвратом. Но не смог придумать эвристики (наподобие правильных перестановок или даже шахмат), чтобы удачно перепрыгивать с ветки на ветку без полного перебора. Но я знаю одного мастера по эвристикам. И как проблематичный вопрос. Тот же Яблонский пишет, что доля минимальных ДНФ среди тупиковых -->0. И это "...заставляет думать, что статистические соображения вряд ли что дают для алгоритма упрощения [ДНФ/КНФ]". Думать-то оно заставляет, только ведь и в задаче нахождения максимума отжигом случайность неплохо приближается к ответу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2021, 17:05 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Я решил восстановить тестовые данные в более каноничном виде. Рудиментарные предикторы и отклики x8, y16-y15 я вернул обратно. Так будет правильно. Чуть позже я попробую сконвертить их в каноническое уравнение ДНФ. Берите в качестве тестовых данных. Если слишком мало - я придумаю другую функцию конвертер. Пока будет koi8-to-UTF-16. koi8-rutf-16charx8..x1y16..y1802500─100000000010010100000000812502│10000001001001010000001082250C┌100000100010010100001100832510┐100000110010010100010000842514└100001000010010100010100852518┘10000101001001010001100086251C├100001100010010100011100872524┤10000111001001010010010088252C┬100010000010010100101100892534┴1000100100100101001101008A253C┼1000101000100101001111008B2580▀1000101100100101100000008C2584▄1000110000100101100001008D2588█1000110100100101100010008E258C▌1000111000100101100011008F2590▐100011110010010110010000902591░100100000010010110010001912592▒100100010010010110010010922593▓100100100010010110010011932320⌠1001001100100011001000009425A0■100101000010010110100000952219∙10010101001000100001100196221A√100101100010001000011010972248≈100101110010001001001000982264≤100110000010001001100100992265≥1001100100100010011001019A00A0 1001101000000000101000009B2321⌡1001101100100011001000019C00B0°1001110000000000101100009D00B2²1001110100000000101100109E00B7·1001111000000000101101119F00F7÷100111110000000011110111A02550═101000000010010101010000A12551║101000010010010101010001A22552╒101000100010010101010010A30451ё101000110000010001010001A42553╓101001000010010101010011A52554╔101001010010010101010100A62555╕101001100010010101010101A72556╖101001110010010101010110A82557╗101010000010010101010111A92558╘101010010010010101011000AA2559╙101010100010010101011001AB255A╚101010110010010101011010AC255B╛101011000010010101011011AD255C╜101011010010010101011100AE255D╝101011100010010101011101AF255E╞101011110010010101011110B0255F╟101100000010010101011111B12560╠101100010010010101100000B22561╡101100100010010101100001B30401Ё101100110000010000000001B42562╢101101000010010101100010B52563╣101101010010010101100011B62564╤101101100010010101100100B72565╥101101110010010101100101B82566╦101110000010010101100110B92567╧101110010010010101100111BA2568╨101110100010010101101000BB2569╩101110110010010101101001BC256A╪101111000010010101101010BD256B╫101111010010010101101011BE256C╬101111100010010101101100BF00A9©101111110000000010101001C0044Eю110000000000010001001110C10430а110000010000010000110000C20431б110000100000010000110001C30446ц110000110000010001000110C40434д110001000000010000110100C50435е110001010000010000110101C60444ф110001100000010001000100C70433г110001110000010000110011C80445х110010000000010001000101C90438и110010010000010000111000CA0439й110010100000010000111001CB043Aк110010110000010000111010CC043Bл110011000000010000111011CD043Cм110011010000010000111100CE043Dн110011100000010000111101CF043Eо110011110000010000111110D0043Fп110100000000010000111111D1044Fя110100010000010001001111D20440р110100100000010001000000D30441с110100110000010001000001D40442т110101000000010001000010D50443у110101010000010001000011D60436ж110101100000010000110110D70432в110101110000010000110010D8044Cь110110000000010001001100D9044Bы110110010000010001001011DA0437з110110100000010000110111DB0448ш110110110000010001001000DC044Dэ110111000000010001001101DD0449щ110111010000010001001001DE0447ч110111100000010001000111DF044Aъ110111110000010001001010E0042EЮ111000000000010000101110E10410А111000010000010000010000E20411Б111000100000010000010001E30426Ц111000110000010000100110E40414Д111001000000010000010100E50415Е111001010000010000010101E60424Ф111001100000010000100100E70413Г111001110000010000010011E80425Х111010000000010000100101E90418И111010010000010000011000EA0419Й111010100000010000011001EB041AК111010110000010000011010EC041BЛ111011000000010000011011ED041CМ111011010000010000011100EE041DН111011100000010000011101EF041EО111011110000010000011110F0041FП111100000000010000011111F1042FЯ111100010000010000101111F20420Р111100100000010000100000F30421С111100110000010000100001F40422Т111101000000010000100010F50423У111101010000010000100011F60416Ж111101100000010000010110F70412В111101110000010000010010F8042CЬ111110000000010000101100F9042BЫ111110010000010000101011FA0417З111110100000010000010111FB0428Ш111110110000010000101000FC042DЭ111111000000010000101101FD0429Щ111111010000010000101001FE0427Ч111111100000010000100111FF042AЪ111111110000010000101010 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 01:09 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Как то так получилось. Провертьте меня. Нигде-ли я не ошибся? Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 02:04 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Любопытно взглянуть на функцию y11. Из 128 значений области определения она принимает истину в 115 раз. Ее выгодно перевернуть. Тоесть не рассматривать минитермы ДНФ там где она принимает единичку. А наоборот расчитать где она будет равна false. И результат записать перевернув еще раз по правилу Де-Моргана. Итого 128 - 115 = 13 минитермов должно быть. Внешний вид будет как-то так Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 02:11 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Год заканчивается, предложена достаточно объемная задача оптимизации системы логических функций, поэтому постараюсь закончить с разбором основных моментов создания программы минимизации булевых функций. Сначала ответы. "такие простыни" Представьте, какая была бы простынь, если бы ТС предложил минимизировать функцию f = x0 \/ x1 \/ . . . \/ x31, заданную таблицей истинности. Для меня основная сложность портянки в том, что пока её допишу сайт меня уже не узнает и требует регистрацию. Поэтому простыни сначала пишу в блокноте. "Это - форум программистов". Да, все программисты сталкиваются с условиями ветвления или повторения, а это и есть булевы функции. Но некоторые программисты могут участвовать в проектах, в которых требуются свои критерии оптимизации. "В топике нас не будет интересовать человеческое восприятие". Наверно поэтому тема не нашла широкого отклика. "В своей реализации я хотел уйти от битов. И просто перейти к использованию списков символов". Хочу список символов - это каприз мальчика в магазине игрушек или слова мужа, понимающего триаду Вирта: структура данных-алгоритм-программа? "Игры с кубитами или с иммитацией символа asterisk "*" кажутся мне не очень актуальными применительно к решению задачи которая в пределе двигается к экспоненциальной". asterisk выглядит так "*" с этой стороны экрана, а с другой стороны этого же экрана он выглядит так "00101010". Что изменится, если с той стороны экрана он будет выглядеть, например, так "11"? К сожалению, минимизация булевых функций относится к классу задач, для которых нет лучшего решения, чем прямой перебор. "Памяти у нас сегодня достаточно чтоб не обращать внимание на биты". Не только на биты, но и на байты, и на качество программ, и на многое другое. 22411318 . Это применение драчёвого напильника после драчёвого напильника? Что подтверждается вашими последующими сообщениями. Обычно после драчёвого напильника применяют бархатный напильник (https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%BF%D0%B8%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA). Правильный ответ ( 22410649 ): x¬y \/ ¬z или в вашей нотации: X~Y + ~Z. Как я уже писал, все основные результаты в области представления булевых функций и их минимизации были получены 50-х - 70-х годах прошлого столетия. Для реализации функций y1, y2, ..., y16, если бы это была реальная задача, я бы сначала применил декомпозицию. "Дешифровал" бы три старших разряда. После этого остались бы минимизировать логические функции от 5 переменных. Вопросы совместной реализации системы булевых функций хорошо рассмотрены в книгах Баранова С.И., в частности в книге Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. — М.: Радио и связь, 1986. — 272 с. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 15:31 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
"К чорту Карно". Карно или Квайн? Если ли между ними принципиальное отличие? Еще раз рассмотрим функцию 1 из предыдущего обсуждения x y z f1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Запишем не меняя порядок следования первые четыре значения этой функции горизонтально, а под ними в следующей строке запишем остальные значения этой функции. Строки и столбцы полученной матрицы отметим черточками там, где независимые переменные равны 1. Полученное приведено на рис.1, которое назовем просто картой. Код: plaintext 1. 2. 3. 4. 5. 6. На рис.3 рассмотрим две единички, которые отмечены красным цветом: x¬y¬z \/ x¬yz = x¬y, т.е. отмеченные красным цветом конституенты склеиваются по переменной z. Следовательно, для минимизации нужно найти единички, которые образуют прямоугольник и записать независимые переменные, общие для всех единичек в прямоугольнике. Теперь рассмотрим две единички, отмеченные на рисунке 4 красным цветом. Они не находятся рядом, поэтому их нельзя обвести прямоугольником. Но они склеиваются по переменной y. Вейч, а затем Карно предложили переставить столбцы местами, как показано на рис.5. Теперь, если полученную карту обернуть вокруг цилиндра, то крайние столбцы будут находиться рядом и можно будет выделить прямоугольник. Карту рис.5 называют картой Карно. Карту на рис.1 легко заполнять, но сложно искать импликанты. Карту на рис.5 сложно заполнять, но легко искать импликанты. Выводы: 1) карта Карно это та же таблица истинности; 2) и алгоритм Квайна, и карты Карно основаны на использовании операции склеивания 22406820 . Хочу обратить внимание на то, что логическая (булева) функция - это функция, аргументами которой являются высказывания, а значением функции может быть истина или ложь, как бы они не обозначались. Если для обозначения истинности используются 0 и 1, то нужно помнить, что они не идентичны 0 и 1 из двоичной арифметики. Т.е. алгебра логики (булева алгебра) и алгебра двоичных чисел - это совершенно разные области. Почему я рассматриваю СДНФ, а не СКНФ? СДНФ: x¬yz \/ y¬z, СКНФ: (x \/ ¬y \/ z)(y \/ ¬z). Это не одна и та же функция, просто показал, что запись СКНФ более громоздкая при одном и том же количестве переменных и операций по сравнению с СДНФ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 15:36 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Я предложил два варианта представления СДНФ для программной реализации алгоритма Квайна ( 22410652 ). 1-й вариант (далее псевдокод, не путать с языком программирования): Код: plaintext 1. 2. 3. 4. 5. Поэтому был предложен второй вариант с упаковкой булевых переменных в целое число: type Функция = array 1 .. 2^n of integer; В этом случае потребуется 4*(2^n) = 4*(2^15) байт, что в четыре раза меньше, чем в первом варианте. Для представления одной переменной потребуется два бита: 1 0 - биты числа 0 0 - представляют ¬х1 0 1 - представляют х1 1 * - представляют склейку по переменной х1, в этом контексте знак * обозначает, что значение бита может быть любым и не имеет значения. Я предлагаю следующий способ сравнения двух наборов на предмет склейки. Доопределим * единицей, т.е. 1* -> 11. Сопоставим логические значения с числами: 00(ложь) <-> 0, 01(истина) <-> 1, 1*(склейка) = 11 <-> 3. Введем функцию Lk(Xik, Xjk) = |Xik - Xjk| - 1, где Xik и Xjk значения в "разряде" k i-го и j-го наборов: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Если учесть возможности сокращения числа переборов, о которых я написал ранее, то можно получить сумму всех L. Если она равна -(n-1), то сравниваемые наборы склеиваются. Использование типа integer для хранения одного набора решает задачу отметки этого набора путем присвоения знака - этому числу. Т.е. мы свели логические операции к арифметическим. Это применимо к обоим предложенным вариантам представления СДНФ. В качестве упражнения можно рассмотреть чисто логическое решение для сравнения двух наборов. Золотое правило механики говорит о том, что нельзя одновременно выиграть в расстоянии и силе. В данном случае пожертвовали силой в виде дополнительных команд выделения нужных битов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 15:40 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Если хочется работать с символами, то можно предложить следующие варианты. Код: plaintext 1. 2. 3. 4. 5. В этом случае функция Lk будет такой: Lk(Xik, Xjk) = |ord(Xik) - ord(Xjk)| - 1. Еще один вариант - это использование массива строк: type Функция = array 1 .. 2^n of string[n+1]; Для обозначения истинности можно использовать высоту букв, например, ¬xy¬z можно записать строкой xYz. Тогда таблица, описывающая функцию Lk, будет выглядеть так: Код: plaintext 1. 2. 3. 4. Поиск аналитического выражения этой функции, как и использование списка вместо массива, оставим для самостоятельной работы. На этом программирование алгоритма Квайна считаю законченным, поскольку все основные моменты программной реализации этого алгоритма были рассмотрены. Если действительно нужно автоматизировать минимизацию булевых функций, то можно продолжить кодирование на своем любимом языке программирования с использованием этих и любых других результатов. С наступающим Новым годом! Здоровья, счастья в личной жизни, успехов не только в булевой алгебре! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 15:52 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton Как то так получилось. Провертьте меня. Нигде-ли я не ошибся? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 17:54 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l, вам не стыдно такие простыни писать постами? Такое надо хоть бы в пдф оформить и приложить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.12.2021, 17:59 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Я не пойму к чему человек писал так много. Карно не работает для больших размерностей. Если взять код Грея и выписать в столбик то очевидно Что монотонные области иксов рвутся уже для матриц 8x8 И выше. И Карно не автоматизируется. Ну по крайней мере я не видел ни одной реализации минимизатора которая заявляла бы о методе Карно. Карно это чисто человеческий или когнитивный метод. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2022, 00:51 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
С наступившим всех! Частоты появлений единичек по всем 16 функциям. FunctionFrequencyy160y150y1456y130y120y11115y107y951y815y750y660y565y456y358y253y156 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2022, 14:41 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Когда читаю терминологию - первым делом пытаюсь устновить соответсвие русской и англоязычной технической литературы. Например закон поглощения. Код: sql 1. В англоязычной wiki это может быть Annihilator for "+". Закон склеивания. (или скорее здесь не закон а тождество). Его хорошо видно на диграмме Венна. На кружочках - остаётся только кружочек w. А кружочек x становится универсумом и пересекаясь с w оставляет только w. Код: sql 1. Вот для склеивания я не нашел англоязычного термина. Кто знает что-либо по этому вопросу? Дайте каменты. Я очень не хочу забуждаться. Я помню как я долго путался в комбинаторике. Сочетания-перестановки-размещения и им английский аналог который слишком вольно переводился в разных статьях и книгах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2022, 21:17 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 я думал над твоей идеей (кажется ты писал) искать корреляции между факторами и откликами. Пришел к мысли. 1) Корреляция (Пирсона?) в булевом пространстве вырождается в подсчет совпадающих битов. 2) Гипотеза о том что взаимное влияние факторов друг на друга даёт нам какие-то вычислительные премущества для меня пока ничем не подтверждается. Тоесть мы скорее всего будем делать тот-же или бОльший объем вычислений т.к. булевы выражения так или иначе всегда содержат влияние всех факторов на нужную функцию отклика и мы не можем уменьшить размерность. Можем правда увеличить добавляя "дрейф" или некую константу но что это даёт - непонятно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2022, 21:22 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Тут мне нужно договориться с самим собой о форме публикации результата. Поскольку имеем дело со строками - то лучше чтобы их форма имела бы сортированный порядок в том виде как аргументы лежат в таблице истинности слева-направо и сверху вниз. (Здесь нолик идет сначала а потом единица тоесть сначала инвертированный аргумент а потом без инверсии. Пример. xyzf100000011010101101001101011001111 Просто форматируем как видим. Код: sql 1. Минимизированная форма МДНФ должна точно так-же печататься в строке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.01.2022, 19:33 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
По поводу представления функции-кандидата на минимизацию в виде кубитов. Идея всё таки хорошая. Она мне нравится. Потому-что после реализации Квайна когда я наиграюсь с экспоненциальной сложностью и сожгу свой процессор - то хочу этот-же метод минимизации написать с помощью ГА. Вот тут-то кубиты и пригодятся. Их очень удобно будет "скрещивать". Для генетики кстати кроссовер x1 и !x1 - это будет вовсе не склеивание а - дохлая хромосома потому как нельзя будет просто так разрезать формулу поперек и склеить ее с другой формулой и никогда не получать противоречий. Противоречия будут. Не помню как в теории ГА отслеживается такой кроссовер. Но наверное просто можно в качестве функции фитнеса выдать MIN_DOUBLE и наверное дальше алгоритм ее выбросит из популяции. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.01.2022, 19:43 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
С новым гадом? )) mayton ... пытаюсь устновить соответсвие русской и англоязычной ... технической литературы.Кто знает что-либо по этому вопросу? Поглощение многолико a + ab = a a + a~b = a + b (a + b)(a + ~b) = 0 a(a + b) = a a(~a + b) = ab ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 17:25 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Насчёт факторов и откликов. Я выше отписался, что не придумал, как соображения конвертировать в формальный метод . И вряд ли придумаю. Но ватрушка всё же есть в виде подспорья в анализе . И потом, я писал про обычную корреляцию. Тут можно даже смотреть на векторы координат как на базис Хаара (на часть его). Х1 - самая медленная волна, Хn - самая быстрая. В силу единтвенности разложения в фурье получаем дополнительный аргумент в пользу наличия либо отстствия влияния и его силы. В то же время, классическая корр-ция имеет хорошую геометрическую интерпретацию в виде скалярного произведения. В отличие от к-ции Пирсона эта мне роднее онаа - скорее работа с производной, т.е. с приращениями. Поэтому и используется краткая форма сути: мера линейной зависимости векторов. Чтобы её хоошенько прочувствовать можно много раз медитировать над наглядными примерами и много раз сравнивать со скаляркой например. Тогда моя писанини уже не покажется не имеющей отношения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 18:02 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
В первый раз упомянул о корр-циях с налёту. А здесь - как пример того, на что может навести корреляционное подспорье. Выше писал, что игрался с ф-цией ДНФ и получил случайную новую ф-цию new Код: plsql 1. 2. 3. И сам не заметил, что последняя половина == 1. Пока не подсчитал корр-ции. Corr(x1, Dnf)= 0. Откуда легко сделать вывод, что прибавить "+х1" к формуле ничего не изменит, но вдруг поможет. Corr(new, Dnf)= 0,3026, что меньше чем от других координат и с другим знаком. А ">0" намекает на много совпадений, а различия в знаках с другими намекает на то, что другие к-ты в довольно сильной степени "~Xk". Собссно, всё. Больше ничего из этого не извлёк. Так что это были всего лишь пробы без обощающих выводов. П.С. в ГА и в строках я не помощник. Ну и вообще вся эта тематика не моя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 18:17 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 П.С. в ГА и в строках я не помощник. Ну и вообще вся эта тематика не моя. Она и не моя тоже. Но разве у тебя нет инженерного любопытсва? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 18:35 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 В то же время, классическая корр-ция имеет хорошую геометрическую интерпретацию в виде скалярного произведения. В отличие от к-ции Пирсона эта мне роднее онаа - скорее работа с производной, т.е. с приращениями. Поэтому и используется краткая форма сути: мера линейной зависимости векторов. Не знаю насчет скалярных произвденеий. Но на двумерного набора данных - это "форма облачка". Если слева направо-наискосок - то корреляция положительная. Рост и вес. А ноборот - отрицательная. Если облачко круглое - то нулевая. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 18:51 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton разве у тебя нет инженерного любопытсва? Облако - это линейная регрессия. Ну да, а в ней линейная корр-ция. А если центрированные векторы попарно скалярно умножить, то по определению 8го класса оно = длине проекции одного вектора А на вектор В, =|A|*|B|*Cos(A^B). Вот и сравни косинус с корр. Другими словами "мера сонаправленности центрированных и нормированных векторов". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 19:41 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Кстати, вот восстановленный из фурье вектор для моей ф-ции ДНФ Код: sql 1. Ведь просвечивается же некая связь есть, а хорошей формализации нету. Конечно, много артефактов, среднее 0,625 выше 1/2. Так ведь высокочастотные гармоники отрезаны, вот и муар на перепадах высоты. Нет? Ну вот, а такая красивая мысля была... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2022, 20:08 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Почему Фурье? Обычно его берут там где есть выраженные периоды. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.01.2022, 13:58 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton Почему Фурье? Обычно его берут там где есть выраженные периоды. Но я начну с самого главного - всё равно обломов, нужно додумывать. Потому что Ф., в его обобщении, есть разложение в виде линейной комбинации по полному базису векторов, в частности по бесконечному для непрерывных ф-ций. Тогда F= Function(X1 X2 X3 ...) вв виде линейной комбинации отдельных координат. То есть слагаемые состоят из одой переменной, а это как правило не подходит. К-ты разложения Ф. считаются независимо один от другого. Опустим полезные предобработки вида исключения тренда и проч... Ck= (F, ek) и F= Sum Ck*ek, где ek - базисные векторы, а скобки== скал-ое пр-ние в некой метрике, связанной с базисом. А почему его? потому что векторы X1 X2 X3 ... сами напрашивались на базис Хаара. Только поэтому)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.01.2022, 22:13 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Картинки обрабатывают не полностью. А выделяя фреймы (8х8) и базируясь на предположении что в фотографиях преобладают низкие частоты. И из 64 комплексных вещественных коэффициентов остаётся только штук 5 в левом верхнем углу матрицы где только крупные волны и волнушки. А всякая рябь отсекается как не оказывающая влияние на зрительное восприятие. Тоесть тезис об обратотке фоток Фурье - неверный потому-что неполный. Это все равно что сказать что аптека оперирует химическими формулами чтоб изготовить лекарство. Формулы там конечно есть но еще больше там - биохимия. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.01.2022, 23:21 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Да нет же, не оттого. Это в жипеге эксперты от фотографии используют варинт Ф. в виде косинус-преобразования потому , что предполагают ... всё то самое, что ты писал ... Или используется БПФ потому что ... А периодичность тут не причём. Бесконечный тригонометрический ряд Ф. равномерно сходится на всей числовой прямой (плоскости и т.д.) для любой непрерывной ф-ции (с конечными разрывами числом не более меры нуль по Лебегу). Получаемый спектр Ф. будет ограниченным (т.е. мера множества точек в частотном пространстве), если выполняется т.Котельникова. А нет - может быть и бесконечной длины. И это важное обст-во используют в локации и в обработке звука. Но ограниченность спектра => конечное число гармоник и только в предположении, а периодичность ф-ции просто потом притягивается ради формул. Гармоники обрезают ещё раньше, нежели наступает полноценный период. Нужна только исккусственная имитация периодичности по технологическим причинам для использования формул БПФ. И периодичность снова не причём. Всего лишь одно из применений. То есть всё как раз наоборот. Изучение ф-ции состоит в том (в частности), что изучают её спектр. Какой получится. Белый шум - значит белый шум. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.01.2022, 00:16 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Не знаю. Мне как-то Фурье больше ассоциируется с электроникой и радио-сигналами. А наша предметная область.. Булевы функции с Квайном - это такие себе "шумелки". Шумят они сильно. К ним может быть ближе криптография чем цифровая обработка сигналов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.01.2022, 00:49 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
А мне захотелось проверить так. Но уже неважно. Главное из написанного в том, что всё равно облом, что система ф-ций Хаара не имеет отношения к тригонометрии, а явл. ортонормированным базисом для всех ф-ций из L2, а в дискретке они все на конечном отрезке. И слово Ф. здесь только по аналогии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.01.2022, 15:59 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Почитал плотненько Матем. энциклопедию. Можно в файле, можно здесь dic.academic.ru/dic.nsf/enc_mathematics/5202/СОКРАЩЕННАЯ ........ (собссно ссылка обрезалась, но этого достаточно) и дополнительно для полноты /БУЛЕВЫХ%20ФУНКЦИИ%20МИНИМИЗАЦИЯ /БУЛЕВЫХ%20ФУНКЦИИ%20НОРМАЛЬНЫЕ%20ФОРМЫ /БУЛЕВЫХ%20ФУНКЦИИ%20МЕТРИЧЕСКАЯ%20ТЕОРИЯ Вынес кое что полезное. Может я повторяю известное ... вот некоторые факты оттуда 1) Возможно, полезно перейти на следующую схему работы: СДНФ(или таблица) - СокращДНФ - перебор тупиковых -->минимальная(одна из) По ссылкам объясняется почему это было популярно 40 лет назад. 2) Оказывается, случай, когда ф-ци F имеет ровно один "0", более чем не типичный. Более того, сложность СДНФ для него самая большая и = n*2^ n-1 . И "почти все" ф-ции имеют ассимптотическую сложность своих СДНФ = n*2^ n-1 . То есть, как и ожидалось, половина длины вектора, т.к. C(n\2, n), сочетания максимальны. 3) "Почти все" ф-ции содержат (если я только правильно понял) подряд "почти всегда" столько "1", что их длина ~Log2 Log2 n. Типичная длина подряд идущих 1 достаточно мала, и не стоит ожидать удобные случаи длинных серий. 4) На этапе преобразования "СДНФ (или таблица) - СокращДНФ" полезно использовать такие 2 универсальных пр-ния а) поглощение A+AB == A б) наоборот (добавление конъюнкции) xA+ !xB == xA+ !xB + AB. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.01.2022, 22:42 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Нулей должно быть больше 50%. Я скажу наверное что нам надо договориться не искать безкомпромиссный СДНФ а просто добавить еще одну инверсию и решать задачу меньшего порядка. Если у нас 5 % нулей в функции то переворачиваем и ищем другую функцию где 95% нулей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 00:19 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
1) ДНФ Код: plaintext 2) СДНФ Код: plaintext если записать как в математике записывают многочлены в столбик то можно заметить что в данном частном случае СДНФ получена просто вычёркиванием лишних факторов Код: plaintext 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 11:45 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
В генетическом смысле. У наилучшей хромосомы - некоторые гены обнулились. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 13:58 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Надо-б тоже самое воспроизвести для 10 функции. Код: sql 1. А то есть сомнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 14:31 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton В генетическом смысле. У наилучшей хромосомы - некоторые гены обнулились. Насчёт у10 я пасс, у мне нет готовой проги. Кстати, чем метод Квайна лучше Блейка? Тем, что не столько много вариантов перебирает? А взамен появляется итеративность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 18:13 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 mayton В генетическом смысле. У наилучшей хромосомы - некоторые гены обнулились. Насчёт у10 я пасс, у мне нет готовой проги. У меня не хватает силы воли просто сесть и карандашом и на бумажке сделать. Я - прокрастинатор. По поводу преобразования Адамара. Кажется я начинаю понимать твою мысль. Это действительно похоже на Фурье. И у нас в аргументах есть периодичность. Ну ладно. Молчу. Дальше никаких домыслов. Надо сначала почитать как это работает. А может даже и отдельным топиком. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.01.2022, 21:02 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Столбиком до этих пор довёл mayton А то есть сомнения. Код: sql 1. Да и вроде всё, только скобки раскрыть. Но тоже не уверен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.01.2022, 20:28 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
И фигня ещё такая. Рыскал в поисках упрощённого описания преобразований. Адамара не нашёл на русском. Уолш (Walsh ) есть, но разные статьи/доклады на math.net Но только не описание, как это применить для кодирования. Может и плохо искал. Собссно книги есть, но за деньги Голубов Б.И. Ефимов Скворцов Ряды и преобразования Уолша.Теория и применения, М. Наука 1987 Голубов Б.И. Элементы двоичного анализа. М.: Издательство ЛКИ, 2007. Стукнулся в библиотеку, тоже облом - выдача только в зал, а у мне билет истёк как раз. Или хоть бы этот Schipp Wade Simon Walsh series. An introduction to Dyadic Harmonic Analysiz. Budapest, 1990 Schipp F., Wade W.R., Simon P. Walsh series: An introduction to dyadic harmonic analysis. N.Y.: Adam Hilger, 1990. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.01.2022, 20:41 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Вряд ли я пойду в библиотеку. Уж лучше кидай ссылки на статьи или на сканированные книги. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 11:24 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
exp98 Столбиком до этих пор довёл mayton А то есть сомнения. Код: sql 1. Да и вроде всё, только скобки раскрыть. Но тоже не уверен. Ахахах я тоже пошел с выноса за скобки как в математике. Кстати предлагаю термин - ССНФ - совершенная скобочная нормальная форма. По ней кстати системотехнику тоже можно компактно создавать. Только нужен базис И-ИЛИ-НЕ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 12:32 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Совсем обленились, искать не хотят. Преобразование Уолша Система функций Уолша Коротко, ясно и достаточно для проганья. Всё остальное - теория. обобщённого преобразования Фурье Для обобщённого понимания Ф. Названия книг приведены ранее. В сети math.net да и повсюду поиск по ключевым словам Голубов Golubov Walsh series Walsh transform и их транскрипции ряды Уолша преобразовани Уолша а также инглиш сочетания из названий книг. Вот ещё книги авторЗалманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применения в управлении, связи и других областях. - М.: Наука, 1989. ISBN 5-02-014094-5 И перевод с русского: авторGolubov B., Efimov A., Skvortsov V. Walsh series and transforms. Theory and applications. – Dordrecht- Boston-London: Kluwer Academic Publishers, 1991. – 368 p. П.С, я ткнулся в библио, не слезая со стула. Что-то можно читать он-лайн, что-то в свободном доступе электронно. От них есть доступ к нек. числу ресурсов. Но это rsl.ru и удалённая перерегистрация с их сайта через госуслуги. А для начальной записи нужно прийти с паспортом. Сылки выше - это бауманка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 19:55 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
[quot mayton#22419764] exp98 Кстати предлагаю термин - ССНФ - совершенная скобочная нормальная форма. Но ведь конъюнкции как и умножение - это разве не свёрточные операции? тогда они дольше, не так? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 20:10 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Эээ ничо не понял. Разве я не тоже самое сказал? P.S. Немцы.. конгрессы какието.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 20:22 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Строго говоря, +/* только часть из них. А я а я имел ввиду любые элементарные. Просто так, к слову. О том и речь. На mathnet.ru есть и русские Но я про это и жаловался. Базовые книги - за деньги. Остальное - отрывочно либо специфично. Методики для приложений - тоже спрятаны. Самое адекватное пока из бауманки. Но надо состряпать матрицу и не 8х8, не о картинках вопрос. Кое-как накопал дежавю Залманзона, но только Главы 1-3 (это про Ф. - и кому это надо?..), а их там 8 глав - как раз интересное и отсутствует. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2022, 21:48 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
ТС " Необходимо реализовать следующее. Дана ДНФ найти минимальную ДНФ. Можно брать метод Квайна ". " Это - форум программистов " ( 22410711 ), но обсуждение напомнило мне очень старый анекдот: На экзамене студент не может вспомнить алгоритм Квайна, на который преподаватель потратил целых две лекции и три практических занятия. Преподаватель: "Карла М. знаете?". Студент: "Нет!". - Фридриха Э. знаете? - Нет! - Последний вопрос. А Уолша вы знаете? - Постойте, а вы Ваньку Рябого знаете? - Нет! - А Генку Косого? - Нет! - Так что вы меня своей бандой пугаете! Честно говоря я не понял, что же нужно ТС. Алгоритм Квайна и его NP-полнота известны давно. Началась вторая пятилетка. Передовой рабочий клас ставит рекорды по добыче угля и выплавки стали. А программной реализации Квайна у ТС как не было, так и нет. Уже хорошо, что наконец-то нашли статью из энциклопедии о ДНФ. ( 22418351 ). Ну узнали, сколько единичек бывает в среднестатистической логической функции. А нам всего лишь нужно включить вон ту кнопочку открытия парашюта в зависимости от этого, вот от того и еще вон от этих сигналов. Если эта кнопочка из 1000 раз один раз не включится, то кому-то просто не повезет, или наоборот кто-то получит наследство. " Как то так получилось. Провертьте меня. Нигде-ли я не ошибся "? ( 22416412 ) Например, неужели найдется тот, кто в здравом уме и твердой памяти согласится проверить глазами вот это?: y14 = x8!x7!x6!x5!x4!x3!x2!x1 + x8!x7!x6!x5!x4!x3!x2x1 + x8!x7!x6!x5!x4!x3x2!x1 + x8!x7!x6!x5!x4!x3x2x1 + x8!x7!x6!x5!x4x3!x2!x1 + x8!x7!x6!x5!x4x3!x2x1 + x8!x7!x6!x5!x4x3x2!x1 + x8!x7!x6!x5!x4x3x2x1 + x8!x7!x6!x5x4!x3!x2!x1 + x8!x7!x6!x5x4!x3!x2x1 + x8!x7!x6!x5x4!x3x2!x1 + x8!x7!x6!x5x4!x3x2x1 + x8!x7!x6!x5x4x3!x2!x1 + x8!x7!x6!x5x4x3!x2x1 + x8!x7!x6!x5x4x3x2!x1 + x8!x7!x6!x5x4x3x2x1 + x8!x7!x6x5!x4!x3!x2!x1 + x8!x7!x6x5!x4!x3!x2x1 + x8!x7!x6x5!x4!x3x2!x1 + x8!x7!x6x5!x4!x3x2x1 + x8!x7!x6x5!x4x3!x2!x1 + x8!x7!x6x5!x4x3!x2x1 + x8!x7!x6x5!x4x3x2!x1 + x8!x7!x6x5!x4x3x2x1 + x8!x7!x6x5x4!x3!x2!x1 + x8!x7!x6x5x4!x3!x2x1 + x8!x7!x6x5x4!x3x2x1 + x8!x7x6!x5!x4!x3!x2!x1 + x8!x7x6!x5!x4!x3!x2x1 + x8!x7x6!x5!x4!x3x2!x1 + x8!x7x6!x5!x4x3!x2!x1 + x8!x7x6!x5!x4x3!x2x1 + x8!x7x6!x5!x4x3x2!x1 + x8!x7x6!x5!x4x3x2x1 + x8!x7x6!x5x4!x3!x2!x1 + x8!x7x6!x5x4!x3!x2x1 + x8!x7x6!x5x4!x3x2!x1 + x8!x7x6!x5x4!x3x2x1 + x8!x7x6!x5x4x3!x2!x1 + x8!x7x6!x5x4x3!x2x1 + x8!x7x6!x5x4x3x2!x1 + x8!x7x6!x5x4x3x2x1 + x8!x7x6x5!x4!x3!x2!x1 + x8!x7x6x5!x4!x3!x2x1 + x8!x7x6x5!x4!x3x2!x1 + x8!x7x6x5!x4x3!x2!x1 + x8!x7x6x5!x4x3!x2x1 + x8!x7x6x5!x4x3x2!x1 + x8!x7x6x5!x4x3x2x1 + x8!x7x6x5x4!x3!x2!x1 + x8!x7x6x5x4!x3!x2x1 + x8!x7x6x5x4!x3x2!x1 + x8!x7x6x5x4!x3x2x1 + x8!x7x6x5x4x3!x2!x1 + x8!x7x6x5x4x3!x2x1 + x8!x7x6x5x4x3x2!x1 Не проще было бы время, в течение которого это писалось, потратить на процедуру, которая бы из таблицы получила бы текстовую СДНФ? По крайней мере текст такой процедуры можно проверить намного легче. Главное, будет то, что можно реально обсудить. Составим запрос SQL (язык T-SQL) так, чтобы на каждом этапе можно было увидеть результат этого этапа. В качестве булевой функции возьмем первую функция из предыдущего обсуждения (эта функция стала мне настолько родной и близкой, что только ради неё я возвращаюсь сюда): Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. После запроса B получим: Код: plaintext 1. 2. 3. 4. 5. Осталось убрать лишний символ дизъюнкции. Это сделаем в основном запросе и получим: ¬x¬yz \/ x¬y¬z \/ x¬yz \/ xy¬z. Т.е. мы от таблицы истинности перешли к текстовому представлению СДНФ. Я угадал мелодию за две ноты. Постойте, так ТС любит строки. Тогда те же две ноты: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. Аналогично можно сделать обратное преобразование, т.е. от текстового представления СДНФ перейти к таблице истинности. А можно ли от минимальной ДНФ, заданной набором простых импликант, перейти к СДНФ? Да, можно, возьмем минимальную ДНФ этой функции и преобразуем ее к единичным наборам СДНФ: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Результат: Код: plaintext 1. 2. 3. 4. 5. Таким образом, у нас появились две полезных процедуры. Теперь составить бы запрос для склейки двух наборов, т.е. из двух наборов 100 (x¬y¬z) и 101 (x¬yz) получить набор 10- (x¬y). Как всегда, на самом интересном месте – рекламная пауза. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2022, 15:45 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Wlr-l, вы мой кумир. Я распечатаю ваши исходники. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2022, 15:48 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Ну а я позволю себе продолжить с Уолшем, пока меня не согнали отсюда. На пробу построил 64 ф-ции У. Это в нумерации, наверное самого У. Уж точно не Пэли. Функции вычислялись в привязке к отрезку [0; 1] с шагом дискретизации =1/64. А чтобы норма была=1, поэтому значения {-1/8; +1/8} согласно формуле. Обратите внимание! Здесь спрятана матрица 64*64. В ширину это не так уж и мало. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2022, 21:42 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Экспериментировал разлагать по этому базису кусочно-постоянные функции. Эта зараза восстанавливает исходный сигнал без потери. Логические переменные входят в этот базис под номерами w3 w7 w15 w31 w63 (нумерация от 0). Соответственно тематике задавал логические переменные, выдавала нужную гармонику. Задал ~w3 or w7, выдала правильные гармоники + в добавок неизвестную квазилогическую ф-цию w4. Оказалось, что это ф-ция полностью покрывается импликацией и не вносит новых "1". Напомню, что речь может идти только о линейных комбинациях. Посмотрел функции вида w3 & w7 & w15. Помимо суммы 3-х переменных выдала ещё несколько квазилогических ф-ций. Я понял, что неправильно думаю. Задаю функцию, используя логические операции, а У-преобразование выполняется арифметическими. Надо перейти хотя бы на двоичные по модулю 2 и сравнить. модулю 2 - это ведь Xor. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.01.2022, 01:37 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Друзья. Я поражен вашей продуктивностью. Я некоторое время придавлен проектом. Поэтому по этой задаче беру паузу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.01.2022, 11:26 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton ... по этой задаче беру паузу. 0) Я сделл в экселке небольшой интерактивный тренажёр на получение коэфф-тов ПУ и собссно результата преобразования. 1) Небольшое уточнения к ф-циям У. Отрезок [0; 1] содержит ровно N=2^6=64 точек, то есть шаг дискретизации = 1/63. x0=0 x64= 1 На самом деле x64=0,1111(1)..... 2) Переходить к операциям в двоичом поле (byadic) не спешу, нашёл косяк в действиях. Примерно прежние, но лучше интерпретируемые результаты получаются, если брать ф-цию, к к-рой применять ПУ, не логического типа {0; 1}, а того же, что и базисные Wk(x), т.е. {-1; 1}. 3) До сих пор у меня вопрос, который в теории по ПУ я до сих пор не встретил. Это - имеет ли место "частота Найквиста" (как для ПФ)? Скорее всего для ПУ удвоенный интервал не нужен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.01.2022, 16:33 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
...Продолжаю (здесь уточнённая редакция предыдущего поста)... 1) Небольшое уточнения к ф-циям У. Отрезок [0; 1] содержит ровно N=2^6=64 точек, то есть шаг дискретизации = 1/63. x0=0 x64= 1 На самом деле x64=0,1111(1)..... в двоичном. Функции - логические переменные W0()=const W1() W3() W7() W15() W31() W63() ...... 3) До сих пор у меня вопрос, который в теории по ПУ я до сих пор не встретил. Это - имеет ли место "частота Найквиста" (как для ПФ)? Скорее всего для ПУ удвоенный интервал не нужен. 4) Исходные ф-ции можно задавать любые с оговоркой на тип значений выше. Но изучать вопросы применимости к ДНФ лучше на основе логических переменных. Если что, то как это выполнять в файле, подскажу. Главное не стесняться спросить, пока я не закончил с темой. Так вот на простых формулах выясняется, что всё же главные полученные гармоники соответствуют переменным. Остальные подгармоники устраняют муар, эффек Гиббса. Причём для простых формул, но обязательнодля кусочно постоянных (это свойство ПУ) а) можно предсказать либо угадать номера подгармоник; б) достаточно использовать не все базисы, а лишь включительно по наиболее быструю используемую переменную, например до W31. в) для конъ/дизъ 2й-3й степени знак коэфф-та С0 коррелирует с заданной ф-цией: больше она похожа на Произведение или на Сумму В любом случае, линейная комбинация только "переменных" остаётся простейшей 1-степенной ДНФ. Случайные же ф-ции используют уже весь базис. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.01.2022, 16:52 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Фактически я закончил. Пока не забыл ... Хорошее свойство ф-ций У. Всегда Wk(x)*Wn(x)= Wp(x), где (pi)= (ki)+(ni) mod 2 для каждого i, (ki) - последовательность в двоичном разложении числа k и т.п. Учитывая, что как переменные для логики использутся W1() W3() W7() W15() W31() W63()..., все остальные ф-ции могут быть получены произведением этих. Парами, тройками и т.д. Казалось бы здорово подходит для ряда Тейлора. В итоге составляется уже НЕлинейная комбинация из основных ф-ций. Её даже можно руками упрощать до минимальной формы)). Но!.. только арифметически упрощать. Вопрос пока остаётся в переводе арифметической формы в логическую. Примеры а) w3 !w7 w31 + w3 w7 w31 коэфф-ты преобразоваия Ck= (3 7 31, 4 24 27 28) Это приводит к 2^N числу арифметических слагаемых, которые сначала ещё надо упростить. Понятно, да? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.01.2022, 20:43 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Этот вопрос конечно остался. exp98 Вопрос пока остаётся в переводе арифметической формы в логическую. Примеры а) w3 !w7 w31 + w3 w7 w31 коэфф-ты преобразоваия Ck= (3 7 31, 4 24 27 28) Это приводит к 2^N числу арифметических слагаемых, которые сначала ещё надо упростить. Для примера взял 22 схожих функций длиной 64 бита. На этот раз я не знал, из каких переменных они созданы. Что за функции, видно из вложения - левый рисунок, ф-ции расположены вертикально, все рядышком. Совершенно случайно оказалось, что-то читабельное. Как ясно из предыдудщего, ПУ без потерь восстанавливает каждую из них. Но 2^n слагаемых в ДНФ - это не то, что хотелось бы. Поэтому я отрезал вторую половину коэф-тов ПУ и получился средний рисунок, потому что восстановленные значения теперь не бинарные, а действительные числа. Раскраска клеток выполнена в 11 градаций (лучше не получилось). Палитра - строчка над рисунком. Клетки в экселе сложно красиво раскрасиьт фоновым цветом. Затем восстановленные значения я дискретзировал в 4 значения -2 -1 0 1 (правый рисунок). И в этом тоже проблема. Пока непонятно, как правильно превращать помежуточные действительные значения в бинарные. Или, как полутоновй рисунок превратить в ч/б. Ну и вечный вопрос, как правильно отсекать базисные ф-ции ПУ, чтобы первое приближение не сильно отличалось от исходной.логической ф-ции. В общем понятно, что для минимизации это не лучший метод. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.01.2022, 23:36 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Унылая пора. На пробу сДэНээФил 6-й столбик правого рисунка (то есть это рисунок уже с потерей информации). СДНФ= + w1w3w7~w15w31w63 + w1w3w7~w15w31~w63 + w1w3w7~w15~w31w63 + w1w3w7~w15~w31~w63 + w1~w3w7~w15w31w63 + w1~w3w7~w15w31~w63 + w1~w3w7~w15~w31w63 + w1~w3w7~w15~w31~w63 + ~w1w3~w7w15w31w63 + ~w1w3~w7w15w31~w63 + ~w1~w3w7~w15~w31w63 + ~w1~w3w7~w15~w31~w63 + ~w1~w3~w7~w15w31w63 + ~w1~w3~w7~w15w31~w63 w1w7~w15 ~w1w3~w7w15w31 ~w1~w3w7~w15~w31 ~w1~w3~w7~w15w31 Дальше что ни вынесу за скобки, всё получается XOR либо его отрицание. Если подсчитать требуемое число бит, выходит 2*5 бит на каждое слагаемое * 4 слаг-х =40 бит из 64х в столбике. Хреновое ДКНФ'ное сжатие получается. Раньше НР рекламировала свои принтеры, что на текстовый лист порошка уходит на 5% площади листа. Здесь сосчитал площадь - 20-24% в квадрате 26*64. Ну, пусть на весь в белом и на весь в чёрном столбики почти ничего не тратится. Допустим, они 70% площади. Остальое сожмётся пусть как здесь 2/3. Получится сжатый лист 2/3*0,3= 20% от всего битов полного листа. То есть 1/5-я, примерно как сжатие текста, притом здесь - уже с потерей инфы,аисходные биты ещё можно сжимать. Вот и фигня такая. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.01.2022, 15:29 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Рекламная пауза затянулась, продолжим программировать алгоритм Квайна. Скажу, что я не обращаюсь к кому-либо конкретно, и не собираюсь привести здесь готовую программу, полностью решающую поставленную задачу. Сам алгоритм Каина я уже разобрал ( 22406820 ), предложил механизм для реализации наиболее сложного, на мой взгляд, шага этого алгоритма - склеивания наборов ( 22410652 , 22416490 ). Основной идей было на основании внешнего сходства 0 и 1 в алгебре логики и арифметике свести логические операции к арифметическим, или, точнее сказать, "арифметизировать" операцию склейки. Осталось разобрать возможную программную реализацию этих шагов. В качестве языка программирования выбран T_SQL. Это позволяет сосредоточиться на главном и дать возможность достаточно просто проверить каждый шаг. Если кто-то не знает SQL? Не страшно, постараюсь не использовать сложные конструкции и не создавать какие-либо объекты в вашей БД, только запросы. Приведенные мной механизмы и тексты запросов можно использовать для реализации алгоритма Квайна, если это действительно нужно, на вашем любимом языке программирования. Только не распечатывайте их, чтобы повесить на стенку. Не сотвори себе кумира, предостерегали древние и сотворили себе нового кумира. Продолжим разбирать алгоритм Квайна на примере предложенной ТС и уже рассмотренной мной ( 22410649 ) функции f11 = ¬x¬yz \/ x¬y¬z \/ x¬yz \/ xy¬z (можно было бы взять мою любимую функцию f1, но она минимизируется за один "проход" алгоритма Квайна): Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Если логическая функция задана формулой, то, я надеюсь, вы, пока шла рекламная пауза, самостоятельно справились с преобразованием формулы в наборы. Дальнейшие действия разобьем на простые шаги. Некоторые шаги предназначены для более глубокого понимания процесса. Каждый шаг я постараюсь сделать отдельным сообщением, чтобы 1) сообщения не были слишком длинными и 2) было проще ориентироваться в шагах. В заключение приведу результирующий запрос. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:29 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 1. Упрощение исходного представление логической функции. Поскольку мы работаем с ДНФ, то строки, на которых значение функции равно 0, нас не интересуют. Удалим их. Теперь столбец f содержит одни 1. Удалим и его. Полученные наборы пронумеруем. Конкретный номер набора не важен, поэтому в качестве номера набора возьмем соответствующее ему десятичное число. Ясно, что все номера строк будут попарно различны и обеспечивают нужный порядок наборов. Функция f11 примет вид: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. Разработанную вами процедуру для преобразования формулы в наборы несложно модифицировать к такому представлению логической функции. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:30 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 2. Для каждого набора из СДНФ найдем все наборы, с которыми будем сравнивать этот выбранный набор на предмет склейки. Есть две возможности уменьшения числа сравнений. 1. Сравнение наборов 0 и 2 даст тот же самый результат, что и сравнение наборов 2 и 0, так как дизъюнкция коммутативна. Так же мы знаем, что a \/ a = a. Поэтому можно сравнивать каждый набор с теми наборами, номер которых больше номера выбранного набора. 2. Наборы можно склеить, если они отличаются друг от друга только в одном разряде, например, набор 0 может склеиваться с наборами 2 и 4, не с наборами 5 и 6. Поэтому, если наборы разбить на группы с одинаковым числом единиц в наборе, то можно сравнивать наборы только из соседних групп, не забывая о первой возможности. Далее воспользуемся первой возможностью, оставляя вторую возможность для самостоятельной работы. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. n1 - номер выбранного набора; n2 - номер набора, с которым будем сравнивать выбранный набор; r1, r2 - пустые столбики, введенные для наглядности представления результата запроса; x1,y1,z1 и x2,y2,z2 - сами наборы, соответствующие n1 и n2. Рассмотрим строки запроса: , B (n1, n2, r1, x1, y1, z1, r2, x2, y2, z2) as ( select a.n, b.n, ' ', a.x, a.y, a.z, ' ', b.x, b.y, b.z Есть разные способы дать новые имена (алиасы) полям запроса. В данном случае выбран такой способ. Потому что это не загромождает список полей в самом запросе, а выравнивание по горизонтали новых и старых имен полей дает хорошую наглядность их соответствия. Немного анализа. При полном сравнении для этой функции мы получили бы 20 строк (почему?). Воспользовавшись первой возможностью, мы получили 10 строк. В общем-то неплохо! Возможность 2. Наши наборы можно разбить на три группы: (0, 0,0,0) - 1-я группа (2, 0,1,0) - 2-я группа (4, 1,0,0) (5, 1,0,1) - 3-я группа (6, 1,1,0) Сравниваем наборы из 1-й и 2-й группы: 0 с 2, 0 с 4; Сравниваем наборы из 2-й и 3-й группы: 2 с 5, 2 с 6, 4 с 5, 4 с 6. Т.е. в этом случае достаточно 6-и сравнений. Наша функция равна 1 на пяти из восьми наборов. Т.е. является "среднестатистической логической функцией". 20 --> 10 --> 6. Это дает примерное представление о возможностях уменьшения числа сравнений наборов СДНФ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:33 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 3. Построчно и поразрядно сравним найденные наборы так, как я описал в сообщении 22416490 . Это наиболее важный шаг. Напомню: Сопоставим логические значения с числами: 0(ложь) <-> 0, 1(истина) <-> 1, *(склейка) <-> 3. Введем функцию Lk(Xik, Xjk) = |Xik - Xjk| - 1, где Xik и Xjk значения в "разряде" k i-го и j-го наборов: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:36 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 4. На этом шаге переставим столбцы местами и найдем сумму Lk по каждой строке, которую обозначим буквой L. Эти операции делаются в запросе D. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. В данном случае это наборы, где L равно -2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:38 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 5. Оставим только те строки, которые склеились. Для дальнейшей работы в каждой строке оставим один из двух наборов. Для определенности оставим первый набор. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:39 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Шаг 6. Заменим значение разряда, по которому произошло склеивание, на значение 3. Это происходит в запросе E. На месте 9-ки может быть любое число, большее 3-х. При правильной работе 9-к быть не должно. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. В склеивании участвовали наборы 0, 2, 4, 5 и 6, т.е. все наборы, поэтому они не являются простыми импликантами и их запоминать не нужно. В качестве самостоятельной работы можно подумать, как определить, есть ли наборы, которые не участвовали в склейке? Далее, описанный процесс нужно повторить над полученными наборами. Вопрос об окончании процесса повторения оставляю для самостоятельной работы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:41 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Теперь, когда мы разобрали механизмы, лежащие в основе алгоритма Квайна, отдельные шаги можно объединить в один запрос: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Результат: Код: plaintext 1. 2. 3. 4. 5. 6. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Результат: Код: plaintext 1. 2. 3. Мы получили две простые импликанты: (1,0,3) и (3,3,0). Нетрудно убедиться, что они покрывают все наборы (конституенты единицы) СДНФ исходной функции. (Помните, что работа с импликантной матрицей была оставлена для самостоятельной работы?). Поэтому они будут представлять тупиковую ДНФ функции f11. Поскольку тупиковая ДНФ только одна, то она будет и минимальной ДНФ функции f11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:42 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
В сообщении 22420479 я привел процедуру преобразования таблицы истинности в формулу. Немного доработаем эту процедуру для вывода результата склеивания в виде формулы: Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. Результат: x¬y \/ ¬z Что совпадает с результатом ручной минимизации ( 22410649 ). Еще раз подчеркну, что здесь я рассмотрел работу алгоритма Квайна в моей интерпретации на примере функций от трех переменных. Доведение алгоритма до работы с произвольным числом переменных оставляю для самостоятельной работы. Удачи! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:44 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Спасибо дружище. Ты конечно оставил меня в большом изумлении. Особенно от инструмента. Я планирвал сделать command-line tool для генерации математических форм ДНФ с последующим их превращением в обычные императивные языки такие как С++/C#/Java. Как быть с твоим исходником - я не знаю. Скажи какой диалект SQL ты использовал? Чтоб хотя-бы воспроизвести. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:54 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton, T-SQL (MS SQL Server), но язык здесь не принципиален. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2022, 17:58 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton Я планирвал сделать command-line tool Я тут метод Блейка прогнул на своё понимание. Мог и ошибиться, прожка ещё не достаточно проверена. Сравните, плз, это первая встречная ТДНФ( y8 ) - твоя функция, я только х8 выбросил за не заданностью _0001311 + _0010003 + _0010030 + _0010300 + _0011310 + _0013010 + _0013100 + _0041143 + _0311111 Извините, я в своей нотации, 0 и 1 в знакоместе - это наличие переменной, остальные - её отсутствие. Как хитро расположились троечки. Для сравнения проверял свою ф-цию 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ..... и далее все нули. Длина=64, 6 переменных Прога дала ТДНФ() _000013 + _010113 + _401003 + _141043 Я решал ручками, вышло на 2 буквы длиннее. Тексты с картинки тоже запускал, но там пока сравнить сложно, потому что это всё в VBA. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2022, 20:23 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Сегодня открыл для себя Python/matplotlib.pyplot Симпатичная штука. Мне удобнее наверное в ней графики рисовать. По работе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2022, 20:46 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Вот ещё функция у9, 51 единица, 15 слагаемых. ТДНФ( y9 )= Сумма( _0004443 _0040043 _0043011 _0140143 _0141043 _0144403 _0144430 _0401443 _0404143 _0404403 _0404430 _0431011 _0440003 _0440030 _0440300 ) Снова становится грустно. Это ведь первые встречные ТДНФ. Для поиска минимальной надо их все наплодить и сравнить. Здесь, благодаря отсутствию х1, 1-й этшагап алгоритма (поглощение) уложился в 512 строк (в 200 не уложился). Я использую единственный порядок перебора. Но на 2-м шаге (склеивания) надо склеивать пары конъ-ций во всех возможных порядках, а потом сравнить рез-ты. Все С(512, 2) ^2 прогонов сравнивать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2022, 20:48 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Оу! даже не так, Число перестановок одной последовательности конъ-ций. Вот его в квадрат и пополам. Как-то не вдохновляют 200 ! прогонов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2022, 21:02 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Макет эскиза. Если охота пробовать блейка, файл во вложении. Учесть, что исходные данные все берутся с текущего листа в эксэлке и ответ туда же кладётся. Настройка на бОльшие размеры ручками, но недолго, хотя и нужна аккуратность. Запускать макрос (в конце текста), но скорее всего его придётся запускать из формочки по кнопке, а не из ячейки, у меня из формочки с выделением мышем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2022, 17:47 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
А как под Linux это запускать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 00:34 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
О терминологии. Я выписал на бумажку следующие короткие определения. СДНФ (PDNF - perfect disjunctive normal form) СКНФ (PCNF - perfect conjunctive normal form) Absorption? Код: plaintext 1. Material conditional (implication) xyx->y001010101111 Annihilator ? Код: plaintext Кто не согласен - напишите плиз какой синоним или аббревиатуру вы еще слышали? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 18:54 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton Material conditional (implication) xyx->y001010101111 Ну если только это назвать "НЕматериальной импликацией" в противоположность обычной (~a+b). Потому что обычная обобщает бытовое наблюдение, чтообычно из ПРАВДЫ не следует ЛОЖь. А из ЛЖИ может следовать что угодно. Здесьже ровно наоборот. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 19:54 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton Annihilator ? Код: plaintext Хотя как раз такие крайние случаи подходят и под склейку тоже. Но как раз склейку я бы интуитивно называл поглощением, поскольку простая склейка хА+А как раз поглощает меньшее множество бОльшим, и поэтому путаюсь в них без шпаргалки. И хто там из них к кому клеится, не в силах понять, вроде обладатель х-хромосомы обычно клеится - так что ль? А нынешнее поглощение называл бы, наоборот "склеиванием по переменной" или даже м.б. как раз "анигиляцией переменной". Но что есть, то есть. Вообще, я замечал и даже отмечал, что программирование с некоторого момента увлеклось околонаучной терминологией. В частности идемпотентностью, нильпотентностью, теперь вот анигилятор. Одно дело когда розово-голубые пушистые нуклоны - здесь нейтральная ассоциация. Другое дело, когда ложится на другую семантику - всегда сбивает с толку. И вопрос, ради чего плодить термины? >>под Linux это запускать? А как бы я под него писал? Запускать просто: х32 виртуалку с ХР и в ней автоэкзэк.бат с эксэлой-2003, хотя м.б. достаточно и 2000. Или транспилировать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 19:59 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Сегодня курьёзная мысля посетила. Известна пародия на "женскую логику": FF= [(A-->B) & (A-->C)] --> (B==C) Левая посылка по правилам классики = ~A + BC = A --> BC. Правая часть: (B==C) = BC + ~B~C В женской же логике FF = [~A --> (B==C)] = ~A --> BC + ~B~C. "Английский юмор" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 20:24 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Я спрашиваю про термины не потому что хочу их плодить. А как раз потому, что хочу их свести к одному русскому синонимы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2022, 22:32 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
mayton, нуу, во-первых я риторически вопрошал тех, кто их придумал. А во-вторых, я помню, что очень давно приходилось читаьть по-русски навроде "материальной импликации", но не помню в каком контексте, и не помню, чтобы кто-то спецом использовал вместо обычной Имп. её отрицание под спец. именем, а у тебя как раз отрицание Имп, и ранее это уже кем-то отмечено. Возможно для того писалось, что в контексте неклассических логик, например чтобы сделать акцент именно на 2-значном варианте ~A+B. Поскольку даже 3-значное ~A+B очевидно противоречит материалистическим привычкам. Соглашаясь с этим, сопровождать термин Имп. чем-либо ещё представляется запутывающим. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2022, 17:41 |
|
||
|
Вторничный Квайн
|
|||
|---|---|---|---|
|
#18+
Так и есть. Эпитет "материальная" использовался в контрасте. Причём его использование более 100 лет назад, а затем и позднее скорее всего и уместно лишь в обсуждении основополагающих принципов логики вообще. В рамках 2-значной матклассики он явно лишний. Например цитирую авторВ 1912 году КИ.Льюис строит новую теорию "логического следования" взамен теории материальной (классической) импликации, изложенной в Principia Mathematica. Исходным мотивом Льюиса было избавиться от так называемых парадоксов материальной импликации: p-->(q-->p), p-->(~p-->q). Правда затем оказалось, что и его "строгая импликация" приводит к ещё более абсурдным бытовым парадоксам вида "всё что угодно следует из всего что угодно": p-->(q-->q), (p & ~p)-->q. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2022, 18:32 |
|
||
|
|
Start [/forum/topic.php?fid=16&tid=1339587&all=1]: |
0ms |
get settings: |
0ms |
get forum list: |
7ms |
check forum access: |
1ms |
check topic access: |
1ms |
track hit: |
43ms |
get topic data: |
2ms |
get forum data: |
1ms |
get page messages: |
44ms |
update_topic_read_status (1339587): 01.02.2022 18:32:37: |
0ms |
get tp. blocked users: |
0ms |
get online users: |
30ms |
check new: |
1ms |
| others: | 98ms |
| total: | 228ms |
| 0 / 0 |
