Дискретная матеметика и формальные системы : вводная лекция

 

 
Кафедра автоматизированных систем управления 

Ю.Ю. Прокопчук, А.И. Широков 

 

 

 

 

Рекомендовано редакционно-издательским 
советом института в качестве учебного пособия 

ДИСКРЕТНАЯ МАТЕМАТИКА И 

ФОРМАЛЬНЫЕ СИСТЕМЫ 

Вводная лекция 

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

МОСКВА 2001 

№ 741 

 

УДК 510(022) 
ПР 68 

Прокопчук Ю.Ю., Широков А.И. Дискретная матеметика и 
формальные системы: Вводная лекция. – М.: МИСиС, 2001. 17 с. 

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

 Московский государственный 

институт стали и сплавов 
(Технологический университет) 
(МИСиС) 2001 

 

СОДЕРЖАНИЕ 

1. О 
причинах 
разделения 
науки 
на 
отдельные научные дисциплины ................................................ 4 
2. О математической науке ......................................................... 6 
Методы, используемые в математике .................................... 6 
Математические предметы ..................................................... 9 
Математический язык ........................................................... 12 
Заключение ............................................................................. 14 
Литература .................................................................................. 16 

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

1. О ПРИЧИНАХ РАЗДЕЛЕНИЯ НАУКИ 
НА ОТДЕЛЬНЫЕ НАУЧНЫЕ 
ДИСЦИПЛИНЫ 

В процессе развития человечество получало и накапливало 
продукты своей общественно-трудовой и мыслительной деятельности. Между разрозненными явлениями устанавливались закономерные связи, отдельные группы фактов объединялись в одно целое. Человечество становилось обладателем определенной информации о 
внешнем мире и о себе. Постепенно эта информация складывалась в 
систему упорядоченных знаний, истинность которых проверялась и 
уточнялась самыми различными способами в частности, в процессе 
общественно-производственного и научного развития. Первоначально все знания были собраны в науке о мировоззрении – философии, 
которой непосредственно предшествовала самая древняя форма мировоззрения – религия. Философия зародилась на заре цивилизации в 
древней Индии, Китае, Египте; своей классической формы она впервые достигла в древней Греции. Возникновение философии исторически совпадает с появлением зачатков научного знания, формированием потребностей в теоретическом исследовании. 
По мере накопления специальных научных знаний, выработки особых приемов исследования началось размежевание отдельных 
областей теоретического и прикладного знания. Это размежевание 
вызвано рядом причин. Вот некоторые из них. 
• 
Любая осмысленная деятельность человека направлена на 
достижение определенной цели – его осознанной потребности. При 
этом обычно важна не вся информация о каком-то объекте или процессе, а только ее некоторая часть. Эту часть можно получить при 
помощи отдельной науки (или отдельных наук), не прибегая ко всем 
научным дисциплинам или различным разделам одной научной дисциплины. 

• 
Вторая причина связана с первой и состоит в том, что с 
экономической точки зрения заниматься всесторонними исследованиями какого-либо объекта или процесса довольно дорого, и не всегда сразу очевидно, как все результаты этих исследований можно 
использовать в практической деятельности, быстро компенсируя тем 
самым затраченные усилия и ресурсы. 
• 
Конкретные связи между различными сторонами одного 
и того же объекта обычно очень сложны. Поэтому их выявление требует высокого уровня знаний. Например, связь между “математической” характеристикой тела – его координатами на земной поверхности и “физической” – его весом была установлена только в XVIII в., 
когда было выяснено, что Земля сплющивается к полюсам. Установлению этой связи предшествовали исследования математиков по 
сферической геометрии и физиков по установлению формы Земли и 
методам точного взвешивания. 

2. О МАТЕМАТИЧЕСКОЙ НАУКЕ 

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

Методы, используемые в математике 

Слово “метод” произошло от греческого methodos, что в буквальном переводе означает “путь к чему-либо”. Под методом в самом широком смысле слова понимают способ достижения цели, 
определенным образом упорядоченную деятельность [1, с. 214]. В 
более узком смысле слово “метод” обозначает совокупность приемов, способов, алгоритмов, которые, будучи применены к какимлибо объектам, ведут к определенным результатам. Существуют методы, используемые во всех сферах человеческой деятельности. Это, 
во-первых, методы философии – науки о наиболее общих закономерностях природы, общества и мышления, и, во-вторых,  – методы логики. На последних мы остановимся более подробно. Логика – это 
наука о приемлемых способах рассуждения. И, конечно, положения 
любой научной дисциплины, если они имеют какую-то ценность, не 
должны противоречить законам логики. 
С давних времен логика наряду с математикой считается самой достоверной и точной наукой. Но по существу логика является 
основой всех наук, в том числе и математики. И как раз в математике 
ее роль особенно велика. Дело в том, что в отличие от эмпирических 

наук (физики, химии, биологии), в которых для проверки истинности 
каких-либо гипотез обращаются к наблюдениям или ставят эксперименты, все математические доказательства носят чисто логический 
характер. Так, многократно убедившись на конкретных примерах, 
что если между положительными числами a, b и c существует связь 
вида a2 + b2 = c2, то из отрезков прямой с длинами a, b и c можно построить прямоугольный треугольник с катетами длиной a и b и гипотенузой длиной c, мы еще не можем утверждать, что доказали геометрическую теорему (обратную теореме Пифагора). И хотя чаще 
всего именно отдельные результаты подталкивают нашу интуицию к 
обобщениям, только строгие логические обоснования превращают 
эти обобщения в утверждения, истинность которых не вызывает сомнений. Приведем несколько основных определений. 
Среди многих объектов, которые изучаются в логике, одно из 
первых мест занимают так называемые логические формы мышления, 
т. е. способы построения, выражения и связи мыслей и частей мысли 
различного конкретного содержания, осуществляющиеся в процессе 
мышления. Основными из них являются понятие, суждение и умозаключение. 
Понятие – форма человеческого мышления, в которой отражаются признаки предметов. Понятия в языке выражаются словами 
(портфель, трапеция), или словосочетаниями (ураганный ветер, параллельные прямые). Среди различных характеристик понятия 
наиболее важными являются его объем и содержание. Под объемом 
понятия имеют в виду класс отраженных в нем предметов, а под содержанием – совокупность признаков, по которым произведено выделение предметов в данное понятие. Например, объемом понятия 
“число 6” является класс множеств, каждое из которых состоит из 
шести хорошо отличимых друг от друга предметов, элементов; а содержанием – набор следующих свойств: 
являться количественным показателем любого множества из 
своего объема; 
принадлежать первому десятку элементов натурального ряда; 
делиться без остатка на 2 и 3; 
равняться сумме всех своих делителей, отличных от него самого (6 = 1 + 2 + 3), т. е. как говорят в теории чисел, быть совершенным, и другим. Предельно широкие понятия, в которых отражены 
наиболее общие и существенные свойства и связи предметов и явлений, называются категориями. Категории не определяются строго 
через другие понятия, а только описываются, поясняются при помо

щи иных категорий или иллюстрируются примерами. Так, в философии категориями являются такие понятия как бытие, материя, сознание; в логике – понятие, метод, определение, доказательство; в 
«наивной» теории множеств – множество, вектор; в физике – путь, 
время, инерция; в химии – химический элемент, химическая связь. 
Суждение – это форма мышления, в которой что-то утверждается или отрицается относительно предметов и явлений, их 
свойств и связей, и которая обладает свойством быть истинной либо 
ложной. Языковыми выражениями суждений являются главным образом повествовательные предложения. Суждения могут быть простыми и сложными. Например, предложение: “Данная точка равноудалена от концов данного отрезка” выражает простое суждение, а 
предложение: “Если данная точка равноудалена от концов данного 
отрезка, то она лежит на перпендикуляре, проведенном через его середину” – сложное. Та часть суждения, которая отображает предмет 
мысли, называется субъектом суждения и обозначается буквой S (от 
лат. Subjectum – субъект, подлежащее), а та часть суждения, которая 
отображает то, что утверждается (или отрицается) о субъекте, называется предикатом суждения и обозначается буквой P (от лат. 
Praedicatum – сказанное, сказуемое). Так, субъектом вышеприведенного простого суждения будет данная точка, а предикатом – свойство 
точки быть равноудаленной от концов данного отрезка. Символически простое суждение можно изобразить так: “S есть P“, где слово 
“есть” (или “суть”, когда речь идет о многих предметах), называется 
связкой. Существуют суждения и других конструкций. 
Умозаключение – форма мышления, посредством которой из 
одного или нескольких суждений, называемых посылками, мы по 
определенным правилам вывода получаем новое суждение, называемое заключением. Приведем два примера умозаключений. 
• 
Все металлы – простые вещества. 
Литий – металл. 
-------------------------------------- 
Литий – простое вещество. 
• 
Действительные числа разделяются на положительные, 
отрицательные и нуль. 
Данное число равно нулю. 
-------------------------------------- 
Данное число не является ни положительным, ни отрицательным. 

Кроме привлечения общенаучных методов, любая наука разрабатывает и применяет к тем предметам, которые она изучает, свои 
методы. Математика не является исключением. В качестве примера 
приведем метод математической индукции, позволяющий на основе 
истинных частных суждений делать умозаключения более широкого 
характера [2, с. 5]. Другой пример –набор алгоритмов, позволяющих 
из изображений таких математических объектов как числа, векторы и 
т. д., получать изображения их суммы, произведения и т. п. Характерной чертой математических методов является то, что они могут 
быть использованы во всех случаях жизни, где установлено наличие 
тех или иных математических структур, способы оперирования с которыми известны из математики. Так, встречаясь с числами, мы можем оперировать с ними как с математическими объектами, т. е. их 
складывать, умножать, делить и т. д. Именно так и поступают, 
например, инженеры, бухгалтеры, продавцы и люди других профессий, имеющие дело с числами в своей практической деятельности. 

Математические предметы 

Теперь мы попытаемся ответить на вопрос: что изучает математика? Отметим, что в основе каждой научной дисциплины, в том 
числе и математики, лежит принцип “сознательно неполного знания”, известный еще выдающемуся мыслителю древней Греции Аристотелю (384-332 гг. до н. э.). Этот принцип состоит в том, что определенные стороны изучаемых явлений, объектов умышленно и систематически игнорируются, но зато тем сторонам, которые данная 
научная дисциплина считает для себя наиболее важными, уделяется 
особое внимание. Можно сказать, что специфический предмет каждой отдельной науки – не ограниченная сфера явлений окружающего 
нас мира, а вся реальность, рассматриваемая под определенным углом, со своей точки зрения. Какие же аспекты действительности изучает математика? 
Процитируем относящиеся к ней высказывания некоторых 
выдающихся мыслителей прошлого. Аристотель в труде “Метафизика” писал, что математик исследует “объекты, полученные посредством отвлечения. Он производит эти рассмотрения, сплошь утратившие все чувственные свойства, например, тяжесть и легкость, 
жесткость и противоположное ей, далее – тепло и холод, и все 
остальные чувственные противоположности, а сохраняет только ко

личественную определенность и непрерывность, у одних – в одном 
измерении, у других – в двух, у третьих – в трех, и рассматривает их, 
поскольку они количество и непрерывно, а не с какой-либо другой 
стороны, и в одних случаях рассматривает взаимное положение 
предметов и свойственное ему, в других – их соизмеримость и несоизмеримость, в третьих – их отношения...”. Знаменитый немецкий 
философ Г. В. Ф. Гегель (1770-1831) в своей “Энциклопедии философских наук” характеризует предмет математики так: “Математика 
имеет дело с абстракциями числа и пространства, но последние все 
еще представляют собой нечто чувственное, хотя это чувственное 
абстрактно и не имеет наличного бытия”. Классик материализма 
Ф. Энгельс (1820-1895) в своем труде “Анти-Дюринг”, вышедшем в 
свет в 1878 г., определил математику как науку, которая «занимается 
исследованием пространственных форм и количественных отношений действительного мира», тем самым указав как на те стороны реальных объектов, которые изучает математика, так и на ее происхождение из практической деятельности людей. 
Объекты, изучаемые в математике, как, впрочем, и в любой 
другой науке, представляют собой не отдельные конкретные предметы материального мира: деревья, звезды, люди и т. д., а понятия, т. е. 
предметы идеального, духовного мира, развитые человечеством в 
процессе практической и сопровождающей ее умственной деятельности. Многие понятия имеют свои близкие или отдаленные прообразы, поверхностные или более глубокие корни в мире материальных 
вещей, и являются интеллектуальными отображениями, образами, 
созданными посредством таких логических методов, как, например, 
абстракция, обобщение, идеализация и т. д. 
В данный момент у нас нет необходимости описать все предметы, изучаемые в математике. По-видимому, этого нельзя сделать в 
принципе, поскольку они непрерывно появляются, переходят друг в 
друга, сливаются, разъединяются и исчезают. Однако многие из 
устоявшихся, основных предметов мы будем постепенно вводить в 
рассмотрение и анализировать. Пока же, полагаясь на известный 
уровень математической культуры, обусловленный знаниями, полученными в средней школе, ограничимся небольшим набором примеров. 
Как известно, существуют самые различные математические 
объекты: те или иные числа, точки, линии, геометрические фигуры и 
тела, множества, элементарные алгебраические и тригонометрические функции, алгебраические операции, операции дифференциро

вания и интегрирования и т. п. Тот или иной раздел математики 
определяется главным образом тем, какие из математических объектов выбраны в нем в качестве основных, наиболее важных. Но некоторые из них более или менее широко используются (чаще всего в 
качестве вспомогательных) и в других разделах. Так, целые числа 
применяются в очень многих разделах математики, но являются основным предметом изучения в разделе “Теория чисел”. 
Заметим, что хотя математические объекты интересны для 
нас и сами по себе, но не менее важны и свойства, которыми они обладают, и отношения, в которых они находятся, а также логические 
связи между ними. Дело в том, что эти свойства, отношения и связи 
являются, хотя и абстрактными, но в большой степени верными отражениями соответствующих объективных свойств, отношений и 
связей между “математическими сторонами” предметов реального 
мира, т. е., сторонами, рассматриваемыми в конечном счете с точки 
зрения “количественных отношений и пространственных форм”. 
Примером отношения между математическими объектами 
может служить отношение естественного порядка между натуральными числами: 2 ≤ 3, 3 ≤ 4 и т. д. Примером логической связи является свойство транзитивности для отношения порядка между натуральными числами, которое формулируется так: если x, y, z – натуральные числа, то из неравенств x ≤ y и y ≤ z следует неравенство 
x ≤ z. Отношения между математическими объектами и логические 
связи между ними также являются предметами, изучаемыми в математике. 
С момента первой публикации работы “Анти-Дюринг” прошло более ста лет. В течение этого периода и в настоящее время математическая наука, анализируя и обобщая простейшие пространственные формы и количественные отношения объектов действительности, создавала и создает на их базе новые понятия и устанавливает между ними новые связи, куда первоначальные понятия и 
связи входят как очень важный, но частный случай. В результате 
многочисленных исследований удалось установить, что единственными математическими объектами являются так называемые математические структуры – известные обобщения пространственных 
форм и количественных отношений, о которых шла речь в определении Ф. Энгельса. По сути математические структуры – это конструкции, построенные из множеств, элементы которых обладают фиксированными свойствами и находятся в известных отношениях. Со