powered by simpleCommunicator - 2.0.29     © 2024 Programmizd 02
Map
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный Квайн
25 сообщений из 100, страница 4 из 4
Вторничный Квайн
    #40128690
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Унылая пора. На пробу сДэНээФил 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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #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
Вторничный Квайн
    #40129136
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо дружище. Ты конечно оставил меня в большом изумлении. Особенно от инструмента.

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

Как быть с твоим исходником - я не знаю. Скажи какой диалект SQL ты использовал? Чтоб хотя-бы воспроизвести.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40129138
Wlr-l
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,

T-SQL (MS SQL Server), но язык здесь не принципиален.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130431
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Вторничный Квайн
    #40130437
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сегодня открыл для себя Python/matplotlib.pyplot

Симпатичная штука. Мне удобнее наверное в ней графики рисовать. По работе.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130438
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот ещё функция у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
Вторничный Квайн
    #40130442
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Оу! даже не так, Число перестановок одной последовательности конъ-ций. Вот его в квадрат и пополам. Как-то не вдохновляют 200 ! прогонов.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130520
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Макет эскиза.
Если охота пробовать блейка, файл во вложении.
Учесть, что исходные данные все берутся с текущего листа в эксэлке и ответ туда же кладётся. Настройка на бОльшие размеры ручками, но недолго, хотя и нужна аккуратность.

Запускать макрос (в конце текста), но скорее всего его придётся запускать из формочки по кнопке, а не из ячейки, у меня из формочки с выделением мышем.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130548
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А как под Linux это запускать?
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130605
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О терминологии. Я выписал на бумажку следующие короткие определения.

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

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

Absorption?

Код: plaintext
1.
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
Вторничный Квайн
    #40130617
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Material conditional (implication)
xyx->y001010101111

Ну если только это назвать "НЕматериальной импликацией" в противоположность обычной
(~a+b).
Потому что обычная обобщает бытовое наблюдение, чтообычно из ПРАВДЫ не следует ЛОЖь. А из ЛЖИ может следовать что угодно.
Здесьже ровно наоборот.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130619
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Annihilator ?
Код: plaintext
x OR 1 = 1
Это вот нафига? Частный случай поглощения. Главное, что тогда интуитивно понятно. А если б я, не дай бо, в статье прочёл "анигилятор", то думал бы, что речь про x *~x или хотя бы 0*x, потому что они схлопываются в результате и исчезают.
Хотя как раз такие крайние случаи подходят и под склейку тоже.

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

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

>>под Linux это запускать?
А как бы я под него писал?
Запускать просто: х32 виртуалку с ХР и в ней автоэкзэк.бат с эксэлой-2003, хотя м.б. достаточно и 2000.
Или транспилировать.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130623
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сегодня курьёзная мысля посетила.
Известна пародия на "женскую логику":
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
Вторничный Квайн
    #40130645
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я спрашиваю про термины не потому что хочу их плодить.

А как раз потому, что хочу их свести к одному русскому синонимы.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40130812
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, нуу, во-первых я риторически вопрошал тех, кто их придумал.
А во-вторых, я помню, что очень давно приходилось читаьть по-русски навроде "материальной импликации", но не помню в каком контексте, и не помню, чтобы кто-то спецом использовал вместо обычной Имп. её отрицание под спец. именем, а у тебя как раз отрицание Имп, и ранее это уже кем-то отмечено.
Возможно для того писалось, что в контексте неклассических логик, например чтобы сделать акцент именно на 2-значном варианте ~A+B. Поскольку даже 3-значное ~A+B очевидно противоречит материалистическим привычкам.
Соглашаясь с этим, сопровождать термин Имп. чем-либо ещё представляется запутывающим.
...
Рейтинг: 0 / 0
Вторничный Квайн
    #40131096
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так и есть. Эпитет "материальная" использовался в контрасте. Причём его использование более 100 лет назад, а затем и позднее скорее всего и уместно лишь в обсуждении основополагающих принципов логики вообще. В рамках 2-значной матклассики он явно лишний.
Например цитирую
авторВ 1912 году КИ.Льюис строит новую теорию "логического следования" взамен теории материальной (классической) импликации,
изложенной в Principia Mathematica. Исходным мотивом Льюиса было избавиться от так называемых парадоксов материальной импликации:
p-->(q-->p), p-->(~p-->q). Правда затем оказалось, что и его "строгая импликация" приводит к ещё более абсурдным бытовым парадоксам вида "всё что угодно следует из всего что угодно":
p-->(q-->q), (p & ~p)-->q.
...
Рейтинг: 0 / 0
25 сообщений из 100, страница 4 из 4
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничный Квайн
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]