рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Пустое отношение.

Пустое отношение. - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен Операции На Отношениях: Пересечение ...

Операции на отношениях:

Пересечение

Объединение

Произведение

Дополнение:

Обратное отношение к R:

Свойства отношений:

Рефлексивность: xRx, для всех x

Симметричность: xRy => yRx

Транзитивность: xRy, yRz => xRz

Антисимметричность: xRy, yRx => x=y

Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности разбивает на семейство подмножеств (классов разбиения). Каждый его элемент принадлежит некоторому из этих подмножеств (именно – R(a)). Совокупность всех классов разбиения обозначается A/R и называется фактор-множеством множества A относительно эквивалентности R.

[a], обозначает класс из A/R к которому принадлежит a. Сам элемент a называют представителем этого класса.

Квазипорядком называют отношение, которое рефлексивно и транзитивно.

Частичным порядком (или просто порядком) называется отношение, которое рефлексивно, антисимметрично и транзитивно.

Порядок обозначается символом .

так же является порядком и обозначается.

Порядок называется линейным, если для любых либо a либо b .

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

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

Каждое подмножество A’ множества частично упорядоченного множества обладает индуцированным порядком. Если порядок A’ линеен, то множество A’ называется цепью вA.

Максимальный, минимальный, наибольший, наименьший элемент.

Нижняя грань (, точная нижняя грань .

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

– Конец работы –

Эта тема принадлежит разделу:

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

Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).   Характеристическая функция пуст

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

Отношения.
n-местным отношением R на множествах называется подмножество прямого произведения . Если множества совпадают, то говорят что задаёт n-арные отношения. При n = 2 о

Алгебра логики
  Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданн

Формулы алгебры логики.
Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы. Формулой явл

Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний. Пример. x1=1, x2=1, x3=0. Определить значение формулы

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

Основные тождества (равносильные формулы) алгебры логики.
  xÙy=yÙx; xÚy=yÚx – коммутативность xÙ(yÙz)= (xÙy)Ùz; xÚ(yÚz)= (xÚy) Úz; - ассоциат

Двойственные функции
Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .

Двойственные функции
Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .

Полные системы функций (связок).
Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему. Систе

Дизъюнктивные и конъюнктивные нормальные формы.
Элементарной конъюнкцией называется конъюнкция переменных высказываний и (или) их отрицаний. Например: Элементарной дизъюнкциейназываетс

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

Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв

Совершенные нормальные формы.
Совершенная дизъюнктивная нормальная форма. Элементарная конъюнкция называется правильной,если в неё каждая переменная входит не более одного раза,

Построения СДНФ и СКНФ.
  Построение СДНФ: 1. Преобразование исходной формулы в ДНФ (см выше): Шаг 1. Преобразовать исходную формулу к равносильному ей виду

Преобразование ДНФ в СДНФ.
Шаг 3. Если в ДНФ есть несколько одинаковых элементарных конъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле , т.к. xVx=x.

Преобразование КНФ в СКНФ.
Шаг 3. Если в КНФ есть несколько одинаковых элементарных дизъюнкций , то оставляем только одну - это преобразование приводит к равносильной формуле ,т.к. x&x=x.

Построение совершенных нормальных форм с помощью таблиц истинности
Для построения СДНФ или СКНФ, исходя из теоремы о разложении функции алгебры логики от n переменных по k переменным (k=n), можно воспользоваться таблицами истинности. Для построения

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

Разложение функций алгебры логики по к переменным.
  Теорема. Всякую логическую функцию f(x)=f(x1,x2,x3,…,xn) можно представить в виде  

Тавтологии и противоречия. Проблема разрешимости в алгебре логики. Логические следствия.
  Формула алгебры логики называется тождественно истиной, общезначимой или тавтологией,если она принимает значение 1 п

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

Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв

Теорема о логическом следствии
Формула алгебры логики f является логическим следствием формулы алгебры логики g,тогда и только тогда, если g f. Доказательство.

Основные схемы доказательств
Схема 1. «Если x то y» Доказательство теорем типа “если x, то y”. Схема доказательства основана на следующем логическом следствии: .

Минимизация функций алгебры логики. Каноническая постановка задачи минимизации. Этапы минимизации. Методы минимизации.
Минимизация функций алгебры логики (ФАЛ) – это процедура нахождения наиболее простого представления ФАЛ в виде суперпозиции функций, составляющих фун

Методы минимизации
К настоящему времени широкое применение получили: 1. Расчетный метод (метод непосредственных преобразований). 2. Расчетно-табличный метод (метод Квайна-МакКласки). 3. Мет

Этапы минимизации
В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов: 1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами к

Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы.
        Разрешимость формальной с-мы: Теория называется разрешимой, если в ней понятие теоремы эффективно

Исчисление предикатов
Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП). Алфавит ИППП состо

Значение формулы логики предикатов.
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики преди

Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj&

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги