МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФГБОУ ВО
«Воронежский государственный университет инженерных технологий»
КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНоЛОГИЙ МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ
Методические указания и задания
К контрольной работе № 1
по дисциплине “Теоретическая информатика”
направления 09.03.03
Воронеж 2016
Контрольная работа состоит из трех заданий. К кажому заданию приведены необходимые для их выполнения теоретические сведения и примеры выполнения заданий. Ход выполнения и результаты решения заданий студентом оформляются средствами MS WORD. Номер варианта каждого задания выбирается по последней цифре шифра логина студента. Варианты заданий приведены на стр. 23.
Теоретический материал к заданию № 1.
Основные понятия теории множеств
Для множества не существует строгого определения, поэтому введем описательные понятия множества и его элементов.
Множеством называется совокупность некоторых предметов, объединенных общим признаком. Элементы множества — это те предметы, из которых состоит множество.
Пусть имеется множество А, элементом которого является предмет а, это записывается как А={а}. Например, В={1,2, 3}.
Если какой-то элемент а принадлежит множеству А, то это обозначается аIА, а если b не принадлежит А, то — bIА. Например, пусть А — множество четных натуральных чисел, тогда 6IА, а 3IА.
Пусть имеется два множества А и В, причем все элементы множества А принадлежат множеству В, т.е. если хIА, то хIB. В этом случае говорят, что множество А включено в множество В. Обозначается: АIВ (I — символ нестрогого включения, т.е. возможно совпадение множеств). Множество А совпадает со множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А. Это можно записать в виде
(АIВ и ВIА) (А = В).
Множество А строго включено в множество В, если все элементы множества А принадлежат множеству В, но не все элементы множества В принадлежат множеству А.
Пример: А = { 1, 2, 3 }, В = { 0, 1, 2, 3 }, АIВ.
Возможны два способа задания множества.
1. Перечислением элементов, т.е. в фигурных скобках дается полное перечисление элементов данного множества. Например : N= {1,2,…,n,…} — множество натуральных чисел.
2. С помощью указания характерного свойства (указание свойства, которым обладают только элементы данного множества). Символически это записывается в виде A={x | P(x)} и читается A есть множество всех элементов х, обладающих свойством P(x).
При задании множеств вторым способом возможны различные противоречия и парадоксы. Рассмотрим примеры таких парадоксов.
1) Парадокс парикмахера: в городе жил парикмахер, который брил всех, кто не брился сам. Кто же брил парикмахера?
2) Пусть имеем натуральное число 11218321 — одиннадцать миллионов двести восемнадцать тысяч триста двадцать один. Это число можно описать с помощью восьми слов. Пусть А — множество натуральных чисел, которые нельзя определить с помощью фразы, имеющей меньше 20 русских слов. Обозначим аmin — наименьшее число из множества А, причем аminIA. Число аmin можно определить следующим образом: наименьшее натуральное число, которое нельзя определить с помощью фразы, имеющей менее двадцати слов. В этой фразе 14 слов. Значит, аmin можно определить с помощью фразы, содержащей менее 20 слов.
Тогда получается, что аminI А.
К настоящему времени накопилось много подобных примеров, когда определение множества оказывалось внутренне противоречиво. Выяснение условий, при которых это может иметь место потребовало специальных исследований, составивших предмет математической логики и выходящих за рамки собственно теории множеств. Поэтому в данном пособии мы не станем касаться спорных случаев и будем рассматривать лишь множества, которые определяются точно и без противоречий.
В теории множеств имеется специальное множество, называемое пустым множеством ( ?), которое не содержит ни одного элемента. Пустое множество по определению содержится в любом множестве А (?IА). Это понятие вводится из следующих соображений. Задавая множество вторым способом не всегда заранее можно быть уверенным, существуют ли элементы, ему принадлежащие. Например, можно говорить о множестве четырехугольников на плоскости, у которых все углы прямые, а диагонали не равны. Только знания основ геометрии позволяют убедиться, что таких четырехугольников не существует и, следовательно, это множество пусто.
Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому надо детально разобраться в методах доказательства этих фактов.
1. Доказательство включения АIВ. Для этого нужно доказать, что любой элемент x, принадлежащий множеству А одновременно является элементом множества В, т.е.
(x I А) = (x I В).
2. Доказательство равенства А = В.
Оно сводится к доказательству двух включений АIВ и ВIА.
Пример 1. Докажем следующую теорему. Для любых множеств А, В и С выполняется закон транзитивности нестрогого включения, т.е. если АIВ и ВIС, то из этого следует, что АIС.
Доказательство. Пусть x — любой элемент множества А, (xIА), тогда в силу условия АIВ, по определению нестрогого включения, элемент х принадлежит множеству В (хIB). После доказательства этого факта, аналогично, используя условие ВIС можно доказать, что х принадлежит С (хIС).
В качестве исходного допущения мы приняли, что x – любой элемент из А. Из этого допущения при выполнении условий а) и б) получено следствие хIС. По определению нестрогого включения это означает АIС, что и требовалось доказать.
Пример 2. Пусть А={1,6}, В ={х | х2-7х+6=0}. Последнее читается как, В является множеством элементов х, для которых выполняется условие х2 — 7х + 6 = 0. Включение АIВ доказывается подстановкой элементов множества А в это условие. Для доказательства обратного включения ВIА нужно найти все корни уравнения и убедиться, что они равны 1 и 6, т.е. принадлежат А. Выполнение обоих нестрогих включений означает равенство множеств А и В.
Операции над множествами.
Определим следующие операции.
1. Объединение. Пусть А и В — произвольные множества. Их объединением называется множество С = АEВ, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В.
2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов одновременно принадлежащих А и В. Обозначается так: C=ACB.
3. Разность. Разность множеств А и В — это множество С (С=А\В), состоящее из элементов множества А, не принадлежащих множеству В. Если ВIА, то разность С = А\В называется дополнением В до А. Иногда, говоря о некотором наборе множеств подразумевают, что все они включены в некоторое множество S, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до S обозначается С(А) или .
4. Симметричная разность. По определению симметричная разность двух множеств А и В — это множество
С = АDВ = (А\В)E(В\А).
Основные свойства операций.
1. Операции пересечения и объединения коммутативны (перестановочны): АCВ = ВCА; АEВ = ВEА.
2. Операции пересечения и объединения ассоциативны.
(АCВ) CС = АC (ВCС) = АCВCС
(АEB) EС = АE (ВEС) = АEВEС.
Свойствами коммутативности и ассоциативности обладают многие операции. Чтобы не создалось впечатления, что коммутативность и ассоциативность являются общими свойствами всех операций, приведем пример неассоциативной операции — возведение в степень. Имеем: (23)2 = 82 = 64; = 28 = 512.
Пример некоммутативной операции — операция умножения матриц (АВ¹ВА).
3. Операции объединения и пересечения взаимно дистрибутивны.
Для вещественных чисел закон дистрибутивности читается так: а(в+с) = ав + ас. Для множеств закон дистрибутивности имеет вид:
а) (АEВ)CС = (АCС) E (ВCС)
б) (АCB) EС = (АEС) C (ВEС).
Докажем равенство а).
Предположим, что xI (АEВ) CС, тогда xIС и xIА или xIВ. Рассмотрим первый случай xIС и xIА. Тогда хIАCС, а значит, по определению объединения, хI(АCС)E(ВCС).
Во втором случае, т.е. при xIС и xIВ получаем, что xI (ВCС)E(АCС). Таким образом, мы доказали включение
[(АEВ) CС]I[(АCС)E(ВCС)].
Докажем обратное включение. Пусть хI(АCС)E(ВCС), тогда хIАCС или хIВCС. В первом случае хIА и хIС. Во втором случае хIВ и xIС. В обоих случаях получаем, что хIС и хIА или хIВ. Следовательно, хI(АEВ) CС. Тем самым доказано включение (АCС)E(ВCС)I(АEВ) CС.
Таким образом, (АEВ) CС=(АCС)E(ВCС), что и требовалось доказать.
Пусть А1, А2, . . . — некоторые множества и пусть все они включены в S (А1, А2, . . . I S). Тогда выполняются следующие соотношения.
4. 
— дополнение объединения множеств равно пересечению их дополнений.
5. 
— дополнение пересечения множеств равно объединению их дополнений.
Докажем свойство 4. Пусть хI 
, тогда хI 
значит, x не принадлежит ни одному из множеств Ak (k, хIАk), следовательно, по определению дополнения хIS\Аk для любого k. Отсюда вытекает, что хI 
.
Обратно, пусть хI тогда этот элемент принадлежит каждому из множеств S \ Ak (k, хIS\ Ak). Следовательно, хIAk для любого k, а, значит, хI и поэтому хI , что и требовалось доказать.
Пример решения задания № 1.
Доказать соотношение AUB=AU(B\A).
Чтобы доказать это соотношение, нужно показать, что каждый элемент первого множества принадлежит второму и наоборот, то есть эти множества совпадают.
Пусть x?AUB, то есть x?A или x?B. Если x?A, то x?AU(B\A). Если x?A, но x?B, то x?B\A, следовательно, x?AU(B\A).
Пусть x?AU(B\A), то есть x?A или x?B\А. Если x?A, то x?AUB. Если x?В, но x?A(x?B\А), то x?AUB.
Таким образом, соотношение доказано.
Теоретический материал к заданию № 2.
Векторы, прямые произведения, произведения векторов.
Вектор , где — компоненты (координаты) вектора. Число компонент называется длиной (размерностью) вектора.
Два вектора и равны, если они имеют одинаковую длину и соответствующие координаты их равны, т.е. , если: 1). ; 2). .
Множество всех возможных (различающихся) векторов длины таких, что , называют прямым произведением множеств Обозначение прямого произведения: . Прямое произведение одинаковых множеств , т.е. когда , обозначают .
Мощность прямого произведения множеств равна произведению мощностей этих множеств, т.е. .
Способы задания прямого произведения множеств — аналогичны способам задания множеств с той разницей, что требуется задание каждого множества
Операции над множествами векторов (данного прямого произведения) – объединение, пересечение, разность, дополнение – аналогичны соответствующим операциям над множествами элементов.
Операции над вектором длины : .
Проекцией вектора на ю ось называется его я компонента: .
Проекцией вектора на оси с номерами называется вектор длины :
Операции над множеством векторов длины :
.
Проекцией множества векторов на ю ось называется множество проекций всех векторов из на ю ось:
.
Проекцией множества векторов на оси с номерами называется множество проекций всех векторов на оси с номерами :
.
Операции над упорядоченным множеством векторов длины : .
Проекцией упорядоченного множества векторов на ю ось называется упорядоченное множество проекций векторов на эту ось: .
Проекцией упорядоченного множества векторов на оси с номерами называется упорядоченное множество проекций всех векторов на оси с номерами :
Над векторами одинаковой длины возможно выполнение различных операций сравнения.
Правило сравнения векторов по предпочтению. Пусть — множество векторов длины , компонентами которых являются числа. Вектор не менее предпочтителен, чем вектор (обозначение ), если компоненты вектора не меньше соотвествующих компонент вектора
.
Примеры решений задания № 2.
1). Пусть . Определить проекции :
1. на первую ось;
2. на вторую ось;
3. на вторую и третью ось.
Решение.
Проекции множества векторов :
.
2). Пусть упорядоченное множество векторов. Определить проекции :
1. на первую ось;
2. на вторую ось;
3. на вторую и третью ось.
Решение.
Проекции упорядоченного множества векторов : .
3). Пусть Найти .
Решение.
