Волжский Университет им. Татищева.

Лекции по математической логике и теории алгоритмов.

Составитель: доцент С.В. Каверин.

Тольятти 2002.

Содержание

Содержание.................................................................................................. 1

Глава I. Алгебра логики.............................................................................. 2

§1.1. Определение булевой функции.......................................................... 2

§1.2. Элементарные булевы функции......................................................... 3

§1.3. Задание булевых функций посредством элементарных.................... 5

§1.4. Существенные и несущественные переменные.................................. 6

§1.5. Таблицы истинности. Эквивалентные функции................................. 6

§1.6. Основные эквивалентности................................................................. 7

§1.7. Функциональная полнота................................................................... 8

Глава II. Булева алгебра............................................................................ 11

§2.1. Нормальные формы.......................................................................... 11

§2.2. Совершенные нормальные формы.................................................. 13

§2.3. Минимизация ДНФ методом Квайна............................................... 17

§ 2.4. Карты Карно.................................................................................... 20

Глава III. Алгебра Жегалкина................................................................... 23

Глава IV. Высказывания. Предикаты....................................................... 25

§4.1. Высказывания................................................................................... 25

§4.2. Предикаты. Логические операции над предикатами....................... 26

§4.3. Кванторы, их свойства...................................................................... 27

Глава V. Формальные теории................................................................... 29

§5.1. Определение формальной теории.................................................... 29

§5.2. Исчисление высказываний................................................................ 30

§5.3. Теорема о дедукции. Полнота ИВ................................................... 32

§5.4. Автоматическое доказательство теорем.......................................... 33

§5.5. Метод резолюций в ИВ.................................................................... 33

Глава VI. Элементы теории алгоритмов.................................................. 35

§6.1. Определение алгоритма.................................................................... 35

§6.2. Машина Тьюринга............................................................................ 36

§6.3. Рекурсивные функции....................................................................... 40

§6.4. Алгоритмически неразрешимые задачи.......................................... 43

§6.5. Алгоритмы и их сложности.............................................................. 44

ЛИТЕРАТУРА........................................................................................... 46

Глава I. Алгебра логики.

§1.1. Определение булевой функции.

Булевой функцией y=f(x ₁ ,x ₂ ,…,x _n )отп переменных x ₁ , x ₂ ,...,x _n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц

(x ₁ ,x ₂ ,...,x n ) ставится в соответствие значение 0 или 1.

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

Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2ⁿ -1 (такой порядок расположения наборов назовем лексикографическим порядком ). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо n

1, заключаем, что существует всего 22 различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.

Пример 1.1.1. (голосование). Рассмотрим устройство, фиксирующее принятие некоторой резолюции "комитетом трех". Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют «за», то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z) , таблица истинности которой имеет вид

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

Вектором значений булевой функции y=f(x₁ ,x₂ ,…,x_n ) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

§1.2. Элементарные булевы функции.

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

1. Булева функция f(x ₁ ,x ₂ ,…,x _n ) принимающая значение 1 на всех наборах нулей и единиц называется константой 1 , или тождественной единицей. Обозначение: 1 .

2. Булева функция f(x ₁ ,x ₂ ,…,x _n ) принимающая значение 0 на всех наборах нулей и единиц называется константой 0 , или тождественным нулем. Обозначение: 0 .

3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности

Обозначения: Ÿx , x . Запись Ÿx читается «не икс» или «отрицание икс».

4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другие названия: логическое умножение (произведение); логическое «и».

Обозначения: x&y, xÿy, x⁄y, min(x,y).

Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».

5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другие названия: логическое сложение (сумма); логическое «или».

Обозначения: x¤y, max(x,y).

Запись x¤y может читаться так: «икс или игрек» или «сумма икс и игрек».

6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: логическое следование. Обозначения: xØy, xfly, xy.

Запись xØy может читаться так: «из икс следует игрек».

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

Обозначения: x~y, x¨y,.xªy.

Запись x~y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».

8. Суммой по модулю_2 называется булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: антиэквивалентность. Обозначения: x∆y, x+y.

Запись x∆y может читаться так: «икс плюс игрек».

9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: отрицание конъюнкции, логическое «не-и».

Обозначение: x|y.

Запись x|y может читаться так: « не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности

Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.

Обозначение: x∞y; для функции Вебба - x±y.

Запись x∞y может читаться так: «ни икс и ни игрек», «икс стрелка Пирсаигрек».

Замечание. Символы Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ участвующие в обозначениях элементарных функций будем называть связками или операциями.

§1.3. Задание булевых функций посредством элементарных.

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

Пример 1.3.1. Пусть задана элементарная булева функция x¤y. Подставим вместо x функцию x₁ ∞x₂ . Получаем функцию трех переменных (x₁ ∞x₂ )¤y. Если вместо переменной y подставить, например, x₃ ∆x₄ , то получаем новую функцию от четырех переменных: (x₁ ∞x₂ )¤(x₃ ∆x₄ ). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

Для более компактной записи сложных функций введем следующие соглашения: 1) внешние скобки опускаются; 2) сначала производятся операции в скобках; 3) считается, что приоритет связок убывает в следующем порядке: Ÿ, ⁄, ¤, Ø, ~. Для равносильных связок и оставшихся связок {∆,|,∞}, следует пока расставлять скобки.

Примеры 1.3.2. В формуле x⁄y¤z скобки расставляются следующим образом: ((x⁄y)¤z), т.к. операция ⁄ сильнее операции ¤ согласно нашему соглашению.

1. В формуле x¤y~zØx скобки расставляются следующим образом: ((x¤y)~(zØx))

2. В формуле (x∆y)~zØxy¤Ÿz скобки расставляются следующим образом: ((x∆y)~(zØ((xy)¤(Ÿz)))).

3. Формула xØyØz, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((xØy)Øz) и (xØ(yØz)).

§1.4. Существенные и несущественные переменные.

Булева функция y=f(x ₁ ,x ₂ ,…,x _n ) существенно зависит от переменной x _k , если существует такой набор значений a ₁ ,a ₂ ,…,a _{k - 1} , a k + 1 ,a k + 2 ,…,a n , что f(a 1,a 2,…,a k-1 , 0 ,a k+1,a k+2,…,a n) π f(a 1,a 2,…,a k-1 , 1 ,a k+1,a k+2,…,a n).

В этом случае x _k называют существенной переменной, в противном случае x _k называют несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции.

Пример 1.4.1. Пусть булевы функции f₁ (x₁ ,x₂ ) и f₂ (x₁ ,x₂ ) заданы следующей таблицей истинности:

Для этих функций переменная x₁ — существенная, а переменная x₂ —несущественная.

Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать: f ₁ (x ₁ ,x ₂ )=x ₁ , f ₂ (x ₁ ,x ₂ )=Ÿx ₁ ).

§1.5. Таблицы истинности. Эквивалентные функции.

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

Пример 1.5.1. F1=x₁ ⁄x₂ ¤(x₁ ⁄Ÿx₂ ¤Ÿx₁ ⁄x₂ )

Таким образом, формула F1реализует дизъюнкцию. Пример 1.5.2. F2=x₁ ⁄x₂ Øx₁

Таким образом, формула F2реализует константу 1. Пример 1.5.3. F3=((x₁ ⁄x₂ )∆x₁ )∆x₂ .

Таким образом, формула F3реализует дизъюнкцию.

Булевы функции f1 и f2 называются эквивалентными , если на всяком наборе (a ₁ , a ₂ ,…, a_n ) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: f1=f2.

Согласно приведенным примерам 1-3, можно написать

• x₁ ⁄x₂ ¤(x₁ ⁄Ÿx₂ ¤Ÿx₁ ⁄x₂ )=x₁ ¤x₂ ;

• x₁ ⁄x₂ Øx₁ =1;

• ((x₁ ⁄x₂ )∆x₁ )∆x₂ =x₁ ¤x₂ .

§1.6. Основные эквивалентности.

Приводимые эквивалентности часто оказываются полезными при оперировании с булевыми функциями.

Ниже H, H1, H2,… означают некоторые булевы функции.

1. Закон двойного отрицания : H = H .

2. Идемпотентность

H&H=H, H¤H=H.

3. Коммутативность:

H1*H2=H2*H1, где символ * означает одну из связок &, ¤, ∆,

~, |, ∞.

4. Ассоциативность:

H1*(H2*H3)=(H1*H2)*H3, где символ * означает одну из связок &, ¤, ∆, ~.

5. Дистрибутивность:

H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).

6. Законы де Моргана:

H1& H2 = H1 ∨ H2 , H1∨ H2 = H1 & H2 .

7. Правила поглощения:

H1¤(H2&H3)=H1, H1&(H2¤H3)=H1

8. Законы склеивания:

H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.

9. Законы инверсий: H ∨ H = 1, H & H = 0.

10. Правила операций с константами:

H¤1=1, H&1=H, H¤0=H, H&0=0.

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

Отметим, что свойство ассоциативности операции позволяет распространить эту операцию для любого количества переменных. Так, например, запись x¤у¤z¤w корректна, т.к. любая расстановка скобок приводит к одной и той же функции. Коммутативность операции позволяет менять местами переменные в формуле. Например, x⁄y⁄z⁄w=w⁄y⁄x⁄z.

§1.7. Функциональная полнота.

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

Введем в рассмотрение ряд классов функций.

1. Класс функций, сохраняющих константу 0, т.е. таких функций

y=f(x ₁ ,x ₂ ,…,x _n ),что f(0,0,…,0)=0. Например, x¤y(Ÿx).

2. Класс функций, сохраняющих константу 1, т.е. таких функций

y=f(x ₁ ,x ₂ ,…,x _n ),что f(1,1,…,1)=1. Например, x¤Ÿ(yx).

3. Класс самодвойственных функций, т.е. таких функций y=f(x ₁ ,x ₂ ,…,x _n ), что f(x ₁ , x ₂ ,… , x _n ) = f( x ₁ , x ₂ ,… , x _n ) .

4. Класс линейных функций, т.е. таких функций y=f(x ₁ ,x ₂ ,…,x _n ), которые могут быть представлены в виде f(x ₁ ,x ₂ ,…,x _n )=c ₀ ∆c ₁ x ₁ ∆c ₂ x ₂ ∆…∆c _n x _n , где с₀ , c₁ , c₂ …коэффициенты, которые могут принимать значение 0 или 1.

5. Класс монотонных функций. На множестве наборов из нулей и единиц ^Вn ={(x ₁ ,x ₂ ,…,x _n ):x _i œ{0,1},i=1,2,…,n} введем частичный порядок следующим образом:

(a ₁ ,,a₂ ,...,a_n )§(b ₁ ,b₂ ,...,b_n ) тогда и только тогда когда a ₁ §b ₁ , a₂ §b₂ ,…,a _n §b _n . Функция f(x₁ , х₂ ,...,х_n ) называется монотонной, если для любых двух элементов из Вⁿ таких, что

(a ₁ ,,a₂ ,...,a_n )§(b ₁ ,b₂ ,...,b_n ) следует, что f(a ₁ ,,a₂ ,...,a_n )§f(b ₁ ,b₂ ,...,b_n ).

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

Критерий полноты (Теорема Поста). Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.

В таблице 1.7 приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция).

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

Построим некоторые часто используемые в приложениях базисы.

Таблица 1.7

1. Система функций S1={Ÿ,⁄,¤} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности: x → у = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , x y = x ∨ y , x ↓ y = x & y .

2. Система S2={Ÿ,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем

использовать соотношение x ∨ y = x ⋅ y .

3. Система S3={Ÿ,¤} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем

использовать соотношение x ⋅ y = x ∨ y .

4. Система S4={1,&,∆} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения x = 1⊕ x , x ∨ y = x ⊕ y ⊕ x ⋅ y .

5. Система S5={|} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения x ⋅ y = x y , x = x x .

6. Система S6={∞} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем

использовать соотношения x ∨ y = x ↓ y , x = x ↓ x .

7. Система S7={Ø,0} образует базис.

Пример 1.7.1. Записать функцию x¨(y∆z) в базисе S1={Ÿ,⁄,¤}. x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)

Глава II. Булева алгебра.

Множество всех булевых в базисе S1={ ÿ, &, ⁄} образуют булеву алгебру . Таким образом в булевой алгебре все формулы записываются при помощи трех связок: Ÿ, &, ¤. Частично свойства этой алгебры мы рассмотрели в главе I (см., например, основные эквивалентности). В этой главе рассматриваются свойства, специфичные для булевой алгебры и поэтому везде в этой главе мы будем иметь дело только с тремя функциями:ÿ, &, ⁄.

§2.1. Нормальные формы.

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

Если х - логическая переменная, а σœ{0,1} то выражение x _σ = x если_если σσ == 10 или x _σ = 10 если_если x x =≠σσ , x называется литерой. Литеры x и Ÿx называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x являются конъюнктами, формулы x ∨ y ∨ z и x ∨ y ∨ x - дизъюнктами, а формула z является одновременно и конъюнктом и дизъюнктом.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.

Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм Примеры.

1. xÿy¤yÿz¤x ― это ДНФ (сумма произведений).

2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z ―это КНФ (произведение сумм).

3. x ∨ y ∨ z ∨ w ― это ДНФ и КНФ (одновременно).

4. x ⋅ y ⋅ z ⋅ w ― это ДНФ и КНФ (одновременно).

5. (x¤x¤y)·(y¤z¤x)·z ― это КНФ.

6. x⋅y⋅z и x⋅y⋅x⋅x ― это ДНФ.

7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z ― это не нормальная форма (не ДНФ и не КНФ).

Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:

1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;

2) применяем правило снятия двойного отрицания: ŸŸx=x;

3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ

H1&(H2¤H3)=(H1&H2)¤(H1&H3) , и второй закон дистрибутивности для приведения к КНФ. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).

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

Пример 2.1.1. Для приведения к ДНФ используем 1-ый закон дистрибутивности.

x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y⋅z)⋅(y∨z)= -это КНФ

= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = -это другая КНФ

= x ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y⋅z =

= x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z -это ДНФ

Пример 2.1.2 . Для приведения к КНФ необходимо использовать второй закон дистрибутивности.

x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =

=x∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=

= ( x ∨ y ) ⋅ ( x ∨ z ) это КНФ

§2.2. Совершенные нормальные формы.

Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ). Примеры: Пусть задана функция трех переменных f(x,y,z).

1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z- это совершенная ДНФ.

2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z)- это совершенная КНФ.

3. ( x ∨ y ) ⋅ ( x ∨ z )- это не совершенная КНФ, т.к. например, в первую сумму не входит переменная z.

4. xÿyÿz - это совершенная ДНФ. Теорема 2.2.1.

1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов.

2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов.

Доказательство теоремы проведем конструктивно, как решение следующей задачи: по данной таблице истинности построить СДНФ.

Решение рассмотрим на примере функции f(x,y,z) заданной таблично (таб.2.2) при n=3.

Пример 2.2.1. По данной таблице истинности (таб.2.2) построить СДНФ.

Решение.

Таблица 2.2

Основные конъюнкции (или конституенты_1 ), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x,y,z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные x,y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равнаx ⋅ y ⋅ z .

Очевидно, что конъюнкция x ⋅ y ⋅ z равна 1 только на наборе

(0,0,0), а x ⋅ y ⋅ z равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция x ⋅ y ⋅ z¤x ⋅ y ⋅ z равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.

Т.о. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .

Задача. По данной таблице истинности построить СКНФ.

Конституента_0 для набора нулей и единиц (которые принимают переменные x,y,z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0 , в противном случае в произведение входит ее отрицание.

Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0 , а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .

Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции f , а затем

использовать f =f и законы де Моргана.

Построим СКНФ для нашего примера на основании замечания. 1. Строим СДНФ для отрицания.

x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z

2. Используем законы де Моргана f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .

Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.

1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.

2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная у, то этот конъюнкт заменяем на эквивалентную формулу K&(y ∨ y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (y ∨ y) .

3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.

Замечание : Для построения СКНФ в дизъюнкт не содержащий скажем переменную у добавляем формулу вида y⋅ y, т.е. этот дизъюнкт заменяем на эквивалентную формулу D ∨ y⋅ y и, применяя 2-й закон дистрибутивности.

Пример 2 . 2 . 2 . Построить СДНФ для функции f при помощи эквивалентных преобразований.

f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) = = x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =

ОТСТУПЛЕНИЕ.

Вычисление СДНФ имеет не только теоретическое, но и большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланк в виде таблицы: в клетках записываются условия, причем клетки одного столбца считаются соединенными конъюнкцией, а столбцы — дизъюнкцией, то есть образуют ДНФ (или наоборот, в таком случае получается КНФ). В частности, так устроен графический интерфейс QBE (Query-byExample), применяемый для формулировки логических условий при запросе к СУБД.

Алгоритм 2.2.1. Построение СДНФ

Вход : вектор Х: array [l..n] of string - идентификаторов переменных, матрица V: array [1..2ⁿ , l..n] of 0..1 всех различных наборов значений переменных,

вектор F: array [1..2ⁿ ] of 0..1 соответствующих значений функции.

Выход: последовательность символов, образующих запись формулы СДНФ для заданной функции.

f:= false { признак присутствия левого операнда дизъюнкции }for i from 1 to 2ⁿ do

if F[i] = 1 then if f then

yield '^¤ ' { добавление в формулу знака дизъюнкции; оператор yield m выводит на печать

символ m}else f:=true

end if g:=false { признак присутствия левого операнда конъюнкции }for j from 1 to n do if g then

yield '⁄' {добавление в формулу знака конъюнкции }

else g: =true

end if if V[i,j}=0 then

yield 'Ÿ' { добавление в формулу знака отрицания }

end if yield X[j] { добавление в формулу идентификатора переменной

}

end for

end if

end for

§2.3. Минимизация ДНФ методом Квайна.

Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных.

Если х - логическая переменная, а σœ{0,1} то выражение x_σ =xx если_если σσ== 10 _.

называется литерой . Конъюнктом называется конъюнкция литер. Например, формулы x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x являются конъюнктами. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание).

Формула f1 называется импликантой формулы f, если f1 — элементарное произведение и f 1 ⁄ f = f 1 ,т. е. для соответствующих формулам функций справедливо неравенство f 1 § f . Импликанта f1 формулы f называется простой , если после отбрасывания любой литеры из f1 не получается формула, являющаяся импликантой формулы f.

Пример 2.3.1 . Найдем все импликанты и простые импликанты для формулы f=xØy. Всего имеется 8 элементарных произведений с переменными х и у. Ниже, для наглядности, приведены их таблицы истинности:

Из таблиц истинности заключаем, что формулы x ⋅ y , x ⋅ y , x ⋅ y , x ,y— все импликанты формулы xØy, а из этих импликант простыми являются формулы x и у (формула x ⋅ y , например, не является простой импликантой, поскольку, отбрасывая литеру y , получаем импликанту x ).

Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции).

Теорема 2.3.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

В примере 2.3.1 функция, соответствующая формулe xØy представима формулой x ∨ y которая является ее сокращенной ДНФ.

Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.

Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ {МДНФ).

Рассмотрим метод Квайна, для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции:

1. операция полного склеивания: f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;

2. операция неполного склеивания:

f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;

3. операция элементарного поглощения f ⋅ x ^σ ∨ f = f , σ ∈ {0,1} .

Теорема 2.3.2 (теорема Квайна). Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.

Пример 2.3.2 . Пусть функция f(x,y,z) задана совершенной ДНФ f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Тогда, производя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем

f

Таким образом, сокращенной ДНФ функции f является формула y¤x·z.

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

Пример 2 . 3 . 3 . Пусть функция f{x,y,z) задана совершенной ДНФ f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .

Тогда, производя операции склеивания, а затем элементарного поглощения, имеем

f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z

Для получения минимальной ДНФ из сокращенной ДНФ используется матрицаКвайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.

Для примера 2.3.3. матрица Квайна имеет вид

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

В примере 2.3.3 по матрице Квайна находим, что минимальная ДНФ заданной функции есть x ⋅ y ¤ x ⋅ z .

Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем

использовать f =f и законы де Моргана.

§ 2.4. Карты Карно.

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

Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2ⁿ клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.

В таб.2.4.1. показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. В таб.2.4.2. приведена разметка карты Карно для n=4 переменных.

таблица 2.4.1. таблица 2.4.2.

Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток).

Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила;

1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2^m где m=0,1,2,...

2. Каждая клетка, входящая в группуиз 2^m клеток, должна иметь m соседних в группе.

3. Каждая клетка должна входить хотя бы в одну группу.

4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.

5. Число групп должно быть минимальным.

Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.

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

А) n=3

F=z f=Ÿx F=Ÿy

F=Ÿz&Ÿy f=Ÿx&y

B) n=4

F=w f=Ÿy F=Ÿz

F=Ÿx&z f=y&w F=Ÿx&Ÿy

F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx

F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz

Пример 2.4.1. Построить МДНФ.

Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий два. Переходим к покрытиям из 2 клеток. Такое покрытие одно. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. В конце выписываем МДНФ: f =x⋅z∨y⋅w∨y⋅z⋅w.

Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем

использовать f =f и законы де Моргана.

Глава III. Алгебра Жегалкина.

Множество булевых функций, заданный в базисе Жегалкина S4={∆,&,1} называется алгеброй Жегалкина.

Основные свойства.

1. коммутативность

H1∆H2=H2∆H1, H1&H2=H2&H1;

2. ассоциативность

H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)&H3;

3. дистрибутивность

H1&(H2∆H3)=(H1&H2)∆(H1&H3);

4. свойства констант H&1=H, H&0=0, H∆0=H;

5. H∆H=0, H&H=H.

Утверждение 3.1.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции:

Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y=1∆xy.

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x₁ ,x₂ ,…,x_n называется выражение вида c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, где постоянные с_к могут принимать значения 0 ли 1.

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

Например, f=x∆yz∆xyz и f1=1∆x∆y∆z–полиномы, причем второй является линейной функцией.

Теорема 3.1.1. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Приведем основные методы построения полиномов Жегалкина от заданной функции.

1. Метод неопределенных коэффициентов. Пусть P(x₁ ,x₂ ,…,x_n ) - искомый полином Жегалкина, реализующий заданную функцию f(x₁ ,x₂ ,…,xn). Запишем его в виде

P= c₀ ∆с₁ x₁ ∆c₂ x₂ ∆…∆c_n x_n ∆c₁₂ x₁ x₂ ∆…∆c12…_n x₁ x₂ …x_n .

Найдем коэффициенты с_к . Для этого последовательно придадим переменным x₁ ,x₂ ,…,x_n значения из каждой строки таблицы истинности. В итоге получим систему из 2ⁿ уравнений с 2ⁿ неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(x₁ ,x₂ ,…,xn).

2. Метод, основанный на преобразовании формул над множеством связок { ÿ,&}. Строят некоторую формулу Ф над множеством связок{Ÿ,&}, реализующую данную функцию f(x₁ ,x₂ ,…,x_n ). Затем заменяют всюду подформулы вида A на A∆1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример 3.1.1. Построить полином Жегалкина функции f(x,y)=xØy.

Решение. 1 . (метод неопределенных коэффициентов). Запишем искомый полином в виде

P(x,y)= c₀ ∆с₁ x∆c₂ y∆c₁₂ xy Пользуясь таблицей истинности

получаем, что f(0,0)=P(0,0)= c₀ =1, f(0,1)=P(0,1)= c₀ ∆ c₂ =1, f(1,0)=P(1,0)= c₀ ∆ c₁ =0, f(1,1)=P(1,1)= c₀ ∆с₁ ∆c₂ ∆c₁₂ =1

Откуда последовательно находим, c₀ =1, с₁ =1, c₂ =0, c₁₂ =1. Следовательно xØy=1∆x∆xy (сравните с утверждением 3.1).

2.(Метод преобразования формул.) Имеем

x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .

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

Глава IV. Высказывания. Предикаты.

§4.1. Высказывания.

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

Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно (значение Л или 0) в конкретный момент времени. Например, «5-простое число», «нажата клавиша «Esc»» и т.д. При помощи связок «не», «и», «или», «если,… то», «если и только если» (им отвечают операции «Ÿ», «&», «¤», «Ø», «~» соответственно) можно построить более сложные высказывания (предложения). Так строится алгебра высказываний.

Для упрощения записи сложных высказываний вводится старшинство связок: «Ÿ», «&», «¤», «Ø», «~», что помогает опустить лишние скобки.

Простые высказывания назовем пропозициональными переменными.

Введем понятие формулы.

1. Пропозициональные переменные являются формулами.

2. Если А, В формулы, то выражения ŸА, А⁄В, А¤В, АØВ, А~В являются формулами.

3. Формулами являются только выражения построенные в соответствии с пп.1 и 2.

Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией (или общезначимой), а формула, принимающая значение Л при всех значениях пропозициональных переменных называется противоречием (или невыполнимой)

Описание свойств алгебры высказываний аналогично описанию соответствующих функций в булевой алгебре и мы их опускаем.

§4.2. Предикаты. Логические операции над предикатами.

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

Определение 2.1 Пусть x₁ ,x₂ ,…,xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x₁ ,x₂ ,…,x_n ) принадлежат множеству M=(M1,M2,…Mn), которое будем называть предметной областью (т.е. x_i œM_i , где Мi называются областью определения переменной хi). Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л.

Пример 4.2.1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двуместный предикат, определенный на множестве пар натуральных чисел M=NäN. Очевидно, D(4,2) = И, D(3,5) = 0.

Пример 4.2.2 . Q(x) ==«x² <-1, хœR» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е.

Q(x) = Л для всех хœR.

Пример 4.2.3. В(x,у,z) =«х² +y² <z; х,у,zœR.» — трехместныйпредикат,определенный на R³ . В(1,1,-2)=Л, В(1,1,2)=И.

Предикат Р, определенный на M, называется тождественно истинным, если он принимает значение И при любых значениях предметных переменных; Предикат Р называется тождественно ложным, если он принимает значение Л при любых значениях предметных переменных. Предикат Q из примера 4.2.2. является тождественно ложным.

Поскольку предикаты — это функции со значениями во множестве высказыраний, где введены логические операции, то эти операции естественно определяются и для предикатов. Пусть P и Q — предикаты, определенные наM. Тогда

1. ¬P(x , x ,…, x_n ) = P(x , x ,…, x )

^∧ 1 2 n 1 2 n ^∧ 1 2 n

3. (P ∨ Q)(x₁ ,x₂ ,…,x_n ) = P(x₁ ,x₂ ,…,x_n ) ∨ Q(x₁ ,x₂ ,…,x_n )

4. (P → Q)(x₁ ,x₂ ,…,x_n ) = P(x₁ ,x₂ ,…,x_n ) → Q(x₁ ,x₂ ,…,x_n ) Предикаты Р и Q, определенные на M, называются равносильными (пишут Р=Q), если P(x₁ ,x₂ ,…,xn)=Q(x₁ ,x₂ ,…,xn)для любого набора (x₁ ,x₂ ,…,x_n ) предметных переменных изM.

Теорема 4.2.1 Множество n-местных предикатов, определенных на M, образует булеву алгебру предикатов. Т.о., для них справедливы основные эквивалентности (см. §1.6).

§4.3. Кванторы, их свойства.

Пусть P(x₁ ,x₂ ,…,xn) — n-местный предикат, определенный на M. Зафиксируем x_i =a . Определим (n-1)-местный предикат Q(x₁ ,x₂ ,…,xk-1, xk+1,xn) следующим образом: Q(x₁ ,x₂ ,…,xk-1,xk+1,xn)=P(x₁ ,x₂ ,…,xk1,a ,xk+1,xn). Говорят, что предикат Q(x₁ ,x₂ ,…,xk-1, xk+1,xn) получен из предиката P(x₁ ,x₂ ,…,xn) фиксацией значения i-й переменной: x_i =a .

Определение 4.3.1 . Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое "xP(x) (читается «для любого х Р(х)»}, которое истинно тогда и только тогда, когда Р(х) — тождественно истинный предикат. О высказывании "xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.

Определение 4.3.2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое $xP(x) (читается «существует х Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании $xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования по переменной х.

Замечание 1. Обозначения " и $ для кванторов — это перевернутые латинские буквы А и Е соответственно, которые являются первыми буквами в английских словах All — все, Exist — существовать.

Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, т. е. 0-местными предикатами (или предикатами любой местности).

Пусть P(x₁ ,x₂ ,…,xn) — n-местный предикат, определенный на M. Зафиксируем в нем значения переменных x₁ ,x₂ ,…,x_k-1 ,x_k+1 ,x_n . На полученный одноместный предикат Q(x_к ) навесим квантор всеобщности (существования), получим высказывание. Тем самым фиксированному набору значений переменных x₁ ,x₂ ,…,x_k-1 ,x_k+1 ,x_n с помощью квантора всеобщности (существования) поставлено в соответствие высказывание. Говорят, что этот (n-1)-местный предикат переменных x₁ ,x₂ ,…,x_k-1 ,x_k+1 ,x_n получен из исходного предиката P(x₁ ,x₂ ,…,x_n ) навешиванием квантора всеобщности (существования) по k-й переменной. Этот предикат обозначают: "x_к P(x₁ ,x₂ ,…,x_n ) ($x_к P(x₁ ,x₂ ,…,x_n )). Об к-й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования).

Пример 4.3.1. Пусть D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2.» — двухместный предикат.

Навесим последовательно на его переменные кванторы. Ясно, что

1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1

4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2)=0 8) "x1$x2D(x1,x2)=1.

Таким образом (сравнением 7 и 8 в последнем примере) мы доказали теорему:

Обычно, связки и кванторы упорядочиваются по приоритету следующим образом Ÿ, ", $, &, ¤, Ø, ~.

Теорема 4.3.1. Разноименные кванторы, вообще говоря, не коммутируют.

Теорема 4.3.2. (основные равносильности, содержащие кванторы) Имеют место следующие равносильности:

1. Законы де Моргана

∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x)

2. Коммутативность

∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y)

3. Дистрибутивность

∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x)

4. Ограничения действия кванторов

∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y)

5. Для любого двухместного предиката

∃y∀xP(x,y) →∀x∃yP(x,y) =1

Глава V. Формальные теории.

§5.1. Определение формальной теории.

Формальная теория (или исчисление) Y — это:

1. множество A символов, образующих алфавит ;

1. множество F слов в алфавите A, F ÃA , которые называются формулами ;

3. подмножество B формул, B ÃF , которые называются аксиомами;

4. множество отношений R на множестве формул, которые называются правилами вывода.

Множество символов A может быть конечным или бесконечным. Обычно для образования символов используют конечное множество букв, к которым, если нужно, приписываются в качестве индексов натуральные числа.

Множество формул F обычно задается индуктивным определением, например, с помощью формальной грамматики. Как правило, это множество бесконечно. Множества A и F в совокупности определяют язык , или сигнатуру , формальной теории.

Множество аксиом B может быть конечным или бесконечным. Если множество аксиом бесконечно, то, как правило, оно задается с помощью конечного множества схем аксиом и правил порождения конкретных аксиом из схемы аксиом.

Множество правил вывода R , как правило, конечно. Итак, исчисление Y есть четверка (A, F, B, R) .

Выводом в исчислении Y называется последовательность формул F₁ ,F₂ ,…,Fn такая, что для любого k (1§k§n) формула Fk есть либо аксиома исчисления Y, либо непосредственное следствие каких-либо предыдущих формул, полученное по правилу вывода.

Формула G называется теоремой исчисления Y (выводимой в Y или доказуемой в Y), если существует вывод F₁ ,F₂ ,…,F_n ,G который называется выводом формулы G или доказательством теоремы G.

Записывается это следующим образом: F₁ ,F₂ ,…,F_n + G.

Исчисление Y называется непротиворечивым , если не все его формулы доказуемы. Можно дать другое определение непротиворечивости: ИсчислениеY называется непротиворечивым, если в нем не являются выводимыми одновременно формулы F и ŸF (отрицание F).

Исчисление Y называется полным (или адекватным), если каждому истинному высказыванию М соответствует теорема теории Y .

Формальная теория Y называется разрешимой , если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой теории Y или нет.

§5.2. Исчисление высказываний.

Используя понятие формального исчисления, определим исчисление высказываний (ИВ).

Алфавит ИВ состоит из

1. букв А, В, Q, R, Р и других, возможно с индексами

(которые называются пропозициональными переменными},

2. логических символов (связок) Ÿ, &, ¤, Ø, 3. вспомогательных символов (,).

Множество формул ИВ определяется индуктивно:

1. все пропозициональные переменные являются формулами ИВ;

2. если A, B —.формулыИВ, тоŸA, A⁄B, A¤B, AØB — формулыИВ;

3. выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "1" и

"2".

Таким образом, любая формула'ИВ строится из пропозициональных переменных с помощью связок Ÿ, ⁄, ¤, Ø.

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

Аксиомами ИВ являются следующие формулы (для любых формул A,B,C)

1. AØ(BØA);

2. (AØB)Ø((AØ(BØC))Ø(AØC));

3. (A⁄B)ØA;

4. (A⁄B)ØB;

5. (AØB)Ø((AØC)Ø(AØ(B⁄C)));

6. AØ(A¤B);

7. AØ(B¤A);

8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA);

10. ŸŸAØA.

Указанные формулы называются схемами аксиом ИВ. При подстановке конкретных формул в какую-либо схему получается частный случай схемы аксиом.

Правилом вывода в ИВ является правило заключения {modus ponens): если A и AØB — выводимые формулы, то B — также выводимая

формула.

Символически это записывается так: ^{A , A} _B ^{→ B} .

Например, если высказывания А⁄В и А⁄ВØ(АØС) выводимы, то высказывание АØС также выводимо согласно правилу заключения.

Говорят, что формула G выводима из формул F₁ ,F₂ ,…,F_n (обозначается F₁ ,F₂ ,…,F_n +G), если существует последовательность формул F₁ ,F₂ ,…,F_k ,G, в которой любая формула является либо аксиомой, либо принадлежит списку формул F₁ ,F₂ ,…,F_n (называемых гипотезами), либо получается из предыдущих формул по правилу вывода. Выводимость формулы G из « (обозначается +G) равносильно тому, что G — теорема ИВ.

Пример 5.2.1 . Покажем, что формула AØA выводима в ИВ. Для этого построим вывод данной формулы:

1) в аксиоме 2 заменим B на AØA, C — на A.

Получаем аксиому

(AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA));

2) в аксиоме 1 заменим B на A. Получаем AØ(AØA);

3) из 1 и 2 по modus ponens заключаем

(AØ((AØA)ØA))Ø(AØA);

4) в аксиоме 1 заменяем B на AØA. Получаем AØ((AØA)ØA);

5) из пп. 3 и 4 по правилу вывода справедливо + AØA.

Теорема 5.2.1.

1. Если F₁ ,F₂ ,…,Fn,A,B — формулы ИВ, Г={F₁ ,F₂ ,…,Fn}, Г+A, то Г,B+A. (можно увеличивать число гипотез).

2. Тогда и только тогда F₁ ,F₂ ,…,F_n +A, когда F₁ ⁄F₂ ⁄…⁄F_n +A (сведение множества гипотез к одной гипотезе).

§5.3. Теорема о дедукции. Полнота ИВ.

Теорема 5.3.1. (теорема о дедукции)

Если Г,B+A, то Г+BØA, где Г — набор некоторых формул Г={F₁ ,F₂ ,…,F_n }.

Следствие 5.3.1. Тогда и только тогда F₁ ,F₂ ,…,F_n +A, когда

+ F₁ Ø(F₂ Ø…Ø(F_n-1 Ø(F_n ØA))…)

Доказательство . Пусть F₁ ,F₂ ,…,F_n +A. Тогда, применяя теорему о дедукции, имеем F₁ ,F₂ ,…,F_n-1 +F_n ØA. Аналогично F₁ ,F₂ ,…,F_n-2 +F_n 1Ø(F_n ØA), и т. д. Продолжая процесс необходимое число раз, получаем

+ F₁ Ø(F₂ Ø…Ø(F_n-1 Ø(F_n ØA))…)

Для доказательства достаточности предположим, что +B, где В=F₁ Ø(F₂ Ø…Ø(F_n-1 Ø(F_n ØA))…). Воспользуемся теоремой 5.2.1., п.1:

F₁ +В. По правилу заключения получаем F₁ + (F₂ Ø…Ø(F_n-1 Ø(F_n ØA))…), Далее через n шагов имеем F₁ ,F₂ ,…,F_n +A.

Таким образом, благодаря следствию 5.3.1., проверка выводимости формулы A из формул F₁ ,F₂ ,…,F_n , сводится к проверке доказуемости формулы

F₁ Ø(F₂ Ø…Ø(F_n-1 Ø(F_n ØA))…).

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

Теорема 5.3.2. (о полноте) . Формула A доказуема тогда и только тогда, когда A тождественно истинна (тавтология): +A ‹ A-тавтология.

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

Пример 5.3.1. Докажем, что Р+Р. По теореме о дедукции это равносильно тому, что +(РØР). В свою очередь, по теореме о полноте, достаточно доказать, что (РØР) тавтология. Составляя таблицу истинности для формулы(РØР), убеждаемся, что (РØР) тождественно истинна и, следовательно, доказуема.

Теорема 5.3.3. (о непротиворечивости). Исчисление ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула А⁄(ŸА).

Множество формул Г называется противоречивым , если Г+А⁄(ŸА). Если Г — противоречивое множество формул, будем обозначать этот факт через Г+.

Утверждение 5.3.1. Формула А выводима из множества формул Г тогда и только тогда, когда множество Г»{ŸA} — противоречиво.

§5.4. Автоматическое доказательство теорем.

Автоматическое доказательство теорем — это краеугольный камень логического программирования, искусственного интеллекта и других современных направлений в программировании. Вообще говоря, может не существовать алгоритма, с помощью которого для произвольной формулы А через конечное число шагов можно определить, является ли A выводимой в исчислении Y или нет. Однако, для некоторых простых формальных теорий (например исчисление высказываний) и некоторых простых классов формул (например прикладное исчисление предикатов с одним одноместным предикатом) алгоритмы автоматического доказательства теорем известны. Ниже, на примере исчисления высказываний, излагаются основы метода резолюций — классического и в то же время популярного метода автоматического доказательства теорем.

§5.5. Метод резолюций в ИВ.

Напомним, что если х - логическая переменная, а σœ{0,1} то выражение

x _σ = xx если_если σσ == 10 или x _σ = 10 если_если x x =≠σσ , называется литерой . Литеры x и Ÿx называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер.

Пусть D₁ = B₁ ∨ A , D₂ = B₂ ∨ A — дизъюнкты. Дизъюнкт B₁ ¤B₂ называется резольвентой дизъюнктов D₁ и D₂ по литере А и обозначается через res_A (D₁ ,D₂ ). Резольвентой дизъюнктов D₁ и D₂ называется резольвента по некоторой литере и обозначается через res(D₁ ,D₂ ). Очевидно, что res(A,ŸA)=0. Действительно, т.к. A=A¤0 и ŸA=ŸA¤0, то res(A,ŸA)=0¤0=0. Если дизъюнкты D₁ и D₂ не содержат контрарных литер, то резольвент у них не существует.

Пример 5.5.1. Если

D₁ =A¤B¤C, D₂ = A ∨ B ∨ Q , то

res_A (D₁ ,D₂ )=B¤C¤ B ¤Q, res_B (D₁ ,D₂ )=A¤C¤A¤Q, resC(D₁ ,D₂ ) не существует.

Утверждение 5.5.1. Если res(D₁ ,D₂ ) существует, то D₁ ,D₂ + res(D₁ ,D₂ ).

Пусть S=(D₁ ,D₂ ,…,Dn) - множество дизъюнктов.

Последовательность формул F₁ ,F₂ ,…,F_n называется резолютивным выводом из S, если для каждой формулы F_k выполняется одно из условий:

1. F_k œS;

2. существуют j, k <i такие, что F_i =res(F_j ,F_k ).

Теорема 5.5.1. (о полноте метода резолюций) . Множество дизъюнктов S противоречиво в том и только в том случае, когда существует, резолютивный вывод из S, заканчивающийся 0.

Отметим, что метод резолюций можно использовать для проверки выводимости формулы F из данного множества формул F₁ ,F₂ ,…,F_n . Действительно, условие F₁ ,F₂ ,…,F_n +F равносильно условию F₁ ,F₂ ,…,F_n ,ŸF+ (множество формул противоречиво), что в свою очередь равносильно условию Q+, где Q=F₁ ⁄F₂ ⁄…⁄F_n ⁄(ŸF). Приведем формулу Q к КНФ: Q=D₁ ⁄D₂ ⁄...⁄Dm, тогда Q+ ‹D₁ ⁄D₂ ⁄...⁄Dm+ ‹ D₁ ,D₂ ,...,D_m +. Таким образом, задача проверки выводимости F₁ ,F₂ ,…,F_n +F сводится к проверке противоречивости множества дизъюнктов S={D₁ ,D₂ ,...,D_m }, что равносильно существованию резолютивного вывода 0 из S.

Пример 5.5.2. Проверить методом резолюций соотношение АØ(ВØС), CDØЕ, ŸFØD&(Ÿ)E + АØ(ВØF).

Согласно утверждению 5.3.1. надо проверить на

противоречивость множество формул

S = {АØ(ВØС), CDØЕ, ŸFØD&(Ÿ)E, Ÿ(АØ(ВØF))}.

Приведем все формулы из. S к КНФ:

S = {A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F} == {A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), A ⋅ B ⋅ F} .

Таким образом, получаем множество дизъюнктов S = {A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F}

Построим резолютивный вывод из S, заканчивающийся 0:

1. res _A {A ∨ B ∨ C,A} = B ∨ C ;

2. res _B {B ∨ C,B} = C ;

3. res _D {C ∨ D ∨ E,F ∨ D} = C ∨ E ∨ F ;

4. res _E {C ∨ E ∨ F,F ∨ E} = C ∨ F ;

5. res _C {C, C ∨ F} = F ; 6. res{F, F} = 0 .

Итак, заключаем, что формула АØ(ВØF) выводима из множества формул АØ(ВØС), CDØЕ, ŸFØD&(Ÿ)E .

Отметим, что метод резолюций достаточен для обнаружения возможной выполнимости данного множества дизъюнктов S. Для этого включим в множество S все дизъюнкты, получающиеся при резолютивных выводах из S. Из теоремы о полноте метода резолюций вытекает

Следствие 5.5.1. Если множество дизъюнктов S содержит резольвенты всех своих элементов, то S выполнимо тогда и только тогда, когда 0–S.

Глава VI. Элементы теории алгоритмов.

§6.1. Определение алгоритма.

Характерной чертой современности является широкое использование компьютеров при решении проблем (задач) в различных областях человеческой деятельности. Однако, предварительно задача должна быть решена алгоритмически, т.е. должно быть задано формальное предписание, следуя которому можно получить итоговый результат для решения всех задач определенного типа (это интуитивное, не строгое понятие алгоритма). Например, алгоритм нахождения наибольшего общего делителя двух натуральных чисел а, b , выглядит следующим образом :

1) разложить число a на простые множители;

2) повторить п. 1 для b и перейти к п. 3;

3) составить произведение общих простых множителей из разложений а и b с показателями, равными наименьшим из показателей вхождения в разложения.

Проанализировав этот пример, отметим важнейшие черты (свойства) алгоритма:

1. Массовость — применимость алгоритма не к одной задаче, а к классу задач.

2. Дискретность — четкая разбивка на отдельные этапы (шаги) алгоритма.

3. Детерминированность — такая организация этапов выполнения, при которой всегда ясно как осуществить переход от одного этапа к другому.

4. Конечность — для получения результата при применении алгоритма к решению конкретной задачи выполняется конечная последовательность шагов алгоритма:

Отметим, что если наличие алгоритма само по себе служит доказательством существования алгоритма, то для доказательства его отсутствия необходимо иметь строгое математическое определение алгоритма.

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

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

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

§6.2. Машина Тьюринга.

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

Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A={ a₀ , a₁ ,…, a_n }. Некоторый символ (будем обозначать его Ÿ ) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.

Управляющее устройство в каждый момент времени находится в некотором состоянии q_j , принадлежащем множеству Q={q₀ , q₁ ,..., q_m } (m=l). Множество Q называется внутренним алфавитом . Одно из таких состояний (обычно q₀ ) называется заключительным, а некоторое другое (обычно q₁ ) -начальным.

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

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

Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:

1) последовательностьюa i ( 1 ) , a i ( 2 ) ,..., a i ( s ) символов из внешнего алфавита А , записанных в ячейках ленты, где a i (1) .- символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом), 2) состоянием внутренней памяти q_r ;

3) номером k воспринимаемой ячейки.

Конфигурацию машины будем записывать так:

a ,a ,..., a ^{a i(r)} a ,a ,..., a

i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s)

здесь r -воспринимаемая ячейка, выделяется в виде дроби.

Если машина, находясь во внутреннем состоянии q_i , воспринимает ячейку с символом a_u , записывает к следующему моменту времени в эту ячейку символ a_r , переходит во внутреннее состояние q_s и сдвигается по ленте, то говорят, что машина выполняет команду q_i a_u ^Æ q_s a_r S , где символ S может принять одно из значений: -1 – сдвиг головки влево; +1 - сдвиг головки вправо; 0 – головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении

строки a u и столбца q_i будет стоять q_s a_r S ( см. таб.6.2.1)

Таб.6.2.1.

Если в программе машины для пары ( q _i ,a _u ) пятерка отсутствует, то в таблице на пересечении строки a _u , и столбца q _i ставится прочерк.

Итак, машина Тьюринга есть, по определению , набор М=(А,Q,П) , где А ― внешний алфавит, Q ― алфавит внутренних состояний, П ― программа.

Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову . Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.

Пример 6.2.1. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).

Решение. Рассмотрим алфавит А = {|, +, ⁄}.

Машина определяется следующей программой:

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+^||| , т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

Пример 6.2.2. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.

Решение. Искомую машину построим в алфавите A={|, α, ⁄}. Программа такой машины может выглядеть так:

Применим полученную машину к слову|| .

Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) | . Состояние q₁ обеспечивает замену | на α, состояние q₂ обеспечивает поиск α, предназначенных для замены на | , и останов машины в случае, когда α не обнаружено, q₃ обеспечивает дописывание | в случае, когда произошла замена α на |.

§6.3. Рекурсивные функции

Договоримся, что в этом параграфе

1. множество N натуральных чисел содержит 0 (нуль), т.е. N={0,1,2,3,...};

2. рассматриваемые функции f=f(x₁ ,x₂ ,…,x_n ) определены только тогда, когда переменные принимают значения из N, т.е. xiœN;

3. область значений функций DŒN;

4. рассматриваемые функции f=f(x₁ ,x₂ ,…,x_n ) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.

Введём в рассмотрениепростейшие функции

о(x)=0, s(x)=x+1, I^m _n (x₁ ,..., x_n ) ⁼ x_m

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

Оператор суперпозиции. Пусть даны функция f(x₁ ,x₂ ,…,x_k ) от k переменных и k функций f₁ (x₁ ,x₂ ,…,x_n ),…,f_k (x₁ ,x₂ ,…,x_n ) от n переменных. Суперпозицией функций f,f₁ ,…,f_k называется функция j(x₁ ,x₂ ,…,x_n )= f(f₁ (x₁ ,x₂ ,…,x_n ),…,f_k (x₁ ,x₂ ,…,x_n ))

Мы говорим, что функция j получается применением оператора суперпозиции S^к+1 к функциям f,f₁ ,…,f_k , и пишем j=S^к+1 (f,f₁ ,…,f_k ) Например, S² (s,o)=s(o(x)), т.е. функция, тождественно равная 1, а S² (s,s)=s(s(x)) - это функция у(x)=x+2.

Оператор примитивной рекурсии. Пусть даны функции g(x₁ ,x₂ ,…,x_n ) и h(x₁ ,x₂ ,…,x_n+2 ). Построим функцию f(x₁ ,x₂ ,…,x_n+1 ) Пусть зафиксированы значения x₁ ,x₂ ,…,x_n . Тогда полагаем: f(x₁ ,x₂ ,…,x_n ,0)= g(x₁ ,x₂ ,…,x_n )

f₁ (x₁ ,x₂ ,…,x_n ,y+1)= h(x₁ ,x₂ ,…,x_n ,y, f(x₁ ,x₂ ,…,x_n ,y))

Эти равенства определяют функцию f(x₁ ,x₂ ,…,x_n+1 ) однозначно. Функция f называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись f=R(g,h).

Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются 1) степень с натуральным показателем: a ⁰ =1, a ⁿ⁺¹ =aⁿ ÿa ;

2) факториал: 0!=1, (n+1)!= n!ÿ(n+1) и т.д.

Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, I ^m _n ( x ₁ ,..., x _n ) = x _m применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.

Проверим, что функция u(x,y)=x+y является примитивно рекурсивной. Действительно, мы имеем: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Это есть схема примитивной рекурсии, так как x= I¹ ₁ (x), а u(x,y)+1=s(u(x,y))=S² (s,u). Здесь g(x)= I¹ ₁ (x), а h(x,y,u)=s(u)=S² (s, I³ ₃ ).

Аналогично доказывается, что функции m(x,y)=xÿy, d(x,y)=x^y (считаем по определению 0⁰ =1), fact(x)=x! и многие другие являются примитивно рекурсивными.

Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, I^m _n являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как

⁼ ^ x − y, если x ≥ y < y

^f(x,y) не существует, если x

примитивно рекурсивной быть не может. Рассматривать функцию f(x,y)=x-y здесь мы не имеем права, так как значения функций должны быть натуральными числами (поэтому не отрицательными). Однако, можно рассмотреть функцию

x

÷ y = 0x − y еслиесли x x<≥y.y

Проверим, что она примитивно рекурсивна. Докажем вначале, что функция j(x)=xπ1 примитивно рекурсивна. Действительно, j(0)=0. j(y+1)=(y+1)π1=y, что служит схемой примитивной рекурсии для функции xπ1. Наконец, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) - схема примитивной рекурсии для xπy.

Существенно более широким классом функций, чем примитивно рекурсивные функции, является классрекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.

Оператор минимизации. Пусть дана функция f(x₁ ,x₂ ,… ,x_n ,x_n+1 ). Зафиксируем какие-либо значения x₁ ,x₂ ,… ,x_n первых n переменных и будем вычислять f(x₁ ,x₂ ,… ,x_n ,0), f(x₁ ,x₂ ,… ,x_n ,1), f(x₁ ,x₂ ,… ,x_n ,2) и т.д. Если y- наименьшее натуральное число, для которого f(x₁ ,x₂ ,…

,x_n ,y)=x_n+1 (т.е. значения f(x₁ ,x₂ ,… ,x_n ,0), f(x₁ ,x₂ ,… ,x_n ,1),…,f(x₁ ,x₂ ,…

,x_n ,y-1) все существуют и не равны xn₊₁ ), то полагаем g(x₁ ,x₂ ,…

,x_n ,x_n+1 )=y. Таким образом, g(x₁ ,x₂ ,… ,x_n ,x_n+1 )=min(y|f(x₁ ,x₂ ,…,x_n ,y)=x_n+1 ).

Если такого y нет, то считаем, что f(x₁ ,x₂ ,… ,x_n ,x_n+1 ) не определено. Итак, возможны три случая:

1. f(x₁ ,x₂ ,… ,x_n ,0), f(x₁ ,x₂ ,… ,x_n ,1),…,f(x₁ ,x₂ ,… ,x_n ,y-1) существуют и не равны xn₊₁ , а f(x₁ ,x₂ ,…,x_n ,y)=x_n+1 ;

2. f(x₁ ,x₂ ,… ,x_n ,0), f(x₁ ,x₂ ,… ,x_n ,1),…,f(x₁ ,x₂ ,… ,x_n ,y-1) существуют и не равны xn₊₁ , а f(x₁ ,x₂ ,…,x_n ,y) не существует;

3. f(x₁ ,x₂ ,… ,x_n ,i) существуют при всех iœN и отличны от xn₊₁ .

Если имеет место 1-й случай, то g(x₁ ,x₂ ,… ,x_n ,x_n+1 )=y, а если 2й или 3-й, то g(x₁ ,x₂ ,… ,x_n ,x_n+1 ) не определено. Про функцию g полученную таким образом, говорят, что она получена из f применением оператора минимизации М . Мы пишем g= Мf.

Оператор минимизации - это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной x_n+1 )

Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, I^m _n (x₁ ,..., x_n ) = x_m применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.

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

⁼ ^ x − y, если x ≥ y < y

^f(x,y) не существует, если x

является рекурсивной. Действительно, f(x,y)=min(z| y+z=x), а ранее было установлено, что функция u(x,y)=x+y примитивно рекурсивна.

Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга (см. предыдущий параграф). Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места. Полное доказательство можно найти, например, в книге А.И.Мальцева "Алгоритмы и рекурсивные функции".

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

§6.4. Алгоритмически неразрешимые задачи.

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

Сформулируем одну из этих задач

Проблема остановки машины Тьюринга. Машина Тьюринга - это объект, определяемый конечным числом параметров. Все частичные отображения одного конечного множества в другое могут быть эффективным образом перенумерованы. Поэтому каждой машине Тьюринга можно присвоить номер (натуральное число). Пусть T(n) машина Тьюринга с номером n. Некоторые машины, начинающие работать на пустой ленте, в конце концов останавливаются, а некоторые работают бесконечно долго. Возникает задача: по натуральному числу n определить, остановится или нет машина Тьюринга T(n) запущенная на пустой ленте. Эта задача

алгоритмически неразрешима. То есть не существует автоматической процедуры, для каждого n решающей, останавливается или нет машина T(n). Это не исключает того, что для какой-либо конкретной машины мы установим, останавливается она или нет. Не существует метода, решающего это сразу для всех машин.

§6.5. Алгоритмы и их сложности.

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

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

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

Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время cÿn² , где c — некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n² ) (читается "порядка эн квадрат").

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

Допустим, у нас есть пять алгоритмов A1,A2,…,A5 со следующими временными сложностями:

Здесь временная сложность — это число единиц времени, требуемого для обработки входа размера n. Пусть единицей времени будет одна миллисекунда (1сек=1000 милисекунд). Тогда алгоритм A1 может обработать за одну секунду вход размера 1000, в то время как A5 — вход размера не более 9. В таб. 6.5.1. приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.

Таблица 6.5.3.

Предположим, что следующее поколение вычислительных машин будет в 10 раз быстрее нынешнего. В таб.6.5.2. показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма A5 десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три единицы (см. последнюю строку в таб.6.5.2.), тогда как для алгоритма A3 размер задачи более чем утраивается.

Таблица 6.5.4.

Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Вернемся к таб.6.5.1. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм A4 алгоритмом A3, можно решить задачу, в 6 раз большую, а заменяя A4 на A2, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.

Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную (постоянная c в определении О(f(x)) ), чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют. Например, предположим, что временные сложности алгоритмов A1, A2, A3, A4, A5 в действительности равны соответственно 1000n, 100nÿlog(n), 10n² , n³ и 2 . ⁿ Тогда A5 будет наилучшим для задач размера 2§n§9, A2 —для задач размера

10§n§58, A1 — при 59§n§1024, а A1— при n>1024.-

ЛИТЕРАТУРА.

1. Ф.А.Новиков. Дискретная математика для программистов./ Санкт-Петербург: Питер, 2001г., 304С.

2. С.В.Судоплатов, Е.В.Овчинникова. Элементы Дискретной математики./ М., ИНФРА-М, Новосибирск, Изд-во НГТУ,

2002г., 208С.

3. Я.М.Ерусалимский. Дискретная математика/ М., «Вузовская книга», 2001г.,279С.

4. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. / М., Мир, 1979г., 536С.

5. В.Н.Нефедов, В.А.Осипова Курс дискретной математики./ М., Изд-во МАИ, 1992г., 264С.