Решение. Ведем обозначения

Ведем обозначения. Обозначим прописными буквами девочек:

М­­ – Мушкина,

К – Кукушкина,

Л – Лягушкина.

Строчными буквами обозначим полученные девочками подарки:

к – кактус,

ш – шоколадка,

т – шкатулка.

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

Лт – Лягушкина получила шкатулку,

Мк – Мушкина получила кактус,

Кш – Кукушкина получила шоколадку.

Согласно условию задачи каждая девочка получила только один подарок. Например, если Лягушкина получила шоколадку (Лш), то Мушкина и Кукушкина шоколадку получить не могут, в этом случае возможны две альтернативы: Мушкина получила кактус (Мк), Кукушкина – шоколадку (Кт), или Кукушкина получила кактус (Кк), а Мушкина шоколадку (Мш). Выражения, содержащие данную информацию можно записать в виде следующих конъюнкций:

Лш Мк Кт

Лш Кк Мт

В данных выражениях конъюнкция (логическое умножение) подразумевается, хотя явно не обозначена. Очевидно, что в подобных выражениях, представляющих собой возможный с точки зрения единственности подарка вариант, должны присутствовать все буквы (как прописные, так и строчные), причем только единожды, варианты отличаются способами сочетания пар: девочка – подарок. В нашем случае возможны всего шесть вариантов:

Лш Мк Кт

Лш Мт Кк

Лк Мш Кт

Лк Мт Кш (4)

Лт Мш Кк

Лт Мк Кш.

Кроме того, будут ложны все выражения типа

Лш Лк, Мк Мш,

ЛшМш, ЛкКк…,

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

Запишем выражения, соответствующие условиям задачи:

1. Лк®Мш,

2. Лш ®Мк,

3. ® ,

4. Кк®Лш.

5. Кт®Лк.

Поскольку все эти условия и условие единственности подарка (4) должны выполняться одновременно получим выражение:

(Лш Мк Кт Ú Лш Мт Кк Ú Лк Мш КтÚЛк Мт КшÚ Лт Мш КкÚ Лт Мк Кш)Ù

Ù(Лк®Мш)(Лш ®Мк)( ® )(Кк®Лш) (Кт®Лк).

Избавляясь от импликаций получим:

(Лш Мк Кт Ú Лш Мт Кк Ú Лк Мш КтÚЛк Мт КшÚ Лт Мш КкÚ Лт Мк Кш)Ù

Ù( ÚМш)( ÚМк)(МтÚ )( ÚЛш) ( ÚЛк).

Отсюда, выполняя элементарные преобразования с учетом получим:

(Лш Мк Кт Ú Лш Мт Кк Ú Лк Мш КтÚЛк Мт КшÚ Лт Мш КкÚ Лт Мк Кш) Ú ÚЛк Мш КтÚЛт Мш Кк)( ÚМк)(Мт ÚМтЛшÚ Ú Лш) ( ÚЛк).

С учетом того, что Кт (Кукушкина не получила ни шоколадку, ни кактус тождественно тому, что она получила шкатулку) и Лш=Лш (если Лягушкина получила шоколадку, очевидно, что Кукушкина ее не может получить) получим:

(Лш Мк Кт Ú Лш Мт Кк Ú Лк Мш КтÚЛк Мт КшÚ Лт Мш КкÚ Лт Мк Кш) Ú ÚЛк Мш Кт Ú Лт Мш Кк)( ÚМк)(Мт ÚМтЛшÚКтÚЛш) ( ÚЛк) =

=(Лш Мк Кт Ú Лш Мт Кк Ú Лт Мш Кк Ú Лт Мк Кш Ú Лк Мш Кт) ( ÚМк)Ù Ù(Мт ÚМтЛшÚКтÚЛш) ( ÚЛк)=

=(Лт Мш КкÚ Лт Мк Кш Ú Лк Мш Кт ÚЛш Мк Кт)(Мт Ú Лш МтÚ КтÚЛш)Ù

Ù( ÚЛк) = (Лк Мш КтÚЛш Мк Кт) ( ÚЛк) = Лк Мш Кт.

То есть, Лягушкина получила кактус, Мушкина – шоколадку, а Кукушкина – шкатулку.

Из последнего выражения видно, что если использовать только первые четыре условия то получим два ответа, не противоречащие в данном случае условию задачи: Лк Мш Кт и Лш Мк Кт, т.е. еще добавляется ответ: Лягушкина получила шоколадку, Мушкина – кактус, а Кукушкина – шкатулку. В общем случае можно получить множество решений, формально выводимых из условия, однако конечно, гораздо интереснее смотрятся те задачи, в которых мы путем применения аппарата алгебры высказываний получаем единственный правильный ответ.

Варианты заданий к практическим занятиям

Ниже приведены варианты заданий ПФ, зависящих от 3, 4 и 5 аргументов, необходимые для выполнения практических занятий 1 – 5. В табл. 9 занесены числовые представления полностью определенных ПФ. В табл.10 представлены неполностью определенные ПФ (числа, записанные в скобках, задают номера наборов аргументов, где ПФ не определена).

Таблица 9

№ п/п	n=5	n=4	n=3
	0,1,2,3,4,6,10,15,19,25,31	0,2,3,4,5,6,7,8,9,10, 14	0,1,2,3,4
	4,7,9,10,12,13,14,15,19,20,22,23,26,	0,1,2,3,6,7,9,10,11,12,13	0,4,5,6,7
	3,4,5,6,7,11,12,13,14,15,16,19,20,21,22,25, 27,28,30	6,9,10,13,14,15	0,2,4,5,6
	0,2,3,4,5,6,8,10,18,19,21,22,23,24,25	0,4,6,7,8,9,10,11,14	0,3,4,5,6
	1,3,5,10,13,14,15,19,22,23,24,25,26,29	0,2,5,6,13,15	0,1,5,6,7
	2,8,9,10,11,12,15,16,17,18,19,20,23,25,26,31	0,1,2,6,7,8,9	0,5,6,7
	0,1,3,4,6,7,9,10,11,12,13,14,15,16,17,20,21,22,23,24,26,28,29,30	0,3,4,5,6,7,8,13,14	0,2,6
	1,3,4,5,6,7,8,11,13,14,15,17,18,20,21,22,23, 24,25,26,27,28,29,30,31	0,1,3,7,8,9,13	3,4,5,6,7
	2,3,4,5,6,7,11,14,15,16,17,19,22,24,26,27,28,31	1,2,9,10,13,14,15	2,3,4,5
	1,3,4,5,8,11,12,15,18,19,20,21,25	0,6,7,8,10,11,12,13, 14,15	3,6,7
	0,1,3,5,9,11,12,13,14,15,16,17,22,23,30	0,1,2,3,4,6,10,12	0,2,3,4,6
	1,2,3,4,5,6,7,9,10,12,13,15,17,19,21,22,24,25,29, 30	0,1,2,3,4,5,6,8,9,14,	0,4,5,7
	1,4,5,7,9,15,20,21,22,23,30,31	4,5,7,9,10,11,12,13	0,2,4,5,6
	0,1,8,9,12,14,16,17,19,20,21,26,27,29	2,3,6,7,9,11,12,13,14	0,1,3,4
Окончание табл. 9
	1,4,5,6,7,8,12,14,16,20,21,22,23	0,1,5,7,8,9,10,14,15	0,2,5,7
	3,4,5,6,7,9,11,13,14,18,19,20,21,23,24,25,26,27,30,31	0,1,2,3,4,8,9,10,11,13,15	0,1,5
	0,1,6,7,16,17,20,22,24,25,29,30	2,3,6,7,8,14,15	1,3,4,6
	0,4,5,9,13,17,18,19,20,21,22,25,26,29,30	0,1,4,6,8,9,10,11, 12,15	0,1,4,5,7
	1,3,5,8,10,11,12,15,17,19,21,22,23,24,26,28,	0,1,2,3,4,6,7,9,12, 14,15	1,3,5
	2,5,6,8,9,10,13,15,18,19,20,21,22,23,24,26, 27,28,29,31	1,3,5,6,7,10,13,14	0,3,5,6,7
	2,4,5,9,11,12,13,15,17,18,19,20,21,22,23,24,25,27,29,31	2,3,5,7,8,9,10,11, 13,15	0,2,3,4,7
	0,1,4,5,8,9,11,13,18,19,20,21,24,27,29	0,1,2,7,8,9,10,11, 12,13,14,15	0,1,2,6,7
	1,6,8,9,10,12,14,17,18,19,22,24,25,26,28,30,	1,5,6,8,9,10,11,14,	0,1,2,4,6,7
	1,3,4,5,6,7,8,9,17,19,22,26,28,29	0,1,4,5,6,7,12,13,14	0,4,6,7
	0,1,2,3,4,6,7,9,11,13,14,15,16,20,24,27,29,30,31	1,3,7,9,10,11,15	0,1,6
	2,7,9,10,12,15,18,19,20,24,26,29,30	1,4,7,8,9,10,12, 14,15	2,6,7
	1,2,3,5,8,10,11,13,14,16,18,19,21,27,28,29	1,5,8,9,13,14,15	0,2,5,6,7
	0,1,2,3,5,6,11,12,13,16,17,20,21,23,24,27,28, 29,30,31	1,2,3,7,8,9,10,15	0,1,2,4,5,7
	5,13,15,16,17,19,21,22,23,24,25,28,29,30	1,4,6,8,9,10,11,12,	2,3,4,6
	2,3,6,7,8,10,15,18,19,20,22,24,26,28,30	1,5,7,10,12,13,14,15	2,5,6,7

Таблица 10

№ п/п	n=5	n=4	n=3
	5,7,8,9,10,13,15,18,25,26,27,29,30,31 (11,17,19,21,22,24)	4,11,12,14,15 (5,6,7,10,13)	2,4 (6,7)
	0,4,5,8,9,10,14,16,21,22,23,25,26,30 (1,2, 6,7,11,13,17,24,29)	0,2,5,7,13,14 (1,4, 6,8,10,15)	1,2,3,6 (5)
	4,5,9,12,17,19,23,25 (1,3,7,11,18,20,21, 22,24,26,27,28,29,30,31)	1,3,7,8,12,15 (2,9,11, 14)	0,4,7 (1,2,5,6)
	0,2,5,7,12,18,20,21,22,23,27,29 (1,3,4,6,9, 14,16,17,19,24)	3,12,13 (6,8,9,11, 15)	1,2,4,6 (3)
	0,6,8,9,14,16,18,20,21,26,28,30 (2,3,5,10,13, 17)	3,8,11,14 (1,2,4,9, 10,13,15)	0,1,3,5, 6,7 (2)
Продолжение табл. 10
	0,1,2,3,4,5,6,12,14,20,26,27,28,29 (7,8,13,16,18,19,21,22,24,30)	1,9,11,12,14 (3,4,7,8,10,15)	1,5,7 (4)
	0,1,6,8,9,23,24,31 (2,3,5,7,10,11,13,15, 20,22,27,29,30)	0,4,8,10,11,13 (3,5,9,12,14,15)	3 (4,5,6,7)
	4,9,19,20,23,26,27,28,29,30 (2,3,6,8,10,11,12,13,24,25,31)	0,2,3,6,8,14 (1,4,7,12)	0,4,6 (2,3,5,7)
	0,4,6,14,16,17,21,29 (1,3,5,7,9,11,13,15,18, 19,20,24,25,26,27,28,31)	0,7,13 (4,5,9,11,14,15)	3,4 (0,1, 2,5,6)
	4,7,8,10,11,13,15,20,27 (5,6,9,14,16,21, 22,23,29)	8,13,15 (0,6,7,10, 11,12,14)	1,3,4,5 (0,6,7)
	0,8,12,14,15,17,26,30 (1,7,9,10,16,18,20,22, 24,28,31)	4,5,8,11 (1,3,6,7,9,13)	0,3,4,6 (7,2)
	4,5,12,17,19,21,23 (0,2,3,6,13,16,20,22, 24,25,30)	5,6,7,8,12 (0,1,3,4,10,11,15)	0,1,5,7 (2,4,6)
	0,1,5,12,13,15,20,21,24,28,29 (6,8,11, 14,16,17,25,26,27)	3,7,8,11,15 (2,9, 13,14)	6, 0 (2,5,7)
	0,2,3,11,16,26,27,30 (7,9,19,21,24,27,28)	0,1,2,5,6,8 (9,10,12,14)	1,4,5 (2,6,7)
	2,4,8,14,19,22,27,28,30 (1,3,6,7,10,11,12,15, 18,20,23,24,26,29)	1,4,5,7,12,13 (0,2, 6,9,11)	0,2,6 (1,3,5,7)
	2,6,10,12,13,14,22,23,24,26 (0,1,7,18,25, 27,28,29)	7,8,11,13,15 (0,1,2,3,5)	1,4,5,7 (0)
	2,7,9,22,23,26,31 (4,5,6,8,10,12,13,14,15, 19,28,29,30)	0,8,10,11,12, (1,9,13,14)	0,3 (2,4)
	0,2,4,6,8,20,23,28,30 (3,5,7,9,11,16,19, 24,26,27,29,31)	0,2,4,6,9,11,12 (5,8,13,14)	1,6 (2,4)
	2,5,6,7,15,18,19,22,23,24,25,26,27,28,31 (0,3,8,9,10,13,14,29)	1,2,5,8,11 (3,4,7,9,10,12,13)	1,2,3 (5,6,7)
	1,4,6,12,14,15,16,17,21,23,26 (0,2,3,8,10, 18,19,28,29,31)	2,3,7,10,13,14,15 (0,5,6,9)	3,6 (0,2,5)
	0,1,3,17,18,23,25,28,30 (2,4,6,7,8,12,16,19, 21,22,27,31)	2,7,8,10,13,15 (0,3,4,5)	1,2,3,6,7 (0,5)
	1,8,11,24,25,31(3,6,7,9,10,13,15,16,19,23,26,28,30)	0,6,12,14 (1,2,4,5, 8)	0,1,4,5,6 (2)
	3,4,5,7,9,18,26 (0,1,11,15,19,23,24,25, 27,28,30,31)	0,4,5,8,12 (1,3,7, 10,14)	0,3,4,5,7 (2,6)
	0,2,5,9,14,16,17,19,25,29,30,31 (1,3,4,7,10, 13,15,18,26)	1,4,6,12,14,15 (2,5,7,9)	0,4,7 (1,2,3,5)
	0,2,3,8,11,12,13,18,20,26 (5,13,16,19,21,24,25, 27,28)	0,3,9,10,15 (1,2,8, 11,12,13,14)	2,6 (0,1,3,7)
	0,2,3,4,5,8,14,16,17,18,19 (1,7,10,12,17,21, 24)	2,5,7,12,13,14 (1,3,4,6,8,9,10)	0,2,4,5,7 (3,6)
Окончание табл. 10
	1,3,9,10,17,23,25,26,29 (0,5,6,11,15,16, 20,21,27,31)	7,8,10,11,12,13 (0,1,2,3,9)	0,1,2 (3,4,5,6)
	2,3,4,5,8,12,13, 16,17,28 (0,14,21,23,29,30)	0,2,3,5,11,13,15 (7,9,12)	1,4,5,6 (0,2,7)
	1,11,22,24,25,26,27,29 (4,8,12,15,17,18,30,31)	0,1,3,6,9,10,11,12, 13 (4,5,7,14,15)	1,3,5,6 (0,7)
	6,7,10,11,12,14,15,19,22,27 (0,2,3,4,8,9,18,25, 28,31)	0,2,4,12,14 (8,10, 11,13,15)	1,2,4,6 (0,1,3,5)

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Савельев А.Я. Основы информатики. – М.: Изд-во МГТУ им. Баумана, 2001. – 327 с.

2. Савельев А. Я. Арифметические и логические основы цифровых автоматов. –М.: Высш. школа, 1980. – 255 с.

3. Майоров С. А., Новиков Г. И. Принципы организации цифровых машин. – Л.: Машиностроение, 1974. – 432 с.

4. Проектирование цифровых вычислительных машин / Под ред. С. А. Майорова. М.: Высш. школа, 1972. – 344 с.

5. В.И. Потапов и др. Основы компьютерной арифметики и логики: Учеб. пособие / В.И. Потапов, О.П. Шафеева, И.В. Червенчук. – Омск: Изд-во ОмГТУ, 2004. – 172 с.

6. Нефедов А.В. Интегральные микросхемы и их зарубежные аналоги: Справочник: в 8 т. – М.:ИП РадиоСофт, 2001.

7. Интегральные микросхемы: Справочник / Под ред. Б. В. Тарабрина. – М.: Энергоатомиздат, 1985.– 528 с.

8. Методические указания к практическим занятиям по курсу «Прикладная теория цифровых автоматов» / Сост. И.А. Пальянов, О.П. Шафеева. – Омск: Изд-во ОмПИ, 1987. – 36 с.

СОДЕРЖАНИЕ

1. Практическое занятие 1. Минимизация переключательных функций

с помощью карт Карно........................................................................................... 3

2. Практическое занятие 2. Минимизация переключательных функций

методом Квайна – Мак-Класки.............................................................................. 7

3. Практическое занятие 3. Синтез комбинационных схем в базисе

«И, ИЛИ, НЕ»....................................................................................................... 12

4. Практическое занятие 4. Синтез комбинационных схем

на логических элементах И-НЕ и ИЛИ-НЕ......................................................... 15

5. Практическое занятие 5. Синтез комбинационных схем в смешанных

базисах................................................................................................................... 18

6. Практическое занятие 6. Синтез комбинационных схем с исполь-

зованием дешифраторов и мультиплексоров...................................................... 19

7. Практическое занятие 7. Алгебра высказываний...................................... 25

8. Варианты заданий к практическим занятиям............................................ 29

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.................................................................. 32

Дата добавления: 2015-07-19