матлогика_методичка

Федеральное агентство по образованию

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









Математическая логика
и
теория алгоритмов

Методические указания
к выполнению практических работ



















Омск
Издательство ОмГТУ
2009

Составитель Л. А. Денисова, канд. техн. наук, доц. кафедры «Автоматизированные системы обработки информации и управления»






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












Печатается по решению редакционно-издательского совета
Омского государственного технического университета





© ГОУ ВПО «Омский государственный технический университет», 2009
СОДЕРЖАНИЕ

13 TOC \o "1-2" \h \z \u 1413 LINK \l "_Toc235253812" 14ВВЕДЕНИЕ 13 PAGEREF _Toc235253812 \h 1441515
13 LINK \l "_Toc235253813" 14ТЕМА 1. ЛОГИКА ВЫСКАЗЫВАНИЙ 13 PAGEREF _Toc235253813 \h 1441515
13 LINK \l "_Toc235253814" 141.1. Логические операции над высказываниями 13 PAGEREF _Toc235253814 \h 1441515
13 LINK \l "_Toc235253815" 141.2. Формулы логики высказываний. Следование и равносильность формул 13 PAGEREF _Toc235253815 \h 1451515
13 LINK \l "_Toc235253816" 141.3. Отыскание нормальных форм формул логики высказываний. 13 PAGEREF _Toc235253816 \h 1471515
13 LINK \l "_Toc235253817" 141.4. Тождественно истинные и тождественно ложные формулы. Проблема разрешимости 13 PAGEREF _Toc235253817 \h 14101515
13 LINK \l "_Toc235253818" 141.5.
·Формализация рассуждений. Правильные рассуждения 13 PAGEREF _Toc235253818 \h 14111515
13 LINK \l "_Toc235253819" 141.6. Задания 13 PAGEREF _Toc235253819 \h 14121515
13 LINK \l "_Toc235253820" 14Варианты индивидуальных заданий 13 PAGEREF _Toc235253820 \h 14121515
13 LINK \l "_Toc235253821" 14ТЕМА 2. ЛОГИКА ПРЕДИКАТОВ 13 PAGEREF _Toc235253821 \h 14151515
13 LINK \l "_Toc235253822" 142.1. Определение предиката. Кванторы. Формулы логики предикатов 13 PAGEREF _Toc235253822 \h 14151515
13 LINK \l "_Toc235253823" 142.2. Приведенные и предваренные нормальные формулы 13 PAGEREF _Toc235253823 \h 14181515
13 LINK \l "_Toc235253824" 142.3. Выражение суждения в виде формулы логики предикатов 13 PAGEREF _Toc235253824 \h 14191515
13 LINK \l "_Toc235253825" 142.4. Задания 13 PAGEREF _Toc235253825 \h 14201515
13 LINK \l "_Toc235253826" 14ТЕМА 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ 13 PAGEREF _Toc235253826 \h 14221515
13 LINK \l "_Toc235253827" 143.1. Построение формализованного исчисления высказываний 13 PAGEREF _Toc235253827 \h 14221515
13 LINK \l "_Toc235253828" 143.2. Автоматическое доказательство теорем. Метод резолюций. 13 PAGEREF _Toc235253828 \h 14251515
13 LINK \l "_Toc235253829" 143.3. Задания 13 PAGEREF _Toc235253829 \h 14271515
13 LINK \l "_Toc235253830" 14ТЕМА 4. НЕЧЕТКАЯ ЛОГИКА 13 PAGEREF _Toc235253830 \h 14301515
13 LINK \l "_Toc235253831" 144.1. Основные понятия нечетких множеств 13 PAGEREF _Toc235253831 \h 14301515
13 LINK \l "_Toc235253832" 144.2. Элементы нечеткой логики. 13 PAGEREF _Toc235253832 \h 14311515
13 LINK \l "_Toc235253833" 144.3. Задания 13 PAGEREF _Toc235253833 \h 14331515
13 LINK \l "_Toc235253834" 14ТЕМА 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ 13 PAGEREF _Toc235253834 \h 14331515
13 LINK \l "_Toc235253835" 145.1. Понятие алгоритма 13 PAGEREF _Toc235253835 \h 14331515
13 LINK \l "_Toc235253836" 145.2. Машина Тьюринга 13 PAGEREF _Toc235253836 \h 14341515
13 LINK \l "_Toc235253837" 145.3 Задания 13 PAGEREF _Toc235253837 \h 14371515
13 LINK \l "_Toc235253838" 14Список литературы 13 PAGEREF _Toc235253838 \h 14381515
15
ВВЕДЕНИЕ
Математическая логика, как и теория алгоритмов, возникла в связи с внутренними проблемами математики, с изучением границ применимости ее теорий и методов. В настоящее время эти взаимосвязанные между собой теории получили развитие в так называемой компьютерной математике (computer science). Вот некоторые направления их использования в прикладных областях:
– при проектировании элементной базы компьютеров используется математический аппарат логики высказываний;
– в основе алгоритмических языков лежат теория алгоритмов, теория формальных систем, логика предикатов;
– тестирование программ основано на логическом анализе их структуры;
– доказательство корректности программ базируется на теории логического вывода;
– в экспертных системах используются формально-логические выводы для имитации деятельности экспертов;
– автоматизация доказательства теорем основана на методе резолюций, изучаемом в курсе логики.


Тема 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
1.1. Логические операции над высказываниями
Высказыванием называется предложение, представляющее собой такое утверждение, относительно которого можно судить, истинно оно или ложно. Высказывание не может быть одновременно истинным и ложным.
По совокупности всех высказываний определяется функция истинности, принимающая значения в двухэлементном множестве {0, 1}:
13 EMBED Equation.3 1415
Значение ((P) называется значением истинности высказывания P.
Символ
· обычно опускают. Это связанно с тем, что в алгебре высказываний полностью отвлекаются от содержания высказываний, а изучают их только в связи с их свойством быть истинными или ложными. Поэтому каждое ложное высказывание можно рассматривать как элемент 0, а истинное – как элемент 1 и писать вместо
·(Р) = 0 или
·(Р) = 1 только Р = 0 или Р = 1.
Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся операций строить новые:
отрицание (P (читается "не P");
конъюнкция P(Q или P(Q (читается "P и Q");
дизъюнкция P(Q (читается "P или Q");
импликация P(Q (читается "если P, то Q" или "из P следует Q" );
эквивалентность P(Q (читается "P равносильно Q" или "P тогда и только тогда, когда Q").
Операция отрицания определяется следующим образом: если P истинно, то (P ложно и наоборот. Остальные операции определяются по таблице 1 (таблице истинности соответствующих операций).

Таблица 1
Операнды
Определение операции

P
Q
P(Q
P(Q
P(Q
P(Q

0
0
0
0
1
1

0
1
0
1
1
0

1
0
0
1
0
0

1
1
1
1
1
1


Следует обратить внимание, что конъюнкция P(Q истинна тогда и только тогда, когда P и Q одновременно истинны, а в остальных случаях ложна. Конъюнкцию называют логическим произведением.
Дизъюнкция P(Q ложна тогда и только тогда, когда P и Q одновременно ложны, а в остальных случаях истинна. Дизъюнкцию называют логической суммой.
Импликация P(Q ложна тогда и только тогда, когда P = 1, а Q = 0. Импликация играет важную роль в логике высказываний. При учете смыслового содержания высказывания (а не только значений истинности) оборот “если, то” подразумевает причинно-следственную связь. Истинность импликации означает лишь то, что если истинна посылка, то истинно и заключение. При ложной посылке заключение всегда истинно.
Эквивалентность P(Q истинна тогда и только тогда, когда значения истинности P и Q совпадают.
С помощью логических операций можно из простых высказываний строить формулы логики высказываний, представляющие составные высказывания.

1.2. Формулы логики высказываний. Следование и равносильность формул
Пропозициональными переменными называются такие переменные, вместо которых можно подставлять конкретные высказывания.
Понятие формулы логики высказываний определяется следующим (индуктивным) образом:
всякая пропозициональная переменная есть формула;
если F1 и F2 – формулы, то выражения (F, (F1(F2), (F1(F2), (F1(F2), (F1(F2) тоже являются формулами;
других формул, кроме построенных по правилам двух предыдущих пунктов, нет.
Обычно внешние скобки у формулы не пишут. Подформулой формулы называется всякая ее часть, которая сама является формулой.
Если F(X1, X2,, Xn) – формула алгебры высказываний, содержащая пропозициональные переменные X1, X2,, Xn, и A1, A2,, An – некоторые конкретные высказывания, то, подставив последние в данную формулу вместо соответствующих пропозициональных переменных, получим составное высказывание F(A1, A2,, An).
Формула F(X1, X2,, Xn) называется выполнимой (опровержимой), если существует такой набор высказываний A1, A2,, An, который обращает эту формулу в истинное (ложное) высказывание F(A1, A2,, An).
Формула называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если она обращается в истинное (ложное) высказывание при всех наборах значений переменных. Обозначение тавтологии:
·F(X1, X2,, Xn).
Некоторые тавтологии играют большую роль в логике и поэтому называются законами: законы рефлексивности P(P, исключенного третьего ¬P(P, закон отрицания противоречия ¬(¬P(P), закон двойного отрицания ¬¬P(P, законы де-Моргана ¬(P(Q)(((P((Q), ¬(P(Q)(((P((Q) и другие.
Высказывания вместе с определенными для них операциями образуют алгебру высказываний.
На множестве формул логики высказываний можно определить семантические (смысловые) отношения следования и равносильности. Эти отношения играют важную практическую роль при упрощении логических выражений и построении корректных логических выводов.
Формула G(X1, X2,, Xn) называется логическим следствием формул F1(X1, X2,, Xn) , , Fm(X1, X2,, Xn) , если она обращается в истинное высказывание на всяком наборе значений переменных, для которых в истинное высказывание обращаются все формулы F1 , ,Fm. Это обозначается F1 , ,Fm
·G.
Две формулы логики высказываний называются равносильными, если на всех одинаковых наборах переменных значения этих формул совпадают. Равносильность формул F и G будем обозначать следующим образом: F ( G. Для того чтобы установить равносильность формул, можно составить таблицы значений для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей формул логики высказываний.
Для любых формул P, Q, R справедливы следующие равносильности:
1. Коммутативность.
а) P(Q
·
· Q(P (для конъюнкции);
б) P(Q
· Q(P (для дизъюнкции).
2. Ассоциативность.
а) P((Q(R)
· (P(R)(R (для конъюнкции);
б) P((Q(R)
· (P(Q)(R (для дизъюнкции).
3. Дистрибутивность.
а) P((Q(R)
· (P(Q)((P(R) (для конъюнкции относительно дизъюнкции);
б) P((Q(R)
· (P(Q)((P(R) (для дизъюнкции относительно конъюнкции).
4. Закон де Моргана.
а)
·(P(Q)
·
·
·P(
·Q (отрицание конъюнкции есть дизъюнкция отрицаний);
б)
·(P(Q)
·
·
·P(
·Q (отрицание дизъюнкции есть конъюнкция отрицаний).
5. Идемпотентность.
а) P(P
· P (для конъюнкции);
б) P(P
· P (для дизъюнкции).
6. Поглощение.
а) P((P(Q)
· P (1-й закон поглощения);
б) P((P(Q)
·
· P (2-й закон поглощения).
7. Расщепление (склеивание).
а) (P(Q)((P(
·Q)
· P (1-й закон расщепления);
б) (P(Q) ( (P(
·Q)
· P (2-й закон расщепления).
8. Двойное отрицание.

·(
·P)
· P.
9. Свойства констант.
а)P(1
· P; б) P(0
· 0; в)P(1
· 1;
г) P(0
· P; д)
·0
·
· 1; е)
·1
·
· 0.
10. Закон противоречия.
P(
·P
· 0.
11. Закон исключенного третьего.
P(
·P
· 1.
12. P(Q
·
·P(Q
·
·
·(P(
·Q).
13. P(Q
· (P(Q)((Q(P)
· (P(Q) ( (
·P(
·Q)
·
·
·P(
·Q)((
·P(Q).
Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “
·”.

1.3. Отыскание нормальных форм формул логики высказываний
Формулы алгебры высказываний могут быть приведены к нормальным формам: дизъюнктивной и конъюнктивной.
Конъюнктивным (дизъюнктивным) одночленом от переменных Х1, Х2,,Хn называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Сокращенная запись: ДН-форма (или ДНФ) и КН-форма (или КНФ) соответственно. Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него.
Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. Сокращенная запись: СДН-форма (или СДНФ) – совершенная дизъюнктивная нормальная форма, СКН-форма (или СКНФ) – совершенная конъюнктивная нормальная форма.
Например, (X1((X2(Х3)((Х1(Х3)((Х2 – дизъюнктивная (но не совершенная) нормальная форма от трех переменных Х1, Х2, Х3, а (Х1((Х2)(((Х1(Х2)(((Х1((Х2) – совершенная конъюнктивная нормальная форма от двух переменных Х1 и Х2.
Для того чтобы формулу равносильными преобразованиями привести к ДНФ, нужно руководствоваться следующим алгоритмом:
избавиться от операции импликации и эквивалентности, выразив их через логические связки (, ( и ( по законам: X(Y ( (X(Y, X(Y ( ((X(Y)(((Y(X);
довести знаки отрицания до независимых переменных, используя законы де Моргана: ((X(Y) ( (X((Y, ((X(Y)( (X((Y;
применяя закон дистрибутивности (X(Y)(Z((X(Z)((Y(Z) , преобразовать формулу к дизъюнкции конъюнктивных одночленов;
постоянно избавляться от двойных отрицаний: ((Х(Х.
Пример 1.1.
Привести равносильными преобразованиями формулу ((X(Z)((X(Y) к дизъюнктивной нормальной форме.
Решение. Преобразуем формулу к ДНФ, руководствуясь приведенными правилами:
((Х(Z)((X(Y)( ((X((Z)(((X(Y)((X(((Z(((X(Y))( (X((((Z((X)(((Z(Y))(( (X((Z((X)(((X(Y((Z) (((X((Z)(((X(Y((Z).
Пример 1.2.
Привести равносильными преобразованиями формулу примера 1.1 к конъюнктивной нормальной форме.
Решение. Формулу равносильными преобразованиями можно привести к КНФ, руководствуясь приведенными четырьмя правилами, с той лишь разницей, что в правиле 3) следует использовать другой (двойственный) закон дистрибутивности: (X(Y)(Z((Х(Z)((Y(Z).
Преобразуем данную формулу:
((Х(Z)((X(Y)(((X((Z)(((X(Y)(((X((Z)(((X(Y((Z)((((X((Z)((X)(
((((X((Z)(Y)((((X((Z)((Z)((X((((X(Y)(((Z(Y))((Z( (((X(((X(Y))((((Z(Y)((Z)((X((Z.
Пример 1.3.
Применяя равносильные преобразования, найти СДНФ для формулы из примера 1.1
Решение. Чтобы привести формулу к СДНФ, нужно сначала равносильными преобразованиями привести ее к какой-нибудь ДНФ (см. пример 1.1). При этом нужно убрать члены дизъюнкции, содержащие переменную вместе с ее отрицанием, а из одинаковых членов дизъюнкции удалить все, кроме одного. Если какой-либо конъюнктивный одночлен в ДНФ содержит не все переменные из числа входящих в исходную формулу, то его умножают на единицы, представляемые в виде дизъюнкций Xi((Xi каждой недостающей переменной Xi с ее отрицанием (Xi (закон исключенного третьего). Затем раскрывают скобки внутри каждого такого конъюнктивного одночлена, применяя закон дистрибутивности конъюнкции относительно дизъюнкции. Наконец, если среди членов полученной дизъюнкции окажутся одинаковые конъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.
Приведем данную формулу к СДНФ, начав преобразования с ДНФ, полученной при решении примера 1.1:
((Х(Z)((X(Y)(((X((Z)(((X(Y((Z)((((X((Z)((Y((Y))(((X(Y((Z)( (((X((Z(Y)(((X((Z((Y)(((X(Y((Z) (((X(Y((Z)(((X((Z((Y).
Пример 1.4.
Применяя равносильные преобразования, найти СКНФ для формулы из примера 1.2.
Решение. Правила приведения формулы к СКНФ двойственны соответствующим правилам приведения к СДНФ. Найчав с какой-нибудь КНФ данной формулы, нужно в каждом ее дизъюнктивном одночлене, в котором присутствуют не все переменные из числа входящих в данную формулу, добавить (через дизъюнкцию) нули, представляемые в виде конъюнкции Xi((Xi каждой недостающей переменной Xi с ее отрицанием (Xi. Затем внутри каждого такого дизъюнктивного одночлена раскрыть скобки, используя закон дистрибутивности дизъюнкции относительно конъюнкции. Если среди членов полученной конъюнкции окажутся одинаковые дизъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.
Приведем данную формулу к СКНФ, начав преобразование с КНФ, полученной при решении примера 1.2:
((Х(Z)((X(Y)((X((Z(((X((Y((Y))(((Z((X((X))(((X(Y)(((X((Y)(
((X((Z)(((X((Z)(((X(Y((Z((Z))(((X((Y((Z((Z))((X((Z((Y((Y))(
(((X((Z((Y((Y))(((X(Y(Z)(((X(Y((Z)(((X((Y(Z)(((X((Y((Z)( ((X(Y((Z)((X((Y((Z)(((X(Y((Z)(((X((Y((Z)( (((X(Y(Z)(((X(Y((Z)(((X((Y(Z)(((X((Y((Z)((X(Y((Z)((X((Y((Z).

1.4. Тождественно истинные и тождественно ложные формулы. Проблема разрешимости
Проблема разрешимости для логики высказываний заключается в том, чтобы установить, является ли произвольная формула тождественно истинной.
Это условие выражает теорема: формула является тождественно истинной тогда и только тогда, когда в ее КНФ в любой из дизъюнктивных одночленов одновременно входят какая-либо переменная и ее отрицание.
Согласно другой теореме, формула является тождественно ложной тогда и только тогда, когда в ее ДНФ в любой из конъюнктивных одночленов одновременно входят какая-либо переменная и ее отрицание.
Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно ложной.
Пример 1.5.
Доказать, что формула F =(P
·(Q)
·(((R(P)
·((R(Q)) является тождественно истинной.
Применяя равносильные преобразования, приведем формулу к КНФ:
(P(Q)(((R(P)((R(Q))
·
·(P(Q)(((R(P)
·((R(Q))
·
·(P(
·Q)(
·(R(P)( ((R(Q)
·
·
·
·(P(
·Q) ((
·R(
·P) ((R(Q)
·
·
·
·(P (
·R)( (P(
·P) ((
·Q(
·R)(
((
·Q(
·P)((R(Q)
·
·(P(
·R)((
·Q(
·R)((
·Q(
·P)((R(Q) 
·
·
·(P(
·R(R(Q)((
·Q(
·R(R(Q)((
·Q(
·P(R(Q).
В первую дизъюнкцию входят R и
·R. Во вторую – Q и
·Q, R и
·R. в третью – Q и
·Q. Следовательно, можно утверждать, что исходная формула является тождественно истинной.
Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:
1) приведением с помощью равносильных преобразований к КНФ или ДНФ;
2) составлением таблицы истинности.
Пример 1.6.
Установить, является ли тождественно истинной данная формула логики высказываний: F(P, Q) = (P((P(Q))
·(Q.
1) Применяя равносильные преобразования, приведем формулу к КНФ:
(P((P(Q))
·(Q
·(P((
·P(Q))(Q
·
·(P((
·P(Q)(Q (
·
·
·P(
·(
·P(Q))(Q
·
·
·
·P((P((Q)(Q
·
·
·(
·P(Q)((P(
·Q)(
·
·(
·P(Q(P)((
·P(Q(
·
·Q).
В первую дизъюнкцию входят P и
·P. Во вторую – Q и
·Q, поэтому формула является тождественно истинной, F(P, Q)
· 1.
2) Составим таблицу истинности F(P, Q) (таблица 2).
Таблица 2
P
Q
P(Q
P((P(Q)
(P((P(Q))(Q

0
0
1
0
1

0
1
1
0
1

1
0
0
0
1

1
1
1
1
1

Из таблицы 2 видно, что F(P, Q)
· 1.

1.5.
· Формализация рассуждений. Правильные рассуждения
Рассуждение – это построение нового высказывания D на основании уже имеющихся высказываний P1, P2, ... , Pn. Высказывания P1, P2, ... , Pn называются посылками, а высказывание D – заключением.
Рассуждение называется правильным, если из конъюнкции посылок следует заключение, т. е. формула P1( P2( ... ( Pn ( D тождественно истинна.
Таким образом, если все посылки истинны (т. е. их конъюнкция равна 1), то истинное заключение соответствует правильному рассуждению, а ложное заключение – неправильному. При ложности хотя бы одной из посылок независимо от истинностного значения заключения рассуждение будет правильным.
Схематически рассуждение изображается следующим образом:
P1, P2, ... , Pn
D
Пример 1.7.
Проверить правильность следующих рассуждений.
а) Если погода дождливая, то небо не ясное. Небо ясное. Значит, погода не дождливая.
Введем высказывания: А= "Погода дождливая"; B= "Небо ясное". Схема рассуждения имеет вид:
А (
·B, B

·А
Докажем, что формула ((А(
·B)(B)(
·А является тождественно истинной. Приведем эту формулу к КНФ и покажем, что формула тождественно истинна:
((А(
·B)(B)(
·А
·
·
·((А(
·B)(B)(
·A
· (A(B)(
·B(
·A
·

· (
·А(
·
·B(A)((
·A(
·B(B)
· 1.
Значит, рассуждение правильное.
б) Если будет хорошая погода, я пойду гулять. Если будет плохая погода, я буду читать книгу. Погода будет хорошая. Следовательно, я не буду читать книгу.
Введем высказывания: А = “Будет хорошая погода”; B = “Я пойду гулять”. C = “Я буду читать книгу”. Схема рассуждения имеет вид:
А ( B,
·A ( С, A.

·С
Найдем КНФ формулы ((А ( B) ( (
·A ( С) ( A) (
·
·C:
((А ( B) ( (
·A ( С) ( A) (
·
·C
·
·
·((А ( B) ( (
·A ( С) (A) (
·
·C
·
·
·(А ( B) (
·(
·A ( С) (
·A) (
·
·C
·
·А (
·B (
·A (
·С (
·A (
·C
·
·А (
·B (
·A (
·
·C
·
·(А (
·A (
·
·C) ( (
·B (
·A (
·
·C)
·
·
·B (
·A (
·
·C.
Полученная КНФ нашей формулы не содержит одновременно какой-либо переменной и ее отрицания. Следовательно, формула не является тождественно-истинной, а рассуждение не является правильным.

1.6. Задания
1. Выполнив равносильные преобразования, установить, является ли данная формула тождественно истинной. Привести данную формулу к СДНФ.
2. Установить, является ли данное рассуждение правильным (проверить, следует ли заключение из конъюнкции посылок).

Варианты индивидуальных заданий
Вариант № 1
1. (P ( Q) ( ((Q ( R) ( (P ( R)).
2. Если исходные данные корректны и программа работает правильно, то получается верный результат. Результат неверен. Следовательно, исходные данные некорректны или программа работает неправильно.
Вариант № 2
1. (P ( Q) ( ((P ( (Q ( R)) ( (P ( R)).
2. Профсоюзы штата будут поддерживать губернатора, если он подпишет этот закон. Фермеры окажут ему поддержку, если он наложит на него вето. Очевидно, что он или не подпишет закон, или не наложит на него вето. Следовательно, губернатор потеряет голоса рабочих, объединенных в профсоюзы, или голоса фермеров.
Вариант № 3
1. (P ( R) ( ((Q ( R) ( ((P ( Q) ( R)).
2 Если подозреваемый совершил кражу, то либо она была тщательно подготовлена, либо он имел соучастников. Если бы кража была тщательно подготовлена, то, если бы были соучастники, украдено было бы много. Украдено мало. Значит, подозреваемый невиновен.
Вариант № 4
1. (Q ( R) ( ((P ( Q) ( (P ( R)).
2. Если курс ценных бумаг растет или процентная ставка снижается, то падает курс акций. Если процентная ставка снижается, то либо курс акций не падает, либо курс ценных бумаг не растет. Курс акций понижается. Следовательно, снижается процентная ставка.

Вариант № 5
1. ((Q ( (R (
·P)) ( (R ( (P ( Q))) (
·R .
2. Договор будет выполнен тогда и только тогда когда дом будет закончен в феврале. Если дом будет закончен в феврале, то мы можем переехать в марте. Договор будет выполнен, Следовательно, мы можем переехать в марте.
Вариант № 6
1. ((P ( Q) ( (Q ( R))( P ( R.
2. Если мы не будем продолжать политику сохранения цен, то мы потеряем голоса фермеров. Если же мы будем продолжать эту политику и не прибегнем к контролю над производством, то продолжится перепроизводство. Без голосов фермеров нас не переизберут. Значит, если нас переизберут и мы не прибегнем к контролю над производством, то продолжится перепроизводство.
Вариант № 7
1. (Q ( (R ( P)) ( (R ( (P ( Q)).
2. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастет. Безработица не возрастет. Следовательно, правительственные расходы возрастут.
Вариант № 8
1. (P ( Q) ( ((Q ( R) ( (P ( R)).
2. В бюджете возникнет дефицит, если не повысят налоги. Если в бюджете возникнет дефицит, то расходы на социальные нужды сократятся. Следовательно, если повысят налоги, то расходы на социальные нужды не сократятся.
Вариант № 9
1. (P ( Q) ( ((Q ( R) ( (P ( R)).
2. Если цены высоки, то и заработная плата высока. Цены высоки или применяется регулирование цен. Если применяется регулирование цен, то нет инфляции. Наблюдается инфляция. Следовательно, заработная плата высока.
Вариант № 10
1. ((Q ( (R (
·P)) ( (R ( (P ( Q))) (
·R.
2. Если я устал, я хочу вернуться домой. Если я голоден, я хочу вернуться домой или пойти в ресторан. Я устал и голоден. Поэтому я хочу вернуться домой.
Вариант № 11
1. (P ( Q) ( ((Q ( R) ((P ( R)).
2. Если будет холодно, то я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а рукав не будет починен. Значит, я не надену теплое пальто.
Вариант № 12
1. (P ( Q) ( ((P ( (Q ( R)) ( (P ( R)).
2. Если будет идти снег, машину будет трудно вести. Если будет трудно вести машину, я опоздаю, если не выеду пораньше. Идет снег, и я выеду пораньше. Значит, я не опоздаю.
Вариант № 13
1. (P ( R) ( ((Q ( R) ( ((P ( Q) ( R)).
2 Намеченная атака удастся, если захватить противника врасплох или его позиции плохо защищены. Захватить противника врасплох можно только, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Следовательно, намеченная атака не удастся.
Вариант № 14
1. (Q ( R) ( ((P ( Q) ( (P ( R)).
2. Если бы он был умен, то он увидел бы свою ошибку. Если бы он был искренен, то он признался бы в ней. Однако он не умен и не искренен. Следовательно, он или не увидит свою ошибку, или не признается в ней.
Вариант № 15
1. ((Q ( (R (
·P)) ((R ( (P ( Q))) (
·R .
2. Если завтра будет хорошая погода, то я буду кататься на коньках или я пойду на лыжах. Если я пойду на лыжах, то лучше поехать за город, а если буду кататься на коньках, то останусь в городе. Мне не хочется завтра в выходной день оставаться в городе. Следовательно, если завтра будет хорошая погода, то я пойду на лыжах.
Вариант № 16
1. ((P ( Q) ( (Q ( R))( P ( R.
2. Андрей или очень переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, Андрей не болен.
Вариант № 17
1. (Q ( (R ( P)) ( (R ((P ( Q)).
2. Если Иванов работает, то он получает зарплату. Если же Иванов учится, то он получает стипендию. Но Иванов не получает зарплату или не получает стипендию. Следовательно, он не работает или не учится.
Вариант № 18
1. (P ( Q) (((Q ( R) ((P ( R)).
2. Если я лягу спать, то не сдам экзамен. Если я буду заниматься ночью, то тоже не сдам экзамен. Следовательно, я не сдам экзамен.

Вариант № 19
1. (P ( Q) ( ((Q ( R) ( (P ( R)).
2. Если я пойду завтра на первую лекцию, то должен буду встать рано. Если я пойду вечером на дискотеку, то лягу спать поздно. Если я лягу спать поздно, а встану рано, я буду плохо себя чувствовать. Следовательно, я должен пропустить первую лекцию или не ходить на дискотеку.
Вариант № 20
1. (R ( P) (((P ( Q) ( (R (Q)).
2. Если человек занимается спортом, то он здоров. Если человек здоров, то он счастлив. Этот человек занимается спортом. Значит, он счастлив.
13 EMBED Equation.3 1415

Тема 2. ЛОГИКА ПРЕДИКАТОВ
2.1. Определение предиката. Кванторы. Формулы логики предикатов
Предикат – это повествовательное предложение, содержащее предметные (индивидные) переменные, замена которых на константные значения превращает рассматриваемое предложение в высказывание – истинное или ложное. Другими словами, выражение P(x1, x2, ... , xn), содержащее предметные переменные x1(M1, x2(M2, xn(Mn, называется n-местным предикатом, если оно выражает некоторое n-местное отношение на множествах M1, M2,Mn.
Например, если x, y – предметные переменные, принимающие значения из множества M=(Солнце, Земля, Луна, Марс(, то предложение "x вращается вокруг y" можно рассматривать как 2-местный предикат P(x, y). Множество истинности P(x, y) – это множество упорядоченных пар (кортежей) rP={(Земля, Солнце), (Луна, Земля), (Марс, Солнце)}, на которых P(x, y)=1. Множество rP выражает бинарное отношение на множестве M небесных тел, например, "Земля rP Солнце". Можно сказать, что P(x, y) – это предикат отношения rP .
Если все переменные x1, x2, ... , xn принимают конкретные значения, то предикат есть не что иное, как высказывание, Таким образом, высказывание является частным случаем предиката.
Предикат называется тождественно истинным, если значение его для любых аргументов есть "истина"; тождественно ложным, если значение его для любых аргументов есть "ложь"; выполнимым (опровержимым), если существует, по крайней мере, один набор его аргументов, для которого значение предиката есть "истина" ("ложь").
Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом, можно говорить об алгебре предикатов. Кроме операций логики высказываний, в логике предикатов используются особые логические символы – кванторы.
Квантор общности. Пусть P(x) – некоторый предикат, определенный для каждого x ( М. Тогда выражение (xP(x) является истинным высказыванием, если P(x) истинно для всякого x ( М, и ложным в противном случае. Символ (x называется квантором общности. Выражение (xP(x) читается: "Для всех x имеет место P(x)". В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности:
·(xP(x): "Не для всех x имеет место P(x)".
Квантор существования. Пусть P(x) – некоторый предикат, x ( М. Тогда выражение (xP(x) является истинным высказыванием, если P(x) истинно хотя бы для одного x ( М, и ложным в противном случае. Символ (x называется квантором существования. Выражение (xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования:
·(xP(x): "Не существует x, для которого имеет место P(x)".
Кванторы существования и общности называются двойственными кванторами. Переменная, стоящая под знаком квантора, называется также связанной переменной. Несвязанная переменная называется свободной.
Кванторы применяются и к многоместным предикатам, при этом число свободных переменных уменьшается на единицу. Одноместный предикат при связывании переменной квантором становится 0-местным предикатом, т. е. высказыванием.
Формула логики предикатов определяется индуктивно следующим образом:
всякая формула логики высказываний есть формула логики предикатов;
предметные переменные x, y, z, ... есть формулы;
предикаты P(x), Q(x, y), ... , а также выражения с кванторами (xP(x), (xR(x), (x(yQ(x, y),... есть формулы;
если F1 и F2 – формулы, то выражения (F, (F1(F2), (F1(F2), (F1(F2), (F1(F2) тоже являются формулами, в которых свободные переменные формул F1 и F2 остаются свободными, а связанные переменные формул F1 и F2 остаются связанными;
других формул, кроме построенных по правилам пунктов 1 – 4, нет.
Пусть A – формула, содержащая свободную переменную x. Тогда (xA, (xA – формулы, причем в первом случае A является областью действия квантора общности, а во втором – областью действия квантора существования.
Формулы F и G, определенные на некотором множестве М, называются равносильными на этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения. Формулы, равносильные на любых множествах, называются просто равносильными.
Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по нижеследующим правилам.
1. Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов.
2.
·Знак отрицания можно ввести под знак квантора, заменив квантор на двойственный.

·((xA(x)
·
·(x(
·A(x)).

·((xA(x))
·
·(x(
·A(x)).
3. Вынос квантора за скобки.
Пусть формула A(x) содержит переменную x, а формула B не содержит переменной x, и все переменные, связанные в одной формуле, связаны в другой. Тогда
(xA(x)(B
·
· (x(A(x)(B).
(xA(x)(B
·
·(x(A(x)(B).
(xA(x)(B
·
·(x(A(x)(B).
(xA(x)(B
·
·(x(A(x)(B).
4. Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции.
Пусть формула B, так же, как и формула A, зависит от х. Тогда
(xA(x) ( (xB(x)
·
· (x(A(x)(B(x)).
(xA(x) ( (xB(x)
·
· (x(A(x)(B(x)).
Дистрибутивные законы для квантора общности относительно дизъюнкции и квантора существования относительно конъюнкции не имеют места.
5. Перестановка одноименных кванторов.
(x(yA(x,y)
·
·(y(xA(x,y).
(x(yA(x,y)
·
·(y(xA(x,y).
Разноименные кванторы переставлять нельзя.
6. Переименование связанных переменных.
Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора – получим формулу, равносильную A.
Формула есть перевод содержательного рассуждения в формальное рассуждение. Формула имеет смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Каждая интерпретация состоит в указании множества М изменения предметных переменных и задании отношения между переменными с помощью предикатов.
Для данной интерпретации формула представляет собой высказывание, если переменные связаны кванторами, а если есть свободные переменные, то формула есть предикат, который может быть истинным для одних значений переменных из области интерпретации и ложным для других.
Формула A называется выполнимой в данной интерпретации, если существует набор значений переменных (a1, a2, ... , an) 13 EMBED Equation.2 1415 M, для которого A(a1, a2, ... , an) = 1. Формула A называется истинной в данной интерпретации, если A(x1, x2, ... , xn) = 1 на любом наборе своих переменных (x1, x2, ... , xn) 13 EMBED Equation.2 1415 M. Формула A называется общезначимой или тождественно-истинной, если она истинна в каждой интерпретации. Формула A называется выполнимой, если существует интерпретация, для которой она выполнима.
Проблема разрешимости для логики предикатов, так же, как и для логики высказываний, заключается в том, чтобы установить, является ли произвольная формула тождественно истинной.

2.2. Приведенные и предваренные нормальные формулы
Формулы, в которых из логических символов имеются только символы (, ( и
·
·
·причем символ
·
·встречается лишь перед символами предикатов, называются приведенными формулами. Для каждой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают. Приведенная формула называется предваренной нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди. Для каждой приведенной формулы существует равносильная ей нормальная формула.
Пример 2.1.
Найти равносильную предваренную нормальную формулу для приведенной формулы: (x(yA(x, y) ( (x(u(x, u).
В формуле (yA(x, y) переменная y связана, поэтому (yA(x, y) не зависит от y. Обозначим D(x) = (yA(x, y).
В формуле (uB(x, u) переменная u связана, поэтому (uB(x, u) не зависит от u. Обозначим F(x) = (uB(x, u).
Тогда (x(yA(x, y) ( (x(uB(x, u) = (xD(x) ( (xF(x).
Применим правило переименования переменных и за скобки вынесем два квантора (x и (x. Получим
(xD(x) ( (xF(x)
·
·(x(z(D(x) ( F(z)).
Рассмотрим формулу D(x) ( F(z) = (yA(x, y) ( (uB(z, u). Применив два раза правило вынесения квантора за скобки, получим
(yA(x, y) ( (uB(z, u)
·
· (y(A(x, y) ( (uB(z, u))
·
· (y(u (A(x, y) ( B(z, u)).
Применив снова правило вынесения квантора за скобки, получим окончательно
(x(yA(x, y) ( (x(uB(x, u)
·
· (x(z(y(u(A(x, y) ( B(z, u)).
В полученном тождестве в левой части – исходная формула, а в правой части – ее предваренная нормальная формула.

Пример 2.2.
Найти равносильную предваренную нормальную формулу для формулы: (x(yA(x, y) ( (x(uB(x, u).
1. Найдем вначале приведенную формулу, равносильную данной. Избавимся от символа (
·
(x(yA(x, y) ( (x(u(x, u)
·
·
·
·((x(yA(x, y)) (
· (x(uB(x, u).
Применим правило переноса квантора через отрицание:

·((x(yA(x, y))
·
·
· (x(y
·A(x, y),
Следовательно,
(x(yA(x, y) ( (x(uB(x, u)
·
·
·(x(y
·A(x, y)( (x(uB(x, u).
Правая часть тождества – приведенная формула, равносильная данной.
2. Найдем теперь предваренную нормальную формулу, равносильную приведенной формуле (x(y
·A(x, y) ( (x(uB(x, u). Проделаем преобразование этой формулы аналогично предыдущему примеру:
(x(y
·A(x, y)((x(uB(x, u)
·
·
·(x(y
·A(x, y) (
· (z(uB(z, u)
·
·

·
·
·(x(z((y
·A(x, y) (
· (uB(z, u))
·
·
·(x(z(y(u(
·A(x, y) (B(z, u)).
Получена предваренная нормальная формула, равносильная исходной.

2.3. Выражение суждения в виде формулы логики предикатов
Суждение – это мысль, в которой утверждается наличие или отсутствие свойств предметов, отношений между предметами. Простым суждением называется суждение, в котором нельзя выделить часть, в свою очередь являющуюся суждением. Среди простых суждений выделяют атрибутивные суждения и суждения об отношениях. В атрибутивных суждениях выражается наличие или отсутствие у предметов некоторых свойств. Например, "Иванов – спортсмен", "некоторые моря имеют пресную воду".
Все атрибутивные суждения можно разделить на типы и перевести на язык логики предикатов: "a есть P" – P(a) ; "Все S есть P" – (x(S(x)(P(x)) (общеутвердительное суждение); "Ни один S не есть P" – (x(S(x)(
·P(x)) (общеотрицательное суждение); "Некоторые S есть P" – (x(S(x)(P(x)); (частноутвердительное суждение); "Некоторые S не есть P"– (x(A(x)(
·P(x)) (частноотрицательное суждение).
При переводе на язык логики предикатов надо руководствоваться правилом: если кванторная переменная связана квантором общности ((), то в формуле используется знак импликации ( ()
·
·а если кванторная переменная связана квантором существования ((), то в формуле используется знак конъюнкции (().
Пример 2.3.
Перевести на язык логики предикатов следующие суждения.
а) Андрей – студент.
Заменим имя " Андрей" символом "а" и введем предикат P(x) = "x – студент". Это суждение можно выразить формулой: P(а).
б) Всякая логическая функция может быть задана таблицей.
Введем предикаты S(x) = "x – логическая функция"; P(x) = "x может быть задана таблицей". Это суждение можно выразить формулой: (x(S(x) ( P(x)).
в) Ни один человек не всеведущ.
Введем предикаты S(x) = "x – человек"; P(x) = "x всеведущ". Суждение можно выразить формулой: (x(S(x) (
·P(x)).
г) Некоторые студенты были на конференции.
Введем предикаты S(x) = "x – студент"; P(x) = "x был на конференции". Суждение можно выразить формулой: (x(S(x) ( P(x)).
д) Некоторые люди не умеют слушать.
Введем предикаты S(x) = "x – человек"; P(x) = "x умеет слушать". Суждение можно выразить формулой: (x(A(x) (
·P(x)).
Суждения об отношениях выражают отношения между объектами. При переводе этих суждений в формулы используют многоместные предикаты и рассмотренные правила. При переводе отрицаний суждений на язык формул применяется правило переноса квантора через знак отрицания и другие равносильные преобразования.
Пример 2.4.
Суждение "Некоторые студенты сдали все экзамены" записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.
Введем предикаты: A(x) = "x – студент"; B(y) = "y – экзамен", C(x, y) = "x сдал экзамен y". Тогда предложение "Некоторые студенты сдали все экзамены" можно записать в виде следующей формулы:
(x(y(A(x)(B(y) ( C(x, y)).
Построим отрицание этой формулы, применяя равносильные преобразования:

·(x(y(A(x)(B(y)(C(x, y)))
·
·(x(y(
·(A(x)(B(y) (C(x, y))(

·
·(x(y(A(x)(B(y)(
·C(x, y)).
Это предложение можно прочитать следующим образом:
"Каждый студент не сдал хотя бы один экзамен".

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

Варианты индивидуальных заданий
Вариант № 1
1
·
·(x
·P(x)(R(x)((yQ(x,y)).
2. Не всякое действительное число является рациональным.
Вариант № 2
1
·
·(x
·P(x)((R(x)((yQ(x,y)).
2. Каждый студент выполнил хотя бы одну практическую работу.
Вариант № 3
1. (xP(x)((yP(y))((z(xR(x, z).
2. Ни одно четное число, большее 2, не является простым.
Вариант № 4
1.
·x
·
·
·y(
·P(x)(Q(y))( R(y, z)).
2. Некоторые звезды не видны.
Вариант № 5
1.
·x
·
·
·y(
·P(x,y)(Q(y, z))).
2. Произведение любых двух простых чисел не является простым числом.
Вариант № 6
1.
·x
·
·y(
·P(x))(Q(y)).
2. Всякое положительное число больше всякого отрицательного числа.
Вариант № 7
1.
·x
·
·y(
·P(x))(Q(y, z)).
2. Все ромбы являются параллелограммами.
Вариант № 8
1.
·x
·P(x)
·( Q(x, y))
·(
·
·
·yP(y)
·(
·
·zQ(y, z
·).
2. Некоторые четные функции периодические.
Вариант № 9
1
·
·
·xP(x, y)( (Q(x) (
·
·
·u(P(x, u))).
2. Всякий равносторонний треугольник является равнобедренным.
Вариант № 10
1.
·x
·y(
·zP(x, z) ( Q(x, z)) ( (uR(x, y, u).
2. Некоторые змеи ядовиты.
Вариант № 11
1.
·x
·P(x)
·(
·y(Q(x, y)
·(
·
·zR(x, y, z))).
2. Некоторые реки не судоходны.
Вариант № 12
1.
·
·x
·P(x)
·(
·yQ(x, y
·.
2. Никакое знание не бесполезно.
Вариант № 13
1. ((
·x
·yP(x, y
·)(
·(
·x
·y
·zQ(x, y, z
·))(
·yR(y).
2. Некоторые абитуриенты поступили в институт.

Вариант № 14
1.
·x(P(x) ( ((
·y
·zQ(x, y, z))).
2. Студент ответил на некоторые вопросы.
Вариант № 15
1. (
·(
·xP(x))
·(
·(
·xQ(x
·)((R(x) (
·yS(x, y
·).
2. Автобус останавливается на всех остановках.
Вариант № 16
1.
·x P(x) (
·
·xQ(x).
2. Ни одна монотонная функция не явлвется четной.
Вариант № 17
1. ((
·xP(x)
·(
·
·xQ(x))((R (
·S(x, y
·).
2. Ни один лентяй не заслуживает похвалы.
Вариант № 18
1. P(x, y) ( (((xQ(x, y)((uP(u)).
2. Не все металлы твердые.
Вариант № 19
1.
·x
·y(Q(x
·
·(
·(
·P(x, y)(((
·uR(x, y, u)))).
2. Некоторые студенты получают стипендию.
Вариант № 20
1. (P(x, y)
·(
·
·(xQ(x)(((
·y(uR(y, u, y
·
·).
2. Некоторые параллелограммы являются ромбами.


Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ
3.1. Построение формализованного исчисления высказываний
Способ построения научной теории в виде системы аксиом и правил вывода, позволяющих формальным логическим путем получать утверждения (теоремы) данной теории, называется аксиоматическим методом. Аксиомы (утверждения, принимаемые без доказательств) выделяются, а правила вывода определяются так, что по ним из аксиом могут быть получены все тавтологии алгебры высказываний и только они.
В качестве аксиом выбраны формулы следующих видов:
(A1) 13 EMBED Equation.3 1415
(А2) 13 EMBED Equation.3 1415
(А3) 13 EMBED Equation.3 1415
где F, G, H – произвольные формулы. Таким образом, каждое из выражений (A1), (A2), (A3) задает лишь форму аксиомы. Они превращаются в аксиомы, если вместо F, G, H подставить конкретные формулы (в частности, пропозициональные переменные). Следовательно, каждое из этих выражений задает бесконечное множество формул. Все они называются аксиомами. Поэтому каждое из выражений (A1), (A2), (A3) называют схемой аксиом. Далее определяется следующее правило получения новых формул из имеющихся. Если имеются формулы F и 13 EMBED Equation.3 1415, то они дают формулу G. Это правило называется modus ponens или правилом отделения (сокращенно m. p.) и записывается так:
13 EMBED Equation.3 1415.
Доказательством или выводом формулы F из множества формул (гипотез) Г называется такая конечная последовательность B1, B2 Bs формул, каждая формула которой является либо аксиомой, либо формулой из Г (гипотезой), либо получена из двух предыдущих по правилу m. p., а последняя формула Bs совпадает с F. Если имеется вывод формулы F из множества гипотез Г, то говорят, что F выводима из Г, и пишут Г
· F. Если же имеется вывод F из пустого множества гипотез, то говорят, что F выводима из аксиом или что F доказуема. В таком случае F называют теоремой и пишут
· F. Если Г = {F1,F2Fm}
· G, можно писать F1,F2Fm
· G.
Поскольку в аксиомах не участвуют связки 13 EMBED Equation.3 1415, то они вводятся с помощью следующих определений: 13 EMBED Equation.3 1415обозначает 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415 обозначает 13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415 обозначает 13 EMBED Equation.3 1415.
Вывод формулы представляет собой последовательность формул, сопровождаемых указаниями, является ли данная формула гипотезой, аксиомой или получена из других формул по некоторому правилу вывода. Принято вначале выписать все гипотезы и слева указывать номер шага вывода.
Пример 3.1.
Построить вывод формулы A
· B (A.
(1) A – гипотеза;
(2) A (
·(B (
·A) – аксиома (А1);
(3) 13 EMBED Equation.3 1415 – из (1) и (2) по m. p.
Любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: 13 EMBED Equation.3 1415. Равносильность A (
·B
·
·
·B (
·A порождает закон контрапозиции: 13 EMBED Equation.3 1415.
Некоторые правила вывода исчисления высказываний.
1. Введение конъюнкции: 13 EMBED Equation.3 1415.
2. Удаление конъюнкции: 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
3. Отрицание конъюнкции: 13 EMBED Equation.3 1415.
4. Введение дизъюнкции: 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
5. Удаление дизъюнкции: 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
6. Отрицание дизъюнкции: 13 EMBED Equation.3 1415.
7. Введение импликации: 13 EMBED Equation.3 1415.
8. Удаление импликации: 13 EMBED Equation.3 1415 (m. p.) и 13 EMBED Equation.3 1415.
9. Отрицание импликации: 13 EMBED Equation.3 1415.
10. Введение эквивалентности: 13 EMBED Equation.3 1415.
11. Удаление эквивалентности: 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415.
12. Введение отрицания: 13 EMBED Equation.3 1415.
13. Удаление отрицания: 13 EMBED Equation.3 1415.
14. Закон контрапозиции: 13 EMBED Equation.3 1415.
Для построения выводов в исчислении высказываний служит теорема о дедукции: пусть Г – множество формул, A и B – формулы и имеет место вывод: Г, A
·
·B. Тогда имеет место следующий вывод: Г
·
·A (
·B.
Таким образом, если нужно вывести формулу вида A (B из множества формул (возможно, пустого), можно ввести дополнительное допущение A.

Важным следствием теоремы дедукции является правило силлогизма:
A (B, B ( C
· A(C.
Рассмотрим примеры построения вывода в исчислении высказываний.
Пример 3.2.
Обосновать вывод A (
·(B (
·C), A(B
· C.
A ( (B (
·C) – гипотеза;
A(B – гипотеза;
A – из (2) и правила удаления конъюнкции;
B (
·C – из (1), (3) и m. p.
B – из (2) и правила удаления конъюнкции;
C – из (4), (5) и m. p.
Пример 3.3.
Обосновать правильность следующего рассуждения, построив вывод.
Если число целое, то оно рациональное. Если число рациональное, то оно действительное. Число целое. Значит, оно действительное.
Сначала формализуем наше рассуждение, введя следующие высказывания:
A = “число целое”.
B = “число рациональное”.
C = “число действительное”.
Нужно построить следующий вывод: A (
·B, B (
·C, A
· C.
Построим этот вывод.
A (
·B – гипотеза;
B (
·C – гипотеза;
A – гипотеза;
A (
·C – из (1) и (2) по правилу силлогизма;
C – из (3) и (4) по m. p.

3.2. Автоматическое доказательство теорем. Метод резолюций
Пусть имеется множество формул Г = {A1, A2, , An} и формула B. Автоматическим доказательством теоремы B называют алгоритм, который проверяет вывод A1, A2, , An
·B. Выражение читается следующим образом: "Если посылки A1, A2, , An
·
·истинны, то истинно заключение B".
Проблема доказательства в логике состоит в том, чтобы установить, что если истинны формулы A1, A2, , An, то истинна формула B. Доказательство этого равносильно доказательству общезначимости некоторой формулы. Наиболее эффективно доказательство общезначимости формул осуществляется методом резолюций. Процедура поиска доказательства методом резолюций фактически является процедурой поиска опровержения, т. е. вместо доказательства общезначимости формулы доказывается, что отрицание формулы противоречиво.
При изложении метода резолюций обычно употребляется следующая терминология.
Литерой называется выражение A или
·A. Литеры A и
·A называются контрарными, а множество {A,
·A} – контрарной парой.
Дизъюнкт – это дизъюнкция литер (или элементарная дизъюнкция). Дизъюнкт называется пустым, (обозначается (), если он не содержит литер. Пустой дизъюнкт всегда ложен, так как в нем нет литер, которые могли бы быть истинными при любых наборах переменных.
Рассмотрим применение метода резолюций к исчислению высказываний.
Правилом резолюции называют следующее правило вывода:
13 EMBED Equation.3 1415.
Правило резолюции можно записать в следующем виде: A(B,
·A(C
·B(C.
Дизъюнкт B(C называется резольвентой дизъюнктов A(B и
·A(C по литере A: B(C = resA(A(B и
·A(C).
Если дизъюнкты не содержат контрарных литер, то резольвенты у них не существует. Для дизъюнктов A и
·A резольвента есть пустой дизъюнкт: resA(A,
·A) = (.
Пример 3.4.
Пусть F = A(B(C, G =
·A(
·B(D.
Тогда
resA(F, G) = B(C(
·B(D.
resB(F, G) = A(C(
·A(D.
resC(F, G) не существует.
Метод резолюций соответствует методу доказательства от противного. Условие A1, A2, , An
· B равносильно условию A1, A2,, An,
·B
· (.
Алгоритм построения вывода методом резолюций.
Шаг 1. Все формулы посылок A1, A2, , An и формулу отрицания заключения
·B
·привести к КНФ.
Шаг 2. Выписать множество K дизъюнктов всех посылок A1, A2, , An и отрицания заключения
·B: K={D1, D2, , Dn}.
Шаг 3. Выполнить анализ пар множества K правилу: если существуют дизъюнкты Di, Dj , один из которых Di, содержит переменную Ai, а другой Dj –отрицание (Ai , то соединить эту пару логической связкой дизъюнкции Di(Dj и сформировать по правилу резолюции новый дизъюнкт – резольвенту, исключив содержащих контрарные литеры Ai и (Ai.
Шаг 4. Процесс продолжаем. Если он заканчивается пустым дизъюнктом, то вывод обоснован.
Изложенный алгоритм назывется резолютивным выводом из K.
Возможны три случая.
1. Среди множества дизъюнктов нет содержащих контрарные литеры. Это означает, что формула B не выводима из множества формул A1, A2, , An.
2. После очередного применения правила резолюции получен пустой дизъюнкт. Это означает, что формула B выводима из множества формул A1, A2,, An .
3. Процесс зацикливается, т. е. получаются все новые резольвенты, среди которых нет пустых.
Пример 3.5.
Применить для примера 3.2 A (
·(B (
·C), A(B
· C метод резолюций. Для этого нужно проверить вывод A (
·(B (
·C), A(B,
·C
·
·(.

Алгоритм решения.
Шаг 1. Привести к КНФ формулы A(
·(B(
·C), A(B,
·C.
A((B(
·C) (
·A((B(
·C) (
·A(
·B(C.
Формулы A(B,
·C уже находятся в КНФ.
Шаг 2. Составим множество К дизъюнктов:
К = {
·A (
·B (
·C, A, B,
·C}.
Шаг 3. Построим резолютивный вывод из K. Выпишем по порядку все дизъюнкты из K:

·A (
·B (
·C;
A;
B;

·C;
Вместо пары дизъюнктов, содержащих контрарные литеры запишем их резольвенту (в скобках указаны номера формул, образующих резольвенту):

·B(C. (1, 2)
C. (3, 5)
(. (4, 6)
Вывод заканчивается пустым дизъюнктом, что является обоснованием вывода A (
·(B (
·C), A(B
· C.

3.3. Задания
1. Установить правильность рассуждения, построив вывод исчисления высказываний.
2. Проверить вывод методом резолюций.

Варианты индивидуальных заданий
Вариант № 1
1. На работу в эту организацию принимают, если пройдешь собеседование и будешь аттестован положительно. Его не приняли. Значит, он либо не прошел собеседование, либо не был положительно аттестован.
2. X, B, (
·C(X)(( B
· C.
Вариант № 2
1. Если светофор красный, то проезд не разрешен. Проезд разрешен. Значит, светофор не красный.
2.
·A (
·(B (
·C),
·A ( C,
·B
· C.
Вариант № 3
1. Если треугольник равносторонний, то его углы равны. Треугольник равносторонний. Следовательно, его углы равны.
2. ((X(C ) (
·(B )
· (C.

Вариант № 4
1. Если ограбление совершил Сидоров, то он знает, где находятся похищенные деньги. Сидоров не знает, где находятся похищенные деньги. Следовательно, он не совершал ограбления.
2. A(F, A(
·C, F(D
· C(D.
Вариант № 5
1. Если растение лекарственное, его следует охранять. Это растение не подлежит охране. Следовательно, оно не лекарственное.
2. A, C, (A(C )(
·D, D ( F
·
· F.
Вариант № 6
1. Петров инженер или студент. Он не инженер. Следовательно, он студент.
2.
·A (
·(B (
·C), A ( B,
·C
· B.
Вариант № 7
1. Если студент занимается не систематически, то он не имеет прочных знаний. Если он не имеет прочных знаний, то он не будет хорошим специалистом. Следовательно, если студент занимается не систематически, то он не будет хорошим специалистом.
2. A, A (
·(
·B (C), B ( D,
·C
· D.
Вариант № 8
1. Это вещество может быть кислотой либо солью. Это вещество не соль. Следовательно, это кислота.
2. (A ( C ) ( (
·A (
·B)
· A ( B.
Вариант № 9
1. Если прямая касается окружности, то радиус, проведенный в точку касания, перпендикулярен к ней. Радиус окружности не перпендикулярен к этой прямой. Следовательно, прямая не касается окружности.
2. F (
·C, C ( A, F ( D, D
·( A
· A.
Вариант № 10
1. Если человек знает геометрию, то он знает теорему Пифагора. Этот человек не знает теорему Пифагора. Следовательно, он не знает геометрию.
2.
·B (
·(D ( C), D, C (
·
· A ( B)
· A ( B.
Вариант № 11
1. Если слово ставится в начале предложения, то оно пишется с большой буквы. Это слово написано с маленькой буквы. Следовательно, это слово не стоит в начале предложения.
2. B ( (C ( A),
·B (
·D, D ( C,
· C.
Вариант № 12
1. Если функция четная, то ее график симметричен относительно оси OY. График несимметричен относительно оси OY. Следовательно, функция не является четной.
2. B (
·
·C ( A),
·B ( E, C,
·E
· A
Вариант № 13
1. Если светофор зеленый, то проезд разрешен. Проезд не разрешен. Значит, светофор не зеленый.
2.
·C, D ( C, A ( (
·B ( D), B
· A ( C.
Вариант № 14
1. Если Андрей отсутствовал на работе, он не выполнил задания. Андрей был на работе. Следовательно, он выполнил задание.
2. C ( (B ( A),
·B ( E, C
·A (
·E.
Вариант № 15
1. Плох тот солдат, который не мечтает стать генералом. Этот солдат хорош. Следовательно, он мечтает стать генералом.
2. A ( (C ( B), D ( A, C
· D (
·B.
Вариант № 16
1. Если треугольник равносторонний, то он равнобедренный. Если треугольник равнобедренный, то углы при основании равны. Следовательно, если треугольник равносторонний, то углы при основании равны.
2. A, X (C
· (A (
·C) (
·X.
Вариант № 17
1. Если диагноз подтвердится, то ему придется лечь в больницу. Если он ляжет в больницу, то поездку придется отменить. Диагноз подтвердился. Значит, поездку придется отменить.
2. A ( (C ( B), D ( A, C
·D (B.
Вариант № 18
1. Петров студент или школьник. Он не школьник. Следовательно, он студент.
2. A, A (
·(B (C),
·B (D,
·C
· D.
Вариант № 19
1. Если я устал, то не могу готовиться к занятиям. Если я не смогу приготовиться к занятиям, я не напишу контрольную работу. Я устал. Значит, я не напишу контрольную работу.
2. B (
·(E (C), E, C (
·
· A (
·B)
· B (A.
Вариант № 20
1. Если Сергей победит на соревнованиях, он войдет в сборную страны. Если он войдет в сборную страны, то будет участвовать в чемпионате мира. Следовательно, если Сергей победит на соревнованиях, он будет участвовать в чемпионате мира.
2. G (
·(B (
·C), G( C,
·B
· C.


Тема 4. НЕЧЕТКАЯ ЛОГИКА
Нечеткая логика отличается от двузначной классической логики тем, что если значения истинности высказывания классической логики могут быть только 0 («ложь») и 1 («истина»), то нечеткая логика допускает несчетное число промежуточных истинностных значений для высказываний в интервале [0, 1].
При описании сложных систем, в которых наряду с количественными данными присутствуют неоднозначные качественные данные, приходится использовать нечеткие понятия и рассуждения. Для формализации таких задач Л. Заде разработал основы математического аппарата, опирающегося на понятия нечетких множеств и нечеткой логики.

4.1 Основные понятия нечетких множеств
Пусть М – некоторое множество, рассмотрим какое-либо подмножество А этого множества. Для любого х(М имеем х(А или х(А. Можно ввести характеристическую функцию подмножества А:
13 EMBED Equation.3 1415
Тогда, например, если M={a, b, c, d, e, f, g, h} и A={a, b, c, d}, имеем:
x
а
b
с
d
е
f
g
h

(A(x)
1
1
1
1
0
0
0
0

Для универсального множества М: (х (M (x) = 1.
Множества, для которых характеристическая функция принимает только значения 0 или 1, будем называть четкими. Классическая логика оперирует с четкими множествами.
Для нечетких множеств характеристическая функция может принимать любые значения из интервала [0,1]. Например,
x
а
b
с
d
е
f
g
h

(A(x)
1,0
0,1
0,8
0,7
0,5
0,2
0,0
0,1

(B(х)
0,1
0,3
0,8
0,9
0,5
0,1
0,0
0,0

Для записи нечетких множеств используется обозначение: А={(х, (A (х))| (x(M}. Запись 13 EMBED Equation.3 1415 характеризует степень принадлежности элемента x множеству A.
Для нечетких множеств определены отношение включения (() и равенства (=):
А(В тогда и только тогда, когда (x(M: (A (х) ( (B (х);
А=В тогда и только тогда, когда (x(M: (A (х) = (B (х).
Над нечеткими множествами выполняются операции:
Дополнение А: 13 EMBED Equation.3 1415
Пересечение: 13 EMBED Equation.3 1415
Объединение:13 EMBED Equation.3 1415
А(В={(х, max {(A (х), (B (х)}) | (x(M }.
4.2 Элементы нечеткой логики
Нечетким высказыванием называется высказывание P, степень истинности которого (P можно оценить числом из интервала [0, 1], (P ( [0, 1].
Нечеткой высказывательной переменной X называется нечеткое высказывание X, степень истинности которого может меняться в интервале [0, 1].
Так как степень истинности нечеткого высказывания не связана с сутью высказывания, будем в дальнейшем отождествлять нечеткое высказывание с его степенью истинности аналогично тому, как обычное четкое высказывание отождествлялось с его истинностью или ложностью. Нечеткие высказывания и степень их истинности будем обозначать буквами: P, Q, X, и т. д.
На множестве нечетких высказываний вводятся логические операции, аналогичные операциям алгебры высказываний.
Отрицание нечеткого высказывания:
·P= 1 – P.
Конъюнкция нечетких высказываний: P(Q = min(P, Q).
Дизъюнкция нечетких высказываний: P(Q= max(P, Q).
Импликация нечетких высказываний: P(Q = max (1 –P, Q).
Эквивалентность нечетких высказываний:
P( Q = min (max (1 –P, Q), max (P, 1 –Q)).
Пример 4.1.
Найти степень истинности высказывания
R = (P(Q) ( (P(
·
·P(Q)) при P= 0,9; Q = 0,3.
1. P(Q = min(0,9; 0,3) = 0,3.
2. (P(
·
·P(Q)) = max (1 – 0,9; 0,3) = 0,3.
3. P(Q = max (0,9; 0,3) = 0,9.
4. R = min (max (1 – 0,9; 0,3), max (0,9; 1 – 0,3)) = min(0,3; 0,9) = 0,3.
Множество нечетких высказываний вместе с введенными на них операциями образуют алгебру нечетких высказываний.
Нечеткой логической формулой называется:
любая нечеткая высказывательная переменная;
если P и Q – нечеткие логические формулы, то
·P, P(Q, P(Q, P(Q, P( Q – тоже нечеткие логические формулы;
других формул, кроме построенных по правилам двух предыдущих пунктов, нет.
Пусть P(X1, X2, ,Xn) и Q(X1, X2, ,Xn) – две нечеткие логические формулы. Степенью равносильности формул P и Q называется величина
((P, Q) =13 EMBED Equation.3 1415{ P((1, (2, ,(n) ( Q((1, (2, ,(n)}
Здесь логические операции конъюнкции и эквивалентности имеют смысл, определенный для логических операций над нечеткими высказываниями, причем конъюнкция берется по всем наборам степеней истинности ((1, (2, ,(n) нечетких переменных (X1, X2, ,Xn).
Если ((P, Q) = 0,5, то нечеткие формулы P и Q называются индифферентными.
Если ((P, Q) > 0,5, то нечеткие формулы P и Q называются нечетко равносильными.
Если ((P, Q) < 0,5, то нечеткие формулы P и Q называются нечетко неравносильными.
Степенью неравносильности формул P и Q называется величина
13 EMBED Equation.3 1415(P, Q) = 1 – ((P, Q) .
Пример 4.2.
Определить степень равносильности формул.
P = X(
·Y,
·
·Q=
·
·X(
·Y
·
·при условии, что X и Y
·принимают значения степеней истинности из множества {0,1; 0,3}. Перечислим все возможные наборы значений X и Y
·
A1 = {0,1; 0,1}; A2 = {0,1; 0,3}; A3 = {0,3; 0,1}; A4 = {0,3; 0,3}.
Запишем формулы P и Q с учетом определений логических операций:
P = X(
·Y
·
·
·max (1 –X, Y); Q =
·
·X(
·Y
·
·
·
·1 – X(Y
·
·
·1 – min(X, Y).
Вычислим формулы P и Q на каждом из четырех наборов A1 – A4:
P1 = max (1 – 0,1; 0.1) = 0,9.
P2 = max (1 – 0,1; 0,3) = 0,9.
P3 = max (1 – 0,3; 0,1) = 0,7.
P4 = max (1 – 0,3; 0,3) = 0,7.
Q1 = 1 –
· min( 0,1; 0.1) = 0,9.
Q2 = 1 –
· min(0,1; 0,3) = 0,9.
Q3 = 1 –
· min(0,3; 0,1) = 0,9.
Q4 = 1 –
· min (0,3; 0,3) = 0,7.

Вычислим теперь степень равносильности формул P и Q. Для этого сначала вычислим P((1, (2, ,(n) ( Q((1, (2, ,(n) для всех наборов A1 – A4:
P( Q = min (max (1 –P, Q), max (P, 1 – Q)).
Поэтому
P1( Q1 = min (max (1 – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9.
P2( Q2 = min (max (1 – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9.
P3( Q3 = min (max (1 – 0,7;0,9), max (0,7; 1 –0,9)) = 0,7.
P4( Q4 = min (max (1 – 0,7;0,8), max (0,7; 1 –0,7)) = 0,7.
Окончательно получим
((P, Q) =13 EMBED Equation.3 1415{P((1, (2, ,(n) ( Q((1, (2, ,(n)} = 0,9(0,9(0,7(0,7 = min(0,9; 0,9; 0,7; 0,7) = 0,7.
Формулы P и Q нечетко равносильны.
На других наборах степеней истинности нечетких переменных X и Y формулы P и Q могут быть нечетко неравносильны.
4.3. Задания
Определить степень равносильности формул P и Q
·при условии, что X и Y
·принимают значения степеней истинности из множества {0,1; 0,5}.

Варианты индивидуальных заданий

P
Q

P
Q

1
X (( Y
X ((Y
11
(X ( Y
X (( Y

2
(X ( Y
X ( Y
12
X ( Y
(X ( Y

3
X ((Y
X (( Y
13
X (( Y
X ((Y

4
X ( Y
X ( (Y
14
X ((Y
X ( Y

5
X ( (Y
(X ( Y
15
(X ( Y
X ( (Y

6
X ( Y
(X ( Y
16
X ( (Y
X ( Y

7
(X ( Y
Y ( X
17
Y ( X
(X ( Y

8
Y (( X
(X ( Y
18
(X ( Y
Y (( X

9
(Y ( X
Y ( (X
19
Y ( (X
(Y ( X

10
(Y (( X
Y ( X
20
Y ( X
(Y (( X




Тема 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
5.1. Понятие алгоритма
Для устранения нечеткости интуитивного понятия алгоритма были предложены точные математические модели алгоритма, например такие, как машина Тьюринга, система рекурсивных функций, нормальные алгоритмы Маркова. С помощью этих моделей алгоритма доказана алгоритмическая неразрешимость ряда важных задач математики и вычислительной техники.
Алгоритмическая неразрешимость некоторой задачи означает, что не существует общего алгоритма, решающего любую задачу рассматриваемого класса, но для отдельных подклассов алгоритмически неразрешимой задачи может существовать алгоритм.
Формализация понятия алгоритма необходима как для доказательства отсутствия алгоритма решения какой-либо задачи, так и для изучения работы вычислительных устройств, реализующих алгоритм.
В разделе рассмотрено одно из формальных описаний интуитивного понятия алгоритма – машина Тьюринга.
5.2. Машина Тьюринга
Машина Тьюринга – абстрактная машина, математическая модель идеализированного вычислительного устройства. Машина Тьюринга полностью определяется:
а) внешним алфавитом A = {a0, a1,... an}, где a0 – символ пустой ячейки;
б) алфавитом внутренних состояний Q = {q0, q1,...qm}, где q0 – состояние остановки: попав в него машина прекращает работу; q1– начальное состояние: в этом состоянии машина начинает работать;
в) программой, т.е. совокупностью команд T(i,j) (i=1, , m; j=0, 1,, n), каждая из которых имеет вид: ajqi(arSqk, где S – предписание лентопротяжному механизму машины (сдвиг), S = L, если сдвиг влево, S = R, если сдвиг вправо, S = C, если каретка остается на месте. Условие однозначности требует, чтобы для любого j и любого i имелась только одна команда указанного вида.
Машина Тьюринга состоит из ленты и управляющего устройства (УУ) со считывающей и записывающей головкой (кареткой) (рис. 5.1).



















Рис. 5.1. Схема машины Тьюринга

Лента жестко закреплена слева и бесконечна справа. Иногда считают, что лента не ограничена справа и слева. Лента разделена на ячейки, которые нумеруются натуральными числами. В каждую ячейку ленты заносятся символы внешнего алфавита машины Тьюринга. Головка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, то стоит против некоторой ячейки ленты; говорят, что головка обозревает эту ячейку. За единицу времени (шаг) головка может сдвинуться на одну ячейку влево или вправо. Головка может распознать содержимое обозреваемой ячейки, заносить символ внешнего алфавита в текущую ячейку и стирать содержимое текущей ячейки (записывать туда пробел). Управляющее устройство может находиться в одном из множества дискретных состояний.
Словом называется последовательность P = ai1, ai2, , ais символов, записанных в ячейках ленты, где ai1 – символ, находящийся в самой левой непустой ячейке, а ais – символ, находящийся в самой правой непустой ячейке. Количество символов в слове называется длиной слова.
Пусть в некоторый момент времени t на ленте записано слово P, управляющее устройство находится в состоянии qi, а каретка – напротив символа aim слова P. Конфигурацией машины в момент времени t называется последовательность K = ai1, , ai(m – 1), qi, aim , ais. Конфигурации в начале и в конце работы называют соответственно начальной и заключительной.

Пример 5.1.
Машина с внешним алфавитом A = {1, a}, алфавитом внутренних состояний Q = {q1, q2} и программой
1q1(1Rq1,
aq1(1R q1,
из любой начальной конфигурации будет работать бесконечно, заполняя единицами всю ленту вправо от начальной точки.
Порядок работы машины Тьюринга задается в виде таблицы. В каждый столбец верхней строчки заносятся символы внутреннего алфавита, в каждую строчку первого столбца – символы внешнего алфавита. В ячейках на пересечении других столбцов и строчек помещаются команды.
Если на пересечении какой-либо строки и какого-либо столбца получим пустую клетку, то это означает, что в данном внутреннем состоянии данный символ встретиться не может.

Таблица 5.1
A
Q
q0
q1

qi
qn

a0
a1

aj

am









arSqk



Формат команды: aSq, где a – новое содержимое текущей ячейки (символ внешнего алфавита, который заносится в ячейку); S – команда лентопротяжному механизму (влево, вправо, стоп); q – новое внутреннее состояние машины Тьюринга. Работа машины на основании заданной программы происходит следующим образом.
Предположим, что в данный момент времени машина Тьюринга находится во внутреннем состоянии qi, а в обозреваемой головкой ячейке ленты находится символ aj. Тогда машина переходит к выполнению команды arSqk в ячейке, на пересечении столбца qi и строки aj:
1) в текущую ячейку ленты заносится новый символ ar ;
2) происходит сдвиг головки влево (S = L), или сдвиг головки вправо (S = R), или головка остается неподвижной (S = C);
3) машина переходит в новое внутреннее состояние qk.
Возможные случаи останова машины Тьюринга:
1) в ходе выполнения программы машина дойдет до выполнения команды остановки; программа считается выполненной (результативная остановка);
2) машина никогда не останавливается, происходит зацикливание.
Данные машины Тьюринга – это слова во внешнем алфавите ленты. На ленте записывается и исходные данные, и конечный результат. На ленте могут быть записаны последовательности слов. Между словами ставится специальный символ – разделитель, пробел или, например, символ (. Натуральное число a представляется словом 11= 1a, состоящим из a единиц. Например, числу 3 соответствует слово 111.
Пример 5.2.
Построить машину Тьюринга, которая производит сложение двух натуральных чисел a и b. Сложить два числа a и b – значит слово 1a ( 1b преобразовать в слово 1 a+b. Это можно сделать, удалив в записи a(b символ разделителя ( и сдвинув первое слагаемое ко второму. Такая машина может быть задана таблицей 5.2.
Внешний алфавит A = {1, (, _}, где ( – символ разделителя, а _ – символ пустой ячейки (пробела). Множество внутренних состояний состоит из трех состояний Q = {q0, q1, q2}.

Таблица 5.2
A
Q
q0
q1
q2

1
*
_
_Rq1
_Rq1

1Rq1
1Lq2
_Cq1
1Lq2

_1Rq1


Начальное и конечное состояния ленты для случая a = 5, b = 3 представлено на рис. 5.2 a и б.

a)




1
1
1
1
1
(
1
1
1




б)





1
1
1
1
1
1
1
1



Рис. 5.2. Схема машины Тьюринга, выполняющей сложение двух натуральных чисел

5.3. Задания
Постройте машину Тьюринга, которая заданное входное слово P преобразует в выходное слово R. В начальном положении обозревается крайняя левая ячейка на ленте.

Варианты индивидуальных заданий


P
R

P
R

1
2
3
4
5
6
7
8
9
10
110
000
000
001
001
001
100
100
100
100
1100
0001
111
0010
0011
110
1000
1011
1100
1001
11
12
13
14
15
16
17
18
19
20
010
010
010
011
011
011
101
101
101
101
0100
0101
101
1010
1011
010
1010
1011
010
0001




Список литературы
Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов: учеб. пособие / И.А. Лавров, Л.Л. Максимова. – М.: Наука, 1984. – 223 с.
Гуц А.К. Математическая логика и теория алгоритмов: учеб. пособие / А.К. Гуц. – Изд-во Либроком, 2009. – 120 с.
Непейвода Н.Н. Прикладная логика: учеб. пособие / Н.Н. Непейвода. – Ижевск: Изд-во Удмурского университета, 1997. – 385 с.
Новиков П.С. Элементы математической логики / П.С. Новиков. – М.: Наука, 1973. – 400 с.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие / В.И. Игошин. – М.: Издательский центр «Академия», 2005. – 304 с.
Математическая логика и теория алгоритмов: метод. указания / сост. С.А. Казаков, Н.А. Правоторова. – М.: Изд-во МГАПИ, 2002. – 45 с.
Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов. – СПб.: Изд-во «Лань», 2005. – 400 с.
Потапов В.И. Компьютерная арифметика и алгоритмическое моделирование арифметических операций: учеб. пособие / В.И. Потапов, О.П. Шафеева. – Омск: Изд-во ОмГТУ, Гриф УМО. 2005. – 96 с.
Анкудинов Г.И. Математическая логика и теория алгоритмов: учеб. пособие / Г.И. Анкудинов, И.Г. Анкудинов, О.А. Петухов. – СПб.: Изд-во СЗТУ, 2003. – 104 с.


































Редактор Л.И. Чигвинцева
Компьютерная верстка О.Г. Белименко
ИД № 06039 от 12.10.2001
Свод. темплан 2009 г.
Подписано в печать 11.09.09. Формат 60х84 1/16. Отпечатано на дупликаторе.
Бумага офсетная. Усл. печ. л. 2,5. Уч.-изд. л. 2,5. Тираж 200 экз. Заказ 601.

Издательство ОмГТУ. Омск, пр. Мира, 11. Т. 23-02-12
Типография ОмГТУ














































13PAGE 15











13 PAGE \* MERGEFORMAT 144015



УУ










Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeGEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

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

  • doc 270523
    Размер файла: 598 kB Загрузок: 0

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