Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.2. Формы представления булевых функций
Базовые наборы булевых функций
Рассмотренные здесь три метода используются для сравнительно небольшого числа переменных. Если же число их становится слишком большим, требуются более изощренные приемы отбора импликант. Представление функций в СДНФ и СКНФ образованы тремя операциями — дизъюнкцией, конъюнкцией и отрицанием, а СПНФ — сложением по модулю два, конъюнкцией и единицей как операцией. В логике Буля действует принцип суперпозиции, который гласит: любая сложная функция может быть представлена в виде совокупности элементарных функций двух аргументов, например:
F (x1,x2,x3,x4) = ((x1 | x2) → (x2 ∨ x3)) ↓ (x3 + x4) =
= f8{ f11[ f14(x1, x2), f7(x2, x3)], f6[f10(x3, x4), x4]}.
Табл. 1.15 является таблицей истинности для сложной функции F(x1,x2,x3,x4). На всех наборах аргументов, кроме двух, эта функция равна нулю. Поэтому ее можно представить в виде одного конъюнкта, который выражается через операцию вычитания:
F(x1,x2,x3,x4) = x2 ∧ x3 ∧ x4 = (x4 – x3) – x2.
Таблица 1.15
| x1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| x2 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| x3 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| x4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| f14 = x1 | x2 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| f7 = x2 ∨ x3 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| f10 = x3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| f6 = f10 + x4 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| f11 = f14 → f7 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| f8 = f11 ↓ f6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Зададимся вопросом: через какие еще системы логических операций можно выразить произвольно взятую булеву функцию? В связи с этим вопросом определим пять классов функций.
Функция, сохраняющая нулевое значение на нулевом наборе термов: f (0, 0) = 0, определяет 0-класс. К этому классу относятся все элементарные функции с 0 по 7 (см. табл. 1.9).
Аналогично определяется 1-класс, сохраняющий константу 1 на единичном наборе: f (1, 1) = 1. К 1-классу относятся нечетные функции.
Класс линейных функций (2-класс) определяется линейностью полиномиальной формы. Например, эквивалентность является линейной функцией, так как
f9 = 1 + a + b ,
а стрелка Пирса за счет нелинейного слагаемого ab уже не будет являться таковой:
f8 = 1 + a + b + ab.
Класс самодвойственных функций (3-класс) описывается формулой:
f(a, b) = f(a, b).
Таких элементарных функций всего четыре.
Наконец, класс монотонных функций (4-класс) определяется неравенством: f (a, b) ≤ f ' (a', b'), при a ≤ a' , и b ≤ b'.
Например, пусть a = 0, a' = 1, b = 1 и b' = 1, тогда для дизъюнкции будем иметь:
(f7 = a ∨ b = 1) ≤ (f '7 = a' ∨ b' = 1).
И какие бы наборы a, a', b и b' мы ни брали, если выполняются условия a ≤ a' и b ≤ b', всегда будет иметь место f7 ≤ f '7 ; значит, дизъюнкция является монотонной функцией.
Принадлежность элементарной функции к тому или иному классу ( К ) отмечена единицей в табл. 1.16. По этой таблице уже можно определить систему базисных функций.
Таблица 1.16
K f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 3 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 4 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 Система функций является базисной, если она перекрывает нулями все строки 0, 1, 2, 3 и 4 классов. Например, СПНФ образована функциями f1, f6, f15. Для этих трех функций нули стоят во всех пяти строках табл. 1.16. Следовательно, в СПНФ может быть представлена любая сколь угодно сложная функция. СДНФ и СКНФ образованы функциями f1,f7, f10. Перекрытие нулями всех пяти классов достигается уже двумя функциями: либо f1 и f10, либо f7 и f10, т.е. в этих формах имеется некоторая избыточность базисных функций. Каждая из функций — стрелка Пирса (f8) и штрих Шефера (f14) — образует базис.
Итогом теории пяти классов функций является теорема Поста, которая гласит: для того чтобы система функций была базисной, необходимо и достаточно, чтобы она включала в себя хотя бы одну функцию, не принадлежащую 0, 1, 2, 3 и 4 классам (условие наличия нулей на всех строках табл. 1.16). Однако для установления базисной системы функций вовсе необязательно вводить пять классов функций: достаточно знать взаимосвязь между операциями. Коль скоро было установлено, что всякая логическая операция представима через три булевых, требуется лишь выразить эти три через все остальные. На основе таблиц истинности можно убедиться в справедливости следующих равенств:
a → b = a – b,
a + b = a + b = a ~ b = a ~ b = a ~ b,
a = 1 – a = a → 0 = 1 + a = a ~ 0 = a | a = a ↓ a,
a ∧ b = a – b = (a | b) | (a | b) = (a ↓ a) ↓ (b ↓ b),
a ∨ b = a → b = (a | a) | (b | b) = (a ↓ b) ↓ (a ↓ b),
1 = a → a = а ∨ a = a ~ a,
0 = a – a = a ∧ a = a + a.
|
|
