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

№1775 

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

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

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

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

Учебное пособие 
Часть II 

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

Под редакцией проф. А.Г. Дъячко и проф. Л.П. Рябова 

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

МОСКВА 2002 

УДК 519.45 
П78 

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

П78 
Дискретная математика: Элементы логико-математического 

языка: Учеб. пособие. Ч.П/ Под ред. проф. А.Г. Дьячко и 
проф. Л.П. Рябова- М.: МИСиС, 2002. - 149 с. 

Одним из средств отражения внутреннего и внешнего мира человека является естественный язык. Описание «мира математических предметов», т.е. 
системы, состоящей из математических объектов, их свойств и отношений 
между ними, а также логических связей между двумя последними, совершается на формализованном так называемом логико-математическом языке 
(ЛМЯ). В данном пособии представлена вторая часть раздела «Элементы логико-математического языка» учебной дисциплины «Дискретная математика». Рассмотрены 
главным 
образом семантические 
аспекты логикоматематического языка, относящиеся к интерпретациям его выражений. 

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

© Московский государственный институт 
стали и сплавов (Технологический 
университет) (МИСиС), 2002 

ОГЛАВЛЕНИЕ 

От авторов 
7 

Введение 
8 

Глава III. Семантические аспекты логико-математического языка 
9 

§ 1. Значения константных выражений 
9 

1. Языковые и основные значения константных выражений 
9 

2. Значность константного выражения 
11 

3. Отношение синонимии между константными выражениями и 
его свойства 
13 

4. Истинностные значения пропозициональных формул 
и константных соотношений 
16 

Упражнения 
18 

Примечание 
21 

§ 2. Значения выражений 
24 

1. Языковые и основные значения термов и элементарных 
соотношений 
24 

2. Интерпретация неэлементарных соотношений 
27 

3. Таблицы истинности для пропозициональных формул 
29 

4. Определенность выражения при интерпретации 
31 

5. Различение термальных и высказывательных форм 
32 

Упражнения 
33 

Примечание 
35 

§ 3. Виды вхождений переменных в выражение 
36 

1. Свободные и связанные переменные выражения 
36 

2. Свободные и связанные вхождения переменных в 
выражение 
39 

3. Зависимость выражения от переменных. Существенные 
и фиктивные переменные выражения 
40 

Упражнения 
42 

Примечание 
43 

§ 4. Отношение синонимии между выражениями 
43 

1. О синтаксическом и семантическом подобии выражений 
43 

2. Отношение синонимии между одноместными выражениями....44 
3. Отношение синонимии между многоместными выражениями 
и его свойства 
46 

4. Основные равносильности 
49 

5. Тождественно истинные, тождественно ложные, выполнимые 
и опровержимые соотношения. Важнейшие тождественно 
истинные формулы 
51 

3 

Упражнения 
52 

Примечание 
54 

Приложение 1. Зависимость выражения от переменных 
различных родов 
54 

Упражнения 
58 

Примечание 
58 

§ 5. Области задания, определения и значений выражений 
59 

1. Области, характеризующие константные выражения 
60 

2. Области, характеризующие логические и математические 
переменные 
60 

3. Области, характеризующие одноместные термы и 
элементарные соотношения 
61 

4. Области, характеризующие многоместные термы и 
элементарные соотношения 
64 

5. Истинностные области элементарных соотношений 
66 

6. Области, характеризующие неэлементарные соотношения 
67 

Упражнения 
69 

Примечание 
70 

Приложение 2. О независимости, совместности и совместимости 
свойств 
72 

1. Зависимость и независимость 
72 

2. Совместность, или непротиворечивость 
75 

3. Совместимость 
75 

Упражнения 
75 

Примечание 
78 

Глава IV. Квантификация соотношений 
79 

§ 1. Кванторы общности и существования 
79 

1. Об операциях связывания переменных выражения 
79 

2. Универсальная квантификация одноместных соотношений 
80 

3. Экзистенциальная квантификация одноместных соотношений... 81 
4. О зависимости соотношения от переменных 
82 

Упражнения 
83 

Примечание 
85 

Приложение 1. Операции квантификации как обобщения 
операций конъюнкции и дизъюнкции 
86 

Упражнения 
87 

Примечание 
87 

§ 2. Квантификация многоместных соотношений 
88 

1. О числе переменных многоместного соотношения 
88 

2. Универсальная квантификация многоместных соотношений.... 89 

4 

3. Экзистенциальная квантификация многоместных 
соотношений 
90 

4. Многократная квантификация многоместных соотношений 
91 

Упражнения 
92 

Примечание 
94 

§ 3. Свойства операций квантификации и их связи с другими 
коннекторными операциями над соотношениями 
94 

1. Свойства операций квантификации 
94 

2. Связь между операциями квантификации и отрицанием 
96 

3. Связь между операциями квантификации и дизъюнкцей 
96 

4. Связь между операциями квантификации и конъюнкцией 
98 

5. Связи между операциями квантификации и импликацией 
99 

6. Связь между операциями квантификации и эквивалентностью ..100 
Упражнения 
101 

Примечание 
103 

§ 4. Типовые, или ограниченные кванторы 
104 

1. Определение и примеры типовых кванторов 
104 

2. Свойства операций ограниченной квантификации и их связи 

с другими коннекторными операциями 
105 

Упражнения 
107 

Примечание 
107 

Глава V. Элементы алгебры логики 
108 

§ 1. Основные понятия и определения 
108 

1. Предмет алгебры логики 
108 

2. Высказывательные формы 
109 

3. Простые высказывания алгебры логики и простые 
предложения естественного языка 
109 

4. Сложные предложения естественного языка и сложные 
высказывания алгебры логики 
111 

5. О языке алгебры логики 
111 

6. О некоторых логических аспектах построения сложных 
высказываний 
112 

7. Основные операции над высказываниями алгебры логики 
113 

Упражнения 
115 

Примечание 
117 

§ 2. Синтаксические и прагматические аспекты языка 

алгебры логики 
118 

1. Определение формул языка алгебры логики 
118 

2. Подформулы 
119 

3. Кодирование формул 
121 

5 

4. Бесскобочное кодирование формул алгебры логики 
123 

Упражнения 
127 

Примечание 
129 

§ 3. Семантические аспекты языка алгебры логики 
130 

1. Таблица истинности для формулы алгебры логики 
130 

2. Отношение равносильности между формулами 
132 

3. Тождественно истинные, тождественно ложные, выполнимые 

и опровержимые формулы 
133 

4. Основные равносильности 
134 

5. О выразимости одних формул через другие 
135 

Упражнения 
137 

Примечание 
139 

§ 4. Применения результатов алгебры логики 
140 

1. Применения в логике 
140 

2. Применение в теории релейно-контактных схем 
142 

Упражнения 
144 

Примечание 
146 

Литература 
147 

6 

Памяти 

Александра Сергеевича 

Урмаева 

От авторов 

Данное пособие авторы посвящают памяти Александра Сергеевича Урмаева, профессора Московского государственного института стали и сплавов (МИСиС), безвременно 
скончавшегося 
16 декабря 1976 г. на 41-м году жизни. 

А.С. Урмаев работал на кафедре инженерной кибернетики 
(КИК), руководимой профессором СВ. Емельяновым, с момента ее 
основания в 1966 г. в должности заместителя заведующего кафедрой. 
К этому времени относится появление в МИСиС аналоговой и цифровой вычислительной техники (ВТ). Помимо большой организаторской, преподавательской и методической работы А.С. Урмаев руководил секцией Методического совета МИСиС «Применение ВТ в 
учебном процессе», которую он создал в 1970 г. и которой бессменно 
руководил до 1976 г. Благодаря его работе в МИСиС, где до 1966 г. 
не было современной вычислительной техники, в учебные планы 
всех специальностей были включены и стали регулярно проводиться 
теоретические и практические занятия по указанным курсам. 
А.С. Урмаев создал несколько общесоюзных учебников и учебных 
пособий, которые вышли в издательстве «Паука». 

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

7 

ВВЕДЕНИЕ 

в настоящем пособии, как и в руководстве [27], повествование ведется в основном в той же форме, что и на лекциях. Глава III 
посвящена главным образом интерпретациям выражений. В нее 
включены, в частности, вопросы синонимии выражений (§ 4) и описание теоретико-множественных конструкций, их характеризующих 
(§ 5). В гл. IV после введения основных понятий (§§ 1 и 2) изучаются 
свойства операций квантификации и их связи с другими коннекторными операциями (§§ 3 и 4). Главным предметом изучения в гл. V 
служат логические аспекты языкового понятия высказывание, т.е. 
лингвистического образа логического понятия конкретное суждение 
[27, гл. I, § 2, п. 2]. Материал этой главы хотя и имеет общие черты с 
материалом, излагаемым в гл. I - IV, но в основном носит самостоятельный характер. Последнее связано с тем, что в учебных планах 
некоторых специальностей присутствует дисциплина «Математическая логика и теория алгоритмов», но нет дисциплины «Дискретная 
математика». Именно в этом случае гл. V служит основным учебным 
пособием для студентов указанных специальностей. Приведенные в 
книге упражнения с подробным разбором решений некоторых из них 
служат базой для проведения практических, а разносторонние примечания - семинарских занятий и курсовых работ. При ссылках на 
I часть пособия [27] указываются ее главы, параграфы и пункты. 

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

Авторы выражают свою признательность О.А. Алещенко и 
М.С. Кузьмину, немало способствовавшим улучшению изложения. 

8 

Глава III. СЕМАНТИЧЕСКИЕ АСПЕКТЫ 
ЛОГИКО-МАТЕМАТИЧЕСКОГО ЯЗЫКА 

в гл. I и II мы занимались следующими синтаксическими и 
прагматическими вопросами ЛМЯ (гл. I, § 2, п. 4), относящимися в 
основном к понятию выражение и его видам: термам и соотношениям (гл. II, § 4, п. 2): а) из каких видов исходных имен состоят выражения (гл. I, § 3, п. 1); б) что представляют собой эти имена (гл. I, 
§§ 4 и 5); в) как обозначаются и вводятся в текст выражения (гл. II, 
§ 1, п.п. 1 и 2); г) как классифицируются выражения и их виды в зависимости от вхождения или невхождения в них переменных (гл. II, 
§ 1, п. 4); д) как формально строятся термы и соотношения из символов различных родов (гл. II, §§ 2 - 4), а также некоторыми попутными вопросами, в частности, прагматическими правилами упрощения 
записи выражений (гл. II, § 5, п.п. 1 и 2). В этой главе мы начнем 
знакомить читателя с некоторыми семантическими аспектами выражений, главным образом -их з н а ч е н и я м и . 

§ 1. Значения константных выражений 

1. Языковые и основные значения 
константных выражений 

С константными выражениями (кн-выражениями), видами 
которых являются термальные и высказывательные константы (тконстанты и вс-константы) (гл. II, § 4, п. 3), связывают несколько 
з н а ч е н и й ^ Одни значения присущи всем кн-выражениям, а другими может обладать один их вид и не обладать иной. Рассмотрим 
эти значения. 

ЯзыковъЫ значением кн-выражения с ч и т а ю т 
его само. 
Таким образом, любое кн-выражение имеет языковое значение. Значения кн-выражения, отличные от языкового, н а з ы в а ю т основными. Для каждого из видов кн-выражений мы рассмотрим в этой главе 
по одному основному значению. 

Денотатом, или предметным {истинностным) значением, 
т-константы (соответственно, вс-константы) называют тот объект, 

9 

который она обозначает (соответственно, ее истинностную 
модальность, т.е. одну из модальностей: истина, ложь (гл. I, § 2, п. 2)). Таким образом, указанные основные значения разных видов кнвыражений различны (гл. I, § 2, примеч. 4). Иерархия введенных понятий ЛМЯ представлена схемой древесной структуры 
[11, с. 149] 
на рис. III. 1. 

Длявысказывательных констант модальность 

Рис. III. 1 

Пример 1. 
1. Языковыми значениями т-констант Вщ, 10», VIII, 2^ log2256, 
(sm^30°)^ 10-2, 3+5 и З5+1О5 являются они сами, а их общим денотатом - число 
восемь. 

2. Языковыми значениями элементарных вс-констант (гл. II, § 3, п. 1): 
(1) 3 < 4; (2) 2-2 = 4; (3) во всяком треугольнике два угла- острые; (4) 1 < 0; 
(5) 2 + 2 = 5; (6) в любом треугольнике один из углов - прямой служат они сами. 
Основным значением каждого из высказываний (1) - (3) является модальность истина, а высказываний (4) - (6) -ложь. 

Замечание. Существуют такие кн-выражения, об основных значениях которых установлено немногое, главным образом по двум следующим 
причинам: 

1) известно, вещами какого рода являются эти значения, и ясно, что 
они существуют, но наши интеллектуальные, в частности технические, возможности не позволяют нам знать (по крайней мере, в настоящее время), 
какими конкретными объектами они являются. Такие положения называют 
неопределенностями 1-го рода; 

2) основные значения каких-то кн-выражений пока не определены 
теоретически, и поэтому- и практически. Иными словами, до настоящего 
времени (2002 г.) не узнали, либо не договорились, не условились, какие объекты считать основными значениями этих кн-выражений. Такие ситуации называют неопределенностями 2-го рода. 

10