|
Вторничный Квайн
|
|||
---|---|---|---|
#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&gotonew=1&tid=1339587]: |
0ms |
get settings: |
8ms |
get forum list: |
5ms |
check forum access: |
1ms |
check topic access: |
1ms |
track hit: |
36ms |
get topic data: |
2ms |
get first new msg: |
3ms |
get forum data: |
1ms |
get page messages: |
461ms |
get tp. blocked users: |
1ms |
others: | 6ms |
total: | 525ms |
0 / 0 |