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

Если предложение содержит n переменных, то можно определить n-местный предикат, заданный на множестве как функцию

Не теряя общности рассуждений, можно полагать и работать с функцией

(22)

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

Рассмотрим n-местный предикат (22). Обозначим через множество всех наборов значений предметных переменных, на которых P получает значение “истина”:

(23)

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

4.2. Множество истинности предикатной формулы

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

Пример 15. Заданы предикаты со множествами истинности . Рассмотрим предикаты, заданные предикатными формулами:

а)

б)

в)

г)

Выразим множества истинности предикатных формул через множества с помощью известных операций над множествами.

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

. (24)

б) В силу определения конъюнкции тогда и только тогда, когда одновременно выполняются условия и . Следовательно, тогда и только тогда, когда и . Это означает, что , то есть

. (25)

в) В силу определения отрицания тогда и только тогда, когда . Следовательно, тогда и только тогда, когда . Это означает, что , то есть

. (26)

г) В силу определения импликации тогда и только тогда, когда одновременно выполняются условия и . Следовательно, тогда и только тогда, когда и , то есть

.

Применим к обеим частям последнего равенства операцию дополнения и получим

Используя известные тождества теории множеств преобразуем равенство к виду

Это означает, что

. (27)

Равенства (24)-(26) обосновывают соответствие между логическими операциями и операциями над множествами, которое отмечалось ранее в разделе 2.1. Равенство (27) можно получить также, рассматривая СКНФ импликации

.

Тогда

и далее с учетом результатов п. п. а, б, в:

. ■

Для предикатной формулы , заданной на множестве , различают следующие случаи:

– формула выполнимая на множестве ;

– формула тождественно истинная на множестве ;

– формула тождественно ложная на множестве .

Если для формулы можно найти предметную область , на которой формула будет выполнимой, то формулу F называют просто выполнимой. Если формула является тождественно истинной на любой предметной области , то формулу F называют общезначимой. Если формула является тождественно ложной на любой предметной области , то формулу F называют противоречивой.

Пример 16. Рассмотрим следующие предикатные формулы:

а) ,

где P – предикатная буква, M – произвольная предметная область;

б)

где P – предикатная буква, M – произвольная предметная область;

в) ,

где M – произвольное числовое множество.

Формула в силу закона противоречия принимает значение ложь при подстановке любого значения x из любой предметной области. Следовательно, формула является тождественно ложной на любой предметной области, то есть противоречивой.

Формула в силу закона исключенного третьего принимает значение истина при подстановке любого значения x из любой предметной области. Следовательно, формула является тождественно истинной на любой предметной области, то есть общезначимой.

Формула является тождественно ложной при xÎR, то есть на множестве действительных чисел. Однако та же формула является выполнимой при xÎC, то есть на множестве комплексных чисел. Следовательно, формула является выполнимой. ■

4.3. Кванторы

Пример 17. Обратимся к предикату P(x)=(x>2), xÎR. Этот предикат встречался в формуле (21) из примера 14. Запишем его, несколько изменив:

x>2, для всех xÎ R. (28)

Очевидно, что предложение (28) ложное. Чтобы сделать такое заключение, не требуется выполнять подстановку в (28) числовых значений переменной x. Мы встретились с новым способом превращать предикаты в высказывания. При этом предметная переменная оказывается связанной в некотором дополнительном условии, а полученное выражение не зависит от этой переменной. В нашем примере условие выражается словами “для всех…”. ■

Условие, которое связывает предметную переменную, выражается в математической записи с помощью специальных логических символов – кванторов. Используют два квантора:

– квантор общности (соответствует словесным формам “для всех…”, “для каждого…”);

– квантор существования (соответствует словесной форме “существует хотя бы один…”).

Предложение (28) можно представить теперь в символьной форме:

("xÎR)P(x). (29)

Принято говорить, что переменная x в формуле (29) связана квантором. Так как предикат – одноместный, то оказывается, что все переменные в формуле (29) связанные. При этом предикат превращается в высказывание. В примере 16 высказывание получилось ложным. Если в том же предикате , который задан в (21), связать переменную квантором существования, то возникнет высказывание вида

($xÎR)P(x). (30)

В словесной форме (30) представляется следующим предложением:

“Существует хотя бы одно действительное число x такое, что x>2”. Очевидно, что данное предложение является истинным высказыванием.

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

Пример 18. На множестве R2 задан двухместный предикат

.

Множество R2 можно представить как координатную плоскость . Тогда множество истинности представляет собой единичную окружность с центром в начале координат (рис.5).

Свяжем переменную y квантором существования. Получим одноместный предикат

B(x)=($yÎR)A(x,y)=($yÎR),

который определен на множестве действительных чисел R. Множество истинности этого предиката Т(B)=[-1,1]. Если в предикате B(x) связать квантором оставшуюся свободную переменную x, то получится 0-местный предикат, то есть высказывание. Например,

C=($xÎR)B(x)=($xÎR)($yÎR)

представляет собой истинное высказывание, в котором утверждается, что существует, по крайней мере, одна точка координатной плоскости Oxy, принадлежащая единичной окружности с центром в начале координат. В то же время

D=("xÎR)B(x)=("xÎR)($yÎR)

представляет собой ложное высказывание, содержащее утверждение, что первая проекция единичной окружности покрывает всю ось Ox. ■

Рис.5

Выше обсуждались высказывания, которые заданы в символьной форме выражениями (29), (30). Каждое из высказываний получено в результате связывания квантором переменной в одном и том же предикате. Однако, логические значения высказываний оказались различными. Это объясняется тем, что в двух случаях применялись разные кванторы.

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

Пример 19. Рассмотрим двухместный предикат

.

Получим из него высказывания, связав переменную x квантором общности, а переменную y – квантором существования. Применяя разный порядок следования кванторов, получим два высказывания:

В высказывании A утверждается, что для любого действительного числа найдется действительное число, которое больше первого. Это высказывание, очевидно, истинное. Высказывание B утверждает, что существует некоторое действительное число, которое больше любого действительного числа. Это утверждение, столь же очевидно, ложное. ■

Упражнения

4.1.  Найти множество истинности предиката . Изобразить это множество на координатной плоскости.

1) .

2) .

3) .

4)

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

Требуется:

1)  представить предикаты таблицами;

2)  определить множества истинности ;

3)  определить логические значения высказываний

4)  определить логические значения высказываний

5)  определить логические значения высказываний

а)

	0	1	1	0
	1	0	1	0
	1	0	0	1

	1	0	0	1
	0	1	0	1
	0	1	1	0

б)

	0	1	1	0
	1	1	0	1
	0	1	0	1

	1	0	0	0
	1	1	1	1
	0	0	1	0

в)

	1	1	0	0
	0	0	1	0
	1	1	0	0

	1	1	1	1
	0	1	0	0
	1	1	1	0

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1.  Аляев математика и математическая логика: учебник / , . М.: Финансы и статистика, 20с.

2.  Шапорев логика: Курс лекций и практических занятий / . СПб.: БХВ-Петербург, 20с.

3.  Судоплатов математика: учебник. / , . Новосибирск: Изд-во НГТУ, 20с.

4.  Новиков математика для программиста /. СПб.: Питер, 20с.

5.  Белоусов математика: учебник для вузов /, ; под ред. , . М.: Изд.-во МГТУ им. , 20с.

6.  Горбатов основы дискретной математики. Информационная математика: учеб. пособие для вузов /. М.: Наука, 20с.

7.  Игошин логика и теория алгоритмов /. М.: Издательский центр «Академия», 20с.

8.  Игошин и упражнения по математической логике и теории алгоритмов / . М.: Издательский центр «Академия», 20с.

9.  Игошин с элементами математической логики (Лекции для студентов гуманитарных специальностей) / . Саратов: Изд-во «Научная книга», 20с.

10.  Новиков математической логики / . М.: Наука, 19с.

11.  Гиндикин логики в задачах / . М.: Наука, 19с.

12.  Гаврилов и упражнения по курсу дискретной математики. / , . М.: Наука, 19с.

13.  Кузнецов математика для инженера. / , -Вельский. М.: Энергоатомиздат, 19с.

Оглавление

Введение………………………………………………………………………..3

1. Начальные сведения о множествах и функциях…………………........3

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

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

Упражнения…………………………………………………………….........6

2. Логические функции………………………………………………………7

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

2.2. Представление логической функции в нормальной форме………...11

2.3. Функционально полные системы…………………………………….16

Упражнения………………………………………………………………...18

3. Применение логических функций в логике высказываний………...18

3.1. Элементарные и составные высказывания…………………………..18

3.2. Тавтологии логики высказываний……………………………………19

Упражнения………………………………………………………………...22

4. Логика предикатов………………………………………………………..22

4.1. Начальные понятия логики предикатов…………….………………..22

4.2. Множество истинности предикатной формулы………….………….24

4.3. Кванторы………………………………………………….……………26

Упражнения………………………………………………………………...28

Заключение…………………………………………………………………...30

Литература……………………………………………………………………31

Учебное издание

СЕРЕБРЯКОВ Андрей Владимирович

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

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