Вторничный Квайн / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный Квайн

25 сообщений из 100, страница 4 из 4

все

Вторничный Квайн

#40128690

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Унылая пора. На пробу сДэНээФил 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-я, примерно как сжатие текста, притом здесь - уже с потерей инфы,аисходные биты ещё можно сжимать. Вот и фигня такая.

...

Рейтинг:

0 / 0

22.01.2022, 15:29

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129117

Wlr-l

Гость

Рекламная пауза затянулась, продолжим программировать алгоритм Квайна.

Скажу, что я не обращаюсь к кому-либо конкретно, и не собираюсь привести здесь готовую программу, полностью решающую поставленную задачу. Сам алгоритм Каина я уже разобрал ( 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.

with A as ( --- Таблица истинности f11
  select *
    from (values (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)
        ) as    T(x, y, z,  f)
)  --- select * from A;

Если логическая функция задана формулой, то, я надеюсь, вы, пока шла рекламная пауза, самостоятельно справились с преобразованием формулы в наборы.

Дальнейшие действия разобьем на простые шаги. Некоторые шаги предназначены для более глубокого понимания процесса. Каждый шаг я постараюсь сделать отдельным сообщением, чтобы 1) сообщения не были слишком длинными и 2) было проще ориентироваться в шагах. В заключение приведу результирующий запрос.

...

Рейтинг:

0 / 0

24.01.2022, 17:29

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129118

Wlr-l

Гость

Шаг 1. Упрощение исходного представление логической функции.

Поскольку мы работаем с ДНФ, то строки, на которых значение функции равно 0, нас не интересуют. Удалим их. Теперь столбец f содержит одни 1. Удалим и его. Полученные наборы пронумеруем. Конкретный номер набора не важен, поэтому в качестве номера набора возьмем соответствующее ему десятичное число. Ясно, что все номера строк будут попарно различны и обеспечивают нужный порядок наборов. Функция f11 примет вид:

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

with A as ( --- СДНФ  функции f11 
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;

Разработанную вами процедуру для преобразования формулы в наборы несложно модифицировать к такому представлению логической функции.

...

Рейтинг:

0 / 0

24.01.2022, 17:30

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129121

Wlr-l

Гость

Шаг 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.

with A as ( --- СДНФ  функции f11 
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;
, 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
    from A  a
    join A  b  on a.n<=b.n-1
)   select * from B;

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

n1	n2	r1	x1	y1	z1	r2	x2	y2	z2
0	2	 	0	0	0	 	0	1	0
0	4	 	0	0	0	 	1	0	0
0	5	 	0	0	0	  	1	0	1
0	6	 	0	0	0	 	1	1	0
2	4	 	0	1	0	 	1	0	0
2	5	 	0	1	0	 	1	0	1
2	6	 	0	1	0	 	1	1	0
4	5	 	1	0	0	 	1	0	1
4	6	 	1	0	0	 	1	1	0
5	6	 	1	0	1	 	1	1	0

Немного пояснений.
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. Это дает примерное представление о возможностях уменьшения числа сравнений наборов СДНФ.

...

Рейтинг:

0 / 0

24.01.2022, 17:33

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129122

Wlr-l

Гость

Шаг 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.

Xik   0   0   0   1   1   1   3   3   3
Xjk   0   1   3   0   1   3   0   1   3
---------------------------------------
Lk   -1   0   2   0  -1   1   2   1  -1
      =               =               =
          *       *
             <>          <>  <>  <>

   / <0 - истинность наборов i и j в "разряде" k одинаковая, склейка возможна, продолжить сравнение этих наборов
Lk|   0 - логические наборы i и j могут быть склеены по переменной "разряда" k, продолжить сравнение этих наборов
   \ >0 - наборы i и j не могут быть склеены, можно прекратить дальнейшее сравнение этих наборов

Этот механизм реализован в запросе C.

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

with A as ( --- СДНФ  функции f11
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;
, 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
    from A  a
    join A  b  on a.n<=b.n-1
) ---  select * from B;
, C     (n1, n2,  r1, x1, x2,           L1,  r2, y1, y2,           L2,  r3, z1, z2,           L3) as (
  select n1, n2, ' ', x1, x2, abs(x1-x2)-1, ' ', y1, y2, abs(y1-y2)-1, ' ', z1, z2, abs(z1-z2)-1
    from B
)   select * from C --order by n1,n2;

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

n1	n2	r1	x1	x2	L1	r2	y1	y2	L2	r3	z1	z2	L3
0	2	 	0	0	-1	 	0	1	 0	 	0	0	-1
0	4	 	0	1	 0	 	0	0	-1	 	0	0	-1
0	5	 	0	1	 0	 	0	0	-1	 	0	1	 0
0	6	 	0	1	 0	 	0	1	 0	 	0	0	-1
2	4	 	0	1	 0	 	1	0	 0	 	0	0	-1
2	5	 	0	1	 0	 	1	0	 0	 	0	1	 0
2	6	 	0	1	 0	 	1	1	-1	 	0	0	-1
4	5	 	1	1	-1	 	0	0	-1	 	0	1	 0
4	6	 	1	1	-1	 	0	1	 0	 	0	0	-1
5	6	 	1	1	-1	 	0	1	 0	 	1	0	 0

Если механизм сравнения наборов понятен, то можно перейти к следующему шагу.

...

Рейтинг:

0 / 0

24.01.2022, 17:36

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129124

Wlr-l

Гость

Шаг 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.

with A as ( --- СДНФ  функции f11 
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;
, 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
    from A  a
    join A  b  on a.n<=b.n-1
) ---  select * from B;
, C     (n1, n2,  r1, x1, x2,           L1,  r2, y1, y2,           L2,  r3, z1, z2,           L3) as (
  select n1, n2, ' ', x1, x2, abs(x1-x2)-1, ' ', y1, y2, abs(y1-y2)-1, ' ', z1, z2, abs(z1-z2)-1
    from B
) ---  select * from C --order by n1,n2;
, D     (n1, n2,  r1, x1, y1, z1,  r2,  x2,  y2,  z2,  r3, L1, L2, L3,  r4,        L) as (
  select n1, n2, ' ', x1, y1, z1, ' ',  x2,  y2,  z2, ' ', L1, L2, L3, ' ', L1+L2+L3
    from C
)   select * from D;

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

n1	n2	r1	x1	y1	z1	r2	x2	y2	z2	r3	L1	L2	L3	r4	 L
0	2	 	0	0	0	 	0	1	0	 	-1	 0	-1	 	-2
0	4	 	0	0	0	 	1	0	0	 	 0	-1	-1	 	-2
0	5	 	0	0	0	 	1	0	1	 	 0	-1	 0	 	-1
0	6	 	0	0	0	 	1	1	0	 	 0	 0	-1	 	-1
2	4	 	0	1	0	 	1	0	0	 	 0	 0	-1	 	-1
2	5	 	0	1	0	 	1	0	1	 	 0	 0	 0	 	 0
2	6	 	0	1	0	 	1	1	0	 	 0	-1	-1	 	-2
4	5	 	1	0	0	 	1	0	1	 	-1	-1	 0	 	-2
4	6	 	1	0	0	 	1	1	0	 	-1	 0	-1	 	-2
5	6	 	1	0	1	 	1	1	0	 	-1	 0	 0	 	-1

Если L равно -(n-1), где n - количество переменных в СДНФ исходной функции, то наборы n1 и n2 склеиваются и дают одну импликанту.
В данном случае это наборы, где L равно -2.

...

Рейтинг:

0 / 0

24.01.2022, 17:38

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129125

Wlr-l

Гость

Шаг 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.

with A as ( --- СДНФ  функции f11
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;
, 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
    from A  a
    join A  b  on a.n<=b.n-1
) ---  select * from B;
, C     (n1, n2,  r1, x1, x2,           L1,  r2, y1, y2,           L2,  r3, z1, z2,           L3) as (
  select n1, n2, ' ', x1, x2, abs(x1-x2)-1, ' ', y1, y2, abs(y1-y2)-1, ' ', z1, z2, abs(z1-z2)-1
    from B
) ---  select * from C --order by n1,n2;
, D     (n1, n2,  r1, x1, y1, z1,  r2,  x2,  y2,  z2,  r3, L1, L2, L3,  r4,        L) as (
  select n1, n2, ' ', x1, y1, z1, ' ',  x2,  y2,  z2, ' ', L1, L2, L3, ' ', L1+L2+L3
    from C
) ---  select * from D;
, E     (n1, n2,  r1, x1, y1, z1,  r2, L1, L2, L3,  r3,        L) as (
  select n1, n2, ' ', x1, y1, z1, ' ', L1, L2, L3, ' ', L1+L2+L3
    from D
   where L1+L2+L3=-2
)   select * from E;

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.

n1	n2	r1	x1	y1	z1	r2	L1	L2	L3	r3	 L
0	2	 	0	0	0	 	-1	 0	-1	 	-2
0	4	 	0	0	0	 	 0	-1	-1	 	-2
2	6	 	0	1	0	 	 0	-1	-1	 	-2
4	5	 	1	0	0	 	-1	-1	 0	 	-2
4	6	 	1	0	0	 	-1	 0	-1	 	-2

...

Рейтинг:

0 / 0

24.01.2022, 17:39

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129126

Wlr-l

Гость

Шаг 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.

with A as ( --- СДНФ  функции f11
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
        ) as    T(n, x,y,z)
) ---  select * from A;
, 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
    from A  a
    join A  b  on a.n<=b.n-1
) ---  select * from B;
, C     (n1, n2,  r1, x1, x2,           L1,  r2, y1, y2,           L2,  r3, z1, z2,           L3) as (
  select n1, n2, ' ', x1, x2, abs(x1-x2)-1, ' ', y1, y2, abs(y1-y2)-1, ' ', z1, z2, abs(z1-z2)-1
    from B
) ---  select * from C --order by n1,n2;
, D     (n1, n2,  r1, x1, y1, z1,  r2,  x2,  y2,  z2,  r3, L1, L2, L3,  r4,        L) as (
  select n1, n2, ' ', x1, y1, z1, ' ',  x2,  y2,  z2, ' ', L1, L2, L3, ' ', L1+L2+L3
    from C
) ---  select * from D;
, E     (n1, n2,  r1, x1, y1, z1,  r2, L1, L2, L3,  r3,        L) as (
  select n1, n2, ' ', x1, y1, z1, ' ', L1, L2, L3, ' ', L1+L2+L3
    from D
   where L1+L2+L3=-2
) ---  select * from E;
, F as (
  select n1*10+n2 as n, ' ' as r1
       , iif(L1<0, x1, iif(L1=0, 3, 9)) as x
       , iif(L2<0, y1, iif(L2=0, 3, 9)) as y
       , iif(L3<0, z1, iif(L3=0, 3, 9)) as z
    from E
)   select * from F;

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.

n1	n2	r1	x	y	z		  R
0	2	 	0	3	0		0 * 0
0	4	 	3	0	0		* 0 0
2	6	 	3	1	0		* 1 0
4	5	 	1	0	3		1 0 *
4	6	 	1	3	0		1 * 0

Столбец R я взял из результата ручной минимизации ( 22410649 ). Видно, что полученный набор соответствует результату ручной минимизации на этом же этапе.

В склеивании участвовали наборы 0, 2, 4, 5 и 6, т.е. все наборы, поэтому они не являются простыми импликантами и их запоминать не нужно. В качестве самостоятельной работы можно подумать, как определить, есть ли наборы, которые не участвовали в склейке?

Далее, описанный процесс нужно повторить над полученными наборами. Вопрос об окончании процесса повторения оставляю для самостоятельной работы.

...

Рейтинг:

0 / 0

24.01.2022, 17:41

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129128

Wlr-l

Гость

Теперь, когда мы разобрали механизмы, лежащие в основе алгоритма Квайна, отдельные шаги можно объединить в один запрос:

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

with A as ( --- Таблица истинности f11
  select *
    from (values (0, 0,0,0),
                 (2, 0,1,0),
                 (4, 1,0,0),
                 (5, 1,0,1),
                 (6, 1,1,0)
         ) as   T(n, x,y,z)
)  --- select * from A;
  select a.n as n1, b.n as n2,
         iif((abs(a.x-b.x)-1)<0, a.x, iif((abs(a.x-b.x)-1)=0, 3, 9)) as x
       , iif((abs(a.y-b.y)-1)<0, a.y, iif((abs(a.y-b.y)-1)=0, 3, 9)) as y
       , iif((abs(a.z-b.z)-1)<0, a.z, iif((abs(a.z-b.z)-1)=0, 3, 9)) as z
    from A  a
    join A  b  on a.n<=b.n-1
   where (abs(a.x-b.x)-1)+(abs(a.y-b.y)-1)+(abs(a.z-b.z)-1) = -2

Результат:

Код: plaintext

1.
2.
3.
4.
5.
6.

n1	n2	x	y	z
0	2	0	3	0
0	4	3	0	0
2	6	3	1	0
4	5	1	0	3
4	6	1	3	0

Чтобы сохранить информацию о номерах наборов СДНФ, полученные наборы перенумеруем по правилу n1*10 + n2. В запросе A исходные наборы заменим на полученные и повторим процесс еще раз.

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

with A as ( --- Таблица импликант, полученных на предыдушем этапе
  select *
    from (values (02, 0,3,0),
                 (04, 3,0,0),
                 (26, 3,1,0),
                 (45, 1,0,3),
                 (46, 1,3,0)
         ) as    T(n, x,y,z)
)  --- select * from A;
  select a.n as n1, b.n as n2,
         iif((abs(a.x-b.x)-1)<0, a.x, iif((abs(a.x-b.x)-1)=0, 3, 9)) as x
       , iif((abs(a.y-b.y)-1)<0, a.y, iif((abs(a.y-b.y)-1)=0, 3, 9)) as y
       , iif((abs(a.z-b.z)-1)<0, a.z, iif((abs(a.z-b.z)-1)=0, 3, 9)) as z
    from A  a
    join A  b  on a.n<=b.n-1
   where (abs(a.x-b.x)-1)+(abs(a.y-b.y)-1)+(abs(a.z-b.z)-1) = -2

Результат:

Код: plaintext

1.
2.
3.

n1	n2	x	y	z
2	46	3	3	0
4	26	3	3	0

В склеивании не принял участие только набор 45, следовательно, он будет простой импликантой. После всех склеек на этом этапе осталась одна импликанта 330, которая будет простой. Поскольку склеивать больше нечего процесс получения простых импликант завершен.
Мы получили две простые импликанты: (1,0,3) и (3,3,0). Нетрудно убедиться, что они покрывают все наборы (конституенты единицы) СДНФ исходной функции. (Помните, что работа с импликантной матрицей была оставлена для самостоятельной работы?). Поэтому они будут представлять тупиковую ДНФ функции f11. Поскольку тупиковая ДНФ только одна, то она будет и минимальной ДНФ функции f11.

...

Рейтинг:

0 / 0

24.01.2022, 17:42

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129130

Wlr-l

Гость

В сообщении 22420479 я привел процедуру преобразования таблицы истинности в формулу. Немного доработаем эту процедуру для вывода результата склеивания в виде формулы:

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

with I as ( --- Таблица наборов минимальной ДНФ функции f11 
  select *
    from (values (1,0,3),
                 (3,3,0)
         ) as   T(x,y,z)
) 
, J as ( --- получим список импликант (minterms)
  select x, y, z
       , concat(iif(x=3, '', iif(x=0, '¬x', 'x')),
                iif(y=3, '', iif(y=0, '¬y', 'y')),
                iif(z=3, '', iif(z=0, '¬z', 'z')) ) as minterms
    from I
) --- select * from J;
, K(dnf) as ( --- попытка получить ДНФ ("disjunctive normal form" DNF) в виде формулы
   select minterms + ' \/ ' from J for xml path('')
) ---  select * from K;

select substring(dnf, 1, len(dnf)-len(' \/ ')) as [DNF]
  from K;

Результат:

x¬y \/ ¬z

Что совпадает с результатом ручной минимизации ( 22410649 ).

Еще раз подчеркну, что здесь я рассмотрел работу алгоритма Квайна в моей интерпретации на примере функций от трех переменных. Доведение алгоритма до работы с произвольным числом переменных оставляю для самостоятельной работы.

Удачи!

...

Рейтинг:

0 / 0

24.01.2022, 17:44

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129136

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 0 / 0

Спасибо дружище. Ты конечно оставил меня в большом изумлении. Особенно от инструмента.

Я планирвал сделать command-line tool для генерации математических форм ДНФ с последующим
их превращением в обычные императивные языки такие как С++/C#/Java.

Как быть с твоим исходником - я не знаю. Скажи какой диалект SQL ты использовал? Чтоб хотя-бы воспроизвести.

...

Рейтинг:

0 / 0

24.01.2022, 17:54

| Ответить | Цитировать | Написать

Вторничный Квайн

#40129138

Wlr-l

Гость

mayton,

T-SQL (MS SQL Server), но язык здесь не принципиален.

...

Рейтинг:

0 / 0

24.01.2022, 17:58

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130431

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

mayton

Я планирвал сделать command-line tool

sqlplus вполне себе утилита командной строки.

Я тут метод Блейка прогнул на своё понимание. Мог и ошибиться, прожка ещё не достаточно проверена.
Сравните, плз, это первая встречная ТДНФ( 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.

...

Рейтинг:

0 / 0

28.01.2022, 20:23

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130437

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 0 / 0

Сегодня открыл для себя Python/matplotlib.pyplot

Симпатичная штука. Мне удобнее наверное в ней графики рисовать. По работе.

...

Рейтинг:

0 / 0

28.01.2022, 20:46

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130438

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Вот ещё функция у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 прогонов сравнивать?

...

Рейтинг:

0 / 0

28.01.2022, 20:48

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130442

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Оу! даже не так, Число перестановок одной последовательности конъ-ций. Вот его в квадрат и пополам. Как-то не вдохновляют 200 ! прогонов.

...

Рейтинг:

0 / 0

28.01.2022, 21:02

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130520

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Макет эскиза.
Если охота пробовать блейка, файл во вложении.
Учесть, что исходные данные все берутся с текущего листа в эксэлке и ответ туда же кладётся. Настройка на бОльшие размеры ручками, но недолго, хотя и нужна аккуратность.

Запускать макрос (в конце текста), но скорее всего его придётся запускать из формочки по кнопке, а не из ячейки, у меня из формочки с выделением мышем.

...

Рейтинг:

0 / 0

29.01.2022, 17:47

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130548

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 0 / 0

А как под Linux это запускать?

...

Рейтинг:

0 / 0

30.01.2022, 00:34

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130605

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 0 / 0

О терминологии. Я выписал на бумажку следующие короткие определения.

СДНФ (PDNF - perfect disjunctive normal form)

СКНФ (PCNF - perfect conjunctive normal form)

Absorption?

Код: plaintext

x AND (x OR y) = x
x OR (x AND y) = x

Material conditional (implication)
xyx->y001010101111

Annihilator ?

Код: plaintext

x OR 1 = 1

Кто не согласен - напишите плиз какой синоним или аббревиатуру вы еще слышали?

...

Рейтинг:

0 / 0

30.01.2022, 18:54

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130617

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

mayton

Material conditional (implication)
xyx->y001010101111

Ну если только это назвать "НЕматериальной импликацией" в противоположность обычной
(~a+b).
Потому что обычная обобщает бытовое наблюдение, чтообычно из ПРАВДЫ не следует ЛОЖь. А из ЛЖИ может следовать что угодно.
Здесьже ровно наоборот.

...

Рейтинг:

0 / 0

30.01.2022, 19:54

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130619

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

mayton

Annihilator ?

Код: plaintext

x OR 1 = 1

Это вот нафига? Частный случай поглощения. Главное, что тогда интуитивно понятно. А если б я, не дай бо, в статье прочёл "анигилятор", то думал бы, что речь про x *~x или хотя бы 0*x, потому что они схлопываются в результате и исчезают.
Хотя как раз такие крайние случаи подходят и под склейку тоже.

Но как раз склейку я бы интуитивно называл поглощением, поскольку простая склейка хА+А как раз поглощает меньшее множество бОльшим, и поэтому путаюсь в них без шпаргалки. И хто там из них к кому клеится, не в силах понять, вроде обладатель х-хромосомы обычно клеится - так что ль?
А нынешнее поглощение называл бы, наоборот "склеиванием по переменной" или даже м.б. как раз "анигиляцией переменной".
Но что есть, то есть.

Вообще, я замечал и даже отмечал, что программирование с некоторого момента увлеклось околонаучной терминологией. В частности идемпотентностью, нильпотентностью, теперь вот анигилятор.
Одно дело когда розово-голубые пушистые нуклоны - здесь нейтральная ассоциация. Другое дело, когда ложится на другую семантику - всегда сбивает с толку. И вопрос, ради чего плодить термины?

>>под Linux это запускать?
А как бы я под него писал?
Запускать просто: х32 виртуалку с ХР и в ней автоэкзэк.бат с эксэлой-2003, хотя м.б. достаточно и 2000.
Или транспилировать.

...

Рейтинг:

0 / 0

30.01.2022, 19:59

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130623

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Сегодня курьёзная мысля посетила.
Известна пародия на "женскую логику":
FF= [(A-->B) & (A-->C)] --> (B==C)

Левая посылка по правилам классики = ~A + BC = A --> BC.
Правая часть: (B==C) = BC + ~B~C
В женской же логике
FF = [~A --> (B==C)] = ~A --> BC + ~B~C.
"Английский юмор"

...

Рейтинг:

0 / 0

30.01.2022, 20:24

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130645

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 0 / 0

Я спрашиваю про термины не потому что хочу их плодить.

А как раз потому, что хочу их свести к одному русскому синонимы.

...

Рейтинг:

0 / 0

30.01.2022, 22:32

| Ответить | Цитировать | Написать

Вторничный Квайн

#40130812

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

mayton, нуу, во-первых я риторически вопрошал тех, кто их придумал.
А во-вторых, я помню, что очень давно приходилось читаьть по-русски навроде "материальной импликации", но не помню в каком контексте, и не помню, чтобы кто-то спецом использовал вместо обычной Имп. её отрицание под спец. именем, а у тебя как раз отрицание Имп, и ранее это уже кем-то отмечено.
Возможно для того писалось, что в контексте неклассических логик, например чтобы сделать акцент именно на 2-значном варианте ~A+B. Поскольку даже 3-значное ~A+B очевидно противоречит материалистическим привычкам.
Соглашаясь с этим, сопровождать термин Имп. чем-либо ещё представляется запутывающим.

...

Рейтинг:

0 / 0

31.01.2022, 17:41

| Ответить | Цитировать | Написать

Вторничный Квайн

#40131096

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Так и есть. Эпитет "материальная" использовался в контрасте. Причём его использование более 100 лет назад, а затем и позднее скорее всего и уместно лишь в обсуждении основополагающих принципов логики вообще. В рамках 2-значной матклассики он явно лишний.
Например цитирую
авторВ 1912 году КИ.Льюис строит новую теорию "логического следования" взамен теории материальной (классической) импликации,
изложенной в Principia Mathematica. Исходным мотивом Льюиса было избавиться от так называемых парадоксов материальной импликации:
p-->(q-->p), p-->(~p-->q). Правда затем оказалось, что и его "строгая импликация" приводит к ещё более абсурдным бытовым парадоксам вида "всё что угодно следует из всего что угодно":
p-->(q-->q), (p & ~p)-->q.

...

Рейтинг:

0 / 0

01.02.2022, 18:32

| Ответить | Цитировать | Написать

25 сообщений из 100, страница 4 из 4

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный Квайн

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=40130548&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 forum data:	1ms
get page messages:	371ms
get tp. blocked users:	0ms
others:	5ms

total:	430ms