15.2. Класс булевых функций, сохраняющих константу 1

Определение. Булева функция сохраняет константу 1 (принадлежит классу T1), если на наборе из всех единиц функция принимает значение единица.

Примеры. Мажоритарная булева функция сохраняет константу 1. Из элементарных булевых функций таковыми являются, например, дизъюнкция и конъюнкция. Не сохраняют константу 1, например, штрих Шеффера и стрелка Пирса. •

Утверждение о числе булевых функций класса T1. Число различных булевых функций, зависящих от n переменных и сохраняющих константу 1, равно 22n –1.

Пример. Из всех 16 булевых функций двух аргументов x1, x2 8 функций (222 –1) принадлежат классу T1: 1, , , , , и тождественные функции x1 и x2 . •

Теорема о замкнутости класса T1. Множество всех булевых функций, сохраняющих константу 1, является замкнутым классом.

Доказательства утверждения и теоремы аналогичны доказательствам соответствующих результатов для класса T0.