Множества. Операции над множествами

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

(5)

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

(6)

3. Разностьюмножества А и В называется множество всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В:

(7)

4. Симметричной разностьюмножеств А и В называется множество , состоящее из элементов множества А , не принадлежащих множеству В, и элементов множества В, не принадлежащих множеству А:

(8)

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

(9)

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

 

Рис 1. Диаграмма Эйлера-Венна

где - это области 1,2,3

- это область 3;

- это область 1;

- это область 1,3

- это области 2,4.

 

Билет №11

Предикаты

Логика предикатов или исчисление предикатов – это раздел математической логики, исследующий операции над высказываниями, расчлененными на субъект и предикат.

Это расширение понятий и логических средств по сравнению с логикой высказываний или Булевой алгеброй. Логические операции с высказываниями, не разделенными на субъект и предикат – это простейший вид логических операций. «В исчислении предикатов делается дальнейший шаг анализа и разрешается рассматривать объектно–предикатную структуру простых предложений и пользоваться операциями композиции, зависящими от этой структуры», - пишет Клини.

Слово предикат (от латинского praedicatum – сказуемое), то что высказывается (утверждается или отрицается) в суждении о субъекте. Предикат выражает наличие или отсутствие того или иного признака у субъекта.

В логике предикатов под предикатом понимается некоторое свойство или отношение.

В логике предикатов, как и в логике высказываний, высказывания представляют собой или «Истину» или «Ложь». Разница в том, что в логике предикатов истинностное значение ставится в соответствие определенному предмету или группе предметов, тогда как в логике высказываний

они относились к высказыванию.

С точки зрения математики Предикат очень удобно рассматривать как функцию от некоторого числа переменных, значением которой будут логические величины.

Определение: n – местным предикатом называется логическая функция, значениями которой являются высказывания об упорядоченных множествах из n объектов, представляющих значения аргументов.

Чтобы задать n – местный предикат Р(х₁…х_N) следует указать множества D_i i=1,N - области изменения предметных переменных Х. Предикат определяется заданием подмножества М в декартовом произведении D_i. При этом Р(х₁…х_N) понимают как высказывание "упорядоченный набор (х₁…х_N) принадлежит М". Понятие предиката может еще интерпретироваться так: "Из посылок х₁…х_N, следует заключение В".

Определение: Квантор – это логическая операция, которая по предикату Р(х) строит высказывание, характеризующее область истинности предиката Р(х).

В математической логике наиболее употребительный квантор всеобщности " и квантор существования $. Высказывание "х Р(х) означает, что область истинности предиката совпадает с областью значения переменной х. Высказывание $х Р(х) означает, что область истинности предиката не пуста.

Определение: Формула

1. Любая переменная – это формула.

2. Если А и В – формулы, то ØА, (АÚВ), (А&В), (А®В),"х А, $х А - формулы

Определение: Правила, по которым в логике из истинных формул образуются новые истинные формулы называются правилами вывода.

Определение: Выводом называется непустая конечная последовательность формул С₁…С_n, таких что:

· каждая С_i – есть либо посылка, либо получена из предыдущих формул по одному из правил вывода.

· Если в выводе применялись правила 5 или 7, то все формулы, начиная с последней посылки и вплоть до результата применения данного правила, исключаются из дальнейших шагов построения вывода.

Билет №12