kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

Метод.рекомендации по выполнению практических работ по дисциплине ЕН.02 "Дискретная математика"

Нажмите, чтобы узнать подробности

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

Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.

Просмотр содержимого документа
«Метод.рекомендации по выполнению практических работ по дисциплине ЕН.02 "Дискретная математика"»

Государственное бюджетное профессиональное образовательное учреждение «Добрянский гуманитарно–технологический

техникум им. П. И. Сюзева»








Методические рекомендации

к выполнению практических работ обучающихся

по дисциплине «ЕН.02 ДИСКРЕТНАЯ МАТЕМАТИКА С ЭЛЕМЕНТАМИ МАТЕМАТИЧЕСКОЙ ЛОГИКИ»

для специальности 09.02.07 «Информационные системы и программирование»



















Добрянка, 2020


Рассмотрено

на заседании П(Ц)К Общеобразовательных, гуманитарных и естественнонаучных дисциплин


Протокол №_____________

ОДОБРЕНО методическим

советом ГБПОУ ДГТТ им. П.И. Сюзева

«__» _____________________ 2020 г.

Протокол № __ от «__» ____________ 2020



Председатель П(Ц)К Общеобразовательных, гуманитарных и естественнонаучных дисциплин





Заведующий структурным подразделением

_________________ Г.П. Трушникова

________________ М.К. Рябкова





Составители: Трушникова Галина Петровна, преподаватель ГБПОУ «Добрянский гуманитарно-технологический техникум им. П.И. Сюзева»



Рецензенты:


Внешние:

















Содержание

Пояснительная записка…………..………………………………………… …. .. …….3

Практическая работа № 1

Операции над множествами………………………………………………….. ……...5

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

Отношения между множествами…………………………………….………………………. … .8

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

Логические операции……………………… .. …………………………………………………. .8

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

Формулы логики……………..………..............................................................................................9

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

Законы алгебры логики ………………………………………………………………………..10

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

Решение Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)………………………………………………………………………………………………………………….10

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

Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ)……………………………………………………………………..11

Практическая работа № 8

Методы упрощения булевых функций ……………………………………………………………12

Практическая работа № 9

Операции над предикатами………………………………………………………………..……13

Практическая работа № 10

Построение графов по исходным данным ……………….…………………………………...……..13

Практическая работа № 11

Теория неориентированных графов ……………………………………………………………………….. …13

Практическая работа № 12

Ориентированные графы ………………………………………………………………………14

Практическая работа № 13

Элементы теории алгоритмов.…………………………………………………………..…….14

Литература……………………………………………………………………………………....15



Пояснительная записка


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

Перечень практических работ соответствует рабочей программе по дисциплине «Дискретная математика с элементами математической логики ЕН 02»

Выполнение студентами практических работ по дисциплине проводится с целью:

- закрепления полученных теоретических знаний по дисциплине;

- углубления теоретических знаний в соответствии с заданной темой;

- формирования умений решать практические задачи;

- развития самостоятельности, ответственности и организованности;

- формирования активных умственных действий студентов, связанных с

поисками рациональных способов выполнения заданий;

- подготовки к экзамену.

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

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

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

- индивидуально;

- в парах;

- в группах (4-6 чел.);

- всей группой.

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

Оценка преподавателем выполненной студентом работы осуществляется комплексно:

- по результатам выполнения заданий;

- по устной работе;

- оформлению работы.

Указания к выполнению практических работ

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

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

  3. Оформление решения задачи следует завершать словом «Ответ».

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

  5. Оценивание индивидуальных образовательных достижений по результатам выполнения практических работ производится в соответствии с универсальной шкалой (таблица).

Процент результативности (правильных ответов)

Качественная оценка индивидуальных образовательных достижений

балл (отметка)

вербальный аналог

90 ÷ 100

5

отлично

80 ÷ 89

4

хорошо

70 ÷ 79

3

удовлетворительно

менее 70

2

неудовлетворительно


Организация выполнения и контроля практических работ по дисциплине «Дискретная математика с элементами математической логики ЕН 02» является подготовительным этапом к сдаче дифференцированного зачета по данной дисциплине.






ПрактическАЯ РАБОТА№ 1

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


Цели:

  • ознакомиться с операциями над множествами

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых 10 заданий работы

оценка «3» ставится за выполнение любых 8 заданий работы

Порядок выполнения работы

Задание 1.

1. Ознакомиться с теоретическим материалом по заданной теме.

2. Выписать в тетрадь основные определения и примеры, решение которых объясняется в лекции.

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

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

 

Два множества А и В называются  равными ( А = В ), если они состоят из одних и тех же элементов, то есть каждый элемент множества  А  является элементом множества  В  и наоборот, каждый элемент множества  В  является элементом множества  А .

 

Говорят, что множество А содержится в множестве В ( рис.1 ) или  множество А  является подмножеством множества  В ( в этом случае пишут А   В ), если каждый элемент множества  А одновременно является элементом множества  В . Эта зависимость между множествами называется  включением. Для любого множества  А имеют место включения:      А  и  А   А .

Сумма ( объединение ) множеств  А и В ( пишется  А   В ) есть множество элементов, каждый из которых принадлежит либо А , либо В. Таким образом,  е   А   В  тогда и только тогда, когда либо  е   А ,  либо  е   В .  

 

Произведение ( пересечение ) множеств  А и В ( пишется  А   В , рис.2 ) есть множество элементов, каждый из которых принадлежит и А , и В . Таким образом,  е   А   В  тогда и только тогда, когда   е   А  и  е   В .

Разность множеств А и В ( пишется  А – В , рис.3 ) есть множество элементов, которые принадлежат множеству А , но не принадлежат множеству В. Это множество называется также дополнением множества В относительно множества А.

Симметричная разность множеств А и В ( пишется  А \ В  ) есть множество:

 

А \ В  = ( А – В )   ( В – А ).

 

 Свойства операций над множествами:

П р и м е р ы.  1. Множество детей является подмножеством всего населения.

 

                         2. Пересечением множества целых чисел с множеством положительных

чисел является множество натуральных чисел.

 

 3. Объединением множества рациональных чисел с множеством иррациональных чисел является множество действительных чисел.

 

                         4. Нуль является дополнением множества натуральных чисел  относительно

множества неотрицательных целых чисел.

Примеры:

Доказать справдливость равенств

1) (A∩B)′=A′∪B′(A∩B)′=A′∪B′

Доказательство.

x∈(A∩B)′⇔x∉(A∩B)⇔x∉A∨x∉B⇔x∈(A∩B)′⇔x∉(A∩B)⇔x∉A∨x∉B⇔ x∈A′∨x∈B′⇔x∈A′∨x∈B′⇔

x∈(A′∪B′)⇔(A∩B)′=A′∪B′.x∈(A′∪B′)⇔(A∩B)′=A′∪B′.

Что и требовалось доказать.

 {jumi[*4]}

2) (A∖B)∖C=A∖(B∪C).(A∖B)∖C=A∖(B∪C). 

Доказательство.

x∈(A∖B)∖C⇔a∈A∖B∧a∉C⇔(a∈A∧a∉B)∧a∉C⇔x∈(A∖B)∖C⇔a∈A∖B∧a∉C⇔(a∈A∧a∉B)∧a∉C⇔

⇔a∈A∧(a∉B∧a∉C)⇔a∈A∧a∉(B∪C)⇔a∈A∖(B∪C).⇔a∈A∧(a∉B∧a∉C)⇔a∈A∧a∉(B∪C)⇔a∈A∖(B∪C). 

Что и требовалось доказать.

 

3)  A∖(A∖B)=A∩B.A∖(A∖B)=A∩B. 

Доказательство.

a∈A∖(A∖B)⇔(a∈A)∧(a∉A∖B)⇔a∈A∖(A∖B)⇔(a∈A)∧(a∉A∖B)⇔

(a∈A)∧((a∉A)∨(a∈B))⇔(a∈A)∧((a∉A)∨(a∈B))⇔

((a∈A)∧(a∉A))∨((a∈A)∧(a∈B))⇔((a∈A)∧(a∉A))∨((a∈A)∧(a∈B))⇔

(a∈A)∧(a∈B)⇔a∈A∩B.(a∈A)∧(a∈B)⇔a∈A∩B.

Что и требовалось доказать.

 

 4) A∪(B∖C)⊃(A∪B)∖C.A∪(B∖C)⊃(A∪B)∖C.

Доказательство.

a∈(A∪B)∖C⇔(a∈A∨a∈B)∧a∉C⇔a∈(A∪B)∖C⇔(a∈A∨a∈B)∧a∉C⇔

(a∈A∧a∉C)∨(a∈B∧a∉C)⇒(a∈A)∨(a∈B∧a∉C)⇔(a∈A∧a∉C)∨(a∈B∧a∉C)⇒(a∈A)∨(a∈B∧a∉C)⇔

a∈A∪(B∖C).a∈A∪(B∖C).

Что и требовалось доказать.

Задание 2. Решить задачи

1.Установить, какая из двух записей верна: 

{1,2}∈{1,2,{1,2}}{1,2}∈{1,2,{1,2}} и {1,2}⊂{1,2,{1,2}}.{1,2}⊂{1,2,{1,2}}.

 В задачах 2 и 3 заданные  множества задать перечислением всех своих элементов

2. A={x∈N|x2−3x−4≤0}.A={x∈N|x2−3x−4≤0}.

3.A={x∈Z|14≤2x∈Z|14≤2x

Изобразить на координатной плоскости следующие множества:

4. {(x,y)∈R2|x+y−2=0}.{(x,y)∈R2|x+y−2=0}.

5. {(x,y)∈R2|x2−y20}.{(x,y)∈R2|x2−y20}. 

6. {(x,y)∈R2|(x2−1)(y+2)=0}.{(x,y)∈R2|(x2−1)(y+2)=0}. 

7. Описать перечислением всех элементов множества A∪B,A∩B,A∖B,B∖A.A∪B,A∩B,A∖B,B∖A.

A={x∈R|x2+x−20=0},B={x∈R|x2−x+12=0}.A={x∈R|x2+x−20=0},B={x∈R|x2−x+12=0}.

В задачах 8 и 9 приняв отрезок за универсальное множество T=[0,1]T=[0,1] найти и изобразить на числовой оси дополнения следующих множеств: 

8 {0,1};{0,1};

9. {1/4}∪[3/4,1).{1/4}∪[3/4,1).

10. Доказать, что операции ∪∪ и ∩∩ связаны законом дистрибутивности:

(A∪B)∩C=(A∩C)∪(B∩C);(A∪B)∩C=(A∩C)∪(B∩C);

 (A∩B)∪C=(A∪C)∩(B∪C);(A∩B)∪C=(A∪C)∩(B∪C);

 Доказать равенства:

11. A∖B=A∩B¯¯¯¯.A∖B=A∩B¯.

12.  A∖B¯¯¯¯¯¯¯¯¯¯¯¯=A¯¯¯¯∪B.

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 2

Тема: Отношения между множествами

  • научиться решать задачи на отношения между множествами

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых 12 заданий работы

оценка «3» ставится за верное выполнение любых 8 заданий работы

Порядок выполнения работы

Задание 1. Ознакомиться с теоретическими знаниями по теме

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

Определение 5: Множество В является подмножеством множества А, если каждый элемент множества В является также элементом множества А. Утверждение, что множество В является подмножеством множества А, записывают так: ВÌА. Такая запись означает, что каждый элемент множества В является элементом множества А и множество В включено во множество А.

Пример 3. Пусть В {2, 4, 6} – множество чётных чисел, А{1, 2, 3, 4, 5, 6, 7} – множество целых чисел. Следовательно, множество В включено во множество А, что записывается так: ВÌА, но множество А не включено во множество В, что записывается так: А Ë В. Например, множества {4, 8} и {6} являются подмножествами множества {2, 4, 6, 8}; а числа 2, 4, 6, 8 – его элементы.

Свойства включения множеств:

  1. Пустое множество является подмножеством любого множества: Æ Ì А.

  2. Любое множество является подмножеством самого себя, т.е. для любого множества А справедливо включение А Í А.

Определение 6: Два множества равны, если каждое из них является подмножеством другого (A = B Û (A Ì B и В Ì А)). Множества, состоящие из одних и тех же элементов, называются равными. При этом порядок перечисления элементов множества значения не имеет. Например. Равны множества {8,2,5}, {2,5,8} и {5,8,2}.

Если множество X равно множеству Y, то можно записать X = Y. В противном случае X ≠ Y. Другой пример. Даны множества: Z ={3,5,7}, Y = {7,5,3,5,7}. Они равны Z=Y, так как они состоят из одних и тех же элементов. Множество Z={3,5,7}, X={{7,5}, {3,5,7}} не равны Z≠X, так как элементами второго множества являются множества. Таким образом, данные множества состоят из элементов различной природы и не могут быть равны.

Считается, что пустое множество является подмножеством любого множества. У любого множества есть обязательно хотя бы два подмножества: пустое множество и само множество. Эти два подмножества называются несобственными подмножествами. Любое подмножество, отличное от несобственного, называется собственным подмножеством данного множества.

У пустого множества нет собственных подмножеств, а оба несобственных подмножества равны между собой. У любого одноэлементного множества также нет собственных подмножеств, но его несобственные подмножества различны. У любого двухэлементного множества есть уже два собственных подмножества. С ростом количества элементов во множестве количество собственных подмножеств растет. Например, если F={3,5}, то собственными подмножествами множества F будут являться множества {3} и {5}.

Определение 7: Множество всех подмножеств множества А называется множеством-степенью множества А и обозначается через R(A).

Пусть А={5,3,9}. Тогда множество-степень состоит из:

1) А={5,3,9} – исходного множества.

2) пустого множества Æ.

3) трёх одноэлементных подмножеств: {5}; {3}; {9}.

4) трех двухэлементных подмножеств множества А: {{5,3}{3,9}{5,9}}.

Таким образом, множество-степень:

R(A) = {А,{5},{3},{9},{5,3},{3,9},{5,9},{Æ}}; состоит из 23=8 элементов.

Для n-элементного множества множество-степень состоит из 2n элементов.

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задача1: Изобразите на диаграмме отношения между следующими множествами:

А – множество жителей города Шуи;

В – множество студентов ШГПУ;

С – множество учащихся школы №1 г.Шуя;

D– множество студентов Ивановской области;

Решение: Для построения диаграммы необходимо определить отношения между перечисленными множествами.

1

А

. Задача 2 Приведите пример множеств А, В, С, D, для которых данная диаграмма была бы верна. Ответ поясните.

Решение

А– множество треугольников;

В– множество равнобедренных треугольников;

С– множество равносторонних треугольников;

D– множество прямоугольных треугольников.

Пояснение: все равносторонние треугольники являются равнобедренными; нет ни одного треугольника, который одновременно являлся бы равносторонним и прямоугольным; есть такие треугольники, которые одновременно являются и равнобедренными и прямоугольными.

Задание 3. Решить самостоятельно:

  1. Пусть К- множество спортсменов, а М множество отличников класса. Определите условия, при которых: а) КМ; б) ZК; в)МК=.

  2. Пусть А- множество учащихся класса, занимающихся в кружке по рисованию, а В- множество мальчиков класса. Определите условия, при которых: а) АВ=; б) АВ=А; в) АВ=В.

  3. Из 80 школьников 40 играют в футбол, а 50 в волейбол. Каким может быть число школьников, играющих в обе игры, хотя бы в одну из этих игр?

  4. Из 100 школьников 40 играют в футбол, а 50 - в волейбол. Каким может быть число школьников играющих а) в обе игры; б) хотя бы в одну игру?

  5. Пусть А – множество желтых цветов в вазе, В – множество роз в вазе . Определите условия, при которых: а) АВ; б) АВ; в) АВ=В.

  6. Пусть А – множество студентов группы, закончивших педучилище, В – множество студентов группы, являющихся отличниками. Определите условия, при которых: а) АВ; б) ВА; в) АВ=А.

  7. Пусть D – множество девочек класса, Е – множество учащихся, сидящих за первыми партами. Определите условия, при которых: а) DЕ=; б) DЕ; в) DЕ=Е.

  8. Из 60 студентов 30 знают немецкий язык, 20 – английский язык. Каково может быть число студентов, знающих: а) оба языка, б)в точности один язык?

  9. Из 30 школьников 20 любят алгебру, а 18 геометрию. Каким может быть число школьников, любящих: а)сразу оба предмета; б) хотя бы один предмет?

  10. Пусть С – множество учащихся, занимающихся плаванием, а Е – множество учащихся, занимающихся борьбой. Определите условия, при которых: а) СЕ=; б) СЕ; в) DЕ.

  11. Пусть А – множество учащихся класса, С – множество спортсменов класса, В – множество отличников класса, D – множество девочек класса. Задайте множество Х=(АС)(ВD) при помощи характеристического свойства, изобразите множества А,В,С,D,Х на диаграмме Эйлера-Венна. Всякий ли спортсмен–отличник принадлежит множеству Х?.

  12. Пусть А – множество нечетных натуральных чисел, С – множество натуральных чисел кратных 7, В – множество натуральных чисел кратных 3, D – множество четных чисел. Задайте множество Х=(АС)\(ВD) при помощи характеристического свойства, изобразите множества А,В,С,D,Х на диаграмме Эйлера-Венна. Принадлежат ли множеству Х числа 25; 14; 8?

  13. Пусть А – множество машин в гараже, С – множество легковых машин, В – множество машин зеленого цвета, D – множество легковых машин в гараже. Задайте множество Х=(АС)\(ВD) при помощи характеристического свойства, изобразите множества А,В,С,D,Х на диаграмме Эйлера-Венна. Всякая ли легковая машина зеленого цвета из гаража принадлежит множеству Х?

  14. Пусть А – множество книг на полке, С – множество книг советских писателей, В – множество книг на полке в сером переплете, D – множество детских книг. Задайте множество Х=(АС)(ВD) при помощи характеристического свойства, изобразите множества А,В,С,D,Х на диаграмме Эйлера-Венна. Всякая ли детская книга на полке в сером переплете принадлежит множеству Х?

  15. Известно, что А – множество учащихся класса, С – множество девочек класса, В – множество голубоглазых девочек класса, D – множество активистов класса. Задайте множество Х=(А\С)(В D) при помощи характеристического свойства, изобразите множества А,В,С, D,Х на диаграмме Эйлера-Венна. Всякая ли девочка–активистка класса принадлежит множеству Х

  16. Докажите, что:

  • А\ (А\ В)=А В ;

  • (А\ В) В=А В ;

  • А\ (В\ А)=А ;

  • В)\ В=А\ В;

  • В)\(А В)=(А\ В) (В\ А);

  • А\ (В С)=(А\ В) (А\ С).

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 3

Тема: Логические операции

Цели:

  • научиться решать задачи на логические операции

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых пяти заданий работы

оценка «3» ставится за верное выполнение любых четырех заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Логические операции (логические связи) — это элементы формального языка, позволяющие составлять правильные выражения на том языке путем объединения более простых.

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

В традиционной нотации логическим операциям назначают собственные знаки-символы: унарная операция отрицания префиксным зна́ком ¬, бинарные операции иили и влечёт — инфиксными знаками ∧, ∨ и →, соответственно. Атомарные (аксиоматически задаваемые) высказывания обозначаются знаками-константами, — заглавными или строчными латинскими буквами: например, ABp.

При помощи такой нотации записываются логические законы, например свойство ассоциативности дизъюнкции: ((a∨b)∨c) ⇔(a∨(b∨c)). Законы де Моргана: ¬(a∧b)=¬a∨¬b, ¬(a∨b)=¬a∧¬b.

Результат вычисления каждой операции в логике высказываний равен константам ⊤ (1, истинно) и ⊥ (0, ложно).

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

Основные операции Конъюнкция

Логическое умножение, выражение «AND», обозначается знаком «∧».

Таблица истинности для пары операндов — 1000. Конъюнкция возвращает 1 только тогда, когда оба операнда равны 1, иначе 0.

Дизъюнкция

Логическое сложение, выражение «OR», обозначается знаком «⋁». Также называется «слабой дизъюнкцией».

Таблица истинности для пары операндов — 1110. Возвращает 0 только тогда, когда оба операнда равны 0, иначе 1.

Отрицание

Инверсия, негация, выражение «NOT», обозначается знаком «¬».

Возвращает противоположный знак: для 0 — 1, для 1 — 0.

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Пример 1. На одной улице стоят в ряд 4 дома, в каждом из которых живёт по одному человеку. Их зовут Василий, Семён, Геннадий и Иван. Известно, что все они имеют разные профессии: скрипач, столяр, охотник и врач. Известно, что:

— столяр живёт правее охотника;

— врач живёт левее охотника;

— скрипач живёт с краю;

— скрипач живёт рядом с врачом;

— Семён не скрипач и не живёт рядом со скрипачом;

— Иван живёт рядом с охотником;

— Василий живёт правее врача;

— Василий живёт через дом от Ивана.

Определим, кто где живёт.

Изобразим дома прямоугольниками и пронумеруем их:

Известно, что скрипач живёт с краю (3). Следовательно, он может жить в доме 1 или в доме 4.

Скрипач живёт рядом с врачом (4), т. е. врач может жить правее (дом 2) или левее (дом 3) скрипача.

Но врач живёт левее охотника (2), следовательно, скрипач не может жить в доме 4, т. к. в противном случае получится, что врач, живущий рядом с ним, живёт правее охотника, а это противоречит условию (2). Таким образом, скрипач живёт в доме 1, а врач — рядом с ним, в доме 2.

Так как врач живёт левее охотника (2), а столяр — правее охотника (1), то охотнику достается дом 3, а столяру — дом 4.

Так как Семён не скрипач и не живёт рядом со скрипачом (5), то он может жить в доме 3 или в доме 4.

Так как Иван живёт рядом с охотником (6), то он может жить в доме 2 или 4.

Так как Василий живёт правее врача (7), то он может жить в доме 3 или 4.

По условию (8) Василий живет через дом от Ивана, значит, в доме 1 может жить только Геннадий, в доме 2 — Иван, в доме 4 — Василий, в доме 3 — Семён.

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

Задачи о рыцарях и лжецах — это такой класс логических задач, в которых фигурируют персонажи:

- рыцарь — человек, всегда говорящий правду;

- лжец — человек, всегда говорящий ложь;

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

Решение подобных задач сводится к перебору вариантов и исключению тех из них, которые противоречат условию.

Пример 2. Двое жителей острова А и В разговаривали между собой в саду. Проходивший мимо незнакомец спросил у А: «Вы рыцарь или лжец?». Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В: «Что сказал А?».

«А сказал, что он лжец», — ответил В. Может ли незнакомец доверять ответу В? Мог ли А сказать, что он лжец?

Если А — рыцарь, то он скажет правду и сообщит, что он рыцарь.

Если А — лжец, то он скроет правду и сообщит, что он рыцарь.

Это значит, что В, утверждающий, что «А сказал, что он лжец» заведомо лжёт; он – лжец.

Определить, кем является А, в данной ситуации невозможно.

Табличный метод

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

Пример 3. В летнем лагере в одной палатке жили Алёша, Боря, Витя и Гриша. Все они разного возраста, учатся в разных классах (с 7-го по 10-й) и занимаются в разных кружках: математическом, авиамодельном, шахматном и фотокружке. Выяснилось, что

— фотограф старше Гриши;

— Алеша старше Вити, а шахматист старше Алёши;

— в воскресенье Алёша с фотографом играли в теннис, а Гриша в то же время проиграл авиамоделисту в городки.

Определим, кто в каком кружке занимается.

В этой задаче речь идёт о высказывательной форме (предикате) вида «Ученик х занимается в кружке у». Требуется определить такие значения х и у, чтобы высказывательная форма превратилась в истинное высказывание.

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

Рассмотрим условия (1)-(3) и сделаем выводы: Гриша — не фотограф (1); шахматист — не Алёша и не Витя (2); Алёша — не фотограф и не авиамоделист, Гриша — не фотограф и не авиамоделист (3). Отметим это в таблице:

Мы можем сделать вывод, что Алёша занимается математикой, а Гриша — шахматами:

Из того, что Гриша — шахматист и условий (1) и (2) можем расположить учеников по возрасту (в порядке возрастания): Витя — Алёша — Гриша — фотограф. Следовательно, Боря — фотограф.

Ответ: Витя (7 класс) занимается в авиамодельном кружке, Алёша (8 класс) — в математическом, Гриша (9 класс) — в шахматном, Боря (10 класс) — в фотокружке.

Использование таблиц истинности для решения логических задач

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

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

  1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

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

  3. Построить таблицу истинности для полученных логических выражений.

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

  5. Убедиться, что полученное решение удовлетворяет условиям задачи.

Задание 3. Решить задачи

Задача 1. Среди приведенных ниже предложений указать те, которые являются высказываниями, и те, которые не являются: 1) Екатеринбург – столица Урала; 2) студент Уральского федерального университета; 3) Луна – спутник Земли; 4) x  0 ; 5) число 5 – иррациональное.



Задача 2. Среди следующих высказываний указать элементарные и составные, в составных высказываниях выделить грамматические связки: 1) число 9 не делится на 3; 2) число 21 делится на 3 и на 7; 3) число 3 является делителем числа 27; 4) если число 15 делится на 5, то оно делится на 3; 5) число 18 делится на 9 тогда и только тогда, когда 9 делится на 3.

Задача 3 Среди следующих предложений выделить высказывания, установить, истинны они или ложны: 1) река Исеть впадает в Каспийское море; 2) пейте апельсиновый сок; 3) все люди – братья; 4) математическая логика – увлекательная наука; 5) 5  4 ; 6) 5 9 2 x  x  ; 7) 5 9 0 2 x  x   ; 8) для всех натуральных чисел x и y верно равенство x  y  y  x .

Задача 4. Являются ли высказываниями следующие утверждения, установить, истинны они или ложны: 1) сумма корней любого приведенного квадратного уравнения равна свободному члену; 2) сумма корней приведенного квадратного уравнения равна свободному члену; 3) существует приведенное квадратное уравнение, сумма корней которого равна свободному члену.

Задача 5. Пусть x – высказывание «Студент Сидоров изучает информатику», y – высказывание «Студент Сидоров успевает по математической логике». Дать словесную формулировку следующих высказываний: 1) x & y , 2) y  x , 3) x  y .

Задача 6. Обозначить элементарные высказывания буквами и записать следующие высказывания с помощью символов алгебры логики: 1) 4  2 или 4  2 ; 2) если число 24 делится на 3 и 4, то оно делится на 12; 3) 18 кратно 3 6 и 15 не кратно 3; 4) 18 кратно 3 и 15 кратно 3; 5) число 15 – двухзначное и кратно 3 или 5, 6) e   .

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 4

Тема: Формулы логики

Цели:

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

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых шести заданий работы

оценка «3» ставится за верное выполнение любых пяти заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме



Составное высказывание, которое может быть получено из элементарных высказываний путем применения логических операций, называется формулой алгебры логики. Порядок выполнения бинарных логических операций: сначала – конъюнкция, затем – дизъюнкция и в последнюю очередь – импликация и эквивалентность. Логические значения формулы алгебры логики могут быть описаны с помощью таблицы истинности. Формула, истинная при всех значениях входящих в нее переменных, называется тождественно истинной или тавтологией. Формула, ложная при всех значениях входящих в нем переменных, называется тождественно ложной или противоречием. Формула, истинная хотя бы на одном наборе значений входящих в нее переменных и не являющаяся тождественно истинной, называется выполнимой или опровержимой. Задача 3. Составить таблицу истинности для формулы x  y . Решение. Таблица истинности будет иметь следующий вид: x y x y x  y 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1

Задание 2. Решить задачи:

Задачи для самостоятельного решения

1. Проверить, не используя таблиц истинности, являются ли следующие формулы тождественно истинными: 1) x  x ; 2) x & x ; 3) x  x ; 4) x  x & ( x  x & x) ; 5) x & ( x  x) . 8

2. Найти логические значения x и y, при которых выполняются следующие равенства: 1) x  y  y ; 2) 1  x  y  0 .

3. 1) Пусть x истинно, чему равны значения импликаций x  y & z и x & y  y  z ? 2) Пусть эквивалентность x  y и импликация y  x ложны, чему равно значение импликации x  y ? 3) Пусть импликация x  y истинна, чему равны значения импликаций z  ( x  y) и x  y  z ?

4. Пусть x = 1, y = 1, z = 0. Определить логические значения следующих формул: 1) x & y & z , 2) x  y  z , 3) x  ( y  z) , 4) x  y  z , 5) x  y  z .

5. Составить таблицы истинности для следующих формул: 1) x & y , 2) x & y  z , 3) x & y  ( x  y  z) , 4) x  y  x  y & z .

6. Установить, какие из следующих формул являются тождественно истинными, а какие – тождественно ложными: 1) x  ( x  y) , 2) x  ( y  x) , 3) y  x  ( x  y) , 4) (x  y) & ( y  z)  (x  z), 5) x  z  ( y  z  ( x  y  z)) , 6) x  ( y  z)  (x  y  (x  z)) .

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия







ПрактическАЯ РАБОТА№ 5

Тема: Законы алгебры логики

Цели:

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

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых 5 заданий работы

оценка «3» ставится за верное выполнение любых 4 заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме. Выписать в тетрадь основные законы логики

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

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

2) Закон непротиворечия. Логическое мышление характеризуется непротиворечивостью. Противоречия разрушают мысль, затрудняют процесс познания. Требование непротиворечивости мышления выражает формально-логический закон непротиворечия: два несовместимых друг с другом суждения не могут быть одновременно истинными; по крайней мере одно из них необходимо ложно. Данный закон формулируется следующим образом: неверно, что А и не-А (не могут быть истинными две мысли, одна из которых отрицает другую). Закон непротиворечия действует в отношении всех несовместимых суждений.

3) Закон исключенного третьего. Данный закон действует только в отношении противоречащих (контрадикторных) суждений. Он формулируется следующим образом: два противоречащих суждения не могут одновременно быть ложными, одно из них необходимо истинно: А есть либо В, либо не-В. Истинно либо утверждение некоторого факта, либо его отрицание. Противоречащие суждения – это суждения, в одном из которых что-либо утверждается (или отрицается) о каждом предмете некоторого множества, а в другом – отрицается (утверждается) о некоторой части этого множества. Эти суждения не могут быть одновременно ни истинными, ни ложными: если одно из них истинно, то другое ложно и наоборот. Противоречащими являются также два суждения об одном предмете, в одном из которых что-либо утверждается, а в другом то же самое отрицается.

4) Закон достаточного основания. Требование доказанности, обоснованности мысли выражает данный закон: всякая мысль признается истинной, если она имеет достаточное основание. Если есть В, то есть и его основание А. Достаточным основанием мыслей может быть личный опыт человека. Истинность некоторых суждений подтверждается путем их непосредственного сопоставления с фактами действительности. Истинность законов, аксиом подтверждена практикой человечества и не нуждается поэтому в новом подтверждении. Для подтверждения какого-либо частного случая нет необходимости обосновывать его при помощи личного опыта. Достаточным основанием какой-либо мысли может быть любая другая, уже проверенная и установленная мысль, из которой с необходимостью вытекает истинность данной.
Задание 2. Самостоятельно решить задачи:

  1. Для какого из указанных значений числа X ложно выражение
    (X 2) ИЛИ НЕ (X 1)?

1) 1

2) 2

3) 3

4) 4

  1. Для какого из указанных значений числа X истинно выражение
    (X 1) И (X 2) И (Х ≠ 3)?

1)   1

2)   2

3)   3

4)   4

  1. Для какого из приведенных чисел истинно высказывание:

НЕ(Первая цифра четная) И НЕ(Вторая цифра нечетная)?

1) 4562

2) 6843

3) 3561

4) 1234

  1. Для какого символьного выражения неверно высказывание:

Первая буква гласная  ¬ (Третья буква согласная)?

1) abedc      2) becde           3) babas     4) abcab

  1. Для какого имени истинно высказывание:

(Первая буква согласная → Вторая буква гласная) ^ Последняя буква согласная?

1) АЛИСА             2) МАКСИМ          3) СТЕПАН             4) ЕЛЕНА

  1. Для какого имени истинно высказывание:

(Вторая буква гласная → Первая буква гласная) ^ Последняя буква согласная?

  1. 1) АЛИСА               2) МАКСИМ          3) СТЕПАН             4) ЕЛЕНА

7. Для какого из указанных значений числа Х истинно выражение

 (X2))?

1) 1

2) 2

3) 3

4) 4

8. Для какого из указанных значений X истинно высказывание 

((X5))  (X15))?

1) 1

2) 5

3) 10

4) 20

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия

ПрактическАЯ РАБОТА№ 6

Тема: Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)

Цели:

  • научиться решать задачи на ДНФ и КНФ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых 4 заданий работы

оценка «3» ставится за верное выполнение любых 3 заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме. Записать себе в тетрадь основные определения и разобранные примеры.

Стандартный базис. Элементарные формулы — литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.

Стандартный базис — это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.

Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ12 . . . xˆл, называется элементарной конъюнкцией. Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x1x1 = x1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.

Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой, или ДНФ. Например,

x1 x3 + x2 x3x4 + x1 x2 x3 x5.

Если состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, то ДНФ называется совершенной. Приведенный пример — это ДНФ, не являющаяся совершен- ной. Напротив, формула

x1x2x3x4 +x1x2x3x4 +x1x2x3x4

есть совершенная форма.

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

Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.

◀Условимся под xσ понимать формулу x, если σ = 1, и формулу x, если σ = 0. Пусть функция f(y1, . . . , yn) принимает значение 1 на векторе (t1, . . . , tn) (такой вектор называют конституэнтой единицы). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу

в которой сумма (объединение) распространяется на все те наборы (t1, . . . , tn) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество таких наборов не пусто, так что в сумме есть по крайней мере одно слагаемое.

Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f. ▶

Следствие 1.1. Стандартный базис является полным.

◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x1, x2, . . . , xn) = x1x1. ▶

Пример 1.2. Рассмотрим функцию трех переменных m(x1, x2, x3) (табл. 1.4), называемую мажоритарной функцией. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.

Мажоритарная функция имеет 4 конституэнты единицы, а значит, в ее СДНФ должно быть четыре слагаемых. Результат будет следующий:

m(x1,x2,x3)=x1x2x3 +x1x2x3 +x1x2x3 +x1x2x3

Аналогично строится СКНФ. Выбираем конституэнты нуля и для каждой составляем элементарную дизъюнкцию. Получим:

m(x1,x2,x3)=(x1 +x2 +x3)(x1 +x2 +x3)(x1 +x2 +x3)(x1 +x2 +x3). #

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

Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина. Сложение по модулю 2 и умножение — базовые операции кольца Z2, выражения, составленные с их помощью — это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина — это многочлен над кольцом Z2.

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

x+y=x⊕y⊕xy, x=x⊕1.

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

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

Пример 1.4. Рассмотрим множество из единственной функции — штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:

x=x|x, xy=x|y=(x|y)|(x|y), x+y=x|y=(x|x)|(y|y).

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


Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 7

Тема: Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ)

Цели:

  • научиться решать задачи на СДНФ и СКНФ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых семи заданий работы

оценка «3» ставится за верное выполнение любых пяти заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).

Совершенная дизъюнктивная нормальная форма (СДНФ)

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

Примеры: y,   ¬ y,   х1 ∧ ¬ х2 ∧ х3 ∧ х4

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

ДНФ записывается в следующей форме: F1 ∨ F2 ∨ ... ∨ Fn, где Fi - элементарная конъюнкция

Примеры: ¬ х1 ∧ х2 ∨ х1 ∧ ¬ х2 ∨ х1 ∧ ¬ х2 ∧ х3,   ¬ y1 ∨ y1 ∧ y2 ∨ ¬ y2

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х
1, х2, …, хk, причем на i-м месте этой конъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Пример: (¬ х1 ∧ х2 ∧ х3) ∨ (х1 ∧ ¬ х2 ∧ х3) ∨ (х1 ∧ х2 ∧ ¬ х3)

Совершенная конъюнктивная нормальная форма (СКНФ)

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

Примеры: ¬ х3,    х1 ∨ х2,    х1 ∨ х2 ∨ ¬ х3

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

КНФ записывается в следующей форме: F1 ∧ F2 ∧ ... ∧ Fn, где Fi - элементарная дизъюнкция

Примеры: (х1 ∨ ¬ х2) ∧ х3,    (х1 ∨ х2) ∧ ( ¬ х1 ∨ х2 ∨ х3) ∧ ( х1 ∨ ¬ х2 ∨ ¬ х3)

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х
1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Пример: (х1 ∨ х2 ∨ х3) ∧ ( ¬ х1 ∨ ¬ х2 ∨ х3)

Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ.

Алгоритм построения СДНФ по таблице истинности
  1. Выбрать все строки таблицы, в которых значение функции равно единице.

  2. Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

  3. Все полученные конъюнкции связываем операциями дизъюнкции.

Алгоритм построения СКНФ по таблице истинности
  1. Выбрать все строки таблицы, в которых значение функции равно нулю.

  2. Для каждой такой строки записать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

  3. Все полученные дизъюнкции связываем операциями конъюнкции.

Анализ алгоритмов показывает, что если на большей части строк таблицы истинности значение функции равно 0, то для получения ее логической формулы лучше построить СДНФ, в противном случае - СКНФ.

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

x

y

z

F (x, y, z)

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

x

y

z

¬ x

¬ x y z

¬ z

¬ x y ¬ z

F (x, y, z)

0

0

0

1

1

1

1

1

0

0

1

1

1

0

1

1

0

1

0

1

1

1

1

1

0

1

1

1

1

0

1

1

1

0

0

0

0

1

1

0

1

0

1

0

1

0

0

0

1

1

0

0

1

1

1

1

1

1

1

0

1

0

1

1

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

Задание 2. Решить самостоятельно следующие задания:

Пример 1. Найти совершенную дизъюнктивную форму для функции  .

Пример 2. Найти совершенную конъюнктивную нормальную форму для функции  .

Пример 3. Найти дизъюнктивную нормальную форму для следующей формулы:

.

Пример 4. Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы:  .

Пример 5. Найти совершенную дизъюнктивную форму формулы  .

Контроль знаний обучающихся:

  • проверить практическую работу;

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия





ПрактическАЯ РАБОТА№ 8

Тема: Решение задач на построение ряда распределения

и графика функции распределения ДСВ

Цели:

  • научиться решать задачи на построение ряда распределения и графика функции распределения ДСВ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых пяти заданий работы

оценка «3» ставится за верное выполнение любых четырех заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр.52-55

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задание 3. Решить № 167-169, №171,№173,175

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия

ПрактическАЯ РАБОТА№ 9

Тема: Вычисление числовых характеристик ДСВ

Цели:

  • научиться решать задачи на вычисление числовых характеристик ДСВ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых восьми заданий работы

оценка «3» ставится за верное выполнение любых шести заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр.63-64

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задание 3. Решить № 188-199

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия

ПрактическАЯ РАБОТА№ 10

Тема: Нахождение математического ожидания и дисперсии ДСВ

Цели:

  • научиться решать задачи на вычисление математического ожидания и дисперсии ДСВ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых шести заданий работы

оценка «3» ставится за верное выполнение любых пяти заданий работы

Порядок выполнения работы


Задание 1. Записать в тетрадь решение рассмотренных примеров.

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр.67-70

Задание 2. Решить № 200-208

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 11

Тема: Решение задач на запись распределения НСВ

Цели:

  • научиться решать задачи на запись распределения НСВ

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых восьми заданий работы

оценка «3» ставится за верное выполнение любых шести заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр.94-96

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задание 3. Решить № 275-288

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 12

Тема: Вычисление вероятностей для показательного

распределения и нормального распределения.

Цели:

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

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых восьми заданий работы

оценка «3» ставится за верное выполнение любых шести заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр. 109-110

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задание 3. Решить № 324-327

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия



ПрактическАЯ РАБОТА№ 13

Тема: Расчёт по заданной выборке её числовых характеристик.

Цели:

  • научиться решать задачи на расчёт по заданной выборке её числовых характеристик.

Оснащение занятия: конспект лекций.

Критерии оценок

оценка «5» ставится за верное выполнение всех заданий работы

оценка «4» ставится за верное выполнение любых восьми заданий работы

оценка «3» ставится за верное выполнение любых шести заданий работы

Порядок выполнения работы


Задание 1. Ознакомиться с теоретическими знаниями по теме

Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике. Учебное пособие. стр. 151-153

Задание 2. Записать в тетрадь решение рассмотренных примеров.

Задание 3. Решить № 439-449

Требования к оформлению практической работы:

Задание должно быть выполнено в тетради для практических работ

Работу сдать после занятия





Литература

  1. Подольский В. А., Суходский А. М., Мироненко Е. С. Сборник задач по математике: Учеб.пособие, М.: Высшая школа, 2017

  2. Богомолов Н. В. Практические занятия по математике: учебное пособие для средних спец. учеб.заведений, М.: Высшая школа, 2017

  3. П. Е. Данко, А. Г. Попов, Т. Я. Кожевникова. Высшая математика в упражнениях и задачах. М.: ОНИКС, Мир и образование, 2018.

  4. Калинина В. Н., Панкин В. Ф. Математическая статистика: Учебник для студентов средних специальных учебных заведений. М.: Высшая школа, 2016.

  5. В.Е.Гмурман Руководство к решению задач по теории вероятностей и

математической М.: Высшая школа, 2017.

  1. Бабенко К. И. Основы численного анализа. — М.: Наука, 2018

  2. Воеводин В. В. Математические основы параллельных вычислений. — М.: Изд-во МГУ, 2016 .

  3. Бахвалов Н. С. Численные методы. 3-е изд. — М, 2016.

  4. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2017

  5. Демидович Б. П., Марон И. А. Основы вычислительной математики. — 2-е изд. — М.: Государственное издательство физико-математической литературы, 2017









36



Получите в подарок сайт учителя

Предмет: Прочее

Категория: Прочее

Целевая аудитория: Прочее

Автор: Трушникова Галина Петровна

Дата: 11.04.2021

Номер свидетельства: 577912


Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

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

Ваш личный кабинет
Проверка свидетельства