Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.[1][2][3]
Преобразование функции можно разделить на два этапа:

  • на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
  • на втором этапе — переход от сокращённой формы к минимальной форме.

Первый этап (получение сокращённой формы)

Представим, что заданная функция представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:

  1. Операция склеивания;
  2. Операция поглощения.

Операция склеивания сводится к нахождению пар членов, соответствующих виду или , и преобразованию их в следующие выражения: . Результаты склеивания теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).

Потом выполняется операция поглощения. Она основана на равенстве (член поглощает выражение ). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания.
Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.
Применение этих операций продемонстрировано в таблице:

0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

СДНФ выглядит так:

Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)

Членами результата склеивания являются

Член поглощает те члены исходного выражения, которые содержат , то есть первый и четвёртый. Эти члены вычёркиваются. Член поглощает второй и третий, а член  — пятый член исходного выражения.

Повторение обеих операций приводит к следующему выражению:

Здесь склеивается пара членов и (склеивание пары членов и приводит к тому же результату), результат склеивания поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

Структурная схема функции
Структурная схема функции

Члены сокращённой формы (в нашем случае это и ) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.

Второй этап (табличный) (получение минимальной формы)

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

0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

СДНФ, собранная по этой таблице выглядит следующим образом:

Конечное выражение достигается за счёт повторного использования операций склеивания и поглощения:

Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.

Импликантная матрица

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта поглощает члены и (в первом и во втором столбцах поставлены крестики).

Простая импликанта  

Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.

В нашем примере ядро составляют импликанты и (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту .

Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна
Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна
      (а)

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант и . Покажем допустимость подобного исключения членов из логического выражения.

Импликанты и становятся равными лог. 1 соответственно при следующих наборах значений аргументов: , , и , , .

Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

  • при , ,

;

  • при , ,

;

Использование метода для получения минимальной КНФ

Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии:

  • для минимизации берётся не СДНФ, а СКНФ функции;
  • склеиваемые пары членов меняются на: или ;
  • правило операции поглощения выглядит следующим образом:

См. также

Примечания

Эта страница в последний раз была отредактирована 7 февраля 2020 в 09:02.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).