Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та


Доведення. Покажемо спочатку, що коли множина булевих функцій Р є функціонально повною, то жодне з включень РT



Сторінка13/16
Дата конвертації27.01.2020
Розмір1,37 Mb.
ТипКурс лекцій
1   ...   8   9   10   11   12   13   14   15   16
Доведення. Покажемо спочатку, що коли множина булевих функцій Р є функціонально повною, то жодне з включень РT0, PT1, PL, PS, PM не виконується. Припустимо супротивне, тобто множина Р є функціонально повною, але принаймні одне з наведених включень виконується. Розглянемо випадок, коли РT0 (тобто кожна функція з Р зберігає константу 0). Тоді, за твердженням 6, будь-яка суперпозиція над множиною Р зберігає константу 0. Отже, серед суперпозицій над Р немає жодної булевої функції, що не зберігає константу 0. Оскільки не кожна булева функція зберігає константу 0, то існує булева функція, що не подається як суперпозиція над Р. Таким чином, множина Р не є функціонально повною (що суперечить умові). Отже, якщо множина булевих функцій Р є функціонально повною, то не виконується включення РT0. Аналогічно, використовуючи твердження 6, можна довести, що коли множина Р функціонально повна, то не виконується PT1 (PL, PS, PM). Таким чином, якщо множина булевих функцій Р функціонально повна, то жодне з включень РT0, PT1, PL, PS, PM не виконується.

Тепер покажемо, що коли для множини булевих функцій Р не виконується жодне включення РT0, PT1, PL, PS, PM (тобто серед елементів множини Р є хоч одна функція, що не зберігає константу 1, хоч одна, що не зберігає константу 1, хоч одна нелінійна, хоч одна несамодвоїста й хоч одна немонотонна), то множина Р є функціонально повною. Як відомо, множина булевих функцій, що містить заперечення, диз’юнкцію та кон’юнкцію або заперечення та кон’юнкцію є функціонально повною. Значить, якщо ми доведемо, що заперечення та кон’юнкція подаються як суперпозиції над множиною булевих функцій Р, для якої не виконується жодне з включень РT0, PT1, PL, PS, PM, то з цього випливатимеме, що множина Р є функціонально повною.



Покажемо, що заперечення подається як суперпозиція над Р за умови, що для Р не виконується жодне з включень РT0, PT1, PL, PS, PM. Нехай fn – функція з Р, що не зберігає константу 0 (nN+). Тоді fn(0,…,0)=1. Розглянемо два випадки: а) fn(1,…,1)=1, б) fn(1,…,1)=0.

У випадку а) маємо: fn(0,…,0)=fn(1,…,1)=1, звідки випливає, що функція, котра реалізується формулою fn1(х1,…,х1) (де fn1 – функціональний символ, з яким зв’язана булева функція fn), тотожно рівна 1; позначимо цю функцію h. Тоді h(x1)=fn(х1,…,х1). Функція h є суперпозицією над Р й тотожно рівна 1. За умовою, множина Р містить принаймні одну функцію, що не зберігає константу 1; нехай gm – така функція. Покладемо l(x1)=gm(h(x1),…,h(x1)). Функція l є суперпозицією над P (оскільки реалізується формулою виду gm1(fn1(х1,…,х1),…,fn1(х1,…,х1)), де gm1 – функціональний символ, з яким зв’язана булева функція gm), й l(0)=gm(h(0),…,h(0)) = gm(1,…,1)=0, l(1) = gm(h(1),…,h(1)) = gm(1,…,1)=0. Отже, функція l тотожно рівна 0. За умовою, у множині Р міститься принаймні одна немонотонна функція; нехай sk – така функція. З немонотонності sk випливає, що існують такі набори a1ak та b1bk значень аргументів цієї функції, що a1akb1bk, але sk(a1,…,ak)>sk(b1,…,bk). Виділимо у наборі a1ak усі ті місця (позначимо їх i1,…,ij, 1 jk), на яких у даному наборі стоять нулі, а у наборі b1bk стоять одиниці. Побудуємо послідовність наборів i0, i1,…, ij, таку що i0=a1ak, ij=b1bk, кожні два сусідні набори im, im+1 (0mj-1) у цій послідовності відрізняються значеннями лише на місці im+1: у наборі im на цьому місці стоїть 0, а у наборі im+1 – 1. (Нехай, наприклад, k=5 й маємо набори =10010, =10111. Бачимо, що ; тоді виділені місця мають номери 3 та 5, адже саме на місцях з цими номерами у наборі стоять нулі, а у наборі – одиниці, а на кожному з місць, номер якого відмінний від 3 та 5, у наборах та стоять однакові значення. Тоді маємо таку послідовність наборів 0, 3, 5, де 0==10010, 3=10110, 5=10111=.) Оскільки sk(a1,…,ak)>sk(b1,…,bk), то sk(a1,…,ak)=1, а sk(b1,…,bk)=0. Тоді у послідовності i0, i1,…, ij знайдуться такі два сусідні набори im, im+1 (0mj-1), що на наборі im функція sk набуває значення 1, а на наборі im+1 – значення 0. Замінимо у наборі im+1 одиницю, що стоїть на місці im+1 змінною х1 й позначимо результат заміни через . Покладемо r(x1)=sk().Функція r є суперпозицією над Р. Маємо: r(0)= sk(im)=1, r(1)= sk(im+1)=0. Отже, r є елементарна булева функція заперечення.

У випадку б) маємо: fn(0,…,0)=1, fn(1,…,1)=0. Покладемо h1(x1)=fn(х1,…,х1). Функція h1 є суперпозицією над Р, й h1(0)=1, h1(1)=0, тобто булева функція h1 – це елементарна булева функція заперечення. За умовою, множина Р містить несамодвоїсту функцію (позначимо її gk). Тоді знайдеться такий набір a1ak значень аргументів функції gk, що . Нехай , 1 ik означає х1, якщо аі дорівнює 1, й , якщо аі дорівнює 0. Покладемо h2(x1)= . Оскільки , то h2(0)=h2(1), отже, функція h2 тотожно рівна нулю або тотожно рівна одиниці. Покладемо h3(х1)= h1(h2(х1)). Якщо h2 тотожно рівна нулю, то h3 тотожно рівна одиниці; навпаки, якщо h2 тотожно рівна одиниці, то h3 тотожно рівна нулю.

Таким чином, якщо серед функцій множини Р є функція, що не зберігає константу 0, то серед суперпозицій над Р існує або булева функція тотожно рівна 1, або заперечення. У першому з випадків за наявності у множині Р функції, що не зберігає константу 1, можна знайти таку суперпозицію над Р, що тотожно дорівнює нулю, а потім, скориставшись тим, що Р містить немонотонну функцію, знайти таку суперпозицію над Р, що є запереченням. У другому із зазначених випадків, за наявності несамодвоїстої функції у множині Р можна знайти такі суперпозиції над Р, одна з яких є функцією, що тотожно рівна нулю, а інша є функцією, що тотожно рівна одиниці.



Отже, якщо множина Р містить функцію, що не зберігає константу 0, функцію, що не зберігає константу 1, немонотонну функцію та несамодвоїсту функцію, то існує суперпозиція над Р, що є запереченням, існує суперпозиція над Р, що тотожно дорівнює нулю, а також суперпозиція над Р, що тотожно дорівнює одиниці. Покажемо, що за наявності у множині Р ще й нелінійної функції, можна побудувати таку суперпозицію над Р, що є кон’юнкцією.

За умовою, у множині Р міститься принаймні одна нелінійна функція. Нехай qp – така функція. Оскільки функція qp нелінійна, то у поліномі Жегалкіна, побудованому за qp, знайдеться принаймні одна елементарна кон’юнкція, ранг якої не менше 2. Нехай ця кон’юнкція містить змінні х1, х2. Виділимо у поліномі Жегалкіна функції qp елементарні кон’юнкції, що містять змінні х1, х2, елементарні кон’юнкції, що містять змінну х1 та не містять змінну х2 (якщо такі є), елементарні кон’юнкції, що містять змінну х2 та не містять змінну х1 (якщо такі є), елементарні кон’юнкції, що не містять ні х1, ні х2 (якщо такі є). Тоді функцію qp можна подати у вигляді х1х2s1(х3,…,xp)  х1s2(х3,…,xp)  х2s3(х3,…,xp)  s4(х3,…,xp), причому s1 не є тотожно рівна нулю. Оскільки s1 не є тотожно рівна нулю, то знайдеться такий набір a3ap значень змінних х3,…, xp, що s1(х3,…,xp)=1. Підставимо у вираз х1х2s1(х3,…,xp)  х1s2(х3,…,xp)  х2s3(х3,…,xp)  s4(х3,…,xp) значення a3,…,ap замість змінних х3,…, xp. Матимемо вираз: х1х2ах1bх2c, де a, b, c  {0,1}. Замінимо у цьому виразі х1 на х1b, а х2 – на х2а та виконаємо рівносильні перетворення. Маємо: (х1b)(х2а)  а(х1b)  b(х2а)  с = х1х2bх2ах1аbах1аbbх2аbс = х1х2  (ах1ах1)  (bх2bх2)  (аbаbаbс) = х1х2  (аbс). Розглянемо випадки: 1) аbс = 0 та 2) аbс = 1. У випадку 1 маємо суперпозицію х1х2 над Р. У випадку 2 маємо формулу х1х21 (тобто ). Позначимо через f2 булеву функцію, що реалізується цією формулою. Оскільки f2(х1, х2) = , то – суперпозиція над Р, є кон’юнкцією.

Отже, доведено, що серед суперпозицій над множиною булевих функцій Р, для якої не виконується жодне з включень РT0, PT1, PL, PS, PM, є заперечення та кон’юнкція.

Розглянемо, наприклад, множину булевих функцій {(10101010), (0100)} та перевіримо, чи є вона функціонально повною. Позначимо f1 = (10101010), f2 = (0100). Функція f1 не зберігає константу 0 та не зберігає константу 1, адже f1(0,0,0)=1, f1(1,1,1)=0. Функція f1 не монотонна, адже з нерівності 000<001 не випливає нерівність f1(0,0,0) < f1(0,0,1), оскільки f1(0,0,0) = 1, f1(0,0,1) = 0. Функція f2 несамодвоїста, адже f2(0,0)  . Дійсно, f2(0,0) = 0, = = = 1. Знайдемо поліном Жегалкіна функції f2. Побудуємо спочатку ДДНФ функції f2. Оскільки f2 набуває значення 1 лише на наборі 01 значень аргументів, то ДДНФ функції f2 має вигляд . Маємо: =(х11)х2 = х1х2х2. Бачимо, що у поліномі Жегалкіна функції f2 зустрічається елементарна кон’юнкція х1х2, що має ранг 2. Отже, функція f2 нелінійна. Таким чином, дана множина булевих функцій містить функцію, що не зберігає константу 0, функцію, що не зберігає константу 1, немонотонну функцію, несамодвоїсту функцію, нелінійну функцію. Отже, за теоремою Поста, дана множина булевих функцій є повною.

Множина булевих функцій {(0011), } не є функціонально повною, адже не містить жодної функції, що не зберігає константу 1.




Каталог: bitstream -> 123456789
123456789 -> Тема: Безпека вулиці: азбука дороги
123456789 -> Методичні вказівки до вивчення дисципліни сво «доктор філософії»
123456789 -> Регіональний підхід до дослідження формування ціннісних орієнтацій студентів мистецьких вишів україни н. Г. Тарарак
123456789 -> Методологічне підґрунтя дослідження формування ціннісних орієнтацій студентів вищих навчальних закладів мистецького профілю україни
123456789 -> Загальна характеристика роботи
123456789 -> Інформаційне суспільство в контексті політичної культури суспільства
123456789 -> Заліщицька районна державна адміністрація Відділ з питань освіти Районний методичний кабінет Використання активних та інноваційних технологій як засіб активізації
123456789 -> Україна тернопільська область опис досвіду роботи учителя біології


Поділіться з Вашими друзьями:
1   ...   8   9   10   11   12   13   14   15   16


База даних захищена авторським правом ©pedagogi.org 2019
звернутися до адміністрації

    Головна сторінка