Тексты лекций / Текст лекции 6

§ 2.4. Классы Поста и замыкание

Функции, сохраняющие 0. Функции, сохраняющие 1. Самодвойственные функции. Монотонные функции. Линейные функции. Классы Поста. Замыкание системы булевых функций.

Базовые понятия и утверждения

1. Функции, сохраняющие 0; функции, сохраняющие 1. Говорят, что булева функ-

ция сохраняет 0, если (0,0,...,0) = 0.

1, , |, ↓ , → , ↔ не сохраняют 0, функции 1, , , , → , ↔ сохра-

няют 1, а функции 0, , |, ↓ , не сохраняют 1.

Очевидно, что определения функций, сохраняющих 0 и 1, можно переформулировать следующим образом: функция сохраняет 0, если ее вектор значений начинается нулем, и функция сохраняет 1, если ее вектор значений оканчивается единицей.

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

Упражнение 2.21. Определить число булевых функций от переменных: а) сохраняющих 1;

б) сохраняющих как 0, так и 1, т.е. содержащихся в пересечении множеств ( ) и

( );

в) содержащихся в объединении множеств ( ) и ( ).

2. Самодвойственные функции. Булева функция называется самодвойственной, если она равна двойственной к ней, т.е. на любом наборе ( ,..., ) значений переменных

( ,..., ) выполняется равенство( ,..., ) = ( ,..., ).

Обозначим через множество всех самодвойственных функций, а через ( ) множество самодвойственных функций от переменных.

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

1

Тема 6 «Классы Поста и замыкание» Олейник Т.А., 2020

б) Среди элементарных функций двух переменных , , , | , ↓ , →, ↔ нетсамодвойственных.Чтобыубедитьсявэтом,достаточносравнитьвекторызначений этих функций с векторами значений функций, двойственных к ним:

( ↔ ) = (1001) = (0110).

Упражнение 2.22. Выяснить, является ли самодвойственной функция ( , , ) =( ↓ ).

3. Монотонные функции. Если для любого ≤ ( = 1,2,..., ), то говорят, что вектор = ( , ,..., ) предшествует вектору = ( , ,..., ), и пишут ̱.

Заметим, что если номер вектора меньше номера вектора (и, значит, в таблице истинности стоит выше ), то это еще не значит, что предшествует . Чтобы выяснить, предшествует ли один вектор другому, нужно, согласно определению, сравнить их координаты (первую с первой, вторую со второй и т.д.).

Пример 4. а) Вектору (1,0) предшествует вектор (0,0) (но не предшествует также меньший его по номеру вектор (0,1)).

б) Вектору (1,0,1) предшествуют векторы (0,0,0), (0,0,1), (1,0,0), (1,0,1).

Если произвольно взять два вектора одной длины, то может оказаться, что ни один из этих векторов не предшествует другому. Например, вектор (0,1,1) не предшествует вектору (1,1,0) и вектор (1,1,0) не предшествует вектору (0,1,1).

Если имеет место хотя бы одно из соотношений ̱ или ̱, то и называют

зовать правило произведения. Вначале выбираем значение (это можно сделать двумя способами - взять 0 или 1), затем выбираем значение (0 или 1) и последним выбираем значение (0 или 1). Следовательно, общее число векторов, предшествующих вектору

(1,0,1,1,0,1,1), равно 2 2 2 2 2 = 32. ►

Упражнение 2.23. Скольким булевым векторам предшествует вектор

(1,0,1,0,0,0,1,0,1)?

Определение. Булева функция называется монотонной, если для любых наборов изначений переменных, таких что ̱, выполняется неравенство ( ) ≤ .

Обозначим через множество всех монотонных функций, а через ( ) множество монотонных функций от переменных.

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

Пример 6. а) Функции 0,1, монотонные, а функция ̄немонотонная, что легко проверить, поскольку для функций одной переменной условие монотонности сводится к выполнению неравенства (0) ≤ (1).

б)Функции , монотонные,а ↔ , | , ↓ , → , немонотонные.Дей-

ствительно, для функций двух переменных условие монотонности сводится к выполнению

2

(1,1) (обратите внимание, что значения (0,1) и (1,0) не сравниваются, так как в паре векторов (0,1),(1,0) ни один не предшествует другому). Для функций , все эти неравенства выполняются, а для остальных элементарных функций двух переменных - нет. Действительно,

для ( , ) = ↔ = (1001) имеем (0,0) > (0,1); для ( , ) = | = (1110) имеем (0,0) > (1,1); для ( , ) = ↓ = (1000) имеем (0,0) > (0,1); для ( , ) = → = (1101) имеем (0,0) > (1,0); для ( , ) = = (0110) имеем (0,1) > (1,1).

Пример 7. Выяснить, монотонна или нет функция = (01010010). ◄ Выпишем таблицу истинности функции (табл. 2.25).

тельно монотонности функции , поэтому переходим к рассмотрению пар с вектором

(0,0,1). Вектор (0,0,1)предшествует векторам (0,1,1), (1,0,1), (1,1,1), при этом (0,0,1) ≤(0,1,1), однакоуже (0,0,1) > (1,0,1).Следовательно,условиемонотонностинарушено, и, значит, функция немонотонна. ►

Упражнение 2.24. Выяснить, монотонна или нет функция = (01010111).

4. Линейные функции.

Определение.Булевафункцияназываетсялинейной,еслиееполиномЖегалкинаимеет степень 0 или 1.

Иначе говоря, функция линейна, если ее можно представить формулой вида =... .

Обозначим через множество всех линейных булевых функций, через ( ) - множество линейных функций от переменных.

Пример 10. а) Все функции одной переменной 0,1, , = 1 линейные.

б)Функции , = , | = 1 , ↓ = 1 и → =̄ = ̄ ̄= 1 линейными не являются. Функции , ↔ == 1 линейные.

Упражнение 2.27. Задать полиномами Жегалкина все линейные функции от двух

Пример 11. Определить, каким из классов Поста принадлежит функция ( , , ) = ( ) ( ↓ ).

◄ Выпишем таблицу истинности функции (табл. 2.28).

3

(0,0,1) = (1,1,0), следовательно, .

(0,1,0) ̱(1,1,0), а (0,1,0) > (1,1,0), следовательно, .

Чтобы определить, линейна ли функция, найдем ее полином Жегалкина методом элементарных преобразований. Выпишем СДНФ функции и упростим ее:

= ̄ ̄ ̄ ̄ = ̄ ( ̄ ) ( ̄ ) = ̄ = = ̄ = ( 1) = .

Поскольку в полиноме Жегалкина есть произведения переменных, то . ► Упражнение 2.28. Определить, каким из классов Поста принадлежит функция

( ,,) = ( ↓ ) ↔ ( ).

5. Замыкание системы булевых функций. Замыкание [ ] системы булевых функций

- это множество всех функций, которые можно задать формулами над .

Заметим что термин «система» используется в дискретной математике как синоним слова «множество».

Пример 12. а) Пусть = {1,}, тогда [ ] = {0,1,,̄}.

б) Замыканием системы = { , ,¬} является множество всех булевых функций , поскольку любая булева функция представима в виде СДНФ или СКНФ.

в) Замыканием системы = {0,1, , } является множество всех булевых функций , поскольку любая булева функция представима в виде полинома Жегалкина.

Определение. Система функций называется замкнутой, если [ ] = .

Классы Поста , , , , являются замкнутыми множествами.

Из этого утверждения (его доказательство приведено во второй части параграфа) вытекает, что если функции , ,..., принадлежат некоторому классу Поста, то любая функция, записанная формулой с использованием только функций этого класса, также будет принадлежать данному классу Поста.

Пример 13. а)Функция = монотонная,посколькуонапредставленаисключительно через дизъюнкцию и конъюнкцию, а эти две функции - монотонные.

б) Функция = ↔ ̄линейная, поскольку она представлена через линейные функции - отрицание, сложение по модулю два и эквивалентность.

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

Пример 14. Доказать, что функцию = (1001) нельзя задать формулой над множе-

ством = { }.

4

◄ Конъюнкция принадлежит кклассу . Класс являетсязамкнутыммножеством, следовательно, любая функция,заданная формулой над егофункциями, сохраняет 0. Функция = (1001) этим свойством не обладает, значит, ее нельзя задать формулой только через конъюнкцию. ►

Упражнение 2.29. Доказать, что функцию нельзя задать формулой над множеством , если:

а) = (1100), = {↔}; б) = (01111101), = { }; в) = 1, = { ,¬}.

Теоретические обоснования

Теорема 2.10. Замыкание обладает следующими свойствами:

1)[ ];

2)[ ] = [ ];

3)( ) ([ ] [ ]);

4)([ ] [ ]) [ ].

Доказательство. Справедливость утверждения (1) непосредственно следует из определения замыкания, поскольку всякая функция реализуется формулой в виде символической записи самой функции.

Справедливостьутверждения(2)вытекаетизиндуктивногоопределенияформулы:всякая функция из [ ] задается некоторой формулой над , а тогда всякая функция из [ ] , которая задается формулой над [ ], задается также некоторой формулой над .

Утверждение (3) очевидно, поскольку, если подмножество , то любая формула над является также формулой над .

Докажемутверждение(4).Возьмемпроизвольнуюфункцию [ ] [ ]. Согласно определению объединения множеств, [ ] или [ ], т.е. можно задать формулой над или формулой над . Но любая формула над ( ) будет формулой и над. Следовательно, [ ], что и требовалось доказать. ■

Теорема 2.11. Классы Поста , , , , являются замкнутыми множествами.

Доказательство.Надодоказать,чтоклассыПостасовпадаютсосвоимизамыканиями. Дляэтогонужно доказать дваутверждения: 1)каждыйклассПостапринадлежит своему замыканию и 2) замыкание каждого класса Поста принадлежит самому классу.

Справедливость первого утверждения непосредственно вытекает из первого свойства замыкания.

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

Базис индукции. Тождественная функция принадлежит всем классам Поста, значит,

5

=( , ,..., ) = ( , ,..., ) = .

4.Покажем, что функция = ( , ,..., ) , если , , ,..., .

Возьмемдвапроизвольныхнабора и значенийпеременных таких,что ̱.Тогда

Таким образом, для любых наборов и таких что ̱, выполняется неравенство

2.20. Доказать, что ни один из классов Поста не содержится в другом.

6

2.22.Показать, что если , то либо немонотонная, либо несамодвойственная.

2.23.Доказать, что функция, двойственная к монотонной функции, монотонна.

2.24. Доказать, что функция, двойственная к линейной функции, линейна.

2.25.Доказать, что пересечение замкнутых классов - замкнутый класс.

2.26.Является ли объединение замкнутых классов замкнутым классом?

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

2.28.Назовем булеву функцию монотонно невозрастающей, если для любых наборов

и значений переменных, таких что ̱, выполняется неравенство () ≥ . Привести пример булевой функции, заданной формулой над множеством монотонно невозрастающих функций, которая не является монотонно невозрастающей.

Замечание. Задача 2.28 объясняет, почему в теории булевых функций не рассматривают монотонноневозрастающие функции. Дело втом,чтоинтерес представляют свойства функций, которые «наследуются» при задании функций формулами, т.е. такие свойства, которые выделяют обладающие ими функции в замкнутый класс. Множество монотонно невозрастающих функций замкнутым не является.

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

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

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

2.33.Найти число линейных функций от n переменных, существенно зависящих ровно от k переменных.

Ответы и указания к упражнениям

7

2.22. Нет. Решение. Функция задается вектором значений ( ,,) = (11001010), двойственная к ней - вектором значений ( ,,) = (10101100), и, значит, ≠ (в частности, (0,0,1) = (0,0,1)). 2.23. 16. 2.24. Последовательно перебрав все пары сравнимых векторов, убеждаемся, что функция монотонна.

2.27.0, 1,  , 1 ,  , 1 ,  , 1 . 2.28 = ( ), принадлежит только . 2.29. а) {↔} , ; б) { } , ; в) { ,¬} , .

8