Основи двійкової арифметики. Порозрядні логічні операції (Булівські операції), Детальна інформація

h

h

h

h

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

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

Означення. Значенням формули T на наборі значень змінних з множини X є:

1) значення змінної x, якщо T є змінною x;

2) f(n)((1, (2, …, (n), якщо T=f(n)(T1, T2, …, Tn), а формули T1, T2, …, Tn мають на цьому наборі значення відповідно (1, (2, …, (n.

Означення. n-місна бульова функція f(n) задається формулою T, якщо всі змінні у формулі T є змінними з множини X, і при будь-якому наборі значень ((1, (2, …, (n) цих змінних x1, x2, …, xn значення формули дорівнює значенню f(n)((1, (2, …, (n).

Звідси випливає інше означення суперпозиції функцій.

Означення. n-місна бульова функція f(n) є суперпозицією функцій f1, f2, …, fn, якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f1, f2, …, fn.

З наведених прикладів 1 і 2 видно, що функція h1(x, y, z) задається формулою ((((x, y), ((y, z)), або в інфіксному записі (x(y)((y(z). Аналогічно функція h2(x, y) задається формулою ((((x, y), ((y, x)), або (x(y)((y(x). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами (, (, (, тобто є суперпозиціями цих функцій.

Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами (, (, (, (, (, (, |, ( записувати не всі необхідні дужки. ****

Суттєві та несуттєві змінні

Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x, y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від y. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.

Означення. Змінна xi функції f(n)(x1, x2, …, xi, …, xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних

((1, (2, …, (i-1, 0, (i+1, …, (n) і ((1, (2, …, (i-1, 1, (i+1, …, (n),

така, що

f(n)((1, (2, …, (i-1, 0, (i+1, …, (n) ( f(n)((1, (2, …, (i-1, 1, (i+1, …, (n).

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

((1, (2, …, (i-1, 0, (i+1, …, (n) і ((1, (2, …, (i-1, 1, (i+1, …, (n)

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

f(n)((1, (2, …, (i-1, 0, (i+1, …, (n) = f(n)((1, (2, …, (i-1, 1, (i+1, …, (n).

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

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

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

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

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

І-елемент АБО-елемент (-елемент НЕ-елемент