Алгоритм выявления фиктивной переменной

- Для переменной x₁ сравниваются половины столбца значений функции: верхняя и нижняя, так как именно в верхней половине x₁ = 0, а нижней x₁ = 1; если они совпадают, то переменная x₁ фиктивная;

- для переменной x₂ сравниваются четвертины столбца в каждой половине, так как именно в верхних четвертинах x₂ = 0, а в нижних x₂ = 1; если четвертины в каждой половине совпадаю, то переменная x₂ фиктивная;

- и так далее (за четвертинами следуют 1/8, 1/16, …).

Достаточное условие отсутствия фиктивных переменных.Если вес вектора – столбца значений функции нечетен, то функция не может содержать фиктивных переменных.

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

Пример.После удаления фиктивной переменной x₃ имеем

10. Формула как способ задания функции. Равносильные формулы. Основные равносильности

Пусть даны Ф — множество символов функций и Х — множество символов переменных.

База индукции. Если f_i - символ n-местной функции из множества Ф, а x₁, x₂, ... , x_n - переменные из множество Х, то последовательность символов f_i (x₁, x₂, ... , x_n) - формула над Ф и Х.

Индуктивный переход. Если f_j - символ m-местной функции из Ф, а A₁, A₂, ... , A_m — переменные из Х или формулы, то последовательность символов f_j(A₁, A₂, ... , A_n) - формула над Ф и Х, а A₁, A₂, ... , A_m – ее подформулы.

Других формул нет.

Способ записи формул для элементарных булевых функций: c Ù a, b¯ c , `a и т.д.

Формула задает функцию, а функция реализует формулу.

Пример. ( a Å ( c Ù`a ) ) Ú ( b ¯ c). или, если опустить скобки, то формула примет вид: a Å c`a Ú ( b ¯ c).