Операция замыкания и предполные классы

Замыканием множества М ÍР₂, обозначается [M], называется множество всех булевых функций, полученных суперпозициями из М. Основные свойства замыкания:

• МÍ[M],
• M₁ÍM₂, то [M₁]Í[M₂],
• [[M]]=[M].

Например, [{&,®,Ø}]=P₂, так как согласно доказанной ранее теореме произвольная булева функция может быть представлена булевой формулой.

Замыкание одноэлементного множества { } определим единственной возможной подстановкой:

Таким образом, замыкание рассматриваемого множества содержит ровно две функции: тождественную функцию х и саму функцию отрицания : .

Замыкание двухэлементного множества {0,1} не содержит никаких новых функций кроме констант 0 и 1, поскольку это нульместные функции и никакие подстановки не возможны. Поэтому [{0,1}]={0,1};

Замыкание двухэлементного множества может быть получено подстановками:

и .

Тогда .

Пусть МÍР₂. Операция получения множества [M] из М называется операцией замыкания. Множество М называется функционально замкнутым классом, если [M]=M. Множество всех булевых функций является функционально замкнутым классом.

Пусть М – замкнутый класс в Р₂. DÌM называется функционально полной системой в М, если [D] = M. Множество D называется неприводимой системой, если замыкание любого его собственного подмножества отлично от замыкания D. Например, множество является функционально полной и неприводимой системой в классе , а множества и {0} не являются.

Функции f₁ и f₂ называются конгруэнтными, если одна из них может быть получена из другой заменой переменных (без отождествления). Например, функции и - конгруэнтные, а функции x&y и z&z – нет.

Множество функций QÍР₂ называется предполным классом, если [Q]ÌP₂, и .

Теорема. Предполный класс замкнут.

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

В математической логике рассматривается пять предполных классов.

Класс функций, сохраняющих 0, Т₀

Определение функции, сохраняющей 0:

.

Пусть функция сохраняет 0. Тогда на нулевом наборе значений переменных значение функции равно 0, а на всех остальных наборах значений переменных функция может принимать произвольные значения. Поскольку число строк таблицы равно 2ⁿ, то число строк, на которых функция может принимать произвольные значения равно 2ⁿ-1, число n-местных булевых функций, сохраняющих 0, равно числу слов длины 2ⁿ-1 в двоичном алфавите, те равно числу размещений с повторениями из 2 по 2ⁿ-1. Таким образом, число n-местных булевых функций, сохраняющих 0 равно половине от числа всех n-местных булевых функций. |T₀(n)|= .

Приведенное выше рассуждение, определяющее мощность класса Т₀ означает замкнутость класса. Докажем это явно. Пусть имеется множество . Покажем, что произвольная суперпозиция этих функций также будет сохранять 0. Пусть суперпозиция получена подстановкой функций из заданного множества вместо аргументов функции F. Очевидно, что на нулевом наборе значений переменных каждая из функций суперпозиции обращается в 0. В свою очередь Следовательно, суперпозиция функций, сохраняющих 0 также сохраняет 0. Т.е. класс функций, сохраняющих 0, замкнут и включает функции всех возможных арностей: T₀= . Способ построения таблицы всех n-местных булевых функций подтверждает, что

.

Элементарные булевы функции сохраняют 0. Функция отрицания , импликация, эквивалентность, штрих Шеффера, стрелка Пирса нуль не сохраняют. Из существования функций, не сохраняющих 0 следует, что класс Т₀ не полон в Р₂.

f(x₁,x₂,…,x_n)ÎT₀(n)Ûf(0,0,…,0)=0. T₀= . Неполнота класса Т₀ следует из существования функций, не сохраняющих 0.

Лемма о функции, не сохраняющей 0: Если fÏТ₀, то отождествлением ее переменных или подстановкой функций, сохраняющих 0, из нее можно получить константу 1 или функцию отрицания Øх.

Пример. Получим константу 1 и функцию отрицания из импликации.

.

.

Класс функций, сохраняющих 1, Т₁

f(x₁,x₂,…,x_n)ÎP₂(n) Û f(1,1,…,1)=1.

.

Доказательство замкнутости класса Т₁ аналогично доказательству замкнутости класса Т₀. Мощность класса T₁(n)=|P₂(n)|/2. Неполнота класса Т₁ следует из существования функций, не сохраняющих 1. , а .

Лемма о функции, не сохраняющей 1: Если fÏТ₁, то отождествлением ее переменных или подстановками функций, сохраняющих 1, из нее можно получить константу 0 или функцию отрицания Øх.

Пример. Получим константу 0 и функцию отрицания из функции Å. Тождественная функция и константа 1 сохраняют 1 и, следовательно, могут участвовать в подстановках при доказательстве.

Произведем отождествление переменных, т.е. подстановку переменной x в формулу:

. Отождествлением переменных получили константу 0.

Следующая подстановка позволяет получит функцию отрицания.

.

Не нашли, что искали? Воспользуйтесь поиском по сайту: