ТЕМА 11. В этом параграфе будут рассмотрены представления ло­гических функций в виде суперпозиций функций И, ИЛИ

B(U) — множество подмножеств U мощности 2ⁿ;

В_n — множество двоичных векторов длины n также мощности 2ⁿ.

В теореме 3-5 участвуют:

то же множество U, но с дополнительным условием n = 2^m (m — любое натуральное число);

В_m — конкретное множество U с этим же условием: |В_m| = 2^m;

множество Р₂(m) логических функций m переменных;

|Р₂(m)| = ;

B(В_m) — множество подмножеств В_m; |B(В_m)| = .

2. Множества В_n и В_m, хотя и имеют одну и ту же природу (состоят из двоичных наборов), использовались в теоремах 3-4 и 3-5 по-разному. В теореме 3-4 была использована структура элементов В_n, благодаря чему над ними оказались возможными поразрядные логические опера­ции. Подмножества В_n не рассматривались. В теореме 3-5 структура элементов В_n не учитывалась, само В_n было выбрано только для естест­венности и наглядности, зато рассматривалась B(В_n) — система под­множеств В_n.

Теоремы 3-4 и 3-5 указывают на тесную связь между множествами и логическими функциями и позволяют переходить от операций над множествами к операциям над функциями и обратно. В частности, они дают возможность непосредственно производить операции над функциями, заданными не формулами, а таблицами или единичными множествами. Из теорем 3-4 и 3-5 следует, что булевы операции над функциями, заданными таблицами, сводятся к поразрядным логическим операциям над столбцами значений функций. Пример приведенв табл. 3-4, содержащей две функции f и g и результаты булевых операций над ними.

Таблица 3-4

x1	x2	x3	f	g	f g	fg

В завершение отметим еще один факт, связывающий логические функции с основными понятиями теории множеств: если (f g) 1, то M_f M_g. Действительно, если (f g) 1, то из определения импли­кации (табл. 3-3, функция ) следует, что ни для какого набора не может быть одновременно f () = 1 и g () = 0, Поэтому если f () = 1, то g () = 1, т. е. если М_f, то М_g и, следовательно, M_f M_g. В таком случае говорят, что функция f имплицирует функ­цию g. При этом если f — элементарная конъюнкция, то f называется импликантом g, а если после удаления буквы f перестает быть импликантом g, то f называется простым импликантом g. Например, для функции х (у z) конъюнкции ху и хz — простые импликанты, а хуz — импликант, но не простой. Отметим, что любая конъюнкция любой ДНФ данной функции является импликантом этой функции.

ДНФ, интервалы и покрытия. Теоретико-множественная интерпре­тация булевой алгебры функций оказывается очень удобным языком для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связан­ные с ДНФ.

Если функция f (x₁,..., х_m) представляется элементарной конъюнк­цией всех m переменных, то M_f содержит ровно один элемент множества В_m. Если же f — элементарная конъюнкция k переменных, где k < m, то M_f содержит 2^m-k двоичных наборов (так как m — k переменных, не вошедших в эту конъюнкцию, несущественны для f и могут прини­мать любые 2^m-k значений, не изменяя f). Множество M_f такой функ­ции f называется интервалом. Например, для m = 4 и f(x₁, х₂, х₃, x₄) = x₂ M_f = {0100, 0110, 1100, 1110} и |M_f| = 2² = 4. В этом слу­чае говорят, что конъюнкция x₂ (точнее, интервал покрывает множество M_f (и все его подмножества). Представление f в виде ДНФ соответствует представлению ее единичного множества в виде объеди-

Таблица 3-5