МЕТОДИЧЕСКИЕ УКАЗАНИЯ Математической логике (го..


Челябинский институт путей сообщения –
филиал государственного образовательного учреждения
высшего профессионального образования
«Уральский государственный университет путей сообщения»
Кафедра «Вычислительная техника»
Т.Н. Половова
Методические указания к выполнению контрольных работ
по дисциплине
«Математическая логика и теория алгоритмов»
Челябинск
2011
УДК 510.6 (075.8)
Половова, Т.Н.
Методические указания к выполнению контрольных работ по дисциплине «Математическая логика и теория алгоритмов» / Т.Н. Половова. – Челябинск:: Челяб. ин-т путей сообщения, 2011, 34 с.
Предлагаемые методические указания используются в качестве практикума для выполнения контрольных работ по изучаемой дисциплине, содержат необходимые теоретические рекомендации по основным разделам курса математической логики и теории алгоритмов.
Предназначается для студентов очной и заочной форм обучения образовательного направления «Информационные системы и технологии», изучающих дисциплину «Математическая логика и теория алгоритмов»; аспирантам, преподавателям.
Рецензент:
А.А. Жуковский, кандидат технических наук, доцент кафедры «Вычислительная техника» ЧИПС УрГУПС
Одобрено научно-методическим советом
Челябинского института путей сообщения
Филиал федерального государственного образовательного
учреждения высшего профессионального образования
«Уральский государственный университет путей сообщения».
Челябинский институт путей сообщения, 2011
Оглавление
TOC \o "1-3" \h \z \u Раздел 1. Алгебра логики PAGEREF _Toc296417016 \h 4Задания для контрольной работы PAGEREF _Toc296417017 \h 5Раздел 2. Алгебра высказываний PAGEREF _Toc296417018 \h 6Задания для контрольной работы PAGEREF _Toc296417019 \h 11Раздел 3. Булева алгебра. Канонические формы записи функций алгебры логики PAGEREF _Toc296417020 \h 14Задание на контрольную работу: PAGEREF _Toc296417021 \h 21Раздел 4. Логическое следование PAGEREF _Toc296417022 \h 22Задания на контрольную работу PAGEREF _Toc296417023 \h 23Раздел 5. Логика предикатов PAGEREF _Toc296417024 \h 24Задание на контрольную работу PAGEREF _Toc296417025 \h 27Раздел 6. Элементы теории алгоритмов. Машины Тьюринга PAGEREF _Toc296417026 \h 28Список используемой литературы PAGEREF _Toc296417027 \h 33
Раздел 1. Алгебра логики
Логика (от греч. Logos – слово, понятие, рассуждение, разум) – наука о законах и формах рационального мышления, методах формализации содержательных теорий.
Предметом исследования науки логики является человеческое мышление. Мышление всегда осуществляется в каких–то формах. В логике выделяют следующие формы мышления: понятие, суждение, умозаключение [3].
Понятие – форма мышления, в которой отражаются отличительные существенные признаки предметов. Например: апельсин, трапеция, река Нил, ураганный ветер, студент медицинского института.
Существенными называются такие признаки, каждый из которых, взятый отдельно, необходим, а все вместе достаточны, чтобы с их помощью отличить (выделить) данный предмет (явление) от всех остальных и сделать обобщение, объединив однородные предметы в множество.
Содержание понятия – совокупность существенных признаков, отраженных в этом понятии.
Объем понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия.
Суждение (высказывание, утверждение) –форма мышления, в которой что–либо утверждается или отрицается о предметах, их свойствах или отношениях между ними.
Примеры суждений:
Этот вкусный апельсин.
Если прошел дождь, то на улице весна.
На Луне живут лунатики, а на Марсе – марсиане.
Суждение характеризуется содержанием и формой.
Содержание суждения – это то, о чем в нем идет речь, его смысл.
Логическая форма суждения – его строение, способ связи его составных частей.
Умозаключение – форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, по определенным правилам вывода получается суждение-заключение.
Умозаключение, так же как и суждение, имеет свою логическую форму (структуру).
Основной принцип формальной логики: правильность рассуждения (умозаключения) определяется только его логической формой (структурой) и не зависит от конкретного содержания входящих в него суждений.
С точки зрения содержания, суждения, входящие в рассуждение, могут быть истинными или ложными (истинно или ложно отражать действительность), а если рассматривать рассуждение со стороны формы, то имеет значение только его логическая правильность или неправильность.
Задания для контрольной работыПриведите примеры понятий, суждений, умозаключений из курсов математики, истории, информатики.
Перечислите существенные признаки, составляющие содержание понятий:
а)квинтэссенция;,
б)добродетель;
в)истина;
г) ложь.
Подсказка: посмотрите толковые словари.
3.Определите объемы понятий:
а)столица России;
б)столица;
в)город;
г)знаменитый полководец;
д)бесконечность;
е)Змей Горыныч.
4.Оцените правильность следующего рассуждения: Сидящий встал; кто встал, тот стоит; значит, сидящий стоит..
Отличаются ли содержания понятий «истина» и «логическая правильность»!
В чем заключается основной принцип формальной логики? Поясните на конкретном примере.
Выведите, если это возможно, заключение из каждой пары посылок:
а)Тем, кто лыс, расческа не нужна. Ни одна ящерица не имеет волос.
б)Ни один добрый поступок не является незаконным. Все, что законно, можно делать без страха.
в)Некоторые уроки трудны.
Все, что трудно, требует внимания.
Раздел 2. Алгебра высказыванийАлгебра логики (алгебра высказываний) – раздел математической логики, изучающей строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Имеет значение F- false, обозначается F или Л).Отдельные высказывания обозначаются буквами какого-либо алфавита, например А, В, С, D и т.д. Истинность или ложность высказываний называется их значением истинности. Истинность высказывания отождествляют с числом 1, а ложность – с числом 0. [3]
Примеры высказываний и предложений, не являющихся высказываниями:
А = Солнце светит для всех =1 – истинное высказывание.
В= Все ученики любят информатику = 0 – ложное высказывание.
Д = А ты любишь информатику? – не высказывание, так как не является повествовательным предложением.
Е = Посмотри в окно – не высказывание, так как является побудительным предложением.
Высказывания бывают простыми и сложными.
Простым называется высказывание, которое не содержит в себе других высказываний
Если несколько простых высказываний объединены в одно с помощью логических операций и скобок, то такое высказывание называется сложным.
Примеры простых высказываний:
Идет дождь:
Нам живется весело
Примеры сложных высказываний:
Идет дождь, а у меня нет зонта;
Пришла весна и прилетели грачи;
Логическая операция – способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний.
Обозначение инверсии: НЕ А, , , NOT A.
Таблица истинности
А
0 1
1 0
Из таблицы истинности следует, что инверсия высказывания истинна, когда высказывание ложно, и ложно, когда высказывание истинно. Иногда это свойство принимают за определение операции инверсии.
Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза «и».
Обозначение конъюнкции: А И В; ; А&В; А·В; А AND B.
Таблица истинности:
А В А&В
0 0 0
0 1 0
1 0 0
1 1 1
Из таблицы истинности следует, что конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно. Иногда это свойство принимают за определение операции конъюнкции.
Логическое сложение (дизъюнкция) образуется соединением двух высказываний в одно с помощью союза «или».
Обозначение дизъюнкции: А ИЛИ В, АВ, А+В.
Таблица истинности:
А В А&В
0 0 0
0 1 1
1 0 1
1 1 1
Из таблицы истинности следует, что дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно.
Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…,то…».
Обозначение импликации: АВ; АВ.
Таблица истинности:
А В АВ
0 0 1
0 1 1
1 0 0
1 1 1
Из таблицы истинности следует, что импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное.
Эквивалентность (логическое равенство) образуется соединением двух высказываний в одно при помощи оборота речи «… тогда и только тогда, когда…».
Обозначения эквивалентности: АВ, АВ, АВ.
Таблица истинности:
А В АВ
0 0 1
0 1 0
1 0 0
1 1 1
Из таблицы истинности следует, что эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны.
Вычисление значений логических выражений выполняется в определенном порядке, согласно их приоритету:
инверсия;
конъюнкция;
дизъюнкция;
импликация и эквивалентность.
Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.
В качестве примера определим форму сложного высказывания – С= Не может быть, что Матроскин выиграл приз и отказался от него – записав его- на языке алгебры логики:
Пусть А= Матроскин выиграл приз, В= отказался от него, тогда

Пример 2.

Составляющими сложного высказывания являются следующие простые высказывания:
А= Человек с детства давал нервам властвовать над собой;
В= Человек в юности давал нервам властвовать над собой;
С= Нервы привыкнут раздражаться;
D= Нервы будут послушны.
Тогда получим в соответствии с логической формой:
Е= Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны. (К.Д.Ушинский)
Задания для контрольной работыПриведите примеры истинных высказываний, ложных высказываний, предложений, не являющихся высказываниями.
Определите, какие из нижеприведенных фраз являются высказываниями с точки зрения алгебры логики. Определите значение высказывания (истина или ложь):
1)Число 8456 является совершенным.
2)Без труда не выловишь и рыбку из пруда.
3)Как хорошо быть генералом!
4)Революция может быть мирной и немирной.
5)Зрение бывает нормальное, или у человека имеется дальнозоркость или близорукость.
6)Познай самого себя.
7)Не может быть, что ни один человек не дышит жабрами.
8)Талант всегда пробьет себе дорогу.
9)Некоторые животные мыслят.
10)Информатика, в частности, изучает алгоритмы.
11)Всякая истина является конкретной.
12)Это утверждение ложно.
13)Когда живется весело, то и работа спорится.
14)Закрой дверь.
15)Челябинск – промышленный город.
16)Вчера было пасмурно, а сегодня ярко светит солнце.
17)Есть ли жизнь на Марсе?
18) Рубль – валюта России.
19)С Новым Годом!
20)Я не знаю английского языка.
Определите формы следующих сложных высказываний, записав их на языке алгебры логики:
Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя.
Если у меня будет свободное время и не будет дождя, то я не буду писать сочинение, а пойду на дискотеку.
Лошадь погибает тот одного грамма никотина, но я не лошадь, следовательно, курить вредно.
Без Вас хочу сказать Вам много, при вас я слушать Вас хочу.
Люди получают высшее образование тогда, когда они заканчивают институт, университет или академию.
Ваш приезд не является ни необходимым, ни желательным
Вчера было пасмурно, а сегодня ярко светит солнце.
Идет дождь, а у меня нет зонта.
Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном расположении духа или с головной болью.
Если фирма продолжает выпуск существующего продукта и ориентирована на существующий рынок, то для нее целесообразна стратегия «малого корабля».
Такая стратегия привлекательна, если интенсивный маркетинг – стратегический хозяйственный фактор, но слабая сторона организации.
Если социологические исследования показывают, что потребитель отдает предпочтение удобству и многообразию выбора, то фирме следует сделать упор на усовершенствование товара или увеличение многообразия новых форм.
Сегодня понедельник или вторник.
Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые.
Если темпы роста рынка продукта корпорации высокие и размер контролируемой ею доли рынка также высок, то в соответствии с матрицей портфельного анализа этот продукт относится к категории «звезда»; он дает большой доход, но требует значительных вложений.
Если при выполнении программы отклонение контролируемых параметров превышает предусмотренные нормы, то требуется оперативная корректировка программы или уточнение стандартов.
Если стратегическая хозяйственная единица корпорации – лидер в непривлекательной отрасли, ее стратегией может быть максимизация прибыли на уже вложенный капитал, но не вложение нового.
Если компьютер при запуске не выдает ошибку при проверке оперативной памяти, то она исправна.
В ситуации, где жизненно необходимо расширение фирмы или где ключевые патенты находятся в руках у других компаний, а данной фирме недостает технических знаний, лучшей стратегией для нее является приобретение.
Стратегическая хозяйственная единица корпорации занимает сильные позиции на рынке и работает в привлекательной отрасли, следовательно, имеет наиболее высокий приоритет рпи распределении ресурсов.
Раздел 3. Булева алгебра. Канонические формы записи функций алгебры логикиАлгебра логики – алгебра, образованная множеством В = {0,1} вместе со всеми возможными операциями на нем.
В алгебре логики из логических переменных, логических констант (0 и 1), знаков логических операций и скобок составляются логические выражения (подобно тому как в алгебре чисел формируются арифметические выражения).
Логическое выражение (логическая форма) – это выражение, содержащее одну или несколько переменных, соединенных знаками логических операций и скобками и превращающихся в высказывания при подстановке вместо этих переменных простых суждений. Выражения алгебры логики также называют формулами.
Например, логическая форма (АВ)С при А= Вы пользуетесь последними версиями антивирусных программ; В= Вы регулярно сохраняете свои файлы на дискетах; С= Снижается вероятность потери данных превращается в высказывание
Е= Если Вы пользуетесь последними версиями антивирусных программ или регулярно сохраняете свои файлы на дискетах, то снижается вероятность потери данных.
Буквы, обозначающие высказывания (А,В,…) можно рассматривать как имена логических переменных.
Логическая функция – это функция, определенная на множестве истинных значений (истина, ложь) и принимающая значение из того же множества.
Например: F (A,B)= AB – логическая функция двух переменных – А и В.
Две переменные, каждая из которых может быть либо нулем, либо единицей, образуют 22=4 различных набора значений: (0,0); (0,1); (1,0); (1,1). На каждом наборе функция принимает значение либо 0, либо 1.
Множество всех логических функций двух переменных Р(2) – бинарных логических операций – представлено в таблице 1 своими таблицами истинности [4]:
Таблица 3.1
х1,х2 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11
0 0
0 1
1 0
1 1 0
0
0
1 0
1
1
1 1
1
0
1 1
0
0
1 0
1
1
0 1
1
1
0 1
0
0
0 1
1
0
0 1
0
1
0 1
1
1
1 0
0
0
0
Конъюнкция & Дизъюнкция , Импликация, Эквивалентность,
Сложение по модулю 2 Штрих Шеффера, Стрелка Пирса, Отрицание x1 Отрицание x2 Константа 1 Константа 0
Существует несколько способов задания ФАЛ, но наиболее распространенными являются два способа задания логических функций: с помощью формулы и с помощью таблицы истинности. По формуле легко составляется таблица. На практике при конструировании различных электронных устройств часто возникает обратная задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему.
Переменные структурной формулы соответствуют входам функциональной схемы. Значение переменных в таблице истинности соответствуют значениям входов функциональной схемы. Для выражения любой ФАЛ применяются 3 оператора: И, ИЛИ, НЕ.
Пример: составить таблицу истинности функции трех переменных, заданной формулой:

Для построения таблицы истинности функции f вычислим ее значения на каждом из восьми наборов значений, используя табл.1.
Таблица 3.2
x1, x2, x3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 1
1
1
1
0
0
0
0 1
1
1
1
0
0
1
1 0
0
0
0
0
1
0
1 0
0
0
0
1
1
0
1
Пример: доказать эквивалентность (равносильность) формул:
а) x1x2 = ;
б) .
Для доказательства эквивалентности формул используем стандартный метод, для чего составим таблицу истинности каждой из указанных формул (используя при этом табл. 1)
Формулы x1x2 , , принимают одинаковые значения на одних и тех же наборах значений (столбцы, соответствующие этим формулам, помечены в табл. 4 меткой ),
Таблица 3.3
x1, x2, x1x2
0 0
0 1
1 0
1 1 1
1
1
0 0
0
0
1 1
1
1
0 1
1
0
0 1
0
1
0 1
1
1
0
Следовательно, они определяют одну и ту же функцию. Таким образом,
x1x2 = = .
Аналогично доказывается второй случай, что отражено в табл.5.
Таблица 3.4
x1, x2,
0 0
0 1
1 0
1 1 1
1
1
0 0
0
0
1 1
1
1
0 1
1
0
0 1
0
1
0 1
1
1
0
Введем следующие определения.
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания и входящих в данную конъюнкцию не более одного раза.
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания и входящих в данную дизъюнкцию не более одного раза.
Всякая дизъюнкцию элементарных конъюнкций есть дизъюнктивная нормальная форма (ДНФ).
Всякая конъюнкция элементарных дизъюнкций есть конъюнктивная нормальная форма (КНФ).
Совершенной дизъюнктивная нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в которой каждая переменная входит только один раз (возможно с отрицанием).
Совершенной конъюнктивной нормальная форма (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в которой каждая переменная входит только один раз (возможно с отрицанием).
Приведем примеры формул, соответствующих и не соответствующих этим определениям (таблица 3.5).
Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ.
Этот факт является теоремой алгебры логики. Из него следует, что любая формула (кроме констант 0 и 1) может быть преобразована к виду как СДНФ, так и СКНФ.
Константа 0 может быть представлена только СКНФ (), а константа 1 – только СДНФ ().
Из вышеперечисленного следует, что если мы хотим построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ и СДНФ этой функции.
Таблица 3.5
Название формулы в определении Формула, соответствующая определению Формула, не соответствующая определению
Элементарная дизъюнкция
Элементарная конъюнкция
ДНФ ДНФ можно построить для всякой формулы (путем преобразования)
КНФ КНФ можно построить для всякой формулы (путем преобразования
СДНФ
СКНФ
ФАЛ заданную любым аналитическим выражением можно преобразовать в КНФ и ДНФ по следующему алгоритму:
Выразить все функции только через И, ИЛИ, НЕ.
Избавиться от инверсии над несколькими переменными, перейдя к форме, в которой имеется инверсия только отдельных элементов (переменных).
Раскрыть скобки, применяя законы алгебры логики.
Привести конъюнкции (дизъюнкции) к элементарным, применяя распределительный закон конъюнкции относительно дизъюнкции.
Алгоритм получения СДНФ по таблице истинностиОтметить те строки таблицы истинности, в последнем столбце которых стоят 1, т.е. найти конституэнты 1:
X Y F(X,Y)
0 0 0
0 1 1
1 0 1
1 1 0
Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание:
– для 2-й строки;
– для 3-й строки.
Все полученные конъюнкции связать в дизъюнкцию:

Алгоритм получения СКНФ по таблице истинности
Отметить те строки таблицы истинности, в последнем столбце которых стоят 0, т.е. найти конституэнты 0:
X Y F(X,Y)
0 0 0
0 1 1
1 0 1
1 1 0
Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание:
– для 1-й строки;
– для 4-й строки.
Все полученные дизъюнкции связать в конъюнкцию:

Пример: логическую функцию трех переменных

Задание на контрольную работу:Для заданной ФАЛ:
минимизировать с помощью законов алгебры Буля;
проверить результат по таблице истинности и найти набор частных значений ФАЛ;
привести к каноническим формам записи (получить совершенные и нормальные формы)
X1 X2 X2 X1 & 1 & X2 & X2 ;
{[(X1 X1)& X2 X2 X3] X3}&[X3 &( X1 & X1)];
{X1 X2 &[(X3 X3) & (X3 1) X4 & X4]};
[X1 & (X3 0)] (X1 X2 & X3);
(X1 X1 X1 & 0) & X2 & (X2 X3);
A & B (A&B&C A&B) B & (B C) & (B A&B&C);
B & (A B C) & (A B D) & (A A & B);
A & (A&B A&C) A&B&C C & (B&C A&B);
(A&B A&B&C)&( A&B C&D) A& (A&B C);
A & (A B) & (A C) (A A&B) & (A B) & A.




Раздел 4. Логическое следованиеОтношение следования между формулами логики высказываний.
Когда мы говорим, что одно предложение Р2 следует из другого предложения Pi, то имеем в виду следующее: всякий раз, когда истинно предложение Pi, истинно и предложение Р2. В логике высказываний это означает, что для формул F\ и F2y соответствующих предложениям Pi и Р2у нет такого набора значений переменных, при котором F\ истинна, a F2 ложна. Например, из предложения «Я пойду в кино» следует предложение «Я пойду в кино или в театр», так как для соответствующих им формул X и XV У невозможен набор значений X и У, при котором первая формула истинна, а вторая ложна: если X принимает значение и, то согласно определению дизъюнкции XV У также принимает значение и.
Говорят, что из формулы F1 следует формула F2, если F1F2– тавтология. При этом употребляют запись Ft = \F2. (Чтобы лучше уяснить смысл этого определения, вспомните, когда импликация, согласно ее определению, ложна.)
Следование, как и равносильность, есть отношение между формулами. Отношение следования обладает свойствами рефлексивности и транзитивности, но не обладает свойством симметричности.
Для того чтобы доказать, что из формулы F\ не следует формула F2, достаточно найти такой набор значений входящих в эти формулы переменных, при котором первая формула принимает значение и, а вторая — л.
Если предложениям Pi и Р2 соответствуют формулы F\ и F2 такие, что из F\ следует F2y то говорят, что из Pi следует Р2 в логике высказываний.
Задания на контрольную работу1. Установите, в каких случаях из первой формулы следует вторая:
a) XY; X;
б) Х; XY;
в) У; ХУ;
г); XvY; XY;
д) XY;XY;
е) XY; YX;
ж) XY; ;
з)(XY)X; Y;
и) (XY)Y;X.
2. Придумайте по два таких предложения, чтобы в логике высказываний: а) из первого следовало второе, но из второго не следовало первое; б) из первого следовало второе и из второго следовало первое.
3. Следует ли из предложения «Если студент много занимается, то он успешно сдает экзамены» предложение «Студент, провалившийся на экзамене, занимался мало»?
Раздел 5. Логика предикатовВ высказывание четко определено: высказывание – это конкретное утверждение о конкретных объектах – истинное или ложное. Предикат – предложение похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно [3].
n–местным предикатом, определенным на множествах М1, М2, ..., Мn, называется предложение, содержащее n переменных x1, x2, ...,xn, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множества М1, М2, ..., Мn соответственно.
Для n–местного предиката будем использовать обозначение P(x1, x2, ...,xn). Переменные x1, x2, ...,xn называются предметными, а элементы множества М1, М2, ..., Мn, которые эти переменные пробегают, – конкретными предметами. Всякий n–местный предикат P(x1, x2, ...,xn), определенный на множествах М1, М2, ..., Мn, представляет собой функцию n аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией–высказыванием.
Например: «Город x – столица России» является одноместным предикатом, определенным над множеством всех названий городов. Подставив место предметной переменной x город «Челябинск», получим высказывание «Город Челябинск – столица России». Это высказывание ложно. Подставив вместо предметной переменной x город «Москва» получим истинное высказывание «Город Москва – столица России».
Другой пример: Выражение «x2 + y2 9» является двухместным предикатом, заданным над множествами R, R. Множества, на которых задан двухместный предикат, совпадают, поэтому говорят, что двухместный предикат задан на множестве R. Пара действительных чисел 2, 1 превращает данный предикат в истинное высказывание: «22 + 12 9», а пара чисел 3, 3 – в ложное: «32 + 32 9».
Множеством истинности предиката P(x1, x2, ...,xn), заданного на множествах М1, М2, ..., Мn, называется совокупность всех упорядоченных n–систем (а1, а2, ...,аn), в которых а1 M1, а2 M2, ...,аn Mn, таких, что данный предикат обращается в истинное высказывание P(а1, а2, ...,аn) при подстановке x1 = a1, x2 = a2,..., xn = an. Это множество будем обозначать P+. Таким образом,
P+ = {(а1, а2, ...,аn) : (P(а1, а2, ...,аn)) = 1}.
Множество P+ истинности n–местного предиката P(x1, x2, ...,xn) представляет собой n–арное отношение между элементами множеств М1, М2, ..., Мn . Если предикат P(x) одноместный, заданный над множеством М, то его множество истинности P+ является подмножеством множества М: P+ M.
Например, множеством истинности двухместного предиката «Точка x принадлежит прямой y», заданного на множестве E всех точек плоскости и на множестве F всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости.
Другой пример, множество истинности двухместного предиката S(x,y): «x2 + y2 = 9», заданного на множестве R, есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиуса 3.
Высказывательные формы называются равносильными, если при всяком наборе значений входящих в них переменных они принимают одинаковые значения истинности.
Таким образом, истинность высказываний P(а1, а2, ...,аn) Q(а1, а2, ...,аn) (Ф1 Ф2) зависит, вообще говоря, от множеств значений переменных, входящих в эти формы.
Утверждение о равносильности двух предикатов P и Q символически записывается следующим образом: P Q. Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех n–местных предикатов, определенных на множествах М1, М2, ..., Мn, распадается на непересекающиеся классы равносильных предикатов ()все они определяют одну и ту же функцию, заданную на множествах М1, М2, ..., Мn и принимающую значения на множествах М1, М2, ..., Мn и принимающую значения в двухэлементном множестве {0,1}.
Переход от предиката P к равносильному ему предикату Q называется равносильным преобразованием первого.
Если Ф1 и Ф2 – равносильные высказывательные формы с одними и теми же переменными, для которых восстановлен один и тот же порядок, то они определяют один и тот же предикат. В самом деле, предикаты P и Q , заданные высказывательными формами Ф1 и Ф2, имеют общую область определения и в силу равносильности Ф1 и Ф2 одинаковые множества истинности; следовательно, P = Q
Например: найти множество истинности предиката, т.е. требуется решить уравнение: 4x – 2 = –3x – 9. Преобразуем его равносильным образом:
4x – 2 = –3x – 9 4x + 3x = –9 + 2 x = –1
Таким образом, {–1} – множество всех решений данного уравнения, т.е. множество истинности данного предиката.
Предикат Q(x1, x2, ...,xn), заданный над множествами М1, М2, ..., Мn, называется следствием предиката P(x1, x2, ...,xn), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Q(x1, x2, ...,xn).
Иными словами, предикат Q является следствием предиката P тогда и только тогда, когда P+ Q+.
Утверждение о том, что предикат Q является следствием предиката P, будем символически записывать так: P+ Q+.
Например: одноместный предикат, определенный на множестве натуральных чисел, «n делится на 3» является следствием одноместного предиката, определенного на том же множестве, «n делится на 6». Из двух предикатов, упомянутых перед последним определением, первый будет следствием второго, если считать, что оба предиката заданы на множестве Z целых чисел.
Два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый из них является следствием другого
Задание на контрольную работуОпределите, следует ли одна высказывательная форма из другой















Изобразите на координатной плоскости множества истинности следующих предикатов:















Раздел 6. Элементы теории алгоритмов. Машины ТьюрингаВведение понятия машины Тьюринга явилось одной из первых и весьма удачных попыток дать точный математический эквивалент для общего интуитивного представления об алгоритме. Это понятие названо по имени английского математика, сформулировавшего его в 1937 году, за 9 лет до появления первой ЭВМ [1].
Определение машины Тьюринга. Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т. д. И так же, как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Именно, Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном «умонастроении», просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается новым «умонастроением» и переходит к просмотру последующих записей.
Машина Тьюринга действует примерно так же. Ее удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки, справа или слева. Причем шаг осуществляется на основании предписанной команды. Совокупность всех команд представляет собой программу машины Тьюринга.
Опишем теперь машину Тьюринга более тщательно.
Машина располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит А=(а0, a1, . . ., a1„). В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита А. Ради единообразия удобно считать, что среди букв внешнего алфавита А имеется «пустая буква» и именно она записана в пустую ячейку ленты. Условимся, что «пустой буквой» или символом пустой ячейки является буква a0. Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.
Далее, в каждый момент времени машина в способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых Q = [q0, q1, . . ., qm). Среди состояний выделяются два — начальное q1 и заключительное, или состояние остановки, q0. Находясь в состоянии q1, машина начинает работать. Попав в состояние q0, машина останавливается.
Работа машины определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда Т (i,j)(i =1, 2, . . ., m; j = 0, 1, . .., п) представляет собой выражение одного из следующих видов:
qiaj qkalC, qial qkajП, qiaj qkalЛ,(28.1)
где 0km, 0ln. В выражениях первого вида символ С будем часто опускать.
Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (то есть в состоянии отличном от q0), машина совершает шаг, который полностью определяется ее текущим состоянием qi, и символом аj, воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой T (i, j): qi;aj qkal X, где X{C, П., Л, . Шаг заключается в том, что: 1) содержимое аj, обозреваемой на ленте ячейки стирается, и на его место записывается символ al (который может совпадать с aj);
2) машина переходит в новое состояние qk (оно также может совпадать с предыдущим состоянием qi);
3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х = П, или к обозрению следующей левой ячейки, если Х = Л, или же продолжает обозревать ту же ячейку ленты, если Х = С.
В следующий момент времени (если qk q0) машина делает шаг, регламентированный командой Т (k, l):qk,ai qrasX, и т. д.
Поскольку работа машины по условию полностью определяется ее состоянием qi, в данный момент и содержимым ai, обозреваемой в этот момент ячейки, то для каждых qi, aj, (i=1, 2, . . ., m; j = 0, 1, . .., п) программа машины должна содержать одну и только одну команду, начинающуюся символами qtaj. Поэтому программа машины Тьюринга с внешним алфавитом А={а0, a1,….., ап и алфавитом внутренних состояний Q = q0, q1, . . ., qm) содержит то m (n+1) команд.
Словом в алфавите А или в алфавите Q, или в алфавите AQ называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-гo шага (или слово в алфавите А, записанное на ленту к началу k-го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, то есть такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.
Если выбрать какую-либо не заключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно, шаг за шагом, преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.
Будем говорить, что непустое слово в алфавите А\{а0= {а1, . . ., ап} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово . Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q\ (соответственно, в состоянии остановки q0). Наконец, будем говорить, что слово перерабатывается машиной в слово , если от слова , воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову , воспринимаемому в положении остановки.
Список используемой литературыИгошин, В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. – 2-е изд., стер. – М.: Издательский центр «Академия», 2008. – 448 с.
Игошин, В.И. Задачи и упражнения по математической логике и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 304 с.
Лыскова, В.Ю. Логика в информатике: Методические пособие / В.Ю. Лыскова, Е.А. Ракитина – 2-е изд., – М.: Издательство «Бином», 2006. – 160 с.
Москвинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: учебное пособие / Г.И. Москвинова. – М.: Логос, 2004. – 240 с.: ил.
Никольская, И.Л. Математическая логика. / И.Л. Никольская – М.: Высшая школа, 1981.
Малышев, В.Н. Информатика: курс лекций / В.Н. Малышев.– Екатеринбург: УрГУПС, 2004, – 185с.

Приложенные файлы

  • docx 8958556
    Размер файла: 165 kB Загрузок: 0

Добавить комментарий