ЛБ3_МЛиТА
.docx
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Юго-западный государственный университет»
Факультет фундаментальной и прикладной информатики
Кафедра «Информационная безопасность»
Предмет «Математическая логика и теория алгоритмов»
Лабораторная работа № 3
Вариант 5
Исполнитель:
студент группы ИБ-11б
Гребенникова А.И.
Проверяющий:
профессор, д.физ-мат.н.
Добрица В.П.
Курск 2022
Цель: освоить алгоритм Квайна приведения ДНФ к минимальной
дизъюнктивной нормальной форме, реализовывать булевы функции
контактными схемами.
Задача 1. Составить контактную схему голосования по большинству
голосов при 5 голосующих.
Решение. Составим таблицу истинности для всех возможных результатов голосования. При этом 0 = «против», 1 = «за». F обозначим результат голосования по большинству.
a |
b |
c |
x |
y |
F |
Формула |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
¬a∧¬b∧c∧x∧y |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
1 |
¬a∧b∧¬c∧x∧y |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
¬a∧b∧c∧¬x∧y |
0 |
1 |
1 |
1 |
0 |
1 |
¬a∧b∧c∧x∧¬y |
0 |
1 |
1 |
1 |
1 |
1 |
¬a∧b∧c∧x∧y |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
a∧¬b∧¬c∧x∧y |
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
1 |
a∧¬b∧c∧¬x∧y |
1 |
0 |
1 |
1 |
0 |
1 |
a∧¬b∧c∧x∧¬y |
1 |
0 |
1 |
1 |
1 |
1 |
a∧¬b∧c∧x∧y |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
1 |
a∧b∧¬c∧¬x∧y |
1 |
1 |
0 |
1 |
0 |
1 |
a∧b∧¬c∧x∧¬y |
1 |
1 |
0 |
1 |
1 |
1 |
a∧b∧¬c∧x∧y |
1 |
1 |
1 |
0 |
0 |
1 |
a∧b∧c∧¬x∧¬y |
1 |
1 |
1 |
0 |
1 |
1 |
a∧b∧c∧¬x∧y |
1 |
1 |
1 |
1 |
0 |
1 |
a∧b∧c∧x∧¬y |
1 |
1 |
1 |
1 |
1 |
1 |
a∧b∧c∧x∧y |
(Вы правильно построили СДНФ?)
(¬a∧¬b∧c∧x∧y)∨(¬a∧b∧¬c∧x∧y)∨(¬a∧b∧c∧¬x∧y)∨(¬a∧b∧c∧x∧¬y)∨(¬a∧b∧c∧x∧y)∨(a∧¬b∧¬c∧x∧y)∨(a∧¬b∧c∧¬x∧y)∨(a∧¬b∧c∧x∧¬y)∨(a∧¬b∧c∧x∧y)∨(a∧b∧¬c∧¬x∧y)∨(a∧b∧¬c∧x∧¬y)∨(a∧b∧¬c∧x∧y)∨(a∧b∧c∧¬x∧¬y)∨(a∧b∧c∧¬x∧y)∨(a∧b∧c∧x∧¬y)∨(a∧b∧c∧x∧y)
Минимизируем формулу с помощью Карт Карно
ab \ cxy |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Выделим на карте Карно прямоугольные области из единиц наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им конъюнкции:
Область 1:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K1: X1X2X3
Область 2:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K2: X1X2X4
Область 3:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K3: X1X2X5
Область 4:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K4: X1X3X4
Область 5:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K5: X1X3X5
Область 6:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K6: X1X4X5
Область 7:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K7: X2X3X4
Область 8:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K8: X2X3X5
Область 9:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K9: X2X4X5
Область 10:
X1X2 \ X3X4X5 |
000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
00 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
01 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
11 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
K10: X3X4X5
Объединим их с помощью операции ИЛИ и получим минимизированную ДНФ
Минимизированная ДНФ:
(a∧b∧c)∨(a∧b∧x)∨(a∧b∧y)∨(a∧c∧x)∨(a∧c∧y)∨(a∧x∧y)∨(b∧c∧x)∨(b∧c∧y)∨(b∧x∧y)∨(c∧x∧y)
(Как получена? Схема не соответствует формуле.) Составим контактную схему: (Разберитесь с картами Карно, если Вы решаете минимизировать формулу с помощью карты Карно. И опишите все действия.)
Задача 2. Найдите сокращенные, все тупиковые и минимальные ДНФ
булевой функции методом Квайна:
f(0,0,0) = f(0,0,1) = f(1,0,1) = f(1,1,1) = 0
Дизъюнктивная нормальная форма называется сокращенной, если она не совпадает с эквивалентной ей СДНФ. (Например, один из дизъюнктивных членов в СДНФ запишем 2 раз и получим «сокращенную ДНФ», т.к. она отлична от СДНФ? В чем суть сокращения?) Сокращенные ДНФ можно получить из СДНФ, проводя преобразования в соответствии с законами логики, в частности дистрибутивными законами, поглощения и идемпотентности.
Если ДНФ уже больше нельзя сократить по законам логики, то она называется тупиковой (ТДНФ).
Дизъюнктивная форма, содержащая наименьшее число элементарных импликант, называется минимальной дизъюнктивной нормальной формой (МНДФ). (Что такое импликанта? МДНФ определяется по импликантам? А с переменными это не связано?) Импликанта - дизъюнкт в тупиковой ДНФ, представляющий собой элементарную конъюнкцию K, которая может принимать значение 1 на нескольких наборах значений переменных, на которых исходная функция f принимает значение 1. (Это частный случай импликанты. А как она определяется в общем случае?) Булева функция g(x) называется импликантой булевой функции f(x), если для любого набора аргументов, на которых g(x) =1, f(x) также равна единице.
С переменными связано следующей теоремой: Если ДНФ булевой функции f не содержит отрицаний переменных, то эта форма будет являться единственной МДНФ, а значит, она будет наименьшей.
A |
B |
C |
f |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
СДНФ: (¬A∧B∧¬C)∨(¬A∧B∧C)∨(A∧¬B∧¬C)∨(A∧B∧¬C)
Выпишем наборы и сократим их
010, 011 – 01_
100, 110 – 1_0
По данным наборам составим сокращённую ДНФ:
(¬A∧B)∨(A∧¬C) – совпадает с тупиковой ДНФ.
Составим таблицу Квайна:
|
|
011 |
100 |
110 |
01- |
* |
* |
|
|
-10 |
* |
|
|
* |
1-0 |
|
|
* |
|
010
*