|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
Ответ:
Как видно из таблицы, значения правой и левой части равенства действительно
совпадают, значит, функции в данной формуле эквивалентны.
Определить к каким классам
(константы нуля, константы единицы, самодвойственных функций, монотонных
функций, линейных функций, симметрических функций) относится функция следующего
вида:
Обозначим:
Решение:
1 Составим
таблицу истинности:
|
|
|
|
|
|
|
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
2 Т.
к. f(0,0,0) ¹
0, значит, данная функция не относится к классу константы 0.
3 Т.
к. f (1,1,1) =
0, значит, данная функция относится к классу не сохраняющих константу 1.
4 Т.
к. f(0,1,1) <
f (0,1,0) и f(1,0,0)
= f(0,1,1),
значит, данная функция не относится к классу монотонных функций.
5 Т.
к., например, f(0,0,0)
¹
f(1,1,1) или f(0,0,1)
¹
f(1,1,0), то данная
функция относится к классу самодвойственных функций.
6 Т.
к. не выполняется условие f(0,1,1)
= f(1,0,1) = f(1,1,0)
(значения соответственно равны 0,0,1), то данная функция не относится к классу
симметрических функций.
7 Проверим
принадлежность функции к классу линейных функций.
Для этого запишем ее в таком виде:
Найдем коэффициенты Ci
:
f
(0,0,0) = 1 (из таблицы истинности)
, т.о., С0
= 1.
f(1,0,0
)= 0 (из таблицы истинности)
, т.о., С1
= 1.
f(0,1,0)
= 1 (из таблицы истинности)
, т.о., С2
= 0.
f(0,0,1)
= 0 (из таблицы истинности)
,т.о., С3
= 1.
Тогда f1(x1,x2,x3)
= 1.
Сравним значения функций f
и f1
по таблице истинности:
|
|
|
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
Т. к. значения функций различны для одинаковых
наборов, то данная функция не относится к классу линейных функций.
Ответ: данная
функция относится к классу константы 1.
Необходимо для данной ФАЛ f(x1,x2,x3,x4)
найти ее ДСНФ, КСНФ, ПСНФ, ЭСНФ, ИСНФ, принимающей значение 1 на следующих
наборах:
4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
15.
Решение:
1 Составим
таблицу истинности:
№
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
2
|
0
|
0
|
1
|
0
|
0
|
3
|
0
|
0
|
1
|
1
|
0
|
4
|
0
|
1
|
0
|
0
|
1
|
5
|
0
|
1
|
1
|
1
|
6
|
0
|
1
|
1
|
0
|
1
|
7
|
0
|
1
|
1
|
1
|
1
|
8
|
1
|
0
|
0
|
0
|
1
|
9
|
1
|
0
|
0
|
1
|
1
|
10
|
1
|
0
|
1
|
0
|
1
|
11
|
1
|
0
|
1
|
1
|
1
|
12
|
1
|
1
|
0
|
0
|
1
|
13
|
1
|
1
|
0
|
1
|
1
|
14
|
1
|
1
|
1
|
0
|
0
|
15
|
1
|
1
|
1
|
1
|
1
|
2 Для
получения ДСНФ, ПСНФ используем термы для 1 значений функции:
3 Для
получения КСНФ, ЭСНФ используем термы для 0 значений функции:
Используя метод неопределенных коэффициентов,
необходимо найти МДНФ функции f(x1,x2,x3),
принимающей значение 1 на наборах:
0, 3, 4, 7.
Решение:
1. Составим таблицу истинности:
№
|
|
|
|
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
2
|
0
|
1
|
0
|
0
|
3
|
0
|
1
|
1
|
1
|
4
|
1
|
0
|
0
|
1
|
5
|
1
|
0
|
1
|
0
|
6
|
1
|
1
|
0
|
0
|
7
|
1
|
1
|
1
|
1
|
2.
К10 \/ К20
\/ К30 \/ К1200 \/ К1300
\/ К2300 \/ К123000 = 1
К10 \/ К20
\/ К31 \/ К1200 \/ К1301
\/ К2301 \/ К123001 = 0
К10 \/ К21
\/ К30 \/ К1201 \/ К1300
\/ К2310 \/ К123010 = 0
К10 \/ К21
\/ К31 \/ К1201 \/ К1301
\/ К2311 \/ К123011 = 1
К11 \/ К20
\/ К30 \/ К1210 \/ К1310
\/ К2300 \/ К123100 = 1
К11 \/ К20
\/ К31 \/ К1210 \/ К1311
\/ К2301 \/ К123101 = 0
К11 \/ К21
\/ К30 \/ К1211 \/ К1310
\/ К2310 \/ К123110 = 0
К11 \/ К21
\/ К31 \/ К1211 \/ К1311
\/ К2311 \/ К123111 = 1
3 Приравняем
0 все коэффициенты при 0 значениях функции:
К10 = К20
= К31 = К1200 = К1301
= К2301 = К123001 = 0
К10 = К21
= К30 = К1201 = К1300
= К2310 = К123010 = 0
К11 = К20
= К31 = К1210 = К1311
= К2301 = К123101 = 0
К11 = К21
= К30 = К1211 = К1310
= К2310 = К123110 = 0
4 Вычеркнем
0 коэффициенты из коэффициентов при 1 значениях функции:
К2300 \/ К123000
= 1
К2311 \/ К123011
= 1
К2300 \/ К123100
= 1
К2311 \/ К123111
= 1
5 Найдем
минимальное покрытие: К2300 и К2311
,т. е.
f1(x1,x2,x3)
=
6. Проверка:
№
|
|
|
|
|
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
2
|
0
|
1
|
0
|
0
|
0
|
3
|
0
|
1
|
1
|
1
|
1
|
4
|
1
|
0
|
0
|
1
|
1
|
5
|
1
|
0
|
1
|
0
|
0
|
6
|
1
|
1
|
0
|
0
|
0
|
7
|
1
|
1
|
1
|
1
|
1
|
Т.к. f
=f1,
то преобразования выполнены верно.
Ответ: f1(x1,x2,x3)
= .
Используя метод Квайна, необходимо найти МДНФ
функции f(x1,x2,x3,x4),
принимающей значение 1 на наборах: 3, 4, 5, 6, 13, 14, 15.
Решение:
1. Составим таблицу истинности:
№
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
2
|
0
|
0
|
1
|
0
|
0
|
3
|
0
|
0
|
1
|
1
|
1
|
4
|
0
|
1
|
0
|
0
|
1
|
5
|
0
|
1
|
0
|
1
|
1
|
6
|
0
|
1
|
1
|
0
|
1
|
7
|
0
|
1
|
1
|
1
|
0
|
8
|
1
|
0
|
0
|
0
|
0
|
9
|
1
|
0
|
0
|
1
|
0
|
10
|
1
|
0
|
1
|
0
|
0
|
11
|
1
|
0
|
1
|
1
|
0
|
12
|
1
|
1
|
0
|
0
|
0
|
13
|
1
|
1
|
0
|
1
|
1
|
14
|
1
|
1
|
1
|
0
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
2 Выпишем
термы для 1 значений функции и склеим все возможные:
3 Составим
таблицу и найдем минимальное покрытие:
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
+
|
+
|
|
|
|
|
|
|
+
|
|
+
|
|
|
|
|
|
|
+
|
|
+
|
|
|
|
|
|
|
+
|
|
+
|
|
|
|
|
|
|
+
|
|
+
|
|
|
|
|
|
|
+
|
+
|
В данном случае следующие импликанты являются
существенными:
3
Проверка:
№
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
0
|
1
|
0
|
0
|
0
|
3
|
0
|
0
|
1
|
1
|
1
|
1
|
4
|
0
|
1
|
0
|
0
|
1
|
1
|
5
|
0
|
1
|
0
|
1
|
1
|
1
|
6
|
0
|
1
|
1
|
0
|
1
|
1
|
7
|
0
|
1
|
1
|
1
|
0
|
0
|
8
|
1
|
0
|
0
|
0
|
0
|
0
|
9
|
1
|
0
|
0
|
1
|
0
|
0
|
10
|
1
|
0
|
1
|
0
|
0
|
0
|
11
|
1
|
0
|
1
|
1
|
0
|
0
|
12
|
1
|
1
|
0
|
0
|
0
|
0
|
13
|
1
|
1
|
0
|
1
|
1
|
1
|
14
|
1
|
1
|
1
|
0
|
1
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
1
|
Т. к. f1
= f, то
преобразования выполнено верно.
Ответ:
Используя метод Квайна- Мак - Класки ,
необходимо найти МДНФ функции f(x1,x2,x3,x4),
принимающей значение 1 на наборах: 2, 6, 7, 10 ,12 ,13 14, 15.
Решение:
1. Составим
таблицу истинности:
№
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
2
|
0
|
0
|
1
|
0
|
1
|
3
|
0
|
0
|
1
|
1
|
0
|
4
|
0
|
1
|
0
|
0
|
0
|
5
|
0
|
1
|
0
|
1
|
0
|
6
|
0
|
1
|
1
|
0
|
1
|
7
|
0
|
1
|
1
|
1
|
1
|
8
|
1
|
0
|
0
|
0
|
0
|
9
|
1
|
0
|
0
|
1
|
0
|
10
|
1
|
0
|
1
|
0
|
1
|
11
|
1
|
0
|
1
|
1
|
0
|
12
|
1
|
1
|
0
|
0
|
1
|
13
|
1
|
1
|
0
|
1
|
1
|
14
|
1
|
1
|
1
|
0
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
2 Составим
группы по количеству единиц и выполним необходимые преобразования:
№
|
|
|
|
|
|
2
|
0
|
0
|
1
|
0
|
по
1 единице
|
6
|
0
|
1
|
1
|
0
|
|
10
|
1
|
0
|
1
|
0
|
по
2 единицы
|
12
|
1
|
1
|
0
|
0
|
|
7
|
0
|
1
|
1
|
1
|
|
13
|
1
|
1
|
0
|
1
|
по
3 единицы
|
14
|
1
|
1
|
1
|
0
|
|
15
|
1
|
1
|
1
|
1
|
по
4 единицы
|
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
|
(2,6) = 0_10 (2,10) = _010 (6,7) = 011_ (6,14)
= _110 (10,14) = 1_10 (12,13) = 110_ (12,14) = 11_0 (7,15) = _111 (13,15) =
11_1 (14,15) = 111_
|
3 Составим
таблицу и найдем минимальное покрытие:
|
0010
|
0110
|
0111
|
1010
|
1100
|
1101
|
1110
|
1111
|
0_10
|
+
|
+
|
|
|
|
|
|
|
_010
|
+
|
|
|
+
|
|
|
|
|
011_
|
|
+
|
+
|
|
|
|
|
|
_110
|
|
+
|
|
|
|
|
+
|
|
1_10
|
|
|
|
+
|
|
|
+
|
|
110_
|
|
|
|
|
+
|
+
|
|
|
11_0
|
|
|
|
|
+
|
|
+
|
|
_111
|
|
|
+
|
|
|
|
|
+
|
11_1
|
|
|
|
|
|
+
|
|
+
|
111_
|
|
|
|
|
|
|
+
|
+
|
Импликанты ,
,
и
являются
существенными. Т. о., получаем:
.
4 Проверка:
№
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
2
|
0
|
0
|
1
|
0
|
1
|
1
|
3
|
0
|
0
|
1
|
1
|
0
|
0
|
4
|
0
|
1
|
0
|
0
|
0
|
0
|
5
|
0
|
1
|
0
|
1
|
0
|
6
|
0
|
1
|
1
|
0
|
1
|
1
|
7
|
0
|
1
|
1
|
1
|
1
|
1
|
8
|
1
|
0
|
0
|
0
|
0
|
0
|
9
|
1
|
0
|
0
|
1
|
0
|
0
|
10
|
1
|
0
|
1
|
0
|
1
|
1
|
11
|
1
|
0
|
1
|
1
|
0
|
0
|
12
|
1
|
1
|
0
|
0
|
1
|
1
|
13
|
1
|
1
|
0
|
1
|
1
|
1
|
14
|
1
|
1
|
1
|
0
|
1
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
1
|
Т.к. f1
= f, то
преобразования выполнено верно.
Ответ:
Используя метод диаграмм Вейча, необходимо найти
МДНФ функции f(x1,x2,x3,x4),
принимающей значение 1 на наборах: 0, 2, 4, 8, 12, 14, 15.
Решение:
1. Составим таблицу истинности:
№
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
2
|
0
|
0
|
1
|
0
|
1
|
3
|
0
|
0
|
1
|
1
|
0
|
4
|
0
|
1
|
0
|
0
|
1
|
5
|
0
|
1
|
0
|
1
|
0
|
6
|
0
|
1
|
1
|
0
|
0
|
7
|
0
|
1
|
1
|
1
|
0
|
8
|
1
|
0
|
0
|
0
|
1
|
9
|
1
|
0
|
0
|
1
|
0
|
10
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
12
|
1
|
1
|
0
|
0
|
1
|
13
|
1
|
1
|
0
|
1
|
0
|
14
|
1
|
1
|
1
|
0
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
1. Для
булевой функции 4-х переменных диаграмма Вейча имеет вид:
0000
|
|
0010
|
=
|
00_0
|
0000
|
|
0100
|
=
|
0_00
|
1100
|
|
1110
|
=
|
11_0
|
1100
|
|
1000
|
=
|
1_00
|
1111
|
|
1110
|
=
|
111_
|
Получаем:
1. Проверка:
№
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
2
|
0
|
0
|
1
|
0
|
1
|
1
|
3
|
0
|
0
|
1
|
1
|
0
|
0
|
4
|
0
|
1
|
0
|
0
|
1
|
1
|
5
|
0
|
1
|
0
|
1
|
0
|
0
|
6
|
0
|
1
|
1
|
0
|
0
|
0
|
7
|
0
|
1
|
1
|
1
|
0
|
0
|
8
|
1
|
0
|
0
|
0
|
1
|
1
|
9
|
1
|
0
|
0
|
1
|
0
|
0
|
10
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
12
|
1
|
1
|
0
|
0
|
1
|
1
|
13
|
1
|
1
|
0
|
1
|
0
|
0
|
14
|
1
|
1
|
1
|
0
|
1
|
1
|
15
|
1
|
1
|
1
|
1
|
1
|
1
|
Т. к. f1
= f,
то преобразования выполнено верно.
Ответ:
константа эквивалентность дизъюнктивная форма функция
Список
использованной литературы
1.Гаврилов Г.П., Сапоженко А.А.
Сборник задач по дискретной математике.- М.: Наука,1977.
.Горбатов В.А. Фундаментальные
основы дискретной математики. Информационная математика. - М.: Наука.
Физматлит, 2000.
.Информатика: Энциклопедический
словарь для начинающих /Сост. Д.А. Поспелов. - М.: Педагогика - Пресс, 1994.
.Кузнецов О.П., Адельсон-Вельский
Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат,1988.
.Лихтарникова Л.М.,Сукачева Т.Г.
Математическая логика / Курс лекций. - СПб. : Издательство «Лань», 1998.
.Логинов Б.М. Лекции и упражнения по
курсу «Введение в дискретную математику». - Калуга: МГТУ им.Н.Э. Баумана, 1998.
.Нефедов В.Н., Осипова В.А. Курс
дискретной математики: Учеб. пособие.-М.: Изд-во МАИ,1992.
.Савельев А.П. Прикладная теория
цифровых автоматов. М.: Наука,1985.
.Фудзисава Т., Касами Т. Математика
для радиоинженеров: Теория дискретных структур: Пер. с япон. - М.: Радио и
связь,1984.
.Муха Ю.П., Авдеюк О.А., Скворцов
М.Г. Математическая логика. Конспект лекций по теоретической информатике: Учеб.
пособие/ ВолгГТУ.- Волгоград, 2001.
/ Муха Ю.П., Авдеюк О.А.
Математическая логика и теория алгоритмов. Конспект лекций: Учеб. пособие/
ВолгГТУ.- Волгоград, 2005.