Бульові функції, Детальна інформація

f(n)(g1((1,1, (1,2, …, (1,m1), g2((2,1, (2,2, …, (2,m2), …, gn((n,1, (n,2, …, (n,mn)).

Суперпозиція ще позначається як

S(f(n); g1(y1,1, y1,2, …, y1,m1), g2(y2,1, y2,2, …, y2,m2), …, gn(yn,1, yn,2, …, yn,mn)).

Приклади.

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. Інша множина функцій 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 є: