Дискретная математика : элементы логико-математического языка. Ч. I

ОГЛАВЛЕНИЕ 

От авторов 
6 

Введение 
7 

Примечания 
9 

Глава I. Начальные понятия 
10 

§ 1. Виды языков. Язык и метаязык 
10 

1. Определение и важнейшие функции языка 
10 

2. Естественные и искусственные языки. Научные языки. 
Логико-математический язык 
10 

3. Иерархия языков 
11 

4. «Переход» из предметного мира в языковой. Главные 
единицы естественного языка и их функции 
12 

Упражнения 
12 

Примечания 
13 

§ 2. Логические и семиотические аспекты 

логико-математического языка 
13 

1. Главные единицы логико-математического языка 

и их функции 
13 

2. Модальность и состав суждения. Виды предложений 
14 

3. Значимость письменной речи научных языков 
16 

4. Семиотические аспекты письменной речи 
логико-математического языка 
16 

Упражнения 
17 

Примечания 
20 

Приложение. Типы письма, используемые в языках 
21 

1. Линейность речи 
21 

2. Пиктография 
23 

3. Идеография 
23 

4. Фонография 
25 

5. Почему научные языки включают в себя в большом 

объеме элементы идеографии 
26 

Примечания 
27 

§ 3. Исходные имена логико-математического языка 
29 

1. Основные и вспомогательные имена 
29 

2. Синтаксические и семантические функции скобок 
30 

Упражнения 
31 

Примечания 
32 

3 

§4. Константы 
33 

1. Константа и ее денотат. Роды и виды констант 
33 

2. Логаческие константы 
34 

3. Математические объектные константы 
35 

4. Математические субстантивные константы 
36 

Упражнения 
41 

Примечания 
42 

§ 5. Переменные 
44 

1.Экстенсионал и денотаты переменной 
44 

2. Номенклатура и номины переменной 
45 

3. Значность переменной. Роды и виды переменных 
47 

4. Логаческие переменные 
47 

5. Переменные, используемые в логако-математическом 

языке (мегаобъектыЛМЯ) 
49 

6. Математические объектные переменные 
50 

7. Математические субстантивные переменные 
52 

Упражнения 
53 

Примечания 
55 

Глава П. Синтаксические и прагматические аспекты 

логико-математического языка 
56 

§ 1. Алфавит логико-математического языка. 

Классификация фраз 
56 

1.06 алфавите логако-математического языка 
56 

2. Обозначения фраз 
57 

3. Введение фраз в текст 
58 

4. Совместная классификация фраз по содержанию и составу 
59 

Упражнения 
62 

Примечания 
64 

§ 2. Конструктивные термы 
66 

1. Родовые символы 
66 

2. Объектные символы 
67 

3. Субстантивные символы 
68 

4. Конструктивные термы. Конструктивные 

термальные константы, формы, переменные и символы 
69 

5. Подфразы конструктивных термов 
70 

Упражнения 
72 

Примечания 
75 

§ 3. Соотношения 
78 

1. Истинностные и предикатные символы. 
Элементарные соотношения 
78 

4 

2. Коннекторные символы. Неэлементарные соотношения 
80 

3. Пропозициональные формулы 
81 

4. Подфразы соотношений 
81 

Упражнения 
82 

Примечания 
83 

§ 4. Дескриптивные термы. Выражения 
84 

1. Семантические предпосылки и синтаксическое 

определение понятия «дескриптивный терм» 
84 

2. Схема совместного определения термов и соотношений 
86 

3. Выражения. Подвыражения 
87 

Упражнения 
88 

Примечания 
88 

§ 5. Упрощение выражений 
89 

1. Правила сокращения записи термов 
89 

2. Правила сокращения записи соотношений 
91 

Упражнения 
94 

Примечания 
95 

Литература 
96 

5 

Памяти 

Марка Борисовича 

Гендлера 

От авторов 

Данное пособие посвящается памяти Марка Борисовича 
Гендлера, доктора технических наук, профессора Московского государственного института стали и сплавов (МИСиС), скоропостижно 
скончавшегося 23 октября 1998 г. на 62-м году жизни. 

М.Б. Гендлер работал на кафедре инженерной кибернетики 
(КИК), руководимой профессором СВ. Емельяновым, с момента ее 
основания в 1966 г. К этому времени относится появление в МИСиС 
аналоговой и цифровой вычислительной техники, методическое руководство и математическое сопровождение которой осуществлялось 
КИК. М.Б. Гендлер был первым в МИСиС, кто стал преподавать несколько учебных дисциплин по различным главам дискретной математики - разделу математики, служащему, в частности, теоретической базой для изучения вычислительной техники и ее использования в практической деятельности, читая целый ряд учебных курсов 
для студентов, аспирантов и сотрудников. Лично и в соавторстве 
М.Б. Гендлер написал серию учебников, учебных и методических 
пособий и сборников упражнений по дискретной математике. 

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

6 

ВВЕДЕНИЕ 

1. Эволюция становления средств для изображения «математического мира» [24, с. 13 - 14] представляется нам как увлекательный «спектакль», действие которого разворачивается одновременно 
с формированием человеческого миропонимания. Однако, начав детально анализировать ее, мы рискуем непозволительно далеко отойти 
от главного предмета нашего изучения - логико-математического 
языка (ЛМЯ). Поэтому сразу же перейдем к изложению основной 
темы, отсылая читателей, интересующихся историческими аспектами возникновения и развития способов компактного и наглядного 
отражения «мира математики», к специальной литературе (см., например, монографии [5] и [27] и приведенную там обширную библиографию). 

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

3. Основной объект, описываемый в данном пособии-ЛМЯдостаточно сложный. Его содержание будет постепенно раскрываться и 
уточняться на протяжении всего нижеследующего текста. Но уже 
сейчас мы могли бы принять в качестве исходного следующее описательное определение. 

Логико-математический язык - это семиотическая система 
для обозначения логических и математических объектов, их свойств 
и отношений, а также логических связей между двумя последними. 

Таким образом, ЛМЯ может рассматриваться как искусственный язык [24, с. 16], предназначение которого сформулировано 
в данном определении. Он включает в себя совокупность знаковых 
средств, а именно, устных и более важных для нас письменных, или 
графических знаков, а также целый ряд правил и методов, которые 
мы будем формулировать и описывать по мере продвижения вперед^'. Пока же отметим только, что среди этих правил нас будут особенно интересовать синтаксические, семантические и прагматические, т.е. относящиеся соответственно к формальным построениям 
и з о б р а ж е н и й математических предметов, осмысливанию, или 

7 

интерпретации, этих изображений и графическим упрощениям последних с целью их более удобного использования на практике. 
Именно на этих аспектах ЛМЯ мы постараемся акцентировать внимание читателя. 

4. Сделаем несколько замечаний относительно назначения и 
специфики пособия. 

4.1. В настоящем пособии мы хотели бы по возможности содержательно познакомить читателей с общим взглядом на ЛМЯ как 
особую знаковую систему и осветить те его важные стороны, на которые не всегда обращают внимание. Поэтому мы перенесли многие 
известные формализации, обычно перегружающие основной текст, в 
упражнения. Решения некоторых из них подробно разобраны^'. 

4.2. Некоторые фрагменты, отмеченные в начале и конце 
звездочками (*), содержат более трудный материал. Их включение в 
текст преследовало по меньшей мере следующие цели: а) сделать 
содержание книги более интересным для читателей с разными уровнями подготовки, например для тех, которые могли бы получить 
сведения, приведенные в этих фрагментах, из других источников; 
б) познакомить читателей с иными подходами и точками зрения на 
излагаемый материал. Указанные фрагменты можно пропустить при 
беглом чтении без ущерба для понимания последующего. 

4.3. Существенную часть текста составляют примечания. Они 
служат для примеров, сравнений, дополнительной информации, исторических справок и т.д. С логической точки зрения игнорирование 
примечаний не вызывает дискомфорта. Образцом такой структуры 
изложения материала (основной текст + упражнения + примечания) 
послужила для авторов монография [30]. 

5. Мы предполагаем, что читатель в известной степени знаком 
с основными понятиями современной математики, такими, например, 
кж множество, кортеж, соответствие, функция, отношение между 
множествами и т.д. О некоторых из них достаточно подробно сказано 
в [7, с. 12 - 15; 19 - 26; 35 - 43; 48 - 54] и [18, с. 11 - 18]. 

6. В заключение - несколько слов о структуре и правилах 
пользования пособием. В нем представлен раздел «Элементы логикоматематического языка» учебной дисциплины «Дискрешая математика». 
Пособие разбито на главы, главы - на параграфы, а параграфы - на 
пункты. Интересующие нас выражения пронумерованы со ссылкой 
на номера главы, параграфа и порядковый номер формулы в главе. 
В каждый пункт включены наглядные примеры. Они, несомненно, 
облегчают понимание текста, поскольку его изложение все же носит 

8 

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

Примечания 

>'Науку, предметом изучения которой служат как отдельные 
знаки, так и знаковые системы, называют семиотикой. Общие сведения о ней можно получить в [1, т. 23, с. 236] или [22]. 

^' С буквами алфавита ЛМЯ и их значениями читатель может 
познакомиться, например в [3, т. 2, с. 457 ст. «Знаки математические»]. 
Более подробно об этом алфавите говорится в п.1 § 1 гл. П. 

^'«Упражнения должны, с одной стороны, дать возможность 
читателю проверить, хорошо ли он усвоил текст; с другой стороны, 
они должны познакомить его с результатами, которые не нашли себе 
места в основном тексте, но тем не менее по-своему интересны» [6, с. 20]. 

9 

Глава I. НАЧАЛЬНЫЕ ПОНЯТИЯ 

§ 1. Виды языков. Язык и метаязык 

1. Определение и важнейшие функции языка 

Прежде чем приступить к изучению логико-математического 
языка (ЛМЯ), познакомимся с общим понятием языка. Для него существует много определений. В качестве отправного мы выберем 
следующее: язык-это 
с е м и о т и ч е с к а я, или з н а к о в а я , 
система [22, с. 32], выполняющая ряд функций, важнейшие из которых: 

Я1. Номинативная, т.е. обозначения предметов и действий^'. 
Я2. Познавательная, т.е. отражения явлений действительности. 
ЯЗ. Коммуникативная, т.е. общения. 

2. Естественные и искусственные языки. 
Научные языки. Логико-математический язык 

По происхождению различают естественные и искусственные 
языки. Под естественным языком понимают исторически сложившуюся в человеческом обществе систему дискретных звуковых, а 
позднее и письменных знаков, служащую главным образом для выполнения функций яг - ЯЗ (см. п. 1). Здесь термин естественный не 
следует понимать только как данный природой. Наоборот, весь процесс становления и развития естественного языка, продолжающийся 
и сейчас, свидетельствует о том, что во многом он является результатом творческих усилий сотен поколений человечества. 

Признаки стихийности возникновения и формирования, а 
также практически неограниченные область применения и выразительные возможности отличают естественный язык от искусственных, созданных в качестве его заменителей в тех сферах человеческой деятельности, где он не отвечает каким-либо требованиям 
[24, с. 16]. Искусственные научные языки служат средством отражения аспектов реальности, которые в этих науках изучаются. Разумеется, и искусственные языки должны выполнять функции Я1 - ЯЗ, по 
крайней мере, в описываемых ими областях. 

10 

Одним из искусственных научных языков является и ЛМЯ, 
служащий с р е д с т в о м , 
а его основные единицы (см. п. 1 § 2 ) р е з у л ь т а т о м о т р а ж е н и я 
«мира математических предметов» 
(см. [24, с. 10 - 13]). ЛМЯ отвечает условиям Я1 -ЯЗ, поскольку, вопервых, его термины представляют собой имена математических 
объектов, их свойств и отношений; во-вторых, при его помощи отображаются стороны действительности, изучаемые в математике 
[24, с. 14 - 15]; в-третьих, ЛМЯ является средством общения при изучении математики и обсуждении математических проблем. Сейчас 
было бы нелегко дать исчерпывающее описание ЛМЯ, но его строение и содержание будут постепенно уточняться и раскрываться на 
протяжении всего раздела. 

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

3. Иерархия языков 

Поскольку описание ЛМЯ будет излагаться на русском языке, 
то фактически мы будем иметь дело по крайней мере с двумя языками. 
Когда говорят о каком-либо языке U на некотором языке ^2, то U называют объектным, а его осмысленные состшшющш - объектами, а 
Ьг-метаязыком, и его осмысленные состшшющш - метаобъектами. Из сказанного следует, что для нас ЛМЯ будет объектным, а русский - метаязыком. Отметим, что без известных навыков различать 
объекты и метаобъекты не всегда просто, и ниже, (в частности, в п. 5 
§ 5 и п. 2 § 3 гл. II) мы будем говорить об этом более подробно. Пока 
же ограничимся наглядным примером, иллюстрирующим связи между 
двумя указанными языками: «Отношение между метаязыком и объектным языком можно в некотором смысле уподобить отношению 
между русским и французским языками с точки зрения человека, родным языком которого является русский и который изучает французский. Все начальные сведения и пояснения в словарях, учебниках 
грамматики и т.п. учащийся воспринимает на русском языке (мета
11 

языке). Впоследствии он начинает писать по-французски, т.е. строить 
предложения на объектном языке» [26, с. 183]. 

Добавим еще несколько слов по рассматриваемому вопросу 
[12, с. 61]. Иногда говорят о двух языках U и Ьг, относящихся друг к 
другу как объектный к метаязыку. В этом случае в качестве языка их 
описания используют третий язык L^, называемый метаметаязыком. 
Таким образом, может быть построена иерархия языков с любым 
числом уровней. Однако независимо от него естественный язык 
представляет собой высший из уровней. Если существует два уровня, 
то естественньй язык является метаязыком, если три - метаметаязыком 
и т.д. В последнем случае естественный язык и метаязык следует 
различать^'. 

4. «Переход» из предметного мира в языковой. 
Главные единицы естественного языка и их функции 

Произнеся или написав последовательность слов: Обозначим 
что-то через что-то, мы «переносимся» в нашем воображении из 
предметного мира в языковой, где фигурируют уже не его объекты, а 
и м е н у ю щ и е 
их осмысленные знакосочетания, или единицы 
языка [25, с. 74], построенные обычно (но не всегда!) по строгим 
синтаксическим правилам^' из исходных знаков, принадлежащих к 
алфавиту языка (см. примеч. 2 к Введению, *а также п.1 § 1 гл.П.*). 
Важнейшими единицами естественного языка являются слова и словосочетания, служащие языковыми обозначениями вещей из предметного мира, и предложения, чаще всего представляющие собой 
я з ы к о в ы е р е а л и з а ц и и с у ж д е н и й об этих вещах. 

Упражнения 

1. Приведите 5 - 7 русских фраз, в каждой из которых реализуется хотя бы одна функция языка из их перечня Я1 - ЯЗ в п.1. 

2. Какие еще функции, кроме функций Я1 - ЯЗ из п. 1, реализуют некоторые языки? (см. [1, т. 30, с. 464, ст. «Язык»; то же, т. 28, 
с. 139 ст. «Функция в языкознании»]). 

3. Укажите 10-12 естественных и 5 - 7 искусственных языков (см. [14, с. 695, ст. «Язык естественный» и «Язык искусственный»]. 

4. Приведите несколько примеров пар вида «объектный 
язык-метаязык». 

12 

5. Укажите ситуацию, в которой объектный язык совпадает с 
метаязыком. 

6. Приведите пример ситуации, где фигурируют объектный 
язык, метаязык и метаметаязык. 

7. Может ли предметный мир быть частью языкового? 
8. Изобразите посредством диаграммы Эйлера-Венна взаимоотношения между объемами понятий, отражающих основные единицы естественных языков [14, с. 142 ст. «Диаграммы Венна»; 
с. 675 ст. «Эйлеровы круги»; 15]. 

9. Приведите 10-15 слов и словосочетаний естественного 
языка, служащих именами математических предметов, а также 10-15 
предложений естественного языка, являющихся реализациями суждений о математических объектах [24, с. 13 - 14]. 

Примечания 

>'Во многих своих работах известный швейцарский лингвист 
Фердинанд де Соссюр (1857-1913) неоднократно подчеркивал, что 
способность создавать системы р а з л и ч н ы х о б о з н а ч е н и й для 
р а з л и ч н ы х 
понятий 
является для человека естественной 
(см. соответствующую литературу при ст. «Сосюр Ф.М.» в [3, т. 24(1), 
с. 203]). 

^'Более подробные сведения об иерархии языков можно получить, например, в [2, т. 2 с. 550 ст. «Метаязык»; 3, т. 3 с. 653 
ст. «Метаязык» и с. 652 «Метатеория»; 4, с. 256 ст. «Язык»; 12, с. 62; 14, 
с. 348 ст. «Метаязык»]. 

^' См. п. 3 «Введения», а также [22, с. 35 - 37]. Об этих правилах 
мы еще будем говорить в п. 4 § 2. 

§ 2. Логические и семиотические аспекты 
логико-математического языка 

1. Главные единицы логико-математического языка 
и их функции 

в ЛМЯ используют как терминологию естественных языков, 
так и свою. Например, его единицы, т.е. осмысленные знакосочетания 
(в частности, отдельные знаки) (см. п. 4 § 1) именуют фразами'К Условно [30, с. 30] их разделяют на два непустых непересекающихся 
подкласса^'. Фразы, обозначающие логические и математические 

13 

объекты [24, с. 10-14], называют именами, а фразы, представляющие 
собой предложения, передающие математические 
суждения, 
т.е. 
суждения о математических предметах, - соотношениями\ 
или 
формулами'\ 

Пример!. Среди знакосочетаний ЛМЯ: (а)6; (б)+-5)>'[; (B)sin; 
(г)х-у; (д) ^ ; (е)Д5); (ж) с; (з)XvjY; (и) п; (к) делитель 8; (л) 1 < 2; (м)0; 
(н)2 = 0; (о) ш ^;7атно п осмысленными, т.е. фразами, являются (а), (в) - (о). 
Из них (а), (в), (д), (е) - (к) и (м) - имена, а (г), (л), (н) и (о) - формулы. 
*Среди последних (л) и (н) - истинное и ложное высказывания соответственно (см. п. 2)*. 

Замечание. В классе имен ЛМЯ выделяют некоторые подклассы, состоящие только из имен математических объектов того 
или иного р о д а 
или в и д а [14, с. 519 ст. «Род» и с. 88 ст. «Вид»; 
24, с. 13]. Для большей точности в рассуждениях эти имена часто 
дополняют их названиями. 

Пример 2 (см. пример 1). Имена (а), (и) и (к) -обозначения чисел, 
т.е. числовые; из них (а) и (к) - натуральные, а (и) - вещественное. Имена (з) 
и (н) - обозначения множеств, т.е. множественные; имя (в) - обозначение 
функции, т.е. функциональное; *знак (д): ^ (импликатор) - обозначение логической операции (над суждениями) импликация, т.е. коннекторный (см. п. 2 
§ 4); знак (ж): с - обозначение теоретико-множественного отношения нестрогое включение, т.Q. реляционный (см. п. 2 § 4)*. 

2. Модальность и состав суждения. Виды предложений 

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

Волга впадает в Каспийское море; 
(1.2.1) 

Лондон - столица Франции; 
(1.2.2) 

Тот день в Москве был снежным; 
(1.2.3) 

выражают соответственно некие географические положения и состояние московской погоды в какой-то день. 

Описывая в данном пособии элементы ЛМЯ, а не логики, мы 
будем уделять основное внимание не логическим объектам, в част
14 

ности суждениям, а языковым, в данном случае - реализующим их 
предложениям. Но какие-то их стороны, которые нас будут интересовать, имеют логическую природу. Поэтому познакомимся вкратце с 
некоторыми понятиями^', относящимися к суждению, и соответствующей им терминологией. А именно, с теми из них, которые чаще 
всего «переносятся» на языковые реализации суждения, рассматриваемого со следующих сторон: 1) степени его соответствия отражаемому им факту, т.е. его модальности'\ 2) его состава. 

1. Примерами модальностей суждения служат такие его черты как истинность, ложность, неопределенность, возможность, необходимость, неразрешимость и т. д. Модальности истина и ложь называют истинностными. Модальностью предложения, выражающего суждение, называют модальность последнего^'. Эта дефиниция 
модальности такого предложения позволяет нам говорить об истинных, ложных, неопределенных и т. д. предложениях. Например, 
предложения (1.2.1) и (л) из примера 1 п. 1 - истинные, (1.2.2) и (н) ложные, а (1.2.3), (г) и (о) - неопределенные, т.е. высказываниями не 
являются. В классической логике, на результаты которой в основном 
и опирается математика, рассматривают главным образом истинные, 
ложные и неопределенные суждения. Именно с ними, точнее, с их 
языковыми реализациями мы будем иметь дело ниже. 

Скажем еще несколько слов о видах суждений, определяемых 
понятием модальность, и реализующих эти виды предложениях. Суждение называют конкретным, если заключенная в нем информация позволяет утверждать, что оно имеет истинностную модальность, т.е. соответствует либо нет фактическому положению дел. Предложение, выражающее конкретное суждение, называют высказываниел^\ Суждение, имеющее модальность неопределенность, таы^ш,т неопределенным; так же 
именуют соответствующее ему предложение. Поскольку не любое суждение - конкретное, то и не любое предложение, выражающее суждение, - высказывание. В предыдущих абзацах приведены примеры истинных и ложных высказываний, а также неопределенных предложений 
ЛМЯ. Они свидетельствуют о том, что в математических текстах употребляют предложения различных видов. 

2. По составу различают простые и сложные суждения. В логике простым называют суждение, отражающее связь между двумя 
понятиями [24, с. 8], а сложным - «составленное» из простых по 
вполне определенным правилам. Обычно так же именуют и реализующие их предложения, в частности, высказывания. Так, предложе
15