Бульові функції (стр. 2 из 2)

(a₁, a₂, …, a_i-1, 0, a_i+1, …, a_n) і (a₁, a₂, …, a_i-1, 1, a_i+1, …, a_n),

така, що

f⁽ⁿ⁾(a₁, a₂, …, a_i-1, 0, a_i+1, …, a_n) ¹ f⁽ⁿ⁾(a₁, a₂, …, a_i-1, 1, a_i+1, …, a_n).

Змінна x_i називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень

(a₁, a₂, …, a_i-1, 0, a_i+1, …, a_n) і (a₁, a₂, …, a_i-1, 1, a_i+1, …, a_n)

мають місце рівності:

f⁽ⁿ⁾(a₁, a₂, …, a_i-1, 0, a_i+1, …, a_n) = f⁽ⁿ⁾(a₁, a₂, …, a_i-1, 1, a_i+1, …, a_n).

Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну x і несуттєву y. Функція двох змінних, задана як вектор (1111), не має суттєвих змінних.

Еквівалентні формули та закони

Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули x®y і ØxÚy обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул.

Означення. Нехай **** Формули F₁ і F₂ називаються еквівалентними, якщо

2. Бульові функції та комбінаційні схеми

І-елемент АБО-елемент Å-елемент НЕ-елементa a a b r b r b r a r r = aÙb r = aÚb r = aÅb r = Øa

Розглянемо реалізацію бульових функцій у вигляді комбінаційних схем. Найпростішими з них є логічні елементи, відповідні бульовим функціям: кон'юнкції Ù, диз'юнкції Ú, додавання за модулем 2 Å та заперечення Ø. Вони позначаються й зображаються таким чином:

Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон'юнкція, диз'юнкція та додавання за модулем 2.

З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:

a₁ b₁

a₂ b₂

.

.

.

a_n b_m

Тут b_j=f_j(a₁, a₂, …, a_n), j=1, 2, …, m..

Приклади.

1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію Å. Виразимо її за допомогою функцій набору {Ù, Ú, Ø}:

xÅy = xÙØyÚØxÙy.