БУЛЕВЫ ФУНКЦИИ

          Пусть I = {0, 1} – множество, состоящее из двух элементов: 0 (ложь) и 1 (истина). Функцией алгебры логики или булевой функцией f : Iⁿ ® I называется произвольная функция f(x₁, x₂, …, x_n) от n аргументов, принимающая значения в I. Будем предполагать, что функции от n переменных определены для всех натуральных чисел n і 0, причем функциями от 0 переменных являются константы 0 и 1.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

         Для того чтобы производить операции над функциями, например, из функций f(x₁, x₂) = x₁ + x₂ - x₁x₂, g(x₁) = 1 - x₁, получить функцию f(x₁, x₂) Ч g(x₁), удобно предполагать, что области определения функций f и g совпадают. С этой целью вводиться понятие несущественной переменной. В данном примере функция g(x) рассматривается как функция от x₁ и x₂, для которой переменная x₂ – несущественная.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

          Определение. Функция f(x₁, …, x_n) зависит существенным образом от аргумента x_i , если существуют такие значения аргументов a₁, …, a_i-1, a_i+1, …, a_n, что f(a₁, …, a_i-1, 0, a_i+1, …, a_n) № f(a₁, …, a_i-1, 1, a_i+1, …, a_n). В противном случае переменная x_i называется несущественной или фиктивной. Две булевы функции называются равными, если одна из другой получается введением или удалением несущественных переменных.
          Несущественные переменные удаляются следующим образом:
          Сначала строится таблица значений функции f(x₁, …, x_n). Затем перебираются пары строк аргументов, на которых значения функции f(x₁, …, x_n) совпадают, и отмечается i-й элемент строк вида
             
          Если, в результате, все элементы некоторого столбца j окажутся отмеченными, то x_i будет несущественной переменной.

      Пример
             f(x₁, x₂, x₃) = x₁ + x₃ + x₁x₂ + x₁x₂ ² mod 2. Здесь x mod 2 обозначает остаток от деления x на 2. Составим таблицу значений:

и не имеет фиктивных элементов.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

          Рассмотрим следующие специальные булевы функции, на основе которых могут быть построены другие:
             0, 1 – константы, могут рассматриваться как булевы функции от любого числа переменных n і 0;
             x₁ – тождественная функция (или проекция x(x, ..., x_n) = x₁);
             Шx₁ = 1 - x₁ – отрицание, обозначается также ;
             x₁ & x₂ = x₁x₂ – конъюнкция;
             x₁ Ъ x₂ = x₁ + x₂ - x₁x₂ – дизъюнкция;
             x₁ Е x₂ = x₁ + x₂ mod 2 – сложение по модулю 2;
             x₁ Ї x₂ = (1 - x₁)(1 - x₂) – стрелка Пирса;
             x₁ ~ x₂ = (1 - x₁)(1 - x₂) + x₁x₂ – эквивалентность;
             x₁ ® x₂ = 1 - x₁ + x₁x₂ – импликация;
             x₁ | x₂ = 1 - x₁x₂ – штрих Шеффера.
          Эти функции можно определить с помощью таблиц истинности:

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

          Пусть F = {f₁, …, f_m} – множество булевых функций. Понятие формулы над F определяется индуктивно:

1. Каждая переменная x_i и каждая булева функция из F являются формулами над F.
2. Если t₁, t₂, …, t_n – формулы над F, то для каждой функции f(x₁, …, x_n) из F выражение вида f(t₁, t₂, …, t_n) являются формулой над F.

          Каждой формуле над F соответствует булева функция, которая называется интерпретацией этой формулы. Интерпретацию, как и формулу, можно определить индуктивно:

1. Интерпретация формулы x_i сопоставляет элементу (a₁, …, a_n) О I ⁿ элемент a_i О I.
2. Интерпретация формулы f(t₁, …, t_n) принимает значения f(t₁(a₁, …, a_k), …, t_n(a₁, …, a_k)), где функции t_i дополняются, в случае необходимости, фиктивными переменными.

      Пример
          Пусть F = {f₁(x₁, x₂) = x₁ + x₂ - x₁x₂, f₂(x₁, x₂) = x₁x₂, f₃(x₁) = 1 - x₁}. Тогда g₁(x₁, x₂, x₃) = x₁ + x₃ - x₁x₃, g₂(x₁, x₂) = 1 - x₁x₂, g₃(x₁) = 1 - x₁² и g₄(x₁, x₂) = 1 - x₁ – формулы над F, ибо
             
          Подставляя x₁, x₂, x₃ О I в формулы, получим значения интерпретаций этих формул.
          Если интерпретацией формулы g является булева функция f, то формула g называется реализацией функции f. Две формулы называются равносильными, если их интерпретации равны.
          Например, формулы x₁ ® (x₂ ® x₁) и 1, над F = {x₁ ® x₂, 1}, равносильны, ибо функция g(x₁, x₂) = (x₁ ® (x₂ ® x₁)) принимает значения 1, для всех x₁, x₂ О I.
          Множество классов равносильных формул составляют булеву алгебру относительно операций:

которая называется алгеброй Линденбаума – Тарского.
          В следующем разделе будет доказано, что все булевы функции реализуемы формулами над F = {&, Ъ, Ш}, поэтому классы равных булевых функций можно рассматривать как элементы этой булевой алгебры.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

      Теорема. Каждая булева функция f : I ⁿ ® I реализуема с помощью формулы над .
          Доказательство. Функция 0 реализуема с помощью формулы: . В общем случае имеет место равенство: , где x¹обозначает x, а . Здесь обозначает логическую сумму всех значений функции y : I ⁿ ® I. Это приводит к равенству, доказывающему теорему: .
          Правая часть этого равенства называется совершенной дизъюнктивной нормальной формой (СДНФ).

      Пример 1
          Найдем СДНФ для функции x₁ Ї x₂. С этой целью составим таблицу истинности:

Так как f(a₁, a₂) = 0 лишь в случае a₁ = 1 и a₂ = 0, то СКНФ будет равна: . Заметим, что СКНФ формулы x₁ ® x₂ будет равна: . Система булевых функций F называется полной, если каждая булева функция реализуема с помощью формулы над F. Поскольку , то имеет место следствие.
          Следствие. Системы функций {Ъ, Ш}, {&, Ш}, {®, Ш} являются полными.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

          Карты Карно – это графическое изображение таблиц истинности.
          Пусть задана функция f(x₁, …, x_n). Подмножество элементов (a₁, …, a_n) О I ⁿ, в которых f(a₁, …, a_n) = 1, называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств вида: I p ґ {a_i} ґ I ^n-p-1 называются кубиками. Кубики будут равны: , для некоторых (s₀, s₁, s_m) и (b₁, …, b_m) О I ⁿ, таких, что s₀ + s₁ + ... + s_m + m = n. Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула
             
будет давать разложение в дизъюнктивную нормальную форму, минимальное по количеству слагаемых. Карты Карно позволяют “увидеть” эти кубики. Для функций двух, трех и четырех переменных они имеют следующие структуры: