Некоммерческое акционерное общество
АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ
Кафедра высшей математики

ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания и задания к расчетно-графическим работам
(для специальности 5В070400 Вычислительная техника и программное обеспечение) Часть 2

Алматы 2014

СОСТАВИТЕЛИ:  Астраханцева  Л.Н., Байсалова  М.Ж.  Дискретная математика. Методические указания и задания к расчетно-графическим работам   (для специальности  5В070400 Вычислительная техника и программное обеспечение) Часть 2.  - Алматы: АУЭС, 2013.- 23 стр.

Методические указания и задания к расчетно-графическим работам  содержит раздел «Элементы математической логики» дисциплины Дискретная математика. Методические указания и задания к расчетно-графическим работам  для студентов специальности 5В070400 – Вычислительная техника и  программное обеспечение составлено в соответствии с программой дисциплины «Дискретная математика».

Ил. 1, табл. 9, библиогр. – 7 назв.

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2014 г.

ã   НАО «Алматинский университет энергетики и связи»,  2014 г.

1 Типовой расчёт 2. Элементы математической логики

1.1   Теоретические вопросы

1. Основные понятия логики высказываний. Высказывание, основные логические операции.

2. Логические переменные и формулы. Таблицы истинности логических операций и формул. Соглашение о приоритетах логических операций.

3. Функции алгебры логики. Способы задания логических функций (таблица истинности, нулевые и единичные наборы, вектор значений, формула).

4. Эквивалентность формул. Основные эквивалентные соотношения алгебры логики.

5. Полные системы логических функций. Приведение логических формул к ДНФ, КНФ.

6. Совершенные ДНФ и КНФ (СДНФ и СКНФ).

7.  Минимизация в классе ДНФ. Карты Карно.

8. Коммутационные схемы.

9. Двойственность. Булева алгебра и теория множеств.

1.1   Расчётные  задания

1. Данную функцию f(x,y) заданную формулой, задать:

а) таблицей истинности;

б) единичными и нулевыми наборами;

в) вектором значений.

         Т а б л и ц а 1

№	f(x,y)	№	f(x,y)
1.1		1.2
1.3		1.4
1.5		1.6
1.7		1.8
1.9		1.10
1.11		1.12
1.13		1.14
1.15		1.16
1.17		1.18
1.19		1.20
1.21		1.22
1.23		1.24
1.25		1.26
1.27		1.28
1.29		1.30

2. Используя соглашение о приоритетах логических операций, расставить скобки в формуле f(x,y).

         Т а б л и ц а 2

№	f(x,y)	№	f(x,y)
2.1		2.2
2.3		2.4
2.5		2.6
2.7		2.8
2.9		2.10
2.11		2.12
2.13		2.14
2.15		2.16
2.17		2.18
2.19		2.20
2.21		2.22
2.23		2.24
2.25		2.26
2.27		2.28
2.29		2.30

3.  Записать формулу из задания 2 в виде, содержащем только операции отрицание, конъюнкцию и дизъюнкцию; упростить эту формулу.

4. Проверить эквивалентность формул  и :

          а) с помощью таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных

преобразований.

         Т а б л и ц а  3

№
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
4.16
4.17
4.19
4.20
4.21
4.22
4.23
4.24
4.25
4.26
4.27
4.28
4.29
4.30

5. Для данной функции f(A,B,C) составить таблицу истинности.

         Т а б л и ц а 4

№	f(A,B,C)	№	f(A,B,C)
5.1		5.2
5.3		5.4
5.5		5.6
5.7		5.8
5.9		5.10
5.11		5.12
5.13		5.14
5.15		5.16
5.17		5.18
5.19		5.20
5.21		5.22
5.23		5.24
5.25		5.26
5.27		5.28
5.29		5.30

   Для функции из задания 5 проделать следующее:

 1) привести к ДНФ;

 2) по таблице истинности составить СДНФ;

 3) построить карту Карно;

 4) с помощью карты Карно найти минимальную ДНФ (МДНФ);

 5) от МДНФ перейти к КНФ;

 6) найти СКНФ;

7) по карте Карно найти МКНФ.

6. По данной схеме составить и упростить переключательную функцию, построить упрощённую схему.

 

6.1

 

6.2

 

6.3           

 

6.4

 

 

6.5

 

6.6

 

6.7

 

6.8

 

6.9

6.10

 

6.11

                   

6.12

 

6.13

 

6.14

 

6.15

6.16  

 

6.17       

 

6.18

 

6.19

 

6.20

 

6.21

  

 

6.22

 

6.23           

 

6.24

 

 

6.25

 

6.26

 

6.27

 

6.28

 

6.29

 

6.30

1.3 Решение типового варианта

1 Данную функцию f(x,y) =  , заданную формулой, задать:

          а) таблицей истинности;

         б) единичными и нулевыми наборами;

         в) вектором значений.

Решение:

         а) таблица истинности:

         Т а б л и ц а 5

					f(x,y)
0	0	1	1	1	1
0	1	1	0	0	0
1	0	0	0	1	0
1	1	0	0	0	1

б) единичный набор: 1=f(0,0)=f(1,1); нулевой набор: 0=f(0,1)=f(1,0);

в) вектор значений: (1001).

2. Используя соглашение о приоритетах логических операций, расставить скобки в формуле  f(x,y)= .

         Решение: согласно схеме приоритетов логических операций , в нашей формуле скобки должны быть расставлены так:  =

= .

3. Записать формулу из задания 2 в виде, содержащем только операции отрицание, конъюнкцию и дизъюнкцию; упростить эту формулу.

Решение: = = | 15, 16 | == | 6 | =

 == | 1 | = = | 5 | = .

         В преобразовании указаны номера формул из справочного материала на странице 20. Под упрощением будем понимать получение формулы в виде, содержащем наименьшее число переменных.

4. Проверить эквивалентность формул = и

= :

         а) с помощью таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных

преобразований.

         Решение:

         а) таблица истинности  и :

         Т а б л и ц а 6

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

Так как столбцы значений формул   и  совпадают, то эти формулы эквивалентны;

б) используя известные свойства логических операций, номера которых будем указывать, преобразуем формулы сначала к ДНФ - дизъюнктивной нормальной форме, затем, пользуясь законом расщепления, к совершенной дизъюнктивной нормальной форме (СДНФ):

== | 15 | =  = | ДНФ,10а | =

== = | 4 | =

=  - СДНФ;

= = | 15 | = = | 3 | =

= = | 4,10a | =  =

= |1,10a | = = | 1,4 | =

= - СДНФ.

         Если закон дистрибутивности использовать по - другому – не «раскрыть скобки», а «вынести за скобки», то преобразования будут короче:

= = | 15 | =

= = | 3 | == | 10 a | =…=.

         Так как СДНФ обеих формул совпадают, то эти формулы эквивалентны.

5 Для формулы  построить таблицу истинности.

Решение: таблица истинности формулы:

         Т а б л и ц а 7

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

6. Привести формулу из задания 5 к ДНФ.

Решение:

= | 15,16 | =  = | 6 | =

= =  =

== | 3 | ==

= | 9,3 | =  = | 4,9 | = - ДНФ

(а также СДНФ).

         7.  Для формулы из задания 5 по таблице истинности составить СДНФ.

         Решение: по таблице истинности формулы выпишем её единичные наборы: . Теперь применяем правило, по которому СДНФ функции содержит столько конъюнкт, сколько единиц в столбце значений ; каждому единичному  набору нулей и единиц  соответствует конъюнкта всех переменных, в которых  взято с отрицанием, если , и без отрицания, если . Итак, СДНФ нашей формулы содержит дизъюнкцию двух конъюнкт:  (знак  опущен). Заметим, что СДНФ было получено в предыдущем пункте методом элементарных преобразований.

8 – 9. Для формулы из задания 5 построить карту Карно; с помощью карты Карно найти минимальную ДНФ (МДНФ).

Решение: карта Карно функции трёх переменных представляет собой  таблицу, содержащую  ячеек (столько, сколько всех возможных наборов 0 и 1 функции трёх переменных), строки и столбцы соответствуют значениям переменных или их отрицаниям, так, чтобы соседние ячейки отличались только значением одной переменной. Для получения МДНФ каждая конъюнкта СДНФ функции отмечается единицей в соответствующей ячейке карты Карно.

         Т а б л и ц а 8

	1
			1

Чтобы получить МДНФ, надо объединить рядом стоящие по вертикали и горизонтали единицы в так называемые блоки, состоящие из 2, 4 и т.д. ячеек (блоком из 2  ячеек считаются также единицы, стоящие в углах при одной стороне таблицы, или из 4 – единицы, стоящие во всех углах, т.к., например, в последнем случае карту можно «свернуть» как тор столбцы к столбцам и строки к строкам. В нашей карте Карно только две единицы и они не объединяются в блок, поэтому МДНФ = СДНФ:   .

10. Для формулы из задания 5 от МДНФ перейти к КНФ.

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

= | 7 | = = | 6 | = =

= | 3 | =

=   = | 9, 8, 6 | =

=  = | 6 | =

=- КНФ.

         11. Для формулы из задания 5 построить СКНФ.

Решение: пользуясь законом расщепления, КНФ, полученную в предыдущем пункте, приведём к СКНФ: 

= | 10a | =

 

= | 1,4 | =

- СКНФ.

Совершенную конъюнктивную нормальную форму (СКНФ) можно получить, используя нулевые  наборы значений переменных, которые выпишем из таблицы истинности формулы:  =

=. Теперь, следуя правилу, что СКНФ содержит столько дизъюнкт, сколько нулей в столбце значений , и каждому нулевому набору нулей и единиц  соответствует дизъюнкта всех переменных, в которой i-ая переменная взята с отрицанием, если , и без отрицания, если , получим СКНФ:  

.

12.            Для формулы из задания 5 по карте Карно найти МКНФ.

Решение: для получения МКНФ можно использовать карту Карно, по которой находили  МДНФ. В этой карте следует заменить переменные на их отрицания и наоборот; на пустые места поставить 0 и убрать 1. Либо в обычной карте Карно заполнить нулями ячейки, соответствующие дизъюнктам СКНФ. Затем и в том и в другом случаях отметить на карте максимальные блоки, содержащие 2, 4 и т.д. нулевых соседних ячеек. В нашем случае имеется 3 блока по 2 ячейки, которым соответствуют упрощённые дизъюнкты двух переменных. Заметим, что блоки по две ячейки в этом случае можно отметить по- разному. Мы выбрали один из вариантов.

         Т а б л и ц а 9

		0	0	0
	0	0		0

По этой карте МКНФ формулы имеет вид: .

13. По данной схеме составить и упростить переключательную функцию, построить упрощённую схему.

 

Решение:    составим функцию проводимости для данной схемы:

.

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

= | 3 | = = | 5 | = .

Для наглядности знак  в некоторых местах опущен.

Для минимизации с помощью карт Карно сначала получим СДНФ:

 = | 5 | = = | 3 | =  =

= | 10 a | = = | 4 | = - СДНФ.

В карте Карно отметим единицами конъюнкты, рядом стоящие единицы объединим в блоки и составим МДНФ.

         Т а б л и ц а 10

	1		1
		1	1

МДНФ: = |, вынося за скобки переменную  по закону дистрибутивности, получим упрощённую формулу, где наименьшее число переменных | = .

Полученной формуле соответствует упрощённая схема:

 

1.4 Справочный материал

Логические операции и их таблицы истинности

1. Конъюнкция – (), читается «x и y».

2. Дизъюнкция – ( ), читается «x или y».

3. Отрицание (инверсия) – (), читается «не x».

4. Импликация  -  (), читается «если х, то у».

5. Эквиваленция – (), читается «х если и только если у».

6. Штрих Шеффера – (), определяется как отрицание конъюнкции, т.е. читается «не x и y».

7. Стрелка Пирса – (), определяется как отрицание дизъюнкции, т.е. читается «не x или y».

8. Кольцевая сумма – (), определяется как отрицание эквиваленции (исключающее «или»), т.е. читается «или х, или у».

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

        

         Основные эквивалентные соотношения (законы)

1	Коммутативность
2	Ассоциативность
3	Дистрибутивность
4	Идемпотентность
5	Законы поглощения
6	Законы  Де-Моргана
7	Двойное отрицание
8	Свойства констант
9	-закон противоречия		-закон исключённого третьего

        

         Некоторые другие полезные эквивалентные соотношения

10	Закон склеивания
10а	Закон расщепления
11	Обобщённое склеивание
12
13
14
15
16

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

Список литературы

1.Судоплатов С.В., Овчинникова  Е.В. Элементы дискретной математики. – М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.

2.Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.

3.Новиков Ф.А. Дискретная математика для программистов.Учебник для вузов. 2-е изд.  – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).

4.Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.

5.Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.

6.Яблонский С.В. Введение в дискретную математику. – М. «Высшая школа», 2001.

7.Астраханцева Л.Н. Дискретная математика. Учебное пособие.- Алматы: АУЭС, 2011.- 98 с.

Содержание

1 Типовой расчёт 2. Математическая логика	3
1.1 Теоретические вопросы	3
1.2  Расчётные задания	3
1.3 Решение типового варианта	12
1.4 Справочный материал	20
Список литературы	22

Сводный план  2014 г., поз. 213  

Астраханцева Людмила Николаевна
Байсалова Маншук Жумамуратовна

ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания и задания к расчетно-графическим работам
(для специальности 5В070400 Вычислительная техника и программное обеспечение) Часть 2

Редактор  Л.Т.Сластихина

Специалист по стандартизации  Н.К.Молдабекова

Подписано в печать_______
Формат 6084  1/16
Тираж   300  экз.
Бумага  типографская №1
Объем 1,3  уч.-из.л.
Заказ______ цена  650  тг.

Копировально-множительное бюро
Некоммерческого акционерного общества
«Алматинский университет энергетики и связи»
050013, Алматы, ул.Байтурсынова, 126