Минимизация ФАЛ (КК, КМК, НК)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:15, 7 июня 2016.

Введение

На основе ФАЛ осуществляется построение схем различных ДУ. Поэтому актуальной задачей является преобразование ФАЛ к виду, обеспечивающему наиболее простую по количеству используемых логических элементов, схемную реализацию. Решение этой задачи в полном объёме сопряжено со значительными трудностями, обусловленными необходимостью учёта индивидуальных особенностей используемой элементной базы. Однако существуют методы, позволяющие преобразовывать ФАЛ к виду, содержащему минимальное число термов.

Под минимизацией логической функции понимается выполнение преобразований с целью получения наиболее простого представления ФАЛ. В инженерной практике исполь­зуются следующие основные методы минимизации: последовательного перебора, последовательного упрощения аналитического выражения, карт Карно, Квайна, Квайна – Мак-Класки, Л.Т. Мавренкова и т. д.

Метод последовательного перебора основан на простом переборе всех возможных вариантов алгебраического выражения ФАЛ. Использование метода не требует специальных знаний, однако, он применим только для очень простых функций АЛ, образованных от одной или двух переменных.

Метод последовательного упрощения аналитического выражения базируется на преобразовании ФАЛ с использованием основных законов и тождеств АЛ. Применение данного метода проиллюстрируем на примере минимизации функции (2.17). Достоинством метода является возможность его применения для минимизации любых ФАЛ, представленных в виде аналитического выражения. Однако рассматриваемый метод достаточно трудоёмок, мало нагляден, требует большого опыта, внимания и интуиции и, следовательно, легко приводит к возникновению ошибок.

Метод, основанный на применении карт Карно, предусматривает задание ФАЛ в виде коорди­натных карт состояний (рис. 2.3, 2.4). После записи ФАЛ в карту Карно сразу можно записать минимальную форму функции, что существенно уменьшает вероятность появления ошибки.

Метод Квайна основан на последовательном применении к ДСНФ функции АЛ операций неполного склеивания (2.13) и элементарного поглощения (2.10). Метод применим в основном для ФАЛ от небольшого количества аргументов.

Метод Квайна–Мак-Класки основан на использовании предложенного Мак-Класки более удобного подхода к практической реализации алгоритма Квайна. При применении данного метода функция также должна быть представлена одной из совершенных нормальных форм. Однако конституенты единицы (нуля) данной функции записываются не в натуральном виде, как в методе Квайна, а в виде условных чисел, называемых номерами соответствующих конституент. Такой подход существенно упрощает использование метода для функций с большим количеством аргументов и значительно уменьшает вероятность появления ошибки на этапе выполнения преобразований.

Метод Л.Т. Мавренкова также базируется на представлении конституент единицы в виде условных чисел, соответствующих различным наборам значений аргументов. Связи между двоичными соседними числами наглядно отображаются с использованием специальной решётки. В основу минимизации положена операция склеивания рабочих наборов рассматриваемой функции, расположенных на горизонтальных и вертикальных линиях решётки.

В данной статье приведены примеры минимизации ФАЛ с помощью карт Карно, метода Квайна - Мак-Класки, метода неопределенных коэффициентов.

Вариант 1

Исходная функция:


Минимизация табличным методом (Карты Карно)

Рис. 1. Минимизация с помощью карт Карно

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

Карта заполняется единицами, количество которых равно количеству слагаемых в СДНФ, каждое слагаемое - 1 единица.

Правила минимизации для карт Карно:

  1. В карте Карно группы единиц (ДНФ) необходимо покрыть контурами. Внутри контура должны находится только единицы (соответствует операции склеивания - нахождения импликант данной функции).
  2. Количество единиц контура должно быть степенью двойки (1, 2, 4, 8, ...).
  3. Каждый контур должен включать максимально возможное количество клеток. В этом случае он будет соответствовать простой импликанте.
  4. Все единицы в карте (даже одиночные) должны быть охвачены контурами. Любая единица может входить в контуры произвольное количество раз.
  5. Множество контуров, покрывающих все единицы функции, образуют тупиковую ДНФ.
  6. В элементарной конъюнкции, которая соответствует одному контуру, остаются только те переменные, значение которых не изменяется внутри контура.
  7. На основании закона тавтологии любая единичная клетка может быть включена в любое количество контуров, для получения минимальной ДНФ нужно стремиться к отсутствию лишних покрытий.

Этапы минимизации:

  1. Переход от ДНФ к СДНФ. Членами будут являться несклеивающиеся элементарные произведения.
  2. Переход к тупиковой форме.
  3. Переход к минимальной ДНФ.

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

Итоговая функция с учетом минимизации:

Минимизация методом Квайна - Мак-Класки

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

Вес Набор I II III
0 000000
2 011000
010001
000110
011~00 01100~
01~001 010~01
~10001 001~01
010~10 00~110
~00110
011~0~ ~11~00
~1~001 ~10~01
01~~01 010~~1
~1~001 ~10~01
001~~1 ~01~01
0~1~01 ~10~10
~10~~1
01~-~1
01~-~1
0~1~~1
~10~~1
0~1~~1
~10~1~
3 011100
011001
010101
110100
110001
001011
001110
100110
0110~1 ~11001
0101~1 ~10101
11010~ 1100~1
110~01 11~001
~01011 001~11
0~1011 ~01110
00111~ 10011~
10~110 101~01
011~01 110~01
111~00 110~10
010~11 100~11
~110~1 ~110~1
~101~1 ~101~1
110~~1 11~0~1
110~~1 11~0~1
~01~11 ~~1011
~01~11 ~~1011
~01~11 0~1~11
~~1011 0~1~11
~0111~ ~0111~
10~11~ 10~11~
101~~1 011~~1
110~1~ ~10~11
01~~11 1~0~11
10~~11
4 010111
100111
110011
110101
101011
101101
101110
001111
011011
111010
111001
01~111 ~10111
10~111 1~0111
110~11 11~011
1101~1 101~11
1~1011 1011~1
10111~ ~01111
0~1111 011~11
~11011 11101~
1110~1
5 101111
011111
110111
111011

После выбора первичных импликант нужно отобрать только те, которые войдут в конечную минимальную функцию. Это осуществляется по следующему принципу:

  1. Выбирается тот импликант, который для конкретного набора является единственным.
  2. Если таковых не осталось, импликанты выбираются таким образом, чтобы для конкретного набора их был не более двух и чтобы они покрывали максимально возможное число наборов без повторений (см. таблицу).
  3. То же самое, но количество импликант равно трем.
Первичные импликанты 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
+
+
+ +
+ + +
+
+ + +
+ + +
+ + + +
+ + + + + + + + +
+ + + + + + + +
+ + + + + + + +
+ + + + + + +
+ + + + + + +
+ + + + +
+ + + + +
+ + +
+ + + +
+ + + +

Итоговая функция, составленная из выбранных импликант:

Минимизация методом неопределённых коэффициентов

Метод неопределенных коэффициентов является самым трудоемким из всех представленных. Для минимизации функции с помощью этого метода желательно иметь полную таблицу наборов чисел в ДСС.

Выпишем столбец функции от шести переменных.

Нахождение минимальной ДНФ сводится к решению системы линейных уравнений и состоит из следующих этапов:

  1. Составляются уравнения из всех наборов коэффициентов от 1 до 6 переменных.
  2. Выкидываются уравнения, в которых значение функции равно нулю, а также нулевые коэффициенты
  3. Поиск наиболее часто встречающихся терм минимального ранга.
  4. Удаляются повторяющиеся коэффициенты.

Шаг 1. Составляем систему уравнений


K10 v K20 v K30 v K40 v K50 v K60 v K1200 v K1300 v K1400 v K1500 v K1600 v K2300 v K2400 v K2500 v K2600 v K3400 v K3500 v K3600 v K4500 v K4600 v K5600 v K123000 v K124000 v K125000 v K126000 v K134000 v K135000 v K136000 v K145000 v K146000 v K156000 v K234000 v K235000 v K236000 v K245000 v K246000 v K256000 v K345000 v K346000 v K356000 v K456000 v K12340000 v K12350000 v K12360000 v K12450000 v K12460000 v K12560000 v K13450000 v K13460000 v K13560000 v K14560000 v K23450000 v K23460000 v K23560000 v K24560000 v K34560000 v K1234500000 v K1234600000 v K1235600000 v K1245600000 v K1345600000 v K2345600000 v K123456000000 = 1


K11 v K20 v K30 v K40 v K50 v K60 v K1210 v K1310 v K1410 v K1510 v K1610 v K2300 v K2400 v K2500 v K2600 v K3400 v K3500 v K3600 v K4500 v K4600 v K5600 v K123100 v K124100 v K125100 v K126100 v K134100 v K135100 v K136100 v K145100 v K146100 v K156100 v K234000 v K235000 v K236000 v K245000 v K246000 v K256000 v K345000 v K346000 v K356000 v K456000 v K12341000 v K12351000 v K12361000 v K12451000 v K12461000 v K12561000 v K13451000 v K13461000 v K13561000 v K14561000 v K23450000 v K23460000 v K23560000 v K24560000 v K34560000 v K1234510000 v K1234610000 v K1235610000 v K1245610000 v K1345610000 v K2345600000 v K123456100000 = 0


K10 v K21 v K30 v K40 v K50 v K60 v K1201 v K1300 v K1400 v K1500 v K1600 v K2310 v K2410 v K2510 v K2610 v K3400 v K3500 v K3600 v K4500 v K4600 v K5600 v K123010 v K124010 v K125010 v K126010 v K134000 v K135000 v K136000 v K145000 v K146000 v K156000 v K234100 v K235100 v K236100 v K245100 v K246100 v K256100 v K345000 v K346000 v K356000 v K456000 v K12340100 v K12350100 v K12360100 v K12450100 v K12460100 v K12560100 v K13450000 v K13460000 v K13560000 v K14560000 v K23451000 v K23461000 v K23561000 v K24561000 v K34560000 v K1234501000 v K1234601000 v K1235601000 v K1245601000 v K1345600000 v K2345610000 v K123456010000 = 0


K11 v K21 v K30 v K40 v K50 v K60 v K1211 v K1310 v K1410 v K1510 v K1610 v K2310 v K2410 v K2510 v K2610 v K3400 v K3500 v K3600 v K4500 v K4600 v K5600 v K123110 v K124110 v K125110 v K126110 v K134100 v K135100 v K136100 v K145100 v K146100 v K156100 v K234100 v K235100 v K236100 v K245100 v K246100 v K256100 v K345000 v K346000 v K356000 v K456000 v K12341100 v K12351100 v K12361100 v K12451100 v K12461100 v K12561100 v K13451000 v K13461000 v K13561000 v K14561000 v K23451000 v K23461000 v K23561000 v K24561000 v K34560000 v K1234511000 v K1234611000 v K1235611000 v K1245611000 v K1345610000 v K2345610000 v K123456110000 = 0


K10 v K20 v K31 v K40 v K50 v K60 v K1200 v K1301 v K1400 v K1500 v K1600 v K2301 v K2400 v K2500 v K2600 v K3410 v K3510 v K3610 v K4500 v K4600 v K5600 v K123001 v K124000 v K125000 v K126000 v K134010 v K135010 v K136010 v K145000 v K146000 v K156000 v K234010 v K235010 v K236010 v K245000 v K246000 v K256000 v K345100 v K346100 v K356100 v K456000 v K12340010 v K12350010 v K12360010 v K12450000 v K12460000 v K12560000 v K13450100 v K13460100 v K13560100 v K14560000 v K23450100 v K23460100 v K23560100 v K24560000 v K34561000 v K1234500100 v K1234600100 v K1235600100 v K1245600000 v K1345601000 v K2345601000 v K123456001000 = 0


K11 v K20 v K31 v K40 v K50 v K60 v K1210 v K1311 v K1410 v K1510 v K1610 v K2301 v K2400 v K2500 v K2600 v K3410 v K3510 v K3610 v K4500 v K4600 v K5600 v K123101 v K124100 v K125100 v K126100 v K134110 v K135110 v K136110 v K145100 v K146100 v K156100 v K234010 v K235010 v K236010 v K245000 v K246000 v K256000 v K345100 v K346100 v K356100 v K456000 v K12341010 v K12351010 v K12361010 v K12451000 v K12461000 v K12561000 v K13451100 v K13461100 v K13561100 v K14561000 v K23450100 v K23460100 v K23560100 v K24560000 v K34561000 v K1234510100 v K1234610100 v K1235610100 v K1245610000 v K1345611000 v K2345601000 v K123456101000 = 0


K10 v K21 v K31 v K40 v K50 v K60 v K1201 v K1301 v K1400 v K1500 v K1600 v K2311 v K2410 v K2510 v K2610 v K3410 v K3510 v K3610 v K4500 v K4600 v K5600 v K123011 v K124010 v K125010 v K126010 v K134010 v K135010 v K136010 v K145000 v K146000 v K156000 v K234110 v K235110 v K236110 v K245100 v K246100 v K256100 v K345100 v K346100 v K356100 v K456000 v K12340110 v K12350110 v K12360110 v K12450100 v K12460100 v K12560100 v K13450100 v K13460100 v K13560100 v K14560000 v K23451100 v K23461100 v K23561100 v K24561000 v K34561000 v K1234501100 v K1234601100 v K1235601100 v K1245601000 v K1345601000 v K2345611000 v K123456011000 = 0


K11 v K21 v K31 v K40 v K50 v K60 v K1211 v K1311 v K1410 v K1510 v K1610 v K2311 v K2410 v K2510 v K2610 v K3410 v K3510 v K3610 v K4500 v K4600 v K5600 v K123111 v K124110 v K125110 v K126110 v K134110 v K135110 v K136110 v K145100 v K146100 v K156100 v K234110 v K235110 v K236110 v K245100 v K246100 v K256100 v K345100 v K346100 v K356100 v K456000 v K12341110 v K12351110 v K12361110 v K12451100 v K12461100 v K12561100 v K13451100 v K13461100 v K13561100 v K14561000 v K23451100 v K23461100 v K23561100 v K24561000 v K34561000 v K1234511100 v K1234611100 v K1235611100 v K1245611000 v K1345611000 v K2345611000 v K123456111000 = 0


K10 v K20 v K30 v K41 v K50 v K60 v K1200 v K1300 v K1401 v K1500 v K1600 v K2300 v K2401 v K2500 v K2600 v K3401 v K3500 v K3600 v K4510 v K4610 v K5600 v K123000 v K124001 v K125000 v K126000 v K134001 v K135000 v K136000 v K145010 v K146010 v K156000 v K234001 v K235000 v K236000 v K245010 v K246010 v K256000 v K345010 v K346010 v K356000 v K456100 v K12340001 v K12350000 v K12360000 v K12450010 v K12460010 v K12560000 v K13450010 v K13460010 v K13560000 v K14560100 v K23450010 v K23460010 v K23560000 v K24560100 v K34560100 v K1234500010 v K1234600010 v K1235600000 v K1245600100 v K1345600100 v K2345600100 v K123456000100 = 0


K11 v K20 v K30 v K41 v K50 v K60 v K1210 v K1310 v K1411 v K1510 v K1610 v K2300 v K2401 v K2500 v K2600 v K3401 v K3500 v K3600 v K4510 v K4610 v K5600 v K123100 v K124101 v K125100 v K126100 v K134101 v K135100 v K136100 v K145110 v K146110 v K156100 v K234001 v K235000 v K236000 v K245010 v K246010 v K256000 v K345010 v K346010 v K356000 v K456100 v K12341001 v K12351000 v K12361000 v K12451010 v K12461010 v K12561000 v K13451010 v K13461010 v K13561000 v K14561100 v K23450010 v K23460010 v K23560000 v K24560100 v K34560100 v K1234510010 v K1234610010 v K1235610000 v K1245610100 v K1345610100 v K2345600100 v K123456100100 = 1


K10 v K21 v K30 v K41 v K50 v K60 v K1201 v K1300 v K1401 v K1500 v K1600 v K2310 v K2411 v K2510 v K2610 v K3401 v K3500 v K3600 v K4510 v K4610 v K5600 v K123010 v K124011 v K125010 v K126010 v K134001 v K135000 v K136000 v K145010 v K146010 v K156000 v K234101 v K235100 v K236100 v K245110 v K246110 v K256100 v K345010 v K346010 v K356000 v K456100 v K12340101 v K12350100 v K12360100 v K12450110 v K12460110 v K12560100 v K13450010 v K13460010 v K13560000 v K14560100 v K23451010 v K23461010 v K23561000 v K24561100 v K34560100 v K1234501010 v K1234601010 v K1235601000 v K1245601100 v K1345600100 v K2345610100 v K123456010100 = 0


K11 v K21 v K30 v K41 v K50 v K60 v K1211 v K1310 v K1411 v K1510 v K1610 v K2310 v K2411 v K2510 v K2610 v K3401 v K3500 v K3600 v K4510 v K4610 v K5600 v K123110 v K124111 v K125110 v K126110 v K134101 v K135100 v K136100 v K145110 v K146110 v K156100 v K234101 v K235100 v K236100 v K245110 v K246110 v K256100 v K345010 v K346010 v K356000 v K456100 v K12341101 v K12351100 v K12361100 v K12451110 v K12461110 v K12561100 v K13451010 v K13461010 v K13561000 v K14561100 v K23451010 v K23461010 v K23561000 v K24561100 v K34560100 v K1234511010 v K1234611010 v K1235611000 v K1245611100 v K1345610100 v K2345610100 v K123456110100 = 1


K10 v K20 v K31 v K41 v K50 v K60 v K1200 v K1301 v K1401 v K1500 v K1600 v K2301 v K2401 v K2500 v K2600 v K3411 v K3510 v K3610 v K4510 v K4610 v K5600 v K123001 v K124001 v K125000 v K126000 v K134011 v K135010 v K136010 v K145010 v K146010 v K156000 v K234011 v K235010 v K236010 v K245010 v K246010 v K256000 v K345110 v K346110 v K356100 v K456100 v K12340011 v K12350010 v K12360010 v K12450010 v K12460010 v K12560000 v K13450110 v K13460110 v K13560100 v K14560100 v K23450110 v K23460110 v K23560100 v K24560100 v K34561100 v K1234500110 v K1234600110 v K1235600100 v K1245600100 v K1345601100 v K2345601100 v K123456001100 = 0


K11 v K20 v K31 v K41 v K50 v K60 v K1210 v K1311 v K1411 v K1510 v K1610 v K2301 v K2401 v K2500 v K2600 v K3411 v K3510 v K3610 v K4510 v K4610 v K5600 v K123101 v K124101 v K125100 v K126100 v K134111 v K135110 v K136110 v K145110 v K146110 v K156100 v K234011 v K235010 v K236010 v K245010 v K246010 v K256000 v K345110 v K346110 v K356100 v K456100 v K12341011 v K12351010 v K12361010 v K12451010 v K12461010 v K12561000 v K13451110 v K13461110 v K13561100 v K14561100 v K23450110 v K23460110 v K23560100 v K24560100 v K34561100 v K1234510110 v K1234610110 v K1235610100 v K1245610100 v K1345611100 v K2345601100 v K123456101100 = 1


K10 v K21 v K31 v K41 v K50 v K60 v K1201 v K1301 v K1401 v K1500 v K1600 v K2311 v K2411 v K2510 v K2610 v K3411 v K3510 v K3610 v K4510 v K4610 v K5600 v K123011 v K124011 v K125010 v K126010 v K134011 v K135010 v K136010 v K145010 v K146010 v K156000 v K234111 v K235110 v K236110 v K245110 v K246110 v K256100 v K345110 v K346110 v K356100 v K456100 v K12340111 v K12350110 v K12360110 v K12450110 v K12460110 v K12560100 v K13450110 v K13460110 v K13560100 v K14560100 v K23451110 v K23461110 v K23561100 v K24561100 v K34561100 v K1234501110 v K1234601110 v K1235601100 v K1245601100 v K1345601100 v K2345611100 v K123456011100 = 1


K11 v K21 v K31 v K41 v K50 v K60 v K1211 v K1311 v K1411 v K1510 v K1610 v K2311 v K2411 v K2510 v K2610 v K3411 v K3510 v K3610 v K4510 v K4610 v K5600 v K123111 v K124111 v K125110 v K126110 v K134111 v K135110 v K136110 v K145110 v K146110 v K156100 v K234111 v K235110 v K236110 v K245110 v K246110 v K256100 v K345110 v K346110 v K356100 v K456100 v K12341111 v K12351110 v K12361110 v K12451110 v K12461110 v K12561100 v K13451110 v K13461110 v K13561100 v K14561100 v K23451110 v K23461110 v K23561100 v K24561100 v K34561100 v K1234511110 v K1234611110 v K1235611100 v K1245611100 v K1345611100 v K2345611100 v K123456111100 = 1


K10 v K20 v K30 v K40 v K51 v K60 v K1200 v K1300 v K1400 v K1501 v K1600 v K2300 v K2400 v K2501 v K2600 v K3400 v K3501 v K3600 v K4501 v K4600 v K5610 v K123000 v K124000 v K125001 v K126000 v K134000 v K135001 v K136000 v K145001 v K146000 v K156010 v K234000 v K235001 v K236000 v K245001 v K246000 v K256010 v K345001 v K346000 v K356010 v K456010 v K12340000 v K12350001 v K12360000 v K12450001 v K12460000 v K12560010 v K13450001 v K13460000 v K13560010 v K14560010 v K23450001 v K23460000 v K23560010 v K24560010 v K34560010 v K1234500001 v K1234600000 v K1235600010 v K1245600010 v K1345600010 v K2345600010 v K123456000010 = 0


K11 v K20 v K30 v K40 v K51 v K60 v K1210 v K1310 v K1410 v K1511 v K1610 v K2300 v K2400 v K2501 v K2600 v K3400 v K3501 v K3600 v K4501 v K4600 v K5610 v K123100 v K124100 v K125101 v K126100 v K134100 v K135101 v K136100 v K145101 v K146100 v K156110 v K234000 v K235001 v K236000 v K245001 v K246000 v K256010 v K345001 v K346000 v K356010 v K456010 v K12341000 v K12351001 v K12361000 v K12451001 v K12461000 v K12561010 v K13451001 v K13461000 v K13561010 v K14561010 v K23450001 v K23460000 v K23560010 v K24560010 v K34560010 v K1234510001 v K1234610000 v K1235610010 v K1245610010 v K1345610010 v K2345600010 v K123456100010 = 1


K10 v K21 v K30 v K40 v K51 v K60 v K1201 v K1300 v K1400 v K1501 v K1600 v K2310 v K2410 v K2511 v K2610 v K3400 v K3501 v K3600 v K4501 v K4600 v K5610 v K123010 v K124010 v K125011 v K126010 v K134000 v K135001 v K136000 v K145001 v K146000 v K156010 v K234100 v K235101 v K236100 v K245101 v K246100 v K256110 v K345001 v K346000 v K356010 v K456010 v K12340100 v K12350101 v K12360100 v K12450101 v K12460100 v K12560110 v K13450001 v K13460000 v K13560010 v K14560010 v K23451001 v K23461000 v K23561010 v K24561010 v K34560010 v K1234501001 v K1234601000 v K1235601010 v K1245601010 v K1345600010 v K2345610010 v K123456010010 = 1


K11 v K21 v K30 v K40 v K51 v K60 v K1211 v K1310 v K1410 v K1511 v K1610 v K2310 v K2410 v K2511 v K2610 v K3400 v K3501 v K3600 v K4501 v K4600 v K5610 v K123110 v K124110 v K125111 v K126110 v K134100 v K135101 v K136100 v K145101 v K146100 v K156110 v K234100 v K235101 v K236100 v K245101 v K246100 v K256110 v K345001 v K346000 v K356010 v K456010 v K12341100 v K12351101 v K12361100 v K12451101 v K12461100 v K12561110 v K13451001 v K13461000 v K13561010 v K14561010 v K23451001 v K23461000 v K23561010 v K24561010 v K34560010 v K1234511001 v K1234611000 v K1235611010 v K1245611010 v K1345610010 v K2345610010 v K123456110010 = 1


K10 v K20 v K31 v K40 v K51 v K60 v K1200 v K1301 v K1400 v K1501 v K1600 v K2301 v K2400 v K2501 v K2600 v K3410 v K3511 v K3610 v K4501 v K4600 v K5610 v K123001 v K124000 v K125001 v K126000 v K134010 v K135011 v K136010 v K145001 v K146000 v K156010 v K234010 v K235011 v K236010 v K245001 v K246000 v K256010 v K345101 v K346100 v K356110 v K456010 v K12340010 v K12350011 v K12360010 v K12450001 v K12460000 v K12560010 v K13450101 v K13460100 v K13560110 v K14560010 v K23450101 v K23460100 v K23560110 v K24560010 v K34561010 v K1234500101 v K1234600100 v K1235600110 v K1245600010 v K1345601010 v K2345601010 v K123456001010 = 0


K11 v K20 v K31 v K40 v K51 v K60 v K1210 v K1311 v K1410 v K1511 v K1610 v K2301 v K2400 v K2501 v K2600 v K3410 v K3511 v K3610 v K4501 v K4600 v K5610 v K123101 v K124100 v K125101 v K126100 v K134110 v K135111 v K136110 v K145101 v K146100 v K156110 v K234010 v K235011 v K236010 v K245001 v K246000 v K256010 v K345101 v K346100 v K356110 v K456010 v K12341010 v K12351011 v K12361010 v K12451001 v K12461000 v K12561010 v K13451101 v K13461100 v K13561110 v K14561010 v K23450101 v K23460100 v K23560110 v K24560010 v K34561010 v K1234510101 v K1234610100 v K1235610110 v K1245610010 v K1345611010 v K2345601010 v K123456101010 = 1


K10 v K21 v K31 v K40 v K51 v K60 v K1201 v K1301 v K1400 v K1501 v K1600 v K2311 v K2410 v K2511 v K2610 v K3410 v K3511 v K3610 v K4501 v K4600 v K5610 v K123011 v K124010 v K125011 v K126010 v K134010 v K135011 v K136010 v K145001 v K146000 v K156010 v K234110 v K235111 v K236110 v K245101 v K246100 v K256110 v K345101 v K346100 v K356110 v K456010 v K12340110 v K12350111 v K12360110 v K12450101 v K12460100 v K12560110 v K13450101 v K13460100 v K13560110 v K14560010 v K23451101 v K23461100 v K23561110 v K24561010 v K34561010 v K1234501101 v K1234601100 v K1235601110 v K1245601010 v K1345601010 v K2345611010 v K123456011010 = 1


K11 v K21 v K31 v K40 v K51 v K60 v K1211 v K1311 v K1410 v K1511 v K1610 v K2311 v K2410 v K2511 v K2610 v K3410 v K3511 v K3610 v K4501 v K4600 v K5610 v K123111 v K124110 v K125111 v K126110 v K134110 v K135111 v K136110 v K145101 v K146100 v K156110 v K234110 v K235111 v K236110 v K245101 v K246100 v K256110 v K345101 v K346100 v K356110 v K456010 v K12341110 v K12351111 v K12361110 v K12451101 v K12461100 v K12561110 v K13451101 v K13461100 v K13561110 v K14561010 v K23451101 v K23461100 v K23561110 v K24561010 v K34561010 v K1234511101 v K1234611100 v K1235611110 v K1245611010 v K1345611010 v K2345611010 v K123456111010 = 1


K10 v K20 v K30 v K41 v K51 v K60 v K1200 v K1300 v K1401 v K1501 v K1600 v K2300 v K2401 v K2501 v K2600 v K3401 v K3501 v K3600 v K4511 v K4610 v K5610 v K123000 v K124001 v K125001 v K126000 v K134001 v K135001 v K136000 v K145011 v K146010 v K156010 v K234001 v K235001 v K236000 v K245011 v K246010 v K256010 v K345011 v K346010 v K356010 v K456110 v K12340001 v K12350001 v K12360000 v K12450011 v K12460010 v K12560010 v K13450011 v K13460010 v K13560010 v K14560110 v K23450011 v K23460010 v K23560010 v K24560110 v K34560110 v K1234500011 v K1234600010 v K1235600010 v K1245600110 v K1345600110 v K2345600110 v K123456000110 = 1


K11 v K20 v K30 v K41 v K51 v K60 v K1210 v K1310 v K1411 v K1511 v K1610 v K2300 v K2401 v K2501 v K2600 v K3401 v K3501 v K3600 v K4511 v K4610 v K5610 v K123100 v K124101 v K125101 v K126100 v K134101 v K135101 v K136100 v K145111 v K146110 v K156110 v K234001 v K235001 v K236000 v K245011 v K246010 v K256010 v K345011 v K346010 v K356010 v K456110 v K12341001 v K12351001 v K12361000 v K12451011 v K12461010 v K12561010 v K13451011 v K13461010 v K13561010 v K14561110 v K23450011 v K23460010 v K23560010 v K24560110 v K34560110 v K1234510011 v K1234610010 v K1235610010 v K1245610110 v K1345610110 v K2345600110 v K123456100110 = 1


K10 v K21 v K30 v K41 v K51 v K60 v K1201 v K1300 v K1401 v K1501 v K1600 v K2310 v K2411 v K2511 v K2610 v K3401 v K3501 v K3600 v K4511 v K4610 v K5610 v K123010 v K124011 v K125011 v K126010 v K134001 v K135001 v K136000 v K145011 v K146010 v K156010 v K234101 v K235101 v K236100 v K245111 v K246110 v K256110 v K345011 v K346010 v K356010 v K456110 v K12340101 v K12350101 v K12360100 v K12450111 v K12460110 v K12560110 v K13450011 v K13460010 v K13560010 v K14560110 v K23451011 v K23461010 v K23561010 v K24561110 v K34560110 v K1234501011 v K1234601010 v K1235601010 v K1245601110 v K1345600110 v K2345610110 v K123456010110 = 0


K11 v K21 v K30 v K41 v K51 v K60 v K1211 v K1310 v K1411 v K1511 v K1610 v K2310 v K2411 v K2511 v K2610 v K3401 v K3501 v K3600 v K4511 v K4610 v K5610 v K123110 v K124111 v K125111 v K126110 v K134101 v K135101 v K136100 v K145111 v K146110 v K156110 v K234101 v K235101 v K236100 v K245111 v K246110 v K256110 v K345011 v K346010 v K356010 v K456110 v K12341101 v K12351101 v K12361100 v K12451111 v K12461110 v K12561110 v K13451011 v K13461010 v K13561010 v K14561110 v K23451011 v K23461010 v K23561010 v K24561110 v K34560110 v K1234511011 v K1234611010 v K1235611010 v K1245611110 v K1345610110 v K2345610110 v K123456110110 = 1


K10 v K20 v K31 v K41 v K51 v K60 v K1200 v K1301 v K1401 v K1501 v K1600 v K2301 v K2401 v K2501 v K2600 v K3411 v K3511 v K3610 v K4511 v K4610 v K5610 v K123001 v K124001 v K125001 v K126000 v K134011 v K135011 v K136010 v K145011 v K146010 v K156010 v K234011 v K235011 v K236010 v K245011 v K246010 v K256010 v K345111 v K346110 v K356110 v K456110 v K12340011 v K12350011 v K12360010 v K12450011 v K12460010 v K12560010 v K13450111 v K13460110 v K13560110 v K14560110 v K23450111 v K23460110 v K23560110 v K24560110 v K34561110 v K1234500111 v K1234600110 v K1235600110 v K1245600110 v K1345601110 v K2345601110 v K123456001110 = 1


K11 v K20 v K31 v K41 v K51 v K60 v K1210 v K1311 v K1411 v K1511 v K1610 v K2301 v K2401 v K2501 v K2600 v K3411 v K3511 v K3610 v K4511 v K4610 v K5610 v K123101 v K124101 v K125101 v K126100 v K134111 v K135111 v K136110 v K145111 v K146110 v K156110 v K234011 v K235011 v K236010 v K245011 v K246010 v K256010 v K345111 v K346110 v K356110 v K456110 v K12341011 v K12351011 v K12361010 v K12451011 v K12461010 v K12561010 v K13451111 v K13461110 v K13561110 v K14561110 v K23450111 v K23460110 v K23560110 v K24560110 v K34561110 v K1234510111 v K1234610110 v K1235610110 v K1245610110 v K1345611110 v K2345601110 v K123456101110 = 1


K10 v K21 v K31 v K41 v K51 v K60 v K1201 v K1301 v K1401 v K1501 v K1600 v K2311 v K2411 v K2511 v K2610 v K3411 v K3511 v K3610 v K4511 v K4610 v K5610 v K123011 v K124011 v K125011 v K126010 v K134011 v K135011 v K136010 v K145011 v K146010 v K156010 v K234111 v K235111 v K236110 v K245111 v K246110 v K256110 v K345111 v K346110 v K356110 v K456110 v K12340111 v K12350111 v K12360110 v K12450111 v K12460110 v K12560110 v K13450111 v K13460110 v K13560110 v K14560110 v K23451111 v K23461110 v K23561110 v K24561110 v K34561110 v K1234501111 v K1234601110 v K1235601110 v K1245601110 v K1345601110 v K2345611110 v K123456011110 = 0


K11 v K21 v K31 v K41 v K51 v K60 v K1211 v K1311 v K1411 v K1511 v K1610 v K2311 v K2411 v K2511 v K2610 v K3411 v K3511 v K3610 v K4511 v K4610 v K5610 v K123111 v K124111 v K125111 v K126110 v K134111 v K135111 v K136110 v K145111 v K146110 v K156110 v K234111 v K235111 v K236110 v K245111 v K246110 v K256110 v K345111 v K346110 v K356110 v K456110 v K12341111 v K12351111 v K12361110 v K12451111 v K12461110 v K12561110 v K13451111 v K13461110 v K13561110 v K14561110 v K23451111 v K23461110 v K23561110 v K24561110 v K34561110 v K1234511111 v K1234611110 v K1235611110 v K1245611110 v K1345611110 v K2345611110 v K123456111110 = 1


K10 v K20 v K30 v K40 v K50 v K61 v K1200 v K1300 v K1400 v K1500 v K1601 v K2300 v K2400 v K2500 v K2601 v K3400 v K3500 v K3601 v K4500 v K4601 v K5601 v K123000 v K124000 v K125000 v K126001 v K134000 v K135000 v K136001 v K145000 v K146001 v K156001 v K234000 v K235000 v K236001 v K245000 v K246001 v K256001 v K345000 v K346001 v K356001 v K456001 v K12340000 v K12350000 v K12360001 v K12450000 v K12460001 v K12560001 v K13450000 v K13460001 v K13560001 v K14560001 v K23450000 v K23460001 v K23560001 v K24560001 v K34560001 v K1234500000 v K1234600001 v K1235600001 v K1245600001 v K1345600001 v K2345600001 v K123456000001 = 0


K11 v K20 v K30 v K40 v K50 v K61 v K1210 v K1310 v K1410 v K1510 v K1611 v K2300 v K2400 v K2500 v K2601 v K3400 v K3500 v K3601 v K4500 v K4601 v K5601 v K123100 v K124100 v K125100 v K126101 v K134100 v K135100 v K136101 v K145100 v K146101 v K156101 v K234000 v K235000 v K236001 v K245000 v K246001 v K256001 v K345000 v K346001 v K356001 v K456001 v K12341000 v K12351000 v K12361001 v K12451000 v K12461001 v K12561001 v K13451000 v K13461001 v K13561001 v K14561001 v K23450000 v K23460001 v K23560001 v K24560001 v K34560001 v K1234510000 v K1234610001 v K1235610001 v K1245610001 v K1345610001 v K2345600001 v K123456100001 = 0


K10 v K21 v K30 v K40 v K50 v K61 v K1201 v K1300 v K1400 v K1500 v K1601 v K2310 v K2410 v K2510 v K2611 v K3400 v K3500 v K3601 v K4500 v K4601 v K5601 v K123010 v K124010 v K125010 v K126011 v K134000 v K135000 v K136001 v K145000 v K146001 v K156001 v K234100 v K235100 v K236101 v K245100 v K246101 v K256101 v K345000 v K346001 v K356001 v K456001 v K12340100 v K12350100 v K12360101 v K12450100 v K12460101 v K12560101 v K13450000 v K13460001 v K13560001 v K14560001 v K23451000 v K23461001 v K23561001 v K24561001 v K34560001 v K1234501000 v K1234601001 v K1235601001 v K1245601001 v K1345600001 v K2345610001 v K123456010001 = 0


K11 v K21 v K30 v K40 v K50 v K61 v K1211 v K1310 v K1410 v K1510 v K1611 v K2310 v K2410 v K2510 v K2611 v K3400 v K3500 v K3601 v K4500 v K4601 v K5601 v K123110 v K124110 v K125110 v K126111 v K134100 v K135100 v K136101 v K145100 v K146101 v K156101 v K234100 v K235100 v K236101 v K245100 v K246101 v K256101 v K345000 v K346001 v K356001 v K456001 v K12341100 v K12351100 v K12361101 v K12451100 v K12461101 v K12561101 v K13451000 v K13461001 v K13561001 v K14561001 v K23451000 v K23461001 v K23561001 v K24561001 v K34560001 v K1234511000 v K1234611001 v K1235611001 v K1245611001 v K1345610001 v K2345610001 v K123456110001 = 1


K10 v K20 v K31 v K40 v K50 v K61 v K1200 v K1301 v K1400 v K1500 v K1601 v K2301 v K2400 v K2500 v K2601 v K3410 v K3510 v K3611 v K4500 v K4601 v K5601 v K123001 v K124000 v K125000 v K126001 v K134010 v K135010 v K136011 v K145000 v K146001 v K156001 v K234010 v K235010 v K236011 v K245000 v K246001 v K256001 v K345100 v K346101 v K356101 v K456001 v K12340010 v K12350010 v K12360011 v K12450000 v K12460001 v K12560001 v K13450100 v K13460101 v K13560101 v K14560001 v K23450100 v K23460101 v K23560101 v K24560001 v K34561001 v K1234500100 v K1234600101 v K1235600101 v K1245600001 v K1345601001 v K2345601001 v K123456001001 = 0


K11 v K20 v K31 v K40 v K50 v K61 v K1210 v K1311 v K1410 v K1510 v K1611 v K2301 v K2400 v K2500 v K2601 v K3410 v K3510 v K3611 v K4500 v K4601 v K5601 v K123101 v K124100 v K125100 v K126101 v K134110 v K135110 v K136111 v K145100 v K146101 v K156101 v K234010 v K235010 v K236011 v K245000 v K246001 v K256001 v K345100 v K346101 v K356101 v K456001 v K12341010 v K12351010 v K12361011 v K12451000 v K12461001 v K12561001 v K13451100 v K13461101 v K13561101 v K14561001 v K23450100 v K23460101 v K23560101 v K24560001 v K34561001 v K1234510100 v K1234610101 v K1235610101 v K1245610001 v K1345611001 v K2345601001 v K123456101001 = 0


K10 v K21 v K31 v K40 v K50 v K61 v K1201 v K1301 v K1400 v K1500 v K1601 v K2311 v K2410 v K2510 v K2611 v K3410 v K3510 v K3611 v K4500 v K4601 v K5601 v K123011 v K124010 v K125010 v K126011 v K134010 v K135010 v K136011 v K145000 v K146001 v K156001 v K234110 v K235110 v K236111 v K245100 v K246101 v K256101 v K345100 v K346101 v K356101 v K456001 v K12340110 v K12350110 v K12360111 v K12450100 v K12460101 v K12560101 v K13450100 v K13460101 v K13560101 v K14560001 v K23451100 v K23461101 v K23561101 v K24561001 v K34561001 v K1234501100 v K1234601101 v K1235601101 v K1245601001 v K1345601001 v K2345611001 v K123456011001 = 1


K11 v K21 v K31 v K40 v K50 v K61 v K1211 v K1311 v K1410 v K1510 v K1611 v K2311 v K2410 v K2510 v K2611 v K3410 v K3510 v K3611 v K4500 v K4601 v K5601 v K123111 v K124110 v K125110 v K126111 v K134110 v K135110 v K136111 v K145100 v K146101 v K156101 v K234110 v K235110 v K236111 v K245100 v K246101 v K256101 v K345100 v K346101 v K356101 v K456001 v K12341110 v K12351110 v K12361111 v K12451100 v K12461101 v K12561101 v K13451100 v K13461101 v K13561101 v K14561001 v K23451100 v K23461101 v K23561101 v K24561001 v K34561001 v K1234511100 v K1234611101 v K1235611101 v K1245611001 v K1345611001 v K2345611001 v K123456111001 = 1


K10 v K20 v K30 v K41 v K50 v K61 v K1200 v K1300 v K1401 v K1500 v K1601 v K2300 v K2401 v K2500 v K2601 v K3401 v K3500 v K3601 v K4510 v K4611 v K5601 v K123000 v K124001 v K125000 v K126001 v K134001 v K135000 v K136001 v K145010 v K146011 v K156001 v K234001 v K235000 v K236001 v K245010 v K246011 v K256001 v K345010 v K346011 v K356001 v K456101 v K12340001 v K12350000 v K12360001 v K12450010 v K12460011 v K12560001 v K13450010 v K13460011 v K13560001 v K14560101 v K23450010 v K23460011 v K23560001 v K24560101 v K34560101 v K1234500010 v K1234600011 v K1235600001 v K1245600101 v K1345600101 v K2345600101 v K123456000101 = 0


K11 v K20 v K30 v K41 v K50 v K61 v K1210 v K1310 v K1411 v K1510 v K1611 v K2300 v K2401 v K2500 v K2601 v K3401 v K3500 v K3601 v K4510 v K4611 v K5601 v K123100 v K124101 v K125100 v K126101 v K134101 v K135100 v K136101 v K145110 v K146111 v K156101 v K234001 v K235000 v K236001 v K245010 v K246011 v K256001 v K345010 v K346011 v K356001 v K456101 v K12341001 v K12351000 v K12361001 v K12451010 v K12461011 v K12561001 v K13451010 v K13461011 v K13561001 v K14561101 v K23450010 v K23460011 v K23560001 v K24560101 v K34560101 v K1234510010 v K1234610011 v K1235610001 v K1245610101 v K1345610101 v K2345600101 v K123456100101 = 1


K10 v K21 v K30 v K41 v K50 v K61 v K1201 v K1300 v K1401 v K1500 v K1601 v K2310 v K2411 v K2510 v K2611 v K3401 v K3500 v K3601 v K4510 v K4611 v K5601 v K123010 v K124011 v K125010 v K126011 v K134001 v K135000 v K136001 v K145010 v K146011 v K156001 v K234101 v K235100 v K236101 v K245110 v K246111 v K256101 v K345010 v K346011 v K356001 v K456101 v K12340101 v K12350100 v K12360101 v K12450110 v K12460111 v K12560101 v K13450010 v K13460011 v K13560001 v K14560101 v K23451010 v K23461011 v K23561001 v K24561101 v K34560101 v K1234501010 v K1234601011 v K1235601001 v K1245601101 v K1345600101 v K2345610101 v K123456010101 = 0


K11 v K21 v K30 v K41 v K50 v K61 v K1211 v K1310 v K1411 v K1510 v K1611 v K2310 v K2411 v K2510 v K2611 v K3401 v K3500 v K3601 v K4510 v K4611 v K5601 v K123110 v K124111 v K125110 v K126111 v K134101 v K135100 v K136101 v K145110 v K146111 v K156101 v K234101 v K235100 v K236101 v K245110 v K246111 v K256101 v K345010 v K346011 v K356001 v K456101 v K12341101 v K12351100 v K12361101 v K12451110 v K12461111 v K12561101 v K13451010 v K13461011 v K13561001 v K14561101 v K23451010 v K23461011 v K23561001 v K24561101 v K34560101 v K1234511010 v K1234611011 v K1235611001 v K1245611101 v K1345610101 v K2345610101 v K123456110101 = 1


K10 v K20 v K31 v K41 v K50 v K61 v K1200 v K1301 v K1401 v K1500 v K1601 v K2301 v K2401 v K2500 v K2601 v K3411 v K3510 v K3611 v K4510 v K4611 v K5601 v K123001 v K124001 v K125000 v K126001 v K134011 v K135010 v K136011 v K145010 v K146011 v K156001 v K234011 v K235010 v K236011 v K245010 v K246011 v K256001 v K345110 v K346111 v K356101 v K456101 v K12340011 v K12350010 v K12360011 v K12450010 v K12460011 v K12560001 v K13450110 v K13460111 v K13560101 v K14560101 v K23450110 v K23460111 v K23560101 v K24560101 v K34561101 v K1234500110 v K1234600111 v K1235600101 v K1245600101 v K1345601101 v K2345601101 v K123456001101 = 0


K11 v K20 v K31 v K41 v K50 v K61 v K1210 v K1311 v K1411 v K1510 v K1611 v K2301 v K2401 v K2500 v K2601 v K3411 v K3510 v K3611 v K4510 v K4611 v K5601 v K123101 v K124101 v K125100 v K126101 v K134111 v K135110 v K136111 v K145110 v K146111 v K156101 v K234011 v K235010 v K236011 v K245010 v K246011 v K256001 v K345110 v K346111 v K356101 v K456101 v K12341011 v K12351010 v K12361011 v K12451010 v K12461011 v K12561001 v K13451110 v K13461111 v K13561101 v K14561101 v K23450110 v K23460111 v K23560101 v K24560101 v K34561101 v K1234510110 v K1234610111 v K1235610101 v K1245610101 v K1345611101 v K2345601101 v K123456101101 = 1


K10 v K21 v K31 v K41 v K50 v K61 v K1201 v K1301 v K1401 v K1500 v K1601 v K2311 v K2411 v K2510 v K2611 v K3411 v K3510 v K3611 v K4510 v K4611 v K5601 v K123011 v K124011 v K125010 v K126011 v K134011 v K135010 v K136011 v K145010 v K146011 v K156001 v K234111 v K235110 v K236111 v K245110 v K246111 v K256101 v K345110 v K346111 v K356101 v K456101 v K12340111 v K12350110 v K12360111 v K12450110 v K12460111 v K12560101 v K13450110 v K13460111 v K13560101 v K14560101 v K23451110 v K23461111 v K23561101 v K24561101 v K34561101 v K1234501110 v K1234601111 v K1235601101 v K1245601101 v K1345601101 v K2345611101 v K123456011101 = 1


K11 v K21 v K31 v K41 v K50 v K61 v K1211 v K1311 v K1411 v K1510 v K1611 v K2311 v K2411 v K2510 v K2611 v K3411 v K3510 v K3611 v K4510 v K4611 v K5601 v K123111 v K124111 v K125110 v K126111 v K134111 v K135110 v K136111 v K145110 v K146111 v K156101 v K234111 v K235110 v K236111 v K245110 v K246111 v K256101 v K345110 v K346111 v K356101 v K456101 v K12341111 v K12351110 v K12361111 v K12451110 v K12461111 v K12561101 v K13451110 v K13461111 v K13561101 v K14561101 v K23451110 v K23461111 v K23561101 v K24561101 v K34561101 v K1234511110 v K1234611111 v K1235611101 v K1245611101 v K1345611101 v K2345611101 v K123456111101 = 1


K10 v K20 v K30 v K40 v K51 v K61 v K1200 v K1300 v K1400 v K1501 v K1601 v K2300 v K2400 v K2501 v K2601 v K3400 v K3501 v K3601 v K4501 v K4601 v K5611 v K123000 v K124000 v K125001 v K126001 v K134000 v K135001 v K136001 v K145001 v K146001 v K156011 v K234000 v K235001 v K236001 v K245001 v K246001 v K256011 v K345001 v K346001 v K356011 v K456011 v K12340000 v K12350001 v K12360001 v K12450001 v K12460001 v K12560011 v K13450001 v K13460001 v K13560011 v K14560011 v K23450001 v K23460001 v K23560011 v K24560011 v K34560011 v K1234500001 v K1234600001 v K1235600011 v K1245600011 v K1345600011 v K2345600011 v K123456000011 = 0


K11 v K20 v K30 v K40 v K51 v K61 v K1210 v K1310 v K1410 v K1511 v K1611 v K2300 v K2400 v K2501 v K2601 v K3400 v K3501 v K3601 v K4501 v K4601 v K5611 v K123100 v K124100 v K125101 v K126101 v K134100 v K135101 v K136101 v K145101 v K146101 v K156111 v K234000 v K235001 v K236001 v K245001 v K246001 v K256011 v K345001 v K346001 v K356011 v K456011 v K12341000 v K12351001 v K12361001 v K12451001 v K12461001 v K12561011 v K13451001 v K13461001 v K13561011 v K14561011 v K23450001 v K23460001 v K23560011 v K24560011 v K34560011 v K1234510001 v K1234610001 v K1235610011 v K1245610011 v K1345610011 v K2345600011 v K123456100011 = 1


K10 v K21 v K30 v K40 v K51 v K61 v K1201 v K1300 v K1400 v K1501 v K1601 v K2310 v K2410 v K2511 v K2611 v K3400 v K3501 v K3601 v K4501 v K4601 v K5611 v K123010 v K124010 v K125011 v K126011 v K134000 v K135001 v K136001 v K145001 v K146001 v K156011 v K234100 v K235101 v K236101 v K245101 v K246101 v K256111 v K345001 v K346001 v K356011 v K456011 v K12340100 v K12350101 v K12360101 v K12450101 v K12460101 v K12560111 v K13450001 v K13460001 v K13560011 v K14560011 v K23451001 v K23461001 v K23561011 v K24561011 v K34560011 v K1234501001 v K1234601001 v K1235601011 v K1245601011 v K1345600011 v K2345610011 v K123456010011 = 1


K11 v K21 v K30 v K40 v K51 v K61 v K1211 v K1310 v K1410 v K1511 v K1611 v K2310 v K2410 v K2511 v K2611 v K3400 v K3501 v K3601 v K4501 v K4601 v K5611 v K123110 v K124110 v K125111 v K126111 v K134100 v K135101 v K136101 v K145101 v K146101 v K156111 v K234100 v K235101 v K236101 v K245101 v K246101 v K256111 v K345001 v K346001 v K356011 v K456011 v K12341100 v K12351101 v K12361101 v K12451101 v K12461101 v K12561111 v K13451001 v K13461001 v K13561011 v K14561011 v K23451001 v K23461001 v K23561011 v K24561011 v K34560011 v K1234511001 v K1234611001 v K1235611011 v K1245611011 v K1345610011 v K2345610011 v K123456110011 = 1


K10 v K20 v K31 v K40 v K51 v K61 v K1200 v K1301 v K1400 v K1501 v K1601 v K2301 v K2400 v K2501 v K2601 v K3410 v K3511 v K3611 v K4501 v K4601 v K5611 v K123001 v K124000 v K125001 v K126001 v K134010 v K135011 v K136011 v K145001 v K146001 v K156011 v K234010 v K235011 v K236011 v K245001 v K246001 v K256011 v K345101 v K346101 v K356111 v K456011 v K12340010 v K12350011 v K12360011 v K12450001 v K12460001 v K12560011 v K13450101 v K13460101 v K13560111 v K14560011 v K23450101 v K23460101 v K23560111 v K24560011 v K34561011 v K1234500101 v K1234600101 v K1235600111 v K1245600011 v K1345601011 v K2345601011 v K123456001011 = 1


K11 v K20 v K31 v K40 v K51 v K61 v K1210 v K1311 v K1410 v K1511 v K1611 v K2301 v K2400 v K2501 v K2601 v K3410 v K3511 v K3611 v K4501 v K4601 v K5611 v K123101 v K124100 v K125101 v K126101 v K134110 v K135111 v K136111 v K145101 v K146101 v K156111 v K234010 v K235011 v K236011 v K245001 v K246001 v K256011 v K345101 v K346101 v K356111 v K456011 v K12341010 v K12351011 v K12361011 v K12451001 v K12461001 v K12561011 v K13451101 v K13461101 v K13561111 v K14561011 v K23450101 v K23460101 v K23560111 v K24560011 v K34561011 v K1234510101 v K1234610101 v K1235610111 v K1245610011 v K1345611011 v K2345601011 v K123456101011 = 1


K10 v K21 v K31 v K40 v K51 v K61 v K1201 v K1301 v K1400 v K1501 v K1601 v K2311 v K2410 v K2511 v K2611 v K3410 v K3511 v K3611 v K4501 v K4601 v K5611 v K123011 v K124010 v K125011 v K126011 v K134010 v K135011 v K136011 v K145001 v K146001 v K156011 v K234110 v K235111 v K236111 v K245101 v K246101 v K256111 v K345101 v K346101 v K356111 v K456011 v K12340110 v K12350111 v K12360111 v K12450101 v K12460101 v K12560111 v K13450101 v K13460101 v K13560111 v K14560011 v K23451101 v K23461101 v K23561111 v K24561011 v K34561011 v K1234501101 v K1234601101 v K1235601111 v K1245601011 v K1345601011 v K2345611011 v K123456011011 = 1


K11 v K21 v K31 v K40 v K51 v K61 v K1211 v K1311 v K1410 v K1511 v K1611 v K2311 v K2410 v K2511 v K2611 v K3410 v K3511 v K3611 v K4501 v K4601 v K5611 v K123111 v K124110 v K125111 v K126111 v K134110 v K135111 v K136111 v K145101 v K146101 v K156111 v K234110 v K235111 v K236111 v K245101 v K246101 v K256111 v K345101 v K346101 v K356111 v K456011 v K12341110 v K12351111 v K12361111 v K12451101 v K12461101 v K12561111 v K13451101 v K13461101 v K13561111 v K14561011 v K23451101 v K23461101 v K23561111 v K24561011 v K34561011 v K1234511101 v K1234611101 v K1235611111 v K1245611011 v K1345611011 v K2345611011 v K123456111011 = 1


K10 v K20 v K30 v K41 v K51 v K61 v K1200 v K1300 v K1401 v K1501 v K1601 v K2300 v K2401 v K2501 v K2601 v K3401 v K3501 v K3601 v K4511 v K4611 v K5611 v K123000 v K124001 v K125001 v K126001 v K134001 v K135001 v K136001 v K145011 v K146011 v K156011 v K234001 v K235001 v K236001 v K245011 v K246011 v K256011 v K345011 v K346011 v K356011 v K456111 v K12340001 v K12350001 v K12360001 v K12450011 v K12460011 v K12560011 v K13450011 v K13460011 v K13560011 v K14560111 v K23450011 v K23460011 v K23560011 v K24560111 v K34560111 v K1234500011 v K1234600011 v K1235600011 v K1245600111 v K1345600111 v K2345600111 v K123456000111 = 1


K11 v K20 v K30 v K41 v K51 v K61 v K1210 v K1310 v K1411 v K1511 v K1611 v K2300 v K2401 v K2501 v K2601 v K3401 v K3501 v K3601 v K4511 v K4611 v K5611 v K123100 v K124101 v K125101 v K126101 v K134101 v K135101 v K136101 v K145111 v K146111 v K156111 v K234001 v K235001 v K236001 v K245011 v K246011 v K256011 v K345011 v K346011 v K356011 v K456111 v K12341001 v K12351001 v K12361001 v K12451011 v K12461011 v K12561011 v K13451011 v K13461011 v K13561011 v K14561111 v K23450011 v K23460011 v K23560011 v K24560111 v K34560111 v K1234510011 v K1234610011 v K1235610011 v K1245610111 v K1345610111 v K2345600111 v K123456100111 = 1


K10 v K21 v K30 v K41 v K51 v K61 v K1201 v K1300 v K1401 v K1501 v K1601 v K2310 v K2411 v K2511 v K2611 v K3401 v K3501 v K3601 v K4511 v K4611 v K5611 v K123010 v K124011 v K125011 v K126011 v K134001 v K135001 v K136001 v K145011 v K146011 v K156011 v K234101 v K235101 v K236101 v K245111 v K246111 v K256111 v K345011 v K346011 v K356011 v K456111 v K12340101 v K12350101 v K12360101 v K12450111 v K12460111 v K12560111 v K13450011 v K13460011 v K13560011 v K14560111 v K23451011 v K23461011 v K23561011 v K24561111 v K34560111 v K1234501011 v K1234601011 v K1235601011 v K1245601111 v K1345600111 v K2345610111 v K123456010111 = 1


K11 v K21 v K30 v K41 v K51 v K61 v K1211 v K1310 v K1411 v K1511 v K1611 v K2310 v K2411 v K2511 v K2611 v K3401 v K3501 v K3601 v K4511 v K4611 v K5611 v K123110 v K124111 v K125111 v K126111 v K134101 v K135101 v K136101 v K145111 v K146111 v K156111 v K234101 v K235101 v K236101 v K245111 v K246111 v K256111 v K345011 v K346011 v K356011 v K456111 v K12341101 v K12351101 v K12361101 v K12451111 v K12461111 v K12561111 v K13451011 v K13461011 v K13561011 v K14561111 v K23451011 v K23461011 v K23561011 v K24561111 v K34560111 v K1234511011 v K1234611011 v K1235611011 v K1245611111 v K1345610111 v K2345610111 v K123456110111 = 1


K10 v K20 v K31 v K41 v K51 v K61 v K1200 v K1301 v K1401 v K1501 v K1601 v K2301 v K2401 v K2501 v K2601 v K3411 v K3511 v K3611 v K4511 v K4611 v K5611 v K123001 v K124001 v K125001 v K126001 v K134011 v K135011 v K136011 v K145011 v K146011 v K156011 v K234011 v K235011 v K236011 v K245011 v K246011 v K256011 v K345111 v K346111 v K356111 v K456111 v K12340011 v K12350011 v K12360011 v K12450011 v K12460011 v K12560011 v K13450111 v K13460111 v K13560111 v K14560111 v K23450111 v K23460111 v K23560111 v K24560111 v K34561111 v K1234500111 v K1234600111 v K1235600111 v K1245600111 v K1345601111 v K2345601111 v K123456001111 = 1


K11 v K20 v K31 v K41 v K51 v K61 v K1210 v K1311 v K1411 v K1511 v K1611 v K2301 v K2401 v K2501 v K2601 v K3411 v K3511 v K3611 v K4511 v K4611 v K5611 v K123101 v K124101 v K125101 v K126101 v K134111 v K135111 v K136111 v K145111 v K146111 v K156111 v K234011 v K235011 v K236011 v K245011 v K246011 v K256011 v K345111 v K346111 v K356111 v K456111 v K12341011 v K12351011 v K12361011 v K12451011 v K12461011 v K12561011 v K13451111 v K13461111 v K13561111 v K14561111 v K23450111 v K23460111 v K23560111 v K24560111 v K34561111 v K1234510111 v K1234610111 v K1235610111 v K1245610111 v K1345611111 v K2345601111 v K123456101111 = 0


K10 v K21 v K31 v K41 v K51 v K61 v K1201 v K1301 v K1401 v K1501 v K1601 v K2311 v K2411 v K2511 v K2611 v K3411 v K3511 v K3611 v K4511 v K4611 v K5611 v K123011 v K124011 v K125011 v K126011 v K134011 v K135011 v K136011 v K145011 v K146011 v K156011 v K234111 v K235111 v K236111 v K245111 v K246111 v K256111 v K345111 v K346111 v K356111 v K456111 v K12340111 v K12350111 v K12360111 v K12450111 v K12460111 v K12560111 v K13450111 v K13460111 v K13560111 v K14560111 v K23451111 v K23461111 v K23561111 v K24561111 v K34561111 v K1234501111 v K1234601111 v K1235601111 v K1245601111 v K1345601111 v K2345611111 v K123456011111 = 0


K11 v K21 v K31 v K41 v K51 v K61 v K1211 v K1311 v K1411 v K1511 v K1611 v K2311 v K2411 v K2511 v K2611 v K3411 v K3511 v K3611 v K4511 v K4611 v K5611 v K123111 v K124111 v K125111 v K126111 v K134111 v K135111 v K136111 v K145111 v K146111 v K156111 v K234111 v K235111 v K236111 v K245111 v K246111 v K256111 v K345111 v K346111 v K356111 v K456111 v K12341111 v K12351111 v K12361111 v K12451111 v K12461111 v K12561111 v K13451111 v K13461111 v K13561111 v K14561111 v K23451111 v K23461111 v K23561111 v K24561111 v K34561111 v K1234511111 v K1234611111 v K1235611111 v K1245611111 v K1345611111 v K2345611111 v K123456111111 = 0


Шаг 2. Избавляемся от нулевых коэффициентов

K123456000000 = 1


K134101 v K145110 v K146110 v K12341001 v K12451010 v K12461010 v K13451010 v K13461010 v K14561100 v K1234510010 v K1234610010 v K1245610100 v K1345610100 v K123456100100 = 1


K134101 v K145110 v K146110 v K12341101 v K12451110 v K12461110 v K13451010 v K13461010 v K14561100 v K1234511010 v K1234611010 v K1245611100 v K1345610100 v K123456110100 = 1


K145110 v K146110 v K12451010 v K12461010 v K13451110 v K13461110 v K14561100 v K1234510110 v K1234610110 v K1245610100 v K1345611100 v K123456101100 = 1


K23451110 v K1234501110 v K2345611100 v K123456011100 = 1


K145110 v K146110 v K12451110 v K12461110 v K13451110 v K13461110 v K14561100 v K23451110 v K1234511110 v K1234611110 v K1245611100 v K1345611100 v K2345611100 v K123456111100 = 1


K135101 v K145101 v K156110 v K12351001 v K12451001 v K12561010 v K13451001 v K13561010 v K14561010 v K1234510001 v K1235610010 v K1245610010 v K1345610010 v K123456100010 = 1


K245101 v K12450101 v K23451001 v K24561010 v K1234501001 v K1245601010 v K2345610010 v K123456010010 = 1


K135101 v K145101 v K156110 v K245101 v K12351101 v K12451101 v K12561110 v K13451001 v K13561010 v K14561010 v K23451001 v K24561010 v K1234511001 v K1235611010 v K1245611010 v K1345610010 v K2345610010 v K123456110010 = 1


K145101 v K156110 v K12451001 v K12561010 v K13451101 v K13561110 v K14561010 v K1234510101 v K1235610110 v K1245610010 v K1345611010 v K123456101010 = 1


K245101 v K12450101 v K23451101 v K24561010 v K1234501101 v K1245601010 v K2345611010 v K123456011010 = 1


K145101 v K156110 v K245101 v K12451101 v K12561110 v K13451101 v K13561110 v K14561010 v K23451101 v K24561010 v K1234511101 v K1235611110 v K1245611010 v K1345611010 v K2345611010 v K123456111010 = 1


K12450011 v K23450011 v K24560110 v K1234500011 v K1245600110 v K2345600110 v K123456000110 = 1


K134101 v K135101 v K146110 v K156110 v K12341001 v K12351001 v K12461010 v K12561010 v K13451011 v K13461010 v K13561010 v K14561110 v K23450011 v K24560110 v K1234510011 v K1234610010 v K1235610010 v K1245610110 v K1345610110 v K2345600110 v K123456100110 = 1


K134101 v K135101 v K146110 v K156110 v K12341101 v K12351101 v K12461110 v K12561110 v K13451011 v K13461010 v K13561010 v K14561110 v K1234511011 v K1234611010 v K1235611010 v K1245611110 v K1345610110 v K123456110110 = 1


K12450011 v K24560110 v K1234500111 v K1245600110 v K2345601110 v K123456001110 = 1


K146110 v K156110 v K12461010 v K12561010 v K13461110 v K13561110 v K14561110 v K24560110 v K1234610110 v K1235610110 v K1245610110 v K1345611110 v K2345601110 v K123456101110 = 1


K146110 v K156110 v K12461110 v K12561110 v K13461110 v K13561110 v K14561110 v K1234611110 v K1235611110 v K1245611110 v K1345611110 v K123456111110 = 1


K12361101 v K12461101 v K12561101 v K1234611001 v K1235611001 v K1245611001 v K123456110001 = 1


K23461101 v K23561101 v K1234601101 v K1235601101 v K2345611001 v K123456011001 = 1


K12461101 v K12561101 v K23461101 v K23561101 v K1234611101 v K1235611101 v K1245611001 v K2345611001 v K123456111001 = 1


K134101 v K145110 v K12341001 v K12451010 v K13451010 v K13461011 v K14561101 v K1234510010 v K1234610011 v K1245610101 v K1345610101 v K123456100101 = 1


K134101 v K145110 v K12341101 v K12361101 v K12451110 v K12561101 v K13451010 v K13461011 v K14561101 v K1234511010 v K1234611011 v K1235611001 v K1245611101 v K1345610101 v K123456110101 = 1


K145110 v K12451010 v K13451110 v K14561101 v K1234510110 v K1245610101 v K1345611101 v K123456101101 = 1


K23451110 v K23561101 v K1234501110 v K1235601101 v K2345611101 v K123456011101 = 1


K145110 v K12451110 v K12561101 v K13451110 v K14561101 v K23451110 v K23561101 v K1234511110 v K1235611101 v K1245611101 v K1345611101 v K2345611101 v K123456111101 = 1


K135101 v K145101 v K12351001 v K12451001 v K13451001 v K13561011 v K14561011 v K1234510001 v K1235610011 v K1245610011 v K1345610011 v K123456100011 = 1


K245101 v K12450101 v K23451001 v K23561011 v K24561011 v K1234501001 v K1235601011 v K1245601011 v K2345610011 v K123456010011 = 1


K135101 v K145101 v K245101 v K12351101 v K12361101 v K12451101 v K12461101 v K13451001 v K13561011 v K14561011 v K23451001 v K23561011 v K24561011 v K1234511001 v K1234611001 v K1235611011 v K1245611011 v K1345610011 v K2345610011 v K123456110011 = 1


K34561011 v K1235600111 v K1345601011 v K2345601011 v K123456001011 = 1


K145101 v K12451001 v K13451101 v K14561011 v K34561011 v K1234510101 v K1245610011 v K1345611011 v K2345601011 v K123456101011 = 1


K245101 v K12450101 v K23451101 v K23461101 v K24561011 v K34561011 v K1234501101 v K1234601101 v K1245601011 v K1345601011 v K2345611011 v K123456011011 = 1


K145101 v K245101 v K12451101 v K12461101 v K13451101 v K14561011 v K23451101 v K23461101 v K24561011 v K34561011 v K1234511101 v K1234611101 v K1245611011 v K1345611011 v K2345611011 v K123456111011 = 1


K12450011 v K23450011 v K34560111 v K1234500011 v K1245600111 v K1345600111 v K2345600111 v K123456000111 = 1


K134101 v K135101 v K12341001 v K12351001 v K13451011 v K13461011 v K13561011 v K23450011 v K34560111 v K1234510011 v K1234610011 v K1235610011 v K1345610111 v K2345600111 v K123456100111 = 1


K23561011 v K34560111 v K1235601011 v K1345600111 v K2345610111 v K123456010111 = 1


K134101 v K135101 v K12341101 v K12351101 v K12361101 v K13451011 v K13461011 v K13561011 v K23561011 v K34560111 v K1234511011 v K1234611011 v K1235611011 v K1345610111 v K2345610111 v K123456110111 = 1


K12450011 v K1234500111 v K1235600111 v K1245600111 v K123456001111 = 1


Шаг 3. Ищем часто встречающиеся термы минимального ранга

K123456000000 = 1


K23451110 = 1


K34561011 = 1


K12450011 = 1


K245101 = 1


K245101 = 1


K145110 = 1


K245101 = 1


K145101 = 1


K245101 = 1


K145110 = 1


K12450011 v K24560110 = 1


K23461101 v K23561101 = 1


K23451110 v K23561101 = 1


K23561011 v K34560111 = 1


K145110 v K146110 = 1


K145101 v K156110 = 1


K146110 v K156110 = 1


K134101 v K145110 = 1


K135101 v K145101 = 1


K145110 v K146110 = 1


K146110 v K156110 = 1


K134101 v K145110 = 1


K134101 v K135101 = 1


K145101 v K245101 = 1


K134101 v K135101 = 1


K12450011 v K23450011 v K24560110 = 1


K12361101 v K12461101 v K12561101 = 1


K12450011 v K23450011 v K34560111 = 1


K134101 v K145110 v K146110 = 1


K134101 v K145110 v K146110 = 1


K135101 v K145101 v K156110 = 1


K145101 v K156110 v K245101 = 1


K135101 v K145101 v K245101 = 1


K12461101 v K12561101 v K23461101 v K23561101 = 1


K135101 v K145101 v K156110 v K245101 = 1


K134101 v K135101 v K146110 v K156110 = 1


K134101 v K135101 v K146110 v K156110 = 1


Шаг 4. Избавляемся от повторов

K123456000000 = 1


K23451110 = 1


K34561011 = 1


K12450011 = 1


K245101 = 1


K145110 = 1


K23561101 = 1


K34560111 = 1


K145101 = 1


K146110 = 1


K12461101 = 1


Ответ

Для упрощения выполнения работы рекомендуется воспользоваться следующими ресурсами: Карно-Вейч[1], Квайн - Мак-Класки[2]

Вариант 2

Таблица истинности исходной функции:

Рис. 2. Таблица истинности исходной функции

Минимизация табличным методом (Карты Карно)

На рис. 3 изображена карта Карно для исходной функции с обведенными склейками:

Рис. 3. Карта Карно исходной функции

Получаем следующую ДНФ:

Минимизация методом Квайна - Мак-Класки

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

На рис. 4 изображена таблица склейки:

Рис. 4. Таблица склейки
Рис. 5. Таблица покрытия

Получаем следующую ДНФ:

Минимизация методом неопределённых коэффициентов

Шаг 1. Избавляемся от нулевых коэффициентов

K135000 v K12340000 v K12350000 v K13450000 v K1234500000 = 1


K135000 v K12350100 v K12450100 v K13450000 v K1234501000 = 1


K13451100 v K1234510100 = 1


K12450100 v K23451100 v K1234501100 = 1


K12341110 v K13451100 v K23451100 v K1234511100 = 1


K135000 v K12350000 v K13450010 v K1234500010 = 1


K135000 v K12350100 v K13450010 v K1234501010 = 1


K12340000 v K12450001 v K1234500001 = 1


K125111 v K12351101 v K12451101 v K1234511001 = 1


K12450001 v K1234500101 = 1


K125111 v K12341110 v K12351111 v K12451101 v K1234511101 = 1


K125111 v K12351101 v K12451111 v K1234511011 = 1


K125111 v K12351111 v K12451111 v K1234511111 = 1


Шаг 2. Сортируем уравнения по возрастанию

K13451100 v K1234510100 = 1


K12450001 v K1234500101 = 1


K12450100 v K23451100 v K1234501100 = 1


K12340000 v K12450001 v K1234500001 = 1


K12341110 v K13451100 v K23451100 v K1234511100 = 1


K135000 v K12350000 v K13450010 v K1234500010 = 1


K135000 v K12350100 v K13450010 v K1234501010 = 1


K125111 v K12351101 v K12451101 v K1234511001 = 1


K125111 v K12351101 v K12451111 v K1234511011 = 1


K125111 v K12351111 v K12451111 v K1234511111 = 1


K135000 v K12340000 v K12350000 v K13450000 v K1234500000 = 1


K135000 v K12350100 v K12450100 v K13450000 v K1234501000 = 1


K125111 v K12341110 v K12351111 v K12451101 v K1234511101 = 1

Шаг 3. Ищем часто встречающиеся термы минимального ранга

K13451100 = 1


K12450001 = 1


K135000 = 1


K135000 = 1


K125111 = 1


K125111 = 1


K125111 = 1


K135000 = 1


K135000 = 1


K125111 = 1


K12450100 v K23451100 = 1


K12340000 v K12450001 = 1


K12341110 v K13451100 v K23451100 = 1

Шаг 4. Избавляемся от повторов

K135000 = 1


K12451000 = 1


K12351100 = 1


K12341100 = 1


K145111 = 1


Получаем следующую ДНФ:

Реализация метода карт Карно и метода Квайна - Мак-Класки на JS

Карты Карно:

// Copyright (C) Thorsten Thormaehlen, Marburg, 2013, All rights reserved
// Contact: www.thormae.de

// This software is written for educational (non-commercial) purpose. 
// There is no warranty or other guarantee of fitness for this software, 
// it is provided solely "as is". 

function UIElement(x, y, width, height, type, ref, subref, slotType) {
  this.x = x;
  this.y = y;
  this.x2 = x + width;
  this.y2 = y + height;
  this.type = type; // 0 = field, 1 = slot, 2 connection
  this.ref = ref;
}

function KVField() {
  this.position = [0.0, 0.0];
  this.value = 0;
  this.active = false;
  this.uniqueID = -1;
  this.truthmapID = -1;
}

function KVBlock() {
  this.fieldID = -1;
  this.dimx = -1;
  this.dimy = -1;
  this.used = false;
  this.color = [0, 0, 0];
  this.primTerm = "";
}

function KarnaughMapDataCtrl(qmcRef) {
  this.noOfVars = -1;
  this.fieldLines = -1;
  this.fieldPerLine = -1;
  this.fieldBorder = -1;
  this.fieldHeight = 40;
  this.fieldWidth = 40;
  this.qmc = qmcRef;
  this.fields = new Array();
  this.blocks = new Array();
  this.allowDontCare = false;

  this.init = function (no) {

    this.noOfVars = no;

    this.qmc.setNoOfVars(no);

    var noOfEvenVars = Math.floor(this.noOfVars / 2);
    var noOfOddVars = Math.floor((this.noOfVars + 1) / 2);

    this.fieldLines = Math.pow(2, noOfEvenVars);
    this.fieldPerLine = Math.pow(2, noOfOddVars);
    this.fieldBorder = noOfOddVars * 20;

    this.fields.length = 0;
    this.blocks.length = 0;

    var id = 0;
    for (var i = 0; i < this.fieldLines; i++) {
      for (var j = 0; j < this.fieldPerLine; j++) {
        var field = new KVField();
        field.position[0] = this.fieldBorder + j * this.fieldWidth;
        field.position[1] = this.fieldBorder + i * this.fieldHeight;
        field.value = 0;
        field.uniqueID = id;
        this.fields.push(field);
        id++;
      }
    }

    var mapped = 0;
    this.fields[0].truthmapID = 0;
    this.fields[1].truthmapID = 1;
    var mirrorDirection = 0;
    var mirrorXCount = 2;
    var mirrorYCount = 1;
    var mapped = 2;
    var x = 0;
    var y = 1;
    var loop = 0;
    var direction = 0;
    while (loop < this.noOfVars - 1) {
      for (var xx = 0; xx < mirrorXCount; xx++) {
        for (var yy = 0; yy < mirrorYCount; yy++) {
          var loc = xx + yy * this.fieldPerLine;

          if (direction === 0) {
            var mirrorLoc = (x + xx) + (y + (mirrorYCount - 1) - yy) * this.fieldPerLine;
            this.fields[mirrorLoc].truthmapID = this.fields[loc].truthmapID + mirrorXCount * mirrorYCount;
          } else {
            var mirrorLoc = (x + (mirrorXCount - 1) - xx) + (y + yy) * this.fieldPerLine;
            this.fields[mirrorLoc].truthmapID = this.fields[loc].truthmapID + mirrorYCount * mirrorYCount;
          }
        }
      }
      if (direction === 0) {
        mirrorYCount = mirrorYCount * 2;
        x = mirrorXCount;
        y = 0;
        direction = 1;
      } else {
        mirrorXCount = mirrorXCount * 2;
        y = mirrorYCount;
        x = 0;
        direction = 0;
      }
      loop++;
    }

  };

  this.getKVFieldsCount = function () {
    return this.fields.length;
  };

  this.getKVFieldPositionX = function (fieldId) {
    return this.fields[fieldId].position[0];
  };

  this.getKVFieldPositionY = function (fieldId) {
    return this.fields[fieldId].position[1];
  };

  this.getKVFieldTruthmapID = function (fieldId) {
    return this.fields[fieldId].truthmapID;
  };

  this.getKVFieldValue = function (fieldId) {
    return this.fields[fieldId].value;
  };

  this.activated = function (fieldId) {

    this.fields[fieldId].value += 1;
    if (this.allowDontCare) {
      if (this.fields[fieldId].value > 2)
        this.fields[fieldId].value = 0;
    } else {
      if (this.fields[fieldId].value > 1)
        this.fields[fieldId].value = 0;
    }

    this.qmc.data.setFuncData(this.fields[fieldId].truthmapID, this.fields[fieldId].value);
    this.qmc.data.compute();
    this.qmc.update();
    this.compute();
  };

  this.random = function () {
    for (var i in this.fields) {
      if (this.allowDontCare) {
        this.fields[i].value = Math.floor(Math.random() * 3);
      } else {
        this.fields[i].value = Math.floor(Math.random() * 2);
      }
      this.qmc.data.setFuncData(this.fields[i].truthmapID, this.fields[i].value);
    }
    this.qmc.data.compute();
    this.qmc.update();
    this.compute();
  };

  this.clear = function () {
    for (var i in this.fields) {
      this.fields[i].value = 0;
      this.qmc.data.setFuncData(this.fields[i].truthmapID, this.fields[i].value);
    }
    this.qmc.data.compute();
    this.qmc.update();
    this.compute();
  };

  this.compute = function () {

    this.blocks.length = 0;

    var localFieldsValues = new Array();

    for (var m = 0; m < this.qmc.data.minimalTermPrims.length; m++) {
      var minPrim = this.qmc.data.minimalTermPrims[m];

      localFieldsValues.length = 0;
      for (var i in this.fields) {
        if (this.fields[i].truthmapID in minPrim.implicant.imp) {
          localFieldsValues.push(1);
        } else {
          localFieldsValues.push(0);
        }
      }

      var maxX = Math.floor(Math.log(this.fieldPerLine) / Math.LN2);
      var maxY = Math.floor(Math.log(this.fieldLines) / Math.LN2);

      // this might be computationally expensive (computing all possible blocks)
      for (var x = maxX; x >= 0; x--) {
        for (var y = maxY; y >= 0; y--) {
          var px = Math.pow(2, x);
          var py = Math.pow(2, y);
          var stepI = Math.max(Math.floor(py / 2), 1);
          var stepJ = Math.max(Math.floor(px / 2), 1);
          for (var i = 0; i < this.fieldLines; i += stepI) {
            for (var j = 0; j < this.fieldPerLine; j += stepJ) {

              var id = i * this.fieldPerLine + j;

              if (localFieldsValues[id] === 1) {

                // search zero
                var noZero = true;
                for (var xx = 0; xx < px && noZero; xx++) {
                  for (var yy = 0; yy < py && noZero; yy++) {
                    var otherId = ((i + yy) % this.fieldLines) * this.fieldPerLine + ((j + xx) % this.fieldPerLine);
                    if (localFieldsValues[otherId] === 0)
                      noZero = false;
                  }
                }

                if (noZero) {
                  var block = new KVBlock();
                  block.fieldID = id;
                  block.dimx = px;
                  block.dimy = py;
                  block.color = minPrim.color;
                  this.blocks.push(block);
                  if (true) { //clearing all 1s
                    for (var xx = 0; xx < px; xx++) {
                      for (var yy = 0; yy < py; yy++) {
                        var otherId = ((i + yy) % this.fieldLines) * this.fieldPerLine + ((j + xx) % this.fieldPerLine);
                        localFieldsValues[otherId] = 0;
                      }
                    }
                  }

                } // end if(noZero)
              } // end if (localFieldsValues[id] === 1)
            } // end j
          } // end i
        } // end y
      } // end x
    } // end m
  };
}

function KarnaughMap(parentDivId, qmcRef) {
  var data = new KarnaughMapDataCtrl(qmcRef);
  var qmc = qmcRef;
  var svg;
  var svgns = "http://www.w3.org/2000/svg";
  var divId = parentDivId;
  var fieldColor = "rgba(133, 178, 255, 1.0)";
  var hooveredKVFieldColor = "#AAD7FF";
  var hooveredElement = -1;
  var hooveredKVField = -1;
  var uiElements = new Array();
  var that = this;
  var overlays = new Array();
  var overlayStyle = 'position:absolute; font-family:"Times New Roman",Georgia,Serif; visibility:inherit;';
  var overlayStyle2 = overlayStyle + 'border: 1px solid gray; background:white; pointer-events:none;';
  var resultStyle = 'position:inline; font-family:"Times New Roman",Georgia,Serif; visibility:inherit;';
  var dontShowResult = false;
    
  this.init = function () {

    data.init(4);

    var width = data.fieldBorder + data.fieldPerLine * data.fieldWidth + 50;
    var height = data.fieldBorder + data.fieldLines * data.fieldHeight + 50;

    svg = document.createElementNS(svgns, "svg");
    if (!svg)
      console.log("KarnaughMap error: can not create a svg element");
    //svg.setAttribute('style', 'border: 1px solid black');
    svg.setAttribute('width', width.toString());
    svg.setAttribute('height', height.toString());
    svg.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:xlink", "http://www.w3.org/1999/xlink");
    svg.setAttribute('id', parentDivId + "_KarnaughMap");
    document.body.appendChild(svg);

    var parent = document.getElementById(divId);
    if (!parent)
      console.log("KarnaughMap error: can not find an element with the given name: " + divId);
    parent.appendChild(svg);

    svg.onmousedown = function (event) {
      canvasMouseDown(event);
    };
    svg.onmousemove = function (event) {
      canvasMouseMove(event);
    };
    svg.onmouseup = function (event) {
      canvasMouseUp(event);
    };
    svg.onmouseup = function (event) {
      canvasMouseUp(event);
    };

    createOverlays();
    this.update();
  };

  this.setNoOfVars = function (no) {

    var c = parseInt(no);
    if (c < 1 && c > 10)
      return;

    hooveredKVField = -1;
    data.init(c);
    createOverlays();

    var width = data.fieldBorder + data.fieldPerLine * data.fieldWidth + 50;
    var height = data.fieldBorder + data.fieldLines * data.fieldHeight + 50;
    svg.setAttribute('width', width.toString());
    svg.setAttribute('height', height.toString());
    this.update();
  };

  this.allowDontCares = function (type) {
    if (type > 0) {
      data.allowDontCare = true;
    } else {
      data.allowDontCare = false;
    }
    data.clear();
    this.update();
  };
  
  this.setDontShowResult = function (type) {
    if (type > 0) {
      dontShowResult = true;
    } else {
      dontShowResult = false;
    }
    this.update();
  };

  this.genRandom = function () {
    data.random();
    this.update();
  };

  this.clear = function () {
    data.clear();
    this.update();
  };

  function createOverlays() {

    var parent = document.getElementById(divId);
    if (!parent)
      console.log("KarnaughMap error: can not find an element with the given name: " + divId);
    parent.setAttribute('style', 'position:relative;');

    // remove old ones
    for (var i in overlays) {
      parent.removeChild(overlays[i]);
    }
    overlays.length = 0;

    for (var i = 0; i < data.noOfVars + 2; i++) {
      var overlay = document.createElement('div');
      overlay.setAttribute('style', 'position:absolute; top:0px; left:0px; visibility:hidden;');
      overlay.innerHTML = "overlay" + i;
      document.body.appendChild(overlay);

      parent.appendChild(overlay);
      overlays.push(overlay);
    }
  }



  function drawKVField(fieldId) {

    var fieldPosX = data.getKVFieldPositionX(fieldId);
    var fieldPosY = data.getKVFieldPositionY(fieldId);
    var truthmapID = data.getKVFieldTruthmapID(fieldId);
    var value = data.getKVFieldValue(fieldId);
    var dn = new UIElement(fieldPosX, fieldPosY, data.fieldWidth, data.fieldHeight, 0, fieldId, 0, 0);

    var strokeColor = "#000000";
    var fillColor = "#FFFFFF";
    if (fieldId === hooveredKVField) {
      fillColor = hooveredKVFieldColor;
    }

    var dx = dn.x2 - dn.x;
    var dy = dn.y2 - dn.y;

    var rect = document.createElementNS(svgns, 'rect');
    rect.setAttribute('x', dn.x);
    rect.setAttribute('y', dn.y);
    rect.setAttribute('height', dx);
    rect.setAttribute('width', dy);
    rect.setAttribute('fill', fillColor);
    rect.setAttribute('stroke', strokeColor);
    svg.appendChild(rect);

    var text = document.createElementNS(svgns, 'text');

    var textColor = "#000000";
    if (value >= 2) {
      value = "X";
      textColor = "#C8C8C8";
    }
    text.setAttribute("fill", textColor);
    //text.setAttribute("style", "font-family: sans-serif; font-weight: normal; font-style: normal");
    text.setAttribute("font-family", "sans-serif");
    text.setAttribute("text-anchor", "middle");
    text.setAttribute("font-size", "20");
    var posX = dn.x + Math.floor(dx / 2);
    var posY = dn.y2 - Math.floor(dx / 3);
    text.setAttribute("x", posX.toString());
    text.setAttribute("y", posY.toString());
    text.textContent = value.toString();
    svg.appendChild(text);

    uiElements.push(dn);

    if (true) {
      var text2 = document.createElementNS(svgns, 'text');
      text2.setAttribute("fill", "#909090");
      text2.setAttribute("text-anchor", "start");
      text2.setAttribute("font-family", "sans-serif");
      text2.setAttribute("font-size", "10");
      var posX = dn.x + Math.floor(dx / 32);
      var posY = dn.y2 - Math.floor(dy / 16);
      text2.setAttribute("x", posX.toString());
      text2.setAttribute("y", posY.toString());
      text2.textContent = truthmapID.toString();
      svg.appendChild(text2);
    }
  }

  function drawRoundRect(colorStr, x, y, width, height, radius) {
    var x1 = x + width;
    var y1 = y + height;

    var path = document.createElementNS(svgns, 'path');
    path.setAttribute("stroke-width", "3");
    path.setAttribute("stroke", colorStr);
    path.setAttribute("fill", "none");

    var d = "";
    d += "M " + (x + radius) + "," + y;
    d += " L " + (x1 - radius) + "," + y;
    d += " Q " + x1 + "," + y + " " + x1 + "," + (y + radius);
    d += " L " + x1 + "," + (y1 - radius);
    d += " Q " + x1 + "," + y1 + " " + (x1 - radius) + "," + y1;
    d += " L " + (x + radius) + "," + y1;
    d += " Q " + x + "," + y1 + " " + x + "," + (y1 - radius);
    d += " L " + x + "," + (y + radius);
    d += " Q " + x + "," + y + " " + (x + radius) + "," + y;
    d += " Z";
    path.setAttribute("d", d);
    svg.appendChild(path);
  }

  function drawRoundRectOpenRightLeft(colorStr, x, y, w, height, radius, offset) {

    var width = w / 2 + Math.floor(data.fieldWidth * 0.6);

    var x1 = x + width;
    var y1 = y + height;

    var path = document.createElementNS(svgns, 'path');
    path.setAttribute("stroke-width", "3");
    path.setAttribute("stroke", colorStr);
    path.setAttribute("fill", "none");

    var d = "";
    d += "M " + (x1 - radius) + "," + y1;
    d += " L " + (x + radius) + "," + y1;
    d += " Q " + x + "," + y1 + " " + x + "," + (y1 - radius);
    d += " L " + x + "," + (y + radius);
    d += " Q " + x + "," + y + " " + (x + radius) + "," + y;
    d += " L " + (x1 - radius) + "," + y;
    path.setAttribute("d", d);
    svg.appendChild(path);

    x1 = x + w + offset;
    x = x + offset + w / 2 - Math.floor(data.fieldWidth * 0.6);

    var path2 = document.createElementNS(svgns, 'path');
    path2.setAttribute("stroke-width", "3");
    path2.setAttribute("stroke", colorStr);
    path2.setAttribute("fill", "none");

    var d = "";
    d += "M " + (x + radius) + "," + y;
    d += " L " + (x1 - radius) + "," + y;
    d += " Q " + x1 + "," + y + " " + x1 + "," + (y + radius);
    d += " L " + x1 + "," + (y1 - radius);
    d += " Q " + x1 + "," + y1 + " " + (x1 - radius) + "," + y1;
    d += " L " + (x + radius) + "," + y1;
    path2.setAttribute("d", d);
    svg.appendChild(path2);

  }

  function drawRoundRectOpenTopDown(colorStr, x, y, width, h, radius, offset) {

    var height = h / 2 + Math.floor(data.fieldHeight * 0.6);
    var x1 = x + width;
    var y1 = y + height;


    var path = document.createElementNS(svgns, 'path');
    path.setAttribute("stroke-width", "3");
    path.setAttribute("stroke", colorStr);
    path.setAttribute("fill", "none");

    var d = "";
    d += "M " + x1 + "," + (y1 - radius);
    d += " L " + x1 + "," + (y + radius);
    d += " Q " + x1 + "," + y + " " + (x1 - radius) + "," + y;
    d += " L " + (x + radius) + "," + y;
    d += " Q " + x + "," + y + " " + x + "," + (y + radius);
    d += " L " + x + "," + (y1 - radius);
    path.setAttribute("d", d);
    svg.appendChild(path);

    y1 = y + h + offset;
    y = y + offset + h / 2 - Math.floor(data.fieldHeight * 0.6);

    var path2 = document.createElementNS(svgns, 'path');
    path2.setAttribute("stroke-width", "3");
    path2.setAttribute("stroke", colorStr);
    path2.setAttribute("fill", "none");

    var d = "";
    d += "M " + x + "," + (y + radius);
    d += " L " + x + "," + (y1 - radius);
    d += " Q " + x + "," + y1 + " " + (x + radius) + "," + y1;
    d += " L " + (x1 - radius) + "," + y1;
    d += " Q " + x1 + "," + y1 + " " + x1 + "," + (y1 - radius);
    d += " L " + x1 + "," + (y + radius);
    path2.setAttribute("d", d);
    svg.appendChild(path2);

  }


  function drawRoundRectAllOpen(colorStr, xx, yy, w, h, radius, offsetX, offsetY) {
    var height = h / 2 + Math.floor(data.fieldHeight * 0.6);
    var width = w / 2 + Math.floor(data.fieldWidth * 0.6);

    var x = xx;
    var y = yy;
    var x1 = xx + width;
    var y1 = yy + height;

    var path = document.createElementNS(svgns, 'path');
    path.setAttribute("stroke-width", "3");
    path.setAttribute("stroke", colorStr);
    path.setAttribute("fill", "none");

    var d = "";
    d += "M " + (x1 - radius) + "," + y;
    d += " L " + (x + radius) + "," + y;
    d += " Q " + x + "," + y + " " + x + "," + (y + radius);
    d += " L " + x + "," + (y1 - radius);
    path.setAttribute("d", d);
    svg.appendChild(path);

    x1 = xx + w + offsetX;
    x = xx + offsetX + w / 2 - Math.floor(data.fieldWidth * 0.6);

    var path2 = document.createElementNS(svgns, 'path');
    path2.setAttribute("stroke-width", "3");
    path2.setAttribute("stroke", colorStr);
    path2.setAttribute("fill", "none");

    var d = "";
    d += "M " + (x + radius) + "," + y;
    d += " L " + (x1 - radius) + "," + y;
    d += " Q " + x1 + "," + y + " " + x1 + "," + (y + radius);
    d += " L " + x1 + "," + (y1 - radius);
    path2.setAttribute("d", d);
    svg.appendChild(path2);

    y1 = yy + h + offsetY;
    y = yy + offsetY + h / 2 - Math.floor(data.fieldHeight * 0.6);
    x = xx;
    x1 = xx + width;

    var path3 = document.createElementNS(svgns, 'path');
    path3.setAttribute("stroke-width", "3");
    path3.setAttribute("stroke", colorStr);
    path3.setAttribute("fill", "none");

    var d = "";
    d += "M " + x + "," + (y + radius);
    d += " L " + x + "," + (y1 - radius);
    d += " Q " + x + "," + y1 + " " + (x + radius) + "," + y1;
    d += " L " + (x1 - radius) + "," + y1;
    path3.setAttribute("d", d);
    svg.appendChild(path3);

    x1 = xx + w + offsetX;
    x = xx + offsetX + w / 2 - Math.floor(data.fieldWidth * 0.6);

    var path4 = document.createElementNS(svgns, 'path');
    path4.setAttribute("stroke-width", "3");
    path4.setAttribute("stroke", colorStr);
    path4.setAttribute("fill", "none");

    var d = "";
    d += "M " + x1 + "," + (y + radius);
    d += " L " + x1 + "," + (y1 - radius);
    d += " Q " + x1 + "," + y1 + " " + (x1 - radius) + "," + y1;
    d += " L " + (x + radius) + "," + y1;
    path4.setAttribute("d", d);
    svg.appendChild(path4);
  }

  function drawKVBlock(blockId) {
    var fieldId = data.blocks[blockId].fieldID;

    var x0 = data.getKVFieldPositionX(fieldId);
    var y0 = data.getKVFieldPositionY(fieldId);
    var dx = data.blocks[blockId].dimx * data.fieldWidth;
    var dy = data.blocks[blockId].dimy * data.fieldHeight;
    var colorStr = "rgb(" + data.blocks[blockId].color[0].toString() + "," + data.blocks[blockId].color[1].toString() + "," + data.blocks[blockId].color[2].toString() + ")";

    var offsetX = (data.fieldWidth * data.fieldPerLine);
    var offsetY = (data.fieldHeight * data.fieldLines);
    var overX = (x0 + dx > offsetX + data.fieldBorder);
    var overY = (y0 + dy > offsetY + data.fieldBorder);
    if (overX && overY) {
      drawRoundRectAllOpen(colorStr, x0 + 2, y0 + 2, dx - 4, dy - 4, 17, -offsetX, -offsetY);
    } else {
      if (overX) {
        drawRoundRectOpenRightLeft(colorStr, x0 + 2, y0 + 2, dx - 4, dy - 4, 17, -offsetX);
      } else {
        if (overY) {
          drawRoundRectOpenTopDown(colorStr, x0 + 2, y0 + 2, dx - 4, dy - 4, 17, -offsetY);
        } else {
          drawRoundRect(colorStr, x0 + 2, y0 + 2, dx - 4, dy - 4, 17);
        }
      }
    }
  }

  function drawKVFields() {
    var count = data.getKVFieldsCount();
    for (var i = 0; i < count; i++) {
      drawKVField(i);
    }
  }

  function drawKVBlocks() {
    var count = data.blocks.length;
    for (var i = 0; i < count; i++) {
      drawKVBlock(i);
    }
  }


  this.update = function () {

    uiElements.length = 0;

    // clear svg element
    while (svg.lastChild) {
      svg.removeChild(svg.lastChild);
    }

    // draws all fields
    drawKVFields();

    // draws all blocks
    if(!dontShowResult) drawKVBlocks();

    // draw labels
    if (overlays.length !== data.noOfVars + 2)
      console.log("KarnaughMap error: overlay not available");

    var labelNum = 1;
    var labelPos = 10;
    var k = 0;
    while (k < data.noOfVars) {

      overlays[k].innerHTML = "<i>x</i><sub><small>" + k + "</small></sub>"

      for (var x = 0; x < data.fieldPerLine; x++) {
        var bits = data.getKVFieldTruthmapID(x);

        if ((bits & labelNum) === labelNum) {
          var x0 = data.fieldWidth * x + data.fieldBorder;
          var x1 = data.fieldWidth * (x + 1) + data.fieldBorder;

          var path = document.createElementNS(svgns, 'path');
          path.setAttribute("stroke-width", "2");
          path.setAttribute("stroke", "#000000");
          path.setAttribute("fill", "none");

          var d = "";
          d += "M " + x0 + "," + (labelPos - 2);  // start marker
          d += " L " + x0 + "," + (labelPos + 2);
          d += " M " + x0 + "," + labelPos;
          d += " L " + x1 + "," + labelPos;
          d += " M " + x1 + "," + (labelPos - 2);  // end marker
          d += " L " + x1 + "," + (labelPos + 2);
          path.setAttribute("d", d);
          svg.appendChild(path);

          var style = overlayStyle + 'top:' + (labelPos - 10) + 'px; left:' + (x1 + 5) + 'px;';
          overlays[k].setAttribute('style', style);
        }
      }
      k++;
      if (k < data.noOfVars) {

        overlays[k].innerHTML = "<i>x</i><sub><small>" + k + "</small></sub>";

        labelNum = labelNum << 1; // move bit to left

        for (var y = 0; y < data.fieldLines; y++) {
          var bits = data.getKVFieldTruthmapID(y * data.fieldPerLine);
          if ((bits & labelNum) === labelNum) {
            var x0 = data.fieldHeight * y + data.fieldBorder;
            var x1 = data.fieldHeight * (y + 1) + data.fieldBorder;

            var path = document.createElementNS(svgns, 'path');
            path.setAttribute("stroke-width", "2");
            path.setAttribute("stroke", "#000000");
            path.setAttribute("fill", "none");

            var d = "";
            d += "M " + (labelPos - 2) + "," + x0;  // start marker
            d += " L " + (labelPos + 2) + "," + x0;
            d += " M " + labelPos + "," + x0;
            d += " L " + labelPos + "," + x1;
            d += " M " + (labelPos - 2) + "," + x1;  // end marker
            d += " L " + (labelPos + 2) + "," + x1;
            path.setAttribute("d", d);
            svg.appendChild(path);

            var style = overlayStyle + 'top:' + (x1) + 'px; left:' + (labelPos - 5) + 'px;';
            overlays[k].setAttribute('style', style);
          }
        }
        labelNum = labelNum << 1; // move bit to left
        labelPos += 20;
        k++;
      }
    }

    // draw binary value
    if (hooveredKVField >= 0 && hooveredKVField < data.getKVFieldsCount()) {
      var truthmapID = data.getKVFieldTruthmapID(hooveredKVField);
      var binString = truthmapID.toString(2);
      while (binString.length < data.noOfVars)
        binString = "0" + binString;

      var valueString = "";
      for (var z = 0; z < binString.length; z++) {
        valueString += binString[z];
        if (z < binString.length - 1)
          valueString += ",";
      }

      var value = data.getKVFieldValue(hooveredKVField);
      if (value >= 2)
        value = "X";
      valueString = "&nbsp;f(" + valueString + ") = " + value;
      //valueString += " (ID: " + hooveredKVField + ")";
      var textX = Math.floor(hooveredKVField % data.fieldPerLine) * data.fieldWidth + Math.floor(data.fieldWidth * 0.8) + data.fieldBorder;
      var textY = Math.floor(hooveredKVField / data.fieldPerLine) * data.fieldHeight + Math.floor(data.fieldHeight * 0.1) + data.fieldBorder;
      var style = overlayStyle2 + 'top:' + textY + 'px; left:' + textX + 'px;';
      overlays[data.noOfVars].setAttribute('style', style);
      overlays[data.noOfVars].innerHTML = valueString;
    } else {
      overlays[data.noOfVars].innerHTML = "";
      var style = 'visibility:hidden;';
      overlays[data.noOfVars].setAttribute('style', style);
    }

    // draw minterm
    var termX = data.fieldBorder;
    var termY = data.fieldHeight * data.fieldLines + data.fieldBorder;
    var termStyle = resultStyle + 'max-width:' + data.fieldPerLine * data.fieldWidth + 'px;';
    overlays[data.noOfVars + 1].setAttribute('style', termStyle);
    if(!dontShowResult) {
      overlays[data.noOfVars + 1].innerHTML = "<span class='qmcMathFont'><i>y</i>&nbsp;=&nbsp;" + qmc.data.coloredMinimalTerm + "</span></p>";
    }else{
      overlays[data.noOfVars + 1].innerHTML = "<span class='qmcMathFont'><i>y</i>&nbsp;=&nbsp;" + "<span style='color:rgb(255,0,0)'>hidden</span>"+ "</span></p>";
    }
  };
  
  function mouseOverElement(pos) {
    var selectedElement = -1;
    for (var n in uiElements) {
      if (uiElements[n].type !== 2) {
        // not of type "connection"
        if (uiElements[n].x - 1 < pos.x &&
                uiElements[n].x2 + 1 > pos.x &&
                uiElements[n].y - 1 < pos.y &&
                uiElements[n].y2 + 1 > pos.y)
        {
          selectedElement = n;
        }
      }
    }
    return selectedElement;
  }

  function canvasMouseDown(event) {
    var pos = getMouse(event);

    // handle selection
    if (!event.altKey && event.which === 1) {
      var selectedElement = mouseOverElement(pos);
      if (selectedElement !== -1) {
        // handle field selection
        if (uiElements[selectedElement].type === 0) {
          var newSelectedKVField = uiElements[selectedElement].ref;
          data.activated(newSelectedKVField);
        }
      }
      that.update();
    }
    event.preventDefault();
  }

  function canvasMouseUp(event) {
  }

  function canvasMouseMove(event) {
    var pos = getMouse(event);

    hooveredKVField = -1;
    var oldHooveredElement = hooveredElement;
    hooveredElement = mouseOverElement(pos);
    console.log(hooveredElement);
    if (hooveredElement !== -1) {
      hooveredKVField = uiElements[hooveredElement].ref;
    }
    if (oldHooveredElement !== hooveredElement)
      that.update();
    oldPos = pos;
    event.preventDefault();
  }

  function getMouse(e) {
    var element = svg;
    var offsetX = 0, offsetY = 0, mx, my;

    // compute the total offset
    if (element.offsetParent !== undefined) {
      do {
        offsetX += element.offsetLeft;
        offsetY += element.offsetTop;
      } while ((element = element.offsetParent));
    }

    mx = e.pageX - offsetX;
    my = e.pageY - offsetY;

    return {x: mx, y: my};
  }
}

Метод Квайна - Мак-Класки:

// Copyright (C) Thorsten Thormaehlen, Marburg, 2013, All rights reserved
// Contact: www.thormae.de

// This software is written for educational (non-commercial) purpose. 
// There is no warranty or other guarantee of fitness for this software, 
// it is provided solely "as is". 

function PetrickMethod()
{
  this.problem;
  this.maxProblemSize = 100;
  this.solution;
  this.log = "";
  var that = this;
  
  this.test = function() {
    var andArray = new Array();
    var orArray;
    var monomA;
    var monomB;
    orArray = new Array();
    monomA = new Object(); // using objects ensures that (x and x) = x
    monomA[1] = 1;
    orArray.push(monomA);
    monomB = new Object();
    monomB[2] = 2;
    orArray.push(monomB);
    andArray.push(orArray);
    orArray = new Array();
    monomA = new Object();
    monomA[3] = 3;
    orArray.push(monomA);
    monomB = new Object();
    monomB[4] = 4;
    orArray.push(monomB);
    andArray.push(orArray);
    orArray = new Array();
    monomA = new Object();
    monomA[1] = 1;
    orArray.push(monomA);
    monomB = new Object();
    monomB[3] = 3;
    orArray.push(monomB);
    andArray.push(orArray);
    orArray = new Array();
    monomA = new Object();
    monomA[5] = 5;
    orArray.push(monomA);
    monomB = new Object();
    monomB[6] = 6;
    orArray.push(monomB);
    andArray.push(orArray);
    orArray = new Array();
    monomA = new Object();
    monomA[2] = 2;
    orArray.push(monomA);
    monomB = new Object();
    monomB[5] = 5;
    orArray.push(monomB);
    andArray.push(orArray);
    orArray = new Array();
    monomA = new Object();
    monomA[4] = 4;
    orArray.push(monomA);
    monomB = new Object();
    monomB[6] = 6;
    orArray.push(monomB);
    andArray.push(orArray);
    /*orArray = new Array();
     monomA = new Object(); 
     monomA[4] = 4;
     orArray.push(monomA);
     monomB = new Object();
     monomB[4] = 4;
     orArray.push(monomB);
     andArray.push(orArray);*/
    
    this.solve(andArray);
  };

  this.solve = function(eq) {

    this.problem = eq;
    this.log = "";
    
    //printEqnArray(eq);
    printEqnArrayFancy(eq);
    
    // multiply out
    var andArray = eq;
    var loopCounter = 0;
    while (andArray.length > 1) {
      var newAndArray = new Array();
      for (var i = 1; i < andArray.length; i += 2) {

        var orTermA = andArray[i - 1];
        var orTermB = andArray[i];
        var newOrArray = new Array();
        for (var a = 0; a < orTermA.length; a++) {
          for (var b = 0; b < orTermB.length; b++) {
            var monom1 = orTermA[a];
            var monom2 = orTermB[b];
            var resultingMonom = new Object();
            for (var m in monom1) {
              resultingMonom[monom1[m]] = monom1[m];
            }
            for (var n in monom2) {
              resultingMonom[monom2[n]] = monom2[n];
            }
            newOrArray.push(resultingMonom);
          }
        }

        newAndArray.push(newOrArray);
      }
      // if uneven copy last and-term
      if (andArray.length % 2 === 1) {
        newAndArray.push(andArray[andArray.length - 1]);
      }
      //printEqnArray(newAndArray);
      printEqnArrayFancy(newAndArray);
      
      andArray.length = 0;
      // simplify or-term
      for (var i = 0; i < newAndArray.length; i++) {
        var orTerm = newAndArray[i];
        var newOrTerm = simplifyOrTerm(orTerm);
        if (newOrTerm.length > 0) {
          andArray.push(newOrTerm);
        }
      }

      var problemSize = eqnArrayProblemSize(andArray);
      if (problemSize > this.maxProblemSize) {
        console.log("Error: The cyclic covering problem is too large to be solved with Petrick's method (increase maxProblemSize). Size=" + problemSize);
        return false;
      }
      
      //printEqnArray(andArray);
      printEqnArrayFancy(andArray);
      loopCounter++;
    }
    this.solution = andArray;
    return true;
  };

  function simplifyOrTerm(orTerm) {
    // find a monom that is the same or simpler than another one
    var newOrTerm = new Array();
    var markedForDeletion = new Object();
    for (var a = 0; a < orTerm.length; a++) {
      var keepA = true;
      var monomA = orTerm[a];
      for (var b = a + 1; b < orTerm.length && keepA; b++) {
        var monomB = orTerm[b];
        var overlapBoverA = 0;
        var lengthA = 0;
        for (var m in monomA) {
          if (monomB[m] in monomA) {
            overlapBoverA++;
          }
          lengthA++;
        }

        var overlapAoverB = 0;
        var lengthB = 0;
        for (var m in monomB) {
          if (monomA[m] in monomB) {
            overlapAoverB++;
          }
          lengthB++;
        }

        if (overlapBoverA === lengthB) {
          keepA = false;
        }

        if (lengthA < lengthB && overlapAoverB === lengthA) {
          markedForDeletion[b] = b;
        }

      }
      if (keepA) {
        if (a in markedForDeletion) {
          // do nothing
        } else
          newOrTerm.push(orTerm[a]);
      }
    }
    return newOrTerm;
  }


  function printEqnArrayFancy(andArray) {
    var str = "";
    for (var i = 0; i < andArray.length; i++) {
      var first = true;
      str += "(";
      var orArray = andArray[i];
      for (var j = 0; j < orArray.length; j++) {
        if (!first)
          str += " &or; ";
        var monom = orArray[j];
        for (var k in monom) {
          str += "<i>p</i><sub><small>"+ monom[k] + "</small></sub>";
        }
        first = false;
      }
      str += ")";
    }
    if(that.log.length > 0) {
      that.log += "<p>&hArr;&nbsp;" + str + "</p>";
    }else{
      that.log += "<p>"+ str + "</p>";
    }
  }
  
  function eqnArrayProblemSize(andArray) {
    var monomCounter = 0;
    for (var i = 0; i < andArray.length; i++) {
      var orArray = andArray[i];
      monomCounter += orArray.length;
    }
    return monomCounter;
  }
  
  
  function printEqnArray(andArray) {
    var str = "";
    for (var i = 0; i < andArray.length; i++) {
      var first = true;
      str += "(";
      var orArray = andArray[i];
      for (var j = 0; j < orArray.length; j++) {
        if (!first)
          str += " or ";
        var monom = orArray[j];
        for (var k in monom) {
          str += monom[k];
        }
        first = false;
      }
      str += ")";
    }
    console.log(str);
  }
  
}

function PrimTerm() {
  this.implicant = -1;
  this.termString = "";
  this.color = [0, 0, 0];
  this.coloredTermString = "";
  this.used = false;
  this.neededByVar = new Object;
}

function Implicant() {
  this.imp = new Object();
  this.isPrim = false;
  this.isOnlyDontCare = false;
  this.bitMask = 0;
}

function ImplicantGroup() {
  this.group = new Array;
  this.order = -1;
}

function PrimTermTable(ord) {
  this.essentialPrimTerms = new Array();
  this.order = ord;
  this.remainingVars =  new Array();;
  this.remainingPrimTerms =  new Array();
  this.supersededPrimTerms =  new Array();
}

function hsvToRgb(h, s, v) {

  var r, g, b;
  var i = Math.floor(h * 6);
  var f = h * 6 - i;
  var p = v * (1 - s);
  var q = v * (1 - f * s);
  var t = v * (1 - (1 - f) * s);

  switch (i % 6) {
  case 0:
    r = v, g = t, b = p;
    break;
  case 1:
    r = q, g = v, b = p;
    break;
  case 2:
    r = p, g = v, b = t;
    break;
  case 3:
    r = p, g = q, b = v;
    break;
  case 4:
    r = t, g = p, b = v;
    break;
  case 5:
    r = v, g = p, b = q;
    break;
  }

  return [ Math.floor(r * 255), Math.floor(g * 255), Math.floor(b * 255) ];
}

function QuineMcCluskeyDataCtrl() {
  this.noOfVars = -1;
  this.funcdata = new Array;
  this.primTerms = new Array;
  this.implicantGroups = new Array;
  this.minimalTerm = "";
  this.coloredMinimalTerm = "";
  this.minimalTermPrims = new Array;
  this.primTermTables = new Array;
  this.petrickSolver = new PetrickMethod();
  this.petrickTermPrims = new Array;
  this.allowDontCare = false;
  
  this.init = function(no) {
    this.noOfVars = no;
    this.funcdata.length = 0;
    this.primTerms.length = 0;
    this.implicantGroups.length = 0;
    this.minimalTerm = "0";
    this.coloredMinimalTerm = "0";
    this.minimalTermPrims.length = 0;
    this.primTermTables.length = 0;
    this.petrickTermPrims.length = 0;

    var noOfFuncData = Math.pow(2, this.noOfVars);
    for (var i = 0; i < noOfFuncData; i++) {
      this.funcdata.push(0);
    }
    
    //this.petrickSolver.test();
    
  };
  
  this.setFuncData = function(i, val) {
    if (i < 0 || i >= this.funcdata.length)
      return;
    this.funcdata[i] = val;
  };
  
  this.activated = function(i) {
    if (i < 0 || i >= this.funcdata.length)
      return;

    this.funcdata[i] += 1;
    if(this.allowDontCare) {
      if (this.funcdata[i] > 2) this.funcdata[i] = 0;
    }else{
      if (this.funcdata[i] > 1) this.funcdata[i] = 0;
    }
    this.compute();
  };
  
  this.random = function() {
    for (var i = 0; i < this.funcdata.length; i++) {
      if(this.allowDontCare) {
        this.funcdata[i] = Math.floor(Math.random() * 3);
      }else{
        this.funcdata[i] = Math.floor(Math.random() * 2);
      }
    }
    this.compute();
  };
  
  this.clear = function() {
    for (var i = 0; i < this.funcdata.length; i++) {
      this.funcdata[i] = 0;
    }
    this.compute();
  };

  function bitCount(value) {
    var counter = 0;
    while (value > 0) {
      if ((value & 1) === 1) counter++;
      value >>= 1;
    }
    return counter;
  }
  
  this.compute = function() {
    this.primTerms.length = 0;
    this.implicantGroups.length = 0;
    this.minimalTerm = "0";
    this.coloredMinimalTerm = "0";
    this.minimalTermPrims.length = 0;
    this.primTermTables.length = 0;
    this.petrickTermPrims.length = 0;
    
    var counter = 0;
    var lastIg = -1;
    var continueLoop = true;
    while(continueLoop) {
      
      continueLoop = false;
      var ig = new ImplicantGroup();
      
      if(counter === 0) {
         for (var i = 0; i < this.funcdata.length; i++) {
           if(this.funcdata[i] > 0) {
             var impl = new Implicant();
             impl.imp[i] = i;
             impl.isPrim = true;
             ig.group.push(impl);
             continueLoop = true;
           }
         }
      }else{
        
        for (var i = 0; i < lastIg.group.length; i++) {
          for (var j = i+1; j < lastIg.group.length; j++) {
            var imp1 = lastIg.group[i];
            var imp2 = lastIg.group[j];
            
            if (imp1.bitMask === imp2.bitMask) {

              var found = false;
              var xor = -1;
              for (var m in imp1.imp) {
                for (var n in imp2.imp) {
                  var i1 = imp1.imp[m];
                  var i2 = imp2.imp[n];
                  //console.log(i1 + "<->" + i2);
                  xor = (i1 ^ i2) & (~imp1.bitMask);
                  if (bitCount(xor) === 1) {
                    //console.log("found merge candidate" + i1 + "<->" + i2);
                    found = true;
                  }
                  break;
                }
                break;
              }
              if (found) {
                imp1.isPrim = false;
                imp2.isPrim = false;

                var impl = new Implicant();
                impl.isPrim = true;
                impl.bitMask = imp1.bitMask | xor;
                for (var m in imp1.imp)
                  impl.imp[m] = parseInt(m);
                for (var n in imp2.imp)
                  impl.imp[n] = parseInt(n);

                var foundMatch = false; // determine if this combination is already there
                for(var k=0; k < ig.group.length; k++) {
                  var exist = ig.group[k];
                  var isTheSame = true;  
                   for(var m in impl.imp) {
                     var found = false;
                     for (var n in exist.imp) {
                      if(parseInt(m) === parseInt(n)) {
                        found = true;
                      }
                     }
                     if(!found) {
                       isTheSame = false;
                       break;
                     }
                   }
                   if(isTheSame) {
                     foundMatch = true;
                     break;
                   }
                }
                if(!foundMatch) {
                  ig.group.push(impl);
                  continueLoop = true;
                }
              }
            }
          }
        }
      }
      
      if(continueLoop) this.implicantGroups.push(ig);
      lastIg = ig;
      counter++;
    }
    
    // collect primterms
    this.primTerms.length = 0;
    this.minimalTermPrims.length = 0;
    var color = 0.0;
    for(var i= this.implicantGroups.length-1; i >=0; i--) {
      var g = this.implicantGroups[i].group;
    
      for(var j=0; j < g.length; j++) {
        if(g[j].isPrim) {
          
          // prim terms introduced by don't cares
          // must have at least one 1
          var containsOne = false;
          var allFuncPrimTerm = g[j].imp;
          for(var kk in allFuncPrimTerm) {
            var k = allFuncPrimTerm[kk];
            if(this.funcdata[k] === 1) {
              containsOne = true;
            }
          }
          
          if(!containsOne){
            g[j].isOnlyDontCare = true;
          } else {
            var primTerm = new PrimTerm();
            primTerm.implicant = g[j];

            // extract minTerm as string
            for (var thisVal in primTerm.implicant.imp) {
              var minTerm = "";
              var one = 1;
              var needed = (~primTerm.implicant.bitMask);
              for (var v = 0; v < this.noOfVars; v++) {
                if ((needed & one) === one) {
                  if ((thisVal & one) === one) {
                    minTerm = "<i>x</i><sub><small>" + v + "</small></sub>" + minTerm;
                  } else {
                    minTerm = "<i>x&#772;</i><sub><small>" + v + "</small></sub>" + minTerm;
                  }
                }
                one = one << 1;
              }
              minTerm = "(" + minTerm + ")";
              if (primTerm.implicant.bitMask === Math.pow(2, this.noOfVars) - 1)
                minTerm = "1";
              primTerm.color = hsvToRgb(color, 1.0, 0.5);
              color += 0.22;
              color = color % 1.0;


              primTerm.termString = minTerm;
              var colorStr = "rgb(" + primTerm.color[0] + "," + primTerm.color[1] + "," + primTerm.color[2] + ")";
              primTerm.coloredTermString = "<span style='color:" + colorStr + "'>" + minTerm + "</span>";
              break;
            }

            this.primTerms.push(primTerm);
          }
        }
      }
    }
    
    
    // looking for essential prime implicants 
    var remaining = new Object();
    for (var i = 0; i < this.funcdata.length; i++) {
      if(this.funcdata[i] === 1) {
        remaining[i] = i;
      }
    }
    
    this.primTermTables.length = 0;
    var primTableLoop = 0;
    var primTableFound = (this.primTerms.length > 0);
    var cyclicCoveringFound = false;
    var primTermTable;
    while (primTableFound) {

      primTableFound = false;

      primTermTable = new PrimTermTable(primTableLoop);
      for (var r in remaining) {
        primTermTable.remainingVars.push(remaining[r]);
      }

      if (primTableLoop === 0) { 
        for (var j = 0; j < this.primTerms.length; j++) {
          primTermTable.remainingPrimTerms.push(this.primTerms[j]);
        }
      } else {
        // remove rows
        var prevTable = this.primTermTables[primTableLoop-1]; 
        for(var k=0; k <prevTable.remainingPrimTerms.length; k++) {
          if(!prevTable.remainingPrimTerms[k].used){
            
            var superseded = false;
            var impA = prevTable.remainingPrimTerms[k].implicant.imp;
            var varCover = new Object;
            var countA = 0;
            for(var r in remaining) {
              var v = remaining[r];
              if (v in impA) {
                varCover[v] = v;
                countA++;
              }
            }
            
            for (var l = 0; l < prevTable.remainingPrimTerms.length && !superseded; l++) {
              if (!prevTable.remainingPrimTerms[l].used && k !== l) {
                var impB = prevTable.remainingPrimTerms[l].implicant.imp;
                var countB = 0;
                for (var r in varCover) {
                  var v = varCover[r];
                  if (v in impB) {
                    countB++;
                  }
                }
                if(countA === countB) {
                  var countBInRemaining = 0;
                  for (var r in remaining) {
                    var v = remaining[r];
                    if (v in impB) {
                      countBInRemaining++;
                    }
                  }
                  if(countBInRemaining > countA) {
                    superseded = true;
                  }else{
                    if(k > l) {
                      superseded = true;
                    }
                  }
                }

              }
            }
            
            if(!superseded) {
              primTermTable.remainingPrimTerms.push(prevTable.remainingPrimTerms[k]);
            }else{
              prevTable.supersededPrimTerms.push(prevTable.remainingPrimTerms[k]);
            }
          }
        }
      }

      if (primTermTable.remainingPrimTerms.length > 0) {
        this.primTermTables.push(primTermTable);
        var currentTerms = primTermTable.remainingPrimTerms;

        var toBeRemoved = new Object();
        
        for (var r in remaining) {
          var i = remaining[r];
          var count = 0;
          var term = -1;
          for (var j = 0; j < currentTerms.length && count < 2; j++) {
            if (i in currentTerms[j].implicant.imp) {
              term = j;
              count++;
            }
          }

          if (count === 1) {
            currentTerms[term].neededByVar[i] = primTableLoop;
            if(!currentTerms[term].used) {
              this.minimalTermPrims.push(currentTerms[term]);
              currentTerms[term].used = true;
              primTermTable.essentialPrimTerms.push(currentTerms[term]);
              primTableFound = true;

              for (var r in remaining) {
                var ii = remaining[r];
                if (ii in currentTerms[term].implicant.imp) {
                  toBeRemoved[ii] = ii;
                }
              }
            }
          }
        }
        
        // remove columns
        var tmpRemaining = new Object();
        for (var e in remaining){
          var ee = remaining[e];
          tmpRemaining[ee] = ee;
          delete remaining[e];
        }
        var remainingCount = 0;
        for (var r in tmpRemaining) {
          var t = tmpRemaining[r];
          if(!(t in toBeRemoved)) {
             remaining [t] = t;
             remainingCount++;
          }
        }    
      }
      
      if( remainingCount === 0 ) {
        primTableFound = false; // break loop
      }else{
        if(!primTableFound) {
          cyclicCoveringFound = true;
        }
      }

      primTableLoop++;
    }
    
   var solutionFound = true;
    
    // Petrick's Method
    if (cyclicCoveringFound) {
      //console.log("Cyclic covering found");

      var andArray = new Array();
   
      for (var r in remaining) {
        var ii = remaining[r];
         var orArray = new Array();

        for (var k = 0; k < primTermTable.remainingPrimTerms.length; k++) {
          var imp = primTermTable.remainingPrimTerms[k].implicant.imp;
          if(ii in imp){
            var monom = new Object();
            monom[k] = k;
            orArray.push(monom);
          }
        }
        andArray.push(orArray);
      }
      
      solutionFound = this.petrickSolver.solve(andArray);
      
      if (solutionFound) {
        var solutions = this.petrickSolver.solution[0];

        var bestSolution = -1;
        var bestCount = 10000000;
        var bestVarCount = 10000000;
        for (var i = 0; i < solutions.length; i++) {
          var count = 0;
          for (var j in solutions[i]) {
            count++;
          }
          if (count <= bestCount) { // first sort accoring to monom length

            var foundBest = true;
            if (count === bestCount) {
              var bestVarCountNew = 0;
              for (var j in solutions[i]) {
                for (var v in primTermTable.remainingPrimTerms[j].implicant.imp) {
                  bestVarCountNew++;
                }
              }
              if (bestVarCountNew >= bestVarCount)
                foundBest = false;
            }

            if (foundBest) {
              bestCount = count;
              bestSolution = i;
              bestVarCount = 0;
              for (var j in solutions[bestSolution]) {
                for (var v in primTermTable.remainingPrimTerms[j].implicant.imp) {
                  bestVarCount++;
                }
              }
            }
          }
        }
        //console.log("Best solution " + bestSolution);

        var best = solutions[bestSolution];
        for (var b in best) {
          var addPrimTerm = primTermTable.remainingPrimTerms[best[b]];
          this.minimalTermPrims.push(addPrimTerm);
          this.petrickTermPrims.push(addPrimTerm);
        }
      }
    }
    
    if (solutionFound) {
      this.minimalTerm = "";
      this.coloredMinimalTerm = "";
      var firstL = true;
      for (var i = 0; i < this.minimalTermPrims.length; i++) {
        if (!firstL) {
          this.minimalTerm += " &or; ";
          this.coloredMinimalTerm += " &or; ";
        }
        this.minimalTerm += this.minimalTermPrims[i].termString;
        this.coloredMinimalTerm += this.minimalTermPrims[i].coloredTermString;
        firstL = false;
      }

      if (this.minimalTermPrims.length === 0) {
        this.minimalTerm = "0";
        this.coloredMinimalTerm = "0";
      }
    }else{
       this.minimalTerm = 'Error: The cyclic covering problem is too large (increase the "maxProblemSize" parameter)';
       this.coloredMinimalTerm = 'Error: The cyclic covering problem is too large (increase the "maxProblemSize" parameter)';
    }
  };
}




function QuineMcCluskey(parentDivId, columns, language) {
  var myDiv = -1;
  var divId = parentDivId;
  this.cols = columns + 1;
  this.rows = Math.pow(2, columns);
  this.data =  new QuineMcCluskeyDataCtrl();
  var that = this;

  var labels;
  if(language === 0) {
    labels = {ttable:"Truth table",
              minExp:"Minimal boolean expression",
              impli:"Implicants",
              order:"Order",
              primChart:"Prime implicant chart",
              primChartReduced:"Reduced prime implicant chart (Iteration",
              extractedPrims:"Extracted essential prime implicants",
              extractedMPrims:"Extracted prime implicants",
              petricksM:"Petrick's method"};
  }else{
    labels = {ttable:"Wahrheitstafel",
              minExp:"Minimaler boolescher Ausdruck",
              impli:"Implikanten",
              order:"Ordnung",
              primChart:"Primimplikantentafel",
              primChartReduced:"Reduzierte Primimplikantentafel (Iteration",
              extractedPrims:"Extrahierte essentielle Primimplikanten",
              extractedMPrims:"Extrahierte Primimplikanten",
              petricksM:"Verfahren von Petrick"};
    
  }

  this.init = function() {
    
    this.data.init(columns);
    
    myDiv = document.createElement('div');
    if (!myDiv) {
      console.log("QuineMcCluskey error: can not create a canvas element");
      myDiv = -1;
    } else {
     
      var parent = document.getElementById(divId);
      if (!parent) {
        if(divId !== "fakeDivId") {
          console.log("QuineMcCluskey error: can not find an element with the given name: " + divId);
        }
        myDiv = -1;
      } else {
        document.body.appendChild(myDiv);
        parent.appendChild(myDiv);
      }
    }
    this.update();
  };

  this.setNoOfVars = function(vars) {
    var c = parseInt(vars);
    if (c < 1 && c > 6)
      return;
    this.cols = c + 1;
    this.rows = Math.pow(2, c);
    this.data.init(c);
    this.update();
  };

  this.genRandom = function() {
    this.data.random();
    this.update();
  };

  this.allowDontCares = function(type) {
    if(type > 0) {
      this.data.allowDontCare = true;
    }else{
      this.data.allowDontCare = false;
    }
    this.data.clear();
    this.update();
  };

  this.drawImplicantGroup = function(g, parent, primFlag, t, drawPetrickVars) {
    var primTermTable = this.data.primTermTables[t];
    var myTable = document.createElement('table');
    myTable.setAttribute('class', 'qmcTableClass');
    var myRow = document.createElement('tr');
    
    var cell1h = document.createElement('td');  
    cell1h.setAttribute('class', 'qmcTdNoBorder');
    cell1h.innerHTML = "";
    myRow.appendChild(cell1h);
    
    for (var j = 0; j < this.data.noOfVars; j++) {
      var myCell = document.createElement('th');
      myCell.innerHTML = "<i>x</i><sub><small>" + (this.data.noOfVars-1-j) + "</small></sub>";
      myCell.setAttribute('class', 'qmcHeaderX qmcBit');
      myRow.appendChild(myCell);
    }
    
    if (primFlag) {
      for (var i = 0; i < primTermTable.remainingVars.length; i++) {
        var cellImph = document.createElement('td');
        cellImph.setAttribute('class', 'qmcTdNoBorder');
        cellImph.innerHTML = primTermTable.remainingVars[i].toString(10);
        myRow.appendChild(cellImph);
      }
    }
    
    var cellImph = document.createElement('td');
    cellImph.setAttribute('class', 'qmcTdNoBorder');
    cellImph.innerHTML = "";
    myRow.appendChild(cellImph);


    myTable.appendChild(myRow);
    
    var iMax = 0;
    if(!primFlag) iMax = g.group.length; else iMax = primTermTable.remainingPrimTerms.length;
    
    for (var i = 0; i < iMax; i++) {
      var impl = -1;
      if(!primFlag) impl = g.group[i]; else impl = primTermTable.remainingPrimTerms[i].implicant;
      var bits = 0;
      var mask = impl.bitMask;
      
      for(var m in impl.imp) {
        bits = impl.imp[m];
        break;
      }
               
      myRow = document.createElement('tr');
      
      var cell1 = document.createElement('td');      
      var cell1Str = "";
      var first = true;
      for(var m in impl.imp) {
        if(!first) cell1Str +=  ", ";
        cell1Str += impl.imp[m].toString(10);
        first = false;
      }
      cell1.innerHTML = cell1Str + ":";
      cell1.setAttribute('class', 'qmcTdNoBorder');
      myRow.appendChild(cell1);
      
      var res = bits.toString(2);
      for (var j = 0; j < this.data.noOfVars; j++) {
        var myCell = document.createElement('td');
        myCell.setAttribute('class', 'qmcBit');
        var str;

        var currentBit = Math.pow(2, (this.data.noOfVars - 1)-j);
             
        if ((currentBit & mask) === currentBit) {
          str = "-";
          myCell.innerHTML = str;
        } else {
          if (j >= (this.data.noOfVars) - res.length) {
            str = res.charAt(j - (this.data.noOfVars - res.length));
            myCell.innerHTML = str;
          } else {
            str = "0";
            myCell.innerHTML = str;
          }
        }
        myRow.appendChild(myCell);
      }
      
     
      if (!primFlag) {
         var cellLast = document.createElement('td');
         cellLast.setAttribute('class', 'qmcTdNoBorder');
        if (impl.isPrim) {
          cellLast.innerHTML = "&#x2713;";  //equivalent &check; in most browsers
          if(impl.isOnlyDontCare){
            cellLast.innerHTML = " (&times;)"
          }
        } else {
          cellLast.innerHTML = "&rarr;";
        }
        myRow.appendChild(cellLast);
      }else{
        for (var v = 0; v < primTermTable.remainingVars.length; v++) {
          var ii = primTermTable.remainingVars[v];
          var cellUsed = document.createElement('td');
          cellUsed.setAttribute('class', 'qmcPrimItem qmcBit');
          if (ii in impl.imp) {
            cellUsed.innerHTML = "&#9675;";
            if (ii in primTermTable.remainingPrimTerms[i].neededByVar) {
              if(primTermTable.remainingPrimTerms[i].neededByVar[ii] === t) {
                cellUsed.innerHTML = "<span style='color:green;'>&#9679;</span>";
              }
            }
          }

          myRow.appendChild(cellUsed);
        }
         var cellLast = document.createElement('td');
         cellLast.setAttribute('class', 'qmcTdNoBorder');    
         cellLast.innerHTML = primTermTable.remainingPrimTerms[i].coloredTermString;  
         if(drawPetrickVars) {
           var pVars = "&nbsp;&equiv;&nbsp;<i>p</i><sub><small>" + i + "</small></sub>";
           cellLast.innerHTML += pVars;        
         }
         
         
         myRow.appendChild(cellLast);
      }
 
      
      myTable.appendChild(myRow);
    }

    parent.appendChild(myTable);
  };


  this.update = function() {

    if(myDiv === -1) return;

    // clean up
    var oldInnerDiv = document.getElementById(divId+"_innerDiv");
    if (oldInnerDiv) myDiv.removeChild(oldInnerDiv);
    
    var myInnerDiv = document.createElement('div');
    myInnerDiv.setAttribute('id', divId+"_innerDiv");
    

    var myTruthTableDiv = document.createElement('div');
    myTruthTableDiv.innerHTML = "<div>" + labels['ttable'] + ":</div>";
    myTruthTableDiv.setAttribute('class', 'qmcTableLabelDiv');
    
    // re-generate
    var myTable = document.createElement('table');
    myTable.setAttribute('class', 'qmcTableClass');

    var myRow = document.createElement('tr');
    
    var cell1h = document.createElement('td');      
    cell1h.innerHTML = "";
    cell1h.setAttribute('class', 'qmcTdNoBorder');
    myRow.appendChild(cell1h);
    
    for (var j = 0; j < this.cols; j++) {
      var myCell = document.createElement('th');
      if (j < this.cols - 1) {
        myCell.innerHTML = "<i>x</i><sub><small>" + (this.cols-2-j) + "</small></sub>";
        myCell.setAttribute('class', 'qmcHeaderX qmcBit');
      } else {
        myCell.innerHTML = "<i>y</i>";
        myCell.setAttribute('class', 'qmcHeaderY qmcBit');
      }
      myRow.appendChild(myCell);
    }
    myTable.appendChild(myRow);
   

   
    for (var i = 0; i < this.rows; i++) {
      myRow = document.createElement('tr');
      
      var cell1 = document.createElement('td');      
      cell1.innerHTML = i.toString(10) + ":";
      cell1.setAttribute('class', 'qmcTdNoBorder');
      myRow.appendChild(cell1);
      
      var res = i.toString(2);
      for (var j = 0; j < this.cols; j++) {
        var myCell = document.createElement('td');

        if (j < this.cols - 1) { // x element
          myCell.setAttribute('class', 'qmcBit');
          var str;
          if (j >= (this.cols - 1) - res.length) {
            str = res.charAt(j - ((this.cols - 1) - res.length));
            myCell.innerHTML = str;
          } else {
            str = "0";
            myCell.innerHTML = str;
          }
        } else { // y element
          myCell.setAttribute('class', 'qmcBit qmcBitY');
          myCell.setAttribute('title', i);
          myCell.onmousedown = function(event) {
            myCellMouseDown(event);
          };

          if (this.data.funcdata[i] === 0) {
            myCell.innerHTML = "0";
          } 
          if (this.data.funcdata[i] === 1) {
            myCell.innerHTML = "1";
          }
          if (this.data.funcdata[i] === 2) {
            myCell.innerHTML = "&times;";
          }
        }
        myRow.appendChild(myCell);
      }
      myTable.appendChild(myRow);
    }

    myTruthTableDiv.appendChild(myTable);
    myInnerDiv.appendChild(myTruthTableDiv);
    

    for(var i=0; i < this.data.implicantGroups.length; i++) {
      var myImplicantDiv = document.createElement('div');
      myImplicantDiv.innerHTML = "<div>"+ labels['impli'] + " (" + labels['order'] + " "+i+"):</div>";
      myImplicantDiv.setAttribute('class', 'qmcTableLabelDiv');
      this.drawImplicantGroup(this.data.implicantGroups[i],  myImplicantDiv, false, 0, false);
      myInnerDiv.appendChild(myImplicantDiv); 
    }
    
     
    for (var i = 0; i < this.data.primTermTables.length; i++) {
      var resultDiv = document.createElement('div');
      if(i === 0 ) {
        resultDiv.innerHTML = "<p>" + labels['primChart'] + ":</p";
      }else{
        resultDiv.innerHTML = "<p> " +labels['primChartReduced'] + " " + (i-1) + "):</p>";
      }
        
      resultDiv.setAttribute('class', 'qmcTableResultDiv');

      var drawPetrickVars = false;
      if(this.data.petrickTermPrims.length > 0 && i === this.data.primTermTables.length-1) {
        drawPetrickVars = true;
      }
      
      this.drawImplicantGroup(this.data.primTerms, resultDiv, true, i, drawPetrickVars);
      
      var essPTermsDiv = document.createElement('div');
      var essPTermsStr = "";
      var primTermTable = this.data.primTermTables[i];
      var jj = primTermTable.essentialPrimTerms.length;
      for(var j=0; j < jj; j++) {
        essPTermsStr += primTermTable.essentialPrimTerms[j].coloredTermString;
        if(j !== (jj-1)) essPTermsStr += ", ";
      }
      if(jj > 0) {
       essPTermsDiv.innerHTML = "<p>" + labels['extractedPrims'] +": <span class='qmcMathFont'>" + essPTermsStr + "</span></p>";
       essPTermsDiv.setAttribute('class', 'qmcIndent');
       resultDiv.appendChild(essPTermsDiv);
      }
     
      myInnerDiv.appendChild(resultDiv);
    }
    
    if (this.data.petrickTermPrims.length > 0) {
      var petrickDiv = document.createElement('div');
      petrickDiv.innerHTML = "<p> " + labels['petricksM'] + " </p>";

      var petrickInnerDiv = document.createElement('div');
      petrickInnerDiv.innerHTML = "<span class='qmcMathFont'>" + this.data.petrickSolver.log + "</span>";
      petrickInnerDiv.setAttribute('class', 'qmcIndent');
      petrickDiv.appendChild(petrickInnerDiv);

      var petrickEssTermsDiv = document.createElement('div');
      var petrickEssTermsStr = "";
      var jj = this.data.petrickTermPrims.length;
      for (var j = 0; j < jj; j++) {
        petrickEssTermsStr += this.data.petrickTermPrims[j].coloredTermString;
        if (j !== (jj - 1))
          petrickEssTermsStr += ", ";
      }
      if (jj > 0) {
        petrickEssTermsDiv.innerHTML = "<p>" + labels['extractedMPrims'] + " (" + labels['petricksM'] + "): <span class='qmcMathFont'>" + petrickEssTermsStr + "</span></p>";
        petrickEssTermsDiv.setAttribute('class', 'qmcIndent');
        petrickDiv.appendChild(petrickEssTermsDiv);
      }

         myInnerDiv.appendChild(petrickDiv);
    }
    
    
    var termDiv = document.createElement('div');
    termDiv.innerHTML = "<p><strong>" + labels['minExp']+ ":</strong> </p> <p ><span class='qmcMathFont'><i>y</i>&nbsp;=&nbsp;" + this.data.coloredMinimalTerm; +"</span></p>";
    myInnerDiv.appendChild(termDiv);
    myDiv.appendChild(myInnerDiv);
  };

  function myCellMouseDown(e) {

    var targ;
    if (e.target) {
      targ = e.target;
    } else { // deal with Microsoft
      if (e.srcElement)
        targ = e.srcElement;
    }
    if (targ.nodeType === 3) { // deal with Safari
      targ = targ.parentNode;
    }
    var i = parseInt(targ.title);
    that.data.activated(i);

    that.update();
  }
}

Примечания