3410_2 МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

ВВЕДЕНИЕ

 

Начало исследования формальной логики и алгоритмов восходит к временам Древнего Египта, Древней Греции и Вавилона. Эти исследования проводились в рамках теории чисел. Хорошо известны алгоритмы сложения, умножения, деления чисел, записанные Евклидом. В XVI веке известный математик Х.Рудольф провозгласил алгоритм основным принципом арифметики.

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

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

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

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

 

 

 

 

1. ОСНОВНЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

 

1.1. Элементы теории формальных грамматик

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

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

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

Примеры

Пусть задан алфавит { а, b, с, 1, 2 }. Тогда цепочками в этом алфавите являются следующие слова: ааааааа, 12bbbb, a2b, 1 , 0, где 0 - пустая цепочка в этом алфавите.

Для длин цепочек можно привести следующие примеры:
| a a a b b 1 |= 6,     | 0 |  =   0 .

Конкатенацией (композицией) цепочек х и у называют новую цепочку z = =ху, получаемую приписыванием символов цепочки у к концу цепочки х.

Цепочку (слово) у называют подцепочкой (подсловом) цепочки z, если справедливо одно из следующих соотношений:

z=xy,      z=yx,      z=xyt, где х и t - какие-либо цепочки.

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

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

При этом все слова языка, составленные из символов алфавита, называют терминальными символами языка.

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

Правила порождения предложений некоторого языка называют его грамматикой.

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

Продукция представляет собой выражение следующего вида: Nàх, где N - нетерминальный символ, обозначающий целую цепочку терминальных символов х. Продукция читается так: "N представляет собой х". N называют левой частью продукции, а х- правой.

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

Если обозначить множество терминальных символов через Т, а множество нетерминальных символов через U, то будет справедливо следующее утверждение: V = Т È U. Здесь “È” - знак объединения множеств.

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

Итак, языком L называется следующая система множеств:

L = < Т, U, G(S) >, где G(S) - грамматика языка с начальным символом S.

Пример

Определим язык L с грамматикой G(<предложение>). Пусть множества Т и N будут равны соответственно:

Т = { в, туманном, закатном, утреннем, море, заливе, белеет, тает, маячит, одинокий, таинственный, парус }.

N = { <предлог> <группа подлежащего> <сказуемое>

<подлежащее><обстоятельство места>

<прилагательное><место>}.

Зададим грамматику G(<предложение>):

<предложение> à <обстоятельство места><сказуемое>

<группа подлежащего>,

<обстоятельство места> à <предлог>

<прилагательное>< место>,

<группа подлежащего> à <прилагательное><подлежащее>,

<сказуемое> à белеет, <сказуемое> à тает,

<подлежащее> à парус, <место> à море,

<место> à заливе,

<прилагательное> à туманном, закатном, утреннем, одинокий, таинственный,

<предлог> à в.

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

"В туманном море маячит одинокий парус".

Варианты заданий

Самостоятельно составить несколько однотипных предложений из какой-либо произвольной (для каждого варианта - своей) предметной области (например, “рынок”, “вокзал”, “метеосводка”, “туризм” и т.п.). Описать для этих предложений грамматику аналогично примеру п.1.1.

 

1.2. Элементы  математической логики

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

 

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

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

Под формальной системой Ф понимается следующая система множеств:       Ф = < F, А, Т, P > ,

где F - множество правильно построенных формул, А - множество аксиом формальной системы, Т - множество теорем, Р - множество правил вывода из одних истинных утверждений других.

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

Множество аксиом состоит из заведомо истинных выражений, сформулированных в том же языке.

Множество теорем отличается от множества аксиом тем, что в него включаются все истинные высказывания формальной системы, доказанные c помощью использования некоторых правил вывода Р.

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

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

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

 

1.2.2. Алгебра высказываний

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

Операции над высказываниями:

-         отрицание - (ù                   ),  конъюнкция - (Ù), дизъюнкция - (v),

-         импликация - (Þ), неравнозначность - (¹),

-         эквивалентность – (=).

Приоритет операций (в порядке убывания): ù  , Ù, v, Þ,=, ¹.

Основные свойства операции отрицания:

-   закон двойного отрицания: ùùP=P;

-   закон исключенного третьего: P vù  P=true;

-   закон противоречия :    P Ù  ù P= false.

Для операций конъюнкции и дизъюнкции:

-   ассоциативность:     PÙ(QÙV)=(PÙQ) ÙV;

-   P v (Q v V)=(P v Q) v V;

-   коммутативность: P v Q=Q v P; PÙQ=QÙP;

-   дистрибутивность: (PÙQ) v V=(P v V) Ù(Q v V);

-   (P v Q) ÙV=(PÙV) v (QÙV);

-   закон де Моргана: ù(Q v P)= ùQÙùP; ù(QÙP) =ù Q vù P.

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

PÞQ=ùP v Q; PÞ(QÞV)=(PÙQ)ÞV;

(PÞQ)Þ((PÙV)ÞQ); (PÞQ) v (PÞV)=PÞ(V v Q).

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

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

Пример построения КНФ

Приведем к КНФ формулу: (pÞ(qÞr)) Þ((pÙs) Þ r).

  1. Исключение импликации

ù(pÞ(qÞr)) Ú ((pÙs) Þ r), ù(ùpÚ(qÞr)) Ú ((ùpÙs) Úr),

ù(ùpÚ(ùqÚr)) Ú ((ùpÙs) Úr).

  1. Перенос и снятие отрицаний

(ù ùpÙù(ùqÚr)) Ú ((ùpÚùs) Úr), (ù ùpÙ(ùùqÙùr)) Ú ((ùpÚùs) Úr),

(pÙ(qÙùr)) Ú ((ùpÚùs) Úr).

  1. Использование свойств дистрибутивности

(pÚ((ùpÚùs) Úr) Ù ((qÙùr)Ú(ùpÚùs) Úr)),

(pÚ((ùpÚùs) Úr) Ù (qÚ(ùpÚùs) Úr) Ù (ùrÚ(ùpÚùs) Úr)).

  1. Использование ассоциативности

(pÚùpÚùsÚr) Ù (qÚùpÚùs Úr) Ù (ùrÚùpÚùsÚr) - уже КНФ.

  1. Упрощение исключенным третьим

qÚùpÚùs Úr.



 
Условие до которого будет выполняться цикл. элемент Списки определений