Минимизация функций алгебры логики

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Формулировка: Записать формулу функции F и минимизировать ее геометрическим методом, методом карт Карно, Квайна, Квайна-Мак-Класки, неопределенных коэффициентов, минимизирующих карт. Сравнить результаты

Решение:

Функция задана следующей таблицей истинности

Табл. 1

0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Запишем по таблице истинности функцию:

=

Минимизация геометрическим методом.

Рис. 1

Отметим на рис. 1 вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.

Минимизация методом неопределенных коэффициентов.

=

Составим таблицу соответствующую данной таблице истинности.

Табл. 2

Из уравнений 1, 2, 3, 4 в силу свойств дизъюнкции вытекает, что:



Удобно вычеркнуть уравнения, в правой части которых стоят нули, а в остальных уравнениях вычеркнуть коэффициенты равные нулю.

После этого система примет вид:

В системе в силу свойства дизъюнкции можно приравнять единице коэффициент .

Получим минимальную форму функции

Минимизация методом минимизирующих карт.

=

Рассмотрим следующую таблицу:

Табл. 3

Взяв по одной конъюнкции для всех не зачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.

Табл. 4

Отметим справа от последнего столбца те конъюнкции, которые входят в СДНФ данной функции. Вычеркнем неотмеченные строки, затем вычеркнем в остальных строках (действуя по столбцу) те элементы, которые попали в вычеркнутые строки. В 1 столбце (с одной переменной) положим = 1, при этом остальные элементы строк (5, 6, 7, 8 строки), где стоит элемент , положим равными нулю.

Получим минимальную форму функции

Минимизация методом карт Карно.

=

Строим карту с симметричным расположением аргументов, один из них расположим с одной стороны, два других - с другой. Каждая клетка карты соответствует членам СДНФ функции, содержащим 3 знака.

Табл. 5

1	1	0	0
1	1	1	1

Итак, получим МДНФ данной функции в виде:

Минимизация методом Квайна.

=

Запишем первичные импликаты в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 6

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 2) *	(1, 4)
2.	*	(1, 3) *	(2, 3)
3.	*	(2, 4) *
4.	*	(3, 4) *

Не склеившиеся простые импликанты обводим рамочкой. В данном примере 1-й этап сразу приводит к цели:

Минимизация методом Квайна-Мак-Класки.

=

Заменим исходные импликанты их кодами в двоичных переменных: 100, 101, 110, 111.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 7

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	Группы	Коды	Группы	Коды	Группы
100	0-я	-	10-	1-я	-	1--
101	1-я	100 *	1-0	2-я	1-0 *	1--
110	2-я	101 *	1-1		1-1 *
111		110 *	11-	3-я	11-
	3-я	111 *			10-

Получим минимальную форму функции:

Вывод: При минимизации функции разными методами ответ получился одинаковый.

2. Записать формулу функции и минимизировать ее методами Квайна, Квайна-Мак-Класки и карт Карно. Сравнить результаты

Решение:

Функция задана следующей таблицей истинности:

Табл. 8

0	0	0	0	1
0	0	0	1	0
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

Ее формула в СДНФ имеет вид:

Минимизация методом карт Карно.

Построим карту Карно, соответствующую данной функции, где каждая клетка карты соответствует членам СДНФ функции.

Рис. 2

После склеивания элементов получим минимальную форму функции:

Минимизация методом Квайна.

Поместим первичные импликаты в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 9

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	1.(1,3)	(3,6)
2.	*	2.(1,6)	(4,10)
3.	*	3.(2,3)*	(5,7)
4.	*	4.(2,4)*	(6,11)
5.	*	5. (2,8)*	(7,8)
6.	*	6.(4,5)*
7.	*	7. (4,9)*
8.	*	8. (5,10)*
9.	*	9. (7,9)
10.	*	10. (8,9)*
11.		11. (9,10)*

Табл. 10

Несклеившиеся простые импликанты обводим рамочкой. Дизъюнкция их дает сокращенную ДНФ. Составим таблицу меток, число строк которой равно числу найденных простых импликант, а число столбцов - числу членов СДНФ данной функции. В 1-й столбец записываются члены функции, в 1-ю строку первичные импликанты. Если в член СДНФ входит первичная импликанта, то на пересечении их ставится метка .

В таблице меток столбцами с единственной меткой являются столбцы (6), (7), (8), (10). Соответствующие импликанты , , , являются существенными. Метку обводят кружочком, существенные импликанты - рамочкой, а столбцы с единственной меткой вычеркивают из таблицы. По закону поглощения меньшее количество меток в столбце может исключить большее. Так столбцы (6), (7), (8), (10) входят соответственно в (1), (2), (4), (5), (9), поэтому исключаем все эти столбцы из таблицы меток.

Для оставшегося (3) столбца выберем наиболее удобную импликанту. В данном случае выбираем , т. к. она имеет наименьшее число букв. Получим минимальную форму функции:

Минимизация методом Квайна-Мак-Класки.

Заменим исходные импликанты их кодами в двоичных переменных: 0001,0100,0101,0110,0111,1001,1010,1100,1110,1111.Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 11

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	группы	Коды	группы	Коды	группы
0001	0-я	-	0-01	1-я	-001	-1-0
0100	1-я	0001*	-001		-100*	-11-
0101		0100*	010-		-110*	01--
0110	2-я	0101*	01-0		-111*	-1-0
0111		0110*	-100	2-я	0-01	01--
1001		1001*	01-1		1-10	-11-
1010		1010*	-110	3-я	01-0*
1100		1100*	011-		01-1*
1110	3-я	1110*	1-10		11-0*
1111		0111*	11-0	4-я	010-*
	4-я	1111*	111-		011-*
			-111		111-*

Далее построим таблицу меток, в нее впишем исходные и первичные импликанты в виде двоичных кодов:

Табл. 12

3. Записать формулу функциии минимизировать методом карт Карно

Табл. 13

0	0	0	0	0	0
0	0	0	0	1	1
0	0	0	1	0	1
0	0	0	1	1	1
0	0	1	0	0	1
0	0	1	0	1	0
0	0	1	1	0	0
0	0	1	1	1	0
0	1	0	0	0	1
0	1	0	0	1	1
0	1	0	1	0	1
0	1	0	1	1	0
0	1	1	0	0	0
0	1	1	0	1	1
0	1	1	1	0	1
0	1	1	1	1	1
1	0	0	0	0	1
1	0	0	0	1	1
1	0	0	1	0	0
1	0	0	1	1	0
1	0	1	0	0	0
1	0	1	0	1	1
1	0	1	1	0	1
1	0	1	1	1	0
1	1	0	0	0	0
1	1	0	0	1	0
1	1	0	1	0	0
1	1	0	1	1	1
1	1	1	0	0	1
1	1	1	0	1	1
1	1	1	1	0	1
1	1	1	1	1	1

Решение:

Представим ее в совершенной дизъюнктивной нормальной форме:

Минимизация методом Карт Карно.

Построим карту Карно, соответствующую данной функции, где каждая клетка карты соответствует членам СДНФ функции.

Рис. 3

Ответ:

4. Формулировка: Во всех случаях заданий по п. №1,2,3 получить абсолютно минимальное представление ФАЛ в базисе {-,&,}. Сравнить результаты

Решение:

Практическая часть:

1) Для функции:

FСДНФ=

найдена МДНФ вида: FМДНФ=, откуда видно, что найденная МДНФ уже является абсолютно минимальным представлением ФАЛ.

2) Для функции:

найдена МДНФ вида

Если вынести за скобки , то получим абсолютно минимальное представление:

Видно, что полученное выражение содержит 10 букв вместо 12 и, следовательно, является более простым, чем МДНФ исходной функции.

3) Для функции:

найдена МДНФ вида:

Если сгруппировать элементы и вынести за скобки , , то получим:

Видно, что полученное выражение содержит 22 буквы вместо 29 и, следовательно, является более простым, чем МДНФ исходной функции.

5. Формулировка: Записать исходную ФАЛ во всех случаях заданий по п. №1,2,3 в базисах Вебба и Шеффера; минимизировать её методами неопределенных коэффициентов, минимизирующих карт, Квайна, Квайна-Мак-Класки, карт Карно. Сравнить результаты.

Решение:

Запишем исходную ФАЛ во всех случаях заданий п. №1,2,3 в базисе Вебба:

Функция трех переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Вебба, получим:

Функция четырех переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Вебба, получим:



Функция пяти переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Вебба, получим:

Запишем исходную ФАЛ во всех случаях заданий п. №1,2,3 в базисе Шеффера.

Функция трех переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Шеффера, получим:

Функция четырех переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Шеффера, получим:

Функция пяти переменных:

Используя алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе n-местной функции Шеффера, получим:

Преобразования и минимизация в базисе, состоящем из функции Вебба:

Функция трех переменных в базисе Вебба.

Метод карт Карно:

Построим карту Карно, соответствующую данной функции, где каждая клетка карты соответствует членам СНФ функции.

Рис. 4

Ответ:

Метод неопределенных коэффициентов:

Переходя к системе уравнений с неопределенными коэффициентами для данной функции, получаем:



С учетом того, что все коэффициенты для уравнений, у которых в левой части стоит единица, равны нулю, преобразуем исходную систему к следующему виду:

Приравниваем к единице коэффициент: .

Ответ:

Метод минимизирующих карт:

Строим для функции минимизирующую карту:

Табл. 14

Отметим справа от последнего столбца те конъюнкции, которые входят в СНФ данной функции. Вычеркнем неотмеченные строки, затем вычеркнем в остальных строках (действуя по столбцу) те элементы, которые попали в вычеркнутые строки. В 1 столбце (с одной переменной) положим = 1, при этом остальные элементы строк (1, 2, 3, 4 строки), где стоит элемент , положим равными нулю. Ответ:

Метод Квайна:

Для удобства вычисления построим таблицу и сделаем в ней преобразования, опираясь на ранее изложенный алгоритм:

Табл. 15

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 2) *	(1, 4)
2.	*	(1, 3) *	(2, 3)
3.	*	(2, 4) *
4.	*	(3, 4) *

Ответ:

Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных: 000, 001, 010, 011.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 16

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	Группы	Коды	Группы	Коды	Группы
000	0-я	000 *	00-	1-я	-	0--
001	1-я	001 *	0-0	2-я	0-0 *	0--
010		010 *	0-1		0-1 *
011	2-я	011 *	01-	3-я	01- *
					00- *

Ответ:

Вывод: При минимизации функции разными методами ответ получился одинаковый.

Функция четырех переменных в базисе Вебба

Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных: 0000,0010,0011, 1000, 1011, 1101.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 17

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	группы	Коды	группы	Коды	группы
0000	0-я	0000*	00-0	1-я	-000
0010	1-я	0010*	-000		-011
0011		1000*	001-	2-я	-
1000	2-я	0011*	-011	3-я	00-0
1011	3-я	1011*		4-я	001-
1101		1101

Далее построим таблицу меток, в нее впишем исходные и первичные импликанты в виде двоичных кодов:

функция дизъюнктивный базис минимизация

Табл. 18

Если в каком-либо столбце составленной таблицы меток имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Она не может быть исключена из минимальной формы функции, т.к. без нее не может быть получено покрытие всего множества импликант данной функции. Из таблицы меток исключаются строки и столбцы, на пересечении которых стоит эта единственная метка. По закону поглощения меньшее количество меток в столбце может исключить большее.

Для оставшегося столбца выберем наиболее удобную импликанту. В данном случае выбор равнозначен, т.к. количество цифр одинаково. Выбираю 001-.

Ответ:

Метод Квайна:

Поместим члены F в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 19

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	1.(1,2)
2.	*	2.(1,4)
3.	*	3.(2,3)
4.	*	4.(3,5)
5.	*
6.

Табл. 20

Обработка таблиц осуществляется аналогично предыдущему методу (Квайна-Мак-Класки).

Ответ:

Метод неопределенных коэффициентов:

Опираясь на вышеизложенные алгоритмы, составим систему уравнений с неопределенными коэффициентами для данной функции, получаем:

С учетом того, что все коэффициенты для уравнений, у которых в левой части стоит единица, равны нулю, преобразуем исходную систему к следующему виду:

Из системы следует:

Ответ:

Метод минимизирующих карт:

Построим для данной функции минимизирующую карту:

Табл. 21

Работа с картой производится аналогично классическому методу. Обведем прямоугольником те элементы, которые остались после вычеркивания.

Пусть ====1, тогда все остальные элементы будут равны нулю. В результате этих преобразований получаем окончательный ответ.

Ответ:

Метод карт Карно:

Построим карту Карно:

Ответ:

Вывод:

При минимизации функции разными методами ответ получился одинаковый.

Функция пяти переменных в базисе Вебба

Метод Карт Карно:

Построим карту Карно:

Рис. 5

Ответ:

Метод Квайна:



Поместим первичные импликаты в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 22

	Члены	Результат 1-го склеивания	Результат 2-го склеивания
1.	*	(1,2)
2.	*	(1,4)
3.		(2,8)
4.	*	(4,6)
5.		(4,11)
6.	*	(6,7)
7.	*	(8,10)
8.	*	(8,12)
9.	*	(9,10)
10.	*	(9,13)
11.	*	(11,12)
12.	*	(11,13)
13.	*

Построим таблицу меток.

Получили минимальную форму функции:

Ответ:



Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных:

00000, 00001, 00111, 01000, 01011, 01100, 01101, 10001, 10010, 10011, 11000, 11001, 11010. Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 23

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	группы	Коды	группы	Коды	группы
00000	0-я	00000*	0000-	1-я	-0001
00001	1-я	00001*	0-000	2-я	0-000
00111		01000*	-0001		1-001
01000	2-я	01100*	01-00		1-010
01011		10001*	0110-	3-я	01-00
01100		10010*	100-1	4-я	100-1
01101		11000*	1-001		110-0
10001	3-я	00111	1001-	5-я	0000-
10010		01011	1-010		0110-
10011		01101*	110-0		1001-
11000		10011*	1100-		1100-
11001		11010*			-1000
11010		11001*

Составим таблицу меток:

Табл. 24

Получили минимальную форму функции:

Ответ:

Метод неопределённых коэффициентов:

Опираясь на вышеизложенные алгоритмы, составим систему уравнений с неопределенными коэффициентами для данной функции

С учетом того, что все коэффициенты для уравнений, у которых в левой части стоит единица, равны нулю, преобразуем исходную систему к следующему виду:

;

;

;

;

;

;

;

;

;

;

;

;

Из системы следует:

Все остальные элементы системы будут равны 0.В результате этих преобразований получаем:

Ответ:

Метод минимизирующих карт:

Построим для данной функции минимизирующую карту в базисе Вебба и обработаем ее аналогично классическому методу.

Работа с картой производится аналогично классическому методу (обведем те элементы, которые не вычеркиваются в ходе работы).

Пусть:

Тогда оставшиеся элементы будут равны 0. Запишем окончательный ответ.

Ответ:

Вывод: При минимизации функции разными методами ответ получился одинаковый.

Преобразования и минимизация в базисе, состоящем из функции Шеффера:

Решение

Функция трех переменных в базисе Шеффера.

Метод карт Карно:

Построим карту Карно, соответствующую данной функции, где каждая клетка карты соответствует членам СНФ функции.

Рис. 6

Ответ:

Метод неопределенных коэффициентов:

Вычеркнем уравнения, в левой части которых стоят нули, а в остальных уравнениях вычеркнем коэффициенты, равные нулю. После этих преобразований система примет вид:

Приравняем к единице коэффициент=1. Наиболее экономное решение для оставшихся уравнений.

Ответ:

Метод минимизирующих карт:

Строим для функции минимизирующую карту:

Табл. 25

Отметим справа от последнего столбца те конъюнкции, которые входят в СНФ данной функции. Вычеркнем неотмеченные строки, затем вычеркнем в остальных строках (действуя по столбцу) те элементы, которые попали в вычеркнутые строки. В 1 столбце (с одной переменной) положим = 1, при этом остальные элементы строк (5, 6, 7, 8 строки), где стоит элемент , положим равными нулю.

Ответ:

Метод Квайна:



Для удобства вычисления построим таблицу и сделаем в ней преобразования, опираясь на ранее изложенный алгоритм:

Табл. 26

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 2) *	(1, 4)
2.	*	(1, 3)	(2, 3)
3.	*	(2, 4)
4.	*	(3, 4)

Ответ:

Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных: 100, 101, 110, 111.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 27

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	Группы	Коды	Группы	Коды	Группы
100	0-я	-	10-	1-я	-	1--
101	1-я	100 *	1-0	2-я	1-0	1--
110	2-я	101 *	1-1		1-1
111		110 *	11-	3-я	11-
	3-я	111 *			10-

Ответ:

Вывод: При минимизации функции разными методами ответ получился одинаковый.

Функция четырех переменных в базисе Шеффера

Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных: 0001, 0100, 0101, 0110, 0111, 1001, 1010, 1100, 1110, 1111.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 28

Данная функция	Результаты 1-го склеивания	Результаты 2-го склеивания
Коды	группы	Коды	группы	Коды	группы
0001	1-я	0001*	0-01	1-я	-001	-1-0
0100		0100*	-001		-100*	-11-
0101	2-я	0101*	010-		-110*	01--
0110		0110*	01-0		-111*	01--
0111		1001*	-100	2-я	0-01	-11-
1001		1010*	01-1		1-10	-1-0
1010		1100*	011-	3-я	01-0*
1100	3-я	0111*	-110		01-1*
1110		1110*	1-10		11-0*
1111	4-я	1111*	-111	4-я	011-*
			111-		111-*
			11-0		010-*

Далее построим таблицу меток, в нее впишем исходные и первичные импликанты в виде двоичных кодов:

Табл. 29

Если в каком-либо столбце составленной таблицы меток имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Она не может быть исключена из минимальной формы функции, т.к. без нее не может быть получено покрытие всего множества импликант данной функции. Из таблицы меток исключаются строки и столбцы, на пересечении которых стоит эта единственная метка. По закону поглощения меньшее количество меток в столбце может исключить большее.

Для оставшегося столбца выберем наиболее удобную импликанту. В данном случае выбираю 01--, т.к. данная импликанта содержит наименьшее количество цифр.

Ответ:

Метод Квайна:

Поместим членыF в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 30

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	1. (1,3)	(3,7)
2.	*	2. (1,6)	(4,6)
3.	*	3.(2,3)*	(4,11)
4.	*	4. (2,4)*	(5,8)
5.	*	5. (2,8)*	(7,12)
6.	*	6. (3,5)*	(8,9)
7.	*	7. (4,5)*
8.	*	8. (4,9)*
9.	*	9. (5,10)*
10.	*	10. (7,9)
		11. (8,9)*
		12. (7,9)*

Далее построим таблицу меток, в нее впишем исходные и первичные импликанты. Обработка таблиц осуществляется аналогично предыдущему методу (Квайна-Мак-Класки).

Ответ:

Метод неопределенных коэффициентов:

Опираясь на вышеизложенные алгоритмы, составим систему уравнений с неопределенными коэффициентами для данной функции, получаем:

Вычеркнем уравнения, в левой части которых стоят нули, а в остальных уравнениях вычеркнем коэффициенты, равные нулю. После этих преобразований система примет вид:



Из системы следует:

Ответ:

Метод минимизирующих карт:

Построим для данной функции минимизирующую карту в базисе Шеффера и обработаем ее аналогично классическому методу.

Работа с картой производится аналогично классическому методу (обведем те элементы, которые не вычеркиваются в ходе работы).

Пусть:

Тогда оставшиеся элементы будут равны 0. Запишем окончательный ответ:

Ответ:

Метод карт Карно:

Построим карту Карно:

Рис. 7

Ответ:

Вывод: При минимизации функции разными методами, ответ получился одинаковый.

Функция пяти переменных в базисе Шеффера

Метод Квайна-Мак-Класки:

Заменим исходные импликанты их кодами в двоичных переменных: 00010, 00011, 00100, 00101, 00110, 01001, 01010, 01110, 01111, 10000, 10100, 10101, 10110, 10111, 11011, 11100, 11101, 11110, 11111.

Разобьем коды исходных импликант на группы, поместим их в таблицу. Далее применим закон склеивания к членам соседних групп, перебирая каждый член 1-й группы со всеми членами 2-й группы и т.д.

Табл. 31

Данная функция	Результаты 1-го склеивания	Результаты склеивания
Коды	группы	Коды	группы	2-го	3-го
00010	1-я	00010*	0001-	1-я	-0100*	-010-	1-1--
00011		00100*	00-10		-0101*	-01-0	1-1--
00100		10000*	0-010		-0110*	--110
00101	2-я	00011*	0010-		-1110*	-111-
00110		00101*	001-0		-1111*	0--10
01001		00110*	-0100	2-я	0-010*	--110
01010		01001	10-00		0-110*	1-10-*
01110		01010*	-0101		1-100*	1-1-0
01111		10100*	0-110		1-101*	1-11-*
10000	3-я	01110*	-0110		1-110*	0--10
10100		10101*	01-10		1-111*	-01-0
10101		10110*	1010-	3-я	00-10*	101--*
10110		11100*	101-0		10-00	1-1-0
10111	4-я	01111*	1-100		01-10*	111--*
11011		10111*	0111-		11-11	-010-
11100		11011*	-1110	4-я	001-0*	101--
11101		11101*	101-1		101-0*	1-10-
11110		11110*	1-101		101-1*	-111-
11111	5-я	11111*	1011-		111-0*	1-11-
			1-110		111-1*	111--
			1110-	5-я	0001-
			111-0		0010-*
			-1111		1010-*
			1-111		0111-*
			11-11		1011-*
			111-1		1110-*
			1111-		1111-*

Составим таблицу меток.

Получили минимальную форму функции:

Ответ:

Метод Квайна:

Поместим членыF в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы,снова занумеруем их, склеенные члены 1-го столбца отметим звездочками.

Табл. 32

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания	Результаты 3-го склеивания
1.	*	1. (1,2)
2.	*	2. (1,5)
3.	*	3. (1,7)
4.	*	4. (3,4)
5.	*	5. (3,5)
6.		6. (3,11)
7.	*	7. (4,12)	*
8.	*	8. (5,8)
9.	*	9. (5,13)	*
10.	*	10. (7,8)
11.	*	11. (8,9)
12.	*	12. (8,18)	*
13.	*	13. (9,19)
14.	*	14. (10,11)	*
15.	*	15. ...

Подобные документы

• Алгебра логики

  Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
  
  реферат [63,3 K], добавлен 06.12.2010
  

• Булевы функции

  Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
  
  контрольная работа [178,2 K], добавлен 20.01.2011
  

• Логические функции и логические уравнения

  Логическая переменная в алгебре логики. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Основные законы алгебры логики. Правила минимизации логической функции (избавление от операций импликации и эквивалентности).
  
  курсовая работа [857,2 K], добавлен 16.01.2012
  

• Дискретная математика

  Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
  
  учебное пособие [702,6 K], добавлен 29.04.2009
  

• Применение аппарата алгебры логики к решению содержательных задач

  Операции над логическими высказываниями: булевы функции и выражение одних таких зависимостей через другие. Пропозициональные формулы и некоторые законы логики высказываний. Перевод выражений естественного языка на символическую речь алгебры логики.
  
  контрольная работа [83,3 K], добавлен 26.04.2011
  

• Математическая логика

  Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
  
  контрольная работа [345,3 K], добавлен 29.11.2010
  

• Понятие математической логики

  Основы формальной логики Аристотеля. Понятия инверсии, конъюнкции и дизъюнкции. Основные законы алгебры логики. Основные законы, позволяющие производить тождественные преобразования логических выражений. Равносильные преобразования логических формул.
  
  презентация [67,8 K], добавлен 23.12.2012
  

• Минимальные формы булевых многочленов

  Булевы алгебры – решетки особого типа, применяемые при исследовании логики (как логики человеческого мышления, так и цифровой компьютерной логики), а также переключательных схем. Минимальные формы булевых многочленов. Теоремы абстрактной булевой алгебры.
  
  курсовая работа [64,7 K], добавлен 12.05.2009
  

• Моделирование систем

  Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
  
  контрольная работа [43,2 K], добавлен 27.04.2011
  

• Основы дискретной математики

  Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
  
  контрольная работа [286,7 K], добавлен 28.02.2009
  

• Минимизация функции многих переменных. Приближённые численные методы. Метод Монте-Карло

  Многие переменные, минимизация их функций. Точки максимума и минимума называются точками экстремума функции. Условия существования экстремумов функции многих переменных. Квадратичная форма, принимающая, как положительные, так и отрицательные значения.
  
  реферат [70,2 K], добавлен 05.09.2010
  

• Дискретная математика в задачах

  Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
  
  учебное пособие [1,5 M], добавлен 27.10.2013
  

• Эквиваленты функций

  Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
  
  контрольная работа [335,2 K], добавлен 05.07.2014
  

• Многочлен Жегалкина. Диаграмма Эйлера-Венна. Свойства логической функции двух переменных

  Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
  
  контрольная работа [227,5 K], добавлен 20.04.2015
  

• Исследование алгебр многоместных функций

  История развития и становления математического понятия функции. Абстрактные характеристики упорядоченных алгебр многоместных функций: P-алгебры и D-алгебры. Исследование теории суперпозиций алгебраических структур n-местных функций Менгера и Глускера.
  
  курсовая работа [263,7 K], добавлен 22.12.2015
  

• Код Прюфера

  Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
  
  контрольная работа [181,9 K], добавлен 25.09.2013
  

• Синтез логического автомата

  Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.
  
  курсовая работа [862,4 K], добавлен 12.12.2012
  

• Математическая логика и теория алгоритмов

  Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.
  
  курс лекций [651,0 K], добавлен 08.08.2011
  

• Изучение функций в курсе математики

  Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
  
  контрольная работа [133,5 K], добавлен 08.06.2010
  

• Минимизация функций нескольких переменных. Метод спуска

  Общая схема методов спуска. Метод покоординатного спуска. Минимизация целевой функции по выбранным переменным. Алгоритм метода Гаусса-Зейделя. Понятие градиента функции. Суть метода наискорейшего спуска. Программа решения задачи дискретной оптимизации.
  
  курсовая работа [90,8 K], добавлен 30.04.2011
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам