Квантор всеобщности

25. Двухместные предикаты: использование кванторов общности и существования.

Квантор существования. Пусть P(x) – некоторый предикат. Под выражением ∃xP(x) будем понимать высказывание истинное, когда существует элемент множества M, для которого P(x) истинно, и ложное – в противном случае. Читается это выражение так: «существует x такое, что P(x)». Это высказывание уже не зависит от x. Символ ∃x называется квантором существования.

Квантор всеобщности. Пусть P(x) – некоторый предикат, принимающий значение И или Л для каждого элемента множества M. Тогда под выражением ∀xP(x) будем подразумевать высказывание истинное, когда P(x) истинно для каждого элемента x из множества M, и ложное – в противном случае. Читается это выражение так: «для всех x P(x)». Это высказывание уже не зависит от x. Символ ∀x называется квантором всеобщ

Логические законы, формулирующиеся с использованием кванторов.

Действительно в поле М нет элементов, обладающих свойствами Р(х), тогда и только тогда, когда все элементы из М не…

Множества и классы понятий, основные операции над нами. Круги Эйлера.

Чтобы как-то описать, о чем все же идет речь, говорят, что множество – это совокупность некоторых объектов, которые называются элементами множества. Однако такое описание не может считаться определением, так как совокупность – это просто другое на- звание множества. Множество, которому не при- надлежит ни один элемент, называется пустым.
Универсальным называют все остальные множества и обозначают U.
Операции над множествами:
1) Множество A называется дополнением множества A, если A состоит из
элементов, которые не принадлежат A: A =△ {x : x ∈/ A}
2)Множество A ∪ B называется объединением множеств A и B, если оно состоит из элементов, которые принадлежат или множеству A, или множеству
B(операция«или»)
3)Множество A ∩ B называется пересечением множеств A и B, если оно состоит из элементов, которые принадлежат и множеству A, и множеству B
(операция «и»)
4) Множество A − B = A B =△ A ∩ B называется разностью множеств A и B, оно состоит из элементов, которые принадлежат множеству A, но не
принадлежат множеству B

Круги Эйлера— геометрическая схема, с помощью которой можно изобразить отношения между подмножествами, для наглядного представления

Прямое (декартово) произведение множеств. Комбинаторные структуры.

Прямое (декартово) произведение множеств А и В называется множество, состоящее из всех упорядоченных пар, первый компонент принадлежит А, а второй принадлежит В.

, соответственно

Понятие отношения. Обратное отношение. Графическое представление бинарных отношений.

Множество точек плоскости, координаты которых (x,y), образуют упорядоченные пары некоторого бинарного отношения называется графиком данного… Бинарные отношения – это множества, их можно объединять, пересекать, дополнять… Бинарное отношение указывает на наличие определенной связи между некоторыми парами объектов.

Отношение эквивалентности. Свойства отношений. Разбиение множеств на классы.

Отношение рна множестве М называется отношением эквивалентности, если обладает отношениями:

1.Рефлексивности

2. Симметричности

3.Транзитивности

Отношения могут обладать рядом свойств, которые определяются через условия, которым должны удовлетворять их элементы

Пусть рна множестве А, тогда р называется:

 

· рефлексивным, если

· симметричным, если

· транзитивным, если

 

Отношение порядка. Свойства отношений.

1.Иррефлексивность 2.Асиметричность 3.Транзитивность

Отображения и их основные свойства. Виды отображений.

Мн-во F(y) вторых компонент мн-ва F(мн-во всех образов) называется областью значений отображения N. Виды: 1) F(x)=x – всюду определённое;

Комбинаторные структуры (размещение, перестановки, сочетания)

Перестановкой из n элементов называется любой упорядоченный набор этих элементов, т.е. место элемента в наборе, порядок перечисления имеют… Pn = n× (n- 1) ×...× 1 = n! Размещением, содержащим k элементов из n имеющихся называется любой упорядоченный набор, содержащий k элементов,…

Перестановка с учетом повторения.

=, где n = n1 + n2 +…+ nk 35. Сочетания с учётом повторений. Сочетанием с повторением из nэлементов по kэлементам называется всякая последовательность из kэлементов:

Биноминальные коэффициенты. Свойства биномиальных коэффициентов.

Биномиальным коэффициентом называется количество способов выбрать набор предметов из различных предметов без учёта порядка расположения этих… Также биномиальные коэффициенты - это коффициенты в разложении (т.н. бином…

Изоморфизм графов.

Графы называют изоморфными, если между множествами вершин можно установить взаимно однозначное соответствие, сохраняющее смежность. Отношение изоморфизма - отношение эквивалентности. Фактически, изоморфные графы - это один и тот же граф.

Маршруты, цепи, циклы.

пример маршрута: 1-2-3-5-7-4-3-5-6-2-3 пример замкнутого маршрута : 3-4-5-7-3-4-1-3  

Деревья.(ориентированные, сбалансированные, бинарные, остовные)

Ориентированным деревом ( или ордеревом) называется ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга.… Висячая вершина ордерева называется листом. Путь из корня в лист называется… Расстояиние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного…

Разрезы.

пусть G (V U) - неориентированный граф

Разрезом называется всякое множество R ребер графа G такое, что удаление этих ребер из графа делает его несвязным.

Разрез называется ппростым, если никакое его собственное подмножество разрезом не является. Разрез по-другому называют коциклом.