Способы выявления равносильности булевых функций.

Как табличная запись функции, так и запись функции в СДНФ и в СКНФ являются единственными, поэтому для доказательства равносильности булевых функций используются следующие способы:

1) Сравнение табличных записей функций по всем возможным наборам переменных.

Пример. Доказать тождество f₂₄₈(ABC)= (табл. 1.9,1.10).

Таблица 1.9 Таблица 1.10

A B C f₂₄₈(ABC) A B C B↓C

0 0 0 1 0 0 0 1 0 1

0 0 1 1 0 0 1 0 1 1

0 1 0 1 0 1 0 0 1 1

0 1 1 1 0 1 1 0 1 1

1 0 0 1 1 0 0 1 0 1

1 0 1 0 1 0 1 0 1 0

1 1 0 0 1 1 0 0 1 0

1 1 1 0 1 1 1 0 1 0

248=128+64+32+16+8=2⁷+2⁶+2⁵+2⁴+2³=11111000₂.

Так как значение функций на всех наборах совпадает, то f₂₄₈(ABC)= и тождество доказано.

Способ доказательства равносильности функций по таблицам очень нагляден, но при большом числе n затруднителен.

2) Сравнение СДНФ и СКНФ функций.

Пример. Доказать тождество f₁₉₆(ABC)= ;

196₁₀=128+64+4=2⁷+2⁶+2²=11000100₂.

В индексе функции единиц меньше, чем нулей, следовательно, СДНФ функции имеет более короткую запись, чем СКНФ:

f₁₉₆(ABC)= m₀+m₁+m₅;

= m₀+m₁+m₅.

СДНФ функций совпадают, следовательно, тождество доказано.

Пример. Доказать тождество

F₂₃₇(ABC)= ;

237₍₁₀₎=128+64+32+8+4+1=2⁷+2⁶+2⁵+2³+2²+2⁰=11101101₍₂₎,

так как нулей мало, используем СКНФ:

f₂₃₇(ABC)= М₄ М₁ ;

СКНФ функций совпадают, тождество доказано.

3) Преобразование одной из сравниваемых функций с помощью основных соотношений до полного совпадения с другой. Этот способ не поддается алгоритмизации, и поэтому, если не удалось привести функции к одному виду, то еще нельзя утверждать, что эти функции неравносильны.

Пример. Доказать тождество ;

Тождество доказано.

Свойства функций сложения по модулю 2.

Основные соотношения для функции: :

ассоциативный закон

коммутативный закон

дистрибутивный закон относительно функции конъюнкции

а также

x при n нечетном;

0 при n четном.

n

В справедливости этих соотношений можно убедиться, если вместо подставить СДНФ этой функции:

Пример. Доказать равносильность функций

а) аналитически

б) с помощью таблиц истинности (табл.1.11,1.12) функций:

Таблица 1.11 Таблица 1.12

x y xy x y x+y

0 0 0 0 0 0 0 0

0 1 0 1 1 0 1 1

1 0 0 0 1 1 0 1

1 1 1 0 1 1 1 1

Пример. Доказать равносильность функций с помощью таблиц истинности (табл.1.13, 1.14).

Таблица 1.13 Таблица 1.14

x y x y xy

0 0 1 0 0 0 0 0

0 1 0 0 0 0 1 0

1 0 1 1 0 1 0 0

1 1 0 0 1 1 1 1

Теорема Жегалкина: любая булева функция может быть представлена в виде многочлена

f(x₁ x₂ … x_n)= α₀ α₁ x₁ α₂ x₂ … α_n x_n α_n+1

x₁ x₂ α_n+2 x₁ x₃ … α_N x₁ x₂ … x_n ,

где α₀, α₁, … , α_N - некоторые константы, равные 0 или 1.

Для доказательства воспользуемся основной теоремой, утверждающей, что любую булеву функцию можно записать в виде 2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i .

i=0

Для любого конкретного набора < x₁ x₂ … x_n > из тех наборов, на которых функция принимает значение 1, только один минтерм обращается в единицу, а остальные равны нулю. Поэтому справедлива запись 2ⁿ-1

f(x₁ x₂ … x_n)= α _i m_i .

i=0

От этой формы записи можно перейти к функции в виде полинома через операции и , пользуясь соотношением .

Пример. .

Таким образом, после приведения подобных членов функция f(x₁ x₂ … x_n) будет записана в виде многочлена, при построении которого используются только операции конъюнкции и сложения по mod 2.

Теорема доказана.

Алгоритм построения.

Чтобы булеву функцию, заданную таблицей значений или любым другим способом, представить в виде многочлена, достаточно:

1) записать функцию в виде суммы по mod 2 минтермов, равных единице на тех же наборах, на которых равна заданная функция;

2) все аргументы, входящие в полученное выражение в инверсной форме, заменить с помощью соотношения ;

3) раскрыть скобки и сделать приведение подобных членов с учетом тождества:

x, если n нечетно;

0, если n четно.

n

Пример. Представить в виде многочлена функцию f₁₄(AB):

f₇(AB)= m₀+m₁+m₂= m₀ m₁ m₂=

Пример. Представить в виде многочлена функцию f₉(AB):

f₉(AB)= m₀+m₃= m₀ m₃=

.

На базе функции 1, /\ и строится алгебра Жегалкина, но по своим свойствам она более близка к обычной алгебре и отличается от последней лишь тем, что логическое сложение заменено сложением по mod 2.