Бульові функції

1 0 0111

1 0 1111

1 1 0100

1 1 11112. h2(x, y)=S(; xy, yx) задається таблицею:

x yxyyxh2(x, y)

0 0010

0 1100

1 0111

1 1111

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

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

Означення.

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

2. Якщо f(n) – функціональний символ, а T1, T2, …, Tn є формулами, то f(n)( T1, T2, …, Tn) є формулою.

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

Це означення задає множину формул із функціональними символами з множини 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).

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