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



Сторінка8/16
Дата конвертації27.01.2020
Розмір1,37 Mb.
ТипКурс лекцій
1   ...   4   5   6   7   8   9   10   11   ...   16
Твердження 3. Конституента одиниці l1&…&ln у алфавіті Х приймає значення 1 рівно на одному наборі значень з 2n наборів значень булевих змінних x1,…,xn.

Доведення. Нехай l – конституента одиниці l1&…&ln у алфавіті X. Покажемо, що знайдеться набір a1an значень змінних x1,…,xn, на якому значення l дорівнює одиниці. Побудуємо набір a1an таким чином, що ai=1, якщо li=xi, й ai=0, якщо li= (i= ). На цьому наборі l набуває значення, що дорівнює значенню виразу &…& , де = ai, якщо li=xi, й = ai, якщо li= (i= ). За побудовою набору a1an, маємо, що l набуває значення 1 на цьому наборі.

Таким чином, показано, що l набуває значення 1 принаймні на одно-му наборі значень змінних x1,…,xn. Покажемо, що такий набір лише один. Припустимо, що існує відмінний від набору a1an набір b1bn значень змінних x1,…,xn, на якому l набуває значення 1. Тоді знайдеться принаймні одне число k (1kn) таке, що akbk. Знайдемо найменше таке число і, що aibi (1in). Зазначимо, що літера li має вигляд хі або . Якщо li = хі, то, за побудовою набору a1an, ai=1, але тоді bi=0, отже, для обчислення зна-чення конституенти одиниці l1&…&ln на наборі b1bn маємо вираз виду b1& … &bi-1&0&bi+1&…&bn, й цей вираз набуває значення 0. Якщо li = , то, за побудовою набору a1an, ai =0, але тоді bi =1, отже, для обчислення значення конституенти одиниці l1&…&ln на наборі b1bn маємо вираз виду b1&…&bi-1&(1)&bi+1&…&bn, й цей вираз набуває значення 0. Отже, на наборі значень змінних x1,…,xn, відмінному від a1an, конституента одиниці l набуває значення 0.

Таким чином, доведено, що конституента одиниці l набуває значення 1 на наборі значень змінних x1,…,xn тоді й тільки тоді, коли цей набір збігається з набором a1an, побудованим за описаним вище правилом.

Нехай fn – булева функція від змінних x1,…,xn (nN+), що не є тотожно рівна нулю. Нехай fn подана таблицею, нехай і1,…,ik – усі ті набори значень змінних x1,…,xn, на яких функція fn набуває значення 1 (1ijn, 1jk). За кожним таким набором побудуємо конституенту одиниці таким чином. Нехай j – довільний набір з-поміж і1,…,ik. Нехай j = aj1ajn. Покладемо lj = lj1&…&ljn (1jk), де ljm=xm, якщо ajm=1, й ljm= , якщо ajm = 0. Оскільки lj – конституента одиниці, то lj набуває значення 1 рівно на одному наборі значень змінних x1,…,xn (а саме, на наборі j). Тоді функцію fn можна подати формулою виду L1…Lk, тобто як диз’юнкцію усіх конституент одиниці, котрі утворюються за табличним поданням даної функції.



Твердження 4. Нехай fn – булева функція, що не є тотожно рівна нулю (nN+).Тоді fn є суперпозицією над множиною булевих функцій {, , }.

Доведення. Оскільки функція fn не рівна тотожно нулю, існує принаймні один набір значень аргументів x1,…,xn цієї функції, на якому вона набуває значення 1. Нехай функція fn подана таблицею. Нехай а11а12а1n,…, ak1ak2akn – усі набори значень аргументів функції fn, на яких вона набуває значення 1. За кожним таким набором ai1ai2ain (1ik) побудуємо конституенту одиниці li1&li2&…&lin таким чином: покладемо lij=xj, якщо aij=1, й lij= , якщо aij=0. Функція, що реалізується формулою li1&li2&…&lin, набуває значення 1 на наборі ai1ai2ain значень аргументів x1,…,xn за побудовою. Оскільки li1&li2&…&lin – конституента одиниці, вона набуває значення 1 лише на наборі ai1ai2ain. Тоді функція, що реалізуєть-ся формулою l11&l12&…&l1n  …  lk1&lk2&…&lkn, набуває значення 1 на тих й тільки тих наборах значень аргументів, що належать множині {a11a12a1n, …, ak1ak2akn}. Таким чином, fn подається формулою l11&l12&…&l1n  …  lk1&lk2&…&lkn. Отже, fn є суперпозицією над множиною булевих функцій {, , }.

Наслідок. Будь-яка булева функція fn, що не є тотожно рівна нулю (nN+), подається дднф над множиною змінних Х={x1,…,xn} (nN+).

Доведення. За твердженням 4, функція fn подається формулою F виду l11&l12&…&l1n  …  lk1&lk2&…&lkn, що є диз’юнкцією конституент одиниці у алфавіті Х, тобто F є дднф над множиною змінних Х.

Зазначимо, що будь-яка булева функція fn, тотожно рівна 0, реалізується формулою х1 над множиною булевих функцій {, }.



Контрольні питання

1. Що таке літера?

2. Яка формула називається кон’юнкцією?

3. Яка формула називається диз’юнкцією?

4. Що таке елементарна кон’юнкція (елементарна диз’юнкція)?

5. Що таке ранг елементарної кон’юнкції (елементарної диз’юнкції)?

6. Що таке диз’юнктивна нормальна форма (днф)?

7. Що таке кон’юнктивна нормальна форма (кнф)?

8. Що таке довжина днф (довжина кнф)?

9. Що таке днф (кнф) над множиною змінних Х?

10. Що таке досконала диз’юнктивна нормальна форма (дднф) над множиною зміннх Х?

11. Що таке досконала кон’юнктивна нормальна форма (дкнф) над множиною зміннх Х?

12. Що таке конституента одиниці у алфавіті Х?

Задачі та вправи

І. Знайти днф та кнф формули F та обчислити довжину побудованих форм.



1. F = ((x  ) & ((y v)  )  yz)  (xv)

2. F = ((x yz) & (yv z)  xv)  x

3. F = (x  (y z)) & ((x|y)  z)

4. F = (x  (yz))  (  (y  z))

5. F = (x  ( ))  ( | (xy)).

II. Подати формулу F у вигляді дднф над множиною змінних {x, y, z}.

1. F = xyz 2. F = xyz  xz  zy 3. F = xyz

4. F = xy  yxz 5. F = xy.



ІІІ. Подати формулу F у вигляді дкнф над множиною змінних {x, y, z}.

1. F = (xy) & (yz) 2. F = (xz) & (x  y) & (zy)

3. F = (y z) & x & (z  x) & (y  x) 4. F = xyz 5. F = xz.

ІV. Знайти усі конституенти одиниці функції f та подати f у вигляді дднф над множиною змінних {x, y, z}.

1. f = (01100010) 2. f = (10001110) 3. f = (xy)  yz

4. f = xyxz  (yz) 5. f = x | (y  (xz)).



ПОЛІНОМИ ЖЕГАЛКІНА

Елементарна кон’юнкція називається монотонною, якщо вона не містить символів заперечення (тобто літер виду х або , де х – змінна). Наприклад, елементарна кон’юнкція х1х2х3 монотонна, а елементарна кон’юнкція не є монотонною, оскільки містить літеру .



Поліномом Жегалкіна (поліномом Жегалкіна над множиною змінних Х = {x1,…,xn}) називається формула виду

Р = K1  …  Km (mN+),

де K1,…, Km – попарно різні монотонні елементарні конюнкції над множи-ною змінних Х = {x1,…,xn}. Якщо m = 0, то вважається, що Р = 0. Символ “” у елементарних кон’юнкціях K1,…, Km зазвичай опускається.

Твердження 5. Будь-яка булева функція fn подається поліномом Жегалкіна над множиною змінних {x1,…,xn}.

Доведення. Якщо булева функція fn тотожно рівна нулю, то вона подається поліномом виду 0.

Нехай функція fn не є тотожно рівна нулю. Тоді fn подається у вигляді днф або дднф. Використовуючи еквівалентності:



хy = (xyx)  y, хх = 0, x = x1,

можна перетворити задану днф (дднф) на формулу, що містить лише входження зв’язок &,  та констант 0 й 1, але не містить входжень зв’язок  й . Використовуючи далі еквівалентності:



x&(yz) = (xy)  (xz), ху = ух, (ху)z = x&(y&z),

xx = x, xx = 0, x0 = 0,

можна побудувати формулу виду K1  …  Km (mN+), де K1,…, Km – монотонні елементарні кон’юнкції.

Розглянемо приклад побудови поліному Жегалкіна за формулою у днф. Нехай F = xy  yz. Виконаємо перетворення формули F. Маємо:

F = xy  yz = ((xy)(yz)  (xy))  (yz) = x(y&y)z  (xy)  (y1)z = (x&0)z  (xy)  yz z = 0&z  xyyzz = xyyzz. Отже, поліном Жегалкіна, побудований за формулою F, має вигляд xyyzz.

Поліном Жегалкіна булевої функції fn можна знайти методом невиз-начених коефіцієнтів. Нехай fnбулева функція з аргументами х1,…,хn, що не є тотожно рівна нулю. Розглянемо усі попарно різні монотонні елемен-тарні кон’юнкції рангів 0, 1,…,n над множиною {х1,…,хn}. Таких кон’юнк-цій 2n. Будемо шукати поліном Жегалкіна Р функції fn у вигляді:



P = 011K1  …  mKm,

де m=2n-1, Ki – елементарна кон’юнкція з номером i, ( ). Для того, щоб знайти поліном Р, потрібно визначити 0, 1,…, m (коефіцієнти поліному). Для кожного набору a1an значень аргументів х1,…,хn функції fn побудуємо рівнян-ня виду Р(a1,…,an) = fn(a1,…,an). Таких рівнянь буде стільки, скільки існує різних набо-рів значень аргументів х1,…,хn функції fn (тобто 2n). Отже, матимемо систему 2n рів-нянь з 2n невідомими 0, 1,…, m. Розв’язавши її, визначимо коефіцієнти поліному Р.

Нехай, наприклад, маємо булеву функцію f2, що визначена таким чином: f2(х1,х2)=х1х2(х1х2). Побудуємо усі монотонні елементарні кон’юнкції рангів 0,1,2 над множиною {х1,х2}. Елементарною кон’юнкцією рангу 0 є 1. Монотонні елементарні кон’юнкції рангу 1 такі: х1, х2. Монотонною елементарною кон’юнк-цією рангу 2 є х1х2. Будемо шукати поліном Жегалкіна Р цієї функції у вигляді:



Р = 011х12х23х1х2.

Складемо рівняння для обчислення коефіцієнтів 0, 1, 2, 3:

0110  20  300 = f2(0,0),

0110  21  301 = f2(0,1),

0111  20  310 = f2(1,0),

0111  21  311 = f2(1,1).

Виконавши спрощення у лівих частинах даних рівнянь маємо:

01 = f2(0,0),

0121 = f2(0,1),

0111 = f2(1,0),

01112131 = f2(1,1).

Знайдемо значення функції f2 на усіх наборах значень аргументів х1, х2 цієї функції. Маємо: f2(0,0) = f2(0,1) = f2(1,0) = 1, f2(1,1) = 0, звідки:

01 = 1,

0121 = 1,

0111 = 1,

01112131 = 0.

Тепер з першого рівняння знаходимо: 0 = 1; з другого та третього рівнянь маємо 2 = 0, 1 = 0; з останнього рівняння знаходмо 3 = 1. Отже, поліном Жегалкіна функції f2 має вигляд: Р = 1х1х2 (або Р = х1х21).


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


Поділіться з Вашими друзьями:
1   ...   4   5   6   7   8   9   10   11   ...   16


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

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