Элементарный курс математической логики (стр. 1 )

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Саратовский государственный технический университет

ЭЛЕМЕНТАРНЫЙ КУРС МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Учебное пособие

для студентов всех специальностей

Саратов 2011

УДК 510.6

ББК 22.12

С 32

Рецензенты:

Кафедра вычислительного эксперимента в механике

Саратовского государственного унверситета

им.

Доктор физико-математических наук, профессор

Одобрено

редакционно-издательским советом

Саратовского государственного технического университета

С 32 Элементарный курс математической логики. Логические функции: учеб. пособие. Саратов: Сарат. гос. техн. ун-т, 20с.

ISBN 2368-5

Учебное пособие содержит начальные понятия о множествах и функциях; рассмотрены основные законы алгебры двузначных логических функций с применением в логике высказываний и предикатов.

Предназначается для студентов, обучающихся в технических вузах.

УДК 510.6

ББК 22.12

ã Саратовский государственный

технический университет, 2011

ISBN 2368-5 ã , 2011

ВВЕДЕНИЕ

В настоящем учебном пособии излагаются начальные понятия о множествах и функциях. Рассмотрены основные законы алгебры двузначных логических функций. Далее обсуждается применение логических функций в логике высказываний и предикатов. Каждый раздел заканчивается набором упражнений для самостоятельного решения. В списке литературы [1-13] приведены некоторые учебники и учебные пособия, изданные в последние годы, а также широко известные учебники прошлых лет издания.

Пособие предназначено для студентов, обучающихся в технических вузах. Материал пособия может быть использован при освоении отдельных разделов курса общего курса математики, а также при изучении дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов».

1. НАЧАЛЬНЫЕ СВЕДЕНИЯ О МНОЖЕСТВАХ И ФУНКЦИЯХ

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

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

Если каждый элемент, который принадлежит множеству , принадлежит в то же время множеству , то множество называют подмножеством множества ( включается в ). При работе с подмножествами принято, что для любого множества :

Символ используется для обозначения пустого множества, то есть множества, которому не принадлежит ни одного элемента. Множество называется универсальным, если для любого множества выполняется условие . Если выполняются условия и , говорят, что и – равные множества: .

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

1)  перечислить все элементы, принадлежащие множеству;

2)  задать порождающую процедуру, которая позволяет определить все элементы искомого множества, совершая действия с элементами уже известного множества;

3)  указать универсальное множество и характеристическое свойство, позволяющее выбрать из все те и только те элементы, которые принадлежат искомому множеству.

Перечислением элементов можно задать только конечное множество, то есть множество, содержащее конечное число элементов.

Пример 1. Рассмотрим конечные множества, заданные перечислением элементов:

– множество всех букв латинского алфавита;

– множество всех арабских цифр;

– бинарное множество логических констант. ■

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

Объединением множеств и (обозначается как ) называется множество всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств , . Символьная запись данного определения:

Пересечением множеств и (обозначается как ) называется множество всех тех и только тех элементов, которые принадлежат и :

Разностью множеств и (обозначается как ) называется множество всех тех и только тех элементов множества , которые не принадлежат :

Дополнением множества (обозначается как , или ) называется множество всех тех и только тех элементов, которые не принадлежат :

.

Иллюстрации данных операций в виде диаграмм Венна приведены на рис.1-4.

В заключение приведем некоторые тождества теории множеств:

(1)

1.2. Соответствие между множествами. Понятие функции

Пусть – произвольные множества. Декартово произведение множеств и (обозначается как ) – это множество всех упорядоченных пар таких, что .

Пример 2. При записи шахматной партии используются множества

–для обозначения вертикалей, –для обозначения горизонталей. Поля шахматной доски обозначаются с помощью элементов множества . ■

Можно построить декартово произведение произвольного числа множеств:

.

Упорядоченный набор элементов будем далее называть вектором. Компоненты будем называть проекциями вектора:

Рассматривая частный случай декартова произведения при , получим множество .

Используя понятие декартова произведения, определим соответствие между множествами как упорядоченную тройку множеств:

(2)

Множество , которое состоит из векторов , называется графиком соответствия. Зададим область определения соответствия как множество

и область значений соответствия как множество

.

Пусть теперь – произвольный фиксированный элемент множества . Элемент называется образом элемента при данном соответствии, если . Если при данном соответствии каждый элемент из области определения имеет единственный образ, то соответствие называют функцией.

В дальнейшем изложении встретятся функции многих переменных, то есть функции, для которых множество из (2) само является декартовым произведением: . Компоненты вектора являются в этом случае независимыми переменными (аргументами). Обозначать такие функции будем как или .

Пример 3. Расстояние точки на координатной плоскости от начала координат может быть задано функцией f: R2 → R, которая представлена формулой ■

Упражнения

1.1  Следующие множества задать перечислением их элементов:

1) A={xÎR ½ x3–3x2+2x = 0};

2) A={xÎR ½ x+1/x £ 2, x > 0};

3) A={xÎN ½ x2–3x–4 £ 0};

4) A={xÎZ ½ ¼ £ 2x < 5}.

1.2. Задать множества перечислением их элементов и найти , если:

1) – множество делителей числа 12; – множество корней уравнения ; – множество нечетных чисел таких, что

2) – множество четных чисел таких, что ; – множество делителей числа 21; – множество простых чисел, меньших 12.

1.3. Найти и изобразить эти множества на числовой прямой, если:

1)

2)

3)

1.4. Пусть – такие множества, что . Найдите множество , удовлетворяющее условиям .

1.5. Найти область определения для следующих функций f: R→R

1) 2)

3) 4)

1.6. Используя определения операций над множествами, доказать данное тождество теории множеств. Проиллюстрировать доказательство с помощью диаграмм Венна.

2. ЛОГИЧЕСКИЕ ФУНКЦИИ

2.1. Двузначные логические функции

Двузначной логической функцией n переменных называется любая функция

. (3)

В формуле (3) через B обозначено множество из двух логических значений: ложь (обозначается как 0), истина (обозначается как 1). Для логической функции число всех возможных наборов значений аргументов конечное, равное 2n. Это позволяет задавать логические функции в форме таблиц истинности. Так как для любого данного набора значений аргументов функция может принимать одно из двух значений из множества B, оказывается, что существует конечное число функций от n аргументов. Число таких функций равно .

Рассмотрим функции от одного аргумента (n=1), заданные в табл.1.

Таблица 1.

x	f0(x)	f1(x)	f2(x)	f3(x)
0	0	0	1	1
1	0	1	0	1

Приведем названия и обозначения для функций из табл.1:

f0(x)= 0 –логическая константа ложь; f1(x)= x –тождественная функция;

f2(x)= –отрицание (обозначается также );

f3(x) = 1 –логическая константа истина.

Рассмотрим теперь функции от двух аргументов (n=2). Таких функций будет 16. Для каждой из них можно задать 4 набора значений аргументов. Функции gi(x1,x2), i=0,…,15 приведены в табл.2.

Таблица 2.

x1	x2	g0	g1	g2	g3	g4	g5	g6	g7	g8	g9	g10	g11	g12	g13	g14	g15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Следует обратить внимание на правило перечисления наборов (x1,x2) в табл.2. Использован лексикографический порядок, который совпадает с порядком возрастания наборов, понимаемых как двоичные числа. В качестве столбца значений функции gi в табл.2 присутствует двоичная запись числа i. Зафиксировав лексикографический порядок перечисления наборов, мы можем представлять логические функции столбцами значений. Например,