Реферат Курсовая Конспект
Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен - раздел Математика, 1. Основные Понятия Теории Множеств (Множество, Пустое Множество, Уни...
|
1. Основные понятия теории множеств (множество, пустое множество, универсальное множество, подмножество, булеан). Мощность множества, равномощные множества. Конечные, бесконечные и счётные множества. Способы задания множеств.
Множество - это совокупность определённых различаемых объектов, причём таких, что для каждого можно установить, принадлежит этот объект данному множеству или нет.
Множества обычно обозначаются заглавными латинскими буквами, а элементы множества - строчными. Элементами множеств могут быть любые объекты, например, числа, символы, слова, объекты реального мира. В частности, элементами множества могут быть другие множества.
Например:
A = { a, b, c } - множество A состоящее из 3 элементов
N = { 1, 2, 3, … } - множество N целых чисел
Элементы множества являются уникальными, то есть, один и тот же элемент не может включаться в множество несколько раз (в отличие от векторов и мультимножеств). Считается, что при добавлении в множество элемента, который в нем уже присутствует, множество не меняется.
Порядок записи элементов множества не является существенным (в отличие от записи элементов векторов, где порядок важен).
Таким образом, множества считаются равными, если они состоят из одних и тех же элементов.
Если некоторый объект является элементом множества , то этот факт записывается следующим образом: и читается «x принадлежит А». Аналогично, если элемент не является элементом множества , используется запись («y не принадлежит А»).
Пустое множество – это множество, не содержащее элементов. Пустое множество может быть обозначено с использованием фигурных скобок: = { }. Однако, множество B = {} не является пустым: это множество, содержащее один элемент, который является пустым множеством.
Универсальное множество Е – множество всех объектов, рассматриваемых в данной задаче.
Конечные и бесконечные множества.Если количество элементов множества конечно (то есть существует натуральное число, равное количеству элементов множества), то такое множество называется конечным.В противном случае множество называется бесконечным.
Мощность множества или кардинальное число |A| (иногда card(A)). Мощность множества является обобщением понятия количества элементов на бесконечные множества. Для конечных множеств мощность равна количеству элементов множества.
Мощность пустого множества по определению равна нулю: .
Равномощные множества – это множества, между элементами которых можно установить взаимно однозначное соответствие.
Счётное множество – множество, равномощное множеству натуральных чисел.
Множество А называют подмножеством множества B (обозначается либо ) если все элементы, которые принадлежат множеству A, так же принадлежат и множеству B.
В этом случае B называют надмножеством A
Пустое множество является подмножеством любого множества.
Любое множество является подмножеством самого себя:
Любое множество является подмножеством универсального множества:
Два множества A и B равны тогда и только тогда, когда A является подмножеством B и B является подмножеством A.
Если множество A является подмножеством множества B, но A и B не равны, то в этом случае говорят что А является собственным подмножеством B (обозначается ).
Некоторые специальные множества: (Натуральные числа), (целые числа), (вещественные числа), (рациональные числа),
Способы задания множеств
Списком: Элементы множества записываются через запятую и обрамляются фигурными скобками.
Иногда, список может содержать многоточие: , однако такая запись не является строгой и может быть использована только там, где смысл её ясен. Более строго следовало бы записать .
Так же, для записи элементов с индексами иногда используется упрощенная запись
Описанием свойств элементов (или характеристическим предикатом): В фигурных скобках записывается обозначение элемента множества, от которого вертикально чертой отделяется логическая функция (предикат), определяющий принадлежность элементов множеству.
Такая запись читается «A – это множество таких x, что для них верно H(x)»
Например, множество четных чисел может быть задано в виде: (читается «A – множество таких натуральных чисел, которые делятся на 2»)
При задании подмножеств может использоваться сокращенная запись:
(«А – множество таких x, принадлежащих B, что x делится на 2»)
Порождающей процедурой: В фигурных скобках записывается обозначение элемента множества, от которого вертикально чертой отделяется описание порождающей процедуры, генерирующей элементы множества.
Например, множество четных чисел может быть задано в виде
Множество степеней двойки:
Словестным описанием. Описание должно быть точным и недвусмысленным, объективным.
Например: А = множество чётных чисел. B = множество белых ворон.
Множество хорошей музыки – не катит, т.к. воспринимается каждым по-своему.
Графическое. (Диаграммы Эйлера – Венна). Круг Эйлера - ограничивает множество. Рамка - универсальное множество.
Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность, декартово произведение). Законы алгебры множеств. Способы доказательства законов алгебры множеств. Характеристические функции.
Операции над множествами (алгебра множеств)
Основные операции: объединение , пересечение , разность (), симметрическая разность , дополнение.
Объединение множеств – это множество, состоящее из элементов входящих в любое из множеств A или B:
Например, для множеств и результатом объединения будет:
Операция объединения может быть использована для объединения нескольких множеств:
Пересечение множеств – множество, содержащее элементы, входящие в оба множества одновременно:
Для множеств, приведенных выше:
Разность множеств – это подмножество элементов множества A, не входящих в B:
Для множеств, приведенных выше:
Разности AB и BA в общем случае не совпадают:
Симметрическая разность – состоит из элементов входящих либо в A либо в B, но не в оба множества сразу.
Для множеств, приведенных выше:
Дополнение до универсального множества - подмножество универсального множества, элементы которого не содержатся в A.
Для того что бы выписать элементы дополнения не достаточно знать только элементы множества A, необходимо так же задать элементы универсального множества E.
Графическое отображение операций на множествах: а, б) – исходные множества А и В, в) объединение г) пересечение д) разность AB, е) симметрическая разность, ж) дополнение A
Декартово (прямое) произведение множеств
Называется множество всех векторов (a,b), таких что и :
Мощность прямого произведения n множеств равна произведению мощностей соответствующих множеств.
Доказательство…. (Метод мат. индукции)
Способы доказательства тождеств на множествах
С использованием характеристических функций
Докажем что
1) Характеристическая функции левой части:
2) Характеристическая функции правой части:
3) , следовательно
Кортежи. Декартово произведение множеств. Отношения, свойства отношений (рефлексивность, симметричность, транзитивность, антисимметричность). Операции на отношениях. Отношения эквивалентности и порядка.
Кортеж (вектор) – упорядоченная последовательность элементов. Элементы вектора – координаты или компоненты. Число компонент – размерность вектора.
Обозначение – в круглых скобках (иногда – в треугольных).
Проекция вектора на ось i – его i-й компонент.
Декартово (прямое) произведение множеств
Называется множество всех векторов (a,b), таких что и :
Мощность прямого произведения n множеств равна произведению мощностей соответствующих множеств.
Доказательство…. (Метод мат. индукции)
Понятие высказывания, основные операции с высказываниями, алгебра логики. Формулы алгебры логики. Значения формул и таблицы истинности. Классификация формул.
Высказывание — термин математической логики, обозначающий формализованную структурированную запись мысли с помощью буквенных символов и логических связок, рассматриваемую с точки зрения истинностных значений. Это утверждение, для которого оценивается логическое значение: ложь или истина. Логическое высказывание принято обозначать заглавными латинскими буквами. Является основным объектом логики высказываний.
Пример.
Для формулы построить таблицу истинности.
В нашем примере 22=4.
Равносильность формул. Основные тождества алгебры логики. Двойственные функции.
Правило отрицания
Для получения отрицания некоторого выражения достаточно заменить в нем знаки дизъюнкции знаками конъюнкции, знаки конъюнкции знаками дизъюнкции, а все аргументы – их отрицаниями. Если в выражении имеются константы их тоже надо заменить противоположными значениями.
Правило свертки
xÚØx Ùy=xÚy
xÙ(ØxÚy)=xÙy
Правило обобщенного склеивания (теорема П.С.Порецкого)
xyÚØyzÚxz=xyÚØyz
(xÚy)(ØyÚz)(xÚz)=(xÚy)(ØyÚz)
Преобразование импликации
x®y= ØxÚy;
Ø (x®y)= xÙØy
Принцип двойственности.
Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:
f0(f1,...,fm)* = f0*(f1*,...,fm*)
Полнота системы логических функций. Примеры полных систем. Классы логичиских функций и критерий Поста. Сигнатура алгебры логики.
Принцип двойственности.
Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:
f0(f1,...,fm)* = f0*(f1*,...,fm*)
Конъюнктивные и дизъюнктивные нормальные формы. Алгоритмы построения КНФ и ДНФ. Теоремы о тождественной ложности и тождественной истинности формул.
Совершенные КНФ и ДНФ. Способы построения совершенных нормальных форм. Разложение логических функций по переменным.
Алгоритм построения СКНФ.
Преобразование исходной формулы в КНФ.
Шаг 1.
Преобразовать исходную формулу к равносильному ей виду, в котором есть лишь операции конъюнкции, дизъюнкции и отрицания (перейти в сигнатуру алгебры логики), причём отрицания могут стоять лишь над элементарными переменными высказываниями.
Шаг 2.
Преобразовать полученную формулу к равносильному ей виду, в котором все дизъюнкции выполняются раньше, чем конъюнкции (применить дистрибутивный закон), т.е. построить КНФ для исходной формулы.
Построение совершенных нормальных форм, используя принцип двойственности.
Построение совершенной дизъюнктивной нормальной формы.
Рассмотрим вместо исходной функции её отрицание и построим для полученной формулы алгебры логики её совершенную конъюнктивную нормальную форму. Взяв затем отрицания от левой и правой частей полученного выражения и применив, если это необходимо. закон де Моргана, а так же возможно упростив полученное выражение, получим совершенную дизъюнктивную нормальную форму для исходной функции.
Проблема разрешимости в алгебре логики. Логическое следствие. Основные схемы доказательств.
Теорема о противоречивости множества формул алгебры логики
Множество формул алгебры логики противоречиво, если из него в качестве логического следствия можно вывести противоречие.
Для доказательства теоремы используется теорема 4 и определение операции импликации.
Теорема о тождественной истинности формулы алгебры логики
,если в качестве логического следствия из и можно вывести противоречие.
Исчисление высказываний как формальная система. Правила вывода. Язык и интерпретация исчисления высказываний. Общезначимость, выполнимость, следование. Полнота и непротиворечивость исчисления высказываний.
Исчисление высказываний:
Формальная система, в которой выводятся общезначимые формулы логики высказываний и только они.
Позволяет выводить все общезначимые формулы из аксиом, не рассматривая их интерпретации.
Интерпретация языка высказываний:
Правила вывода см. вопрос 11.
Связь между логикой и исчислением высказываний. Способы доказательства общезначимости формул логики высказываний и выводимости формул в исчислении высказываний. Метод резолюций в исчислении высказываний.
Доказательство общезначимости:
Семантические методы:
Связь между алгеброй логики и исчислением высказываний:
Формулы исчисления высказываний можно интерпретировать как формулы алгебры логики.
Теорема. Каждая формула, доказуемая в исчислении высказываний является тавтологией в алгебре логики.
Обратная теорема. Каждая тождественно истинная формула (тавтология) алгебры логики доказуема в исчислении высказываний.
Понятие предиката. Область определения и множество истинности предикатов. Интерпретация исчисления предикатов и значение формул логики предикатов. Общезначимость и выполнимость формул логики предикатов. Чистая и прикладная логика предикатов.
Предика́т (n-местный, или n-арный) — это функция с множеством значений (или «ложь» и «истина»), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный».
Предикат называют тождественно-истинным и пишут:
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно-ложным и пишут:
если на любом наборе аргументов он принимает значение 0.
Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.
Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д.
Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).
Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество или иначе: или так: Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности IP для него есть множество всех простых чисел.
Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является
Кванторы существования и всеобщности. Логические суждения с кванторами. Область действия кванторов, связанные и свободные переменные. Эквивалентные отношения в логике предикатов.
В предикатной логике, квантор существования (экзистенциальный квантификатор) — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.
Квантор всеобщности (обозначения: , ∀) — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».
Эквивалентные отношения в логике предикатов см. тетрадь.
Понятие алгоритма. Неформальное (интуитивное) определение алгоритма. Примеры алгоритмов. Основные свойства алгоритмов. Роль алгоритмов в информатике. Алгоритмические проблемы. Машина Тьюринга - описание и примеры. Рекурсивные функции.
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.
Алгоритм деления отрезка АВ пополам:
1) поставить ножку циркуля в точку А;
2) установить раствор циркуля равным длине отрезка АВ;
3) провести окружность;
4) поставить ножку циркуля в точку В;
5) провести окружность;
6) через точки пересечения окружностей провести прямую;
7) отметить точку пересечения этой прямой с отрезком АВ.
Основными свойствами алгоритма являются:
1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.
Понятие алгоритма — одно из основных в программировании и информатике. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синонимы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения. Программа же всегда связана с записью алгоритма на конкретном формальном языке.
Перечислим некоторые важные алгоритмические проблемы.
1. Проблема самоприменимости. Существует ли алгоритм, позволяющий по произвольному натуральному числу x отвечать на вопрос: "сходится ли jx(x)?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: "существует ли общерекурсивная функция g0 такая, что g0«1, если jx(x) сходится и g0«0, если jx(x) расходится?".
2. Проблема остановки [Роджерс,1972,с.43]. Существует ли алгоритм, позволяющий по произвольной паре натуральных чисел (x,y) отвечать на вопрос: "Сходится ли jx(y)?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: "существует ли общерекурсивная функция g от двух переменных такая, что g(x,y)«1, если jx(y) расходится и g(x,y)«0, если jx(y) расходится?".
3. Проблема общерекурсивности [Роджерс,1972,с.45]. Существует ли алгоритм, позволяющий по произвольному натуральному числу x отвечать на вопрос: "Является ли n-местная функция jx общерекурсивной?". Согласно тезису Чёрча-Клини эту проблему можно переформулировать в следующей эквивалентной форме: "Существует ли общерекурсивная функция t(x) такая, что t(x)«1, если jx - n-местная общерекурсивная функция и t(x)«0 в противном случае?".
Машина Тьюринга:
Пример машины Тьюринга
Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:
Набор правил | Набор правил |
q0*→q0*R | q4a→q4aR |
q01→q01R | q4=→q4=R |
q0×→q1×R | q41→q41R |
q11→q2aR | q4*→q51R |
q21→q21L | q5 →q2*L |
q2a→q2aL | q6a→q61R |
q2=→q2=L | q6×→q7×R |
q2×→q3×L | q7a→q7aR |
q31 → q4aR | q71→q2aR |
q3a→q3aL | q7=→q8=L |
q3*→q6*R | q8a→q81L |
q4×→q4×R | q8×→q9×N |
Умножим с помощью МТ 3 на 2 в единичной системе:
В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения на основе значений , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого , необходимо, чтобы для некоторых функция была определена нерекурсивно (например, для ).
Примеры
Пример рекурсивной функции, дающей n-ое число Фибоначчи:
Руководствуясь этой записью, мы можем вычислить для любого натурального n за конечное число шагов. Правда, по пути придется дополнительно вычислить значения .
– Конец работы –
Используемые теги: порядок, записи, элементов, множества, является, существенным, Отличие, записи, элементов, векторов, Где, порядок, важен0.145
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов