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

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

Для монотонной ФАЛ из \(\alpha \le \beta\) следует \(f(\alpha)\le f(\beta)\). Простые импликанты такой функции не содержат отрицаний. Они однозначно соответствуют нижним единицам функции. Сокращённая ДНФ монотонной ФАЛ является её единственной тупиковой ДНФ, а сама функция является ядровой.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 называется монотонной, если из \(\alpha \le \beta\) следует \(f(\alpha)\le f(\beta)\). Геометрически переход от 0 к 1 в координатах не может превратить единицу функции в ноль.1

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

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

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

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

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

Функция большинства трёх переменных монотонна. Её нижние единицы — 110, 101 и 011, поэтому простые импликанты равны \(x_{1}x_{2}, x_{1}x_{3}\) и \(x_{2}x_{3}\). Сокращённая ДНФ \(x_{1}x_{2} \vee x_{1}x_{3} \vee x_{2}x_{3}\) не содержит отрицаний и является единственной тупиковой ДНФ этой функции. Для линейной функции \(x_{1}\oplus x_{2}\), наоборот, единичные вершины 01 и 10 не соседствуют, поэтому импликанты должны фиксировать обе существенные переменные.

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

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

Источники

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