2.3.2. Равносильность функций. Существенные и несущественные переменные

Выясним, какие из функций алгебры логики будем считать одинаковыми.

Определение

Пусть f и g – функции алгебры логики и х₁, х₂, х_{3, … ,}х_n - совокупность аргументов, входящих, по крайней мере, в одну из этих функций. Мы будем говорить, что f и g равносильны (и писать f = g ), если при всех значениях

(х₁, х₂, х_{3, … ,}х_n) значения f и g совпадают.

В силу определения функции, имеющие одинаковые истинностные таблицы, но отличающиеся обозначениями переменных, равносильными не считаются.

Говорят, что булева функция f существенно зависит от переменной x_i, если существует такой набор значений

a₁, a₂, ..., a_i-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 называют существенной переменной. В противном случае x_i называют несущественной (фиктивной) переменной.

x1	x2	f
0	0	0
0	1	0
1	0	1
1	1	1

Пример. Пусть булева функция f(x₁, x₂) задана следующей таблицей истинности:

Для этой функции переменная х₁ существенна, а х₂ – фиктивная.

В связи с этим иногда пользуются тем, что к аргументам функции всегда можно формально добавить новый аргумент. После этого получится функчия, равносильная исходной, фиктивно зависящая от добав-ленного аргумента.

2.3.3. Реализация функций формулами. Суперпозиция функций

Пусть дано множество булевых функций F = {f₁, f₂, ..., f_n}.

Формулой над F называется выражение вида

F[F] = f(t₁, t₂, ..., t_n),

где и t_i либо переменная, либо формула над F.

Множество F называется базисом, функция f называется главной (внешней) функцией, а t_i называются подформулами.

Определим основную операцию, которую можно производить над функциями алгебры логики, - суперпозицию (или операцию образования сложной функции). Интуитивный смысл этого понятия состоит в том, что в аргумент функции подставляются другие функции, некоторые переменные отождествляются, и эта процедура может повторяться.

Определение1.

Пусть Ф={φ₁(x₁₁, ...,x_1k1), φ₂(x₂₁, ...,x_2k2), ...,φ_m(x_m1, ...,x_mkm)} – конечная система функций алгебры логики. Функция ψ называется элементарной суперпозицией или суперпозицией ранга 1 (обозначение ), если она может быть получена одним из следующих способов:

а) из какой-либо функций , переименованием какой-то из ее переменных x_ij, т.е. имеет вид:

φ_j(x_j1, ..., x_ji-1, y, x_ji+1, ..., x_jki),

где у, в частности, может совпадать с одной из переменных x_en;

б) подстановкой некоторой функции вместо какого-то аргумента x_ji одной из функций :

φ_j(x_j1, ..., x_ji-1, .

Получающаяся в результате функция ψ зависит от аргументов (x_j1, ..., x_ji-1, , т.е. от всех переменных φ_j, φ_e, исключая, быть может, x_ji.

Строгое определение суперпозиции дается по индукции:

Если описан класс Ф^(r) функций, являющихся суперпозицией класса r функций из системы Ф, то класс Ф^(r+1) состоит из элементарных суперпозиций функций из Ф^(r), т.е.

Ф^(r+1) =(Ф^(r))⁽¹⁾.

Суперпозициями функций из Ф называются функции, входящие в какой-либо из классов Ф^(r).

Замечание 1. Множество Ф называется базисом.

Замечание 2. Если функции φ и ψ имеют одинаковые истинностные таблицы, отличаясь только обозначением переменных, то в силу п.а) определения, каждая из них является суперпозицией другой.

Определение 2. Суперпозиция основных функций , X^Y, XvY, называется формулой.

Понятие равносильности формул, введенное ранее, согласуется с определением равносильности функций.

Пример:

Таким образом, всякой формуле однозначно соответствует некоторая функция (F). Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение формулы, при заданных значениях переменных (приписывание истинных значений переменным).

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

x1	x2	x3	x4	x1^x2		F
1	0	1	1	0	0	1	0
1	1	1	0	1	1	1	1
0	0	0	0	0	0	1	1

Всего возможно 2⁴ = 16 интерпретаций формулы F

Отношение равносильности формул является эквивалентностью. Важнейшие из них:

1. ava = a a^a = a

2. avb = bva a^b = b^a

3. av(bvc) = (avb)vc a^(b^c) = (a^b)^c

4. (a^b)va = a (avb)^a = a

5. av(b^c) = (avb)^(avc) a^(bvc) = (a^b)v(a^c)

6. av1 = 1 a^0 = 0

7. av0 = a a^1 = a

8. ¬ ¬a = a

9. ¬(a^b) = ¬av¬b ¬(avb) = ¬a^¬b

10. av¬a = 1 a^¬a = 0.

Все они могут быть проверены построением соответствующих таблиц истинности. Таким образом, <E₂, v, ^, ¬> - , булева алгебра.