Дискретная математика (1). Лекция Составные высказывания

• Название: Лекция Составные высказывания
• Дата: 05.09.2022
• Размер: 2.15 Mb.
• Имя файла: Дискретная математика (1).doc
• Тип: Лекция; #662788
• страница: 7 из 16

Сравнение множеств.

Множество А содержится во множестве В (множество В включает множество А, множество А является подмножеством В), если каждый элемент множества А является элементом множества В. Обозначение: А В.

А В х А х В.

Два множества называются равными, если они являются подмножествами друг друга. Обозначение: А=В.

А=В А В и В А.

Если непустое множество А является подмножеством В и множества А и В не являются равными, то А является собственным подмножеством В.

Пример: М={4, 6, 8, 10}, К={6, 8}; К М, М К, М К, К – собственное подмножество М.

Для множеств существует понятие мощность. Для конечных множеств мощность совпадает с количеством элементов.

Пример: | |=0, |{ }|=1, |{1, 2, 3, 4}|=4.
Лекция 8. Операции над множествами
Объединение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А или множеству В. Обозначение: А В.

А В={x| х А или х В}.

Пересечение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и множеству В. Обозначение: А В.

А В={x| х А и х В}.

Разность двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и не принадлежащие множеству В. Обозначение: А \ В.

А \ В={x| х А и х В}.

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

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

=U \ A или ={x| х А и х U}.

Пример: U={1, 2, 3, 4, 5, 6, 7}, A={1, 2, 3, 4, 5}, В={2, 4, 6}.

А В = {1, 2, 3, 4, 5, 6} А В = {2, 4} А \ В = {1, 3, 5}

В \ А = {6} = {6, 7} = {1, 3, 5, 7}

Для наглядного изображения соотношений между множествами и изображения результатов операций над множествами используют диаграммы Эйлера.

П ример:


А

В



B A А В А В А \ В

Свойства операций над множествами.

Идемпотентность пересечения, объединения.

А А = А А А = А

Коммутативность пересечения, объединения.

А В = В А А В = В А

Ассоциативность пересечения, объединения.

(А В) С = А (В С) (А В) С = А (В С)

Законы поглощения.

(А В) А = А (А В) A = А

Свойства пустого множества.

А = А = А

Свойства универсума.

А U = A А U = U

Инволютивность.

= А

Законы де Моргана.



Свойства дополнения.

А = А = U

Выражения для разности.

А \ В = А
Лекция 9. Понятие предикат.
При анализе рассуждений в логике высказываний нас не интересовала внутренняя структура самих высказываний. И это обстоятельство не позволяет анализировать большое количество рассуждений.

Например:

Через две данных точки проходит единственная прямая.

Точка лежит между двумя точками.

х>5.

Эти предложения не являются высказываниями, но становятся таковыми, если предметным переменным, входящим в эти предложения, задать конкретны значения. Так в последнем примере при х = 3 получим ложное высказывание, а при х = 8 истинное высказывание. Значения предметных переменных берутся из некоторого предметного множества А (точек, углов, прямых, чисел, ромбов и т.д.).

Введем понятие предиката.

Под предикатом предметной переменной х А будем понимать функцию Р(х) на {0,1}. Предикат р (х) называется одноместным предикатом

Например:

Предикат х > 5, x R: при х = 4 предикат обращается в ложное высказывание. При х = 7 предикат обращается в истинное высказывание.

Функция Р (х, у), где х, у А, принимающая значения во множестве {0,1} называется двухместным предикатом.

Например: х<у

Пусть У = 5, получим х < 5 – одноместный предикат. Если положить х = 4, то 4 < 5 – нульместные предикаты (высказывания).

Местность предиката - количество предметных переменных. Задание конкретного значения предметным переменным понижает местность предиката. Одноместные предикаты выражают свойство быть чем-то.

Например:

Свойство быть точкой. х – точка. Введем обозначение этого предиката: Т (х). Тогда Т (А) читается как А-точка.

Двухместные предикаты и предикаты более высокой местности выражают отношения между объектами.

Например: Двухместный предикат принадлежности – х у.

Если х – точка, а у – прямая, то читаем: точка х принадлежит прямой у.

Выбор предикатного символа остается за пользователем. Так, вместо х у можно ввести предикат Р (х, у), оговорив, что Р (,) – это предикат принадлежности (запятая в скобках свидетельствует о том, что предикат двухместный). Разумеется, что нельзя использовать одно и тоже обозначение для разных предикатов. Широко используются известные из математики обозначения предикатов ≈, ≠, ≡, ≤, ≥, ┴, _║, =

Область истинности.

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