Логика. логіка. Математична логіка та теорія алгоритмів

• Название: Математична логіка та теорія алгоритмів
• Анкор: Логика
• Дата: 15.05.2022
• Размер: 1.6 Mb.
• Имя файла: логіка.pdf
• Тип: Навчальний посібник; #530647
• страница: 4 из 18

Теорема 1.4.1. Число всіх наборів значень аргументів булевої функції
)
,...,
,
(
2 1
n
x
x
x
f
дорівнює 2
n
, а число всіх булевих функцій від n змінних дорівнює
n
2 2
1.
n = 1. Задамо табличним способом всі булеві функції від однієї змінної. х
0 0
0 1
1 1
0 1
0 1
Аналітично вони записуються так: (х) = 0, (х) = х, (х) = , (х) =1.

25 2.
n = 2. Знову задамо табличним способом всі булеві функції від двох змінних. Одержимо: х у
0 0 0 0
0 0
0 0
0 0
1 1
1 1
1 1
1 1
0 1 0 0
0 0
1 1
1 1
0 0
0 0
1 1
1 1
1 0 0 0
1 1
0 0
1 1
0 0
1 1
0 0
1 1
1 1 0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 Λ

x

y

V


y

x
→

1
Отже, є 16 булевих функцій від двох змінних. Більшість із них має свої назви і спеціальні позначення, а саме:
(х,у) =0 – тотожний нуль;
(х,у) =1 – тотожна одиниця;
(х,у) =
y
x 
– кон’юнкція (множення) х та у;
(х,у) =
=х|у – заперечення (інверсія) кон’юнкції або штрих Шеффера;
(х,у) =
y
x 
– диз’юнкція (додавання) х та у;
(х,у) =
= х у – заперечення (інверсія) диз’юнкції, або стрілка Пірса;
(х,у) =х→у – імплікація х та у;
(х,у) =
- заперечення (інверсія) імплікації х та у;
(х,у) =у → х – імплікація у та х;
(х,у) =
- заперечення (інверсія) імплікації у та х;
(х,у) =х↔у – еквіваленція х та у;
(х,у)=
=
y
x 
- сума Жегалкіна або додавання за mod2 (заперечення еквіваленції х та у);
(х,у) = х;
(х,у) = - інверсія х;
(х,у) = у;
(х,у) = - інверсія у.
Кожній формулі алгебри висловлень відповідає булева функція (функція
істинності). Чи має місце обернене твердження, тобто, чи для кожної булевої функції існує формула алгебри висловлень, яка реалізує цю функцію?

26
Теорема 1.4.2. Кожна булева функція задається формулою алгебри висловлень, яка містить символи не більш, ніж трьох логічних операцій – кон’юнкції, диз’юнкції, заперечення.
Дійсно, якщо булева функція
)
,...,
,
(
2 1
n
x
x
x
f
=0 – тотожній нуль, то її можна представити, наприклад, у вигляді
1 1
2 1
)
,...,
,
(
x
x
x
x
x
f
n


. Якщо
)
,...,
,
(
2 1
n
x
x
x
f
набуває значення 1 на деяких наборах (нехай m – кількість одиниць булевої функції), то занумерувавши ці набори аргументів будуємо конституенти одиниці:

i
n
i
j
x
K
1



, де
)
2 1
,
1
(
n
m
m
j




Тоді формулою, що реалізує f будедиз’юнкція всіх К
j
:
j
m
j
n
K
x
x
x
f
1 2
1
)
,...,
,
(



, причому вона є досконалою диз’юнктивною нормальною формою.
Не кожна система операцій алгебри висловлень має властивість, визначену теоремою 1.4.2 для системи




 ,
,
. Наприклад, через →, ↔ не можна зобразити всі булеві функції, оскільки не існує такого зображення для булевої функції
, яка мала б значення 0 на наборі (1, 1, …, 1), що складається з одних лише одиниць. На цьому наборі значення кожної з операцій →, ↔, а отже, і їх суперпозицій, дорівнює 1.
Система операцій алгебри висловлень (система булевих функцій) називається функціонально повною, якщо довільну булеву функцію можна зобразити формулою, що містить лише логічні операції (є суперпозицією функцій) даної системи.
Теорема 1.4.3. Наступні системиє функціонально повними:
1)




 ,
,
; 2)



,
; 3)



,
; 4)



,
; 5)



,
0
; 6)


1
,
,

; 7)
 
; 8)
 

Задання булевої функції формулою, що містить лише функції системи


1
,
,

називають поліномом Жегалкіна. Канонічним видом полінома Жегалкіна є наступне представлення булевої функції:
n
n
i
i
i
i
n
x
x
x
k
x
x
k
x
x
k
x
k
x
k
k
x
x
x
f
t
t




















)
,...,
,
(
2 1
12 2
1 12 2
2 1
1 0
2 1
або
n
n
i
i
i
i
n
x
x
x
k
x
x
k
x
x
k
x
k
x
k
k
x
x
x
f
t
t
)
,...,
,
(
2 1
12 2
1 12 2
2 1
1 0
2 1








, де коефіцієнти
 
1
,
0

t
i
i
k
і мають узагальнені індекси, що вказують на їх

27
належність до кон’юнкції (добутку) аргументів
t
i
i
x
x

 ...
(
t
i
i
x
x ...
). Будувати поліноми Жегалкіна можна за допомогою: 1) методу невизначених коефіцієнтів,
2) рівносильних перетворень, 3) досконалої диз’юнктивної нормальної форми
(табличний спосіб).
Приклад 1: Знайти канонічний вид полінома Жегалкіна для заданої функції:
2 1
2 1
)
,
(
x
x
x
x
f


Розв’язання. (спосіб 1) Використаємо, спочатку, метод невизначених коефіцієнтів. Канонічний вид полінома для функції двох змінних має наступний вигляд:
2 1
12 2
2 1
1 0
x
x
k
x
k
x
k
k



, де
 
1
,
0
,
,
,
12 2
1 0

k
k
k
k
. Будемо послідовно підставляти набори значень аргументів в задану формулу та полінном:
0 0
0
)
0
,
0
(



f
і
0 12 2
1 0
0 0
0 0
k
k
k
k
k





, отже
0 0

k
;
1 1
0
)
1
,
0
(



f
і
2 0
12 2
1 0
1 0
1 0
k
k
k
k
k
k






, отже
1 2

k
;
1 0
1
)
0
,
1
(



f
і
1 0
12 2
1 0
0 1
0 1
k
k
k
k
k
k






, отже
1 1

k
;
1 1
1
)
1
,
1
(



f
і
12 2
1 0
12 2
1 0
1 1
1 1
k
k
k
k
k
k
k
k








, отже
1
;
1 1
1 12 12




k
k
;
Підставивши знайдені значення коефіцієнтів одержимо:
2 1
2 1
2 1
x
x
x
x
x
x




(спосіб 2) Застосуємо рівносильні перетворення до заданої функції:
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
1 1
1
)
1 1
1 1
(
1
))
1
(
)
1
((
)
1
(
)
1
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x


































або
2 1
2 1
2 1
2 1
2 1
x
x
x
x
x
x
x
x
x
x








Приклад 2: Знайти канонічний вид полінома Жегалкіна для заданої формули: використовуючи ДДНФ.
Для побудови полінома Жегалкіна функції
)
,...,
,
(
2 1
n
x
x
x
f
, яка не є тотожнім нулем, за допомогою ДДНФ треба:
1) знайти ДДНФ(f),
2) замінити

на

(+),
3) замінити
i
x
на
)
1
(

i
x
,
4) спростити, використовуючи закони:
z
x
y
x
z
y
x
x
x
x
x
x
x














)
(
,
0
,
0 1
1
,
0
,
1

28
Спочатку побудуємо ДДНФ. Для цього побудуємо таблицю істинності для даної формули: А=
0 0
0 0
1 0
0 0
1 1
0 0
0 1
0 1
0 0
0 1
1 1
0 0
1 0
0 0
0 0
1 0
1 1
1 1
1 1
0 1
1 0
1 1
1 1
1 1
Отримаємо два кон’юнктивні одночлени:
,
ДДНФ нашої формули має такий вигляд: А=
Знак диз’юнкції (

) замінимо на знак додавання за mod2 (

) і використаємо рівносильність
. Отримаємо:
Опустимо дужки, знак кон’юнкції (

) замінимо на знак множення ( ):
Скористаємось наступними властивостями виключного додавання
. Отримаємо: А
Виділяють п’ять класів булевих функцій.
Множина булевих функцій:


0
)
0
,...,
0
,
0
(
/
)
,...,
,
(
2 1
0


f
x
x
x
f
T
n
називається класом функцій, що
зберігають нуль.


1
)
1
,...,
1
,
1
(
/
)
,...,
,
(
2 1
1


f
x
x
x
f
T
n
називається класом функцій, що
зберігають одиницю.






n
n
n
x
x
f
x
x
f
x
x
x
f
S
,...,
,...,
/
)
,...,
,
(
1 1
2 1


називається класом
самодвоїстих функцій.


n
i
f
f
x
x
x
f
M
i
i
n
n
n
,
1
,
),
,...,
,
(
)
,...,
,
(
/
)
,...,
,
(
2 1
2 1
2 1












називається класом монотонних функцій.

29
 


n
i
k
x
k
x
k
x
k
k
f
x
x
x
f
L
i
n
n
n
,
1
,
1
,
0
,
/
)
,...,
,
(
2 2
1 1
0 2
1








називається класом лінійних функцій.
Теорема 1.4.4. (Критерій Е. Поста) Система булевих функцій буде функціонально повною тоді і лише тоді, коли вона не міститься в жодному з класів T
0
, T
1
, S, M, L.
Запитання для самоконтролю
1. Що називається булевим вектором? Скільки різних булевих векторів довжини nіснує?
2. Що називається булевою функцією від n змінних? Як вони задаються?
3. Скільки існує різних булевих функцій від n змінних?
4. Які булеві функції однієї змінної визнаєте?
5. Які булеві функції двох змінних існують?
6. Як визначаються штрих Шеффера, стрілка Пірса, сума Жегалкіна?
7. Який зв'язок між булевими функціями та формулами алгебри висловлень?
8. Яка система булевих функцій називається функціонально повною?
9. Які функціонально повні системи ви знаєте?
10. Яку булеву функцію називають поліномом Жегалкіна?
11. Що таке канонічний вид полінома Жегалкіна? Які існують методи для побудови полінома Жегалкіна?
12. Які існують класи булевих функцій?
13. Як визначаються класи функцій, що зберігають нуль (зберігають одиницю)?
Наведіть приклади функцій, що відносяться до цих класів.
14. Як визначаються клас монотонних функцій, клас само двоїстих функцій та клас лінійних функцій? Наведіть приклади булевих функцій, що відносяться до цих класів.
15. В чому суть критерія Поста?
ВПРАВИ
1.26 Знайти значення булевої функції (таблицю істинності), заданої логічною формулою та деяку рівносильну формулу алгебри висловлень: a)




z
y
x
y
z
z
x






; b)








z
y
x
y
z
x
z






; c)








z
z
x
x
y
z
z
x







; d)



 

z
y
x
y
z
x
z






;

30
e)

 


 

z
y
x
y
z
y
x





/
; f)



 

z
y
x
y
z
z
x





/
; g)








z
z
x
x
y
z
x






; h)






z
y
x
y
z
x
z






; i)

 



z
y
x
y
z
x
z






; j)



 

y
z
y
x
y
z
y






1.27Довести функціональну повноту наступних систем операцій алгебри висловлень не використовуючи теорему Поста: а)



,
; б)



,
; в)



,
0
; г)


1
,
,

; д)
 
; е)
 

1.28 Визначити, які з булевих функцій двох змінних належать до класів
M
S
L
T
T
,
,
,
,
1 0
Відповідь оформити у вигляді таблиці.
Обґрунтувати функціональну повноту систем булевих функції прикладу 1.27 опираючись на теорему Е.Поста.
1.29 Довести, що кожна з наступних систем операцій алгебри висловлень не є функціонально повною : а)


1
,
,

; б)



,
; в)



,
; г)



,
1.30 Які формули алгебри висловлень подаються такими поліномами Жегалкіна: a)
1



x
y
x
; b)
y
x
y
x



; c)
1




x
z
y
x
; d)
z
y
x
z
y
x





1.31 Знайти канонічний вид поліномів Жегалкіна, що зображають наступні функції Буля використовуючи метод невизначених коефіцієнтів: a)
y
x
x


; b)
z
x
x
z



; c)


z
x
x
y



; d)


z
y
x
z



1.32. Знайти канонічний вид поліномів Жегалкіна, що зображають наступні функції Буля використовуючи метод рівносильних перетворень: a)






z
x
z
y
x
y
x






;

31
b)

 

x
x
y
x
z




; c)

 

z
x
x
y



; d)


z
y
x
z



1.33 Знайти канонічний вид поліномів Жегалкіна, що зображають наступні функції Буля за допомогою ДДНФ: a)




z
z
y
x
y
x





; b)

 

x
x
y
x
z




; c)


z
x
x
y



; d)

 

y
x
y
x
z




1.34 Потрійною стрілкою Лукасевича назвемо логічну дію
3

яка визначається так: висловлення


3 2
1 3
,
,
x
x
x

істинне тоді й тільки тоді, коли
3 2
1
,
,
x
x
x
- хибні висловлення. Чи буде система {
3

} повною?