Методические рекомендации для выполнения практических работ по дисциплине "Дискретная математика"
методическая разработка по математике

Бессонова Надежда Олеговна

Здесь представлены методические рекомендации по выполнению практических работ по Дискретной математике. Всего практических работ - 18 (36 часов).

Скачать:

ВложениеРазмер
Файл часть 1787.61 КБ

Предварительный просмотр:

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

 «СОРМОВСКИЙ МЕХАНИЧЕСКИЙ ТЕХНИКУМ

ИМЕНИ ГЕРОЯ СОВЕТСКОГО СОБЗА П.А. СЕМЕНОВА»

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ

ПО ДИСЦИПЛИНЕ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

Преподаватель Бессонова Н. О.

2020 год.


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Практические работы по дисциплине «Дискретная математика» разработаны в соответствии с рабочей программой

Количество практических работ                                                 18

Количество учебных часов для выполнения практических работ                38

Практические работы соответствуют следующим темам:

1. Теория множеств

2. Операции над графами. Лес. Деревья

3. Теория графов

4. Понятия. Операции над понятиями. Определение понятия

5. Булевы функции одной и двух переменных

6. Минимизация булевых функций. КНФ, ДНФ

7. Логические схемы

8. Карты Карно

9. Функционально полные системы функций

10. Повторение и обобщение темы «Булевы функции»

11. Творческая работа на тему «Математическая логика»

12. Применение алгебры высказываний для работы с умозаключениями

13. Метод математической индукции (работа 1)

14. Метод математической индукции (работа 2).

15. Количество информации. Формула Хартли. Формула Шеннона.

16. Повторение разделов «Теория множеств. Теория графов».

17. Повторение раздела «Математическая логика».

18. Повторение раздела «Логика предикатов».


Методические указания к практической работе №1 (2 часа)

Подготовка к контрольной работе на тему «Теория множеств».

Цель: научиться решать задачи по теории множеств. Закрепление определений, понятий и теорем раздела.

Оснащение:

– учебник;

– рабочая тетрадь;

– материалы лекций.

Краткие теоретические сведения:

Определение множества.

Понятие «множество» - четко математически не определяется, так же, как такие понятия, как «точка», «прямая», «плоскость» и т. д. Мы будем называть множеством совокупность элементов, объединенных некоторым признаком или свойством.

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

Изображение множеств.

Множества изображают при помощи кругов Эйлера. Элементы множества изображаются точками внутри круга, если они принадлежат множеству, и вне круга – если не принадлежат.

Основные операции над множествами:

Название операции

Обозначение

Изображение кругами Эйлера

Определение

Символическая запись

Пересечение множеств

АВ

Те и только те элементы, которые принадлежат одновременно А и В

АВ = {х|хАихВ}

Объединение множеств

AUB

Те и только те элементы, которые принадлежат хотя бы одному из множеств А к В

АВ={х|хА или хВ)

Разность множеств

А\В

Те и только те элементы множества А, которые не принадлежат В

А\B={х|хА ихВ}

Дополнение к множеству А

Те и только те элементы, которые не принадлежат множеству А (т. е. дополняют его до универсального U)

Симметрическая разность

АΔВ

Те и только те элементы, которые принадлежат одному из множеств: А либо В, но не являются общими элементами

АΔВ = (А\В) U (B\A)=

=(AB)\(АВ)

Ход работы:

Задача 1.

Начертите фигуры, изображающие множества 

где R2 - вещественная плоскость. Какие фигуры изображают множества ?

Задача 2. Докажите тождество http://www.matburo.ru/Examples/dm_set/img2-0.gif

Задача 3. Определите свойства следующих отношений: 
1. «прямая x пересекает прямую y» (на множестве прямых) 
2. «число x больше числа y на 2» (на множестве натуральных чисел) 
3. «число x делится на число y без остатка» (на множестве натуральных чисел)
4. «x - сестра y» (на множестве людей).

Задача 4. Установите взаимно однозначное соответствие между всеми прямыми на плоскости и всеми точками координатной оси Ох.

Задача 5. Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение «непересекающихся прямых».

Эталон выполнения работы

Задача 1.

Начертите фигуры, изображающие множества 

где R2 - вещественная плоскость. Какие фигуры изображают множества ?

Решение.

Задача 2. Докажите тождество http://www.matburo.ru/Examples/dm_set/img2-0.gif

Решение:

Изобразим кругами Эйлера правую часть тождества. Затем по действиям – вторую. Смотри рисунок. Тождество доказано.

дм2.jpeg

Задача 3. Определите свойства следующих отношений: 
1. «прямая x пересекает прямую y» (на множестве прямых) 
2. «число x больше числа y на 2» (на множестве натуральных чисел) 
3. «число x делится на число y без остатка» (на множестве натуральных чисел)
4. «x - сестра y» (на множестве людей).

Решение:

  1.  

Это бинарное взаимно-однозначное отношение, которое обладает следующими свойствами:

– Антирефлетктивность, т. к. x  не пересекает x, а совпадает.

– Симметричность. Если x пересекает y, то и y пересекает x.

– Антитранзитивность, т. к. если x пересекает у, а  y пересекает z, то не обязательно x пересечет z.

– Связность, т. к. для любых xy выполняется x пересекает y или y пересекает x.

Аналогично рассматриваем остальные отношения.

Задача 4. Установите взаимно однозначное соответствие между всеми прямыми на плоскости и всеми точками координатной оси Ох.

Решение:

Зададим прямую двумя числами – точкой пересечения с осью Ох

x = …y3y2y1,x1x2x3… (любое действительное число, в том числе может быть отрицательное,

тогда вначале минус)

и углом наклона a = 180*b (угол между прямой и положительным направлением оси Ох,

изменяется от 0 до 180 градусов), где b – положительное действительное число из интервала

[0,1), b = 0, z1z2z3…

Сопоставим этим двум числам x и b точку q на оси Ох по следующему правилу:

q = …y3y2y1,x1z1x2z2x3z3… (здесь знак числа q совпадает со знаком числа x).

Видно, что по числу q можно однозначно восстановить числа x и b.

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

и всеми точками координатной оси Ох.

Задача 5. Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение «непересекающихся прямых».

Решение

Отношение эквивалентности – это такое отношение, которое обладает тремя свойствами: рефлективность, симметричность и транзитивность.

Проверим, является ли наше отношение – отношением эквивалентности.

Отношение непересекающихся прямых можно перефразировать, как отношение параллельности.

1. Рефлективность. Любая прямая параллельна сама себе. Выполняется.

2. Если прямая а параллельна прямой b, то и b параллельна а. Выполняется.

3. Если прямая а параллельна прямой b, а прямая b параллельна прямой с, то прямая а параллельна прямой с. Выполняется.

Следовательно отношение параллельности является отношением эквивалентности.


Практическая работа №2 (2 часа)

Операции над графами. Лес. Деревья.

Цель: научиться изображать графы по заданным таблицам смежности и инцидентности, изображать операции над графами. Научиться применять теоретические знания теории графов.

Оснащение:

– учебник;

– рабочая тетрадь;

– материалы лекций.

Краткие теоретические сведения

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

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

http://matmetod-popova.narod.ru/theme213/picture2_13_1.GIF

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длинойпути.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь. 
Цепь маршрут, в котором все ребра попарно различны.
Цикл замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последнейпопарно различны, называются простым циклом.

ПОДГРАФЫ

Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).

Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана. 
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

Деревья

Дерево — это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.

Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями
Деревья - очень удобный инструмент представления информации самого разного вида. 
Деревья 
отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.

Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.

В теории графов применяются

  1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующнго рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y)содержит - 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех остальных 0. Петлю, т.е. дугу (х,х) можно представлять иным значением в строке х, например,2. Если граф неориентированный, то столбец, соответствуюший ребру (х,у) содержит 1, соответствующие х и у и нули во всех остальных строках.
  2. Матрица смежности. Это матрица n×n где n - число вершин, где bij = 1, если существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае.

Ход работы:

Дано
http://kontromat.ru/graf/image002.gif
Обозначим вершины и ребра
http://kontromat.ru/graf/image006.gif
Задача 1.
Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.

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

Задача 3.
Определить, является ли данный граф:
- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);
- двудольным графом ( обосновать ответ и, если необходимо, то достроить до двудольного графа);
- деревом ( обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева)
- псевдографом или мультиграфом, или простым графом ( обосновать ответ и выполнить необходимые преобразования)

Задача 4.
Привести пример подграфа, частичного графа и частичного подграфа.

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

Эталон выполнения работы

Задача 1.

Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.
Решение:
Перечисление:
Множество вершин 
http://kontromat.ru/graf/image008.gif
Множество связей 
http://kontromat.ru/graf/image010.gif
Множество изолированных вершин пусто.
Матрица инцидентности

V1

V2

V3

V4

V5

V6

X1

1

0

0

0

0

0

X2

-1

1

1

0

0

0

X3

0

-1

0

1

0

0

X4

0

0

0

-1

-1

0

X5

0

0

-1

0

1

1

X6

0

0

0

0

0

-1

Матрица смежности

X1

X2

X3

X4

X5

X6

X1

0

1

0

0

0

0

X2

0

0

1

0

1

0

X3

0

0

0

1

0

0

X4

0

0

0

0

0

0

X5

0

0

0

1

0

1

X6

0

0

0

0

0

0

Задача 2.
Определить следующие основные характеристики графа:
- число ребер и дуг,
- число вершин,
- коэффициент связности графа,
-степени всех вершин,
-цикломатическое число графа.
Решение:
Число ребер – 0, дуг – 6.
Число вершин – 6.
Коэффициент связности графа- 1
Степени всех вершин

X1

X2

X3

X4

X5

X6

Полустепень исхода

1

2

1

0

2

0

Полустепень захода

0

1

1

2

1

1

Степень

1

3

2

2

3

1

Цикломатическое число графа = (число связей – число вершин)+ коэффициент связности. Т.е. 6-6+1=1

Задача 3.
Определить, является ли данный граф:
- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);
- двудольным графом ( обосновать ответ и, если необходимо, то достроить до двудольного графа);
- деревом ( обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева)
- псевдографом или мультиграфом, или простым графом ( обосновать ответ и выполнить необходимые преобразования)
Решение:
Данный граф является плоским, поскольку все его связи пересекаются только в вершинах. Преобразуем данный граф в планарный.
http://kontromat.ru/graf/image012.gif
Данный граф является двудольным:
http://kontromat.ru/graf/image014.gif
Данный граф не является деревом, поскольку он содержит циклы. Приведем пример остова данного графа.
http://kontromat.ru/graf/image016.gif
V1,V2,V3,V4,V6 – ветви, V5 — хорда.
Данный граф является простым, поскольку не содержит петли, изолированные вершины и кратные связи.
Преобразуем данный граф в мультиграф:
http://kontromat.ru/graf/image019.gif
Преобразуем исходный граф в псевдограф:
http://kontromat.ru/graf/image021.gif
Задача 4.
Привести пример подграфа, частичного графа и частичного подграфа.
Решение:
Подграф
http://kontromat.ru/graf/image023.gif
Частичный подграф
http://kontromat.ru/graf/image025.gif
Частичный граф
http://kontromat.ru/graf/image027.gif
Задача 5.
Провести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа.
Обозначим цвета числами натурального ряда, номер рядом с каждой вершиной или связью будет обозначать цвет.
Решение:
Вершинная раскраска:
http://kontromat.ru/graf/image031.gif
Вершинное хроматическое число равно 2.
Реберная раскраска
http://kontromat.ru/graf/image033.gif
Реберное хроматическое число равно 3.


Практическая работа №3 (2 часа)

на тему «Теория графов».

Цель: научиться изображать графы по заданным таблицам смежности и инцидентности, изображать операции над графами. Научиться применять теоретические знания теории графов.

Оснащение:

– учебник;

– рабочая тетрадь;

– материалы лекций.

Краткие теоретические сведения:

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

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

http://matmetod-popova.narod.ru/theme213/picture2_13_1.GIF

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длинойпути.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь. 
Цепь маршрут, в котором все ребра попарно различны.
Цикл замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последнейпопарно различны, называются простым циклом.

ПОДГРАФЫ

Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).

Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана. 
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

Деревья

Дерево — это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.

Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями
Деревья - очень удобный инструмент представления информации самого разного вида. 
Деревья 
отличаются от простых графов тем, что при обходе дерева невозможны циклы. Это делает графы очень удобной формой организации данных для различных алгоритмов. Таким образом, понятия дерева активно используется в информатике и программировании.

Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.

В теории графов применяются

  1. Матрица инцинденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующнго рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y)содержит - 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех остальных 0. Петлю, т.е. дугу (х,х) можно представлять иным значением в строке х, например,2. Если граф неориентированный, то столбец, соответствуюший ребру (х,у) содержит 1, соответствующие х и у и нули во всех остальных строках.
  2. Матрица смежности. Это матрица n×n где n - число вершин, где bij = 1, если существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае.

Ход работы:

Задача 1. Орграф задан матрицей смежности. Постройте его рисунок, определите степени вершин, и найдите маршрут длины 5

Задача 2. Составьте все возможные планы маршрута путешествия по историческим местам, если туристам надо проехать из M в N, осмотрев все памятники ровно 1 раз? Как называется такой маршрут?

рис1.jpeg

Задача 3. Ориентированный граф G(V, X) с множеством вершин V={1, 2, 3, 4, 5, 6} задан списком дуг: X={(1,2), (2,3), (4,3), (4,5), (6,5), (7,6), (7,1), (7,7), (7,2), (6,4), (4,4), (2,7), (6,4), (5,3)}

1. Постройте реализацию графа G. 2. Постройте матрицу инцидентности. 3. Постройте матрицу смежности. 4. Задайте соответствующий неориентированный граф матрицей смежности. 5.Укажите степени вершин полученных графов, найдите цикломатическое число графа G.

Задача 4. Составьте сценарий, и по нему постройте сетевой граф, иллюстрирующий порядок выполнения операций, для того чтобы: - изготовить табурет; - вышить салфетку; - организовать конкурс чтецов… Выберите любой из списка или придумайте процесс сами

Задача 5. Решите с помощью графов. Как с помощью 4 взвешиваний на чашечных весах определить, какая из 80 монет – фальшивая? На вид все монеты одинаковые, фальшивая – легче.

Задача 6. Находясь в Париже (пункт А на карте), рыцарь узнает, что через 14 часов его возлюбленную, находящуюся в Мадриде (пункт К на карте), съест дракон. Он тут же поспешил на помощь. Сумеет ли рыцарь спасти свою даму сердца? Укажите кратчайший маршрут.

рис2.jpeg

Задача 7. Граф G задан диаграммой.

рис3.jpeg

Составьте для него матрицу смежности. Постройте матрицу инцидентности. Укажите степени вершин графа. Найдите длину пути из V2 в V5, составьте маршруты длины 5, цепь и простую цепь, соединяющую эти вершины. Постройте цикл, содержащий вершину V4. Найдите цикломатическое число. Определите вид данного графа.

Эталон выполнения работы:

Задача 1. Орграф задан матрицей смежности. Постройте его рисунок, определите степени вершин, и найдите маршрут длины 5

 

Решение

ГРАФ.png

Степени вершин: Х1=3, Х2=2, Х3=1, Х4=1, Х5=3, Х6=3

Маршрут длины 5: Х1 – Х6 – Х5 – Х2 – Х4 (и др…)

Задача 2. Составьте все возможные планы маршрута путешествия по историческим местам, если туристам надо проехать из M в N, осмотрев все памятники ровно 1 раз? Как называется такой маршрут?

рис1.jpeg

Такой маршрут называется цепью. По теореме Эйлера, в данном случае пройти таким образом маршрут нельзя, т. к. V-E+F=2 здесь не соблюдено.

9-14+6=1≠2

Задача 3. Ориентированный граф G(V, X) с множеством вершин V={1, 2, 3, 4, 5, 6} задан списком дуг: X={(1,2), (2,3), (4,3), (4,5), (6,5), (7,6), (7,1), (7,7), (7,2), (6,4), (4,4), (2,7), (6,4), (5,3)}

1. Постройте реализацию графа G. 2. Постройте матрицу инцидентности. 3. Постройте матрицу смежности. 4. Задайте соответствующий неориентированный граф матрицей смежности. 5.Укажите степени вершин полученных графов.

Задача 4. Составьте сценарий, и по нему постройте сетевой граф, иллюстрирующий порядок выполнения операций, для того чтобы: - изготовить табурет; - вышить салфетку; - организовать конкурс чтецов… Выберите любой из списка или придумайте процесс сами

Задача 5. Решите с помощью графов. Как с помощью 4 взвешиваний на чашечных весах определить, какая из 80 монет – фальшивая? На вид все монеты одинаковые, фальшивая – легче.

Задача 6. Находясь в Париже (пункт А на карте), рыцарь узнает, что через 14 часов его возлюбленную, находящуюся в Мадриде (пункт К на карте), съест дракон. Он тут же поспешил на помощь. Сумеет ли рыцарь спасти свою даму сердца? Укажите кратчайший маршрут.

рис2.jpeg

При таком раскладе принцесса будет съедена драконом. Кратчайший маршрут А-Г-И-З-К – 15 часов.

Задача 7. Граф G задан диаграммой.

рис3.jpeg

Составьте для него матрицу смежности. Постройте матрицу инцидентности. Укажите степени вершин графа. Найдите длину пути из V2 в V5, составьте маршруты длины 5, цепь и простую цепь, соединяющую эти вершины. Постройте цикл, содержащий вершину V4.

Решение:

Матрица смежности

V1

V2

V3

V4

V5

V6

V7

V1

0

1

1

0

1

1

0

V2

1

0

1

1

0

0

0

V3

1

1

0

0

1

1

1

V4

0

0

0

0

0

1

1

V5

1

1

1

0

0

0

0

V6

1

0

1

1

0

0

1

V7

0

1

1

1

1

1

1

Степени вершин

V1 – 4, V2 – 3, V3 – 5, V4 – 2, V5 – 3, V6 – 4, V7 – 5

Длина пути из V2 в V5 равна 2.

1-2-3-5-7

V4-V7-V6


Практическая работа №4 (2 часа)

Понятия. Операции над понятиями. Определение понятия.

Цель: научиться логическим приемам формирования понятий и логических операций над ними.

Краткая теоретическая справка

В процессе мышления совершаются четыре основные операции: обобщение, ограничение, определение и деление понятий.

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

Ограничение понятия логическая операция, которая состоит в переходе от понятия с большим объемом (и меньшим содержанием) к понятию с меньшим объемом (но с большим содержанием). В процессе ограничения происходит переход от родовых понятий к видовым. Достигается это путем добавления к содержанию исходного понятия какого-либо нового признака. Например, понятие «юрист» можно ограничить, добавив признаки о специфике профессиональной деятельности юриста, например, «быть следователем» - получится понятие «следователь»; добавив признак «быть следователем прокуратуры», можно получить понятие «следователь прокуратуры» и т. д.

Понятие «деяние» можно ограничить следующим образом: «преступное деяние» (т. е. «преступление») → «должностное преступление» → «получение взятки» -» «получение взятки заведующим базой Петровым». Пределом ограничения являются единичные понятия.

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

Определение понятий - это такая логическая операция, с помощью которой раскрывается (уточняется) содержание понятия. Определить понятие о предмете - значит указать существенные признаки этого предмета. Например: «Кража - тайное хищение чужого имущества»; «Человек - живое существо, способное производить орудия труда». Понятие, содержание которого уточняется (например, «кража»), - это определяемое понятие, или дефиниендум (сокращенноDfd). Понятие, с помощью которого происходит уточнение содержания исходного понятия («хищение», «чужое имущество», «тайное»), - это определяющее понятие, или дефиниенс (сокращенно Dfri).

Рассмотрим виды определений:

1. По способу выявления содержания понятий выделяются явные и неявные определения. Наиболее часто применяемым явным определением понятий является определение через род и видовое отличие, в котором предметы, о которых говорится в определяемом понятии, сначала соотносятся с предметами ближайшего рода, а затем указывается тот видообразующий признак, при помощи которого определяемый предмет выделяется из множества предметов данного рода. Так, определяя понятие «кража», вначале указывается его родовой признак - «хищение чужой собственности», затем с помощью видового признака - «тайное» - выделяют данный вид преступлений среди других преступлений против собственности.

Неявные определения - такие, в которых содержание понятий раскрывается косвенным путем. К ним принадлежат:

 контекстуальные определения - когда содержание понятий раскрывается через контекст - отрывок письменной или устной речи, в которой используются данные понятия; например, «на данный вопрос я прошу вас ответить категорически - да или нет»;

•  остенсивные - определения, раскрывающие существенные признаки предметов путем их указания, показа: «это ручка», «это книга, по которой будете изучать логику»;

•  определения через отношение - понятие «материя» определяется через отношение к «сознанию», «свобода» через отношение к «необходимости», «причина» - через отношение к «действию», «необходимость» - через отношение к «случайности» и т.д.

К приемам, заменяющим определения, относятся описание, характеристика, сравнение.

2. В зависимости от того, что именно определяется (предметы или слова), различают реальные и номинальные определения. Реальным является определение, раскрывающее существенные признаки предметов. Например, улика - доказательство виновности обвиняемого в совершении преступления. Реальные определения строятся по схеме: «Предметы вида А есть предметы рода В, имеющие признаки с», сокращенно А = Вс.

Номинальным является определение, посредством которого вводится новый термин (имя), объясняется значение термина, его происхождение и т. д. Например, термином «улика» обозначается доказательство виновности обвиняемого в совершении преступления. Термин «юридический» обозначает все, относящееся к правоведению, праву. Номинальное определение отвечает на вопрос, что обозначает то или иное выражение, и строится по схеме: «Выражение "А" обозначает предметы В, имеющие признаки с». Например: «Слово "кинология" обозначает науку о собаках, их породах, разведении и уходе за ними» или «Покровительство, оказываемое влиятельным лицом кому-либо в устройстве его дел, называется протекцией».

В процессе мышления следует соблюдать следующие четыре основные правила определения.

Правила определения (касаются структуры, формы определения).

1. Определение должно быть соразмерным, т. е. объем определяемого понятия должен быть равен объему определяющего понятия. Например, «грабеж - открытое хищение чужого имущества», «рецидивист-лицо, совершившее преступление после осуждения за ранее совершенные преступления». Схематично: А - Вс, или Dfd =Dfn.

При несоблюдении данного правила возможны две ошибки: а) слишком широкое определение - объем определяющего понятия шире объема определяемого понятия, например, «рецидивист - лицо, совершившее преступление»; б) слишком узкое определение -объем определяющего понятия уже объема определяемого, например, «рецидивист - совершивший вторично убийство».

2. Определение не должно заключать в себе круга. Круг в определении возникает тогда, когда понятие Аопределяется через понятие В, а В в свою очередь определяется при помощи понятия А. Разновидностью круга в определении является тавтология - ошибочное определение, в котором определяющее понятие повторяет определяемое: «то же - через то же». Например: «идеалист – человек идеалистических убеждений», «свидетель - лицо, дающее свидетельские показания», «лекарство - то, что лечит».

3.Определение должно быть ясным, т.е. в определяющем понятии должны указываться известные признаки, не нуждающиеся в определении и не содержащие двусмысленности. Если же понятие определяется через другое понятие, которое само нуждается в определении, то это ведет к ошибке, называемой определением неизвестного через неизвестное. Это правило предостерегает от подмены операции определения понятий сравнениями, метафорами, которые не раскрывают существенных признаков предмета. Например, не являются определениями: «государство - политическое проявление мирового духа» (Гегель); «смех есть солнечный свет в жизни»; «повторение - мать учения».

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

Определение понятий играет важную роль в теоретической и практической деятельности. Раскрывая главное в предмете, определение позволяет выделить данный предмет, отличить его от других предметов, предостерегает от смешения понятий, от путаницы в рассуждениях. В любой науке всем основным понятиям даются точные определения; большое значение имеет определение понятий в правовых науках. По существу, любой Уголовный кодекс состоит из понятий и их определений (изложенных в соответствующих статьях). Ошибочное толкование понятий (например, понятий «умысел», «соучастие», «вина», «неосторожность» и т. д. в уголовном праве) может привести к неправильному пониманию отражаемых в них явлений, а следовательно, к ошибкам суда и следствия.

Итак, определение раскрывает содержание понятий. Но понятие, как мы уже знаем, состоит из содержания и объема. К объему понятий применима операция деления понятий.

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

Необходимо отличать логическое деление от мысленного расчленения целого предмета на части. Если мы скажем, что человек состоит из головы, ног, рук и т.д., то это не будет логическим делением понятия «человек».

Различают деление по видообразующему признаку и дихотомическое деление. По видообразующему признаку деление может производиться - по какому-то основанию - на несколько разных видов; в дихотомическом деление производится на два вида.

Дихотомическое (от греч. слов - dicha и time, означающих «сечение на две части») - деление объема делимого понятия на два противоречивых понятия. Например, А - граждане России, В - совершеннолетние, С -несовершеннолетние. Всех учеников можно разделить на курящих и некурящих; спортсменов и неспортсменов; любящих классическую музыку и не любящих ее и т. п.

Видом операции деления является классификация. Классификация - распределение предметов по группам (классам), при котором каждый класс имеет свое постоянное, определенное место. Вспомним классификацию химических элементов в периодической таблице Менделеева или распределение книг в библиотеке по предметному или алфавитному каталогу. Например, в Особенной части Уголовного кодекса все составы преступлений делятся сначала по различию в объекте посягательства: преступления против личности; преступления в сфере экономики; преступления против общественной безопасности и общественного порядка; преступления против государственной власти; преступления против воинской службы и преступления против мира и безопасности человечества. Затем каждый из этих видов делится в свою очередь на подвиды. Таким образом, все виды преступлений распределяются по группам, причем каждый вид (группа) занимает строго определенное место, закрепленное соответствующей статьей Уголовного кодекса.

Чтобы правильно производить операцию деления, необходимо знать правила деления понятий.

1.      Деление должно быть соразмерным, т. е. объем делимого понятия должен быть равен сумме объемов всех членов деления.

Возможные ошибки при нарушении этого правила:

а)      неполное деление (когда перечислены не все члены деления). Например, «допросы делятся на допросы потерпевшего и допросы обвиняемого» (не указаны допросы свидетелей, подозреваемого);

б)      деление с лишними членами (когда среди членов деления встречается понятие, объем которого не входит в объем делимого понятия). Например, если при делении понятия «наказание» мы укажем «предупреждение», которое не входит в перечень мер наказания в уголовном законодательстве, а является видом административного взыскания, то совершим ошибку (укажем лишний член).

2.      Деление должно производиться только по одному основанию. Это значит, что в процессе деления выбранный признак должен оставаться тем же и не подменяться другим. Ошибки при несоблюдении этого правила называются: «не по одному основанию» или «сбивчивое деление». Например, деление преступлений на умышленные, неосторожные и воинские - сбивчивое, произведено не по одному основанию.

3.      Члены деления должны исключать друг друга. Это правило вытекает из предыдущего. Например, при делении студентов на заочников, первокурсников и спортсменов подклассы предметов не исключают друг друга: студенты-заочники могут быть первокурсниками и спортсменами; первокурсники могут быть заочниками и спортсменами и т. д. Таким образом, члены деления - перекрещивающиеся понятия. При делении объема понятия «преступление» на понятия «умышленное преступление», «неосторожное преступление» и «воинское преступление» нарушается и второе, и третье правила. При смешении оснований деления члены деления (видовые понятия) будут частично совпадать.

4. Деление должно быть непрерывным. Это значит, что в процессе-деления родового понятия нужно переходить к ближайшим видам, не пропуская их. Например, понятие «преступление» можно разделить на понятия «государственное преступление», «должностное преступление», «воинское преступление» и т. д. В свою очередь каждое из этих видов можно разделить на подвиды. Так, понятие «воинское преступление» можно разделить на «неисполнение приказа», «угроза начальнику», «самовольная отлучка» и т. д. Ошибка, которая возникает при нарушении этого правила, называется «скачком в делении».

Операция деления (и классификация) помогает глубже познавать класс предметов в целом и каждый предмет в отдельности. Эта операция имеет большое значение в работе юриста. Например, она лежит в основе таких действий, как: планирование расследования преступлений, классификация следственных версий и т. д.; в криминалистике классифицируются лица, совершившие преступления, предметы (орудия преступления, следы, документы и т. п.). Знание правил деления и классификации необходимо при изучении больших групп явлений и для их упорядочивания. Операция деления позволяет глубже изучить свойства предметов, найти какие-то закономерности во взаимосвязях предметов и их свойствах, облегчает поиск необходимых предметов (как, например, ту или иную книгу в библиотеке, ученика по номеру класса или группы, в которой он учится, и т. п.).

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

Ход работы.

Задача 1.

Какая произведена операция с понятиями: а) частное решение – общее решение; б) число, делящееся на 6 – четное число; в) деление – деление на 10; г) системный блок – персональный компьютере; д) алгоритм решения – постановка задачи; е) несчетные множества – бесконечные множества?

Задача 2.

Ограничьте следующие понятия:

1) Семейное право;

2) Государственный служащий

Задача 3.

Укажите правильность следующих определений (в неправильных укажите, какое правило нарушено):

1) Мошенник — человек, занимающийся мошенничеством.

2) Правонарушение — родовое понятие, означающее любое деяние, нарушающее какие-либо нормы права.

Задача 4

Соблюдено ли правило деления в следующем случае:

1) Право собственности включает в себя владение и распоряжение вещью.

2) Преступность бывает подростковая и взрослая.

Задача 5

Определите, правильно ли произведено ограничение понятий. Если допущена ошибка – исправьте. Изобразите кругами Эйлера. а) время, час, минута, секунда; б) язык программирования, Pascal, C++; в) бит, байт, килобайт; г) системный блок, материнская плата, процессор; д) игра, спортивная игра, футбол; е) граф, плоский граф, дерево.

Задача 6.

При помощи логического квадрата установите все возможные суждения данному суждению. Определите их истинность или ложность:

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

Эталон выполнения работы:

Задача 1.

Какая произведена операция с понятиями: а) частное решение – общее решение; б) число, делящееся на 6 – четное число; в) деление – деление на 10; г) системный блок – персональный компьютере; д) алгоритм решения – постановка задачи; е) несчетные множества – бесконечные множества?

Решение:

а) Здесь произведена операция обобщения понятия, так как понятие «общее решение» включает в себя все частные решения. Изобразим кругами Эйлера. А – «общее решение», В – «частное решение».

                 А

                               В

б) Обобщение; в) ограничение; г) обобщение; д) ни обобщение, ни ограничение; е) ограничение, т. к. бесконечные множества включают в себя счетные и несчетные множества.

Задача 2.

Ограничьте следующие понятия:

1) Семейное право;

2) Государственный служащий

 Решение:

1) Семейное право – российское семейное право – региональное российское семейно право – районное российское семейное право.

2) Государственный служащий – административный государственный служащий – временный административный государственный служащий

Задача 3.

Укажите правильность следующих определений (в неправильных укажите, какое правило нарушено):

1) Мошенник — человек, занимающийся мошенничеством.

2) Правонарушение — родовое понятие, означающее любое деяние, нарушающее какие-либо нормы права.

Решение:

1) Мошенник – человек, занимающийся мошенничеством.

Данное определение неправильное, в нем нарушено правило соразмерности

2) Правонарушение – родовое понятие, означающее любое деяние, нарушающее какие-либо нормы права

Данное определение неправильное, в нем нарушено правило ясности. Определение «родовое понятие» само нуждается в определении

Задача 4

Соблюдено ли правило деления в следующем случае:

1) Право собственности включает в себя владение и распоряжение вещью.

2) Преступность бывает подростковая и взрослая.

Решение

1. Здесь нарушено правило соразмерности. Данное деление неполное, т.к. отсутствует право пользования.

2. Здесь правило деления соблюдено.

Задача 5

Определите, правильно ли произведено ограничение понятий. Если допущена ошибка – исправьте. Изобразите кругами Эйлера. а) время, час, минута, секунда; б) язык программирования, Pascal, C++; в) бит, байт, килобайт; г) системный блок, материнская плата, процессор; д) игра, спортивная игра, футбол; е) граф, плоский граф, дерево.

Решение:

А) ограничение проведено правильно. Время(В), час (Ч), минута (М), секунда(С)

                В

        Ч

             М

                   С

б) ограничение проведено неправильно, т к Pascal и С++ понятия соразмерные

в) здесь обощение понятий. Ограничением будет: килобайт (К), байт (Б), бит (Би)

 

           К

               Б

                      Би

г) Ограничение составлено правильно. Схема при помощи кругов Эйлера аналогична предыдущему случаю.

д) Ограничение составлено правильно. Схема при помощи кругов Эйлера аналогична случаю в).

е) Ограничение составлено правильно. Схема при помощи кругов Эйлера аналогична случаю в).

Задача 6.

При помощи логического квадрата установите все возможные суждения данному суждению. Определите их истинность или ложность:

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

Решение:

Эквивалентные (полно совместимые) суждения:

Иногда предусматривается законом проведение экспертиз.

Истинное субконтрарное (частично совместимое) суждение.

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

Истинное.

Отношение подчинения.

По всем делам предусматривается проведение экспертиз.

Ложное.

По редким делам предусматривается проведение экспертиз.

Истинное

Несовместимое противоположное (контрарное) суждение

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

Ложное

Несовместимое (контрадиктарное) суждение

Все дела не предусматривают закономпроведение экспертиз

Ложное


Практическая работа №5 (2 часа)

Булевы функции одной и двух переменных.

Цель: научиться работать с логическими функциями на примере простейших.

Оснащение:

– учебник;

– рабочая тетрадь;

– материалы лекций.

Краткие теоретические сведения

Понятие булевой функции

В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на (гипер-) плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаться должны функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. Так мы и приходим к понятию булевой функции.

Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.

Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция ``отрицание''. Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:

x

0

x

¬ x

1

0

0

0

1

1

1

0

1

0

1

Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих ``добавочных'' переменных. Такие переменные называются фиктивными, в отличие от остальных – существенных.

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

x1

x2

x1 & x2

x x2

xx2

x x2

x x2

x1 | x2

0

0

0

0

1

0

1

0

0

1

0

1

1

1

0

1

1

0

0

1

0

1

0

1

1

1

1

1

1

0

1

1

Эти функции записываются как бинарные операции в инфиксной нотации. x1 & x2 называется конъюнкциейx x2 – дизъюнкциейx x2 – импликациейx x2 –эквивалентностьюx x2 – суммой по модулю 2x1 | x2 – штрихом Шеффера.

Значения 0 и 1 часто интерпретируют как ``ложь'' и ``истину''. Тогда понятным становится название функции ``отрицание'' – она меняет ``ложь'' на ``истину'', а ``истину'' на ``ложь''. Отрицание читается как ``не''. Конъюнкция читается обычно как ``и'' – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная.* Кроме x1& x2 часто используют обозначение x x2 или x1 · x2 или x1x2 или min(x1,x2). Дизъюнкция читается ``или'' – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная.* Импликация выражает факт, что из x1 следует x2.* Импликацию часто также обозначают x x2.

Двойственные функции

Определение 4 (Двойственная функция). Функция g(x1,...,xn= ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .

Пример 2 (двойственные функции).

(x & y)* = ¬(¬x & ¬y) = x  y.

Предложение 1 (Двойственная к двойственной функции). Функция, двойственная к двойственной функции f равна самой функции f.

Теорема 1 (Принцип двойственности). Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:

Ход работы:

Задача 1. Построить таблицу истинности для формулы  .

Задача 2.

Построить таблицу истинности для формулы .

Задача 3 Является ли функция f двойственной к функции g

а) f=x+y, g=xy,

б) f=xy, g=yx,

в) f=xy, g=ν(x)y

Задача 4  Функцию назовем полной, если класс, единственным элементом которого является эта функция, будет полным. Доказать, что штрих Шеффера и стрелка Пирса – единственные полные функции среди всех двухместных функций

Задача 5. Будут ли следующие функции монотонны: yx+y, xy+y+x, x↔y, x(yx), x(xy)?

Эталон выполнения работы

Задача 1. Построить таблицу истинности для формулы  .

Решение:

x1

x2

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

1

Таким образом, формула   реализует функцию  (тождественная единица).

Задача 2.

Построить таблицу истинности для формулы .

Решение:

x1

x2

0

0

0

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

0

1

Таким образом, формула  реализует функцию   (дизъюнкция).

Задача 3 Является ли функция f двойственной к функции g

а) f=x+y, g=xy,

б) f=xy, g=yx,

в) f=xy, g=ν(x)y

Решение

Составим таблицу истинности для функций f и g

x

y

0

0

0

0

1

1

1

0

1

1

1

1

x

y

0

0

1

0

1

0

1

0

0

1

1

1

Построим двойственную функцию для f

0

0

1

0

1

0

1

0

0

1

1

1

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

Аналогично решаются задачи б) и в).

Задача 4. Будут ли следующие функции монотонны: yx+y, xy+y+x, x↔y, x(yx)?

yx+y

Для выяснения, монотонна ли данная функция, следует изобразить таблицу истинности и выяснить, соблюдено ли определение монотонности

x

y

ху

0

0

0

0

0

1

0

1

1

0

0

0

1

1

1

1

Эта функция не является монотонной, т. к. в 3-й строке мы видим значение «0», которое меньше предыдущего, а должно быть больше или равно.

xy+y+x

x

y

ху

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

1

x↔y не является монотонной, т. к. значения в таблице истинности будут 1-0-0-1

x(yx)

x

y

0

0

1

1

0

1

1

1

1

0

0

0

1

1

1

1

Не является монотонной


Практическая работа №6 (2 часа)

Минимизация булевых функций. КНФ, ДНФ.

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

Краткие теоретические сведения

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

     Минимизация может быть выполнена двумя методами: непосредственными и формальными. Непосредственный метод основан на применении законов алгебры логики к заданной булевой функции. Причем функция может быть задана в произвольной форме.

Ход работы:

Задача 1.  По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ, проверьте результаты по таблице истинности.

а) ; б) ; в)

Задача 2. Пусть известно, что в дорожном происшествии участвовали три автомобиля с водителями AB и C. Свидетели происшествия дали следующие показания: 1-ый свидетель: если A виновен, то из остальных B и C хоть один не виновен; 2-ой свидетель: если C не виновен, то виновен кто-то один из пары A, B но не оба вместе; 3-ий свидетель: в столкновении виновны не менее двух водителей.

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

Эталон выполнения работы

Задача 1.  По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ, проверьте результаты по таблице истинности.

а) ; б) ; в)

Решение: а)

x1

x2

x3

проверка

0

0

0

1

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

1

1

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

1

0

1

1

 – Минимальная ДНФ.

(пользуемся снятием отрицания с конъюнкции, раскрываем скобки, закон поглощения, закон поглощения, закон инверсии)

б);

x1

x2

x3

проверка

0

0

0

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

1

1

0

1

1

1

0

1

1

1

1

0

0

1

0

1

1

1

1

0

1

1

1

1

1

1

1

1

0

0

0

1

1

1

1

1

1

0

1

1

1

1

в)

x1

x2

x3

проверка

0

0

0

1

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

0

1

1

0

1

1

0

0

0

1

1

1

0

0

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

0

1

1

1


Практическая работа №7 (2 часа)

Логические схемы.

Цель: научиться строить логические схемы для практического применения.

Краткие теоретические сведения

С х е м а   И

Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 5.1.

http://book.kbsu.ru/theory/chapter5/0006.gif
  
                  Рис. 5.1

Таблица истинности схемы И

x

y

x . y

0

0

0

0

1

0

1

0

0

1

1

1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом  z  этой схемы и входами  x  и  y  описывается соотношением:   z = x . y 
(читается как 
"x и y"). Операция конъюнкции на структурных схемах обозначается знаком  "&"  (читается как "амперсэнд"),  являющимся сокращенной записью английского слова  and.
 

С х е м а   ИЛИ

Схема  ИЛИ  реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы  ИЛИ  будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис. 5.2.   Знак "1" на схеме — от устаревшего обозначения дизъюнкции как  ">=1"  (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1).    Связь между выходом  z  этой схемы и входами  x  и  y   описывается соотношением:  z = x v y  (читается как "x или y").

http://book.kbsu.ru/theory/chapter5/0007.gif
  
                  Рис. 5.2

Таблица истинности схемы ИЛИ

x

y

x v y

0

0

0

0

1

1

1

0

1

1

1

1


 

С х е м а   НЕ

Схема   НЕ  (инвертор) реализует операцию отрицания.  Связь между входом   x этой схемы и выходом  z  можно записать соотношением   z =http://book.kbsu.ru/theory/chapter5/0008.gif, где http://book.kbsu.ru/theory/chapter5/0008.gif читается как "не x"или "инверсия х".

Если на входе схемы  0,  то на выходе  1.  Когда на входе  1,  на выходе  0.  Условное обозначение на структурных схемах инвертора — на рисунке 5.3

http://book.kbsu.ru/theory/chapter5/0009.gif
  
                  Рис. 5.3

Таблица истинности схемы НЕ

x

http://book.kbsu.ru/theory/chapter5/0010.gif

0

1

1

0


 

С х е м а   И—НЕ

Схема И—НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: http://book.kbsu.ru/theory/chapter5/0011.gif, где   http://book.kbsu.ru/theory/chapter5/0012.gif  читается как   "инверсия x и y".   Условное обозначение на структурных схемах схемы   И—НЕ  с двумя входами представлено на рисунке 5.4.

http://book.kbsu.ru/theory/chapter5/0013.gif
  
                  Рис. 5.4

Таблица истинности схемы И—НЕ

x

y

http://book.kbsu.ru/theory/chapter5/0012.gif

0

0

1

0

1

1

1

0

1

1

1

0


 

С х е м а   ИЛИ—НЕ

Схема ИЛИ—НЕ состоит из элемента ИЛИ и инвертора  и осуществляет отрицание результата схемы ИЛИ.     Связь между выходом  z  и входами  x  и  y  схемы записывают следующим образом:  http://book.kbsu.ru/theory/chapter5/0014.gif,  где  http://book.kbsu.ru/theory/chapter5/0015.gif,  читается как  "инверсия  x или y ". Условное обозначение на структурных схемах схемы ИЛИ—НЕ с двумя входами представлено на рис. 5.5.

http://book.kbsu.ru/theory/chapter5/0016.gif
  
                  Рис. 5.5

Таблица истинности схемы ИЛИ—НЕ

x

y

http://book.kbsu.ru/theory/chapter5/0015.gif

0

0

1

0

1

0

1

0

0

1

1

0

Ход работы:

Задача 1.

По заданной таблице истинности найти логическую функцию

x1

x2

x3

F

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

Решение

Найдем основные конъюнкции, исходя из истинных значений функции:

x1

x2

x3

F

Основные конъюнкции

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

0

Тогда (минимизируем функцию)

Задача 2. По заданной таблице истинности составить логическую схему.

x1

x2

x3

F

x1

x2

x3

F

x1

x2

x3

F

0

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

0

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

0

1

0

1

1

0

1

1

1

0

0

1

1

0

0

1

1

1

1

1

1

1

0

1

1

1

0

Решение:

  1. Сначала найдем саму функцию, минимизируем ее

X1

X2

X3

Аналогичное решение для оставшихся двух таблиц



По теме: методические разработки, презентации и конспекты

методические рекомендации по выполнению практических работ по дисциплине Элементы высшей математики

Методические указания предназначены для проведения практических работ по дисциплине "Элементы высшей математика" (для студентов второго курса специальности 230401 «Информационные системы (по отраслям)...

Методические рекомендации для выполнения практических работ по дисциплине Математика для студентов 1 курса

Всесторонняя подготовка специалистов – это не только приобретение знаний, но и выработка умений применять знания на практике и в жизни. Особенно важными являются умения по специальностям. Однако специ...

Методические рекомендации по выполнению практических работ по дисциплине ЕН.01 «МАТЕМАТИКА»

Методические рекомендации по дисциплине «Математика» разработаны на основе Федерального государственного образовательного стандарта по программам подготовки специалистов среднего звена 13.02.11. «Техн...

Методические рекомендации по выполнению практических работ по ОУД.03 «Математика: алгебра и начала математического анализа; геометрия»

Методические рекомендации по дисциплине «Математика: алгебра и начала математического анализа; геометрия» разработаны на основе Федерального государственного образовательного стандарта по программам п...

Методические рекомендации по выполнению практических работ по учебной дисциплине: Математика: алгебра и начала математического анализа; геометрия.

Методические рекомендации по выполнению практических работ предназначены для организации работы на практических занятиях по учебной дисциплине Математика: алгебра и начала математического анализа...

Методические рекомендации по выполнению практических работ Учебная дисциплина: ОУД 03 МАТЕМАТИКА для профессии 15.01.05 Сварщик (ручной и частично-механизированной сплавки (наплавки)

Методические рекомендации по выполнению практических работУчебная дисциплина: ОУД 03 МАТЕМАТИКАдля профессии 15.01.05 Сварщик (ручной и частично-механизированной сплавки (наплавки)...

Методические рекомендации по выполнению практических работ с прикладной (профессионально-ориентированной) направленностью по математике. Стереометрия

Методические рекомендации по выполнению практических работ по дисциплине Математика представляют собой часть учебно-методического комплекта по математике. Целью создания разработки является оказание п...