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

Определение 1. Множества А и В равны, если они состоят из одних и тех же элементов, обозначается А = В.

Свойство 1. Пустое множество единственно.

Доказательство. Пусть 01 и 02 - пустые множества, тогда утверждения х € 01 и х € 02 равносильны, т.к. они оба являются ложными. Следовательно, 01 = 02 по определению 1.

Для обозначения стандартных числовых множеств будем применять следующие обозначения:

N = { 1,2,3,... , п, .. } — множество натуральных чисел;

Z = {0, ±1, ±2,... , ±n,...} — множество целых чисел;

Q ⁼ {m/n m € Z ,n € N} — множество рациональных чисел;

R = (—оо; +оо) — множество действительных чисел;

C = {a + bi|a € R,b €  R} — множество комплексных чисел.

§ 3. Операции разности и симметрической разности

множеств

§ 16. Кванторы и их свойства

§ 4. Декартово произведение множеств, бинарные

Отношения

Свойство 1. Если подмножество А имеет несколько максимальных элементов, то они несравнимы между собой.

Свойство 2. Если в подмножестве А имеется наибольший элемент, то он является и единственным максимальным элементом этого подмножества.

Свойство 3. Элемент а € А - наибольший в подмножестве А тогда и только тогда, когда он является одним из верхних граней этого подмножества.

ГЛАВА 3. КОМБИНАТОРИКА

§ 1. Перестановки, размещения и их количество

Принцип комбинаторного умножения. Если событие А можно осуществить т способами, и независимо от этого, событие В — п способами, то оба события (событие АВ) можно реализовать тп способами. Под n-множеством будем понимать множество из п различных элементов, а (n)-набор получается из n-множества размножением каждого его элемента в достаточно большом количестве экземпляров.

Определение 1. Перестановкой из п элементов называется упорядоченное n-множество.

Определение 2. Размещением из n по к, где 0 < к<=n, называется упорядоченное k:-подмножество данного n-множества. Размещение из n по к можно реализовать последовательной выборкой к шаров из имеющихся в урне nразличных шаров, поэтому k-подмножество часто называют к -выборкой.

Теорема 1. Количество всех размещений из n по k; находится по формуле

Доказательство. Применим метод комбинаторного умножения. Первый элемент можно выбрать n способами, после этого второй элемент можно выбрать n — 1 способом и т.д., последний k-тый элемент можно выбрать n — k+ 1 способом. Значит последовательная выборка осуществима п(п — 1) •... • (n — n +1) способами. Умножив и разделив это произведение на (n — k)!, мы получим искомую формулу. Теорема доказана.

§6. Функции

Определение 1. Функцией f, отображающей множество Xво множество У, обозначается f : X—> У, называется правило, по которому каждому х € Xставится в соответствие элемент у € У, который считается значением функции f и обозначается через f(х).

Множество Xназывается областью определения, а множество V(f) — {f{x) | х € X} является областью значений функции f.

Множество Г_f = {(х, у) | х € X, у = f(х)} называется графиком функции f : X —> У. Заметим, что Г_f является бинарным отношением между Xи У, для которого выполнено условие V x € X -]! у €У ((х, у) € Г_f). Такие бинарные отношения называют функциональными и часто отождествляют понятия функции и функционального отношения.

Следствие. Количество всех различных перестановок данного n-множества задается формулой Р_п = А_nⁿ= n!.

Определение 3. Упорядоченная к -выборка данного (n) -набора называется размещением из n по k с повторениями.

Размещения из п по к с повторениями можно реализовать, вынимая к раз по одному шару из имеющихся в урне n различных шаров с последующим возвращением его в урну.

Теорема 2. Количество всех размещений из п по к с повторениями задается формулой .