Отношения. - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен N-Местным Отношением R На Множествах Называется Подмножество Прямого Произ...
n-местным отношением R на множествах называется подмножество прямого произведения .
Если множества совпадают, то говорят что задаёт n-арные отношения.
При n = 2 отношение называется бинарным.
Далее будем рассматривать только бинарные отношения определенные на А.
Отношение может быть записано в виде R(a, b) или aRb.
Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Отношения.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).
Характеристическая функция пуст
Графическое доказательство
Для построения графического доказательства необходимо изобразить на диаграмме Эйлера-Венна все множества, входящие в тождество таким образом, что бы присутствовали их все возможные пересечения,
Пустое отношение.
Операции на отношениях:
Пересечение
Объединение
Произведение
Дополнение:
Обратное отношение к R:
Алгебра логики
Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданн
Формулы алгебры логики.
Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы.
Формулой явл
Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний.
Пример. x1=1, x2=1, x3=0. Определить значение формулы
Равносильные формулы
Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в
Двойственные функции
Функция 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 переменных. Рассмотрим отрицание этой функции и , так как полученная формула будет формулой алгебры логики, то разложим её по n переменным. Получе
Теорема о тождественной истинности формулы алгебры логики.
Для того, чтобы формула алгебры логики была тождественно истиной, необходимо и достаточно, чтобы каждая элементарная дизъюнкция её конъюнктивной нормальной формы содержала, по крайней мере, одно эл
Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв
Теорема о логическом следствии
Формула алгебры логики f является логическим следствием формулы алгебры логики g,тогда и только тогда, если g f.
Доказательство.
Основные схемы доказательств
Схема 1. «Если x то y»
Доказательство теорем типа “если x, то y”.
Схема доказательства основана на следующем логическом следствии:
.
Методы минимизации
К настоящему времени широкое применение получили:
1. Расчетный метод (метод непосредственных преобразований).
2. Расчетно-табличный метод (метод Квайна-МакКласки).
3. Мет
Этапы минимизации
В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов:
1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами к
Исчисление предикатов
Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП).
Алфавит ИППП состо
Значение формулы логики предикатов.
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики преди
Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj&
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов