РАБОЧАЯ ТЕТРАДЬ по учебной дисциплине «Дискретная математика с элементами математической логики» (для обучающихся 2 курса) специальность: 09.02.07 «Информационные системы и программирование»
учебно-методическое пособие

Министерство образования и науки Хабаровского края

Краевое государственное бюджетное

профессиональное образовательное учреждение

«Хабаровский промышленно-экономический техникум»

РАБОЧАЯ ТЕТРАДЬ

по учебной дисциплине «Дискретная математика с элементами математической логики»  (для обучающихся 2 курса)

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

Хабаровск, 2022 г

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

Автор-составитель:  Серганова Марина Сергеевна, преподаватель высшей категории КГБ ПОУ ХПЭТ

Рабочая тетрадь по дисциплине «Дискретная математика с элементами математической логики» для обучающихся 2 курса, /Серганова М.С.–Хабаровск, 2022. –23с.

Содержание

АННОТАЦИЯ

Рабочая тетрадь по учебной дисциплине «Дискретная математика с элементами математической логики», специальность 09.02.07 «Информационные системы и программирование» включает в себя:

- аннотацию;

- пояснительную записку;

- Раздел «Основы математической логики» (Теория, задания для обучающихся)

- Раздел «Элементы теории множеств» (Теория, задания для обучающихся)

- Раздел «Логика предикатов» (Теория, задания для обучающихся)

- Перечень рекомендуемой литературы для изучения предмета.

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

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

Рабочая тетрадь по учебной дисциплине «Дискретная математика с элементами математической логики», специальность 09.02.07 «Информационные системы и программирование» является частью основной профессиональной образовательной программы в соответствии с ФГОС СПО.

Составлена в соответствии с Федеральным государственным образовательным стандартом среднего (полного) общего образования, утвержденного приказом Министерства образования и науки РФ от 17.05.2012 г. № 413, и программой учебной дисциплины «Дискретная математика с элементами математической логики» для специальностей среднего профессионального образования.

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

В структуру тетради входят 3 раздела. Рабочая тетрадь по дисциплине «Дискретная математика с элементами математической логики», , к разделам «Основы математической логики», «Элементы теории множеств», «Логика предикатов» предназначена для изучения этой дисциплины в учреждении профессионального образования КГБ ПОУ ХПЭТ, реализующего программу подготовки специалистов среднего звена. Эта тетрадь составлена в соответствии с методическими рекомендациями.

В рабочую тетрадь входят:

1. Аннотация

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

3. Раздел «Основы математической логики» (Теория, задания для обучающихся)

4. Раздел «Элементы теории множеств» (Теория, задания для обучающихся)

5. Раздел «Логика предикатов» (Теория, задания для обучающихся)

6. Перечень рекомендуемой литературы для изучения предмета.

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

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

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

ИНСТРУКЦИЯ ПО РАБОТЕ С ТЕТРАДЬЮ

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

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

выполнение 55% от всей работы -  оценка «3», 56%-90%- оценка «4», выше 90% – «5»;

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

Раздел 1 Основы математической логики.

Несмотря на разнообразие компьютеров в современном мире, все они строятся по единой принципиальной схеме, основанной на фундаменте идеи программного управления Чарльза Бэббиджа (середина XIX в). Эта идея была реализована при создании первой ЭВМ ENIAC в 1946 году коллективом учёных и инженеров под руководством известного американского математика Джона фон Неймана, сформулировавшего концепцию ЭВМ с вводимыми в память программами и числами -программный принцип.

Главные элементы концепции:

1. Двоичное кодирование информации;
2. Программное управление;
3. Принцип параллельной организации вычислений, согласно которому операции над числом проводятся по всем его разрядам одновременно.
4. Принцип хранимой программы;

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

Сам термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, речь, разум».

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

Логика использует ряд основных понятий и описывает действия над ними, подчиняющиеся законам логики. К этим основным понятиям логики относятся следующие.

Высказывание (суждение) — некоторое предложение, которое может быть истинно (верно) или ложно. Например, высказывание «сегодня хорошая погода» является истинным (принимает значение «истина»), если светит солнце, нет ветра и дождя и т. д. В противном случае это же высказывание будет ложным (принимает значение «ложь»). Рассуждая аналогично, в другом примере высказывания А>5, очевидно, приходим к тому, что оно истинно, если переменная А принимает любое значение, большее 5, и ложно в противном случае. Заметим, что любое высказывание не может быть одновременно истинным и ложным, а принимает только одно из этих двух возможных логических значений: истина или ложь. Эти значения называются логическими постоянными, или логическими константами.

Утверждение — суждение, которое требуется доказать или опровергнуть, например, сумма внутренних углов треугольника равна 180°.

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

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

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

Логическое выражение представляет собой запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая единица) или ЛОЖЬ (логический ноль). Приведем некоторые примеры логических выражений:

а>5, где а — переменная, принимающая любое значение. При
значениях а>5 это логическое выражение истинно (равно логической 1), иначе — ложно (равно логическому 0).

Компьютер имеет оперативную память объемом не менее 32Мб.
В одном компьютере это справедливо, то есть такое логическое
выражение истинно (равно логической 1), а в другом — это же
выражение может оказаться ложным (равно логическому 0).

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

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

Логические выражения и логические операции

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

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в ХХ веке ее положения нашли применение в разработке различных электронных схем. Законы и аппарат алгебры логики стали использоваться при проектировании различных частей компьютеров (память, процессор).

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

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

Конъюнкция (логическое умножение). Сложное высказывание 

АʌВ истинно тогда и только тогда, когда оба высказывания истинны одновременно. Истинность такого высказывания задается следующей таблицей:

Обозначим 0 – ложь, 1 – истина

Дизъюнкция (логическое сложение). Сложное высказывание A˅В ложно тогда и только тогда, когда А и В ложны одновременно. Таблица истинности для логической суммы высказываний имеет вид:

Инверсия (логическое отрицание). Присоединение частицы НЕ (NOT) к данному высказыванию называется операцией отрицания (инверсии). Она обозначается Ā (или ¬А)и читается не А . Если высказывание А истинно, то В ложно, и наоборот. Таблица истинности в этом случае имеет вид

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

Таблица истинности операции импликации:

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

Таблица истинности операции эквивалентности:

Пример решения задачи: С помощью таблицы истинности доказать следующее тождества:        

В выделенных столбцах совпадают цифры, значит, тождество верное.

1. Задания для обучающихся.

1.1 Заполните пропуски:

а)Логика (от греческого слова «logos» - ________________________) – совокупность наук о ________________ и __________________ мышления, о наиболее общих законах _________________.

б) Начало исследования в области формальной логики было положено работами ____________________ в ______________

в) Логика оперирует __________________________________________

г) Математическая логика применяет для анализа рассуждений __________________________________________________________________

д) Основоположник алгебры логики ____________________________

е) Высказывание — повествовательное предложение, о котором можно сказать, ______________ оно или ______________

ж) Алгебра логики занимается исследованием ___________________

____________________________

1.2 Закончите предложения:

а) Суждение – это ____________________________________________
__________________________________________________________________

б) Умозаключение – это_______________________________________
__________________________________________________________________

в)Логическое выражение – это _________________________________

__________________________________________________________________

1.3 Какие из приведенных высказываний являются истинными, а какие ложными? Перечислите через запятую в строках таблицы.

а) Земля – это звезда

б) 5>3

в) 4-1=10

г) Париж – это столица Англии

д) Москва – столица России

е) Корова – млекопитающее.

1.4 Заполните пропуски в таблицах истинности:

а)                                    б)

в)                

г)                                                         д)

1.5 Поставить в соответствие определение логических операций и их названий:

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

б) Сложное высказывание ложно тогда и только тогда, когда А и В ложны одновременно.

в) Если высказывание А истинно, то В ложно, и наоборот.

г) Сложное высказывание АʌВ истинно тогда и только тогда, когда оба высказывания истинны одновременно.

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

1.6 С помощью таблицы истинности доказать (или опровергнуть) равносильность следующего тождества:

Вывод: ______________________________________________

Раздел 2 Элементы теории множеств.

Множество- это любая определенная совокупность объектов. Объекты, из которых состоит множество, называется его элементами или точками – Если а элемент множества А, то пишут а∈А. Если А и В состоят из одних и тех же элементов, то говорят, что они совпадают, и пишут А=В.

Подмножеством множества А называется такое множество В, каждый элемент которого принадлежит множеству А.

Объединением множеств А и В называется множество А∪В, содержащее все элементы множества А и множества В, которые принадлежат хотя бы одному из множеств А или В.

А∪В={x/x∈A∨x∈B}

Пересечением множеств А и В называется множество А∩В, содержащее те элементы множества А и множества В, которые входят одновременно в оба множества, А∩В={x/x∈а∧x∈B}

Разностью множеств А и В называется множество А\В, состоящее из тех элементов,  которые лежат в А, но не лежат в В.

A\B={x/x∈A∧x∉B}

Дополнением множества А называется множество , состоящее из всех элементов, которые не принадлежат А={x/x∉A}

Пусть А и В множества,а∈А, b∈B, запишем их в определенные пары и обозначим

(a,b), такая пара элементов называется упорядоченной. Две упорядоченные пары (a,b) и (c,d)называются равными, если равны их соответственные элементы: a=c∧b=d

Прямым (декартовым) произведением множеств A и B называется множество всех упорядоченных пар этих множеств.

AB={(a,b)/a∈A,b∈B}, ABB×A

Если A=B, то А×А=А2 называется декартов квадрат. Любое подмножество прямого произведения А×В называется бинарным отношением  р между элементами этих множеств.

p∈A×В , элементами отношения являются упорядоченные пары,  форма записи a p b, (a,b)∈p, означает, что a и bнаходятся в отношении p. Если АВ, то говорят о бинарном отношении на множестве А.

Свойства бинарных отношений

1. Бинарное отношение р, заданное на множестве А, называется рефлексивным, если элемент этого множества находится в данном отношении сам с собой ∀а∈А,(а,а)∈р
2. Бинарное отношение р, заданное на множестве А, называется симметричным, если для любых элементов a, b, c∈Aиз того, что (a,b)∈p⇒ (b,a)∈p
3. Бинарное отношение р, заданное на множестве А, называется транзитивным, если для любых элементов a, b, c∈Aвыполняется (a,b)∈p∧(b,c)∈p
4. Бинарное отношение р, заданное на множестве А, называется антисимметричным, если для любых элементов a,b∈A,(a,b)∧(b,a)∈p⇒a=b;(a,b)∈p∧a≠b ⇒(a,b)∉p
5. Бинарное отношение р, заданное на множестве А, называется связанным, если для любых элементов a,b∈A,a=b∨(a,b)∈p∨(b,a)∈p
6. Бинарное отношение р, заданное на множестве А, называется антирефлексивным, если ∀a∈A,(a,a)∉p

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

Бинарное отношение R, заданное на множестве А, называется отношением эквивалентности, если оно

1. Рефлексивно.
2. Транзитивно.
3. Симметрично.

Бинарное отношение R, заданное на множестве А, называется отношением порядка, если оно

1. Антисимметрично.
2. Транзитивно.

Бинарное отношение R, заданное на множестве А, называется отношением строгого порядка, если оно

1. Антисимметрично.
2. Тразитивно.
3. Антирефлексивно

Бинарное отношение R, заданное на множестве А, называется отношением не строгого порядка, если оно

1. Антисимметрично.
2. Транзитивно.
3. Рефлексивно.

Бинарное отношение R, заданное на множестве А, называется отношением линейного порядка, если оно

1. Антисимметрично.
2. Транзитивно.
3. Связанно.

Бинарное отношение R, заданное на множестве А, называется отношением частичного порядка, если оно не связанное.

Примеры решения задач:

1. Дано множество V={1,2,…,12}, и два его подмножества А={1,4,6,8,9},B={2,3,9,10}

Найти: A∪B,A∩B,,  ,A\B,B\A,A B,BA,A2

A∪B={1,2,3,4,6,8,9,10},

 A∩B={9},

={2,3,5,7,10,11,12},

 ={1,4,5,6,7,8,11,12},

A \B={1,4,6,8},

B \A={2,3,10}, AB={(1,2),(1,3),(1,9),(1,10),(4,1),(4,3),(4,9),(4,10),(6,2),(6,3),(6,9),(6,10), (8,2),(8,3),(8,9), (8,10) (9,2),(9,3),(9,9), (9,10)},

BA={(2,1),(2,4),(2,6),(2,8),(3,1),(3,4),(9,1),(9,4),(9,6),(9,8),(9,9),(10,1),(10,4),(10,6), (10,8),(10,9)}

A2={(1,1),(1,4),(1,6),(1,8),(1,9),(4,1),(4,4),(4,6),(4,8),(4,9),(6,1),(6,4),(6,6),(6,8),(6,9), (8,1),(8,4),(8,6),(8,8),(8,9),(9,1).(9,4).(9,6),(9,8),(9,9)

2. Верно ли равенство? Проверить с помощью диаграмм Эйлера-Венна.

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

                             (ответ – да)

3. Составить тождество, соответствующее диаграмме Эйлера:

(

4. Определить является ли данное отношение эквивалентностью, или порядком, и, если да, то каким:

 R={(x,y)/x,y∈R,x2=y2}

1. Рефлексивность:∀x∈R, x2= x2, пусть х=2,4=4, выполняется
2. Симметричность: ∀x
3. Транзитивность: ∀x, y∈R, x2=y2, y2=z2⇒ x2= z2,выполняется
4. Антисимметричность: ∀x, y∈R, x2=y2, y2= x2⇒ x=y не выполняется, например, x=2, y=-2, а 4=4.

Таким образом, данное отношение является отношением эквивалентности, но не является отношением порядка.

2.Задания для обучающихся

2.1 Закончите предложения:

а) Множество- это любая определенная __________________          ______________.

б) Объекты, из которых состоит множество, называются его __________________ или ____________________.

в)  Если а элемент множества А, то пишут ________________________

г) Если А и В состоят из одних и тех же элементов, то говорят, что они _________________, и пишут _________________.

д) Подмножеством множества А называется такое множество В, каждый элемент которого ___________________   ________________.

2.2 Вставьте пропущенное слово:

а) ___________________  множества А называется такое множество В, каждый элемент которого принадлежит множеству А

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

в) ___________________ множеств А и В называется множество, содержащее те элементы множества А и множества В, которые входят одновременно в оба множества,

г) ___________________ множеств А и В называется множество, состоящее из тех элементов,  которые лежат в А, но не лежат в В.

д) ___________________ множества А называется множество , состоящее из всех элементов, которые не принадлежат А

2.3 Поставьте в соответствие каждой диаграмме Эйлера название операции над множествами:

1             2                          

         3                                                                           4                        

а) разность;  б) пересечение;  в) объединение;  г) дополнение

2.4 Закончите запись:

а) Пусть А и В множества, а∈А, b∈B, запишем их в определенные пары и обозначим (a,b), такая пара элементов называется ____________________.

б) Множество всех упорядоченных пар множеств A и B называется ____________.

в) Любое подмножество прямого произведения А×В называется _______________.

г) Если А=В, то прямое произведение  называется _________________.

2.5 Найдите:

Дано множество V={1,2,…,13}, и два его подмножества А={2,3,5,6,8,10},B={1,3,4,6,10,12}

Найти:  

__________________________________________________________________

__________________________________________________________________

2.6 Закрасьте

ту область на диаграмме Эйлера, которая соответствует выражению:

а)                                                                 б)

2.7 Составьте выражение, соответствующее диаграмме Эйлера:

а)                                                                                      б)

а)____________________                                     б)____________________

2. 8 Вставьте пропущенные слова:

а) Бинарное отношение р, заданное на множестве А, называется ________________, если ∀a∈A,(a,a)∉p

б) Бинарное отношение р, заданное на множестве А, называется ________________, если для любых элементов a,b∈A,(a,b)∧(b,a)∈p⇒a=b;(a,b)∈p∧a≠b ⇒(a,b)∉p

в) Бинарное отношение р, заданное на множестве А, называется _______________, если для любых элементов a, b, c∈Aвыполняется (a,b)∈p∧(b,c)∈p

г) Бинарное отношение р, заданное на множестве А, называется _______________, если для любых элементов a, b ∈ Aиз того, что (a,b)∈p⇒ (b,a)∈p

д) Бинарное отношение р, заданное на множестве А, называется ________________, если для любых элементов a,b∈A,a=b∨(a,b)∈p∨(b,a)∈p

е) Бинарное отношение р, заданное на множестве А, называется _______________, если элемент этого множества находится в данном отношении сам с собой.

2.9 Выберите из перечисленных свойств бинарных отношений те, которые необходимы (возможны неоднократные повторения)

(Рефлексивно, антирефлексивно, симметрично, антисимметрично, транзитивно, связано, не связанное.)

а) Бинарное отношение R, заданное на множестве А, называется отношением эквивалентности, если оно _________________, _______________, _____________.

б) Бинарное отношение R, заданное на множестве А, называется отношением порядка, если оно ________________, __________________

в) Бинарное отношение R, заданное на множестве А, называется отношением строгого порядка, если оно ___________________, ________________, ___________________.

г) Бинарное отношение R, заданное на множестве А, называется отношением не строгого порядка, если оно ____________________, ___________________, ___________________.

д) Бинарное отношение R, заданное на множестве А, называется отношением линейного порядка, если оно __________________, __________________, ____________________.

е) Бинарное отношение R, заданное на множестве А, называется отношением частичного порядка, если оно ______________________.

2.10 Верны ли следующие утверждения:

а) Множество- это любая определенная совокупность объектов. _______

б) Объекты, из которых состоит множество, называются буквами. ________

в)  Подмножеством множества А называется такое множество В, каждый элемент которого не принадлежит множеству А. ________

г) Объединением множеств А и В называется множество, содержащее все элементы множества А и множества В, которые входят одновременно в оба множества. ________

              д) Любое подмножество прямого произведения А×В называется бинарным отношением  р между элементами этих множеств. ________

              е) Бинарное отношение р, заданное на множестве А, называется рефлексивным, если элемент этого множества находится в данном отношении сам с собой ________

2.11 Определить 

является ли данное отношение эквивалентностью, или порядком, и, если да, то каким:

а) R={(x,y)/x,y∈R,x≥2y}

________________________________________________________________________

б) R={(x,y)/x,y∈R,x3=y3}

_________________________________________________________________________

2.12  Выберите ответ на вопрос из предложенных вариантов ответа:

а) Множество элементов, принадлежащих множеству А или множеству В, называется

1) дополнение 2) пересечение 3) разность 4) объединение.

б) Операции над множествами можно проиллюстрировать с помощью:

1) таблицы 2) графика 3) диаграммы Эйлера 4) формулы

в) Каким свойством бинарных отношений из перечисленных не обладает эквивалентность?

1) антисимметричность 2) симметричность 3) рефлексивность  4) транзитивность

г) Симметричность это свойство:

1) множеств 2) бинарных отношений 3) диаграммы Эйлера 4) отношения порядка

Раздел 3 Логика предикатов

Понятие предиката

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

Например, в рассуждении «Всякий ромб – параллелограмм; ABCD – ромб; следовательно, ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

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

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

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

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

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х).

Так, предикат P(x) – «х – простое число» определён на множестве N, а множество  для него есть множество всех простых чисел.

Определение 2. Предикат Р(х), определённый на множестве M, называется тождественно истинным (тождественно ложным), если .

Определение 3. Двухместным предикатом P(x,у) называется функция двух переменных х и у, определённая на множестве М=М1×М2 и принимающая значения из множества {1,0}.

В качестве примеров двухместных предикатов можно назвать предикаты: Q(x,у) – «х = у» предикат равенства, определённый на множестве R2=R×R; F(x,у) – «х || у» прямая х параллельна прямой у, опредёленный на множестве прямых, лежащих на данной плоскости.

Аналогично определяется n - местный предикат.

Говорят, что предикат Р(х) является следствием предиката Q(х) , если; и предикаты Р(х) и Q (х) равносильны , если .

Приведём примеры к изложенному материалу.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, если M = R для одноместных предикатов и M = R×R для двухместных предикатов:

1. х + 5 = 1
2. при х = 2 выполняется равенство х2 – 1 = 0
3. х2 – 2х + 1 = 0
4. существует такое число х, что х3 – 2х + 1 = 0
5. х + 2 < Зх – 4
6. однозначное неотрицательное число х кратно 3
7. (х + 2) – (3х – 4)
8. х2 + у2 > 0

Решение.

1) Предложение является одноместным предикатом Р(х), IP = {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р(х), IP = {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение является одноместным предикатом Р(х), IP = (3; +∞);
6) предложение является одноместным предикатом Р(х), IP = {0; 3; 6; 9};
7) предложение не является предикатом;
8) предложение является двухместным предикатом Q(х,y), IQ = R×R \ {(0,0)}.

Кванторные операции над предикатами

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

Определение 4. Пусть Р(х) – предикат, определенный на множестве М. Под выражением  понимают высказывание, истинное, когда Р(х) тождественно истинный на множестве М предикат, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «Для всякого х Р(х) истинно». Символ  называют квантором всеобщности.

Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании  переменную х называют связанной квантором .

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

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

Пример 5. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания:  – «Все натуральные числа кратны 5»;  – «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание  истинно только в том единственном случае, когда Р(х) – тождественно истинный предикат, а высказывание  ложно только в том единственном случае, когда Р(х) – тождественно ложный предикат.

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

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

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

Пример 6. Пусть предикат Q(х,у): «ху» определен множестве N × N. Показать, что высказывания  и  имеют различные логические значения.

Решение. Так как высказывание  означает, что для всякого натурального числа у существует натуральное число х такое, что у является делителем х, то это высказывание истинно. Высказывание  означает, что есть натуральное число х, которое делится на любое натуральное число у. Это высказывание, очевидно, ложно.

Далее рассмотрим предикат Р(x), определенный на конечном множестве М = {а1, а2, …, аn}.

Если предикат Р(x) является тождественно истинным, то истинными будут высказыванияР(а1), Р(а2),..., Р(аn). При этом истинными будут высказывание  и конъюнкцияР(а1)&Р(а2)&...&Р(аn).

Если же хотя бы для одного элемента  Р(аk) окажется ложным, то ложными будут высказывание  и конъюнкция Р(а1)&Р(а2)&...&Р(аn). Следовательно, справедлива равносильность

.

Нетрудно показать, что справедлива и равносильность

.

Это означает, что кванторные операции обобщают операции конъюнкции и дизъюнкции на случай бесконечных областей.

3. Задания для обучающихся

3.1 Вставить пропущенные слова:

а) _______________– это то, о чем что-то утверждается в высказывании, а ________________– это то, что утверждается о субъекте.

б) Логика предикатов – это _____________________________________ за счет использования предикатов в роли логических функций.

в) Одноместным предикатом Р(х) называется _____________________________, в которой аргумент x пробегает значения из некоторого множества M, а функция при этом принимает одно из двух значений:_____________или____________.

г) Множество , на котором предикат принимает только _______________________________________________,называется областью истинности   предиката Р(х).

д) Множество M, на котором ______________________________________, называется областью определения предиката.

е) Предикат Р(х), определённый на множестве M, называется тождественно истинным (тождественно ложным), если ____________________________________________________________.

3.2 Поставить в соответствие:

3.3 Привести примеры 1,2,3 местных предикатов

1 местный ____________________________________________________________

2 местный ____________________________________________________________

3 местный ____________________________________________________________

3.4 Какие из клауз истины, а какие ложны? Ответ обосновать

а) ___________________________________________________________

___________________________________________________________

б) ___________________________________________________________

______________________________________________________________________

3.5 Найти область определения и множество истинности предикатов:

а) 2х - 15 = 11 __________________________________________________________

б) х2 – 4х + 4 = 0 ________________________________________________________

г) 4х + 5 < 2х – 1 ________________________________________________________

3.6 Закончить предложение:

А) Символ  называют _________________________________________________

Б) Символназывают __________________________________________________

В) Высказывание  истинно только в том единственном случае, когда Р(х) –_____________________________________________________________________________

Г) Высказывание  ложно только в том единственном случае, когда Р(х) – _____________________________________________________________________________.

Перечень рекомендуемой учебной литературы, методических пособий и Интернет-ресурсов

1. Лупанов О. Б. Курс лекций по дискретной математике. - М., 2020.
2. Новиков Ф.А. Дискретная математика для программистов - 2019 г.
3. Яблонский С.В. Введение в дискретную математику — М. Наука, 2019.
4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. — М.: Наука, 2020.
5. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: учеб. пособ.- М.: Форум: ИНФРА-М, 2020.
6. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика -М., 2020 г.
7. Мендельсон Э. Введение в математическую логику. — М.: Наука, 2019.
8. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.: Издательство МАИ, 2020
9. Спирина М.С. Дискретная математика: учеб. – М.: Академия, 2020.

Электронные ресурсы:

1. http://otherreferats.allbest.ru/
2. http://st.educom.ru/eduoffices/gateways/get_file.
3. http://umu.kemsu.ru/Content/userfiles/files/Математический