Рівність булевих функцій

Обговорення та вирішення завдань з математики, фізики, хімії, економіки

Часовий пояс: UTC + 3 години [ Літній час ]

Введення в аналіз

Теорія черг (СМО)

Рівність булевих функцій. Фіктивні змінні

Ключовим поняттям теорії булевих функцій є поняття рівних булевих функцій. Для функцій від однієї й тієї кількості змінних [math]n[/math] немає необхідності розглядати якесь спеціальне визначення рівності, бо такі функції рівні, якщо вони збігаються як відображення булева куба [math]\mathbb^n[ /math] у [math]\mathbb[/math] . Проблема полягає в тому, щоб визначити рівність булевих функцій незалежно від кількості змінних.

Приклад 6.4. Розглянемо булеви функції [math]f(x,y)=x\lor y[/math] і [math]g(x,y,z)=xz\lor x\overline\lor yz\lor y\overline[/ math].

Можна помітити, використовуючи тотожності булевої алгебри, що [math]g(x,y,z)=(x\lor y)(z\lor\overline)[/math] , а оскільки [math]z\lor\overline= 1[/math] , то

і функції [math]f[/math] і [math]g[/math] природно розглядати як рівні, незважаючи на те, що вони залежать від різної кількості змінних.

У прикладі 6.4 функцію [math]g[/math] визначено як функцію від трьох змінних, але значення змінного [math]z[/math] не впливає на значення функції. Узагальнюючи ситуацію прикладу, можна запровадити поняття фіктивного змінного булевої функції.

Визначення 6.1. Змінне [math]x_i[/math] називають фіктивним змінним булевої функції [math]f(x_1,\ldots,x_n)[/math] , якщо значення функції залежить від значення цього змінного, тобто. якщо для будь-яких значень змінних

Будемо називати змінне [math]x[/math] , яке не є фіктивним змінним функції [math]f[/math] ,істотним змінним цієї функції і говорити, що функція [math] f [/ math] істотно залежить від змінного [ math] x [ / math] .

Нехай дана булева функція [math]y=f(x_1,\ldots,x_n)[/math] від [math]n[/math] змінних. Нехай істотними змінними цієї функції є змінні [math] x_, \ ldots, x_ [/ math], де [math] r \ leqslant n [/ math] і [math] 1 \ leqslant i_1

Приклад 6.5. а. З табл. 6.4 слід, що мажоритарна функція немає фіктивних змінних, оскільки, наприклад, [math]f(0,0,1)=0[/math] , а [math]f(1,0,1)=1[/ math], тобто. змінне [math] x_1 [/ math] суттєве. Далі [math]f(1,0,0)=0[/math] , але [math]f(1,1,0)=1[/math] , що означає суттєвість змінного [math]x_2[/math ]; для [math]x_3[/math] маємо [math]f(1,0,0)=0[/math] , але [math]f(1,0,1)=1[/math] , що означає суттєвість і цього змінного.

б. Нижче наведено таблицю функції [math]g[/math] від чотирьох змінних (табл. 6.5). Рекомендується перевірити, що змінне [math]x_2[/math] є фіктивним і інші змінні істотні. Більше того, аналіз таблиці показує, що ця функція є не що інше, як мажоритарна функція, що істотно залежить від змінних [math]x_1,\,x_3[/math] і [math]x_4[/math].

6.5>> \\hline & x_1& x_2& x_3& x_4& g(x_1,x_2,x_3,x_4) \\hline \scriptstyle>& 0& 0& 0& 0& 0\\ \scriptstyle>& 0& 0& 0& 1& 0\\ \scriptstyle>& 0& 0& 1& 0& 0\\ \scriptstyle>& 0& 0& 1& 1& 1\\ \scriptstyle>& 0& 1& 0& 0& 0\\ \scriptstyle>& 0& 1& 0& 1& 0\\ \scriptstyle>& 0& 1& 1& 0& 0\\ \scriptstyle>& 0& 1& 1& 1& 1\\ \scriptstyle>& 1&0& 0& 0& 0\\ \scriptstyle>& 1& 0& 0& 1& 1\\ \scriptstyle>& 1& 0& 1& 0& 1\\ \scriptstyle>& 1& 0& 1& 1& 1\\ \scriptstyle>& 1& 1& 0& 0& 0\\ \scriptstyle>& 1& 1& 0& 1& 1\\ \scriptstyle>& 1& 1& 1& 0& 1\\ \scriptstyle>& 1& 1& 1& 1& 1\\\hline \end[/math]

Крім процедури видалення фіктивних змінних використовують і процедуру додавання до безлічі змінних булевої функції однієї або декількох змінних фіктивних. Так, якщо дана функція [math] f (x_1, \ ldots, x_n) \ in \ mathcal

_[/math] , то можна ввести нове фіктивне змінне у, визначивши нову, рівну вихідної, згідно з визначенням 6.2, функцію від [math]n+1[/math] змінного таким чином:

Слід зазначити, що фіктивне змінне можна (у новій функції [math]\widehat[/math] ) "поставити будь-яке місце". Або, точніше кажучи, можна визначити сімейство функцій [math]\widehat_i,

i=\overline[/math] , з фіктивним змінним [math]y[/math] так, що

Поняття фіктивного змінного дозволяє також довільні дві булеві функції розглядати як функції від одного і того ж числа змінних.

Справді, нехай функція [math]f(x_1,\ldots,x_n)[/math] є функція від [math]n[/math] змінних, а функція [math]g(y_1,\ldots,y_m)[/math ] – функція від [math]m[/math] змінних. Позначимо безлічі змінних функцій [math]f[/math] і [math]g[/math] через [math]X[/math] і [math]Y[/math] відповідно. Розширимо безліч змінних функції [math]f[/math] до [math]X\cup Y[/math] , вводячи змінні з [math]Y\setminus Y[/math] (якщо вони існують) як фіктивні. Так само зробимо з функцією [math]g[/math] , додаючифіктивні змінні з множини [math]X\setminus Y[/math] (якщо, звичайно, воно не порожнє). Тоді отримаємо функції [math]f[/math] та [math]g[/math] , рівні, згідно з визначенням 6.2, функцій [math]f[/math] і [math]g[/math] відповідно і визначені як функції від однієї й тієї кількості змінних, що становить потужність об'єднання множин [math]X\cup Y[/math] .

Неважко поширити описану конструкцію на довільну кінцеву множину булевих функцій і вважати цим всі функції цієї безлічі функціями від одного і того ж числа змінних.

Проектуюча функція

На закінчення розглянемо поняття проектуючої функції.

Функцію [math]\operatorname_i[/math] від [math]n[/math] змінних, таку, що [math]\operatorname_i(x_1,\ldots,x_i,\ldots,x_n)=x_i\,,[/math ] називають (i-й) функцією, що проектує. У загальному випадку нумерація безлічі змінних може бути явно не задана, і тоді при визначенні функції проектування слід вказувати не номер відповідного змінного, а саме змінне. У цьому випадку функція, що проектує [math]\operatorname_x^X[/math] з безліччю змінних [math]X[/math] цієї функції і виділеним змінним [math]x\in X[/math] визначається так:

(за трьома крапками "приховані" змінні проектуючої функції, відмінні від змінного [math]x[/math] ).

З визначення випливає, що функція [math]\operatorname_x^X[/math] має єдине істотне змінне, а саме змінне [math]x[/math] . Всі інші змінні функції проектування є фіктивними. Тому будь-які дві функції [math]\operatorname_x^X[/math] і [math]\operatorname_x^Y[/math] рівні, згідно з визначенням 6.2, при будь-яких множинах змінних [math]X[/math] і [math] Y[/math] , що містять змінне[math]x[/math] .

Разом про те для двох різних змінних [math]x[/math] і [math]y[/math] проектують функції [math]\operatorname_x^X[/math] і [math]\operatorname_x^Y[/math] різні функції. Так, [math]\operatorname_1(x_1,x_2)[/math] - функція, відмінна від функції [math]\operatorname_2(x_1,x_2)[/math] оскільки, наприклад, [math]\operatorname_1(1,0) =1,

Надалі домовимося будь-яку з безлічі рівних між собою проектуючих функцій [math]\operatorname_x^X[/math] позначати символом [math]x[/math] її єдиного істотного змінного.

Зауваження 6.3. Таке позначення проектуючих функцій є умовність і певна вільність, яка полягає в тому, що функція, що проектує [math]\operatorname_x^X[/math] як би ототожнюється з самим змінним [math]x[/math] . Проте ототожнення функції і змінного неприпустимо, оскільки поняття змінного, хоч і пов'язані з поняттям функції, не є окремий випадок поняття функції. Змінне - тільки ім'я, якесь позначення, яке використовується при аналітичному завданні функції, але ніяк не сама функція. Проте заради стислості, ми збережемо позначення [math]x[/math] як позначення будь-якої з функцій, що проектують [math]\operatorname_x^X[/math] і будемо використовувати іноді навіть вираз "функція [math]x[/math] ", розуміючи під цим будь-яку із зазначеного сімейства функцій, що проектують.