WikiSort.ru - Не сортированное

Комментарии Вейча

О разработке своих диаграмм и их интерпретации Вейч писал следующее.

• Проблема состоит в том, чтобы изобразить булевую функцию от n переменные так, чтобы человеческий глаз мог легко увидеть, как её упростить.
• Функция четырёх переменных имеет шестнадцать входных комбинаций и соответственно диаграмма содержит шестнадцать квадратов, которые должны быть заполнены с помощью таблицы истинности соответствующей функции.
• Основное различие между версиями Вейча и Карно является то, что диаграммы Вейча представляют данные в двоичной последовательности, используемой в таблице истинности, тогда как в картах Карно меняются местами третий и четвёртый ряды и третий и четвёртый столбцы.
• Компьютерное сообщество выбрал подход Карно. Вейч принял это решение, несмотря на то, что в начале 1952 года перед своей презентацией он хотел выбрать такой же подход, но решил этого не делать. Через несколько лет в учебниках появилось описание карт Карно, и в некоторых из них они назывались диаграммами Вейча.

В 1999 Вейч обнаружил в Википедии статью о картах Карно. Он прочитал её и, перечитав свою работу 1952 года, понял, что в ней не был описан метод минимизации. Теперь он считает, что читатели его статьи полагали, что он делал минимизацию, глядя на обозначения столбцов и строк, а те кто использовали карты Карно минимизировали группы по правилам, а затем использовали метки только для идентификации групп.

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

Оригинальные диаграммы Вейча

Было известно, что функции могли быть представлены в виде точек в углах n-мерного куба. Два смежных угла, например два верхних правых могут быть определены как верхние правые углы, а четыре угла на передней грани куба могут быть определены как передние углы. Для четырёх, пяти или шести переменных проблема становится ещё более сложной.

Как изобразить многомерный куб на плоской диаграмме, чтобы можно было легко увидеть эти отношения?

• Для трёх измерений, Вейч рисовал набор квадратов 2х2 для верхней части куба, и второй для нижней части куба с небольшим промежутком между двумя наборами квадратов. В верхнем наборе 2x2 минимизируемой группой были горизонтальная или вертикальная пара клеток или все четыре клетки. Связь между верхним и нижним множеством представлялась как связь один-к-одному между каждым квадратом верхнего набора и соответствующей ячейкой нижнего множества. Аналогичное правило применяется для случая четырёх переменных, который иногда изображается в виде куба, внутри другого куба у которых все соответствующие углы связаны.
• Диаграммы Вейча для четырёх переменных тогда будут изображаться как четыре набора 2х2 большого квадрата с небольшим пространством между каждой парой наборов. Таким образом, горизонтальную пара в левом верхнем наборе можно объединить с соответствующей парой в левом нижнем наборе или верхнем правом наборе или, возможно, со всеми четырьмя наборами, составив группу из возьми клеток.
• Для пяти или шести переменных применяется это же правило. Диаграмма для пяти переменных состоит из двух диаграмм для четырёх переменных, расположенных рядом друг с другом с большим промежутком между ними. Совпадений между двумя диаграммами для четырёх переменных находится для клеток, которые совпадают если одну карту наложить на другую.

В последнюю минуту перед презентацией Вейч удалил промежуток между группами клеток 2x2. Это было плохое решение, потому что усложнило понимание общей структуры функции, а также применение правил минимизации. Позже, решая головоломки Судоку, Вейч понял, что наличие промежутков или толстых линий между группами квадратов может быть очень полезным, особенно если у тебя такое плохое зрение, как было у Вейча в старости.^[16]