Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 14
Текст из файла (страница 14)
Показать, что всякая бупева функция Дхи), отличная от константы О, представима в виде (-)) К,г где К; (г = 1г ..., в) г=г различные элементарные конъюнкции, каждая из которых содержит не более одного отрицания переменной, а в < 2и 2.32. Пусть функция 7"(хи'), где п > 3, зависит существенно от всех своих переменных и реализуется попиномом Жегапкина степени и. Локазатги что найдутся две такие переменные, отождествление которых уменьшает число существенных переменных ровно на 1. Глава П ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА СИСТЕМ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ 8 1.
Понятия функциональной замкнутости и полноты Замыканием [К) множества К функций алгебры логики называется совокупность всех функций из Рг, являющихся суперпозициями функций из множества Л. Множество Л называется [функционально) за,мкнутьгм, если [К) = К. Замкнутые множества называются также замкнутыми классами. Подмножество Р функций из замкнутого множества К называется (функционально) полным в К, если [Р) = К. Полное в замкнутом классе К множество Р называется базисом класса Л, если для всякого собственного подмножества Р' С Р выполнено [Р') ф К. Подмножество Р функций из замкнутого класса К называется иреднолным классом в К, если [Р) ф К и для всякой функции 7 Е К~,Р выполняется равенство [Р ьз' (Д) = К.
Функции тг и гг назовем конгрузнтными, если одна из них может быть получена из другой заменой переменных (без отождествления). Например, функции ху и уг конгрузнтны, а функции ху и гг не являются конгрузнтными. При рассмотрении вопросов, связанных с замкнутыми классами, бывает удобно указывать по одному представителю из множества попарно конгруэнтных функций. Например, класс (х, у, г, ..., хы хг, ... ), состоящий из всех тождественных функций, будет обозначаться через (х). Если А — некоторое множество функций, то через А(Х") или, короче, через А" будет обозначаться множество всех тех функций из А, которые зависят только от переменных хы хг, ..., хо.
1.1. Построить множество всех функций, зависящих от переменных хы хг и принадлежащих замыканию множества А: Ц А = (х); 2) А = (хг 63 хг); 3) А = (О, х); 4) А = (хгхг); 5) А = (хгхгохгхз '' хзхь); б) А = (хг Ч хг); 7) А = (О, хг - хг):, 8) А = (хьхг, хг Ф хг); 9) .4 = (хг бЗ хг Ф хз); 10) -4 = (хьхг у хгхз у хзхг); 1Ц А = (хг ьо хг Ф хз ег Ц: 12) А = (хгхг); 1 1. Пониизин функциональной замкнутости и иолноюы 61 13) А = (хзхг Р хгхз Р хзхг); 14) А = (хз'4 хг Мхз); 15) А = (хзхг Ч хз). 1.2. Показать, что 7" Е [А], выразив 7" формулой над множеством А: 1) 7'=х, А=(О.,хэу); 2) 7'=хну, А=(х(11); 3)~=х, А=(хну); 4)7'=херах, А=(х-у); 5)7'=О, А=(хубзз); 6)1"=х, А=(ху); 7) у=хчу, А=(хру); 8) 7'=х, А=(хунуг~lзх); 9)~=ху, А=(хуаз); 10) з = хуг Ч 1(х р у у з), А = (ху р уя'4 гх); 11) 7"=хбзуйз, А=(х,хуЧугЧгх); 12*) 7" = х 9 у 9 г, А = (ху Р ура Ух); 13) У = х Е у, А = (ху, х р у); 14) У = х ' 7у, А = (х -+ у): 15) У =ту, А = (хну, хну).
1.3. Выписать все попарно неконгруэнтные функции 7'(х~), принадлежащие замыканию множества А: 1) А=(1,х); 2) А=(ху); 3) А=(х у); 4) А = (ху'1~ уг Ч гх): 5) А = (х Ю у В з й Ц:, 6) А =(хм у Р з); 7) А = (х — > у): 8) А = (ху Р г); 9) А = (ху): 10) А = (х(х'~ у)(у р у)(хМух)). 1.4. Из полной для класса ~А) системы выделить базис; 1) А=(0,1,х); 2) А=(хну,х у., Ц; 3) А=(х, хну, хбубзг); 4) А=(ху, хну, хуЧз); 5) А = (хну, х -э у); 6) А = (ху, ху); 7) А=(хзрувг,хуругргх, х); 8)А=(1,х у,хву~ЭзбзЦ:, 9)А=(ху,хуЧхг); 10) А = (х, х Ч у, х Ч у Ч г, ху 7 г).
1.5. Выяснить, какие из указанных ниже множеств являются замкнутыми множествами: 1) множество всех функций от одной переменной; 2) множество всех функций от двух переменных: 3) множество всех функций Дхы хг, ... х„) таких, что 7'(1, 1, ... ...,1)=1., и>0; 4) множество всех функций Д(хо), и > О, таких, что 7"(1, 1, ... ..., 1) = 0; 5) множество всех симметрических функций, т.е. таких функ- /12...
и1 ций 1" (хз, хг, ..., х„), что для любой подстановки ( .. ' ' ' . ~ спра~й 1г... ~..) ведливо равенство Дхы хг, ..., хн) = 1(хи, х„,,х;„); 6) множество всех функций 7(х") таких, что ~1зу ~ = 2" 7) множество всех функций, выражаемых полиномом Жегалкина не выше первой степени; 62 Гл. П. Залкндудпыс классы и полнота 8) множество всех функций, выражаемых полиномом Жегалкина не выше второй степени; 9) множество всех функций., допускающих представление в виде д. н. ф. и не содержащих отрицаний переменных; 10) множество всех функций, любая д. н. ф.
которых содержит хотя бы одно отрицание переменной; 1Ц множество всех функций )'(яи), п > О, полипом Жегалкина которых содержит 2" — 1 слагаемых; 12) множество всех функций Д(ти), и > О, полипом Жегалкина которых содержит 2" — 1 слагаемых и не содержит 1 в качестве слагаемого; 13) множество всех функций д"(яи), и > 1, таких, что [дУу[ = 1; 14) множество всех функций У(х"), и > 1, таких, что [дУу[ = 1 и 1(1, 1, ..., Ц = О. 1.6. Показать, что: Ц пересечение замкнутых классов является замкнутым классом; 2) объединение двух замкнутых классов, вообще говоря, не является замкнутым классом; 3) разность двух замкнутых классов, вообще говоря, не является замкнутым классом; 4) дополнение непустого и отличного от Рз замкнутого класса К до Рд не является замкнутым.
1.7. Показать, что класс А, предполный в замкнутом классе К, является замкнутым. 1.8. Обосновать следующие свойства замыкания: Ц [[КД = [К): 2) из Кд С Кз вытекает [Кд) С [К,): 3) [Кд Гд Кз) С [Кд) Гд [Кз); 4) [Кд) 0 [Кз) С [Кд дд Кз); 5) [И) = И. 1.9. Выяснить, является ли множество А замкнутым классом. Предполагается, что вместе с каждой функцией 1 из А множеству А пРинадлежат и все фУнкции из Рдп конгРУэнтные 1: Ц А = (О, 1):, 2) А = (т); 3) А = (и, х); 4) А = (1,У); 5) А=(ид ... яа, п=1,2,...); б) А=(яд~В...Юяи, п=1,2, ...); 7) А = (О, тд дд... дд т„, п = 1, 2, ...
); 8) А = (яд йд... до иди-д., и = 1, 2, ... ); 9) А = (О, и, В... Е из„д, и = 1, 2, ... ); 10) А = (О, 1, хд 6Э... йд то ев и, и б (О, 1), и = 1, 2,... ). 1.10. Ц Перечислить все замкнутые классы К С Рз такие, что число попарно не равных функций в К конечно. 2) Перечислить все замкнутые классы К С Рз такие, что число попарно нсконгруэнтных функций конечно. 3) Указать множество А С Рз такое, что для каждого п > 1 число функций из [А), существенно зависящих от переменных хд, ..., х„, равно: а) 1; б) 2. 1" с. Класс самодвойственных функций 1.11.
Ц Локазатгь что если замкнутый класс в Рг содержит функцию, существенно зависящую от и > 2 переменных, то он содержит бесконечно много попарно неконгрузнтных функций. 2) Верно ли, что если замкнутый класс К содержит функцию, существенно зависящую от и > 2 переменных, то для всякого т > и он содержит функцию, существенно зависящук~ от т, переменных? 1.12.
Сведением к заведомо полным системам в Рг показать, что множество А является сюлной системой в Рг. 1) А=(х(у): 2) А=(хууг,(х у)~Зг); 3) А = (х в у, х Ю у Ю г); 4) А = (х -+ у, 7' = [01011110)); 5) А = (О, щ(х') = хгхг М хгхз Ч хзхм х Е у Ю 1); 6) А = (х у, х йз у, хууг); 7) А = (хуанхе, у = (01111110)); 8) А = (хд Ю г1 а 1, 7" = [10110110)); 9) А = (О, 1, х 9 у Ю г, ху В гх 9 гу); 10) А = (х у д г, х Ю у). 1.13. Выяснить, какое из отношений С, З, =, у выполняется для множеств Км Кг из Рг [отношение у означает, что не выполнено ни одно из отношений С, З, =): 1) К1 = [Аг П Аг], Кг = [Аг] П [Аг]; 2) Кг — — [Аз~Аз], Кг = [АД[Аз]; 3) Кг = [Аг 0 (.4 гз Аз)], Кг = [А г 0 Аг] и [Аз 0 Аз]; 4) К1 = [А~ ~Аг], Кг = [Аз]~[Аз гз А ].
1.14. Привести примеры замкнутых классов Км Кг из Рг таких, что Кг С Кг, и таких, что; 1) К, П К, = О, Кг~К, ф- О, [К, С1 К,] = К, ~д К,; 2) Кг П Кг г- И, Кг~К1 г- И, [К1 0 Кг] = К1 0 Кг,' 3) Кг ~ Кг, [Кг~Кг] = Кг~Кг; 4) Кг Г) Кг ~ И., Кг'~Кг ~ И, [Кг~Кг] = Кг1Кг,' 5) К1 Й Кг ~ Я, Кг ~К1 ~ яг. [К1 Ог Кг] = К1 6в Кг. 1.15. Перечислить все предполные классы замкнутого класса; 1)К=[О,х]; 2)К=[0,1]; 3)К=[ту]; 4)К=[хйу]; 5)К=[О,хну]; 6)К=[1,ху]; 7)К=[хйуйг]; 8) К = [х со 'у, 1]. 1.16.
Показать, что для любого замкнутого класса К С Рг выполнено равенство [К 0 (хЦ = К 0 (х). 1.17. Показать, что каждый предполный в Рг класс содержит тождественнукз функцию. 1.18. Показать, что всякий замкнутый класс в Рг, содержащий функцию, отличную от константы, содержит и функцию х. 1.19. Показать, что множество Р всех функций алгебры логики не представимо в виде объединения непустых попарно непересекаюшихся замкнутых классов. 64 1"м П.
Замкнутые. кпассы и поанота 1.20. Доказать, что если замкнутый класс Р2 имеет конечный базис, то всякий базис этого класса конечен. 1.21. Доказать, что если непустой замкнутый класс в Р2 отличен от множеств, состоящих из одних констант, то его нельзя расширить до базиса в Р2. 1.22. Доказать, что в замкнутом классе (х — е уе) содержатся только такие функции из Ря, которые могут быть представлены (с точностью до обозначения переменных) в виде х, 1е' 1(х"), где 1(х") е Рз. 1.23.
Пусть функция е'(х") принадлежит множеству (х — > у] и зависит существенно не менее чем от двух переменных. Доказать, что ~?Уе~ > 2" '. 2 2. Класс самодвойственных функций Функция у(х1, хз, ..., хп) называется самодвойственной, если 1(х1, хз, ..., хп) = 1*(х1, хз,, хп), или, что то же самое, если У(Х1 Х2 °; Сп) — 1(Х1; Х2 ° °; Хп) ° Из этого определения вытекает, что функция является самодвойственной тогда и только тогда, когда на любых двух противоположных наборах значений переменных она принимает противоположные значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
