МИНИСТЕРСТВО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

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

учреждение Московской области «Ногинский колледж»

подразделение «Балашиха»

И.А. Каверина

Курс лекций по

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

Балашиха

2016

Введение

Зададимся вопросом: «для чего инженеру–программисту нужен данный курс?». Краткий ответ: Изучение его преследует две цели – изучить логические основы процесса написания программ и приобрести навыки строгого, формализованного мышления. А теперь более подробно.

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

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

Рассмотрим вкратце этапы развития логики.

1-й этап. Как самостоятельная наука логика оформилась в трудах Аристотеля (IVв. до н.э.). Он пытался найти ответ на вопрос ”как мы рассуждаем”, изучал ”правила мышления”. Аристотель впервые дал систематическое изложение логики. В результате возникла формальная теория, связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком, которая впоследствии стала называться формальной или Аристотелевой логикой. Правила вывода, описанные Аристотелем (силлогизмы), были основным инструментом логики вплоть до 17в. Силлогизм - это рассуждение, в котором из заданных двух суждений выводится третье.

Например:

1) Все млекопитающие имеют скелет.

Все киты – млекопитающие.

Следовательно, все киты имеют скелет.

2) Все квадраты ромбы,

все ромбы – параллелограммы.

Следовательно, все квадраты – параллелограммы.

В общем виде этот силлогизм имеет форму:

”Все A суть B, все B суть C. Следовательно, все A суть C.”

А вот пример силлогизма неправильной формы:

Все квадраты – ромбы.

Некоторые ромбы имеют острый угол.

Следовательно, некоторые квадраты имеют острый угол.

Значит, силлогизм, имеющий форму ”Все A суть B, некоторые B суть C. Значит, некоторые A суть C ” может привести и к ложным выводам.

Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: "Все A суть B"; "Некоторые A суть B"; "Все A не суть B"; "Некоторые A не суть B".

2-й этап. Однако, развитие математики выявило недостаточность формальной логики, поэтому в конце 17в. Г.Лейбниц предложил понятия логики обозначить символами, которые соединялись бы по особым правилам. Это позволяло всякое рассуждение заменить вычислением.

Первая реализация идей Г.Лейбница принадлежит английскому математику Дж.Булю (1815-1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний (или булевой алгебре). Именно благодаря введению символов в логику была получена основа для создания новой науки – математической логики.

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

3-й этап связан с XX веком и попытками обосновать справедливость математических доказательств, с исследованиями теории чисел, а также с попыткой разрешить известные логические парадоксы.

Самым знаменитым следует считать парадокс лжеца, известный еще со времен глубокой древности:

Некто говорит: ’’я лгу’’. Если он при этом лжет, то сказанное им есть ложь, и, следовательно, он не лжет. Если же он не лжет, то сказанное им есть истина, и следовательно, он лжет. В любом случае оказывается, что он лжет и не лжет одновременно.

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

В учебном пособии излагается материал по математической логике и основам теории алгоритмов, изучаемый в курсе «Математическая логика и теория алгоритмов» и предназначенный для специалистов инженерного профиля.

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

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

Булевой функцией y=f(x1,x2,…,xn) от п переменных x1,x2,...,xn называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц (x1,x2,...,xn) ставится в соответствие значение 0 или 1. Значение 0 часто называют Ложью (False), а значение 1 – Истинной (True).

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

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

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

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(x1,x2,…,xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

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

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

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

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

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

f(x)

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

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

f(x, y)

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

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

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

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

f(x, y)

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

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

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

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

f(x, y)

Другое название: логическое следование.

Обозначения: xy, x y, x y.

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

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

f(x, y)

Обозначения: xy, xy,.xy.

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

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

f(x, y)

Другое название: антиэквивалентность.

Обозначения: xy, x+y.

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

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

f(x, y)

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

Обозначение: xy.

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

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

f(x, y)

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

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

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

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

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

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

Пример 1.3.1. Пусть задана элементарная булева функция xy. Подставим вместо x функцию x1x2. Получаем функцию трех переменных (x1x2)y. Если вместо переменной y подставить, например, x3x4, то получаем новую функцию от четырех переменных: (x1x2)(x3x4). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.

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

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

Примеры 1.3.2.

1. В формуле xyz скобки расставляются следующим образом: ((xy)z), т.к. операция сильнее операции согласно нашему соглашению.

2. В формуле xyzx скобки расставляются следующим образом: ((xy)(zx))

3. В формуле (xy)zxyz скобки расставляются следующим образом: ((xy)(z((xy)(z)))).

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

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

Булева функция y=f(x1,x2,…,xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2,…,ak-1, ak+1,ak+2,…,an, что

f(a1,a2,…,ak-1,0,ak+1,ak+2,…,an) f(a1,a2,…,ak-1,1,ak+1,ak+2,…,an).

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

Пример 1.4.1. Пусть булевы функции f1(x1,x2) и f2(x1,x2) заданы следующей таблицей истинности:

f1(x1,x2)

f2(x1,x2)

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

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

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

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

Пример 1.5.1. F1=x1x2(x1x2x1x2)

x1x2

(x1x2)(x1x2)

x1x2

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

Пример 1.5.2. F2=x1x2x1

x1x2

F2=(x1x2)x

Таким образом, формула F2 реализует константу 1.

Пример 1.5.3. F3=((x1x2)x1)x2.

x1x2

(x1x2)x1

((x1x2)x1)x2

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

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

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

x1x2(x1x2x1x2)=x1x2;
x1x2x1=1;
((x1x2)x1)x2=x1x2.

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

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

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

Закон двойного отрицания: .
Идемпотентность:

H&H=H, HH=H.

Коммутативность: H1H2=H2H1,

где символ означает одну из связок &, , , , , .

Ассоциативность: H1(H2H3)=(H1H2)H3,

где символ означает одну из связок &, , , .

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

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

H1(H2&H3)=(H1H2)&(H1H3);

H1&(H2H3)=(H1&H2)(H1&H3).

Законы де Моргана: при справедливы формулы

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

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

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

, .

Законы инверсий:
Правила операций с константами 0 и 1:

H1=1, H&1=H, H0=H, H&0=0.

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

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

Докажем 1-й закон де Моргана [pic] методом математической индукции.

Справедливость формулы при [pic] проверим непосредственно при помощи таблицы истинности:

[pic]

Пусть формула верна при [pic] . Тогда при имеем:

применяем

формулу при , получаем применяем

формулу при , получаем =

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

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

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

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

Класс функций, сохраняющих константу 0, т.е. таких функций y=f(x1,x2,…,xn),что f(0,0,…,0)=0. Например, xy(x).
Класс функций, сохраняющих константу 1, т.е. таких функций y=f(x1,x2,…,xn),что f(1,1,…,1)=1. Например, x(yx).
Класс самодвойственных функций, т.е. таких функций y=f(x1,x2,…,xn), что [pic] .
Класс линейных функций, т.е. таких функций y=f(x1,x2,…,xn), которые могут быть представлены в виде f(x1,x2,…,xn)=c0c1x1c2x2…cnxn, где с0, c1, c2…коэффициенты, которые могут принимать значение 0 или 1.
Класс монотонных функций. На множестве наборов из нулей и единиц Вⁿ={(x1,x2,…,xn) | xi{0,1}, i=1,2,…,n} введем частичный порядок следующим образом:

(a1,,a2,...,an) (b1,b2,...,bn) тогда и только тогда когда a1b1, a2b2,…,anbn. Функция f(x1, х2,...,хn) называется монотонной, если для любых двух элементов из Вⁿ таких, что (a1,,a2,...,an)(b1,b2,...,bn) следует, что f(a1,,a2,...,an)f(b1,b2,...,bn).

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

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

Доказательство теоремы Поста приведено в приложении 1, однако для понимания ее доказательства необходимо ознакомится с главами II и III.

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

Таблица 1.7

Обозн.

Не сохрани-мость константы 0

Не сохрани-мость константы 1

Не Самодвойственность

Не Линей-ность

Не Монотон-ность

Конст.0

Конст.1

Отриц.

Конъюн.

Дизъюн.

Имплик.

Эквивал.

Сумма по модулю 2

Штрих Шеффера

Стрелка Пирса

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

Система функций S1={,,} образует базис. Для приведения булевой функции к виду, содержащему лишь связки из базиса S1, могут быть полезны следующие эквивалентности:

, , ,

, .

Система S2={,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношение .
Система S3={,} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношение .
Система S4={1,&,} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения .
Система S5={} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения , .
Система S6={} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать соотношения , .
Система S7={,0} образует базис.

Пример 1.7.1. Записать функцию x(yz) в базисе S1={,,}.

Пример 1.7.2. Используя теорему Поста проверить, является ли полной система функций S={f1,f2}, где

Решение: Проверим какими свойствами обладают данные функции.

1. Сохранимость константы 0.

f1(0,0)=01=0 – сохраняет константу 0.

f2(0,0)= – не сохраняет константу 0.

2. Сохранимость константы 1.

f1(1,1)=10=0 – не сохраняет константу 1.

f2(1,1)=00=1 – сохраняет константу 1.

3. Самодвойственность.

– не самодвойственная.

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

X Y

0 0

0 1

1 0

1 1

Из таблицы истинности видно, что , т.е. f2 - не самодвойственна.

4. Линейность.

Построим полином Жегалкина для функции f2 методом неопределенных коэффициентов. P(x,y) имеет вид:

Используя таблицу истинности для f2, полученную в п.3, имеем

P(0,0)=C0=1 C0=1

P(0,1)=C0C2=0 1C2=0 C2=1

P(1,0)=C0C1=1 1C1=1 C1=0

P(1,1)=C0C1C2C3=1 101C3=1 C3=1.

Итак, f2=1yxy – не линейна.

5. Монотонность.

Очевидно, что наборы упорядочены следующим образом:

(0,0)(0,1); (0,0)(1,0); (0,0)(1,1); (0,1)(1,1); (1,0)(1,1).

Проверим на монотонность функцию f1:

f1(0,0)=01=0 f1(0,1)=00=0;

f1(0,0)=0 f1(1,0)=11=1;

f1(0,0)=0 f1(1,1)=10=0;

f1(0,1)=00=0 f1(1,1)=10=0;

f(1,0)=11=1 f1(1,1)=10=0.

Итак, мы получили, что для (1,0)(1,1), не выполняется f1(1,0)f1(1,1), следовательно функция f1–не монотонна.

Проверим на монотонность функцию f2(0,0)=1; f2(0,1)=0. Итак, для (0,0)(0,1) мы не получили что f2(0,0)f2(0,1). Следовательно, функция f2–не монотонна.

Сведем наши вычисления в таблицу.

Не

сохр.0

Не

Сохр.1

Не

Самодв.

Не

Линейность

Не

Монотонность

Из теоремы Поста, заключаем, что система – полная.

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

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

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

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

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

или ,

называется литерой. Литеры x и x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы являются конъюнктами, формулы - дизъюнктами, а формула является одновременно и конъюнктом и дизъюнктом.

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

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

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

Примеры.

xyyzx ― это ДНФ (сумма произведений).
―это КНФ (произведение сумм).
― это ДНФ и КНФ (одновременно).
― это ДНФ и КНФ (одновременно).
(xxy)·(yzx)·z ― это КНФ.
― это ДНФ.
― это не нормальная форма (не ДНФ и не КНФ).

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

используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;
применяем правило снятия двойного отрицания: x=x;
далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ

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

и второй закон дистрибутивности для приведения к КНФ.

H1(H2&H3)=(H1H2)&(H1H3).

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

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

-это КНФ

-это другая КНФ

-это ДНФ

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

это КНФ

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

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

Примеры: Пусть задана функция трех переменных f(x,y,z).

это совершенная ДНФ.
это совершенная КНФ.
это не совершенная КНФ, т.к. например, в первую сумму не входит переменная z.
xyz это совершенная ДНФ.

Теорема 2.2.1.

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

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

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

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

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

Решение.

Таблица 2.2

основные конъюнкции

f(x,y,z)

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

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

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

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

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

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

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

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

Строим СДНФ для отрицания.

Используем законы де Моргана

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

операция элементарного поглощения: .

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

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

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

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

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

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

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

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

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

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

Замечание. Для построения минимальной КНФ функции 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.

[pic]

таблица 2.4.2.

[pic]

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

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

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

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

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

Приведем шаблоны для n=3, которые помогают строить покрытия единицы (1).

[pic]

Приведем шаблоны для n=4, которые помогают строить покрытия единицы (1).

[pic]

Пример 2.4.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений.

1) f(x,y,z)=(1011 0101); 2) f(x1,x2,x3,x4)=(1011 1111 1011 1100).

Решение. 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимися двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с 0). Таким образом, f(0,0,1)=f(1,0,0)=f(1,1,0)=0.

[pic]

− min ДНФ.

Для построения МКНФ, построим МДНФ для функции :

[pic]

− min ДНФ . Переходя к функции f, получим:

– min КНФ.

2) Заносим данные в карту Карно. Получаем, что

f(0,0,0,1)=f(1,0,0,1)=f(1,1,1,0)=f(1,1,1,1)=0.

Далее, Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий четыре. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. Убрать некоторые покрытия нельзя. Производим считывание функции:

[pic]

– МДНФ.

Для построения МКНФ Функции f, построим сначала МДНФ, функции:

[pic]

– min ДНФ . Переходя к функции f, получим::

– min КНФ.

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

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

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

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

H1H2=H2H1, H1&H2=H2&H1;

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

H1(H2H3)=(H1H2)H3, H1&(H2&H3)=(H1&H2)&H3;

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

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

свойства констант

H&1=H, H&0=0, H0=H;

HH=0, H&H=H.

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

x=1x, xy=xyxy, xy=1xy,

xy=1xxy, xy=1xyxy, xy=1xy.

Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x1,x2,…,xn называется выражение вида

c0с1x1c2x2…cnxnc12x1x2…c12…nx1x2…xn,

где постоянные ск могут принимать значения 0 ли 1.

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

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

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

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

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

P= c0с1x1c2x2…cnxnc12x1x2…c12…nx1x2…xn.

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

2. Метод, основанный на преобразовании формул над множеством связок {, &}. Строят некоторую формулу Ф над множеством связок{,&}, реализующую данную функцию f(x1,x2,…,xn). Затем заменяют всюду подформулы вида на A1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

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

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

P= c0с1xc2yc12xy

Пользуясь таблицей истинности

получаем, что

f(0,0)=P(0,0)= c0=1, f(0,1)=P(0,1)= c0 c2=1,

f(1,0)=P(1,0)= c0 c1=0, f(1,1)=P(1,1)= c0с1c2c12=1

Откуда последовательно находим, c0=1, с1=1, c2=0, c12=1. Следовательно

xy=1xxy (сравните с утверждением 3.1).

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

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

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

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

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

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

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

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

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

Пропозициональные переменные являются формулами.
Если А, В формулы, то выражения А, АВ, АВ, АВ, АВ являются формулами.
Формулами являются только выражения, построенные в соответствии с пунктами 1 и 2.

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

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

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

а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский;

б) если поедут Арбузов и Вишневский, то поедет и Брюквин.

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

Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно.

Тогда условие а) можно записать в виде АБВ, а условие б) в виде А&В Б. Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связью «и» (конъюнкция равна 1 только в одном случае, когда все переменные равны 1). Поэтому принятое решение можно записать в виде формулы L=(АБВ)&(А&ВБ) эта формула должна быть истинной.

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

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

L=(БB)&(В)=(БB)&(Б).

Применяя к последнему выражению второй закон дистрибутивности, получим

L=[(БВ)&(Б)] = [Б(B&)] = Б=AБ.

Отсюда следует, что если поедет в экспедицию Арбузов, то с ним должен ехать и Брюквин.

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

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

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

Пример 4.2.1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двуместный предикат, определенный на множестве пар натуральных чисел M=NN. Очевидно, 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; х,у,zR.» — трехместный предикат, определенный на R³. Очевидно, что В(1,1,-2)=Л, В(1,1,2)=И.

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

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

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

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

§4.3. Кванторы. Логика предикатов

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

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

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

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

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

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

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

1) x1x2D(x1,x2)=0 2) x2x1D(x1,x2)=0 3) x1x2D(x1,x2)=1

4) x2x1D(x1,x2)=1 5) x1x2D(x1,x2)=1 6) x2x1D(x1,x2)=1

7) x1x2D(x1,x2)=0 8) x1x2D(x1,x2)=1.

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

Сравнение 7 и 8 в последнем примере доказывает это утверждение.

Алфавит логики предикатов содержит следующие символы:

1) символы предметных переменных – обычно строчные латинские буквы с индексами или без них;

2) символы предикатов – обычно прописные латинские буквы с индексами или без них;

3) логические символы: ;

4) символы кванторов – ;

5) скобки и запятую.

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

1) Если P – символ предиката, x1, x2,..., xn – символы предметных переменных, то P(x1,x2,...,xn) – формула. Такая формула называется атомарной. Все предметные переменные атомарных формул свободные, связанных переменных нет.

2) Пусть A – формула. Тогда тоже формула. Свободные и связанные переменные формулы – это соответственно свободные и связанные переменные формулы A.

3) Пусть A и B – формулы, причем нет таких предметных переменных, которые были бы связаны в одной формуле и свободны в другой. Тогда есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

4) Пусть A – формула, содержащая свободную переменную x. Тогда тоже формулы, Переменная x в них связана. Остальные переменные, которые в формуле A свободны, остаются свободными, а переменные, которые в формуле A связаны, остаются связанными. Говорят, что формула A есть область действия квантора.

5) Слово в алфавите логики предикатов 1–5 является формулой только в том случае, если это следует из правил 1–4.

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

Пример 4.3.2. Рассмотрим классический силлогизм Аристотеля «Все люди смертны. Сократ – человек. Следовательно, Сократ – смертен.». Пусть – означает быть человеком, – быть смертным, – Сократ. Тогда данный силлогизм может быть представлен в виде следующей формулы:

Пример 4.3.3. Рассмотрим афоризм Козьмы Пруткова «Нет столь великой вещи, которую не превзошла бы величиной большая». На множестве всех вещей введем предикат – вещь «больше» вещи . Тогда данный афоризм формально может быть записан так:

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

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

Имеют место следующие равносильности:

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

, .

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

, .

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

, .

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

, .

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

6. , .

Пример 4.3.4. Определить таблицу истинности предиката , где предикаты определены таблицами

[pic]

Решение. Очевидно, что = есть двуместный предикат. Построим таблицу истинности предиката :

==0, ==1,==0 т.е.

[pic]

Найдем значения

и т.д. для каждого значения из исходной таблицы истинности. Получим, таблицу истинности предиката:

[pic]

Формулы F и G равносильны (в логике предикатов), если они равносильны на всех множествах (обозначаетс: F=G).

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

Пример 4.3.5. С помощью законов равносильности логики предикатов, проверить будут ли равносильны следующие пары формул: и .

Решение. 1) Рассмотрим и предикаты F(x)={5 делится на x без остатка}, , G(x)={3 делится на x без остатка}, . Тогда =1, =0, следовательно, .

Так как,

то можно заключить, что формулы неравносильны.

Приведем к пренексной нормальной форме:

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

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

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

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

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

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

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

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

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

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

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

Множество правил вывода R, как правило, конечно.

Итак, исчисление есть четверка (A, F, B, R).

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

Формула G называется теоремой исчисления (выводимой в или доказуемой в ), если существует вывод F1,F2,…,Fn,G который называется выводом формулы G или доказательством теоремы G. Записывается это следующим образом:

F1,F2,…,Fn├ G.

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

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

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

Интерпретацией формальной теории в область интерпретации называется функция I, которая каждой формуле формальной теории однозначно сопоставляет некоторое содержательное высказывание относительно объектов множества. Это высказывание может быть истинным или ложным. Если высказывание является истинным, то говорят, что формула выполняется в данной интерпретации.

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

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

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

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

букв А, В, Q, R, Р и других, возможно с индексами (которые называются пропозициональными переменными},
логических символов (связок) , &, , ,
вспомогательных символов (,).

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

все пропозициональные переменные являются формулами ИВ;
если A, B —.формулы ИВ, то A, AB, AB, AB — формулы ИВ;
выражение является формулой ИВ тогда и только тогда, когда это может быть установлено с помощью пунктов "1" и "2".

Формулы, указанные в пункте 1, называются элементарными формулами, или атомами, а полученные по правилу пункта 2,-сложными формулами.

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

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

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

A(BA);
(AB)((A(BC))(AC));
(AB)A;
(AB)B;
(AB)((AC)(A(BC)));
A(AB);
A(BA);
(AC)((BC)((AB)C));
(AB)((AB)A);
AA.

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

Правилом вывода в ИВ является правило заключения {modus ponens):

если A и AB — выводимые формулы, то B — также выводимая формула. Символически это записывается так:.

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

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

Говорят, что формула G выводима из формул F1,F2,…,Fn (обозначается F1,F2,…,Fn├G), если существует последовательность формул F1,F2,…,Fk,G, в которой любая формула является либо аксиомой, либо принадлежит списку формул F1,F2,…,Fn (называемых гипотезами), либо получается из предыдущих формул по правилу вывода. Выводимость формулы G из (обозначается ├G) равносильно тому, что G — теорема ИВ.

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

в аксиоме 2 заменим B на AA, C — на A. Получаем аксиому

(A(AA))((A((AA)A))(AA));

в аксиоме 1 заменим B на A. Получаем

A(AA);

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

(A((AA)A))(AA);

в аксиоме 1 заменяем B на AA. Получаем

A((AA)A);

из пп. 3 и 4 по правилу вывода справедливо

├ AA.

Теорема 5.2.1.

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

2. Тогда и только тогда F1,F2,…,Fn├A, когда F1F2…Fn├A

(сведение множества гипотез к одной гипотезе).

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

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

Если Г,B├A, то Г├BA, где Г — набор некоторых формул Г={F1,F2,…,Fn}.

Докажем эту теорему конструктивно, т.е. предложим алгоритм построения вывода Г├BA из имеющегося вывода Г,B├A.

Пусть имеется последовательность формул [pic] , является выводом Г,B├A. Далее будем называть этот вывод вспомогательным. На первом шаге нахождения результирующего вывода припишем спереди к каждой из формул вспомогательного вывода символы , добавляя, если это необходимо, скобки. Получим последовательность с последней формулой , которая и должна быть последней в результирующем выводе. Очевидно, эта последовательность может не являться выводом из F1,F2,…,Fn.

Однако можно перед каждой формулой , вставить дополнительные формулы так, чтобы превратить ее в вывод из F1,F2,…,Fn. Выбор дополнительных формул при каждом i зависит от того, чем оправдывается наличие формулы во вспомогательном выводе. Возможны следующие случаи:

1) – аксиома или подстановка в аксиому;

2) [pic] – одна из посылок F1,F2,…,Fn;

3) ;

4) – modus ponens и где x<i, y<i, причем .

Рассмотрим для каждого из четырех случаев, на какую последовательность формул нужно заменить [pic] .

Случаи 1 и 2:

1) ,

2) в аксиоме 1 заменяем на ,

3) modus ponens 1 и 2.

Случай 3

1) [pic] в аксиоме 1 заменяем на ,

2) в аксиоме 2 заменяем на [pic] , [pic] на , C на B,

3) modus ponens 1 и 2,

4) в аксиоме 1 заменяем на , а на ,

5) modus ponens 4 и 3.

Случай 4

Пусть – modus ponens и где x<i, y<i, причем . Пусть также в результирующем выводе формула имеет номер p, а формула имеет номер q.

1) в аксиоме 2 заменяем на [pic] , [pic] на , C на ,

2) modus ponens, формула p и 1,

3) modus ponens, формула q и 2.

Теорема доказана.

Следствие 5.3.1. Тогда и только тогда F1,F2,…,Fn├A, когда

├F1(F2…(Fn-1(FnA))…)

Доказательство. Пусть F1,F2,…,Fn├A. Тогда, применяя теорему о дедукции, имеем F1,F2,…,Fn-1├FnA.

Аналогично F1,F2,…,Fn-2├Fn-1(FnA), и т. д. Продолжая этот процесс необходимое число раз, получаем

├F1(F2…(Fn-1(FnA))…)

Для доказательства достаточности предположим, что ├B, где В=F1(F2…(Fn-1(FnA))…). Воспользуемся теоремой 5.2.1., п.1: F1├В. По правилу заключения получаем F1├ (F2…(Fn-1(FnA))…), Далее через n шагов имеем F1,F2,…,Fn├A.

Таким образом, благодаря следствию 5.3.1., проверка выводимости формулы A из формул F1,F2,…,Fn, сводится к проверке доказуемости формулы

F1(F2…(Fn-1(FnA))…).

Проведем следующую классификацию формул:

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

Следующая теорема сводит проверку доказуемости формулы к проверке ее тождественной истинности.

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

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

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

Пример 5.3.2. Является ли формула ABAB общезначимой? Составляем таблицу истинности.

АВ

АВ АВ

Вывод: данная формула - общезначима.

Общезначимость формулы можно проверить методом от противного. Этот метод связан с решением логических уравнений. Под логическим уравнением будем понимать равенство вида , где и - формулы алгебры высказываний или одно из истинностных значений (И или Л ). Решить логическое уравнение означает найти все те наборы истинностных значений атомов, входящих хотя бы в одну из формул и , при которых имеет место равенство . Указанное же равенство выполняется, если формулы и имеют одинаковые истинностные значения.

Пример 5.3.3. Общезначима ли формула АВАВ?

Допустим, что данная формула не общезначима, тогда уравнение АВАВ=Л должно иметь решение. Следовательно, уравнения АВ=И, АВ=Л также должны иметь решения. Легко видеть, что А= И, В=Л является таким решением. Итак, имеется набор значений формул А, В, при котором формула АВАВ принимает значение Л. Значит эта формула не общезначима.

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

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

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

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

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

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

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

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

или ,

называется литерой. Литеры x и x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер.

Пусть — дизъюнкты. Дизъюнкт B1B2 называется резольвентой дизъюнктов D1 и D2 по литере А и обозначается через resA(D1,D2). Резольвентой дизъюнктов D1 и D2 называется резольвента по некоторой литере и обозначается через res(D1,D2). Очевидно, что res(A,A)=0. Действительно, т.к. A=A0 и A=A0, то res(A,A)=00=0. Если дизъюнкты D1 и D2 не содержат контрарных литер, то резольвент у них не существует.

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

D1=ABC, , то

resA(D1,D2)=BCQ, resB(D1,D2)=ACQ,

resC(D1,D2) не существует.

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

Пусть S=(D1,D2,…,Dn) множество дизъюнктов. Последовательность формул F1,F2,…,Fn называется резолютивным выводом из S, если для каждой формулы Fk выполняется одно из условий:

FkS;
существуют j, k <i такие, что Fi=res(Fj,Fk).

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

Отметим, что метод резолюций можно использовать для проверки выводимости формулы F из данного множества формул F1,F2,…,Fn. Действительно, условие F1,F2,…,Fn+F равносильно условию F1,F2,…,Fn,F├ (множество формул противоречиво), что в свою очередь равносильно условию Q├, где Q=F1F2…Fn(F). Приведем формулу Q к КНФ: Q=D1D2...Dm, тогда Q├ D1D2...Dm+ D1,D2,...,Dm├. Таким образом, задача проверки выводимости F1,F2,…,Fn├F сводится к проверке противоречивости множества дизъюнктов S={D1,D2,...,Dm}, что равносильно существованию резолютивного вывода 0 из S.

Пример 5.5.2. Проверить методом резолюций соотношение

А(ВС), CDЕ, FD&()E ├ А(ВF).

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

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

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

Таким образом, получаем множество дизъюнктов

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

;
;
;
;
;
.

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

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

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

§5.6. Исчисление предикатов

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

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

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

Исчисление предикатов – это аксиоматическая теория:

Алфавит – те же символы, что и в логике предикатов.

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

Аксиомы:

1) 1 – 10: – аксиомы Клини исчисления высказываний, где под обозначениями понимаются уже любые формулы исчисления предикатов:

2) ( – схема):

3) (– схема)

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

Система правил вывода:

1) modus ponens (m.p.);

2) правило обобщения ( – правило);

3) правило конкретизации (– правило);

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

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

Теорема 5.6.1. Аксиомы исчисления предикатов – общезначимые формулы.

Теорема 5.6.2. Формула, получающаяся из общезначимой по любому из правил вывода 1–4, является общезначимой.

Теорема 5.6.3. Любая выводимая в исчислении предикатов формула общезначима.

Теорема 5.6.4. Исчисление предикатов непротиворечиво.

Теорема Гёделя. Всякая общезначимая формула выводима в исчислении предикатов.

Теорема о дедукции. Если имеется вывод в исчислении предикатов формулы B из последовательности формул Γ, A, то можно построить вывод формулы из последовательности формул Γ (символически: Если Γ, A├B, то Γ├), где Γ – набор некоторых формул A1, A2,..., An.

Пример. Некоторые пациенты любят своих докторов. Ни один пациент не любит знахаря. Следовательно, никакой доктор не является знахарем.

Решение. Введем пропозициональные переменные для простейших предикатов.

Пусть, М - множество людей (пациентов, докторов, знахарей…),

P(x,y) = {x любит y}, ,

Q(x) = {x является знахарем}, ,

R(x) = { x является доктором}, .

Теперь директивные правила примут следующий вид:

, , .

Тогда теорему можно записать так:

├ .

Проверим является ли логичным утверждение задачи при помощи метода резолюций (заодно продемонстрируем этот метод).

Приводим формулы к виду , где - конъюнкция дизъюнктов.

Исследуем множество дизъюнктов:

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

1) .

2) .

Построен резолютивный вывод из , заканчивающийся 0. Следовательно, система - противоречива, а следовательно, рассматриваемое утверждение является логичным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) состоянием внутренней памяти qr;

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

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

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

Если машина, находясь во внутреннем состоянии qi , воспринимает ячейку с символом au , записывает к следующему моменту времени в эту ячейку символ ar , переходит во внутреннее состояние qs и сдвигается по ленте, то говорят, что машина выполняет команду qiauqsarS , где символ S может принять одно из значений: -1 – сдвиг головки влево; +1 - сдвиг головки вправо; 0 – головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении строки ai и столбца qi будет стоять qsarS ( см. таб.6.2.1)

Таблица 6.2.1.

…

qsarS

…

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

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

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

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

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

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

[pic]

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

[pic]

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

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

[pic]

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

[pic]

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

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

множество N натуральных чисел содержит 0 (нуль), т.е. N={0,1,2,3,...};
рассматриваемые функции f=f(x1,x2,…,xn) определены только тогда, когда переменные принимают значения из N, т.е. xiN;
область значений функций DN;
рассматриваемые функции f=f(x1,x2,…,xn) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.

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

о(x)=0, s(x)=x+1,

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

Оператор суперпозиции. Пусть даны функция f(x1,x2,…,xk) от k переменных и k функций f1(x1,x2,…,xn),…,fk(x1,x2,…,xn) от n переменных. Суперпозицией функций f,f1,…,fk называется функция

(x1,x2,…,xn)= f(f1(x1,x2,…,xn),…,fk(x1,x2,…,xn))

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

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

f(x1,x2,…,xn,0)= g(x1,x2,…,xn)

f1(x1,x2,…,xn,y+1)= h(x1,x2,…,xn,y, f(x1,x2,…,xn,y))

Эти равенства определяют функцию f(x1,x2,…,xn+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, применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.

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

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

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

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

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

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

Оператор минимизации. Пусть дана функция f(x1,x2,… ,xn,xn+1). Зафиксируем какие-либо значения x1,x2,… ,xn первых n переменных и будем вычислять f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1), f(x1,x2,… ,xn,2) и т.д. Если y наименьшее натуральное число, для которого f(x1,x2,… ,xn,y)=xn+1 (т.е. значения f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,… ,xn,y-1) все существуют и не равны xn+1), то полагаем g(x1,x2,… ,xn,xn+1)=y. Таким образом,

g(x1,x2,… ,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=xn+1).

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

1. f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,… ,xn,y-1) существуют и не равны xn+1 , а f(x1,x2,…,xn,y)=xn+1;

2. f(x1,x2,… ,xn,0), f(x1,x2,… ,xn,1),…,f(x1,x2,… ,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y) не существует;

3. f(x1,x2,… ,xn,i) существуют при всех iN и отличны от xn+1.

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

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

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

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

является рекурсивной. Действительно, 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 за время cn², где c — некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n²) (читается "порядка эн квадрат").

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

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

Временная сложность

nlog(n)

n²

n³

2ⁿ

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

Таблица 6.5.1.

Временная сложность

Максимальный размер задачи

1 сек

1 мин

1 час

1000

6?10⁴

3,610⁶

nlog(n)

140

4893

2,010⁴

n²

244

1897

n³

153

2ⁿ

Таблица 6.5.2.

Временная сложность

Максимальный размер задачи

до ускорения

после ускорения

10 S1.

nlog(n)

Примерно 10 S2 для больших S2.

n²

3,1б5 S3

n³

2,155 S4.

2ⁿ

S5+3,3

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

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

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

Глава VII. Нечеткая логика

Нечеткая логика (fuzzy logic) является обобщением Булевой логики, которое получается при расширении семантической области от 0, 1 до [0,1] и арифметизации логических операций. Расширение семантической области происходит за счет того, что каждому высказыванию сопоставляется некоторая степень истинности, значение которой может принимать любое числовое значение из интервала [0,1].

Каждое высказывание А в нечеткой логике имеет степень истинности, задаваемую функцией , т.е. : {высказывания} 0,1. Функцию также называют функцией принадлежности.

Для всех логических связок задаются арифметические правила вычисления степени истинности:

или, (1)

[pic] и, (2)

не . (3)

Если в исчислении высказываний булевой логики интерпретация логических связок определялась посредством таблиц истинности, то формулы (1), (2) задают непрерывные функции от двух переменных, определенные на множестве [0,1]×[0,1], а формула (3) – функцию одной переменной, определенную на [0,1].

Нечеткая переменная описывается набором (N,X,A), где N – это название переменной, X – универсальное множество (область рассуждений), A – нечеткое высказывание на X.

Лингвистической переменной (ЛП) называется набор , где

[pic] – название ЛП;
– множество значений, которое также называется базовым терм-множеством. Элементы базового терм-множества представляют собой названия нечетких переменных;
X – универсальное множество;
– синтаксическая процедура, по которой генерируются новые термы с применением слов естественного или формального языка;
– семантическая процедура, которая каждому значению лингвистической переменной ставит в соответствие нечеткое подмножество множества X.

Основой для проведения операции нечеткого логического вывода является база правил, содержащая нечеткие высказывания в форме «Если-то» и функции принадлежности для соответствующих лингвистических термов.

Пример 1. Формализуем неточное определение «горячий чай». В качестве названия лингвистической переменной будет выступать температура в градусах по Цельсию. Будем считать, что она изменяется от 0 до 100 градусов (универсальное множество X). Нечеткое высказывание (нечеткая переменная) для понятия «горячий чай» может выглядеть следующим образом:

100

(A)

0,1

0,3

0,6

0,8

0,9

Так, чай с температурой 60С принадлежит к множеству «Горячий» со степенью принадлежности 0,80. Для одного человека чай при температуре 60С может оказаться горячим, для другого – не слишком горячим. Именно в этом и проявляется нечеткость задания соответствующего высказывания.

Пример 2. Опишем нечеткое высказывание B = {множество молодых людей}. Естественный путь описания множества B состоит в ослаблении строгого разделения на молодых и не молодых. Сделаем это, вынося не только (четкие) суждения типа «Да, он принадлежит множеству молодых людей» или «Нет, он не принадлежит множеству молодых людей», но и более гибкие формулировки типа: «ДА, он принадлежит к достаточно молодым людям» или «Нет, он не очень молод».

Возраст – название лингвистической переменной, – универсальное множество, которое мы ограничили значением 100 (лет). Терм-множество T состоит из одной нечеткой переменной «молодой человек».

Приведем функцию степени истинности [pic] множества молодых людей.

[pic]

То есть 25-летние все еще молоды со степенью уверенности 50 процентов. Значения функции [pic] , измеренные в процентах, можно определить используются субъективные (нечеткие) знания экспертов. Например, в нашем примере, 50% респондентов ответили, что 25-летние все еще молоды, а 50% респондентов ответили противоположное. Аналогично, эксперты дали заключения по остальным возрастам. Так получается функция .

Пример 3. «Синий шар». Пусть заданы степени истинности высказываний «Объект является синим» и «Объект является шаром»:

(«Объект является синим») = 0,85;

(«Объект является шаром») = 0,6 .

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

(«Объект является синим шаром») = min (0,85; 0,6) = 0,6 ,

(«Объект является либо синим, либо шаром») = max (0,85; 0,6) = 0,85.

Треугольная функция принадлежности определяется неубывающей тройкой чисел (a,b,c), и ее значение в точке x вычисляется согласно выражению (выше мы опускали переменную x):

Для задания трапецеидальной функции принадлежности необходима неубывающая четверка чисел (a,b,c,d):

[pic]

Рисунок 1 – Треугольная и трапецеидальная функция принадлежности

Пример 4. Описание лингвистической переменной «возраст» дано на рисунке 2. Базовое терм-множество T для лингвистической переменной «возраст» состоит из трех термов (нечетких переменных), а именно, M=«молодой», C=«средний», P=«пожилой». Область рассуждений ограничим отрезком . Совокупность функций принадлежности для каждого терма из базового терм-множества T обычно изображаются вместе на одном графике.

Функции принадлежности для каждого лингвистического терма из T:

для терма «молодой» – трапецеидальная (0;0;20;30);
для терма «средний» – треугольная (25;40;55);
для терма «пожилой» – трапецеидальная (45;60;90;90).

[pic]

Рисунок 2 – Описание лингвистической переменной «возраст»

Исходя из правил (1)-(3), образуем новые термы.

Терм «не молодой». Функция принадлежности этого терма находится из равенства [pic] (не молодой) = (молодой), что приводит к трапецеидальной (20;30;90;90) (см. рисунок 3). Отметим, что данную функцию легче искать из графика.

[pic]

Рисунок 3 – Описание терма «не молодой»

Терм «молодой, но не очень», является граничным между «молодой» и «средний». Поэтому функция принадлежности этого терма вычислим по формуле (молодой, но не очень) и. График этой функции приведен на рисунке 4 в виде «жирной» линии. Так для человека 22 лет степень истинности высказывания «молодой, но не очень» равна 0; для человека 29 лет:

[pic] .

[pic]

Рисунок 4 – Описание терма «молодой, но не очень»

Степенью неопределенности нечеткого высказывания является мера отличия его степени истинности от 0 и от 1, то есть от возможных «четких» значений истинности. Такая мера может вводиться различными способами, для которых общими должны быть следующие свойства:

1) равенство 0 этой меры, для высказываний, имеющих степень истинности равную (A)=1 (A – истинное) или (A)=0 (A – ложное);

2) равенство 1 в случае наибольшего удаления степени истинности от значений 1 и 0, то есть при (A)=0.5 (A – полностью неопределенное высказывание).

Такой мерой может служить – мера построенная на основе индекса нечеткости нечетких множеств: (A) = | 1 – 2(A) |

Пример 5. Продолжим рассмотрение «синего шара». Тогда

(«Объект является синим») = ;

(«Объект является шаром») = ;

(«Объект является синим шаром») = 0,2;

(«Объект является либо синим, либо шаром») = 0.7.

Пример 6. Определим = (( A B ) ( B A ) ) =

=| 1 – 2 min ( max( 1 – (A), (B)), max (1 – (B), (A) ) ) | .

Уточним это определение.

При 1 – (A) (B) => 1 – ( B) ( A) =>

= | 1 – 2min(1 – (A), 1 – (B)).

При 1 – (A) 1 – (B) => ( B) ( A) =>

= | 1 – 2(1 – (A)) | = | 1 – 2(A)| = A .

При 1 – (A) < 1 – (B) => ( B) < ( A) =>

= | 1 – 2(1 – (B)) | = | 1 – 2(B)| = B .

При 1 – (A) < (B) => 1 – ( B) < ( A) =>

= | 1 – 2min( (A), (B) ) | .

При (A) (B) => = | 1 – 2(B) | = B .

При (A) < (B) => = | 1 – 2 (A) | = A .

Таким образом, при (1 – (A) (B) и ( B) ( A)) или(1 – (A) < (B) и (A) < (B)), = A, иначе = B.

Пример 7. Определим

| = ( (A B) ) = ( A B) ) = | 1 – 2 max(1 – (A), 1 – (B) )) | .

Уточним это определение.

При 1 – (A) > 1 – (B), то есть (B) > (A) ) =>

| = | 1 – 2 + 2(A) | = | 1 – 2(A)| = .

При 1 – (A) < 1 – (B) , то есть (A) > (B) ) =>

| = | 1 – 2 + 2 (B)) | = | 1 – 2(B)| = B .

При 1 – (A) = 1 – (B) , то есть (A) = (B) ) =>

| = | 1 – 2(B)| = | 1 – 2(A)| = = B .

Приложение 1. Доказательство теоремы Поста

Обозначим - множество всех булевых функций. Пусть задана система функций . Замыканием [pic] множества [pic] называется совокупность всех функций из , являющихся суперпозициями функций из множества . Система называется замкнутой, если .

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

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

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

Дизьюнкцию можно выразить через конъюнкцию и отрицание, а конъюнкцию через отрицание и дизъюнкцию (по законам де Моргана), следовательно, системы и будут полными.

Лемма 1. (о нелинейной функции). Если функция [pic] нелинейная, то из нее с помощью подстановки констант: 0, 1, а также переменных и, быть может, отрицания над всей функцией можно получить конъюнкцию [pic] .

Доказательство. Пусть функция [pic] не линейна относительно переменных , тогда ее можно представить в виде:

[pic] ,

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

[pic]

Таким образом, Лемма доказана.

Проиллюстрируем лемму о нелинейной функции на примере.

Пример. Определить, можно ли получить функцию [pic] из функции [pic] .

Решение. Строим полином Жегалкина для функции :

[pic] .

Получили, что функция не линейна относительно переменных [pic] и , и по лемме о нелинейной функции из нее можно получить конъюнкцию [pic] . Представим ее в виде , следовательно, , , . Тогда [pic] .

Заключаем, что конъюнкцию можно получить из функции заменой [pic] на , и на 0.

Лемма 2 (о немонотонной функции). Если функция [pic] не является монотонной, то из нее с помощью подстановки констант 0 , 1 и переменной можно получить .

Доказательство. Пусть функция немонотонна, тогда найдется такая пара сравнимых наборов (a1,,a2,...,an)(b1,b2,...,bn), что , а . Для каждого выполнено либо , либо . В первом случае делаем замену вместо переменной , во втором – подставляем вместо переменной . Вновь полученная функция удовлетворяет условию леммы. Лемма доказана.

Замечание. Если функция не является монотонной, то найдется пара соседних наборов, на которых нарушается условие монотонности.

Следствие. Если функция [pic] немонотонна, то из нее с помощью подстановки констант: вместо переменной и переменной можно получить .

Доказательство. В силу замечания, найдется пара наборов , соседних по компоненте, таких что , на которых условие монотонности нарушается, т. е. . Очевидно, , . Сделаем следующую подстановку

Вновь полученная функция будет зависеть от одной переменной и удовлетворяет условию следствия. Утверждение доказано.

Пример. Определить, можно ли получить функцию из функции .

Решение. Функция f немонотонна, т. к. , значит по лемме о немонотонной функции из этой функции можно получить функцию . Сделаем следующую замену переменных: на 1, и на , тогда получаем, что .

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

Лемма 3 (о несамодвойственной функции). Если функция [pic] не является самодвойственной, то из нее с помощью подстановки и вместо переменных можно получить константу.

Доказательство: Пусть функция [pic] не самодвойственна, тогда найдется пара противоположных наборов и таких, что значения функции на них совпадают, т.е. , где - некоторая константа. Сделаем замену

заменяем на

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

Пример. Определить, можно ли получить константу из функции .

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

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

Теорема Поста о полноте. Система функций [pic] полна тогда и только тогда, когда она не содержится ни в одном из пяти замкнутых классов: [pic] .

Доказательство.

Необходимость докажем от противного. Пусть система [pic] полна и включена в один из пяти классов [pic] т. е. , где [pic] один из пяти замкнутых классов. Тогда , т.е. , а так как класс [pic] замкнут, то один из пяти классов совпадает с множеством всех булевых функций, что ведет к противоречию.

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

1 этап. Получение констант: 0, 1.

a) Пусть , тогда . Вторую константу получаем из :

b) Если , тогда . По лемме о несамодвойственной функции из функции и отрицания можно получить константу, обозначим ее через c. Вторую константу получаем из , .

2 этап. Получение отрицания.

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

3 этап. Получение конъюнкции.

По лемме о нелинейной функции из с помощью подстановки констант и отрицания можно получить конъюнкцию. Константы и отрицание были получены через суперпозицию на первом и втором этапах. Теорема доказана.

Приложение 2. Варианты логики и логическое программирование

Модальная логика – логика в которой кроме стандартных логических связок, переменных и/или предикатов есть модальности (модальные операторы). Модальности бывают разные; наиболее распространены временны́е («когда-то в будущем», «всегда в прошлом», «всегда» и т. д.) и пространственные («здесь», «где-то», «близко» и т. д.). Например, модальная логика способна оперировать утверждениями типа «Москва всегда была столицей России» или «Санкт-Петербург, когда-то в прошлом, был столицей России», которые невозможно или крайне сложно выразить в не модальном языке. Кроме временных и пространственных модальностей есть и другие, например «известно, что» (логика знания) или «можно доказать, что» (логика доказуемости).

Обычно для обозначения модального оператора используется [pic] и двойственный к нему [pic] : например, [pic] . Это отражает то, что сказать «Москва когда-то была столицей России» то же самое, что сказать «не верно, что Москва никогда не была столицей России».

Приведем ряд модальностей:

Алетические модальные понятия:

Логические
- L — необходимо
- M — возможно
- С — случайно
Фактические
- [pic] — необходимо
- [pic] — возможно
- [pic] — случайно

При описании сложных систем часто приходится использовать нечеткие понятия и рассуждения, и классическая логика оказывается в таких случаях неадекватной. Для формализации таких задач Заде разработал основы математического аппарата, опирающегося на понятия нечетких множеств и нечеткой логики. Для нечетких множеств вводится характеристическая функция , которая характеризует "степень истинности" утверждений типа для . Характеристическая функция может принимать любые значения из интервала [0,1]. Пусть А и В - нечеткие множества, тогда для истинности нечеткого высказывания вводится нечеткая конъюнкция: где , . Нечеткая дизъюнкция вводится соотношением: . Нечеткое отрицание определяется формулой: . Нечеткая логика имеет прямое отношение к теории вероятностей.

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

Спецификация (определение) семантики программ средствами логики открывает путь к верификации (доказательству правильности) и синтезу алгоритмов и программ (алгоритмическая логика Хоара).

Идея определения семантики программ средствами логики воплощена в логическом программировании, использующем клаузальную логику, и реализована в языке PROLOG. Клаузальная логика - это форма стандартной (классической) логики предикатов и отличается от нее системой обозначений.

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

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

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

ЛИТЕРАТУРА

Основная литература

Краснов С.В., Каверин С.В. Дискретная математика./ Учебно-методическое пособие.- Тольятти: Волжский университет им. В.Н.Татищева, 2006, -101 с.
Каверина И.А. Задачник по математической логике. Учебно-методическое пособие.- Тольятти: Волжский университет им. В.Н.Татищева, 2006, 69С.
Каверина И.А., Ярыгин О.Н. Задачник по математической логике: Учебно-методическое пособие. - Тольятти: ВУиТ, 2009. - 146 с.
Каверина И.А. Курс лекций по математической логике и теории алгоритмов: Учебно-методическое пособие. - Тольятти: ВУиТ, 2008.-86с.
Ф.А.Новиков. Дискретная математика для программистов. /Санкт-Петербург: Питер, 2008г., 304С.
С.В.Судоплатов, Е.В.Овчинникова. Элементы Дискретной математики./ М., ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002г., 208С.
Я.М.Ерусалимский. Дискретная математика/ М., «Вузовская книга», 2001г.,279С.
Шапорев С.Д. Математическая логика. Курс лекций и практических занятий/ Санкт-Петербург: БХВ-Петербург, 2005г., 410С.

Дополнительная литература

А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. / М., Мир, 1979г., 536С.
Гиндикин С.Г. Алгебра логики в задачах./ М.Наука, 1972.
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. / М. Наука,1992.
Математическая логика /Методические указания к практическим занятиям и выполнению РГР по курсу «Дискретная математика», составители: М.Э.Рояк, С.Х.Рояк, Новосибирский государственный технический университет, 1998г.
Нефедов В.Н., Осипова В.А. Курс дискретной математики./ М., Изд-во МАИ, 1992г., 264С.
Шапиро С.И. Решение логических и игровых задач.– М: Радио и связь,1984. –152 с.
Шапорев С.Д. Математическая логика: Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2005. – 410 с.

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§4.3. Кванторы. Логика предикатов

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

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

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

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

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

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

§5.6. Исчисление предикатов

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

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

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

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

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

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

Глава VII. Нечеткая логика

Приложение 1. Доказательство теоремы Поста

Приложение 2. Варианты логики и логическое программирование

ЛИТЕРАТУРА

Оглавление