bigpo.ru
добавить свой файл
1 2 3 4


М


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


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

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

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


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

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

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

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


С.М. Воротников


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




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

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

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

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


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

УДК 517.11 (07)

ББК 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).

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


А

В

AB

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

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



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


A

В

AB

1


1

1

1


0

0

0


1

1

0


0

1



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



П
Рис. 1.5

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


A

В

AB

1


1

1

1


0

0

0


1

0

0


0

1



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



П
Рис. 1.6

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

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

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

– формулы;

3) других формул, кроме построенных по пп. 1, 2, нет.


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

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

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение 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

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

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

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

в) Либо студент сдает сессию, либо его отчисляют.


^ Решение

а) Альтернативная дизъюнкция, так как предполагается одно условие из двух, но не оба вместе.

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

в) Альтернативная дизъюнкция.


Пример 1.5

Тождественно ли истинны высказывания и формулы:

а) Если Земля столкнется с Солнцем, то пойдет дождь;

б) ;

в) .

Решение

а) Тождественно-истинно, так как посылка – ложна, а из лжи следует все что угодно.

б) Импликация ложна в единственном случае, когда из истины следует ложь. Если истинно, то P и Q принимают одинаковые истинностные значения. Значит, импликация истинна и внешняя импликация – тоже. Если ложно, то внешняя импликация всегда истинна. Итак, вся формула – тождественно-истинна.

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






Здесь приведена сокращенная таблица истинности формулы: сначала заполняются столбцы возможных значений P и Q, таких наборов будет ; затем – столбцы для «внутренних» логических связок (эквивалентность и правая импликация) и, наконец, столбец для внешней (левой) импликации, который и дает истинностные значения всей формулы. Цифры под таблицей показывают порядок заполнения столбцов. Поскольку на любых наборах истинностных значений переменных формула принимает только значение 1, то она является тождественно-истинной.


в) Рассмотрим сразу таблицу истинности:






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


Пример 1.6

Составить таблицы истинности для формул:

а) ;

б) ;

в) ;

г) .


Решение

а)




б)




в)




г)





Задачи


1.1. Записать в виде формул логики высказываний, обозначив за переменные элементарные высказывания:

а) достаточные условия экстремума в точке для функции f(x);

б) необходимые условия экстремума в точке для функции f(x);

в) необходимые и достаточные условия экстремума в точке для функции f(x);


1.2. Определить, является ли данная последовательность формулой:

а) ;

б) ;

в) ;

г) .


1.3. Сколькими способами можно расставить скобки в последовательности, чтобы получилась формула:

а) ;

б) ?


1.4. Выписать все подформулы формулы:

а) ;

б) .

в) ;

г) .


1.5. Составить таблицы истинности для формул;

а) ;

б) ;

в) ;

г) .


1.6. Доказать выполнимость формул:

а) ;

б) ;

в) .


1.7. Доказать тождественную истинность формул:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .


1.8. При каких значениях переменных X, Y, Z, U, V, W следующие формулы ложны:

а) ;

б)

;

в) ;

г) ;

д) ?



следующая страница >>