МАТЕМАТИЧЕСКАЯ ЛОГИКА
Математическая (теоретическая, символьная) логика – нормативная
наука о формах и приемах интеллектуальной познавательной
деятельности, осуществляемой с помощью искусственных
(формальных и формализованных) языков. Иначе, математическая
логика – анализ рассуждений (в первую очередь, их формы, а не
содержания).
Основными разделами математической логики является: логика высказываний,
логика предикатов, металогика.
Логика высказываний, как и логика предикатов, имеет два аспекта: семантический,
когда она является содержательной теорией логических отношений между
суждениями; синтаксический, когда логика является методом дедуктивной
формализацией содержательных теорий.
Замечание.
1) Согласно П.Г.Порецкого математическая логика есть логика по
предмету, математика по методу, а согласно Г.Фреге математическая
логика изучает логику математики путем ее дедуктивной формализации.
2) Математическая логика есть современный этап в развитии формальной
логики – науки о построении правильных заключений (доказательств,
опровержений) чисто формальным путем, когда исходят из вида
(логической формы) посылок, а не их содержания.
3) Логика, в отличие от математики (изучающей количественные
отношения и пространственные формы) изучает не количественные
отношения между объектами.
4) Математическая логика пришла на смену традиционной(описательной)
формальной логике во 2-ой половине 19в.-начале 20 века.
5) Познание объясняется следующим деревом:
ощущение
Чувственные
формы познания

представление

Способы
познания

Рациональные
формы познания

понятия
высказывание

Познание
(процесс
гомоморфного
отображения
действительности)

восприятие

Приемы
интеллектуального
(рационального,

теории
Логические приемы
образования форм познания

дедукция
индукция
аналогия

Логические приемы
оперирования с
формами познания

1

6) Основными объектами математической логики являются: высказывания
и логические процедуры. Поскольку все научные знания, процессы
управления
и
др.
формулируются,
как
последовательность
утвердительных повествовательных предложений (т.е. высказываний
субъектно-предикатной структуры).
7) Науки, предложения которых преимущественно получаются как
следствия некоторых общих принципов, постулатов, аксиом, принято
называть дедуктивными, а аксиоматический метод, посредством
которого выводы этих частных предложений, часто называют
аксиоматико-дедуктивными.
8) Основная задача логики – отделение правильных схем рассуждения
(умозаключения, доказательств – мыслительного процесса, в ходе
которого из одного или нескольких суждений, называемых…….,
выводится новое суждение, называемое заключением или следствием) от
неправильных и систематизации первых.
ПАРАДИГМЫ ФОРМАЛЬНОЙ ЛОГИКИ.
1) Правильность рассуждения (умозаключения, вывода, доказательства)
зависит только от его формы и не зависит то его конкретного содержания.
2) Истинность и правильность мышления суть различных объектов:
- истинность
характеризует
рассуждение
в
его
отношении
к
действительности;
- правильность характеризует рассуждение в его отношении к законам и
правилам логики.
Пояснение. Различие между истинностью и правильностью отчетливо
видно в тех случаях, когда формально правильное рассуждение
приводит к логическому высказыванию.
Пример. Все металлы – твердые тела.
Ртуть – не твердое тело.
Ртуть - не металл.
Это правильное умозаключение логично (из-за логики первой посылки).
ПРЕДМЕТ, ЦЕЛЬ, ЗАДАЧИ И СОДЕРЖАНИЕ ЧИТАЕМОГО КУРСА
ЛЕКЦИЙ.
Предметом читаемого курса являются функциональные и формальные
системы логики: алгебры логики (высказываний и предикатов),
классические и неклассические исчисления высказываний и
предикатов, метатеория логических исчислений.
Целого преподавания дисциплины будущим инженерам в области ВТ является
овладение студентами основами синтеза и анализа дискретных структур методами
алгебры логики и логических исчислений.
Задачи дисциплины:
- освоение предметных языков логики высказываний и логики предикатов;
- приобретение навыков использования дедуктивных методов вывода
заключений из посылок;
2

- умение работать с различными моделями формального уточнения понятия
“алгоритм”.
Содержание
читаемого курса представим следующим деревом:
Математическая
логика

F.S=<L, D>
А=<F,

АB

Логическое
исчисление
Прикладные
исчисления

АП
Метатеория
логических
исчислений

B=< L(B), D(B)>

Классическое п

п=< L(в), D(в)>

неклассическое В

неклассическое п
Классическое В

Многозначное В

Здесь:
А=<F, - функциональная система (т.е. построение математической логики, как
теории, является содержательной):
F.S=<L, D> - формальная система (т.е. построение математической логики, как
теории, является чисто синтаксическим объектом);
 - исчисление ( в - исчисление высказываний; п - исчисление предикатов);
L – язык (L(в) – язык исчисления высказываний, L(п) – язык исчисления
предикатов),
т.е.
множество
синтаксически
правильно
построенных
выражений(формы F).
D – дедуктивные средства (D(в) – дедуктивные средства исчисления высказываний,
D(п) – дедуктивные средства исчисления предикатов);
АB = < B, B2  - алгебра логики высказываний;
АB = < Р(Х1, …, Хn),  ,B2,  - алгебра логики предикатов.
Примечание. В том случае, если между морфологическими элементами формальной
системы F.S. и элементами содержательной системы А существует функциональная
биекция, то все исходные
положения F.S. получают интерпретацию. Говорят, что интерпретированная F.S.
есть язык, описывающий ту или иную предметную область.

3

МЕСТО ЧИТАЕМОГО КУРСА О ЗАКОНАХ И ФОРМАХ ПРАВИЛЬНОГО
МЫШЛЕНИЯ.
Логика
Диалектическая логика

Дедуктивные (достоверные)
логики

Индуктивные
(правдоподобные)
логики

Металогика (методология
дедуктивных наук)

Формальная логика (наука о
законах выводного знания)
Традиционная
(описательная)
логика

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

Нечеткая
логика

Четкая логика
Классическая логика

Антична
я логика

Неклассичес
кие логики

Конечнозначные
логика

Формальные
системы

Бесконечнозначные
логика
метатеории

Вероятностная
логика

Счетнозн
ачная
логика

исчисления

Функциональные
системы
Алгебра логики
высказываний
Алгебра логики
предикатов

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

Мышление как
объект изучения.
Науки,
изучающие
мышление

Мышление
человека

Науки, изучающие
объективный мир

Мышление как
познание
объективного мира

логика
Философия,
физиология,
психология,
кибернетика.

Естественные науки

Общественнополитические науки

Умозаключения в логике делят на дедуктивные и индуктивные.
2) Дедукция – переход от общего к частному по правилам логического
вывода, позволяющие получить из истинных посылок(известных знаний)
истинное заключение (новое знание, т.е. выводное знание).
3) Индукция – переход от частного к общему. В отличии от дедуктивных
рассуждений(построений) индукция не гарантирует истинного
заключения при истинности посылок. Принято дедуктивную логику
называть достоверной, а индуктивную логику – правдоподобной
(проблемотичой). Деление выводов(умозаключений в традиционной
логике) в современной логике на правильные и неправильные означает
различие отношения логического следования на два вида – дедуктивные
и индуктивные.
4) Формальная логика – наука о законах выводного знания, т.е. знания,
полученного из раннее установленных и проверенных истин (без
обращения в каждом конкретном случае к опыту) только с помощью
законов и правил логического мышления. В соответствии с основным
принципом логики правильность рассуждения (умозаключения,
доказательства, вывода) зависит только от его формы и не зависит от его
конкретного содержания.
5) Традиционная (описательная) логика, как совокупность…………..,
изучает общечеловеческие законы правильного построения и сочетания
мыслей в рассуждениях, общечеловеческие формы мыслей (понятия,
суждения) и формы умозаключений, а также средства мысли
(определения, как отношения между понятиями; принципы образования
понятий; суждений, умозаключений),необходимых для рационального
(языкового) познания в любой области человеческой деятельности.
6) Математическая логика (как современный этап развития формальной
логики) изучает логику содержательных теорий (т.е. множество
взаимосвязанных понятий и высказываний, замкнутое относительно
логической выводимости) средствами математики, а логику самой
математики – с помощью различного рода исчислений.
Замечание. Отличие математики от логики поясним вопросами, ответы на
которые они ищут.
5

Сколько?

Вопросы
математики

Как далеко?
Как долго?
(т.е. вопросы о
количественных
отношениях)

Что это значит?
Вопросы
логики

Есть ли
противоречие в этом
суждении?

Каковы
основания
(т.е. вопросы о
неколичественных
отношениях)

7) Нечеткая логика – логика, истинностные значения высказывания
которой интерпретируются нечетким подмножеством заданного
множества значений.
8) Четкая логика – логика, в которой для интерпретации высказываний
используется множество истинностных значений М. Говорят, что
логика называется:
классической (двузначной), если |M|=2, т.е. М={0,1} или М={U,};
неклассической (многозначной), если |M|>2;
бесконечнозначной, если |M|=N (это т. н. счетнозначные логики) или |M|=D
(это т.н.
логики);
вероятностной, если истинностные значения М представляются
вероятностями; степенями правдоподобия высказываний);
темпоральной(временной), если элементы М зависят от времени;
модальной, если алфавит ее языка включает связки, интерпретируемые как
“возможно, что…”
9) Формальная система – уточнение понятия аксиоматической теории,
характеризующееся представлением последней в виде исчисления.
10) Исчисление – дедуктивная система, т.е. способ задания того или иного
множества путем указанных аксиом и правил вывода, каждое из которых
описывает, как строить новые элементы из исходных и уже
построенных.
11) Функциональная система – множество функций с некоторым набором
операций, применяемых к этим функциям и приводящих к получению
других функций из этого множества.

-

6

КОНЦЕПТУАЛЬНЫЙ БАЗИС МАТЕМАТИЧЕСКОЙ ЛОГИКИ.
С синтаксической точки зрения в математической логике различают символы
переменных, термов и формул, а с семантической точки зрения – высказываний,
терминов, предикатов и логических операторов. Поясним эти символы с помощью
дерева:
Основные понятия
математической
логики

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

Простые
высказывания
Сложные высказывания
метавысказывания

термы

Логические
переменные

Предметные переменные
Пропозициональные
переменные
Лингвистические
переменные
Предикатные переменные

Логические
функции

Субъекты

Логические
формулы

Метапеременные

Логические операторы
Однородные
логические функции

метатермbys

Истинностные
значения

Неоднородные
логические функции
(предикаты)

метаформулы
Пропозициональные
формулы

Метафункции

Предикатн
ые
Здесь:
А. Высказывание – абстракция осмысленного повествовательного предложения
естественного языка, для которого имеет смысл говорить о его истинности или
ложности (это пояснение, а не определение, понятие “высказывание” в классической
логике).
 Простые высказывания.
Примеры:
1) Вычислительная система есть программно-аппаратный комплекс.
2) 57=35
Эти два предложения являются простыми (атомарными, элементарными)
истинными высказываниями.
Примеры:
3) 3
4) Волк есть дикая кошка.
7

Эти два простых высказывания являются ложными.
5) Денис скоро будет космонафтом.(не высказывание,т.к. будущее время)
Предостережения:
- предложение “Всякий вечный двигатель работает без бензина ” и “ Земля
вращается быстро ” не являются истинными, но в тоже время не являются и
ложными. Поэтому эти предложения не являются высказываниями
(очевидно, что первое предложение является бессмысленным, а второе –
неопределенно-истинно);
- предложение Х+7=9 не является высказыванием, а есть высказывательная
форма (при указании конкретного значения Х имеем высказывание).
Следует отметить, что всякое простое,бескванторное, категоричное высказывание
имеет субъектно-предикатную структуру (т.е.
логическую форму, способ
содержательных частей) вида a  P ( или сокращенно P(a)), где a – субъект (субъект
указывает на тот объект, о котором идет речь в высказывании);
P – предикатный терм (предикатный терм, иначе, логическое сказуемое, указывает
на свойство субъекта);
 - оператор предикации;
 Сложные высказывания.
Примеры:
1) Волга – самая короткая река России и в ней живут киты;
2) 3+7=9 аналогично 7+3=2
Эти два высказывания, каждое из которых составлено из двух простых ложных
высказываний, являются сложными (составными, молекулярными) ложными
высказываниями. Очевидно, что логические формы этих высказываний следующие:

P1(a) P2(a) или (a  P1)  (a  P2),
P3(b) ~ P4(b) или (b  P3) ~ (b P4),
Где: a, b – субъекты (соответственно: Волга и сумма чисел);
P1, P2, P3, P4 - предикатные символы (соответственно: самая короткая река; река, в
которой живут киты; равно 9; равно 2);

логические
связки
(обозначающие
соответственно
“и”
и
“аналогично”),позволяющие строить из простых высказываний сложные.
 Метавысказывания – это высказывание, субъект которого указывает на
другое высказывание.
Пример. Пусть имеем высказывание P(a) , тогда высказывание “ P(a) - ложно ” о
высказывании P(a) есть метавысказывание. Очевидно, на основе высказывания P(a)
можно построить неограниченное количество метавысказываний различной степени
сложности. Так, например, метевысказыванием будет “высказывание “ P(a) - ложно”
- истинно”. Поскольку в математической логике сложное высказывания
представляют замкнутой формулой, то высказывание о ее доказуемости
(недоказуемости, выполнимости) является метавысказыванием. При этом в целях
упрощения записи метавысказываний используются оператор логического
следования и оператор дедуктивной выводимости. Так, метевысказывание
8

___
“формула” P(a) P(a)” – тавтология” записывается символически |= (P(a) P(a)), а
метавысказывание “ формула“ P(a) P(a) ” – логически доказуема” записывается так |
(P(a)

P(a)).

Б. Терм – языковое выражение для обозначения некоторых эмпирических и
абстрактных объектов. Термы строятся по определенным синтаксическим правилам
в конкретном языке логики. Обычно термы задают с помощью логических
переменных и терминов.
1.
Логическая переменная – символ языка, обозначающий произвольный
объект из некоторого фиксированного множества объектов. В читаемом курсе
логическими переменными являются:
- предметная переменная – переменная, выражающая предмет(субъект,
индивидный объект);
Примеры:
1) Х – студент группы “C”, т.е. P(x) , где
Х – субъект ( на множестве студентов группы “C”; P - является студентом группы
“C”
2) Х+3=5 т.е. P(x) , где х – числовая переменная(т.е. место для подстановки цифр,
обозначающих конкретное число); P – является слагаемым уравнения 1-го порядка.
Р(2)-истинное высказывание.
3) Х сын Y, P(x,y) , где x,y - прямые родственники, P - быть сыном.
Места,которые надо обозначить из множества родственников:
- пропозициональная переменная – переменная, значениями которой
являются высказывания;
- лингвистическая переменная (в нечеткой логике) – переменная, значениями
которой являются субъективные словесные оценки;
- предикатная переменная - переменная, значениями которой являются
предикаты;
- метапеременная – переменная, вместо которой допускается подстановка
других переменных определенного вида.
2.
Термин – символ имени (именной формы) конкретного объекта. Различают
термины:
- индивидные (предметные, субъектные) постоянные (константы);
- логические операторы (составляющие три подмножества – логические
связи, такие как, кванторы, такие, как ; символы
метавысказываний, а именно |=, |
- предикатные термины (двухместные отношения , ;
- истинностное значение – абстрактный объект, выступающий в качестве
характеристического свойства высказывания (в классической логике ={U,

9

}, а в неклассической - || >2; здесь  - множество истинностных
значений для высказываний).
- Метатермин – термин для обозначения множества терминов.
В. Логическая функция – функциональное соответствие на множестве кортежей
длины n>0, принимающее значение в множестве истинностных значений, т.е.
Sf : M1 M2 …  Mk
Различают однородные (пропозициональные) и неоднородные (предикатные)
логические функции, т.е.
1) если M1= M2= … = Mn= , то n - однородная логическая функция (в
частности, если || =2, то пишут f:{0,1}n{0,1}, или f: ВnВ и называют
функциями алгебры логики).
2) Мn - неоднородная логическая функция (в частности, М n{0,1} –
двузначный n-местный предикат)
3) Метафункция метаформулы.
Г. Логическая формула – языковое представление суперпозиции логических
функций. В читаемом курсе будем различать формулы:
1) пропозициональную
–
правильно
построенный
кортеж
из
пропозициональных переменных и логических связок;
2) предикатную – правильно построенный кортеж предикатов, логических
связок и кванторов;
3) метаформулу – кортеж метапеременных и логических операторов (т.е.
метаформула есть логическая форма формул).
Примечание.
- Как правило, определение логической формулы имеет индуктивный
характер:
 Выделяется класс языковых выражений, называемых простыми
(атомарными) формулами;
 Указываются правило, позволяющее из уже построенных
логических формул, строить новые логические формулы, используя
логические операторы.
- формула, подобно терму и переменной, есть семантический объект на
множестве языковых выражений и поэтому с синтаксической точки зрения
должна быть алгоритмически разрешимой.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.
Математическая логика является теорией (т.е. целостной системой абстрактных
объектов, отражающей основные закономерности логического мышления) в том
плане, что ее основными структурными компонентами являются:
1) концептуальный базис (т.е. исходные понятия и основные отношения
между этими понятиями, выраженные в форме аксиом, законов,
гипотез).
2) Дедуктивные средства (т.е. отношение логического следования,
выраженное в форме тех или иных правил логического вывода).
10

3) Содержательная надстройка (т.е. совокупность суждений, выраженных в
форме конкрентных высказываний и теорем, полученных из
концептуального базиса с помощью дедуктивных средств).
В том случае, когда абстрактные объекты теории отображаются с помощью
формального или формализованного языка L=<A,S> (соответственно, L1=<A,S> ,
L2=<A, S1, S2> , где А – алфавит символов, S1 – синтаксические правила построения
языковых выражений FA* , S2 - семантические правила ) и явным образом
определены постулаты D (т.е. аксиомы Ax  F A* и дедуктивные средства P  Fn+1),
то говорят о построении теории как формальной системы F.S. = <L, D> = <A, S, Ax,
P> <A, F, Ax, P>. Примером так построенной теории в читаемом курсе будут
рассмотрены
исчисления высказываний и предикатов (это т.н. логические
исчисления).
Другим подходом к построению математической логике является - содержательный,
т.е. неформальный. В этом случае аксиомы и дедуктивные средства явным образом
не определяются (т.е. постулаты в таком построении теории используются
интуитивно). Примером содержательно построенной математической логикой
является алгебра логики – алгебра высказываний А 1=<{U, }, , , > и алгебра
предикатов А2=< F, , {U, }2{U, },  > (где F – множество предикатных
формул,  - символ отрицания, {U, }2{U, } – бинарные логические связки, квантор всеобщности,  - квантор существования).
Замечания.
1) Содержательная надстройка современных теорий строится на основе
точно заданного концептуального базиса нечетко определенных
дедуктивных средств.
2) Необходимым, но недостаточным условием научной состоятельности
теории является ее внутренняя непротиворечивость.
3) Логические исчисления являются важнейшей разновидностью
формальных систем F.S. От других формальных систем ( например,
интегрального
и
дифференциального
исчисления)
логические
исчисления отличаются чисто логическим пониманием правильно
построенных языковых выражений FA* и правил вывода P : (F1, F2,…, Fn,
Fn+1)  Fn+1

4) На основе логических исчислений строятся ( путем присоединения
некоторых дополнительных аксиом) прикладные исчисления.
5) Для всякого логического исчисления важное значение имеет вопрос о
его непротиворечивости, независимости, полноте, разрешимости.
6) Говорят, что всякая интерпретированная формальная система (т.е. когда
L=<A, S1, S2> ) представляет собой формализованный язык, в котором
заданы S1
- правила синтаксиса и S2 - правила семантики
(интерпретации). Именно в этом плане изучаемые в курсе исчисления
высказываний в и предикатов п являются интерпретированными
логическими формальными системами (или логическими языками).
Примером интерпретированных прикладных логико-математических

11

F.S. (или т.н. логико-математических языков) являются различные
аксиоматико-дедуктивные теории множеств.
7) F.S. есть порождающая процедура (т.е. аксиоматико-дедуктивный способ
индуктивного порождения элементов множества из исходных объектов,
рассматриваемых как аксиомы, или разрешаемое подмножество Ax  F),
а интерпретация, как метод, является распознающей процедурой (т.е.
способом
распознавания
принадлежности
объекта
заданному
множеству).
8) Правила вывода P формальной системы < L, D > есть конечное
множество вычисляемых (разрешающих) отношений на множестве
языковых выражений FA*.
Для лучшего усвоения формального построения теории приведем примеры
формальных систем F.S., несвязанных с логическими интерпретациями.
Пример 1. Пусть F.S.= <A, S, Ax, P> есть описание (интерпретация) игры в шахматы,
т.е. F.S. описывает множество допустимых шахматных позиций. В этом случае
алфавит А состоит из 64 клеток доски, занятые фигурами и свободные;
синтаксические правила S порождают множество допустимых позиций F; аксиомой
(единственной) Ax является исходная шахматная позиция; правилами P являются
правила, определяющие следующие ходы (чередование ходов белых и черных
фигур, правила взятия фигур, рокировки, допустимого хода фигур на свободные
клетки) и заключительные позиции – ничейные, матовые.
Пример 2. Фраза русского языка описывается F.S., алфавит которой А – алфавит
русского языка, S – грамматические правила построения слов русского языка F,
аксиомы Ax – слова фразы, а правила вывода P , т.е. правила построения фразы из
слов – правила синтеза фраз в грамматике русского языка.
Пример 3. Формальная грамматика есть формальная система, описывающая
синтаксис искусственного языка. В этом случае алфавит А есть объединение двух
непересекающих подмножеств символов терминального Т и вспомогательного V
словарей (т.е. А=ТV), а формулами – цепочки из этих символов (т.е. FТV*).
Единственная аксиома 
в этой формальной системе является элементом
вспомогательного словаря V (т.е. V), правило вывода позволяет получать
цепочки в терминальном алфавите ( эти цепочки являются словами искусственного
языка – множества, порождаемого формальной грамматикой) и имеют вид h, где
, hТV*. Так, формальная грамматика (система) 
порождает (описывает) множество (язык) нечетных чисел в унарном представлении,
т.е. множество цепочек вида , ,…, 2n-1,… (здесь nN ).
Пример 4. Индуктивное определение можно представить формальной системой,
аксиомы которой перечислены в базисе (первом пункте) определения, а правила
вывода – в индуктивном (втором пункте) шаге. Необходимым условием перехода к
формальной системе в этом случае является разрешимость множества аксиом.
Так, индуктивное определение двухполюсной системы вида
б
12

а

k
с

d

Может быть следующим:
1) объект ха, б, с, д,…, к является схемой, полюсы которой совпадают
с полюсами объекта (язык построения объекта L( может быть описано,
например, какой-нибудь формальной грамматикой)
2) если Сi и Сj – схемы, то

Ci
Ci

Cj

Cj

также схемы (это т.н. правила последовательного p1 и параллельного p2
соединения схем в схему)
3) других схем нет.
В этом случае F.S.= < L (),а, б, с, д,…, к, p1, p2 >
ЯЗЫК КЛАССИЧЕСКОЙ ЛОГИКИ ВЫСКАЗЫВАНИЙ LВ = <AВ, FВ>.
А. Синтаксис языка Л.В,
Перечисленные множества исходных символов алфавита AВ и правил образования
языковых выражений, составляет синтаксис языка логики высказываний (Я.Л.В.).
I. Алфавит Я.Л.В.
AВ = 123; ij = , ij; 1={p, q, x, y,…,p1, q1, x1, y1,… p2, q2, x2, y2,… } –
множество
дескриптивных
(нелогических)
символов,
называемых
пропозициональными термами (переменными). Эти символы используются как
параметры (буквы) простых высказываний (при выявлении логических форм
контекстов естественного языка). 2={} – множество логических символов
(констант), называемых пропозициональными связками. Эти символы являются
терминами, обозначающими логические отношения и образующие
функционально-полную систему (т.е. из них можно выразить любую
логическую функцию).
3={(,) } - множество разделительных (технических) знаков
Примечание.
1) 12 – есть множество значащих символов.
13

2) В языке логики высказываний логические связки получают единую и
постоянную интерпретацию ( - не;  - или;  - и;  - если…то), а
пропозициональные переменные в составе формул и формулы могут
получать различные интерпретации от случая к случаю. Существование
такой интерпретации определяет семантику языка.
II. Языковые выражения Л.В.
Языковыми выражениями в логике высказываний являются формулы,
называемые пропозициональными формулами. Язык формул с переменными
x,y,z порождается формальной грамматикой = <Т, V, , P >, где Т= x,y,z, 
; V ={}, P =хy,
z
Замечание.
1) В алгебре логике формулы Я.Л.В. являются аналитическим способом
представления (реализации, задания) пропозициональной функции {U,
}2{U, }, а в логике высказываний – логическими формами
высказываний.
2) Принять следующие сложные высказывания (задаваемые их логическими
формами, т.е. формулами Я.Л.В.) (ху), (ху), х  у, х называть
соответственно дизъюнктивным, конъюнктивным, импликативным и
отрицанием, связки   - дизъюнкцией, конъюнкцией, импликацией,
отрицанием.
Б. Семантика Я.Л.В.
Интерпретации подлежат пропозициональные переменные и пропозициональные
формулы. Поскольку логические связки имеют постоянную интерпретацию, то
формулы, приобретя тем самым некоторый смысл, представляют собой логические
формы сложных высказываний. В таком смысле пропозициональные формулы
называют полуинтерпретированными. Полная интерпретация формулы получается в
результате приписывания истинностных значений пропозициональным переменным.
В этом случае полностью интерпретированная формула есть некоторое
высказывание Я.Л.В. Поскольку каждой формуле Я.Л.В. можно поставить в
соответствие таблицу истинности, указывающей зависимость истинностного
значения формулы от истинностных значений ее переменных, то имеем для
логических связок их табличное представление.
Пропозициональные
переменные
x


U
U

Пропозициональные формулы
y

U

U

х
U
U



(ху)

U
U
U

(ху)



U

х  у
U
U

U

Использование таких таблиц позволяет вычислить истинностное значение любой
формулы Я.Л.В.
Пример. Вычислить истинностное значение высказывания вида:
14

((ху) х), если х=, у= U. Имеем
Переменные
х


Подформулы
у
U

(ху)
U

Формулы
(ху) х
U

х
U

Т.е. при заданной интерпретации простых высказываний сложное высказывание
истинно. Часто результат интерпретации формулы записывают так:
|((ху) х)| = И при х=, у= U.
Примечание. Для упрощения записи логических форм
1) вводят старшинство связок, а “лишние” скобки опускают;
2) используют производные связки (связки  в таком случае
называют основными).
Пояснения:
1) о соглашениях по сокращению записи формул над множеством логических
связок:
- внешние скобки формул опускаются
_
- формуле х записывается в виде х ;
- формуле (ху) записывается в виде ху ( т.е. скобки и символ операции
опускаются);
- приоритет в последовательности применения связок возрастает в
следующем порядке:  ( т.е. унарная связка  сильнее любой
бинарной операции; связка  - самая сильная бинарная операция).
Эти соглашения позволяют записать формулу:
_

_

((((х) у)  z) ( х (y)  z)) записать в более компактном виде ( ху)zxyz
2) Производные связки для сокращения записи логических выражений
- оператор “эквиваленция”  (интерпретируется как союз естественного
языка “тогда и только тогда”) позволяет формулу (ху)  (ух) записать в
виде ху, т.е. (ху)(ух)= ху (часто  называют оператором
эквивалентности)
- строгая дизъюнкция 
(интерпретируется как союз “либо…либо” )
позволяет формулу (х y)  (х  у) записать в виде х  у (часто вместо
символа  используется символ , т.е. пишут ху);
Введенные связки позволяют легко выявить логическую форму высказывания
“треугольник не является прямоугольным тогда и только тогда, если верно одно из
двух: он либо остроугольный, либо он тупоугольный”. Пусть для этого
высказывания пропозициональными переменными будут х, у, z, т.е.:
х – треугольник прямоугольный,y - треугольник остроугольный, z - треугольник
тупоугольный. Терминам “не” соответствует связка , “тогда и только тогда” - ,
“либо…либо” - . Логическая форма исходного высказывания х  (у z), в Я.Л.В.
имеет вид:
_
_
_ _ _
_ _
_
(х  (у z))( (у z) х) = (хyz  yz)(yz  yzx)
15

Замечание. Высказывание, построенное из других высказываний с помощью
оператора эквивалентности, называют тавтологией.
Пример. Сложное высказывание “Земля по форме есть эллипсоид Красовского тогда
и только тогда, если неверно, что Земля не есть по форме эллипсоид Красовского”.
Это высказывание (его логическая форма 1 2 ) есть тавтология 1 2, где 1 –
первое простое высказывание, а 2 – второе простое высказывание исходного
сложного высказывания.
КЛАССИЧЕСКАЯ ЛОГИКА ВЫСКАЗЫВАНИЙ.
Содержательно пропозициональную логику определяют как раздел математической
логики, формализующей употребление логических связок, служащих для
образования сложных высказываний из простых. Как и любая другая логическая
теория, логика высказываний решает две задачи:
- выделяет среди класса формул множество своих законов;
- устанавливает логические отношения между формулами.
В этом плане формально логику высказываний понимают как определенное на
множестве формул языка логики высказываний отношение логического следования |
= и законов, т.е. < F,|= >, с привлечением таблиц истинности.
а) Законы классической логики высказываний.
Определение. Формула, которая при любых распределениях истинностных значений
ее параметров принимает значение “истина”, называется общезначимой.
Определение. Денотат (т.е. объект обозначения) метевысказывания об
общезначимости пропозициональной формулы называется логическим законом.
Для метавысказывания “А есть логический закон” принять обозначение |=A (здесь А
–
метаформула).
Так,
принцип
исключенного
третьего
выражается
метавысказыванием |= ( , говорящим о том, что общезначимой является
пропозициональная формула ( , а принцип противоречивости выражает
метавысказывание |=(  , говорящее о том, что общезначимой является формула
(  ,
(где  - пропозициональная переменная, |= - оператор логического
следования). При подстановке вместо  любых конкретных высказываний (как
истинных, так и ложных) из формул (  и  (  получаются только истинные
высказывания.
Замечание.
1) Факт общезначимости пропозициональной формулы устанавливается с
привлечением таблицы истинности (пассивный метод) или
эквивалентным преобразованием (активный метод).
2) Каждый закон логики имеет бесконечное множество вариантов
формульного представления. Так принцип исключенного третьего может
быть записан следующими аналитическими выражениями:
|=x x; |=(ху) (ху); |=((xz) (yp)  ((хz)(yp));
3) Тождественно-ложная формула (т.е. формула, имеющая значение “ложь”
на всех значениях истинности ее переменных) являются отрицанием
закона логики.
б) Отношения логического следования и логической эквивалентности.
I.
Из множества формул T логики следует формула В (символическая
запись T |=B, или R(F1, F2,…, Fn , Fn+1=B), где T ={ F1, F2,…, Fn }) в логической
16

теории, если и только если в теории не существует интерпретации нелогических
символов, входящих в T и В, при которой каждая формула из T принимает
значения “истина”, а формула В - значение “ложь”. Иначе, логическое следование
12 - отношение между пропозициональными формулами 1 и 2 такое, что
1 2. В противном случае, т.е. когда формулы T истинны, а В – ложны, то В
не следует из T (символически запись T |В). В логике высказываний
эффективной процедурой (алгоритмом) выявления отношения логического
следования между конечным множеством формул T и формулой В является
таблица истинности.
Пример 1. Проверить правильность умозаключения “Если тело движеися
равномерно и прямолинейно, то на него не действуют силы. Тело движется
равномерно, но не прямолинейно. Следовательно, на тело действуют силы”.
Логическая форма заданного умозаключения имеет вид:
((рq) z)
посылки T
(рq)
заключение
z
здесь р – “тело движется равномерно”
q – “тело движется прямолинейно”
z – “на тело действуют силы”
Таблица истинности умозаключения имеет вид:
Пропозициональные
переменные
p
q
z
U
U
U
U





U
U


U
U



U

U

U

U


посылки
((рq) z)

U
U
U
U
U
U
U

заключение
(рq)

z



U
U


U
U

U

U

U

U


В четвертой строке этой таблицы посылки истинны, а заключение – ложно.
Поэтому из ((рq) z),
(рq) не следует логически z и, следовательно,
умозаключение является неправильным.
Напоминание. Следует различать правильность умозаключения и истинность
заключения. В общем случае ложное заключение может быть получено в
результате следующих умозаключениях:
- все посылки T истинны, а само умозаключение не правильно;
- умозаключение правильно, но в нем есть ложная (ложные) посылки;
- умозаключение не правильно и в нем есть ложная посылка. В этом плане
следует отметить, что если к истинным посылкам T применяется
правильное умозаключение, то с логической неотвратимостью будет
получено истинное заключение В, т.е. T |=В.
17

Пример 2. Согласно легенде обоснования сожжения книг Александрийской
библиотеки :
- если ваши книги согласны с Кораном (р), то они излишни (q), (рq)
- если же ваши книги не согласны с Кораном (р), то они вредны (z), (рz)
- но вредные (z) или излишние(q) книги следует уничтожать(у), (qz) y
Поэтому ваши книги следует уничтожать.
Покажем, что это рассуждение правильно, но заключение ложно. Действительно,
логическая форма рассуждения имеет вид:
рq
рz
(qz) y
y

посылки
заключение

Построив таблицу истинности, заключаем, что (рq), (рz), ((qz) y) |= y.
Аналитически этот результат можно получить, если учесть, что согласно теореме
дедукции:
|=( F1…( Fn В)…)  F1, F2,…, Fn|=В, в нашем случае: надо показать, что
|=((

рq)

((рz)

__


( p

т.е.

y))),

p z

__ __ __

y 

y (q z 

__

((рz)

(((qz)

__ __

q y 

qz 

((рq)

z  (( q

q ( p

__ __ __



(((qz)

__

z y 

__

q z 

z 

y)

y)))=

y )  y )))

__

__

y ) y ( p q 

z) 

__ __

y y ( z 

p

z) 

Пример 3Рассуждение “Если на данное движущееся тело не действуют никакие
силы или равнодействующая всех действующих сил равна нулю, то оно движется
равномерно.
Данное
тело
движется
неравномерно,
следовательно,
равнодействующая всех действующих сил не равна нулю”. Это умозаключение,
логическая форма которого
((рq) r)
r
q

правильно, т.е. ((рq) z), r |=q
действительно:
_
_
__
_
_
__
_
_ __
__
(((рq) r) (rq))  (p qr) (rq)  (p r  q r  r  q)  (p r  q r  r  q rq r )  (p r  r 
_
 r )=u

II. Формулы А и С логически эквивалентны (логически равнозначны), если и
только если из А
логически следует С и из С логически следует А,
т.е. имеет место двустороннее логическое
следование:
A|=C и C|=A
18

__

Из этого определения вытекает, что в каждой строке совместной таблицы
истинности обе логически эквивалентные формулы принимают одинаковые
значения, что можно записать следующим образом АС(АС)(СА). Если
АС и СА тождественно истинны, то АС есть закон, т.е. |= АС.
Примечание. Таблично алгебраическим вариантом логики высказываний является
алгебра логика, имеющая большое прикладное значение в синтезе
комбинационных автоматов. Однако, если в логике высказываний формула
рассматривается как логическая форма высказывания, то в алгебре логики формула
является аналитическим способом представления логической функции f:{0,1}n
{0,1}, где {0,1} заменяют истинностные значения {, И} логики высказываний.
ЯЗЫК КЛАССИЧЕСКОЙ ЛОГИКИ ПРЕДИКАТОВ (Я.Л.П.).
Язык логики предикатов <An,, Fn > является расширением рассмотренного выше
языка логики высказываний.
А. Синтаксис языка Л.П.
Синтаксис Я.Л.П. обусловлен алфавитом An и правилами образования из символов
An языковых выражений термов  и формул Fn
I.
Алфавит Я.Л.П. An
Множество символов An рассматриваемого формализованного языка состоит из
трех подмножеств – дескриптивных терминов 1, логических операторов 2 и
вспомогательных символов 3.
а)Дескриптивные термины 1. Дескриптивными (нелогическими) терминами
редметные (индивидные) константы {a,b,c,d,…,a1,b1,c1,d1,…,a2,…}, n-местные
предметно-функциональные константы {f,g,h,…,f1,g1,h1,…,f2,…}, m-местные
предикатные константы {P,Q,R,S,…,P1,Q1,R1,S1,…,P2,…}, и предметные
(индивидные) переменные {x,y,z,…,x1,y1,z1,…,x2,…} (это пропозициональные
переменные)
Пояснение.
1) При переводе выражений естественного языка на Я.Л.П. объекты
заменяются индивидными константами;
2) n-местные предметно-функциональные константы (n1) соответствуют
предметным функторам естественного языка, таким как “ сложение”,
“вычитание”, извлечение корня, дифференцирование, расстояние от…
до…(вообще, n-местные предметный функтор обозначает n-местную
предметную функцию).
3) m- местные предикаторные константы ( m  1) соответствуют
предикатам естественного языка, т.е. знакам свойств ( например,
горячий, электропроводный, зеленый) и отношений ( например, южнее,
больше, старше). При этом свойства в ЯЛП являются одноместными
предикаторными, а отношения многоместными.
4) Предикаторные символы синтаксически используют для образования
формул, а семантически они обозначают предикаты ( например, xy, x
Y)
Примеры:
1) Космонавт Гагарин – первопроходец космического пространства. По
ЯПЛ- это субъектно-предикатное простое высказывание имеет вид
19

P(f(a)),
где
P-означает
логическое
сказуемое,первопроходец
космического пространства, f(a)- космонавт Гагарин ( т.е. а- Гагарин, fкосмонавт).
2) Микросхема, диод и транзистор- множество с агрегатной точки зрения.
Это высказывание на ЯЛП имеет вид P(a,b, c), где P- множество с
агрегатной точки зрения, a,b,c- элементы множества- соответственно
микросхема, диод, транзистор.
б) Логические операторы ( константы).
Логическими операторами в ЯЛП являются логические связи { , , ,  и
кванторы , .
Пояснения:
1) Кванторам в естественном языке соответствуют кванторы слова типа «
для всех» и «существует».
2) Иногда в ЯЛВ используют так называемый математический базис
операторов, например , , , , , , , , , , , .
3) Связки и кванторы имеют следующий приоритет: , , , , , .
в) Вспомогательные символы
Вспомогательными ( разделительными) символами являются левая и правая
круглые скобки, т.е. Р3= , .
III. Языковые выражения , F.
В ЯЛП имеются два типа правильно построенных выражений из символов Anтермы  и формулы F.
а) Термы .
Термы  являются символической записью предметов естественного языка.
Формально терм можно определить по инструкции:
- произвольная предметная константа является термом;
- произвольная предметная переменная является термом;
- если Ф – n-местная предметно-функциональная константа, а t1…tnтермы, то выражение Ф(t1…tn)- является термом;
- других термов нет, т.е. ничто не является термом ЯЛП;
Замечание:
1)
предметные константы и предметные переменные называют простыми
термами, а Ф(t1…tn)- сложными термами.
2)
Символы, использованные в определении терма ti , Ф – есть
метасимволы ( это не символы объектного языка.
3)
Терм называют замкнутым, если он не содержит предметных
переменных.
Пример:
1) Записать на ЯЛП следующие выражения : 3, 5, 7+2.
Решение:
20

Пусть a, b, c, d – индивидные константы, соответствующие объектам 3, 5, 7,
2.
В этом случае a – простой терм, а f(b) и g(c, d)- сложные замкнутые термы, где
1
f – одноместная предметно-функциональная константа, соответствующая
функтору  , а g2- двуместная предметно-функциональная константа,
соответствующая функтору t.
2) С учетом обозначений объектов в примере 1 выражениям ( 3  x) , ((7+3)),
(7+7)+(2+2), 7+7+2+2 в ЯЛП соответствуют свободно замкнутые термы g2(f1(а),
х), f1(g2(c, d)), g2(g2(c, c), g2(d, d)), g2(g2(g2(c, c), d),d)
3) Естественно-языковые выражения « Столица России», «Расстояние от Москвы
до Тулы», «расстояние от столицы России до Тулы» в ЯЛП соответствуют
замкнутые термы: f1(а), g2(b,c), g2(f(а), c), где a,b,c- соответственно, Россия,
Москва, Тула, f1 «столица», g2 «расстояние от… до…».
Предостережение
Символическая запись h2(g2(х, а)) не является термом, так как в скобках после
двухместного предметно-функциональной константы h2 стоит только один терм
g2(х, а), а не два, как этого требует определение образования сложных термов. Не
является термом и выражение Р1(g2(х, а)), так как Р1- предикаторная константа, а не
функциональная.
б) Формулы Fn
Формулы ЯПЛ Fn являются символической записью логических форм
высказываний и предикатов.
Индуктивное определение Fn:
1) Выражение Пn (t1…tn) является формулой, если Пn- n-местная
предикаторная константа, а t1…tn- термы;
2) Если А- формулам, то  А- формула;
3) Если А и В – формулы, то (АВ), (АВ) и (АВ)- формулы;
4) Если А(х)- формула, а х-свободная переменная, то х А(х) и  х А(х)формулы;
5) Ничто иное не является формулой ЯЛП;
Пояснения:
1) В приведенном определении П, А, В являются символами метаязыка,
значениями которых являются соответственно предикаторные буквы и формулы
объектного ЯЛП.
2) Формула Пn (t1…tn) называется элементарной (атомарной), а формулы пунктов 2,
3, 4 приведенного индуктивного определения принято называть сложными
(молекулярными). Говорят, что сложная формула состоит из подформул (в
пункте 3 это А и В, в 2 и 4 –А).
3) Одноместный предикат П(х) есть логическая формула высказываний «х есть П».

21

Примеры:
1) Р2(х, f1(а)), Q2(h, g2(a, x), R1(x), S1(c) – элементарные предикаторные формулы,
где Р2 , Q2 – двухместные предикаторные константы, а R, S – одноместные, а в
скобках находятся термы. Однако выражения Р2(х, f1(а)), Q2(h, g2(a, x), R1(x),
S1(c) не являются формулами ЯЛП.
2)Выражение Р2(х, Q1(а)) – не формула ЯЛП, так как Q1(а) не является термом.
3) Выражение х Р2(х, f1(а)) и х Q2(х, f1(а)) являются формулами ЯЛП согласно
пункту 4 индуктивного определения Fn. Однако, выражения  Р2(х, f1(а)),  Q2(х,
f1(а)), а Р2(х, f1(а)), а Q2(х, f1(а)) не являются формулами ЯЛП, так как в
первых двух выражениях нет кванторных переменных, а в 3-м и 4-м после
кванторов стоит предметная константа, а не предметная переменная. Очевидно,
что х g2(x, f1(a)) и x Q2(b, f1(а)) не являются формулами ЯЛП навешиваются
на высказывательнюю формулу, а не на терм. (Q2(х, f1(а)) – замкнутая, а не
высказывательная формула.)
В дальнейшем будем пользоваться терминологией.
1) Предметная переменная формулы называется ее вхождением в
формулу.
2) В формулах х А(х) и  х А(х) подформула А называется областью
действия кванторов  и  по предметной переменной х (А –
метаформула).
3) Переход от Р(х) к х Р(х) и  х Р(х) – называется связыванием
предметной переменной х (навешиванием квантора на переменную х,
квантификацией переменной х).
4) Переменная, на которую навешивается квантор, называется связанной
переменной, несвязанная переменная называется свободной.
5) х Р(х) является высказыванием ( замкнутой формулой), а Р(х) –
переменной высказывание, то есть незамкнутая формула.
6) Одна и та же переменная может быть и свободной и связанной в
некоторой формуле.
Пример:
В формуле х(у  Р2(х, у) Q2(у, z)) областью действия квантора  по переменной
х является подформула у  Р2(х, у) Q2(у, z), а областью действия квантора  по у
– подформула  Р2(х, у). В рассматриваемой формуле переменная х имеет два
вхождения, у – три, z – одно. Первые вхождения переменных х и у связаны,
поскольку они следуют непосредственно за кванторами  и . Второе вхождение х
находится в области действия квантора  по х в подформуле у
 Р2(х, у)
Q2(у, z), а второе вхождение у расположено в подформуле  Р2(х, у). Поэтому
вторые вхождения х и у являются связанными. Третье вхождение у и единственное
вхождение переменной z в подформуле Q2(у, z) являются свободными.
Следует отметить, что:
1) Сформулированный выше синтаксис ЯЛП называют первопорядковым
в том смысле, что в этом языке разрешается квантификация только
предметных переменных. Если же разрешить квантификацию
22

введенных
в
алфавит
первопорядкового
ЯЛП
предметнофункциональных и предикаторных переменных , то говорят о ЯЛП
более высокого, чем первый порядка. В этих языках возможна
квантификация по предикаторам, то есть выражения типа р(Р(х)), и
функторам , то есть f(f(x));
2) ЯЛП, не содержащий предметных констант и предметтнофункциональных констант, называется языком чистого исчисления
предикатов.
Примеры перевода простых высказываний естественного языка и их отрицаний на язык
логики
предикатов.

а) Высказывания без кванторных слов.
Примеры:
1) Переводом высказывания «Сократ-идеалист» может быть предикатная
формула Р1(а), где предметная константа а соответствует имени Сократ, а
одноместная предикаторная константа Р1- знаку свойства «идеалист».
2) Высказывание «Учитель Платона мудр» может быть записано в виде
Q1(f1(b)), если одноместному предметному функтору «учитель» сопоставить
одноместную константу f, знаку свойства «мудр» - одноместную предикатную
константу Q1, имени Платон – предметную константу b. Зная, что «учитель
Платона» имеет значение «Сократ», высказывание «Сократ мудр» имеет
формальное представление Q1(а), то есть a=f1(b).
3) Высказывание «Учитель Платона является идеалистом» может быть записано
в виде предикатной формулы  Р1(f(b)) (здесь Р – идеалист, f1(b)- учитель
Платона).
4) Высказывание «Сократ достоин Платона» может быть формализовано
предметной формулой R2(a, b), где R – двухместный предикаторный символ
«достоин», а индивидные константы a и b соответствуют именам Сократ и
Платон. Очевидно, что в приведенной интерпретации выражение ЯЛП: R2(b,
а) есть высказывание «Платон достоин Сократа», R2(а, а) – «Сократ достоин
сам себя», R2(b, f1(b)) – «Платон достоин своего учителя»,  R2(f1(а), f1b)) –
«Учитель Сократа не достоин учителя Платона»
5) Высказывание о наличии трехместного отношения между тремя объектами
«Сократ достоин Платона больше, чем своего учителя» в ЯЛП имеет вид S3 (а,
b, f1(а)) , где
S3 – трехместная предикаторная константа, соответствующая
отношению «…достоин…больше, чем…». Очевидно, формальное выражение 
S3 (а, b, f1(а)) может быть переведено как отрицание вышеприведенного
высказывание.
б) Высказывания с кванторными словами.
Примеры:
1) Высказывательная форма «х является выдающимся» Р 1(х) становится
высказыванием х Р1(х), если использовать кванторное слово «кто-то», то есть
«Кто-то является выдающимся» (здесь Р1 – предикаторная константа
«выдающийся»). Очевидно, что предикаторная формула х  Р1(х) может быть
23

2)

3)
4)
5)
6)
7)

переведены нка русский язык как «кто-то не является выдающимся» или
аналогичная формула х Р1(х) – «неверно, что все являются выдающимися».
Естественное высказывание «Кто-то достоин Сократа» переводится формулой
х Р2(х, а), а формула х Р2(а, х) соответствует выражению «Сократ достоин
кого-нибудь». Формула х Р2(х, х) переводится как «Кто-то не достоин
самого себя».
Высказыванию «Все являются талантливыми» соответствует формула
х
1
2
S (х), а высказывание «всякий достоин Сократа» - х Р (х, а).
Высказывание «Никто не достоин учителя Платона» и «учитель Платона не
достоин никого» можно соответственно записать предикатными формулами
вида: х  Р2(х, f1(b)) и х  Р2(f1(b), х).
Высказывание «Каждый достоин кого-нибудь» соответствует формуле
х
2
у Р (х, у).
Формуле х у Р2(х, у) можно сопоставить естественно-языковое выражение
«Кто-то кого-то не достоин».
Формулу х у S3(х, а, у) можно интерпретировать фразой «Кто-то достоин
Сократа больше, чем кого-либо»

в) Простые высказывания, выражаемые сложными формулами.
Примеры:
1) Высказывание «Некоторый идеалист мудр» может быть переведено на ЯЛП
посредством формулы х (Р1(х)Q1(х))( буквальный смысл- «существует
объект х, который является идеалистом Р , а является мудрым Q). Очевидно,
что предикатная формула  х (Р1(х)Q1(х)) имеет буквальный смысл «Для
всякого человека х верно, что если он идеалист Р, то он мудр Q» .
2) Формулы х (Р1(х)Q(х))
х (Р1(х)Q(х)) могт быть переведены как
«Некоторый идеалист не мудр» и «Ни один идеалист не мудр».
3) Простое высказывание «Некоторый идеалист достоин Платона» переводится
на ЯЛП формулой х (Р1(х)  R2(x,b)), а формула
х (Р1(х) R2(b,
х)) переводится на естественный язык так: «Существует такой человек, что
если он является идеалистом, то Платон достоин его». Переводом же
высказывания «Каждый идеалист достоин Платона» является формулой вида
х (Р1(х) R2(х, b)).
4) Великая теорема Ферма: «Для любого nN не существует х, у, z N,
удовлетворяющих равенству хn+2+yn+2=zn+2», на ЯЛП есть формула
x
1
1
1
4
1
y z (P (x),P (y),P (z) R (x,y,z,n)), где P – одноместная предикаторная
константа «быть натуральным числом», а R4- одноместная предикаторная
константа, соответствующая равенству хn+2+yn+2=zn+2.
СЕМАНТИКА ЯЛП.
Напомним, что семантикой формализованного языка
называется
совокупность правил приписывания значений выражениям этого языка. Именно в
этом случае говорят об интерполяции нелогических символов языка (логические
символы – логические операторы – имеют заданную при построении языка
24

интерпретацию). Суть данной поцедуры – указать, объекты каких типов могут
быть сопоставлены в качестве значений дискрептивным константам и предметным
переменным. Совокупность таких объектов называется областью интерпретации,
или универсумом рассмотрения (рассуждения) М. Приписывание значений
дискретивным константам в ЯЛП осуществляют с помощью семантической
функции J (называемой часто интерпретационной функцией).
Пару М, J , задающую допустимую в классической логике предикатов
интерпретацию дискретивных констант, называют моделью. Формально моделью
называется кортеж М, J  такой, что М, а J –интерпретирующая функция,
удовлетворяющая условиям: J(k)М, J n : Mn M, J Пn  Mn (здесь k, , П –
соответственно произвольная предметная константа, предметно-функциональная
константа, предикатная константа). Очевидно, что значениями термов являются
предметы (индивиды) из области инте5рпритации М, а возможными значениями
формул – объекты «истина, не ложь» (это означает, что термы являются аналогами
простых и сложных имен, а формулы – аналогами высказываний естественного
языка), то есть ): J(Ф n (t1…tn)М (J(n): Mn M – алгебраическая операция), Пn(t1…
tn): MnМ, л ( то есть J(П n (t1…tn)М, хотя J(П n) М). При этом значения термов
и формул обусловлены выбором конкретной модели М, J  и конкретного
приписывания элементов М предметным переменным.
Примеры:
1) Пусть область интерпретации есть множество целых положительных чисел ( то
есть М=Zt ), а интерпретационная функция J сопоставляется предметной
константе а число 5М, одноместной предметно-функциональной константе f –
операция возведения в квадрат, двухместный предметно-функциональной
константе g – операции сложения. Положим, что предметной переменной х
приписывается значение 3М. В этом случае значениями нижеприведенных
термов в указанной модели < zt,J>, при х=3 будут:

для терма а, очевидно, 5

для терма х, очевидно, 3

для терма f1(а) имеем 52 равно 25.

для терма g2 (x,a), имеем 3+5=8

для терма f 1(g2 (x,a ))=(3+5)2 =64

для терма g2 (f(a),x)=52+3=28
2) Для элементарных предикатных свойств Q2(f1(a),x) и Р1(g2 (x,a)) определить
принимаемые ими значения в модель < zt,J>, если J(Q2) – множество пар таких
чисел: где первая конпонента больше второй, J(Р1) множество четных чисел, а
х=3, а=5, f2, gt
Решение:
Для первой формулы имеем:
<52,3 >=<25,3 > J(Q2), то есть  Q2(f1(a),x)=U при х=3, а=5.
Для второй формулы имеем:
(3+5)=8  J(Р1), то есть  Р1(g2 (x,a))=U при х=3, а=5.
Очевидно, что в случае х f(a), когда х=26 имеем 25, 26 J(Q2) и
25+
1
2 1
1 2
26 J(Р ), то есть  Q (f (a),x)=л при х25,  Р (g (x,a))=л при х четном.
25

3) При условии примера 2 определить значение формул
Q2(f(a),x)  Р1(g2 (x,a)),  Q2(f(a),x)  Р1(g2 (x,a)), Q2(f(a),x)  Р1(g2 (x,a)).
Решение:
Для первой формулы имеем:
 Q2(f(a),x)  Р1(g2 (x,a))=U при х=3, а=5.
Для второй формулы имеем:
  Q2(f(a),x)  Р1(g2 (x,a))=Л при х=з.
Для третьей формулы имеем:
 Q2(f(a),x)  Р1(g2 (x,a))=U при х=3.
4) Замкнутая формула х Р1(х) не содержит свободных переменных и ее значения
в модели < zt,J> при J(Р1)  х zt: х=2n, nN  есть «U», то есть х Р1(х)= U
при х=2n. Аналогично, если J(Q2)х: х=k, l, kl, имеем у Q2(х, у)=л при
k=1.
5) Формула х Р1(f1(х)) в модели N, J при f2, J(Р1)  х: х=2n, nN  будет
логична при хN\ J(Р1), то есть х Р1(f1(х))=л при х- нечетное. Аналогично,
формула Q2(g2(х, а), у) в модели N, J при J(Q2)х: х=k, l, kl, g t , а=2,
у=1 имеет значение «U», то есть х Q2(g2(х, а), у)= U при хN.
КЛАССИЧЕСКАЯ ЛОГИКА ПРЕДИКАТОВ.
Логика предикатов, подобно логике высказываний, строится на базе
формализованного языка, выделяя в множестве предикатных формул понятия
закона логики предикатов и отношения логического следования к логической
эквиваленции.
а) Отношение логического следования.
Из множество формул Г логически следует формула В (то есть Г=В), если и
только если не существует модели М, J и приписывания значений
предметным переменным, при которых каждая формула из Г принимает
значение «U», формула В- значение «Л».
Пример:
Р(а), Q(a) =x(Р(х)Q(х)). Действительно, если предположить, что это не так, то из
истинных высказываний Р(а) и Q(a) высказывание x(Р(х)Q(х)) должно быть
логичным. Однако, Р(х)=U при х=а и Q(х) =U при х=а и, следовательно,
Р(х)Q(х)=U при х=а. Налицо противоречие, свидетельствующее о неверности
допущения. Итак, из формул Р(х), Q(х) следует формула x(Р(х)Q(х)).

Замечание:
26

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

Р(х), Q(х)
x(Р(х)Q(х)).
Итак, правильным, в частности, является естественное умозаключение :

 Студентка Наташа трудолюбива.
 Наташа успешно учится по специальности.
 Некоторые трудолюбивые студенты успешно учатся по специальности.
Однако, следующие умозаключения являются неправильными:
 Существует трудолюбивый студент.
 Существует студент, успешно осваивающий специальность.
 Некоторые
трудолюбивые
студенты
успешно
осваивают
специальность.
Действительно, логическая форма заданного умозаключения имеет вид:
Р(х), Q(х)
x(Р(х)Q(х))
Покажем, что между посылками и заключением в этом случае отсутствует
следование. Положим, что универсумом рассмотрения является множество
животных М, а предикаторным константам Р и Q соответствуют «быть медведем»
и «быть лисой». Поскольку все формулы рассматриваемого умозаключения
замкнуты, то приписывание значения переменной х произвольно. В модели
М, J формулы Р(х), Q(х) истинны, поскольку существуют животные, которые
соответственно есть медведи и есть лисы. Однако формула x(Р(х)Q(х)) есть
ложь, так как не существует таких животных в универсуме М, которые
одновременно являются и медведем и лисой. Именно это и означает, что
Р(х), Q(х) x(Р(х)Q(х)).
б)Законы классической логики предикатов.
Формула А является общезначимой(тождественно истинной), если и только
если А принимает значения «U» в каждой модели М, J и при любом
приписывании значений предметным переменным. Законы классической
логики предикатов выражаются общезначимыми формулами ЯЛП.
Утверждение «Формула ЯЛП – общезначима» символически записывается
так: А.
Пример:
1) В ЯЛП закон исключенного третьего может быть записан эквивалентными
формулами
xР(х)xР(х) xР(х)xР(х).
2) =(x(Р(х) x(Р(х) ) читается так: «Если для любого х присуще свойство Р, то
существует х, обладающий свойством Р. Очевидно, что (x(Р(х)x(Р(х) )
является законом.
Примечания:
1) Как и в логике высказываний, существует связь между отношением логического
следования и законом классической логики предикатов., то есть А 1, А2…Аn= В
тогда и только тогда, когда = (А1(А2…(Аn)…) (что равносильно = ((А1А2…
Аn)В).
27

2) В классической логике предикатов нет, в отличие от логики высказываний,
общей процедуры (алгоритма) для решения вопроса о том, имеет ли место
отношения логического следования Г=В (или в частном случае А=В) и
является ли ГВ законом. В этом плане логика предикатов является
неразрешимой относительно универсальной общезначимости формул.
3) Поскольку логика предикатов является неразрешимой теорией, то особое
значение приобретает формализация понятий логического закона и логического
следования посредством построения логических исчислений именно в тех
случаях, когда семантический анализ не позволяет выявить логическое
следование и логический закон на множестве предикатных формул, это
позволяет сделать исчисление (тго есть это осуществляется синтаксическим
образом).
4) Для логики высказываний исчисление, вообще говоря, как эффективная
процедура не является необходимым. Оно нужно как часть логического
исчисления для формул ЯЛП.
5) Важное в практических применениях узкое исчисление предикатов (то есть
одноместных, сингулярных) – разрешимо. То есть если предикат Р(х) является
теоремой, то есть и алгоритм его разрешения.
АЛГЕБРА ЛОГИКИ ПРЕДИКАТОВ.
Алгебра логики предикатов (алгебра кванторной логики, алгебра неоднородных
логических функций) – раздел математической логики, изучающий операции над
высказываниями субъектно-предикатной структуры, то есть n=Fn, U, Л2U,
Л, , , где Fn- множество предикатных формул вида Рn(х1, х2…хn)
с нелогическими переменными хi (выражение Рn(х1, х2…хn) понимается, как
переменная, высказывание, истинность которого определяется подстановкой
предметных констант вместо предметных переменных.
Выражение отношений посредством многоместных предикатов.
Неоднородная логическая функция Рn(х1, х2…хn): МnВ есть n-местный предикат,
где Рn n-местная предикаторная константа, М универсум (область) рассмотрения
предикатов, В=U, Л - двоичное множество истинных значений высказывания.
Пояснения:
1) Выражение Рn(а1, а2…аn), где а1, а2…аn М являются предметными константами,
есть высказывание, а выражение Рn(х1, х2…хn) есть логическая (двоичная)
переменная (при этом х1, х2…хn – нелогические переменные).
2) Поскольку предикаты могут принимать два значения (интерпретируются как
переменные высказывания), то из них можно образовывать сложные формулы
логики высказываний (сам предикат Рn(х1, х2…хn), являющийся элементарной
формулой, рассматривается в сложной формуле как логическая переменная).
Утверждения:
1) Всякий предикат Рn(х1, х2…хn) определяет отношение R Мn такое, что а1, а2…
аnR, если и только если Р n(а1, а2…аn)=U. При этом R задает область
истинности предиката Рn(х1, х2…хn) .
2)
Каждому n-местному отношению R Мn соответствует предикат Рn(х1,
х2…хn) такой, что Рn(а1, а2…аn)=U, если и только если
а1, а2…аnR.
28

Эти
утверждения
можно
проиллюстрировать
графически
бинарным
n
функциональным соответствием q= М , B, P, с помощью которого возникает
высказывание , если в качестве значений
хi ( i = 1…n)
Dom P
B=JmP
u

Мn
л
Область истинности
предикатов Ru Мn

Говорят, что предикат является выполнимым, если Ru  и Ru Мn (т.е. предикат
выполняется хотя бы для одного набора значений аргументов, само соответствие
сюрьективно). В том случае, если область истинности предиката Pn(x1, x2,…, xn)
пуста, т.е. Ru , то говорят, что предикат является тождественно-ложным
(невыполнимым), а в случае Ru Мn=Dom P предикат является тождественноистинным (общезначимым) – он выполняется для всех наборов аргументов (такой
предикат выражает закон логики)
1) Пример. Для двухместного предиката Р2(х1, х2), где Р2 – быть братом на
множестве детей М1 = {a,в,c} (где а - Алла, в – Володя, с – Сергей) область
определения Dom Р2(х1, х2) выполняемого предиката, есть область истинности:
Ru ={<в, а>, <в,c >, <c, в>, <c, a >} М2 ;
2) М2 = {a,в,c} (где а – Алла, в – Вера, с - - Светлана) имеем невыполнимый
предикат, т.е. Dom Р2(х1, х2)= Ru =
3) М2 = {a,в,c} (где а – Андрей, в – Володя, с – Сергей) имеем тождественноистинный предикат (закон), для которого Ru ={<а, в>, <a, c >, <в, а >, <в,c >,
<c, a >,<c, в>}
Утверждение 3. Всякой алгебраической операции f: Мn M можно поставить в
соответствие (n+1)-местный предикат такой, что Pn+1(x1, x2,…, xn+1) истинен, если и
только если fn(a1, a2,…, an)= аn+1
Однако обратное соответствие, т.е. от (n+1)-местного предиката к n-местной
функции возможно не всегда, а только при условии, чтобы для любого а 1n+1аn+1
Pn+1(а1, а2,…, а1n+1 )=  (т.е. предикат был бы ложным).
семьи М, то в случае:
КВАНТИФИКАЦИЯ ПРЕДИКАТОВ.

29

Навешивание квантора на предикат уменьшает в нем число свободных переменных
и превращает его предикат от меньшего числа переменных.
Пример.
1

x P ( x, y ) Q ( y ),
2

1

1

y P ( x, y ) Q ( x)
2

2

Пример.
3

2

xy R ( x, y, z , p) S ( z, p)
Пример.
1
1
x P ( x) и x P ( x) - высказывания,

истинностное

значение

которых

обусловлено универсумом рассмотрения М.
Примечание.
1) формулы вида хi Pn(x1, x2,…, хi,…, xn) часто называют
экзистенциональной квантификацией формул Pn(x1, x2,…, хi,…, xn)
относительно хi, а формулы вида хi Pn(x1, x2,…, хi,…, xn) –
универсальной квантификацией формулы Pn(x1, x2,…, хi,…, xn)
относительно хi.
2) Высказывание хP(х)=u, если предикат Р(х) является тождественноистинным, а хP(х)=u, если предикат Р(х) – выполним.
3) Если предметная область М предиката конечна, то его универсальная и
экзистенциональная
квантификации
являются
соответственно
обобщением конъюнкции и дизъюнкции всех формул P(аi) (где аi М),
т.е. имеем равносильности:
k

xP( x ) P ( a1 )  P (a2 )  ...  P (ak )   P (ai ),
i 1
k

xP ( x ) P (a1 )  P (a 2 )  ...  P (a k )  P ( ai ).
i 1

4) Равносильные выражения
хР(х)=хР(х),
 хР(х)=хР(х), т.е. взаимовыразимость кванторов означает, что один квантор
определяет сокращенную запись другим. Именно поэтому в логике предикатов
первого уровня достаточно только один из кванторов.
Эквивалентные преобразования кванторных формул.
1) Закон отрицания кванторов:
хР(х)  хР(х),
 хР(х)  хР(х).
Эти эквивалентности являются обобщением законов де-Моргана.
Пример. Пусть Р – сдал экзамен, а М – студент учебной группы. Тогда высказывание
хР(х) ( “не все студенты группы сдали экзамен”) эквивалентно высказыванию
хР(х) (“существуют студенты группы, которые не сдали экзамен”)
2) Законы коммутативности одноименных кванторов.
ху Р(х, у)  ухР(х,у),
30

ху Р(х, у)  ух Р(х, у).
Однако, для разноименных кванторов действительна импликация:
ху Р(х, у)  у х Р(х, у).
3) Законы пронесения и вынесения кванторов (эквивалентности предваренных
приведенных формул):
- х(Р(х)Z)  хP(x) )Z  ZхР(х),
х(Р(х)Z)  хP(x) )Z  ZхР(х),
х(Р(х)Z)  хP(x) )Z  ZхР(х),
х(Р(х)Z)  хP(x) )Z  ZхР(х).
Пример. х(F(x)Q(y))  H(x)  Q(y))  х(Q(y)(H(x)F(x))  Q(y)х(H(x) )F(x))
- х(P1(x)P2(x)) хP1(x)х P2(x),
х(P1(x)P2(x))  хP1(x)х P2(x),

Это т.н. законы дистрибутивности квантора  относительно операции  и 
относительно .
Для квантора  относительно  и  относительно  действительны
соотношения (верно лишь в одну сторону):
(хP1(x)хP2(x))  х(P1(x)P2(x)),
х(P1(x)P2(x))  хP1(x)х P2(x).
Примечание.
1) Предикатная формула, построенная только с привлечением булевых логических
операций  и кванторов ,  так, что логическая операция  (обращение)
встречается лишь перед символами предикатов, называются приведенной
формой. Так, х P1(x)х P2(x, у) – приведенная формула, а формулы
хР(х)хQ(x,y),
хР(х)хQ(x,y) – не приведенные формулы (т.к. “”
2) Предикатная формула вида >|1x >|2x…>|nxF, где >|i, где F –
бескванторная формула,
называется предваренной (пренексной)
нормальной формой – П.Н.Ф.
Так ху( P1(x)P2(x, у)) – приведенная П.Н.Ф., а ху( P1(x)P2(x, у)) – П.Н.Ф.,
но не предваренная формуле.
4)Законы переименования связанных переменных:
хР(х) уР(у),
хР(х) уР(у).
Эти равносильности означают, что переименование связанных переменных не
меняет истинности высказываний.
Утверждения. 1) Для любой предикатной формулы существует равносильная ей
приведенная форма.
2)Для любой предикатной формулы существует эквивалентная ей П.Н.Ф.
КЛАССИЧЕСКИЕ ЛОГИЧЕСКИЕ ИСЧИСЛЕНИЯ.
Понятие “исчисление” является экспликацией интуитивных понятий “вывод”,
“доказательство”, “оперирование”, “вычисление”.
В математической логике исчисление является частным случаем формальных
(дедуктивных) систем F.S. вида
<L, D>, задаваемое правилами синтаксиса
(образования) языковых выражений и правилами построения выводов

31

(дедуцирования). В том случае, если в исчислении не выделяют аксиомы, то говорят
о натуральных исчислениях.
Ниже будем изучать классические исчисления высказываний (И.В.) и предикатов
(И.П.) как гомоморфные отображения (модели) логики высказываний и логики
предикатов.
Цель классических И.В. и И.П.
Целью И.В. и И.П. является описание кланов всех общезначимых (тождественноистинных) формул (часто называемых тавтологиями, или законами).
Метасимволика И.В. и И.П.
Г- множество посылок (гипотез). Обычно Г записывают в виде Г=А 1, А2,…, Аn (Г
читается как “гамма”)
Ф – теорема; Аi – метаформула; R(J) – множество правил вывода в исчислении;
| - символ отношения дедуктивного вывода.
Пример. Запись Г|Ф ( из гипотез Г дедуктивно выводима формула Ф) означает А 1,
А2,…, Аn |Ф, или А1, А2,…, Аn
Ф
Пример. Запись |А означает, что А доказуема.
Пример. Запись А1, А2,…, Аn | означает, что множество посылок противоречива.
Пример. |=, 1 |= 2, 1 | 2 – метавысказывания.
Замечание. Специфика отношений |= и | в том, что в отличие от логических связок
(отношений отрицания, конъюнкции, дизъюнкции) они реализуются не на денотатах
высказываний, а на пропозициональных формулах.
Построение логических исчислений.
Построение (задание) исчислений качественно отличаются видом аксиоматики –
конечным или бесконечным множеством аксиом.
Аксиома – формула объектного языка, в рамках которого строится исчисление.
Система аксиом – конечное множество аксиом. Бесконечное множество аксиом
задается перечислением конечного множества схем аксиом. Схема аксиом –
выражение метаязыка, представляющее бесконечное множество формул
определенной структуры.
КЛАССИЧЕСКОЕ И.В.
Ниже рассмотрим различные И.В., отличающиеся аксиоматикой. Задание
классического И.В. в Я.Л.В. будем осуществлять с привлечением схем аксиом и
одного вывода.
a) I1 A
I2 (AB)((A)
I3 (AB) ((A(BC)) (AC
I4 (AB)
I5 (AB)B
I6 A (B (AB))
I7 A (AB)
I8 B (AB)
I9 (AC) ((BC) ((AB)C))
I10 
32

Правило вывода для этой аксиоматики – правило модус-поненс (Modus ponens, m.p.),
часто называемого правилом отделения:

33

ТЕОРИЯ АЛГОРИТМОВ.
Вводные положения.
Теория алгоритмов - раздел математической логики, в котором изучаются
теоретические
возможности
эффективных
процедур
вычисления
(алгоритмов) и их приложения.
Основное понятие этой теории – алгоритм – в интуитивном (наивном)
понимании существует в математике довольно давно, а точные
математические понятия, которые в том или ином смысле формализуют
интуитивное понятие алгоритма, предложены только в середине 30-х годов
20-го века. Необходимость такой формализации была обусловлена как
вопросами обоснования математики, так и вопросами доказательства
алгоритмической разрешимости и неразрешимости тех или иных задач.
Очевидно, что в математике доказываемый объект должен быть точно
определен.
В настоящее время теорию алгоритмов делят на дескриптивную
(абстрактную) и метрическую (количественную). Первая исследует
алгоритмы с точки зрения устанавливаемого ими соответствия между
исходными данными и результатами; к ней относятся, в частности, проблемы
построения алгоритма, обладающего теми или иными свойствами, алгоритмические (массовые) проблемы (т.е. нахождение единого метода
решения бесконечной серии однотипных единичных задач). Вторая
исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и
задаваемых ими вычислений, т.е. процессов последовательного
преобразования конструктивных объектов. Важно подчеркнуть, что как
сложность алгоритмов, так и сложность вычислений могут определяться
различными способами. Разработка методов оценки сложности алгоритмов и
вычислений имеет важное теоретическое и практическое значение, а сам
поиск теоретических моделей алгоритмов происходит в трех направлениях,
которые и определяют три основных класса этих моделей: арифметизации
алгоритмов, концепции абстрактной машины, принципа нормализации (т.е.
преобразование слов в произвольных алфавитах с помощью подстановок).
Замечание:
Абстрактная дескриптивная теория алгоритмов не учит строить конкретные
алгоритмы. Этим занимается прикладная метрическая (количественная)
теория алгоритмов. В отличие от абстрактной теории алгоритмов прикладная
теория рассматривает не только детерминированные, но также
вероятностные (стохастические) и эвристические алгоритмы. В последнем
случае, кроме детерминированных или статически заданных правил,
алгоритм включает также содержательные указания о целесообразном
направлении процесса.

34

Предмет и содержание читаемого курса.
Предметом изучения в читаемом курсе являются формальные уточнения
интуитивного понятия «алгоритм» с различных точек зрения:
арифметизации, нормализации и построения абстрактной машины. Целью
читаемой дисциплины студентам специальности 2201 является усвоение
необходимости формулировать алгоритмические проблемы как проблемы
решения вопроса о существовании алгоритма для решения данной
бесконечной серии однотипных задач и нахождение такого алгоритма в
случае, если он существует.
Содержанием курса являются следующие вопросы:
- языки операндов и алгоритмические языки;
- рекурсивные функции как математический вариант уточнения понятия
вычислимой арифметической функции;
- машины Тьюринга как математический эквивалент для общего
интуитивного представления об алгоритме;
- нормальный алгоритм Маркова;
- сложность алгоритма.
Интуитивное (наивное) понятие алгоритма как основное первичное
понятие математики.
Алгоритм – точное предписание для свершения некоторой
последовательности элементарных дискретных действий над исходными
данными любой задачи из некоторого класса (вообще бесконечного)
однотипных задач, в результате выполнения которой получится решение
этой задачи.
Иначе: Конечный кортеж правил, обладающих свойствами массовости
(инвариантность относительно входной информации – это так называемое
уточнение
понятия
–
решение
задачи
в
общем
виде),
детерминированности (однозначность применения этих правил на каждом
шаге), результативности (получение после применения этих правил
информации, являющейся результатом) и элементарности (отсутствует
необходимость дальнейшего уточнения правил), называется алгоритмом
на конечном множестве шагов решаемой задачи.
Примеры:
1) «Проезд запрещен», «Не курить» - не алгоритмы;
2) «Придерживайтесь правой стороны», «Место для курения», «Вход» не алгоритмы;
3) Сложение (умножение, вычитание, деление) двух чисел (т.е.
N2N) столбиком – алгоритм.
Пример:
Упорядочить в порядке возрастания конечное множество М
положительных чисел. Описание решения этой задачи в интуитивном
смысле может быть:
Шаг 1: В М ищется наименьшее число
35

Шаг 2: Найденное число приписывается справа к возрастающей
последовательности чисел R (в начальный момент R пусто) и
вычеркивается из М;
Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном
случае перейти к шагу 1;
Шаг 4: Конец. Результатом считать последовательность R, построенную к
данному моменту.
Это описание, которое кажется вполне ясным, далеко от алгоритма.
Действительно, если М=95, 62, (1/3)/2, то в предложенном варианте
решения поставленной задачи не указано, как искать наименьшее число.
Этот пример показывает, что понятие алгоритма в интуитивном смысле
требует уточнения понятия данных (т.е. указать каким требованиям
должны удовлетворять объекты, чтобы алгоритмы могли с ними
работать), памяти, дискретности, элементарности, конечности числа
шагов,
направленности,
детерминированности,
результативности,
массовости.
Пояснения:
1) Приведенное наивное (интуитивное) определение алгоритма не
является точным математическим определением, а лишь объясняет
смысл слова «алгоритм», в котором это слово используется в
математике.
2) Характеристиками алгоритма являются:
- детерминированность (определенность) – однозначность результата
процесса при заданных исходных данных;
- дискретность – расчлененность процесса на отдельные элементарные
акты (шаги, действия), возможность выполнения которых человеком
или машиной не вызывает сомнений,
- массовость – исходные данные для алгоритма можно выбирать из
некоторого множества данных (потенциально бесконечного), т.е.
алгоритм должен обеспечить решение любой задачи из класса
однотипных задач.
Основные требования к алгоритмам.
1) Очевидно, что каждый алгоритм имеет дело с данными: входными,
выходными и промежуточными. В этом плане уточнение понятия
алгоритм требует и уточнения понятия данных, т.е. указать, каким
требованиям должны удовлетворять объекты, чтобы алгоритмы могли
с ними работать. Ясно, что эти объекты должны быть четко
определены и отличимы как друг от друга, так и от «необъектов». В
теории алгоритмов четкая определенность объектов обусловлена
заданием их в формальном языке L=<A,S>, в котором символы
конечного алфавита А рассматриваются как элементарные объекты
для построения более сложных объектов конечными средствами S
(этот язык часто называется языком операндов в отличие от языка
описания самого алгоритма – алгоритмического языка).
36

2) В дальнейшем будем различать:
- описание алгоритма (т.е. инструкции или программы);
- механизм реализации алгоритма (это может быть процессор),
включающий средства пуска, остановки,
реализации
элементарных шагов, выдачи результатов и обеспечения
детерминированности процесса в управлении ходом вычислений;
- память данных алгоритма;
- процесс реализации алгоритма, то есть последовательность
шагов (действий), которая будет порождена при применении
алгоритма к конечным данным.
Пояснения:
1) Предполагается, что описание алгоритма и механизма его реализации
конечны, а память данных алгоритма может быть и бесконечной.
Конечность
процесса реализации алгоритма означает
его
результативность (сходимость), то есть остановки алгоритма после
конечного числа шагов (зависящего от данных) с указанием того, что
считать результатом.
2) Предполагается также, что память данных алгоритма однородна и
дискретна, то есть состоит из одинаковых ячеек, каждая из которых
может содержать только один символ алфавита данных. Вопрос о том,
нужна ли одна память или несколько (в частности для входных,
выходных и промежуточных данных алгоритма) может решаться поразному.
3) Понятие задачи «в общем виде» уточняется при помощи понятия
«массовая алгоритмическая проблема». Последняя задается серией
отдельных единичных проблем и состоит в требовании найти единый
алгоритм их решения (когда такого алгоритма не существует говорят,
что
рассматриваемая
массовая
алгоритмическая
проблема
неразрешима). Так, проблема численного решения уравнений данного
типа и проблема автоматического перевода есть массовые
алгоритмические
проблемы:
образующими
их
единичными
проблемами являются в 1-м случае проблемы численного решения
отдельных уравнений данного типа, а во 2-м случае - проблемы
перевода отдельных фраз.
4) Алгоритмический процесс – есть процесс последовательного
преобразование
конструктивных
объектов,
происходящий
дискретными шагами; каждый шаг состоит в смене одного
конструктивного объекта другим. Так, при применении алгоритма
вычисления (f: D2 D) столбиком к паре <507, 38> последовательно
возникают следующие конструктивные объекты:
_507
38

_507
38
38

_507

_507
38
469
37

Здесь возможными исходными данными служат пары чисел, возможными
результатами – числа (все в десятичной системе счисления), а возможные
промежуточные результаты суть трехэтажные записи вида _pq , где qz

запись числа в десятичной системе, z- такая же запись или пустое слово, а
p- запись числа в десятичной системе с допущением точек над
некоторыми цифрами (точка означает заимствование из старшего
разряда).
Основная терминология теории алгоритмов.
Областью применимости алгоритма называется совокупность тех
объектов, к которым он применим. Про алгоритм U говорят, что он:
1) «Выявляет функцию f», коль скоро его область применимости
совпадает с областью определения f, и U перерабатывает всякий х из
своей области применимости в f(x);
2) «Разрешает множество А относительно множества Х», коль скоро он
применим ко всякому х из Х и перерабатывает х из ХА в слово «да»,
а всякий х из Х\А в слово «нет»;
3) «Перечисляет множество В», коль скоро его область применимости
есть натуральный ряд, а совокупность результатов есть В.
Функция называется вычислимой, если существует вычисляющий ее
алгоритм.
Множество
называется
разрешимым
(рекурсивным)
относительно Х, если существует разрешающий его относительно Х
алгоритм.
Множество
называется
перечислимым
(рекурсивноперечислимым), если либо оно пусто, либо существует перечисляющий
его алгоритм.
Замечания:
1) Область возможных исходных данных и область применимости
любого алгоритма суть перечислимые множества;
2) Для любой пары вложенных одно в другое перечислимых множеств
можно подобрать алгоритм, у которого большее множество служит
областью возможных исходных данных, а меньшее областью
применимости.
3) Разрешимые и перечислимые множества являются множествами,
строение которых задается с помощью тех или иных алгоритмических
процедур.
4) Процесс выполнения алгоритма называется алгоритмическим
процессом.
Основные теоремы теории алгоритмов.
38

Теорема 1: Функция f вычислима тогда и только тогда, когда перечислим
ее график, то есть множество всех пар вида <x, f(x)>.
Теорема 2: Подмножество А перечислимого множества Х разрешимо
относительно Х тогда и только тогда, когда А и Х\А перечислимы.
Теорема 3: Если А и В перечислимы, то АВ и АВ также перечислимы.
Теорема 4: В каждом бесконечном перечислимом множестве Х существует
перечислимое подмножество с неперечислимым дополнением (в силу
теоремы 2 это перечислимое подмножество будет неразрешимым
относительно Х).
Теорема 5: Для каждого бесконечного перечислимого множества Х
существует вычислимая функция, определенная на подмножестве этого
множества и не продолжаемая до вычислимой функции, определенной на
всем Х.
Параметры алгоритма.
Как правило, для данного алгоритма можно выделить семь независимых
характеризующих его параметров:
1) совокупность возможных исходных данных;
2) совокупность возможных результатов;
3) совокупность возможных промежуточных результатов;
4) правило начала;
5) правило непосредственной переработки;
6) правило окончания;
7) правило извлечения результата;
Основная гипотеза теории алгоритмов.
Любая практическая задача, приводящая к необходимости создания
эффективного вычислительного метода (алгоритма), может быть поставлена
в точных математических терминах.
Алгоритмические (формальные математические) модели.
Приведенное выше «наивное» (интуитивное) понятие алгоритма как
первичное (исходное) понятие математики не допускает его определения в
терминах более простых понятий. Возможные уточнения понятия алгоритма
приводят, строго говоря, к известному сужению этого понятия. Каждое такое
уточнение состоит в том, что для каждого из семи параметров алгоритма
точно описывается некоторый класс, в пределах которого этот параметр
может меняться. Выбор таких классов и отличает одно уточнение от другого.
Поскольку семь параметров однозначно определяют некоторый алгоритм, то
выбор семи классов изменения этих параметров определяет некоторый класс
алгоритма.
39

В настоящее время среди математических моделей алгоритмов описанного
типа наиболее известными являются уточнения, предложенные
А.М.Тьюрингом
(модель
абстрактной
вычислительной
машины),
А.А.Марковым (нормальные алгоритмы), А.Черчем (вычислительные
функции).
Так, понятие машины Тьюринга как F S1 следующим образом может быть
использовано для уточнения общего представления об алгоритме в данном
алфавите, если Тьюринговским алгоритмом в алфавите А называется всякий
алгоритм U следующего вида:
- фиксируется некоторая машина Тьюринга в алфавите А, то есть
<A, Q, R>, здесь Q – множество внутренних состояний машины,
а R – правило перехода из одной конфигурации машины к
другой);
- задается  - слово, принимаемое в качестве исходного данного
для U (A*);
- строится исходная конфигурация машины a0q0a0, где q0 –
начальное состояние машины q0Q, a0 – пустой символ, a0А;
- машина, отправляясь из a0q0a0, заканчивает работу в
заключительной конфигурации.
Считается, что для всякого алгоритма U в каком-либо алфавите может быть
построен тьюринговский алгоритм, дающий при одинаковых исходных
данных те же самые результаты, что и алгоритм U. Это соглашение в теории
алгоритмов известно как тезис Тьюринга: «Всякий алгоритм может быть
реализован машиной Тьюринга».
Замечания:
1) Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма
(или эффективной процедуры) является неточным. Это не теорема и не
постулат математической теории, а утверждение, которое связывает
теорию с теми объектами, для описания которых она создана. По
своему характеру тезис Тьюринга напоминает гипотезы физики об
адекватности математических моделей физическим явлениям и
процессам. Подтверждением правильности тезиса Тьюринга является
математическая практика, а также эквивалентные тезисы и, в
частности, тезис Черча для рекурсивных функций: «Всякая функция,
вычислимая некоторым алгоритмом, частично-рекурсивная».
2) Из сопоставления двух вышеприведенных тезисов вытекает
утверждение: «Функция вычислима машиной Тьюринга тогда и только
тогда, когда она частично-рекурсивна». Это утверждение об
эквивалентности двух алгоритмических моделей является (в отличие от
тезисов) вполне точным математическим утверждением и,
следовательно, доказуемо, то есть имеют место две теоремы:
Теорема 1: Всякая частично-рекурсивная функция вычислима на машине
Тьюринга.
Теорема 2: Всякая функция, вычислимая на машине Тьюринга частичнорекурсивная.
40

3) Алгоритмические модели позволяют, с одной стороны, заменить
неточность утверждения о существовании эффективных процедур
(алгоритмов)
точными
утверждениями
о
существовании
соответствующей алгоритмической модели (например, машины
Тьюринга), а с другой стороны, утверждения о несуществовании таких
моделей истолковывать как утверждения о несуществовании алгоритма
вообще.
4) Тезисы позволяют выявлять случаи невозможности алгоритмов,
однако, не указывают в случае их существования пути построения
удобного для практики алгоритма (Напоминание: «Теория алгоритмов
не учит строить конкретные алгоритмы»).
Блок-схемы алгоритмов.
Связи между шагами алгоритма можно изобразить в виде графа (блоксхемы) такого, как, например, следующий:

Ввес
ти

Шаг 1

Шаг 2

Шаг 3

Выве
сти

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

Очевидно, что блок-схемы являются средством описания детерминизма
алгоритма.
Замечания:
1) На практике блок-схемы часть имеют предикаты (точки
разветвления) не только двоичные, но и многозначные, важно лишь,
чтобы верным был ровно один из возможных ответов.
2) Блок схема вида:

Ввес
ти

А1

А2

Выве
сти

где блок А1 вычисляют функцию f1(x), а исходными данными для А 2
являются результаты А1, называется композицией алгоритмов А1 и А2 (то есть
эта блок-схема задает алгоритм, вычисляющий f2(f1(x)), то есть композицию
f1 и f2)
Машина Тьюринга.
Машина Тьюринга Т – название, закрепившееся за вычислительными
абстрактными машинами некоторого точно охарактеризованного типа.
Содержательное понятие машины.
Машину Тьюринга Т=<A, Q, q0, qz, > удобно представлять в виде
автоматически функционирующего устройства, способного находиться в
конечном числе внутренних состояний Q=q1…qn-2, qz и снабженного
бесконечной внешней памятью – лентой. Среди состояний Q имеются два
выделенных – начальное q1 и заключительное qz. Лента разделена на ячейки и
потенциально бесконечна в обе стороны. В каждой ячейке ленты может быть
записана любая из букв внешнего алфавита А=a0, a1…am (a0 – пустая буква,
то есть считается, что в пустой ячейке записана a0). Функционирование
машины обуславливает программа =qj ai  qk aL dt.
Схема такого устройства как совокупность стуктурно-связанных
внутренней и внешней памяти, блока управления и управляемой головки

42

a0

a2

a5

ai

a9

a3

a5

a0

Ячейки внешней памяти для записи-считывания символов
внешнего
алфавита А

dЛ

dп

qi

ai
Блок управления
БУ

aL
dt
dt
К шаговому приводу
перемещения
управляемой головки
(или ленты)

D

Управляемая головка
записи-считывания
символа
внешней
памяти
Канал
воспроизведения
(считывания)
Цепь
О.С.

qk
Q

Внутренняя память состояний
(инструкций Q и перемещений D)

дает возможность имитировать алгоритмические процессы распознавания и
порождения цепочек языка произвольного типа (по Хомскому).
На схеме:
а) Блок управления производит преобразование пары (цепочки из двух
символов) qj aiQ*A в тройку qk aL dt Q*A*D. Это означает, что если
машина находится в состоянии qj (то есть вычисляет инструкцию qj), а
управляемая головка считывает символ ai из обозреваемой ячейки внешней
памяти, то блок управления вырабатывает команду qk aL dt, согласно которой:
1) машина переходит в состояние qk (допускается k=j);
2) в обозреваемую ячейку ленты вместо символа ai записывается символ
aL (допускается i =L);
3) управляющая головка (лента) перемещается на один шаг или остается
на прежнем месте (dЛ – перемещение на один шаг влево, dп –
перемещение на один шаг вправо, dн – оставаться на месте; dЛ, dп,
dнD).
Итак, если блок управления осуществляет функциональное отображение:
Гf: Q*A Q*A*D,
где qj aiQ*A, qk aL dt Q*A*D, ai, aLА, qj, qkQ, dt D= dЛ, dп, dн, то
машину Тьюринга будем называть детерминированной и всюду
определенной.
43

б) Данные (исходные, промежуточные и окончательные) машины есть
цепочки символов (слова) в алфавите А, которые записываются на
бесконечной ленте внешней памяти (каждый символ слова в отдельной
ячейке) (А=Аисх АпромАрез, а0Аисх, а0Арез).
в) Элементарные шаги в рассматриваемой машине следующие:
1) изменение состояния машины и содержимого ячейки, обозреваемой
управляемой головкой;
2) перемещение управляемой головки на один шаг влево ( вправо);
г) Детерминированность работы машины обуславливается программой ее
работы , то есть совокупностью выражений (j, i) (j=0,n; i= 0,n), каждое из
которых имеет один из следующих видов:
qj ai  qk aL dн
qj ai  qk aL dЛ
qj ai  qk aL dп,
где 0  k n, 0 L m.
В дальнейшем программу будем записывать в табличном виде:

A\Q
a0
a1
…
ai
…
am

q0

q1

…

qj

…

qz

qk aL dt

или диаграммой переходов вида:
qi

ai aL dп

qz

q0
qk

д) Начальная атрибуция (конфигурация машины) характеризуется
следующим образом:
1) на ленте записано слово А*;
2) управляемая головка указывает на ячейку ленты, в которой записан
самый левый символ цепочки (слова),
3) машина находится в начальном состоянии q0  Q;
Пример начальной конфигурации машины:
a0

a0

a2

a4

q0

a2
44

a7

БУ

a3

a9

a0

a0

a0

Символически эта конфигурация записывается как машинное слово
q0= q0 a2 a4 a7 a3 a9= k0.
e) Текущая (промежуточная) ситуация (конфигурация) kp есть машинное
слова вида 1 qj ai 2, где 1 и 2 – цепочки символов алфавита А.
ж) Заключительная ситуация (конфигурация) kz имеет вид qz, где qz –
заключительное состояние машины, qzQ, - результат работы машины из
исходной ситуации по заданной программе, А*.
Очевидно, что последовательность конфигураций k0 k1 k2… однозначно
определяется исходной конфигурацией k0 и полностью описывает работу
машины Тьюринга Т= =<A, Q, q0, qz, >, начиная с k0= q0 (А*исх, АисхА).
Эта последовательность конечна, если в ней встретится заключительная
конфигурация kz= qz, и бесконечна в противном случае.
Пример:
1) Пусть последовательность k0 k2 kz имеет вид q0 a2 a1 a4 q1 a1 qz a4 a2
(очевидно, что последовательность команд следующая: q0 a2  q1 a4 dп, q1 a1
qz a2 dЛ).
Имеем следующую интерпретацию смены ситуаций:
k0

a0

a2

a1

a0

q0

dп
а2

а4

k1

a0

a4
dЛ

a1

a0

a0

a0

a0

a0

q1
а2

kz

a0

a4

а1

a2

qz Т=<a0, a, q0, qz, q0 a0 q0 a dп, q0 a q0 a dп> будет работать
2) Машина
бесконечно, заполняя все ячейки ленты символами а вправо от начальной
пустой ячейки (исходная
информация на ленте - пустые символы а 0 в каждой
а4
ячейке ленты).
45

Примечания:
1) Соответствие, устанавливаемое машиной Тьюринга между теми
исходными данными, к которым она применима ( то есть если она
приводит к результату) и результатами ее работы представляет собой
некоторую словарную функцию (в математическом смысле)
Т(*исх*резисхрезпром.
2) Если для функции имеется машина ее реализующая, то говорят, что
эта функция вычислима по Тьюрингу. Функция, для вычисления
которой существует алгоритм, называется вычислимой.
3) Поскольку слово (*, m) можно отождествить с натуральным
числом (в m-ичной системе счисления), то уточнение понятия
вычислимой словарной функции приводит и к уточнению понятия
вычислимой числовой функции f:NkN, kN. Тьюринг доказал. что
класс числовых функций, вычислимых на машине Тьюринга,
совпадает с классом частично-рекурсивных функций.
Формальное определение машины Тьюринга.
Машина Тьюринга Т=<A, Q, > полностью определяется:
1) внешним алфавитом А=а0, а1… аm;
2) Алфавитом внутренних состояний Q=q0, q1… qn;
3) Программой , то есть совокупностью выражений Т(i, j) (i=0,n; j=0,m),
каждое из которых имеет вид следующей команды qj ai  qk aL dt (k=0,n;
L=0,m; dt  dЛ, dп, dн.
Машина Тьюринга есть формальная детерминированная система
F.S=<L, D>=<A, S; Ax, R>, порождающая множество L своих конфигураций
(машинных слов) 1 qj ai 2 (1, 2А*, 1 и 2 могут быть пустыми).
Единственная аксиома – начальная конфигурация q0 (А*), правила
вывода R – система команд (программа) Т(i, j).
Примечания:
1) Очевидно, что всякий алгоритм является формальной системой F.S,
что следует из тезиса Тьюринга: «Любой алгоритм может быть
реализован машиной Тьюринга».
2) Поскольку машина Тьюринга есть алгоритм, то записью последнего
является программа , а алгоритмом выполнения – описание
устройства машины Тьюринга.
Пример:
Построить машину Тьюринга для вычисления базисной рекурсивной
функции f(x)=x+1, xN0 Имеем T=<A=a0, Q=q0, qz, =
A\Q
q0
qz
a0
dн qz
a0 dн qz >
а0dн

dn q0
dн qz
dп
или

q0
46

dп

qz

Пусть:
а) х=0, тогда q0 a0…a0 qzdн;
б) х=2, тогда q0 a0 q0 dn q0 a0 dn qz dн
Основной тезис Тьюринга.
Утверждение: «Для любой вычислимой функции можно построить машину
Тьюринга, реализующую ее» - является гипотезой, называемой тезисом
Тьюринга. (Часто этот тезис формулируют так: «Всякая вычислимая функция
вычислима по Тьюрингу.)
Напомним, что этот тезис нельзя доказать, так как он объединяет два
понятия – расплывчатое, интуитивное понятие вычислимой функции и
строгое понятие машины Тьюринга.
Нормальные алгорифмы (алгоритмы).
Нормальные алгорифмы U=<A, > - класс словарных алгоритмов, то есть
алгоритмов (применимых к словам некоторого алфавита А), элементарными
действиями которых являются подстановки в слова (их кортеж есть схема ).
Всякий нормальный алгоритм, являясь алгоритмом в некотором алфавите
А, порождает в нем детерминированный процесс переработки слов. Поэтому
любой нормальный алгоритм в фиксированном алфавите А вполне
определяется указанием его схемы  - упорядоченного конечного списка
формул подстановки в А. Каждая такая формула по существу представляет
пару <Л, п> слов в А (то есть Л, пА*). Слово Л называется левой частью
этой формулы, а п – ее правой частью. Среди формул данной схемы
некоторые выделяются специально и объявляются заключительными.
Обычно в схеме нормального алгоритма заключительная формула
записывается в виде Л п (, а незаключительная в виде
Л
п. При этом допустимы формулы вида : Лп п;
Л
Нормальный алгоритм U в алфавите А есть предписание строить, исходя из
произвольного слова  в А (А*), последовательность слов i.
Так, пусть задан алфавит А=1, + и схема подстановок  (здесь
 - пустое слово, то есть А*, Слово  этот алгоритм
перерабатывает так:





Процесс оканчивается применением заключительной подстановки, которая
перерабатывает слово само в себя. Очевидно, что рассматриваемый алгоритм
осуществляет операцию сложения (эквивалентный ему алгоритм
<А=1, +, ++, +, >).
47

Пусть теперь  - некоторое слово в А, то есть А*. Говорят, что 
поддается формуле, если левая часть этой формулы входит просто в .
Считается, что всякое слово начинается простым вхождением пустого слова
в . Считается, что всякое слово начинается вхождением пустого слова .
Поэтому всякое слово поддается формуле с пустой левой частью.
Применением нормального алгоритма U к слову  называется процесс,
определяемый следующим правилом (представляющим собой алгоритм
выполнения нормального алгоритма):
1) Считать, что i=1. Перейти к пункту 2.
2) Проверить, поддается ли преобразуемое слово i-ой формуле. Если да,
то перейти к пункту 3, если нет – к пункту 5.
3) Первое простое вхождение левой части i-ой формулы в преобразуемом
слове заменить правой частью i-ой формулы. Результат считать в
дальнейшем преобразуемым словом, перейти к пункту 4.
4) Если i-ой формула является заключительной подстановкой, то процесс
прекратить. В противном случае перейти к пункту 1.
5) Проверить, имеет ли место равенство i=n. Если да, то процесс
прекратить, в противном случае перейти к пункту 6.
6) Увеличить значение i на 1 и перейти к пункту 2.
Любое слово в алфавите А может служить исходными данными для
нормального алгоритма в алфавите А. При этом возможны случаи:
1) Процесс выполнения нормального алгоритма для слова А*
заканчивается формулой Л п после конечного числа шагов. При
этом говорят, что нормальный алгоритм применим к слову , и
полученное после его выполнение слово * называется
результатом.
2) Процесс выполнения нормального алгоритма при исходном слове
А* никогда не заканчивается или происходит безрезультативная
остановка (то есть не на формуле Л п). В этом случае говорят,
что нормальный алгоритм не применим к слову .
Пример:
Алгоритм U=     
       «обращает» любое слово в А, то
есть перерабатывает его в слово, записанное в обратном порядке (его можно
записать как 100 с тем, чтобы использовать ).
Так, слово 100 этот нормальный алгоритм последовательно перерабатывает
в слова   010, 001, 001, 001, 001, 001, 001, 001,
001, 001, 001, 001, 001.
Замечание:
Последний член этой последовательности считается результатом применения
алгоритма U к слову =100 и обозначается символом U(). При этом
считается, что U перерабатывает =100 в =001, и пишут U()= (в нашем
примере U(100)=001).
Пример:
48

Алгоритм U=<a, b, <a b; baaba, aa> реализует предписание:
«Взяв какое-либо слово a, b* в качестве исходного, (где а, ba,
aa), делай допустимые переходы до тех пор, пока не получится слово
вида aa, тогда остановись: слово и есть результат».
Так, взяв слово babaa в качестве исходного данного после первого перехода
(то есть применив формулу ba aba ), получим baaaba (здесь =baa), а
после второго (то есть применив снова формулу ba aba) имеем aabaaba
(здесь =ааba). Применив формулу aa к слову aabaaba получим
результат baaba (то есть U(babaa)=baaba).
Однако, взяв в качестве исходного данного слова =baaba, получим
бесконечную последовательность abaaba, baabab, abababa, bababab, babababa,
… в которой не будет слова aa. Это означает, что алгоритм U не будет
применим к слову =baaba.
Если же исходным данным взять слово abaab, то получим конечную
последовательность baabb, abbaba, bbabab, в которой к последнему слову
нельзя применить допустимый переход, то есть это случай
безрезультативной остановки (это означает также неприменимость заданного
алгоритма U к слову abaab).
Считается, что для любого алгоритма В в алфавите А может быть построен
нормальный алгоритм U над этим алфавитом, перерабатывающий
произвольное слово А* в тот же самый результат, в который
перерабатывает его исходный алгоритм В. Это соглашение известно в теории
алгоритмов под названием принципа нормализации.
Уточнение понятия алгоритма, осуществленного на основании понятия
нормального алгоритма, оказывается эквивалентным другим известным
уточнениям (в частности, на основе абстрактной машины Тьюринга).
Вследствие этого принцип нормализации оказывается равносильным тезису
Черча, предлагающему считать понятие частично рекурсивной функции
адекватным уточнением понятия вычислимой арифметической функции
f:Nn0N0, N0=N0, nN (к ней путем метода арифметизации могут быть
приведены числовые и нечисловые функции).
Рекурсивные функции.
Рекурсивная функция (частично рекурсивная функция) – функция, заданная
с помощью последовательности частичных (определенных не обязательно
для всех значений своих аргументов) функций таких, что каждая функция
последовательности либо является (базисной) простейшей функцией, либо
получена из предыдущих с помощью операторов суперпозиции
(подстановки) Snm, примитивной рекурсии Rn и минимизации .
Все рекурсивные функции являются вычислимыми функциями, то есть для
любой такой функции можно указать алгоритм вычисления ее значений.
Очевидно, что всякий алгоритм однозначно ставит в соответствие исходным
данным (в случае, если он определен на них) результат. Поэтому с каждым
алгоритмом однозначно связана функция, которую он вычисляет. Однако,
49

обратное, то есть: «для всякой функции существует вычисляющий ее
алгоритм», неверно.
Согласно тезису Черча, любая функция, считающаяся вычислимой в
интуитивном смысле, является рекурсивной функцией. Эта гипотеза (тезис)
подтверждается тем, что все известные вычислимые функции являются
рекурсивными. Тезис Черча позволяет придать интуитивному понятию
вычислимой функции точный алгоритмический смысл.
Понятие рекурсивной функции эквивалентно понятию функции,
вычислимой на машине Тьюринга.
В теории рекурсивных функций, рассматриваемой ниже, как и вообще в
теории алгоритмов, принят конструктивный, финитный подход, основной
чертой которого является то, что все множество исследуемых объектов (в
данном случае функций) строится из конечного числа исходных объектов –
базиса – с помощью простых операторов (операций), эффективная
выполнимость которых достаточно очевидна.
Замечание:
Всюду определенные рекурсивные функции называются общерекурсивными
функциями.
Примитивно-рекурсивные функции.
Def. Всюду определенная функция от натуральных аргументов с
натуральными значениями, которую можно получить из простейших
базисных всюду определимых функций
f(x)=x+1, z(x)=0, Jnm(x1,…, xn)=xm
Конечным числом операторов (операций) суперпозиции (подстановок) Snm, и
примитивной рекурсии Rn называется примитивно-рекурсивной (ПРФ).
Базисную функцию f(x)=x+1 принято называть функцией следования (эту
функцию иногда обозначают х` и называют функцией прибавления
единицы), z(x)=0 – нуль функцией, Jnm(x1,…, xn)=xm – функцией тождества
(или введения фиктивных переменных), где nm.
Def. Оператором суперпозиции Snm называется операция подстановки в
функцию от m переменных m функций от n переменных. (одних и тех же).
Пример. Функция f(x1,…, xn)
возникает из функций h(x1,…, xm), g1(x1,
…, xn), …gm(x1,…, xn) суперпозицией, если
f(x1,…, xn)= Snm(h, g1,…, gm) = h(g1(x1,…, xn), …, gm (x1,…, xn)).
Если заданы функции Jnm и операторы Snm, то можно считать заданными
всевозможные операторы подстановки функции в функцию, а также
переименования, перестановки и отождествления переменных.
Так, если f(x1, x2)= h(g1(x1, x2), g2(x1)), то ее стандартный вид следующий:
f(x1, x2)= S22(h(x1, x2), g1 (x1, x2), S12 (J21(x1, x2), g2(x1), g3(x1))), где g3 – любая
функция от х1. Если же имеем f(x2, x1, х3, …, xn) и
f(x1, x1, x3,…,
xn), то пишем:
f(x2, x1, х3, …, xn) = f(J22(x1, x2), J21(x1, x2), х3, …, xn),
50

f(x1, x1, x3,…, xn)= f(J21(x1, x2), J21(x1, x2), х3, …, xn).
Def. Оператором примитивной рекурсии Rn называется процесс
определения функфии f (n+1) переменных через n-местную функцию g и
(n+2)- местную функцию h в следующем виде:
f(x1, x2, …, xn, 0)= g(x1, x2,…, xn)
f(x1, x2, …, xn, y+1)=h(x1, x2,…, xn, y, f(x1, x2, …, xn, y)),
где g и h – две различные функции соответственно n и n+2 аргументов.
Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что
функция f определена схемой примитивной рекурсии выражается равенством
f(x1, x2, …, xn, y)=Rn(g, h). В случае, когда n=0, то есть определяемая функция f
является одноместной, схема примитивной рекурсии принимает более
простой вид:
f(0)=с, f(у+1)=h(y, f(y)), где с – константа.
Схема примитивной рекурсии определяет f рекурсивно не только через
другие функции g и h, но и через значения f в предшествующих точках:
значение функции f в точке у+1 зависит от значения функции f в точке у.
Очевидно, что для вычисления f(x1,…, xn, k) понадобиться k+1 вычислений
по схеме примитивной рекурсии – для у=0, k.
Замечания:
1) Существенным в операторе примитивной рекурсии Rn является то, что
независимо от числа переменных в f рекурсия ведется только по одной
переменной у (остальные n переменных x1, x2, …, xn на момент
применения схемы примитивной рекурсии зафиксированы и играют
роль параметров).
2) Формальное индуктивное определение примитивно-рекурсивной
функции следующее:
- функции 0, х`, Jnm для всех натуральных n, m, где nm являются
примитивно-рекурсивными;
- если g1(x1,…, xn), …gm(x1,…, xn), h(x1,…, xm) - примитивнорекурсивные функции, то Snm(h, g1,…, gm) - примитивнорекурсивные функции для любых натуральных n, m;
- если g(x1,…, xn) и h(x1,…, xm, у, z) - примитивно-рекурсивные
функции, то Rn(g, h) – примитивно-рекурсивная функция;
- других примитивно-рекурсивных функций нет.
3) Схемной интерпретацией примитивной рекурсии может быть схема:
x

h(x1, x2)

f(x, t)

51

Эта схема состоит из элемента, вычисляющего за один такт функцию h
от двух переменных и элемента задержки на один такт. По каналам
схемы могут передаваться натуральные числа. Время t считается
дискретным, то есть t=0, 1, 2, 3…. Схема имеет один вход х и один
выход f. Выход f зависит не только от х, но и от момента t, в котором
он рассматривается. В начальный момент t=0 второй вход h является
константой с, зависящей от начального состояния схемы: f(x, 0)=h(x,
c)=g(x). В момент t=1: f(x, 1)=h(x, f(x, 0)); в общем случае f(x, t+1)=h(x,
f(x,t)).
Нетрудно убедиться, например, что если h выполняет
умножение, а с=1, то f(x, t)=xt+1.
4) Поскольку исходные (базисные) функции являются вычислимыми, а
операторы суперпозиции и примитивной рекурсии вычислимость
сохраняют, то множество всех примитивно-рекурсивных функций есть
подкласс класса всех вычислимых функций;
5) Класс всех примитивно-рекурсивных функций счетен, поскольку
каждая такая функция задается описанием ее построения из исходных
функций.
6) Практически все арифметические функции, употребляемые в
математике по конкретным поводам, являются примитивнорекурсивными функциями, например: х+у, х*у, ху и т.д.
Оператор минимизации (- орератор).
Def. Оператором минимизации 
(наименьшего числа оператора)
называется преобразование (n+1)-местной функции (в общем случае
частичной)  в n-местнуб f, такую, что для любых х 1, х2, …хn, у равенство
f(х1, х2, …хn)=у имеет место лишь в том случае, если определены и не равны
нулю значения ( х1, …, хn, 0), …, ( х1, …, хn, у-1) и при этом
( х1, х2, …хn, у)=0. Применение оператора минимизации обозначают
[, (y)], где у - исчезающий аргумент.
Говорят, что n-местная арифметическая функция f: N nN получается из
функции : Nn+1N с помощью -оператора, если выполнено условие: для
любых k1, k2,…, kn, kN.
f(k1, k2,…, kn)=k,
тогда и только тогда, когда для всех l<k значения ( k1, k2,…, kn, l)
определены и отличны от нуля, а значение ( k1, k2,…, kn, k) определено и
равно нулю.
Если f получается из функции  с помощью оператора наименьшего числа
, то пишут:
f(x1, x2,…, xn)=y[(x1,…, xn, y)=0].
Важным свойством -оператора является то, что с его помощью из
вычислимой функции всегда получается частичная вычислимая функция f.
Именно, если имеется алгоритм для вычисления , то значение f(x1, x2,…, xn)
может вычисляться следующим образом:
52

- вычисляется (x1, x2,…, xn, 0);
- если процесс вычисления закончился, то есть значение
(x1, x2,…, xn, 0) определено, и (x1, x2,…, xn, 0)=0, то полагаем
f(x1, x2,…, xn)=0, а если (x1, x2,…, xn, 0)0, то начинают вычислять
(x1, x2,…, xn, 1). Если процесс вычисления закончился и
(x1, x2,…, xn, 1)=0, то полагают f(x1, x2,…, xn)=1, а если
(x1, x2,…, xn, 1)0, то переходят к вычислению (x1, x2,…, xn, 2) и так
далее.
- Процесс вычисления закончится, если найдется такое у, что для всех
z<y значение (x1, x2,…, xn, z) определено и отлично от нуля, а
(x1,
x2,…, xn, у) определено и равно нулю. Тогда f(x1, x2,…, xn)=у.
Пример:
f(x)=y[12*y-x=0]. Тогда f(x)=x/2 при всех четных значениях хN.
Замечание:
Примитивно-рекурсивные функции всегда определены (имеют значения) для
любых значений аргументов. Иначе обстоит дело с функциями, полученными
при помощи -оператора. Для некоторых комбинаций значений аргументов
они могут быть не определены, потому что исходная функция не принимает
нулевых значений.
Пример:
det f(x)=[J21(x, y), (y)].
Полученная функция f(х) обладает следующими свойствами:
f(0)=0, f(k) не существует при k0. Последнее означает, что для заданной
функции J21(x, y) -оператор не может построить f(k) kN, так как при x=k
функция (x, y)= J21(x, y) ни для какого значения у не будет равной нулю.
Основной тезис Черча.
Утверждение:
«Какова бы ни была вычислимая неотрицательная функция от
неотрицательных целочисленных аргументов, существует тождественно
равная ей рекурсивная функция» - основной тезис Черча.
Перенеся тезис Черча на алгоритмы, сопутствующие рекурсивным
функциям, можно высказать и следующую гипотезу: «Каков бы ни был
алгоритм, перерабатывающий наборы целых неотрицательных чисел в целые
неотрицательные числа, существует алгоритм, сопутствующий рекурсивной
функции, который ему эквивалентен».
Приведенные гипотезы означают, что выполнение алгоритма в
определенном смысле эквивалентно вычислению значений рекурсивной
функции, а невозможность рекурсивной функции означает и невозможность
алгоритма (так как для каждого алгоритма должна быть рекурсивная
функция, а ее-то в данном случае и нет).
Напомним, что тезис Черча и следующие из него другие гипотезы не имеют
доказательства и принципиально не могут быть доказаны, так как в них речь
53

идет об алгоритмах в интуитивном смысле, не являющихся математическими
объектами.
Алгоритмически неразрешимые проблемы.
Массовые проблемы, для которых не существует эффективных методов
разрешения, называются алгоритмически неразрешимыми проблемами.
В интуитивном смысле массовая (алгоритмическая) проблема – это
бесконечный класс родственных единичных конкретных проблем,
правильный ответ для каждой из которых получается применением
алгоритма.
Фактически произвольную массовую проблему можно сформулировать как
проблему распознавания некоторого свойства Р элементов бесконечного
множества М; при этом единичные проблемы. составляющие массовую
проблему, связываются с элементами множества М, и каждая из них состоит
в том, что требует узнать, обладает или нет свойством Р соответствующий
элемент множества М. Поэтому задача ставится так: найти алгоритм,
применимый к любому элементу множества М и для каждого данного хМ
дает «1» или «0» в зависимости от того, обладает или нет элемент х
свойством Р. Массовая проблема называется неразрешимой, если такого
алгоритма нет.
Очевидно, принципиально неразрешимыми должны быть алгоритмы
получения объектов, которые парадоксальны, или решения проблем, из
которых вытекало бы (если бы они были разрешимы) существование
объектов.
Понятие алгоритмической неразрешимости уточняется с привлечением
математических понятий машины Тьюринга, рекурсивных функций,
нормальных алгоритмов и других.
Известны два способа доказательства неразрешимости: прямой и
косвенный, использующий сводимость к данной проблеме другой массовой
проблеме, неразрешимость которой была доказана раньше.
Напоминание:
В настоящее время алгоритмические проблемы формируются как проблемы
решения вопроса о существовании алгоритма для решения данной
бесконечной серии однотипных задач и нахождения такого алгоритма в
случае, если он существует.

54