Тема 3.4 Полнота множества булевых функций

1. Выразить импликацию через функции системы {1, , }:

Решение:

2. Выразить дизъюнкцию и конъюнкцию через функции системы {-, }.

Решение:

3. С помощью достаточного условия полноты проверить на полноту систему а) {0, v, }; б) {-, }; в) {0, , };г) {1, , }

Решение:

а) {0, v, }II

Принять за систему I: {- ,  }

Выразим операции этой системы через II:

Вывод:

б) {-, }II

Принять за систему I: {1, 0, , }

Выразим операции этой системы через II:

1 ≡

0 ≡

Вывод:

в) {0, , }II

Принять за систему I: {1, 0, , }

Выразим операции этой системы через II:

1 ≡

Вывод:

г) {1, , }II

Принять за систему I: {1, 0, , }

Выразим операции этой системы через II:

0 ≡

Вывод:

4. С помощью теоремы Поста проверить на полноту системы : а){+, V, , -}, б){, , -}, в){, -}, г) {1, 0, -}.

Решение:

а){+, V, , -}

Таблица Поста:

f	T0	T1	S	L	M
x+y
xvy
х˄у

Для строчку заполним без дополнительных исследований.

Столбцы T₀ и Т₁ для всех операций так же заполним непосредственно.

Проверку для S, L, M покажем подробно:

Для функции х+у:

S:

L:

M: составим таблицу истинности:

х	у	х+у
0	0
0	1
1	0
1	1

Для функции xvy:

S:

L:

М: составим таблицу истинности:

х	у	хvу
0	0
0	1
1	0
1	1

Для функции х˄у:

S:

L:

М: составим таблицу истинности:

х	у	ху
0	0
0	1
1	0
1	1

Вывод о полноте:

б){, , -}

Таблица Поста:

f	T0	T1	S	L	M
х˄у
x→y

Для строчку заполним без дополнительных исследований.

Столбцы T₀ и Т₁ для всех операций так же заполним непосредственно.

Проверку для S, L, M покажем подробно:

Для функции х˄у:

S:

L:

M: составим таблицу истинности:

х	у	ху
0	0
0	1
1	0
1	1

Для функции x→y:

S:

L:

М: составим таблицу истинности:

х	у	х→у
0	0
0	1
1	0
1	1

Вывод о полноте:

Таблица Поста:

в){, -}

f	T0	T1	S	L	M
x↔y

Для строчку заполним без дополнительных исследований.

Столбцы T₀ и Т₁ для всех операций так же заполним непосредственно.

Проверку для S, L, M покажем подробно:

Для функции х↔у:

S:

L:

M: составим таблицу истинности:

х	у	х↔у
0	0
0	1
1	0
1	1

Вывод о полноте:

г){1, 0, -}.

Решение:

Таблица Поста:

Все столбцы заполним без дополнительных исследований:

f	T0	T1	S	L	M
1
0

Вывод о полноте:

5. Является ли система {1,0,+,} базисом множества всех булевых функций?

Решение:

Проверим систему на полноту:

Заполним таблицу, используя результаты предыдущих задач

Таблица Поста:

f	T0	T1	S	L	M
1
0
x+y
х˄у

Вывод о полноте:

Проверим систему на независимость (наличие лишних функций):

Вывод:

33