2.4 Действительные и фиктивные функции

Булевы переменные могут быть действительными или фиктивными.

Переменная x_i действительна (существенна), если значение функции f₁(x₁,x₂,…,х_n) существенно изменяется при изменении x_i.

Переменная x_i фиктивна (несущественна), если значение функции f₁(x₁,x₂,…,х_n) не изменяется при изменении x_i.

Например, в таблице 2.2 функция y₃ = f(x₁, x₂) от изменения х₂ не зависит, т.е. является вырожденной, то же у₀, у₃, у₅, у₁₀, у₁₂, у₁₅.

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

Правило: Для нахождения несущественных (фиктивных) переменных таблично заданной функции алгебры логики, выписываем отдельно подмножества f(x)=l и f(x)=0. Для проверки фиктивности переменной x_i, вычеркиваем ее столбцы. Если при этом в обоих подмножествах не появились одинаковые наборы, значит x_i несущественна (фиктивна).

Пример. Пусть функция задана таблицей истинности (см. таблицу 2.3).

Таблица 2.3-Таблица истинности

X1	X2	X3	f(x1, x2, x3)	X1	X2	X3	f(x1, x2, x3)
0 0 0 0	0 0 1 1	0 1 0 1	0 0 1 1	1 1 1 1	0 0 1 1	0 1 0 1	1 1 0 0

Для определения существенных или фиктивных функций, проведем разбиение наборов f(x)=l и f(x)=0.

Единичные наборы	Нулевые наборы
010 011 100 101	000 001 110 111

Вычеркнем в наборах второй столбец - x₂. В нулевых и единичных столбцах появились одинаковые наборы. Значит x₂ - существенна. Вычеркнем столбец x₃. Одинаковых наборов нет. Значить x₃ - несущественна.

2.5 Определение общего числа функций

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

Теорема. Число N различных функций алгебры логики, зависящих от n аргументов (переменных), конечно и равно N=2 . Для доказательства теоремы рассмотрим таблицу 2.4 для n переменных.

Наборы переменных назовем кортежами. При таком упорядочивании кортежей, слева стоит нулевой набор, справа - единицы.

Таблица 2.4-Число всех функций для n переменных

X1 X2 X3 … Xn	0 1 0 1 0 1 0 1…0 1 0 0 1 1 0 0 1 1…1 1 0 0 0 0 1 1 1 1…1 1 …………………… 0 0 0 0 0 0 0 0…1 1	Число возможных наборов 2n
Y0 Y1 Y2 Y3 … Y2n-1	0 0 0 0 0 0 0 0…0 0 0 0 0 0 0 0 0 0…0 1 0 0 0 0 0 0 0 0…1 0 0 0 0 0 0 0 0 0…1 1 …………………… 1 1 1 1 1 1 1 1…1 1	Число всех функций =2

В нижней части стоят значения функций Y_i для каждого возможного набора n переменных. Общее число таких наборов равно 2ⁿ. Задавая тот или иной конкретный двоичный набор n-переменных, мы тем самым задаем одно из возможных {0,1} значений функции Y_i. Но так как двоичная функция Y_i задается двоичным числом с разрядностью 2ⁿ,то общее число N различных функций будет равно

N = 2 , т.e. i =0, 1, 2, ..., 2 -1.

Теорема доказана.

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