Практикум по математическим основам информатики. Ч. 2. Введение в математическую логику

московский 

ГОСУДАРСТВЕННЫЙ 
ГОРНЫЙ 
УНИВЕРСИТЕТ 

РЕДАКЦИОННЫЙ 
С
О
В
Е
Т 

Председатель 

Л.А. 
ПУЧКОВ 

Зам. председателя 

ЛХ. 
ГИТИС 

Члены 
редсовета 

И В. ДЕМЕНТЬЕВ 

АЛ. ДМИТРИЕВ 

Б.А. КАРТОЗИЯ 

М.В. КУРЛЕНЯ 

В.И. ОСИПОВ 

Э.М. СОКОЛОВ 

К.Н. ТРУБЕЦКОЙ 

В В. ХРОНИН 

В.А. ЧАНТУРИЯ 

Е.И. ШЕМЯКИН 

ИЗДАТЕЛЬСТВО 
МОСКОВСКОГО 
ГОСУДАРСТВЕННОГО 
ГОРНОГО УНИВЕРСИТЕТА 

ректор 
МГГУ, 
чл.-корр. 
РАН 

директор 
Издательства 
МГГУ 

академик 
РАЕН 

академик 
РАЕН 

академик 
РАЕН 

академик 
РАН 

академик 
РАН 

академик 
МАН 
ВШ 

академик 
РАН 

профессор 

академик 
РАН 

академик 
РАН 

А.Л. Мейлахс 

ИМИ 

Ч А С Т Ь 2 

Введение 
в м а т е м а т и ч е с к у ю 
л о г и к у 

А 

ПО МАТЕМАТИЧЕСКИМ 
О
С
Н
О
В
А
М 

ИНФОРМАТИКИ 

Допущено 
Учебно-методической 
комиссией по 
специальности 
«Управление и информатика 
в технических 
системах» 
в качестве 
методических 
указаний для студентов 
вузов, 
обучающихся по направлению 
подгот05"М инженеров 651900 
«Автоматизации 
и управление» 
специальности 
210100 
«Управление и информатика 
в технических 
системах» 
и направлению 
подготовки 
бакалавров 
550200 
«Автоматизация 
и 
управление» 

МОСКВА 

ИЗДАТЕЛЬСТВО МОСКОВСКОГО 
ГОСУДАРСТВЕННОГО ГОРНОГО 
У Н И В Е Р С И Т Е Т А 

2004 

УДК 519.6:622 
ББК 22.12 
М41 

Экспертиза 
проведена 

Учебно-методической 
комиссией по специальности 
210100 
«Управление 
и информатика 
в технических 
системах» 
Московского государственного 
горного 
университета 
(выписка из протокола № 1 от 05.09.2003) 

Книга 
соответствует 

«Гигиеническим 
требованиям 
к изданиям 
книжным 
для 
взрослых 
СанПиН 
1.2.1253—3», 
утвержденным 
Главным 
санитарным врачом России 30 марта 2003 г. 

- Мейлахс А.Л. 

М 41 
Практикум по математическим основам информатики: 
Метод, указания. — М.: Издательство Московского государственного горного университета, 2004. — Ч. 2: Введение 
в математическую логику. — 73 с : ил. 

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

Для студентов высших учебных заведений, обучающихся по направлению 
подготовки инженеров 651900 «Автоматизация и управление» специальности 
210100 «Управление и информатика в технических системах» и направлению 
подготовки бакалавров 550200 «Автоматизация и управление». 

УДК 519.6:622 
ББК 22.12 

© А.Л. Мейлахс, 2004 
© Издательство МГГУ, 2004 
© Издательство «Горная книга», 2004 
© Дизайн книги. Издательство МГГУ, 
2004 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 4. 

«ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ» 

Литература: [1, 4, 5, 10] 

ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ В 

ОРГАНИЗАЦИИ ЭВМ 

Наиболее низкий иерархический уровень организации ЭВМ 

- это уровень логических 
схем или уровень 
вентилей. 
Разработка и 

описание функционирования аппаратуры ЭВМ на этом уровне 

выполняется на языке математической 
логики. 
Логические и 

арифметические операции над двоичными словами, пересылки 

данных, формирование управляющих сигналов сводятся к суперпозиции элементарных логических операций, выполняемых над 

отдельными разрядами двоичных слов. Описание 
комбинационных или вентильных 
схем, вьшолняющих эти функции, строится 

на основе логических 
формул 
и таблиц 
истинности. 
Понимание 

принципа устройства наиболее низкого аппаратного уровня организации ЭВМ требует знакомства с основными понятиями и языком математической логики, а также практических навыков работы с логическими формулами и таблицами истинности. 

Математическая логика применяется и на более высоких 

уровнях организации вычислительного процесса в ЭВМ. Например, на уровне машинных команд знание методов математической логики позволяет понять, как запрограммировать ЭВМ для 

выполнения «умозаключений» и решения логических задач, на 

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

условие для отбора необходимых данных. 

1 

— 
J 
— 

ВЫСКАЗЫВАНИЯ 

Повествовательное предложение, для которого имеет смысл 

говорить, что оно истинно или ложно, называют 
высказыванием. 

Истинностные значения высказываний обозначают 
символами 

«И» или «1» - истина, «Л» или «О» - ложь. Будем использовать 

символы «О», «1», что облегчит переход от логики 
высказываний 
к 

формальной 
алгебре логики. 
Высказывание можно рассматривать 

как величину принимающую значения «О» или «1». 

Высказывания обозначают буквами латинского алфавита А, 

В, С,... 
Y, Z, а,Ь, с, ... у, г, аналогично обозначениям математических переменных. Буквенные обозначения высказываний именуют пропозициональными 
переменными. 
Запись 

а: «А», 

читается так: переменная а является высказыванием, чья словесная формулировка звучит как «А». 

• Примеры 

1. Предложение: «Число 5 - нечетное» является высказыванием, его истинностное значение - истина, «1». 

2. Предложение: «Сумма чисел 5 и 9 есть число 16» является 

высказыванием, его значение - ложь, «О». 

3. Предложение: «Пусть всегда будет солнце!» не является 

высказыванием в силу определения. 

4. Предложение: «х + 5 > 3» не является в строгом смысле 

высказыванием, однако, при указании значения х, обращается в 

высказывание. Если х = 4, исходное предложение формулируется 

«4 + 5 > 3». Значение полученного высказывания: «1». 

5. Высказывание А: «Длина окружности единичного диаметра равна я» имеет значение А = 1. 

6. Высказывание В: «Сегодня хорошая погода» сформулировано неудачно. Определить значение В затруднительно, посколь
- 4 

ку л и диллши иыхь сделано категорично: лиоо п = и, лиоо а = 1, 

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

7. Высказывание С: «Сегодня солнечно, нет туч, не идет 

дождь, дует легкий ветерок» сформулировано более определенно 

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

8. Предложение: «Предмет имеет круглую форму» будет высказыванием, если указать, к какому предмету оно применяется. • 

Высказывание в последнем примере требует «объектной» 

подстановки. Связанные с такими высказываниями понятия заимствованы из теории множеств. 

Множество объектов Е, к которым применяется высказывание, именуется универсальным 
или областью 
определения 
высказывания. 
Подмножество АаЕ 
универсального множества, образованное объектами, для которых высказывание а имеет истинное 

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

• Примеры 

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

а) а: «Сумма цифр в записи числа равна 5». Универсальное 

множество согласно условию задачи: Е = { 1 , 2, 3, ... 48, 49, 50}. 

Применяем словесную формулировку высказывания а, перебирая 

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

5, затем 14, поскольку 1 + 4 = 5, затем 23, и далее до 50. 

Ответ: {5, 14,23,32,41,50}. 

б) а: «Произведение цифр в записи числа равно 12». 

Ответ: {26, 34, 43}. 

- 5 

Рис. 1. 

2. На рис. 1 изображено множество из девяти пронумерованных объектов. На этом множестве 
определены 

высказывания: 

х: «Объект - круглый»; 

у: «Объект - квадратный»; 

г. «Объект - треугольный»; 

к: «Объект - заштрихованный»; 

т: «Номер объекта - нечетный». 

Области истинности 
высказываний - множества номеров входящих в них объектов - обозначим 

соответствующими заглавными буквами: Х= 
{ 1 , 5, 9}, Y = {2, 6, 

8}, Z = {3, 4, 7},К= 
{2, 4, 5, 6, 9}, М= 
{ 1 , 3, 5,7, 9}. 

3. На множестве объектов, описанном в предыдущем примере, определить область истинности высказывания а: «Объект 
квадратный и заштрихованный». 

Ответ: {2, 6}.И 

Из простых высказываний путем различных 
соединений 

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

«и». 

ЛОГИЧЕСКИЕ СВЯЗКИ 

Для записи составных высказываний применяются 
пропозициональные, 
или по другому, логические 
связки. 

Простые высказывания, объединенные связкой, называют 

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

определения наиболее важных логических связок. 

- 6 

Отрицанием 
высказывания х называют высказывание 

—iX, X , 

истинное тогда и только тогда, когда составляющее - ложно. 

Данная связка служит для образования составного высказывания 

из 
одного 
составляющего, 
поэтому' 
является 
одноместной 

(унарной). 
В грамматических конструкциях отрицанию соответствуют связки «не ...», «неверно, что ...». 

Конъюнкцией 
высказываний х, у называют высказывание 

X Л V, 

истинное тогда и только тогда, когда оба составляющие высказывания истинны. Кроме символа «л» для обозначения конъюнкции 

иногда применяются символы «&», «•», или используется запись 

без символа операции, как при алгебраическом 
умножении. 

Конъюнкция служит для образования составного высказывания 

из двух составляющих, поэтому является двухместной 
(бинарной) 

связкой. В грамматических конструкциях конъюнкции соответствует связка «... и ...» или подразумевающаяся одновременная истинность высказываний. 

Дизъюнкцией 
высказываний х, у называют высказывание 

xv 
у, 

ложное тогда и только тогда, когда оба составляющие высказывания ложны. Кроме символа «v» для обозначения дизъюнкции 

может применяться символ «+». Дизъюнкция является двухместной связкой, в грамматических конструкциях ей соответствует 

связка «... или ...» в значении «... или ... или оба». 

Импликацией 
высказывания - посылки 
х в высказывание 
вывод у называют высказывание 

- 7 

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

Импликация является двухместной, в грамматических конструкциях ей соответствуют связки «... влечет ...», «если 
то ...». Определение импликации не противоречит нашему естественному 

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

лжи следует что угодно! 

Эквиваленцией 
или равнозначностью 
высказываний х, у называют высказывание 

х = у , 

истинное тогда и только тогда, когда истинностные значения 

составляющих высказываний совпадают. Кроме символа «=•» для 

обозначения равнозначности могут применяться символы «<-»» и 

«~». Равнозначность является двухместной, в 
грамматических 

конструтщиях ей соответствуют связки «... равносильно ...», «... 

тогда и только тогда ...». 

Неравнозначностью 
высказываний х, у называют высказывание 

х®у, 

истинное тогда и только тогда, когда истинностные значения 

составляющих высказываний различны. Кроме символа «©» для 

обозначения равнозначности могут применяться символы «*» и 

«+». Неравнозначность является двухместной, в грамматических 

конструкциях ей соответствуют связки «... или ...» в разделительном смысле «... или ... но не оба» и «либо 
либо ...». 

- 8