Реферат: Бульові функції

Приклади .

1. h1(x, y, z)=S(Ù; xÚy, y®z) задається наступною таблицею:

x y z	x Úy	y ®z	h1(x, y, z)
0 0 0	0	1	0
0 0 1	0	1	0
0 1 0	1	0	0
0 1 1	1	1	1
1 0 0	1	1	1
1 0 1	1	1	1
1 1 0	1	0	0
1 1 1	1	1	1

2. h2(x, y)=S(Ù; xÚy, y®x) задається таблицею:

x y	x Úy	y ®x	h2(x, y)
0 0	0	1	0
0 1	1	0	0
1 0	1	1	1
1 1	1	1	1

Нехай є множина бульових функцій F. Утворюючи з них та їх суперпозицій усі можливі суперпозиції, ми одержимо множину функцій, яку позначимо [F]. Отже, маємо алгебру ([F]; S), породжену множиною функцій F. Інша множина функцій F₁ буде породжувати, взагалі кажучи, іншу алгебру ([F₁ ]; S). Наприклад, алгебри ([{(0111), (0001)}]; S) і ([{(10), (0001)}]; S).

Розглянемо тепер поняття алгебри формул (термів , або виразів ). Нехай є множина функцій F. Кожній n-місній функції з F поставимо у взаємно однозначну відповідність символ, що її позначає (функціональний символ ) f⁽ⁿ⁾ . Нехай X – зліченна множина змінних (точніше, їх імен).

Означення .

1. Ім'я змінної є формулою.

2. Якщо f⁽ⁿ⁾ – функціональний символ, а T₁ , T₂ , …, T_n є формулами, то f⁽ⁿ⁾ ( T₁ , T₂ , …, T_n ) є формулою.

3. Інших формул немає.

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

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

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

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

2) f⁽ⁿ⁾ (a₁ , a₂ , …, a_n ), якщо T=f⁽ⁿ⁾ (T₁ , T₂ , …, T_n ), а формули T₁ , T₂ , …, T_n мають на цьому наборі значення відповідно a₁ , a₂ , …, a_n .

Означення . n-місна бульова функція f⁽ⁿ⁾ задається формулою T, якщо всі змінні у формулі T є змінними з множини X, і при будь-якому наборі значень (a₁ , a₂ , …, a_n ) цих змінних x₁ , x₂ , …, x_n значення формули дорівнює значенню f⁽ⁿ⁾ (a₁ , a₂ , …, a_n ).

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

Означення . n-місна бульова функція f⁽ⁿ⁾ є суперпозицією функцій f₁ , f₂ , …, f_n , якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f₁ , f₂ , …, f_n .

З наведених прикладів 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. Уточнимо ці міркування наступними означеннями.

Означення . Змінна x_i функції f⁽ⁿ⁾ (x₁ , x₂ , …, x_i , …, x_n ) називається суттєвою , якщо існує хоча б одна пара наборів значень змінних

(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), не має суттєвих змінних.

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