Элементы математической логики
Вариант 4
Задание 1.
Задать в явном виде множество β (U) – булеан, если U =
.
Решение:
Булеан – множество всех подмножеств. У множества с мощностью 4 подмножеств будет 
. Тогда
Задание 2.
Даны множества: А = 
; В =
; С = 
,
U =
. Найти множества:
А) 
; б) 
; в) 
; г) С\В ; д) В\А ; е) 
И проиллюстрировать каждое диаграммой Венна.
Решение:
А) 
Б) 
В) 
Г) 
Д) 
Е) 
Задание 3.
Получить СДНФ, СКНФ, полином Жегалкина логической функции f(x, y,z) используя табличное представление функции, если f задана булевой формулой:
F(x, y, z) = 
Решение:
Составим таблицу истинности:
|
X |
Y |
Z |
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
На основе таблицы истинности запишем СДНФ:
.
СКНФ:
.
Полином Жегалкина будем искать методом неопределенных коэффициентов. Общий вид полинома Жегалкина:
Определяем коэффициенты:
Функция примет вид:
.
Итак,
.
Задание 4.
Проверить, является ли полной система функций:
.
Решение:
Составим таблицы истинности:
|
Х |
У |
|
|
|
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
1 |
Проверим принадлежность функций классам Поста.
1) 
2) 
3) 
4) 
5) 
;
.
Составим таблицу Поста:
|
|
|
|
|
| |
|
|
+ |
– |
+ |
– |
– |
|
|
– |
+ |
– |
– |
– |
Так как в каждом столбце есть хотя бы один минус, то система функций полна.