Презентация, доклад по математической логике Существенные и фиктивные переменные

переменной xi, если выполняется условие:
f(x1, …, xi-1,0,xi+1, …, xn) ≠ f(x1, …, xi-1,1,xi+1, …, xn).
В этом случае также говорят, что переменная xi  существенная, в противном случае ее называют фиктивной переменной.
Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции

x1 и x3.

Из таблиц истинности видно, что переменная x1 функции f(x1, x2, x3) существенная, так как f(0,x2, x3) ≠ f(1,x2, x3). Переменная x3 фиктивная, так как f(x1, x2, 0) = f(x1, x2, 1).

столбца значений функции: верхняя и нижняя, так как именно в верхней половине x1=0, а в нижней x1=1, если они совпадают, то переменная x1 фиктивна;
– для переменной x2 сравниваются четвертины столбца в каждой половине, так как именно в верхних четвертинах x2 =0, а в нижних x2 =1, если четвертины в каждой половине совпадают, то переменная x2 фиктивна;
– и так далее (за четвертинами следуют 1/8, 1/16, … ).

столбца значений функции (0011) не равна нижней половине (1100).
Переменная x2 существенна, так как четвертины уже в первой половине различаются (00 и 11).
Переменная x3 фиктивна, так как осьмушки во всех четвертинах равны (0 и 0, 1 и 1, 1 и 1, 0 и 0).

функция не может содержать фиктивных переменных.

истинности всех строк, в которых xi = 0 (или всех строк, в которых xi = 1), и столбца xi.
Пример (функция та же). Применив алгоритм для удаления фиктивной переменой x3, получаем результат

полученные из исходных удалением фиктивных переменных

Рассмотрим функции f1(x1, x2) и f2(x1, x2).
Удалив фиктивную переменную x1 функции f1(x1, x2) и фиктивную переменную x2 функции f2(x1, x2), получим равные функции f1(x2)=f2(x1)=f(x).
Значит, исходные функции равны с точностью до фиктивных переменных.