Введение в математическую логику (стр. 1 )

Министерство образования Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

Институт новых информационных технологий

Государственного образовательного учреждения

высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

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

Утверждено в качестве учебного пособия

Ученым советом Государственного образовательного учреждения

высшего профессионального образования

«Комсомольский-на-Амуре государственный технический университет»

Комсомольск-на-Амуре 2003

УДК 517

ББК 22.122 я7

В 75

В 75 Введению в математическую логику.: Учебно-практ. пособие. – Комсомольск-на-Амуре: Государственное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре гос. техн. ун-т», 2003. – 61 с.

По содержанию данное пособие тесно связано с конспектом лекций [1] и является методической основой для самостоятельного изучения следующих вводных разделов математической логики и ее приложений: формулы логики высказываний и операции над ними; упрощение записи формул; доказательство равносильности, тождественной истинности и тождественной ложности формул; приведение формул логики высказываний к нормальным формам; использование формул логики высказываний в теории конечных автоматов; формулы логики предикатов и операции над ними; исследование выполнимости, истинности, ложности и равносильности формул логики предикатов, приведение формул логики предикатов к предваренной (пренексной) нормальной форме; основы исчисления высказываний и исчисления предикатов.

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

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

ББК 22.122 я7

© Государственное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2003

© Институт новых информационных технологий Государственного образовательного учреждения высшего профессионального образования «Комсомольский-на-Амуре государственный технический университет», 2003

ВВЕДЕНИЕ

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

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

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

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

Использованы следующие общепринятые обозначения:

N, Z, Q, R, C, – множества натуральных, целых, рациональных, действительных, комплексных чисел соответственно;

– множество, состоящее из элементов ;

– упорядоченный набор из элементов (-мерный вектор, -ка);

– множество таких элементов , для которых выполняется условие (свойство) .

1. ЭЛЕМЕНТЫ ЛОГИКИ ВЫСКАЗЫВАНИЙ

1.1. Высказывания и операции над ними, формулы

Сводка теории

Имена предметов называются индивидными (предметными) константами. В «грамматике» формального языка индивидные константы играют роль существительных.

Выражения, содержащие знаки «переменных» и превращающиеся в имена предметов, если вместо переменных подставить некоторые имена предметов, называются именными формами. Именные формы мы будем называть индивидными (предметными) переменными. Областью изменения индивидных переменных являются не только числа, но и совокупность любых индивидов (в частности, для нематематического языка – любые предметы или даже любые утверждения). В «грамматике» формального языка индивидные переменные играют роль местоимений.

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

Общее логико-философское определение этого понятия можно сформулировать так: высказывание – это мысленное отражение объективной связи между предметами. Оно истинно, если адекватно отражает эту связь, в противном случае – ложно. В естественном языке высказывание существует в виде повествовательного предложения. Если это предложение простое, т. е. описывает отдельный факт и не может быть разделено на более мелкие осмысленные предложения, то соответствующее высказывание называется простым.

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

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

Будем интерпретировать логические связки как функции, определенные на так называемом булевом (по имени английского математика Дж. Буля) множестве В = {И, Л}, {«истина», «ложь»} или {1, 0}, со значениями в этом же множестве следующим образом:

отрицание	, ;
конъюнкция	1&1 = , ;
дизъюнкция	, ;
импликация	, ;
эквивалентность	.

Действие этих операций (связок) можно представить в виде символических таблиц, которые будем называть таблицами истинности данных логических операций. Например, для операции отрицания таблица истинности выглядит так:

1	0
0	1

Именно эту таблицу (ее надо читать по строкам: «если =1, то = = 0», т. е. одновременно истинно и ложно) мы фактически и приняли в качестве определения операции отрицания.

В технических приложениях операцию отрицания называют инверсией. Эту операцию можно условно проиллюстрировать работой следующей электрической цепи (рис. 1.1).

Действие в цепи: если = 1, то кнопка нажата, цепь разомкнута и лампочка не горит, т. е. = 0; если = 0, то цепь замкнута и лампочка горит, т. е. = 1.

Таблица истинности для операции конъюнкции, соответствующей союзу «и» естественного языка, выглядит следующим образом:

A	В	A^B
1	1	1
1	0	0
0	1	0
0	0	0

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

Таблица истинности для операции дизъюнкции (аналог в естественном языке – союз «или») выглядит следующим образом:

А	В	AÚB
1	1	1
1	0	1
0	1	1
0	0	0

В технических приложениях операцию дизъюнкции называют логическим сложением. Простейшая электрическая цепь, иллюстрирующая эту операцию, имеет вид ( рис. 1.3).

В отдельных технических дисциплинах (а иногда и в математических теориях) используют и исключающее «или», приводящее к операции «альтернативная дизъюнкция», которую обозначают «+2» (а также «», «»). Примером такой операции в математике является сложение по модулю 2. Результаты операций A Ú B и A B отличны лишь в одной ситуации: когда A = 1 и B = 1 одновременно.

Таблица истинности для операции альтернативной дизъюнкции выглядит следующим образом:

А	В	AB
1	1	0
1	0	1
0	1	1
0	0	0

Эту операцию можно проиллюстрировать работой следующей электрической цепи (рис.1.4).

Таблица истинности для операции импликации (ближайший аналог в естественном языке – оборот «если..., то...») такова:

A	В	A B
1	1	1
1	0	0
0	1	1
0	0	1

Соответствующая электрическая цепь имеет вид (рис. 1.5).

Приведем таблицу истинности для эквивалентности (соответствует оборотам естественного языка типа «тогда и только тогда, когда...», «для того, чтобы..., необходимо и достаточно...» и др.):

A	В	A B
1	1	1
1	0	0
0	1	0
0	0	1

Электрическая цепь, реализующая операцию эквивалентности, имеет вид (рис. 1.6)

Понятие формулы алгебры логики (высказываний) определим следующим образом:

1) пропозициональная переменная есть формула;

2) если А и В – формулы, то

– формулы;

3) других форм, нет.

Подформулой формулы А называется любая ее часть, которая сама является формулой.

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

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение 1 (0).

Формула называется тождественно-истинной, или тавтологией (тождественно-ложной, или противоречием), если эта формула принимает значение 1 (0) при всех наборах значений переменных.

Примеры

Пример 1.1

Пусть X – высказывание «В огороде бузина», Y – высказывание «В Киеве дядька».

а) Записать с помощью формул логики высказываний следующие высказывания:

i) «В огороде бузина, а в Киеве дядька»;

ii) «Если неверно, что в огороде бузина, то, или в Киеве дядька, или в огороде бузина»;

iii) «Неверно, что если в Киеве нет дядьки и в огороде нет бузины, то, или в огороде бузина, или неверно, что в Киеве нет дядьки».

б) Записать на естественном языке высказывания, представленные следующими формулами:

i) ;

ii) .

Решение

аi) ;

аii) ;

aiii) ;

бi) Если в огороде нет бузины, то в Киеве нет дядьки;

бii) Если неверно, что если в огороде бузина, то в Киеве дядька, то в огороде бузина, и в Киеве нет дядьки.

Пример 1.2

Разбить высказывание на элементарные и записать в виде формул логики высказываний:

а) «Функция непрерывна и дифференцируема»;

б) «Если функция не является непрерывной, то она недифференцируема»;

в) «Утверждение либо верно, либо неверно»;

г) «Теорема неверна или в доказательстве допущена ошибка»;

д) «Необходимое и достаточное условие счастья для шейха состоит в том, чтобы иметь вино, женщин и услаждать свой слух музыкой».

Решение

а) , где X – «функция непрерывна», Y – «функция дифференцируема»;

б) , где X – «функция непрерывна», Y – «функция дифференцируема»;

в) , где А – «утверждение верно»;

г) , где А – «теорема верна», В – «в доказательстве допущена ошибка»;

д) , где А – «шейх счастлив», В – «шейх имеет вино»; С – «шейх имеет женщин»; D – «шейх услаждает свой слух музыкой».

Пример 1.3

Пусть A – высказывание «Завтра экзамен», B – высказывание «Студент пишет шпаргалки».

Сформулировать словесно:

; ; ; ; ; .

Решение

«Если завтра экзамен, то студент пишет шпаргалки»;

«Завтра экзамен и студент пишет шпаргалки»;

«Неверно, что если завтра экзамен, то студент пишет шпаргалки»;

«Если студент не пишет шпаргалки, то завтра нет экзамена»;

«Студент пишет шпаргалки в том и только том случае, когда завтра экзамен»;

«Если завтра экзамен или студент не пишет шпаргалки, то завтра нет экзамена, и студент не пишет шпаргалки».

Пример 1.4

Какой логической операции соответствует употребление «или» в высказываниях:

а) Родители разрешили завести или собаку, или кошку.

б) Кошелек или жизнь!