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



Сторінка4/16
Дата конвертації27.01.2020
Розмір1,37 Mb.
ТипКурс лекцій
1   2   3   4   5   6   7   8   9   ...   16
Контрольні питання

1. Що таке булева функція?

2. Що таке елементарна булева функція?

3. Що таке логічні зв’язки?

4. Що таке n-арний функціональний символ?

5. Що таке формула над множиною функціональних символів?

6. Що таке формула над множиною логічних зв’язок?

7. Що таке функція, що реалізується формулою над множиною функціо-нальних символів?

8. Якими способами подаються булеві функції?

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

І. Булева функція f подана вектором. Подати f у вигляді таблиці.



1. f = (0010) 2. f = (10010011) 3. f = (01100001)

4. f = (11) 5. f = (1001) 6. f (1001110101100101).

II. Чи є поданий вираз формулою над множиною зв’язок S?

1. xyz 2. xy 3. (x)  (y | z)

4. (xy)z 5. x(y) 6. (x)  (yz).

III. Над множиною функціональних символів Ф побудувати формулу, що містить k входжень функціональних символів.

1. Ф = {f0, g1, r2}, k = 7 2. Ф = {f1, f2, f3}, k = 6

3. Ф = {f0, g0, q4}, k = 9 4. Ф = {f1, g1, s1}, k = 5

5. Ф = {h1, g1, r3}, k = 8 6. Ф = {f0, g1, r2}, k = 4.

IV. Подати функцію h у векторній формі.

1. h(x1, x2, x3, x4) = f(x1, x2)  g(x3, x4), де f = (1010), g = (0101)

2. h(x1, x2, x3, x4) = f(x1, x2)  g(x3, x4), де f = (1110), g = (0100)

3. h(x2, x3, x4) = f(g(x3, x4), x2), де f = (1011), g = (1001)

4. h(x1, x2, x3) = f(x1, g(f(x2, x3), x3), де f = (1011), g = (1001)

5. h(x1, x2, x3, x4) = g(f(x1, x2), f(x3, x4)), де f = (0101), g = (1101).

V. Подати функції, що реалізуються заданими формулами над множиною зв’язок S: а) таблицею, б) вектором.

1. (xy)  ((yz)  (zx)) 2. ((  y)  (х  z))  (xy)

3. x  (z  (yxz)) 4. (xy) | (yzxz)

5. (((x|y)  z) | y)  z 6. xy  (x | y)

7. (xyz)  xyz 8. (xy)  (xy)

9. (x | y)  (xy) 10. (xy)  ((yz)  (zx)).



Еквівалентні формули

Нехай F1, F2 – формули над множиною Ф, а {x1,…,xn} – множина усіх тих змінних, кожна з яких зустрічається принаймні у одній з цих формул. Формули F1 та F2 називаються еквівалентними (позначається F1 = F2 або F1F2), якщо на кожному наборі а1аn значень змінних x1,…,xn значення функцій , , що реалізуються формулами F1, F2, збігаються.



Твердження 1. Нехай x, y, z – змінні. Мають місце такі еквівалентності:

x y = y x, де {&, , , , |, }

(x y) z = x (y z), де {&, , , }



= , =

x(x&y) = x, x&(xy) = x

x( &y) = xy, x&( y) = x&y

x&(yz) = (x&y)(x&z)

x(y&z) = (xy)&(xz)

x&(yz) = (x&y)(x&z)

0 = x& = x&0 = xx

1 = x = x1= xx

x = = xx = x&x = x&1 = x0

x = x 1, xy = (xy)1



xy = (x& )( ), xy = ((x&y)  x)  1.

Доведемо, що = . Множина усіх змінних, кожна з яких зустрічається принаймні у одній з формул та – це {x,y}. Розглядатимемо кожний набір значень змінних х, у, обчислюватимемо значення функцій, що реалізуються формулами та , на кожному наборі й порівнюватимемо ці значення. Набори значень змінних х, у та результати обчислень подамо у вигляді таблиці:


x

y





x&y





0

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

0

1

0

1

1

1

1

0

0

1

0

0

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



Зазначимо, що еквівалентності твердження 1 виконуються, якщо замість х, у, z підставити довільні формули F1, F2, F3 над множиною зв’язок S.

Використовуючи еквівалентності твердження 1, доведемо, що ху= . Маємо: ху = ((x&y)  x)  1 = (((x&y)& )(( )&х))  1 =

= ((x&(y& ))(( )&х))  1 = ((x&( &у))(( )&х))  1 =

= ((x& )&у)(( )&х))  1 = ((0&у)(( )&х))  1 =

= ((у&0)(( )&х))  1 = (0(( )&х)) 1 = ((( )&х)0)  1 =

= (( )&х)  1 = ((  )&х)  1 = (х&(  ))  1 = ((х& )(х& ))  1 =

= (0(х& ))  1 = ((х& )0)  1 = (х& )  1 = =  = у. Еквівалентність доведено.



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

1. Які формули називаються еквівалентними?

2. Як перевірити, чи є формули F1, F2 над множиною Ф еквівалентними?

3. Які еквівалентності мають місце для формул над множиною S?



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

І. Довести еквівалентності з твердження 1.

ІІ. Перевірити, чи еквівалентні формули F1, F2.

1. F1 = x  (yz), F2 = (xy)  (xz)

2. F1 = x  (yz), F2 = (xy)  (xz)

3. F1 = x  (yz), F2 = (xy)  (xz)

4. F1 = x  (yz), F2 = (xy)  (xz)

5. F1 = x  (yz), F2 = (xy)  (xz)

6. F1 = x  (yz), F2 = (xy)  (xz)

7. F1 = x  (yz), F2 =(xy)  (xz)

8. F1 = x  (yz), F2 = (xy)  (xz)

9. F1 = x  (yz), F2 = (x  y)  (xz)

10. F1 = x  (yz), F2 = (xy)  (xz).

III. Довести подані еквівалентності, використовуючи еквівалентності твердження 1.

1. xy = (xy)  (x  y)

2. xy = (xy)  (yx)

3. ху = (хух)  у

4. (xy)  ((x  )  (x  у)) = (ху)  ( )

5. х  (xy  ((ху)  у)  z) = y  (xz).

IV. Реалізувати функцію f формулою над множиною зв’язок S1.

1. f = , S1 = {, } 2. f = , S1 = {} 3. f = , S1 = {, }

4. f = |, S1 = {} 5. f = , S1 = {, } 6. f = , S1 = {|}.

Суперпозиції, тотожно істинні й тотожно хибні формули

Нехай Ф – множина, кожен елемент якої є логічна зв’язка чи функціональний символ, нехай Р – множина булевих функцій, що зв’язані з елементами множини Ф. Суперпозицією над множиною Р будемо називати будь-яку булеву функцію, яка реалізується формулою над Ф.



Розглянемо приклад суперпозиції над деякою множиною булевих функцій Р. Нехай Х={x,y,z} Нехай Ф={, f2, g2}. Побудуємо множину булевих функцій Р, зв’язавши з кожним елементом заданої множини Ф деяку булеву функцію. З елементом  множини Ф зв’яжемо булеву функцію заперечення. З функціональним символом f2 з множини Ф зв’яжемо булеву функцію імплікацію, а з функціональним символом g2 з множини Ф зв’яжемо булеву функцію штрих Шефера. Побудуємо деяку формулу над Ф (позначимо цю формулу F). Нехай F= f2(х, g2(х,y)). Знайдемо булеву функцію F, що реалізується формулою F. Формула F має вигляд F = f2(F1,F2), де F1, F2 – формули над Ф й F1=х, F2 = g2(х,y). Булева функція , що реалізується формулою F1 над Ф, – це заперечення, булева функція , що реалізується формулою F2 над Ф, – це штрих Шефера. Функцію F подамо таблицею, обчисливши значення функції для кожного набору значень змінних x та y. Згідно з визначенням множини Р маємо:


х

у







0

0

1

1

1

0

1

1

1

1

1

0

0

1

1

1

1

0

0

1


Отже, заданою формулою F над множиною Ф реалізується бінарна булева функція, що приймає значення 1 на кожному наборі значень змінних, тобто суперпозиція над множиною Р, яку ми побудували – це булева функція, що тотожно рівна 1. Зазначимо, що, оскільки усі булеві функції, котрі зв’язані з функціональними символами з множини Ф, – елементарні, то замість виразу можемо використовувати вираз  (x|y).

Нехай Р – довільна непорожня множина булевих функцій. Побудує-мо ін’єктивне відображення RР множини Р у множину, що складається з функціональних символів та логічних зв’язок таким чином, що коли f – елементарна булева функція з Р, то RР(f) – логічна зв’язка, що є позна-ченням f, а якщо fn-арна функція (nN+) з Р, що не є елементарною, то RР(f) – n-арний функціональний символ (не обов’язково відмінний від імені даної функції). Під суперпозицією над множиною булевих функцій Р нада-лі (якщо не сказано інше) будемо розуміти будь-яку булеву функцію, що реалізується формулою над RР(Р). Нехай, наприклад, задано множину бу-левих функцій {, 1, (00101101)}. Позначимо функцію (00101101) через f3. Тоді RР(Р) = {, 1, f3}. Побудуємо формулу F над множиною функціо-нальних символів {, 1, f3}. Нехай F = f3(f3(x1,x2,x1), x1x2, 1). Знайдемо булеву функцію, що реалізується формулою F. Позначимо її F. Обчисли-мо значення F на наборах значень змінних x1 та x2. Маємо: F(0,0) = f3(f3(0,0,0), 00, 1). Оскільки f3(0,0,0) = 0, 00 = 0, то F(0,0) = f3(0,0,1) = 0; F(0,1) = f3(f3(0,1,0), 01, 1) = f3(1,1,1) = 1; F(1,0) = f3(f3(1,0,1), 10, 1) = f3(1,1,1) = 1; F(1,1) = f3(f3(1,1,1), 11, 1) = f3(1,0,1) = 1. Подамо функцію F у векторній формі: F = (0111).

Назвемо формулу над множиною Ф тотожно істинною (тотожно хибною), якщо функція, що реалізується цією формулою, набуває значення 1 (0) на кожному наборі значень своїх аргументів.

Розглянемо приклади тотожно істинних та тотожно хибних формул. Нехай Ф = {, }. З елементом  множини Ф зв’язана булева функція диз’юнкція, а з елементом  – булева функція імплікація. Розглянемо формулу F1 = х  (ху) над множиною Ф. Покажемо, що функція , що реалізується даною формулою, набуває значення 1 на кожному наборі значень аргументів. Подамо таблицею:


х

у





0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

1

Отже, бачимо з таблиці, що на кожному наборі значень аргументів функція , що реалізується формулою F1, набуває значення 1. Таким чином, формула F1 є тотожно істинною.

Нехай Ф = {&, }. З елементом  множини Ф зв’язана булева функція кон’юнкція, а з елементом  – булева функція заперечення. Розглянемо формулу F2 = x & x над множиною Ф. Покажемо, що функція , що реалізується даною формулою, набуває значення 0 на кожному наборі значень аргументів. Подамо таблицею:




х





0

1

0

1

0

0

Отже, бачимо з таблиці, що на кожному наборі значень аргументів функція , що реалізується формулою F2, набуває значення 0. Таким чином, формула F2 є тотожно хибною.

Розглянемо формулу   ху xz над множиною S. Викори-стовуючи еквівалентності твердження 1, маємо:   ху xz = x(y1)zxy(z1)  хуxz = (xyx)z  (xyz xy)  хуxz = (xyz xz)  (xyzxy)  хуxz = xyz xzxyz xyхуxz = xyz xzxyz  (xyху)  xz = xyz xzxyz 0xz = xyz xzxyz xz = xyz xyzxzxz = (xyz xyz)  (xzxz) = 00 = 0. Таким чином, показано, що формула   ху xz еквівалентна формулі 0, котра реалізується булевою функцією, що є тотожним нулем. Отже, дана формула є тотожно хибна. Зазначимо, що тотожну істинність формул над множиною S також можна доводити за допомогою еквівалентностей твердження 1: якщо показано, що дана формула еквівалентна формулі 1, то така формула є тотожно істинна.


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


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


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

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