Особенности ДНФ линейных и монотонных функций алгебры логики

Для линейной ФАЛ изменение любой существенной переменной меняет значение функции. Поэтому если f линейно зависит от \(x_i\), в каждую её импликанту обязательно входит один из литералов \(x_i\) или \(\neg x_i\). Для существенной линейной функции простые импликанты фиксируют все существенные переменные.1

Для монотонной ФАЛ из α≤β следует f(α)≤f(β). Простые импликанты такой функции не содержат отрицаний. Они однозначно соответствуют нижним единицам функции. Сокращённая ДНФ монотонной ФАЛ является её единственной тупиковой ДНФ, а сама функция является ядровой.1

Что важно запомнить
  • Линейная зависимость от \(x_i\) означает: на любых соседних по \(x_i\) вершинах значения функции различаются.
  • При линейной зависимости каждая импликанта содержит \(x_i\) или \(\neg x_i\).
  • У монотонной ФАЛ простые импликанты не содержат отрицаний.
  • Простые импликанты монотонной функции соответствуют её нижним единицам.
  • Сокращённая ДНФ монотонной ФАЛ — единственная тупиковая ДНФ этой функции.1

Линейные функции

В терминологии курса f линейно зависит от переменной \(x_i\), если для любых двух наборов, соседних по этой координате, значения функции различаются. Эквивалентно, переключение \(x_i\) при фиксированных остальных переменных всегда переключает значение f. ФАЛ называется линейной, если она линейно зависит от всех своих существенных переменных.1

Отсюда получается важное ограничение на ДНФ. Если f линейно зависит от \(x_i\), то в любую импликанту f должен входить либо \(x_i\), либо \(\neg x_i\). Иначе соответствующая грань содержала бы обе соседние по \(x_i\) вершины, а на них линейно зависящая функция принимает разные значения. Для функции, существенной по всем рассматриваемым переменным, любая максимальная грань поэтому вырождается в отдельную вершину. Её сокращённая ДНФ совпадает с совершенной и является единственной ДНФ на этом фиксированном множестве существенных переменных.1

Монотонные функции

Функция f называется монотонной, если из α≤β следует f(α)≤f(β). Геометрически переход от 0 к 1 в координатах не может превратить единицу функции в ноль.1

Если f монотонно зависит от \(x_i\), простая импликанта не может содержать отрицательный литерал \(\neg x_i\). Если бы он присутствовал, монотонность позволила бы расширить соответствующую грань в направлении \(x_i=1\), и импликанта перестала бы быть простой. Следовательно, все простые импликанты ненулевой монотонной ФАЛ являются монотонными элементарными конъюнкциями, то есть состоят только из неотрицательных переменных.1

Нижние единицы и единственная тупиковая ДНФ

Единичный набор β монотонной функции называют нижней единицей, если каждый строго меньший набор имеет значение 0. Каждой нижней единице β соответствует простая импликанта, состоящая из тех \(x_j\), для которых \(\beta_j=1\). И наоборот, каждая простая импликанта возникает таким образом.1

Поэтому сокращённая ДНФ монотонной функции — дизъюнкция конъюнкций, соответствующих всем нижним единицам. В курсе доказывается, что эта сокращённая ДНФ является единственной тупиковой ДНФ монотонной функции, а все нижние единицы являются ядровыми точками. Отсюда следует, что монотонная ФАЛ является ядровой.1

Пример простыми словами

Функция большинства трёх переменных монотонна. Её нижние единицы — 110, 101 и 011, поэтому простые импликанты равны x1x2, x1x3 и x2x3. Сокращённая ДНФ x1x2 ∨ x1x3 ∨ x2x3 не содержит отрицаний и является единственной тупиковой ДНФ этой функции. Для линейной функции x1⊕x2, наоборот, единичные вершины 01 и 10 не соседствуют, поэтому импликанты должны фиксировать обе существенные переменные.

Частые ошибки
  • Путать линейность и монотонность. В курсе линейная зависимость определяется сменой значения на соседних по переменной наборах, а монотонность — частичным порядком α≤β.
  • Считать, что простая импликанта монотонной функции может содержать отрицание существенной переменной.
  • Из единственности тупиковой ДНФ делать вывод об единственности любой ДНФ. У монотонной функции могут существовать другие, нетупиковые представления.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §5, лемма 5.1, МГУ, факультет ВМК