Вводный курс математики. Раздел (модуль) дисциплины Всего часов (в трудоемк ости) Аудиторные Самостоя тельная работа студентов, включая индивиду альные. - презентация

1 Вводный курс математики

2 Раздел (модуль) дисциплины Всего часов (в трудоемкости) Аудиторные Самостоя тельная работа студентов, включая индивидуальные консультации Лекции Семина рские (практические) занятия Лаборат орные занятия 1 семестр 0 Введение. Математические понятия. Построение математических теорий Элементы теории множеств Элементы алгебры высказываний Элементы алгебры предикатов Бинарные отношения Элементы комбинаторики Итого за 1 семестр:

3 Элементы теории множеств

4 Георг Кантор в конце 19 века создал современную теорию множеств. « Множество состоит из элементов.» Множество может быть конечным или бесконечным. «Множество есть многое, мыслимое как единое». Множества можно сравнивать по «мощности».

5 Понятие множества Под множеством понимают совокупность различных объектов или явлений, мыслимую как единое целое. Обозначают множества заглавными буквами латинского алфавита. Например, А – множество студентов 1 курса. Иногда множества имеют особые названия: стадо, труппа, группа, отряд, N, Z, Q, R. Если х является элементом множества А, пишут: х А. Если у не является элементом множества А, пишут: у А.

6 Способы задания множеств 1. Перечислением его элементов А = {a,b,c,d} – множество А состоит из элементов a,b,c,d. Например, С = {кукла, мяч, пирамидка, совок} - множество С состоит из элементов кукла, мяч, пирамидка, совок.

7 Способы задания множеств Не каждое множество можно задать перечислением элементов. Бесконечные множества нельзя задать перечислением элементов. Исключение: бесконечные множества, для которых ясен порядок образования каждого следующего элемента на основе предыдущего. Например, множество натуральных чисел – бесконечное. Но известно, что в нём каждое следующее число, начиная со второго, на 1 больше предыдущего. Поэтому можно задать так: N = {1, 2, 3, 4, …}.

8 Способы задания множеств 2. Описанием характеристического свойства Характеристическое свойство данного множества – это такое свойство, которым обладают все элементы этого множества и не обладает ни один элемент, не принадлежащий этому множеству. Например, D= {х х N Λ х<5} - множество D состоит из элементов х таких, что х N и х<5. характеристическое свойство Описанием характеристического свойства можно задавать как конечные, так и бесконечные множества.

9 Числовые множества Множества, все элементы которых числа, называются числовыми. N = {1, 2, 3,...} – множество натуральных чисел; N 0 = {0, 1, 2, 3,...} – множество целых неотрицательных чисел; Z = {...,-2, -1, 0, 1, 2,...} – множество целых чисел; – множество рациональных чисел; R – множество действительных чисел.

10 Способы задания множеств Одно и то же множество может быть задано разными способами. Например, В = {1,2,3} В = {х x N x<4} В = {х x N x 3} В= {х x N 0

11 Виды числовых промежутков - [a;b] – закрытый числовой промежуток от a до b - [a;b) – полузакрытый слева числовой промежуток от a до b - (a;b] – полузакрытый справа числовой промежуток от a до b - (a;b) – открытый числовой промежуток от a до b - [a;+ ) – закрытый числовой полу промежуток от a до + - (- ;а) – открытый числовой полу промежуток от - до a - (a;+ ) – открытый числовой полу промежуток от a до + - (- ;а] – закрытый числовой полу промежуток от - до a

12 Множество, не содержащее элементов, называется пустым и обозначается Ø. Например, пустыми являются множество космонавтов в нашей аудитории, множество груш, созревших на яблоне. А = {х x N x<0} = Ø, так как нет натуральных чисел, меньших 0. Пустое множество

13 Парадоксы «наивной» теории множеств. «Парадокс брадобрея» Брадобрей бреет тех и только тех жителей деревни, которые не бреются сами. Бреет ли брадобрей себя самого? Способы преодоления парадоксов. Ограничиться только «конструктивно порождаемыми» множествами. Ограничиться только подмножествами хорошо известных «универсальных» множеств.

14 Отношения между множествами 1. Включение Если каждый элемент множества А является элементом множества В, то говорят, что множество А включается во множество В, или множество А – подмножество В. Обозначение: А В Например, M={a,b,c,d,x}, К={a,b,c} К М

15 Часто в той или иной математической теории имеют дело с подмножествами одного и того же множества, которое называют универсальным в этой теории. Например, в школьной алгебре и математическом анализе универсальным является множество R действительных чисел, в геометрии – множество точек пространства. Договоримся, что мы всегда находимся в некотором универсальном множестве и будем его обозначать через U, что пустое множество является подмножеством любого множества.

16 2. Равенство Множества называются равными, если они состоят из одних и тех же элементов. Обозначение: А=В. Например, А={f,k,e},В={k,e,f} А=В Отношения между множествами

17 Утверждение. Если А В и В А, то А=В Таким образом. чтобы доказать, что множества А и В равны, достаточно показать, что А является подмножеством множества В и В является подмножеством множества А. Это наиболее общий способ доказательства равенства двух множеств, который называют универсальным.

18 Круги Эйлера-Венна АВ А=В А В А В А В А=В А В В А Круги Эйлера – это особый чертеж, на котором множества изображаются в виде кругов. Иллюстрация отношений между множествами на кругах Эйлера. А и В не находятся ни в каких отношениях А В В А UU UUU

19 Леонард Эйлер нем.нем. Leonhard Euler Портрет, выполненный Эмануэлем Хандманном (1756) Дата рождения:4 (15) апреля 4 (15) апреля Место рождения:Базель Базель, Швейцария Швейцария Дата смерти:7 (18) сентября 7 (18) сентября 1783 (76 лет )1783 Место смерти:Санкт- Петербург Санкт- Петербург, Российская империя Российская империя Страна: Швейцария Научная сфера:Математика Математика, механика,физика, астрономия механика физика астрономия Альма-матер:Базельский университет Научный руководитель:Иоганн Бернулли

20 Джон Венн John Venn Джон Венн Дата рождения:4 августа 4 августа Место рождения:Кингстон-апон- Халл Кингстон-апон- Халл, Йоркшир,Анг лия ЙоркширАнг лия Дата смерти:4 апреля 4 апреля 1923 (88 лет)1923 Место смерти:Кембридж Кембридж, Англия Англия Страна: Англия Научная сфера:Математическая логика Место работы:Кембридж

21 Операции над множествами 1. Пересечением множеств А и В называется множество, содержащее те и только те элементы, которые принадлежат и множеству А, и множеству В одновременно. А В={х х А Λ х В} Например, А={1,2,3,4} В={2,3,5,8} А В= {2,3} - А В

22 2. Объединением множеств А и В называется множество, содержащее те и только те элементы, которые принадлежат множеству А или множеству В. А В={х х А V х В} Например, А ={a,b,c,d,e}, B={c,m,n} А В={a,b,c,d,e,m,n} Операции над множествами - А В

23 3. Разностью множеств А и В называется множество, содержащее те и только те элементы множества А, которые не принадлежат множеству В. А\В={х х А Λ х В} Пример 1. А={1,2,3,4,5}, В={1,2,3,7,8} А\В={4,5} - А\В Операции над множествами

24 Пример 2. А={1,2,3,4,5} B={1,2,3} A\B={4,5} Пример 3. A={x,y,z} B={x,y,z,f,e} A\B=Ø, B A B А Операции над множествами - А\В так как нет таких элементов множества А, которые не принадлежали бы множеству В.

25 Пример 4. А={1,2,3,4,5} В={1,2,3,4,5} A\B=Ø Пример 5. A={1,2,3,4,5} B={7,6,8,9} A\B={1,2,3,4,5}=A A=B A B Операции над множествами

26 4. Дополнением множества А до универсального множества U называется множество, содержащее те и только те элементы множества U, которые не принадлежат множеству A. Аu={х х U Λ х A} Аu = - А u

27 Задача 1 А-множество всех студентов, присутствовавших на лекции; В – множество студентов группы 1. Изобразите с помощью кругов Эйлера. a.На лекции присутствовали все студенты группы 1. b.На лекции присутствовали некоторые студенты группы 1. c.На лекции присутствовали все студенты группы 1 и только они. d.На лекции не присутствовал ни один студент группы 1. e.Все присутствующие на лекции учатся в группе 1. f.Каждый студент группы 1 присутствовал на лекции.

28 Решение задачи 1 А В А=В А В А В a, f. c.c. b. d. В А e.

29 А – множество букв в слове «универмаг» В – множество букв в слове «лекторий» Найти А В, АUВ, А\В, В\А. Задача 2 Решение: А= {у, н, и, в, е, р, м, а, г}, В = {л, е, к, т, о, р, и, й} А В = {и, е, р} АUВ = {у, н, и, в, е, р, м, а, г, л, к, т, о, й} А\В = {у, н, в, м, а, г} В\А = {л, к, т, о, й}

30 Некоторые улитки являются горами. Все горы любят кошек. Следовательно, все улитки любят кошек. улитки горы Любители кошек неправильно

31 Все крокодилы могут летать. Все великаны являются крокодилами. Следовательно, все великаны могут летать. крокодилы великаны Те кто могут летать правильно

32 Некоторые кочаны капусты являются паровозами. Некоторые паровозы играют на рояле. Следовательно, некоторые кочаны капусты играют на рояле. кочаны паровозы Те кто играет на рояле неправильно

33 Никто не может стать президентом, если у него красный нос. У всех людей нос красный. Следовательно, никто из людей не может быть президентом. Те кто может стать президентом Те у кого красный нос люди правильно

34

35 Огастес (Август) де Мо́рган (англ. Augustus de Morgan, 27 июня 1806, Мадура, Индия 8 марта 1871, Лондон) шотландский математик и логик; профессор математики университетского колледжа в Лондоне ( , ); первый президент (1866) Лондонского математического общества.англ.27 июня 1806Мадура Индия 8 марта 1871Лондонматематиклогикуниверситетского колледжа в Лондоне Лондонского математического общества

36

37 Перечисленные выше равенства справедливы для любых подмножеств A, B, C универсального множества U (поэтому их и называют законами алгебры множеств). Доказательство этих формул легко получить универсальным способом доказательства равенства двух множеств.

38 Докажем формулу 5

39

40 U A B A B A A B

41 U A AA B

42 Пользуясь формулами 1 – 12, можно производить преобразования над множественными выражениями, как над числовыми.

43 Заметим, что если в равенствах 1–10 заменить на, на, U на Ø, Ø на U, то получим соответствующие равенства. утверждения: если в любом равенстве двух выражений алгебры множеств, не содержащих знака разности, заменить на, на, U на, на U, то вновь получится верное равенство (принцип двойственности теории множеств).

44 тогда

45 Задача. Из 100 человек английский язык изучают 27, немецкий – 31, французский –42, английский и немецкий – 7, английский и французский – 11, немецкий и французский – 6. Все три языка изучают три студента. Сколько студентов изучает только один язык? Сколько студентов не изучает ни одного языка? Все 100 А Н Ф Ответ:21

46 Если множество А содержит а элементов, множество В – в э лементов, то множество А В содержит а+в-c, где с - количество элементов множества A B с а-с в-с

47 В НИИ работают 67 человек. Из них 47 знают английский язык, 35 - немецкий язык, а 23 - оба языка. Сколько человек в институте не знают ни английского, ни немецкого языков? А Н

48 .задача. В конкурсе красоты участвовали 22 девушки. Из них 10 было красивых, 12 -умных и 9 -добрых. Только 2 девушки были и красивыми, и умными; 6 девушек были умными и одновременно добрыми. Определите, сколько было красивых и в то же время добрых девушек, если я скажу вам, что среди участниц не оказалось ни одной умной, доброй и вместе с тем красивой девушки?

49 В конкурсе красоты участвовали 22 девушки. Из них 10 было красивых, 12 - умных и 9 -добрых. Только 2 девушки были и красивыми, и умными; 6 девушек были умными и одновременно добрыми. Определите, сколько было красивых и в то же время добрых девушек, если я скажу вам, что среди участниц не оказалось ни одной умной, доброй и вместе с тем красивой девушки? КУ Д ? = 22 К+Д-?+4= ?+4=22 ?=1

50 Декартово произведение множеств Под упорядоченной парой понимают совокупность двух элементов, каждый из которых занимает в записи определенное место. Обозначение: (а; b) - упорядоченная пара. Декартовым произведением множеств А и В называется множество всевозможных упорядоченных пар вида (x; y) таких, что x А и y В. Обозначение: А В - декартово произведение множеств А и В. Символически: А В = {(x; y) x A y В}. Например: А = {, } и В ={,, }. А В = {( ; ), ( ; ), ( ; ),( ; ), ( ; ), ( ; )}

51 ГЛАВА II. АЛГЕБРА ВЫСКАЗЫВАНИЙ § 1. Операции над высказываниями

52 ПРЕДИСЛОВИЕ толковый словарь С. И. Ожегова. : Логика - наука о законах мышления и его формах Слово "логика" происходит от греческого logos, что, с одной стороны, означает "слово", а с другой - "мысль, рассуждение". Логика изучает акты мышления, зафиксированные в языке в виде слов, предложений и их совокупностей. польский логик А. Тарский: Логика создает возможность лучшего взаимопонимания между теми, кто к этому стремится.

53 Логика как наука сформировалась очень давно в IV в. до н.э. Ее создал древнегреческий ученый Аристотель. АРИСТОТЕЛЬ (лат. Aristotle) (384 до н. э., Стагира, полуостров Халкидика, Северная Греция 322 до н. э., Халкис, остров Эвбея, Средняя Греция), древнегреческий ученый, философ, основатель Ликея, учитель Александра Македонского. Отец Аристотеля Никомах, был врачом при дворе македонских царей. Он сумел дать сыну хорошее домашнее образование, знание античной медицины. Влияние отца сказалось на научных интересах Аристотеля, его серьезных занятиях анатомией. В 367, в возрасте семнадцати лет, Аристотель отправился в Афины, где стал учеником Академии Платона.

54 Сохранившиеся произведения Аристотеля по логике: свод «Органон» (труды «Категории», «Об истолковании», первая и вторая «Аналитика», «Топика»); Аристотель исследовал различные формы суждений и их комбинаций и ввел понятие силлогизма, т.е. рассуждения, в котором из заданных двух суждений выводится третье. Он выделил все правильные формы силлогизмов, которые можно составить из суждений: «Все а суть в», «Некоторые а суть в», «Все а не суть в», «Некоторые а не суть в».

55 Все насекомые - шестиногие. У паука - не шесть ног (а восемь!). Следовательно, паук не насекомое. Все числа, кратные 10» оканчиваются нулем. Число п не оканчивается нулем. Следовательно, число п не кратно 10. Эти короткие, одношаговые рассуждения (умозаключения) имеют одну и ту же форму: Все А это В. не В, Следовательно, не А. Умозаключение такой формы всегда приводит к верному (истинному) выводу (заключению, следствию), если исходные утверждения посылки) истинны.

56 Логика как наука сформировалась очень давно -в IV в. до н.э. Ее создал древнегреческий ученый Аристотель. В течение многих веков логика сколько- нибудь существенно не развивалась. Это, конечно, свидетельствует о гениальности Аристотеля, которому удалось создать столь полную научную систему, что, казалось, "неубавить, не прибавить". Однако в силу такой неизменности логика приобрела славу мертвой, застывшей науки и вызывала у многих скептическое к себе отношение.

57 В XVII в. великий немецкий ученый Лейбниц ( ) задумал создать новую логику, которая была бы "искусством исчисления". В этой логике, по мысли Лейбница» каждому понятию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила в то время распространения и развития.

58 ЛЕЙБНИЦ (Leibniz) Готфрид Вильгельм ( ), немецкий философ, математик, физик, языковед. С 1676 на службе у ганноверских герцогов. Основатель и президент (с 1700) Бранденбургского научного общества (позднее Берлинская АН). По просьбе Петра I разработал проекты развития образования и государственного управления в России. Предвосхитил принципы современной математической логики («Об искусстве комбинаторики», 1666). Один из создателей дифференциального и интегрального исчислений.

59 Только в середине XIX в. ирландский математик и логик Джордж Будь ( ) частично воплотил в жизнь идею Лейбница. Им была создана алгебра логики, в которой действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а предложения. БУЛЬ Джордж (George Boole) (2 ноября 1815, Линкольн, Великобритания 8 декабря 1864, Баллинтемпль, Ирландия), английский математик и логик, один из основоположников математической логики. Разработал алгебру логики (булеву алгебру) («Исследование законов мышления», 1854), основу функционирования цифровых компьютеров.

60 Д. Буль родился в бедной рабочей семье. Первые уроки математики получил у отца. Хотя мальчик посещал местную школу, в общем его можно считать самоучкой. В 12 лет знал латынь, затем овладел греческим, французским, немецким и итальянским языками. В 16 лет уже преподавал в деревенской школе, а в 20 открыл собственную школу в Линкольне. В редкие часы досуга зачитывался математическими журналами Механического института, интересовался работами математиков прошлого Ньютона, Лапласа, Лагранжа, проблемами современной алгебры.

61 Алгебра логики Буля явилась зародышем новой науки - математической логики. В отличие от нее логику, восходящую к Аристотелю, называют классической или традиционной формальной логикой. В названии "математическая логика" отражены две характерные черты этой науки: во-первых, математическая логика - это логика, использующая язык и методы математики; во- вторых, математическая логика была вызвана к жизни потребностями математики.

62 сегодня математическая логика используется в биологии, медицине, лингвистике, педагогике, психологии, экономике, технике. Велика роль математической логики в развитии вычислительной техники: она используется в конструиронании компьютеров и при разработке искусственных языков для общения с ними. Большой вклад в развитие математической логики сделали ученые разных стран: Г. Фреге, Д. Гильберт, Д. Пеано, Б. Рассел, Гедель,П.С. Новиков, А.Н. Колмогоров, Я. Лукасевич, А. Тар:кий, А.Черч, А.Тьюринг, А.А.Марков, Н.А.Шанин и многие другие.

63 ГЛАВА I. ЛОГИКА ВЫСКАЗЫВАНИЙ § 1. Операции над высказываниями

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

65 Примеры высказываний "Москва - столица России." "Волга впадает в Черное море." «2+2=4.» «Если 2+2=5, то Омск - столица России.» Примеры не высказываний «2+х=5.» «Ура!» «Омск - столица России?»

66 Простыми (элементарными) высказываниями называются такие высказывания, которые не расчленяются на другие высказывания. Союзы «и», «или», «если... то,..», «…тогда и только тогда, когда…..» и частицу «не» (словосочетание «неверно, что…») будем называть логическими связками. Высказывания, образованные из других высказываний с помощью логических связок (или союзов, к ним сводящихся), называют составными.

67 Определение. Отрицанием высказывания A называется высказывание «не A», обозначаемое через A или (читается «не »), которое считается истинным, если А ложно, и ложным, если А истинно. A 10 01

68 Определение. Конъюнкцией высказываний A и B называется высказывание « A и B », обозначаемое посредством A B, которое истинно тогда и только тогда, когда оба высказывания A и B истинны. AB A B

69 Определение. Дизъюнкцией высказываний A и B называется высказывание « A или B », обозначаемое посредством A B, которое ложно тогда и только тогда, когда оба высказывания A и B ложны AB A B Заметим, что в обычной речи союз «или» употребляется в двух различных смыслах: В исключающем смысле: или, или, но не оба. Например, «Он будет учиться в университете или совсем не будет учиться». В неисключающем смысле: или, или, или оба. Например, «Число является корнем уравнения или уравнения ». В дизъюнкции, как это следует из определения 3, союз «или» употребляется в неисключающем смысле.

70 Определение. Импликацией высказываний A и B называется высказывание « если A, то B », обозначаемое посредством A B, которое ложно тогда и только тогда, когда высказывание A истинно, а B ложно. AB A B При этом высказывание А называют посылкой, а высказывание В – заключением.

71 Определение. Эквиваленцией высказываний A и B называется высказывание «для необходимо А и достаточно В », обозначаемое посредством A B, которое истинно тогда и только тогда, когда оба высказывания A и B обновременно либо истинны, либо ложны. AB A B

72 Итоговая таблица истинности для логических операций AB AA B oo

73 Замечание. Наряду с операциями отрицания, дизъюнкции, конъюнкции, импликации и эквиваленции в литературе встречаются также операции стрелка Пирса ( ), штрих Шеффера ( ), сумма Жегалкина (+ – сложение по модулю 2). Приведем их определение через таблицы истинности: ABA B A+B

74 § 2. Формулы алгебры высказываний и их равносильность

75 введем в рассмотрение следующие символы: логические константы 1 – символ истины, 0 – символ лжи; высказывательные переменные X, Y, Z, X 1 …..; логические операции -,,,, ; знаки пунктуации (, ). Конечные последовательности указанных символов будем называть выражениями алгебры высказываний. Высказывательные переменные, логические константы и выражения, полученные из них с помощью знаков логических операций и знаков пунктуации, называются формулами алгебры высказываний.

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

77 Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется тождественно истинной, или тавтологией, если для любых высказываний A 1,A 2,…,A n ее значение F(A 1,A 2,…,A n ) является истинным высказыванием Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется тождественно истинной, или тавтологией, если для любого набора истинностных значений для переменных X 1,X 2,…,X n ее истинностное значение равно 1.

78 Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется тождественно ЛОЖНОЙ или противоречием если для любых высказываний A 1,A 2,…,A n ее значение F(A 1,A 2,…,A n ) является ложным высказыванием Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется тождественно ложной, или противоречием, если для любого набора истинностных значений для переменных X 1,X 2,…,X n ее истинностное значение равно 0.

79 Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется выполнимой, если для некоторых высказываний A 1,A 2,…,A n ее значение F(A 1,A 2,…,A n ) является истинным высказыванием Определение. Формула F(X 1,X 2,…,X n ) алгебры высказываний называется тождественно истинной, или тавтологией, если для некоторого набора истинностных значений для переменных X 1,X 2,…,X n ее истинностное значение равно 1.

80 Т е о р е м а 1. Если формулы F и F G являются тавтологиями, то и формула G – тавтология. Определение 8. Формулы F и G алгебры высказываний называются равносильными, если при подстановке вместо переменных любых высказываний значения этих формул будут одновременно истинными или ложными высказываниями. Обозначение: F G

81 Определение. Высказывание, которое получается из какой- либо тавтологии подстановкой вместо высказывательных переменных конкретных высказываний, называется логически истинным (в логике высказываний). О таком высказывании можно сказать, что оно истинно уже в силу одной только своей функционально-истинностной структуры. Примером может служить высказывание: «Если идет экзамен или идет зачет и не идет зачет, то идет экзамен», которое можно получить подстановкой в тавтологию (X Y) X X (проверьте, что это тавтология!).

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

83 Т е о р е м а 2 (о свойствах отношения равносильности формул). Для формул F, G и H справедливы следующие свойства: 1. F F, т.е. отношение равносильности рефлексивно; 2. Если F G, то G F, т.е. отношение равносильности симметрично; 3. если F G и G H, то F H, т.е. отношение равносильности транзитивно. Доказательство очевидно.

84 Т е о р е м а 3 (признак равносильности формул). Формулы F и G являются равносильными тогда и только тогда, когда эквиваленция F G есть тавтология.

85 Наименование закона Равносильные формулы F i F j 1. Коммутативности (F 1 F 2 ) (F 2 F 1 ); (F 1 F 2 ) (F 2 F 1 ) 2. Ассоциативности F 1 (F 2 F 3 ) (F 1 F 2 ) F 3 ; F 1 (F 2 F 3 ) (F 1 F 2 ) F 3 3. Дистрибутивност и F 1 (F 2 F 3 ) (F 1 F 2 ) (F 1 F 3 ); F 1 (F 2 F 3 ) (F 1 F 2 ) (F 1 F 3 ) 4. Идемпотентности F F F; F F F 5. Исключенного третьего F F 1; 6. Противоречия F F 0 7. Де Моргана (F 1 F 2 ) F 1 F 2 ; (F 1 F 2 ) F 1 F Поглощения F 1 (F 1 F 2 ) F 1 ; F 1 (F 1 F 2 ) F 1

86 9. двойное отрицания ( F) F 10. Свойства констант F 0 F; F 0 0; F 1 1; F 1 F ; Исключения импликации F G 13. Введения дизъюнкции F G 14. Введения конъюнкции F G (F G ) 15. Замены эквиваленции F G ( F G) ( G F) 16. Контрапозиции F G G F 17. Противоположностей F G

87 F1F1 F2F2 F 1 F 2 F 1 (F 1 F 2 ) Пример. Сравните значения в первом и четвертом столбцах! Так можно проверить закон поглощения F 1 (F 1 F 2 ) F 1.

88 Замечание. Если формула F содержит подформулу F i, то замена подформулы F i в формуле F на эквивалентную ей формулу F j не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо формулы F i новой формулы F j, то эту операцию нужно выполнить всюду по символу F i. Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.

89 Пример: Упростить ((F 1 F 2 ) (F 2 F 3 )) (F 1 F 2 F 3 ). 1. Удалить всюду логическую связку : (( F 1 F 2 ) ( F 2 F 3 )) ( (F 1 F 2 ) F 3 ) 2. Опустить отрицание на элементарные формулы по закону де Моргана: ( ( F 1 F 2 ) (F 2 F 3 )) ( F 1 F 2 ) F 3 Выполнить преобразование по закону поглащения ( F 1 F 2 ) F 3

90 § 3. Логическое следование и логическая равносильность формул алгебры высказываний

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

92 Определение. Говорят, что из формулы F логически следует формула G, и пишут F G, если при подстановке вместо переменных любых высказываний всякий раз, когда значение формулы F будет истинным высказыванием, значение формулы G также будет истинным высказыванием. Пример. Доказать, что (X Y) Z X Z

93 XYZ (X Y) ZX Z

94 Т е о р е м а 1 (о свойствах логического следования для высказывательных формул). Для любых формул F, G и H справедливы следующие свойства: 1. F F, т.е. отношение логического следования рефлексивно; 2. если F G и G H, то F H, т.е. отношение логического следования транзитивно; 3. из любой формулы F логически следует любая тавтология T, т.е. F T.

95 Т е о р е м а 2 (признак логического следования для высказывательных формул). Из формулы F логически следует формула G тогда и только тогда, когда импликация F G является тавтологией.

96 Определение. Говорят, что из формул F 1, F 2,…, F n логически следует формула G, и пишут F 1, F 2,…, F n G, если при подстановке вместо переменных любых высказываний всякий раз, когда значение формул F 1, F 2,…, F n будет одновременно истинными высказываниями, значение формулы G также будет истинным высказыванием.

97 Теорема 2 а. Пусть даны формулы F 1, F 2,…, F n и формула G. Формула G есть логическое следствие F 1, F 2,…, F n тогда и только тогда, когда формула (( F 1 F 2 … F n ) G) тавтология. Теорема 3. Пусть даны формулы F 1, F 2,…, F n и формула G. Формула G есть логическое следствие F 1, F 2,…, F n тогда и только тогда, когда ((F 1 F 2 … F n G) противоречива.

98 § 3. Соответствия

99 Декартово произведение множеств Под упорядоченной парой понимают совокупность двух элементов, каждый из которых занимает в записи определенное место. Обозначение: (а; b) - упорядоченная пара. Декартовым произведением множеств А и В называется множество всевозможных упорядоченных пар вида (x; y) таких, что x А и y В. Обозначение: А В - декартово произведение множеств А и В. Символически: А В = {(x; y) x A y В}. Например: А = {, } и В ={,, }. А В = {( ; ), ( ; ), ( ; ),( ; ), ( ; ), ( ; )}

100 Понятие соответствия Соответствием f из множества А во множество В называется любое подмножество А В. Символически: f А В или f :А В - соответствие f из множества А во множество В. область отправления область прибытия. Например, зададим различные соответствия из множества А = {, } во множество В ={,, }. f = {( ; ), ( ; ), ( ; ), ( ; )}, g = {( ; ),( ; ), ( ; )}, h = {( ; ),( ; ), ( ; )} и т. п.

101 Образы и прообразы Если пара вида (a;b) принадлежит соответствию f, то b - образ элемента а, а - прообраз элемента b при соответствии f. Например, рассмотрим соответствие f = {( ; ), ( ; )} из множества А = {, } во множество В ={,, }. Тогда - образ - образ - прообраз - прообраз при данном соответствии f.

102 Способы задания соответствий 1. Перечисление упорядоченных пар 2. Указание характеристического свойства 3. Граф 4. График 5. Таблица

103 Перечисление упорядоченных пар Упорядоченные пары, принадлежащие данному соответствию, перечисляются через запятую в фигурных скобках. Например, пусть А = {1; 2; 3; 4}, B={2;3}. Зададим f :А В перечислением упорядоченных пар: f = {(2;2), (3;3);(4;2)}. Данный способ используется для задания соответствия только между конечными множествами.

104 Указание характеристического свойства Указывается, по какому правилу строятся упорядоченные пары, принадлежащие соответствию f. Например, пусть А = {1; 2; 3; 4}, B={2;3}. Зададим f :А В указанием характеристического свойства: f={(x;y) x A y B х у}. Данный способ используется для задания соответствия как между конечными, так и между бесконечными множествами, но только в том случае, если известно правило, по которому строятся упорядоченные пары, принадлежащие соответствию f.

105 Граф Граф – это особый чертеж, на котором элементы множеств А и В изображаются точками в отдельных строках. Если пара (х;у), где х А и у В, принадлежит соответствию f, то х соединяется с у стрелкой. Данный способ используется для задания соответствия только между конечными множествами.

106 График Каждой упорядоченной паре вида (х;у) f, соответствует единственная точка на координатной плоскости с координатами (х;у). Графиком соответствия f является совокупность построенных точек. Данный способ используется для задания соответствия как между конечными, так и между бесконечными, но только числовыми множествами. Например, пусть А = {1;2;3;4}, B={2;3}. Построим график соответствия f :А В, если f = {(2;2), (3;3);(4;2)}.

107 Таблица В первом столбце таблицы записывают элементы множества А, а в первой строке – элементы множества В. Если пара (х;у) принадлежит f:А В, то в соответствующей клетке таблицы записывается 1. Если пара (с;d) не принадлежит f:А В, то в соответствующей клетке таблицы записывается 0. Например, пусть А = {1;2;3;4}, B={2;3}. Построим таблицу соответствия f :А В, если f = {(2;2), (3;3);(4;2)}. Данный способ используется для задания соответствия только между конечными множествами.

108 Область определения и множество значений соответствия Областью определения М соответствия f: A B называется множество элементов, каждый из которых принадлежит множеству А и имеет хотя бы один образ во множестве В. Множеством значений Д соответствия f: A B называется множество элементов, каждый из которых принадлежит множеству В и имеет хотя бы один прообраз во множестве А. Например, соответствие f: А В, где А = {-1; 0; 2; 3}, В = {0; 1; 2; 3}, задано c помощью графика. Областью определения соответствия f является множество М ={-1; 2; 3}, множеством значений - Д = {2; 3}.

109 Функции Соответствие f: A B называется функцией, если каждый элемент множества А имеет не более одного образа во множестве В. Пример 1: Соответствие f: А В, где А = {х; у; с}, В = {k; h}, задано c помощью графа. f:А В – функция, так как каждый элемент множества А имеет не более 1 образа во множестве В. Пример 2: Соответствие f: А В, где А = {х; у}, В = {w; k; h}, задано c помощью графа. f: А В – не является функцией, так как неверно, что каждый элемент множества А имеет не более 1 образа во множестве В. Существует элемент у А, который имеет 2 образа во множестве В.

110 Отображения Соответствие f: A B называется отображением, если каждый элемент множества А имеет единственный образ во множестве В. Пример 1: Пусть соответствие f: А В, где А = {х; у; с}, В = {k; h}, задано c помощью графа. f: А В – отображение, так как каждый элемент множества А имеет единственный образ во множестве В. Пример 2: Пусть соответствие f: А В, где А = {-2; -1; 0; 1;2}, В = {1; 2}, задано c помощью графика. f: А В – не является отображением, так как неверно, что каждый элемент множества А имеет единственный образ во множестве В. Существует элемент -2 А, который не имеет образов во множестве В.

111 Свойства функций и отображений 1. Инъективность 2. Сюръективность 3. Биективность

112 Инъективность Отображение (функция) из множества А во множество В называется инъективным (инъективной), если каждый элемент множества В имеет не более одного прообраза во множестве А. Пример 1: Функция и отображение f: А В, где А = {у; с}, В = {k; h, х}, является инъективной (ым), так как верно, что каждый элемент множества В имеет не более 1 прообраза во множестве А. Пример 2: Функция и отображение f: А В, где А = {х; у; с}, В = {k; h}, не является инъективной (ым), так как неверно, что каждый элемент множества В имеет не более 1 прообраза во множестве А. Во множестве В существует элемент h, который имеет 2 прообраза во множестве А.

113 Сюръективность Отображение (функция) из множества А во множество В называется сюрьективным (сюрьективной), если каждый элемент множества В имеет не менее одного прообраза во множестве А. Пример 1: Функция и отображение f: А В, где А = {х; у; с}, В = {k; h}, является сюръективной (ым), так как верно, что каждый элемент множества В имеет не менее 1 прообраза во множестве А. Пример 2: Функция f: А В, где А = {х; у; с}, В = {k; h}, не является сюръективной, так как неверно, что каждый элемент множества В имеет не менее 1 прообраза во множестве А. Во множестве В существует элемент k, который не имеет прообразов в А.

114 Биективность Отображение (функция) из множества А во множество В называется биективным (биективной), если каждый элемент множества В имеет единственный прообраз во множестве А. Еще говорят, что отображение (функция) из множества А во множество В является биективным (ой), если оно (она) одновременно инъективное (ая) и сюръективное (ая). Пример: Функция и отображение f: А В, где А = {х; у; с}, В = {w, k; h}, является биективной (ым), так как верно, что каждый элемент множества В имеет единственный прообраз во множестве А.

115 Понятие бинарного отношения Бинарным отношением, заданным на множестве А, называется любое соответствие из множества А во множество А, т.е. любое подмножество декартова произведения множеств А А. - «тау» Обозначение: А А, : А А. (х;у) х у – х вступает в отношение с у. (х;у) х у – х не вступает в отношение с у.

116 СПОСОБЫ ЗАДАНИЯ БИНАРНЫХ ОТНОШЕНИЙ 1. Указание характеристического свойства 2. Перечисление упорядоченных пар 3. Граф 4. График 5. Таблица

117 Указание характеристического свойства А = {1,2,3} : А А = {(x;y) x A y А x y } характеристическое свойство Указанием характеристического свойства можно задавать бинарное отношение как на конечном, так и на бесконечном множестве, если существует закономерность образования упорядоченных пар, из которых оно состоит.

118 Перечисление упорядоченных пар = {(1;1), (1;2), (1;3), (2;2), (2;3), (3;3)} Перечислением упорядоченных пар можно задавать бинарное отношение только на конечном множестве.

119 Граф Граф бинарного отношения имеет свои особенности: Элементы множества изображаются в произвольном порядке. Если элемент вступает в отношение сам с собой, то на графе это отмечается петлей. Одна и та же стрелка может иметь два направления. Для удобства изображения элементы упорядоченных пар можно соединять дугой. Построим граф рассматриваемого бинарного отношения. Графом можно задавать бинарное отношение только на конечном множестве.

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

121 Таблица Если упорядоченная пара принадлежит бинарному отношению, то в соответствующей клетке таблицы записывается 1, иначе – 0. Таблицей можно задавать бинарное отношение только на конечном множестве. Построим таблицу рассматриваемого бинарного отношения.

122 Свойства бинарных отношений Рефлексивность Антирефлексивность Симметричность Антисимметричность Транзитивность Связность

123 Рефлексивность Отношение, заданное на множестве А, называется рефлексивным тогда и только тогда, когда каждый элемент множества А вступает в отношение сам с собой. На графе рефлексивного бинарного отношения каждый элемент имеет петлю. - рефлексивно. - не рефлексивно.

124 Отношение, заданное на множестве А, называется антирефлексивным тогда и только тогда, когда каждый элемент множества А не вступает в отношение сам с собой. На графе антирефлексивного бинарного отношения ни один элемент не имеет петли. Антирефлексивность - антирефлексивно. - не антирефлексивно.

125 Симметричность Отношение называется симметричным на множестве А тогда и только тогда, когда для любых двух элементов х и у из этого множества верно, что если элемент х вступает в отношение с элементом y, то элемент y не вступает в отношение с х. На графе симметричного отношения каждая имеющаяся стрелка указывает 2 направления. - симметрично. - не симметрично.

126 Антисимметричность Отношение называется антисимметричным на А тогда и только тогда, когда для любых двух элементов x и y из множества А верно, что, если х вступает в отношение с у и х у, то у не вступает в отношение с х. На графе антисимметричного бинарного отношения каждая имеющаяся стрелка указывает единственное направление. - антисимметрично. - не антисимметрично.

127 Транзитивность Отношение называется транзитивным на множестве А тогда и только тогда, когда для любых трех элементов х, у и z из этого множества верно, что если элемент х вступает в отношение с элементом y и элемент y вступает в отношение с элементом z, то элемент x вступает в отношение с z. - транзитивно. - не транзитивно.

128 Связность Отношение называется связным на множестве А тогда и только тогда, когда для любых двух элементов x и y из этого множества верно, что x вступает в отношение с y или y вступает в отношение с x. На графе связного отношения между любыми двумя элементами есть стрелка хотя бы в одном направлении. - связно. - не связно.

129 Типы бинарных отношений Бинарные отношения отношение эквивалентности отношение порядка рефлексивность, симметричность, транзитивность строгогонестрогого антирефлексивность, антисимметричность, транзитивность рефлексивность, антисимметричность, транзитивность

130 Бинарные отношения линейного порядка - отношение линейного порядка строгогонестрогого - антирефлексивно, антисимметрично, транзитивно, связно - рефлексивно, антисимметрично, транзитивно, связно