Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

высшего профессионального образования

КУРСОВАЯ РАБОТА

По дисциплине «Введение в теорию алгебраических систем»

Логика на словах

Содержание

• Введение
• 1) Основные этапы истории логики. Возникновение различных логик. Имена ученых, внесших существенный вклад в развитие логики
• 2) Основные понятия монадической логики второго порядка
• 2.1 Классификация грамматик
• 2.2 Язык логики предикатов
• 3 Автоматы Бучи
• 3.1 Подход с точки зрения автоматов и полугрупп
• 3.2 Автоматы Бучи
• 3.3 Автоматы и бесконечные слова
• 3.4 Детерминированные автоматы Бучи
• Заключение
• Приложение
• Введение
• Целью данной работы является изучение методов исследования распознаваемых языков, основанных на монадической логике второго порядка.
• Один из основных подходов к исследованию распознаваемых языков базируется на известной теореме Ж. Бучи о характеризации регулярных языков средствами монадической логики второго порядка.
• Для рассмотрения данной темы необходимо изучить следующие задачи:
• 1) Изучить основные этапы истории развития логики.
• 2) Изучить основные понятия монадической логики второго порядка.
• 3) Рассмотреть приложение монадической логики второго порядка к теории языков.
• 4) Разобрать доказательство теоремы Ж. Бучи о характеризации регулярных языков средствами монадической логики второго порядка.
• 5) С помощью теоремы Ж. Бучи исследовать взаимосвязь между иерархиями языков и определяющими их формулами первого порядка.

1) Основные этапы истории логики. Возникновение различных логик. Имена ученых, внесших существенный вклад в развитие логики.

Как самостоятельная наука логика сложилась в IV в. до н.э. Ее основателем по праву считается древнегреческий философ Аристотель (348 - гг. до н.э.). В своих научных трудах, посвященных логике, Аристотель впервые дал ее систематическое изложение и назвал “традиционной” формальной логикой. Традиционная формальная логика включала в то время такие разделы, как понятие, суждение, законы (принципы) правильного мышления, умозаключения (дедуктивные, индуктивные, по аналогии), логические основы теории аргументации, гипотеза. Основными работами Аристотеля по логике являются: “Первая аналитика”и “Вторая аналитика”, в которых дана теория силлогизмов, определение и деление понятий, теория доказательства; “Топика” -содержит учение о вероятных “диалектических” доказательствах; “Категории”, “Об опровержении софистических аргументов”, “Об истолковании”. Позже византийские логики объединили все перечисленные работы Аристотеля под общим названием “Органон” (орудие познания). Законы правильного мышления: закон тождества, закон непротиворечия, закон исключенного третьего - Аристотель изложил в своем главном произведении “Метафизика”. Законы мышления Аристотель рассматривал первоначально как законы бытия, а логические формы истинного мышления считал отображением реальных отношений. Для Аристотеля истина есть соответствие мысли действительности. Истинным он считал суждение, в котором понятия соединены между собой так, как связаны между собой вещи в природе. А ложным - суждение, которое соединяет то, что разъединено в природе, или разъединяет то, что связано в ней. Аристотель, опираясь на эту концепцию истинны, создал свою логику. В “Аналитиках” Аристотель довольно основательно разработал модальную логику. Аристотель видел в логике орудие, или метод исследования. Основным содержанием аристотелевской логики является теория дедукции. В логике Аристотеля содержаться элементы математической (символической) логики, в его работах прослеживаются начала исчисления высказываний, а его учение о силлогизме составило основу логики предикатов - одного из направлений современной математической логики.

Важным этапом в развитии учения Аристотеля явилась логика античных стоиков (Зенон, Хрисип и др.), именно она дополнила аристотелевскую теорию силлогизма описанием сложных умозаключений. Логика стоиков считается основой другого направления математической логики - логике высказываний. Среди других античных мыслителей, развивавших и комментирующих логическое учение Аристотеля, следует назвать Галена, именем которого названа 4-я фигура категорического силлогизма; Порфирия, известного разработанной им наглядной схемой, отображающей отношения подчинения между понятиями (“дерево Порфирия”); Боэция, сочинения которого дли тельное время служили основными логическими пособиями.

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

Значительны успехи логической науки в Новое время. Важнейшим этапом в ее развитии явилась теория индукции, разработанная английским философом Ф. Бэконом (1561- гг.). Бэкон подверг критике извращенную средневековой схоластикой дедуктивную логику Аристотеля, которая, по его мнению, не может служить методом научных открытий. Таким методом должна быть индукция, принципы которой изложены в его сочинении “Новый Органон”(в отличие от старого, аристотелевского “Органона”). Разработка индуктивного метода - огромная заслуга Бэкона, однако он неправомерно противопоставил его методу дедукции; в действительности эти методы не исключают, а дополняют друг друга. Бэкон разработал методы научной индукции, систематизированные впоследствии английским философом и логиком Дж.С.Миллем (1806- 1873 гг.). Таким образом, основателями индуктивной логики по праву считаются Ф. Бэкон и Дж. Милль, позднее в рамках этой логической теории были построены многочисленные дедуктивные теории для исследования логической проблематики.

Дедуктивная логика Аристотеля и индуктивная логика Бэкона-Милля составили основу общеобразовательной дисциплины, которая в течение длительного времени была обязательным элементом европейской системы образования и составляет основу логического образования в настоящее время. Эту логику принято называть формальной, так как она возникла и развивалась как наука о формах мышления. Ее также называют традиционной (или аристотелевской) логикой.

Дальнейшее развитие логики связано с именами таких выдающихся западно-европейских мыслителей, как Р. Декарт, Г. Лейбниц, И. Кант и др. Французский философ Р. Декарт (1569-1650гг.) выступил с критикой средневековой схоластики, он развил идеи дедуктивной логики, сформулировал правила научного исследования, изложенные в сочинении “Правила для руководства ума”. В 1662 г. в Париже вышла книга “Логика, или Искусство мыслить”, написанная последователями Декарта А. Арно и П. Николем, известная также под названием “Логика Пор-Рояля” (так как авторы были членами религиозной корпорации, обосновавшейся в монастыре Пор-Рояль). Эта книга оказала заметное влияние на всю последующую историю развития логики. Крупный вклад в исследование логических проблем внесли немецкий философ Г.Лейбниц (1646-1716 гг.), сформулировавший закон достаточного основания, выдвинувший идею математической логики, которая получила развитие лишь в XIX-XX вв.; немецкий философ И. Кант (1724- гг.) и др. западно-европейские философы и ученые.

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

Значительны заслуги в развитии логики русских философов и ученых. Ряд оригинальных идей выдвинули М.В. Ломоносов (1711-1765 гг.), А.Н. Радищев (1749-1802 гг.), Н.Г. Чернышевский (1828-1889 гг.). Известны своими новаторскими идеями в теории умозаключений русские логики М.И. Каринский (1804-1917 гг.) и Л.В. Рутковский (1859-1920 гг.). Одним из первых начал развивать логику отношений философ и логик С.И.Поварнин (1807-1852 гг.). Во второй половине XIX в. подлинную революцию в логике совершило широкое применение разработанных в математике методов: алгебраических, аксиоматического метода, метода формализованных языков, исчислений и формальных семантик. Это направление разрабатывается в трудах Дж. Буля, У.С. Джевонса, П.С. Порецкого, Г. Фреге, Ч. Пирса, Б. Рассела, Я. Лукасевича и других математиков и логиков. Теоретический анализ - дедуктивных рассуждений методами исчисления с использованием формализованных языков получил название математической (или символической) логики. Однако при всех новациях предмет логического анализа в основном оставался прежним.

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

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

В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646-- 1716), указавший пути для перевода логики “из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно”. Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления.

Следует отметить, что идея использования двух символов для кодирования информации очень стара. Австралийские аборигены считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования -- азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире.

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

Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью “Математический анализ логики, или Опыт исчисления дедуктивных умозаключений”, а в 1854 году появился главный его труд “Исследование законов мышления, на которых основаны математические теории логики и вероятностей”.

Буль изобрел своеобразную алгебру -- систему обозначений и правил, применимую к всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ).

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

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

2) Основные понятия монадической логики второго порядка.

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

Теорема. Если S является выполнимым монадическим предложением, то оно истинно в некоторой интерпретации, область которой содержит не более 2k * r элементов, где к -- количество (одноместных) предикатных символов, а r -- число переменных в S.

Итория логики и понятие разрешимости находятся в следующих причудливых отношениях: существенной чертой современного возрождения логики, начавшегося с работ Буля, Фреге и других, было заметное расширение понятия правильного умозаключения. Умозаключения, правильность которых зиждилась на «классической», или «досовременной», логике, трактуются современной логической теорией как умозаключения монодической логики, умозаключения, посылки и заключения которых могут быть символьно изображены формулами, содержащими только одноместные предикатные символы и, быть может, знак равенства. Однако такие интуитивно правильные умозаключения, как «Все лошади суть животные. Следовательно, всякий, кто ездит верхом на всех животных, ездит верхом на всех лошадях» или «Каждый любит каждого любящего. Следовательно, или никто не любит никого, или каждый любит каждого», которые не могли быть обоснованы «классической логикой», но которые современная логическая теория признает столь же правильными, сколь и любые умозаключения монадической логики, требуют для своего символьного изображения двуместных предикатных символов. Таким образом, платой за возрастание выразительной мощи этой теории является неразрешимость современного понятия правильного умозаключения, поскольку неразрешимость, возникает в тот момент, когда в предложения, используемые для символьного изображения умозаключений, допускаются двуместные предикатные символы (отличные от =).

Так же для раскрытия данной темы необходимо рассмотреть:

Лингвистика (языкознание, языковедение) -- наука, изучающая языки. Это наука о естественном человеческом языке вообще и о всех языках мира как индивидуальных его представителях. В широком смысле является частью семиотики как науки о знаках.

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

Язык -- знаковая система, соотносящая понятийное содержание и типовое звучание (написание).

Различают:

человеческие языки (предмет изучения лингвистики):

естественные человеческие языки,

искусственные языки для общения людей (например, эсперанто),

жестовые языки глухих,

формальные языки

компьютерные языки (например, Алгол, SQL),

языки животных

В математической логике и информатике формальный язык -- это множество конечных слов (син. строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этими объектами, называется теорией формальных языков. Например, если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, е или Л. Некоторые примеры формальных языков: множество всех слов над {a, b} множество {an}, где n -- простое число, а an означает, что a повторяется n раз множество синтаксически корректных программ в данном языке программирования Формальный язык может быть определен по-разному, например: Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.

Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского)

Иерархия Хомского -- классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачуссетского технологического института, лингвистом Ноамом Хомским.

2.1 Классификация грамматик

Согласно Хомскому, формальные грамматики делятся на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам.

Тип 0 -- неограниченные

К типу 0 по классификации Хомского относятся неограниченные грамматики (также известные как грамматики с фразовой структурой). Это -- все без исключения формальные грамматики. Для грамматики G(VT,VN,P,S), V=VTVN все правила имеют вид: где б -- любая цепочка, содержащая хотя бы один нетерминальный символ, а в -- любая цепочка символов из алфавита.

Тип 1 -- контекстно-зависимые

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики G(VT,VN,P,S), V=VTVN все правила имеют вид:бAв>бгв, где б, вV*, гV+, AVN. Такие грамматики относят к контекстно-зависимым.б>в, где б, вV+, |б|?|в|. Такие грамматики относят к неукорачивающим.

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

Тип 2 -- контекстно-свободные

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики G(VT,VN,P,S), V=VTVN все правила имеют вид:A>в, где вV+ (для неукорачивающих КС-грамматик, вV* для укорачивающих), AVN. То есть грамматика допускает появление в левой части правила только нетерминального символа.КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. грамматический анализ).

Тип 3 -- регулярные

К третьему типу относятся регулярные грамматики -- самые простые из формальных грамматик. Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:

A>Bг или A>г, где гVT*, A, BVN (для леволинейных грамматик).

A>гB; или A>г, где гVT*, A, BVN (для праволинейных грамматик).

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

2.2 Язык логики предикатов

Предикатная сигнатура - это множество символов двух типов - объектные константы и предикатные константы - с неотрицательным целым числом, называемым арностью, назначенным каждой предикатной константе. Предикатную константу мы будем называть пропозициональной, если её арность равна 0. Пропозициональные константы являются аналогом атомов в логике высказываний. Предикатная константа унарна, если её арность равна 1, и бинарна, если её арность равна 2. Например, мы можем определить предикатную сигнатуру { a, P, Q } (4) объявляя a объектной константой, P - унарной предикатной константой, и Q - бинарной предикатной константой.

Возьмём предикатную сигнатуру s, которая включает по крайней мере одну предикатную константу и не включает ни одного из следующих символов:

объектные переменные x, y, z, x1, y1, z1, x2, y2, z2, ...,

пропозициональные связки,

квантор всеобщности " и квантор существования $,

скобки и запятая.

Алфавит логики предикатов состоит из элементов из s и четырёх групп дополнительных символов, указанных выше. Строка - это конечная последовательность символов из этого алфавита.

Терм - это объектная константа или объектная переменная. Строка называется атомарной формулой, если она является пропозициональной константой или имеет вид R(t1, ..., tn), где R - предикатная константа арности n (n > 0) и t1, ... , tn - термы. Например, если мы рассматриваем сигнатуру (4), то P(a) и Q(a, x) - атомарные формулы.

Множество X строк замкнуто относительно правил построения (для логики предикатов), если каждая атомарная формула принадлежит X, для любой строки F если F принадлежит X, то ¬F тоже принадлежит, для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G), для любого квантора K, любой переменной v и любой строки F если F принадлежит X, то также принадлежит Kv F. Строка F является (предикатной) формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

Логика предикатов - центральный раздел логики, в котором изучается субъектно-предикатная структура высказывании и истинностные взаимосвязи между ними. Л.п. представляет собой содержательное расширение логики высказываний. В рамках данного раздела любое высказывание (пропозиция, предложение) рассматривается как некоторый структурно-сложный символ, разделяющийся на субъект, предикат и субъектно-предикатную связку. Субъект указывает на целостное понятие о предмете суждения; предикат -- на к.-л. отдельное свойство, присущее предмету суждения; субъектно-предикатная связка -- на отношение предикации (присущности), имеющее место между предметом суждения и отдельным свойством рассматриваемого предмета. Напр., в высказывании «Петр есть студент» слово «Петр» является субъектом, «студент» -- предикатом, а слово «есть» -- субъектно-предикатной связкой. Так же, как и в логике высказываний, в Л.п. любое высказывание считается либо истинным, либо ложным. Однако при этом кроме пропозициональных связок «)», «&», «V», «-->», «<-->» используются еще три логических оператора: оператор предикации «<--», квантор общности «V» и квантор существования «Э». Если с помощью оператора предикации (субъектно-предикатной связки) формализуется внутреннее логическое строение высказываний об отдельных объектах, то с помощью кванторов формализуются высказывания о различных совокупностях объектов. В естественном языке отдаленными смысловыми аналогами этих трех дополнительных операторов являются, соответственно, слова «есть (является)», «все» и «некоторые». Точный логический смысл этих операторов задается с помощью специальных семантических правил и формальных аксиом, постулируемых в соответствующем логическом исчислении. Наиболее распространено классическое исчисление предикатов, в котором из конечного числа аксиом по специальным правилам вывода могут быть получены общезначимые формулы Л.п., выражающие соответствующие логические законы. Средствами классического исчисления предикатов могут быть формализованы все основные типы высказываний силлогистики Аристотеля. Кроме классического первопорядкового исчисления предикатов используются и др., более изощренные варианты формализации содержательной теории предикатов. Среди них наиболее известно исчисление предикатов второго порядка, в котором допускается квантификация формул как по предметным переменным, так и по предикатным переменным. Средствами Л.п. может быть формализовано значительно больше естественно-языковых рассуждений, нежели средствами логики высказываний. Вместе с тем Л.п. не может обеспечить формализацию всего естественного языка, поскольку в ней не учитывается ряд важных содержательных положений, относящихся к сфере компетенции металогики.

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

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

Логика второго порядка существенно отличается от логики первого порядка. Шесть наиболее поражающих отличий таковы:

1) не существует эффективного позитивного теста на общезначимость предложений второго порядка.

2) Существует счетное невыполнимое множество предложений, каждое конечное подмножество которого выполнимо; одно из предложений этого множества является предложением второго порядка. (Таким образом, теорема о компактности не имеет места в логике второго порядка.)

3) Существует предложение второго порядка, имеющее в качестве моделей интерпретации с нечетными областями и только такие интерпретации. (Теорема Лёвенгейма - Сколема места не имеет.)

4) Существует предложение второго порядка, следствиями которого (первого и второго порядков) в L является предложения, истинные в N, и только они.

5) Существует предложение второго порядка, такое, что его моделями являются все те и только те интерпретации языка L, которые изоморфны N.

6) Существует формула второго порядка, истинная в N на гёделевых номерах тех и только тех предложений первого порядка, которые истины в N.

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

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

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

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

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

Предложение второго порядка S истинно в интерпретации X в следующих шести случаях. Где F будет означать формулу, которая может содержать свободные вхождения функциональной переменной u (пропозициональной переменной р, переменной X), а f(P, R) - функциональный символ (пропозициональный символ, предикатный символ), который не встречается в F. Предполагается, что f(R) имеет ту же местность, что и u(X). Обозначим через Xff (Xpi , XR) интерпретацию, если и отличающуюся от X , то только приписыванием функции f символу f (истинного значения i(=0,1) символу Р, характеристической функции символу R ). Через Fuf(FpP, FxR) обозначим предложение, полученное из F подстановкой f(P,R) вместо всех свободных вхождений u(p, X) в F.

Случай 1. X(uF)=1, если X(uF)=0, если	Xff (Fuf)=1 для всякой f , имеющей соответствующее количество аргументов, определенной на всей области интерпретации X и принимающей все свои значения в этой области. Xff (Fuf)=0 для хотя бы одной такой f.
Случай 2. X(uF)=1, если X(uF)=0, если	Xff (Fuf)=1 для хотя бы одной f , удовлетворяющей условиям случая 1. Xff (Fuf)=0 для любой f, удовлетворяющей условиям случая 1.
Случай 3. X(pF)=1, если X(pF)=0, если	Xp0(FpP)=XP1(FpP) Или Xp0(FpP)=0 или XP1(FpP)=0, или и то и другое .
Случай 4. X(pF)=1, если X(pF)=1, если	Или Xp0(FpP)=1, или XP1(FpP)=1, или и то и другое. Xp0(FpP)= XP1(FpP)=0
Случай 5. X(XF)=1, если X(XF)=0, если	XR(FxR)=1 для любой характеристической функции , имеющей соответствующее количество аргументов и определенной на всеё области интерпретации X. XR(FxR)=0 хотя бы для одной такой функции
Случай 6. X(XF)=1, если X(XF)=0, если	XR(FxR)=1 хотя бы для одной функции , удовлетворяющей условиям случая 5. XR(FxR)=0 для любой функции , удовлетворяющей условиям случая 5.

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

Пример 1: Определение равенства.

Как замечают Уайтхед и Рассел, лейбницево определение равенства, приведенное выше, может быть упрощено, поскольку предложение

общезначимо. Нет нужды в эквивалентности в правой части формулы!

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

Импликация справа налево: если , то для конкретной функции , которая приписывает значение 1 элементу и только ему, . Поскольку . Итак, приписывает 1 левой части (1) тогда и только тогда, когда она приписывает 1 правой части; доказательство завершено.

Пример 2. Аксиома счетности.

Обозначим через Ax En предложение

Предложение Ax En истинно в интерпретации тогда и только тогда, когда область интерпретации счетна.

Доказательство. Пусть - интерпретация и D - ее область.

Предположим, что . Тогда для некоторого a из D и некоторой функции f с множеством D в качестве множества значений выполняется



Пусть А= {a,f(a),f(f(a)),f(f(f(a))),…}, Тогда А - счетное подмножество D, содержащее а и для всякого своего элемента b содержащее также f(b). Пусть - характеристическая функция множества А. Тогда

Так как a принадлежит А, то имеет место . Поскольку А содержит f(b), если ему принадлежит А b, то

Значит, . Следовательно, всякое b из D принадлежит и А. Таким образом, D совпадает с А и потому счетно.

Обратно, предположим, что D счетно. Поскольку D является областью интерпретации , оно непусто. Пусть a0 ,a1,a2,… - пересчет без повторений всех элементов из D. Положим а=а0. Определим f , функцию с множеством D в качестве множества значений, следующим образом. Если пересчет а0,а1… бесконечен, положим f(x)=y тогда и только тогда, когда для некоторого I выполняется x=ai и y=ai+1 . А если для некоторого n имеет место a0 ,a1,…= a0 ,a1,a2,…an , положим f(x)=y тогда и только тогда, когда для некоторого i<n выполняется x=ai и y=ai+1 или x=an и y=an. В любом случае, если А - подмножество в D, содержащее a и для всякого своего элемента b содержащее также и f(b), то любой элемент множества D принадлежит А.

Отсюда получим, что для любого подмножества А множества D с характеристической функцией

и, таким образом

а следовательно,

,

т.е .

Таким образом, Ах En истинно в некоторой интерпретации тогда и только тогда, когда область этой интерпретации счетна.

Мы можем теперь заметить, что теорема Лёвенгейма - Сколема в логике второго порядка места не имеет: предложение Ах En истинно в любой интерпретации, область которой бесконечна и несчетна, но не является истинным ни в одной интерпретации со счетной областью. Таким образом, утверждение (3) доказано.

Перейдем теперь к доказательству утверждения (5). Обозначим через Ind предложение

Тогда Ind - предложение второго порядка языка L, формулизующее, с точки зрения интерпретации N, принцип математической индукции. Таким образом, Ind истина в N. Обозначим через PA конъюнкцию остальных шести аксиом теории Ind. Тогда PA истина в N.

Теорема. Любая интерпретация языка L, является моделью для PA, изоморфна N.

Доказательство. Пусть Х - интерпретация языка L, являющаяся моделью для PA, и D - ее область. Пусть далее X приписывает символам 0, `, и соответственно e, s, p и t.

Для любых a и b из D и любого подмножества А множества D

(I) если s(a)=s(b), то a=b;

(II) es(a);

(III) если e принадлежит A и (для любого с из D) то с принадлежит А, s(a) также принадлежит А, то А=D;

(IV) p(a,e)=a;

(V) p(a,s(b))=s(p(a,b));

(VI) t(a,e)=e;

(VII) t(a,s(b))=p(t(a,b),a).

Определим h - одно-однозначная функция с множеством всех натуральных чисел в качестве области определения и с множеством значения D, обладающая следующими свойствами:

h(m+n)=p(h(m),h(n)) и h(mn)=t(h(m),h(n))

для любых натуральных чисел m, n. В этом можно убедиться непосредственной скучной проверкой. Проведем её.

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

Функция h одно-однозначна. Предположим противное. Пусть m - наименьшее натуральное число, такое, что h(m)=h(k) для которого k>m, и пусть n, большее m таково, что h(m)=h(n). Так как m<n, то n=j' для некоторого j. Имеет место h(n)=h(j')=s(h(j)), и m=0, то h(m)=h(0)=e. Но, согласно (II), es(h(j)). Итак, m0. Таким образом, mi' для некоторого i, откуда i'<j', что дает i<j, а значит, поскольку i<m, то, согласно выбору m, h(i)h(j), и, таким образом, согласно (I), s(h(i))s(h(j)); имеем

h(m)=h(i')=s(h(i))s(h(j))=h(j')=h(n)

Противоречие.

Более того, е принадлежит множеству значений функции h, и если с тоже ему принадлежит, то c=h(n) для некоторого n, откуда h(n')=s(c), и, таким образом, s(c) принадлежит этому множеству. Из (III) следует теперь, что множество значений функции h совпадает с D/

Для любых m, n имеет место h(m+n)=p(h(m),h(n)). Действительно. H(m+0)=h(m), что, согласно (jv), равно p(h(m),e)=p(h(m),h(0)); кроме того, h(m+n')=s(h(m+n)) , что в силу предположения индукции равно s(p(h(m),h(n))) и в свою очередь, согласно (V), равно p(h(m),s(h(n)))=p(h(m),h(n')).

Далее, для любых m, n имеет место h(mn)=t(h(m),h(n)). Действительно, h(m0)=h(0)=e, что, согласно, (VI), равно t(h(m), e)=t(h(m),h(0)); кроме того, h(mn')=h(mn+m), что в силу приведенного выше равно p(h(mn),h(m)), что ввиду предположения индукции равно p(t(h(m),h(n)),h(m)), что, согласно (VII), равно t(h(m),s(h(n)))=t(h(m),h(n')).

Следствие.

Предположим, что А - предложение(первого или второго порядка) языка L. Тогда РА|- А. Тогда А истинно во всех моделях для РА. Но N является моделью для РА. Таким образом, А истинно в N. Тогда если X - интерпретация языка L, являющаяся моделью для РА, то, согласно теореме, N изоморфна X, и, таким образом, A истина в X. Итак, РА|- А.

3 Автоматы Бучи

3.1 Подход с точки зрения автоматов и полугрупп

Конечный инициальный полуавтомат А= (Z, A, , z0) называется акцептором, если вместе с А задано множество ЕZ. Е будем называть множеством заключительных состояний. Множество W(A):={A*| (z0, )E} называется языком, распознаваемым акцептором А

Пусть А - множество, и LA*. Язык L называется распозноваемым, если существует такой акцептор А, что L=W(A).

Пусть А - множество, RA*. Язык R называется регулярным, если R получается из одноэлементных подмножеств моноида А* конечным числом допустимых операция, где допустимые операции - это объединение, умножение и порождение подмоноида.

3.2 Связи между различными подходами

Теорема. Пусть LA*. Язык L распознаваем тогда и только тогда, когда он праволинеен.

Доказательство. Пусть язык L распознаваем. Тогда существует акцептор А=(Z, A, , z0, E), для которого W(A)=L. Без ограничения общности можно считать, что ZA=. Положим G:=(A, Z, z0), где :={za(z, a) | zA, aA} {zA | zE}. Очевидно, что грамматики G- правильная грамматика, то можно найти такой акцептор А, что L(G)=W(A).

Распознаваемые языки совпадают с регулярными.

Теорема. (Теорема Клини). Пусть LA*. Язык L распознаваем тогда и только тогда, когда он регулярен.

Доказательство. Пусть язык L распознаваем: L=W(A), где А=(Z, A, ,z0, E). Можно показать, что L строится из одноэлементных подмножеств моноида А* с помощью допустимых операций. Поэтому L регулярен.

Обратно, пусть L регулярен. Для и для одноэлементных подмножеств из А* с помощью допустимых операций. Поэтому L регулярен.

Обратно, пусть L регулярен. Для и для одноэлементных подмножеств из A* легко строятся акцепторы, которые распознают в точности эти множества. Далее показывается, что результат каждой допустимой операции, примененной к распозноваемым множествам, снова распознается подходящим акцептором. С помощью индукции получаем акцептор А, такой что L=W(A). Поэтому L - распознаваемый язык.

Языки, порождаемые грамматиками

Контекстно-свободные языки

Не все подмножества из А* регулярны. Кроме того, можно показать, что существуют контекстно-свободные языки, не являющиеся праволинейными. Поэтому не всякий контекстно-свободный язык регулярен. Контекстно-свободные языки L можно описать в виде L=W(A), если использовать более общий класс автоматов, так называемые автоматы Келлера.

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

Подмножество P={p1, p2,…} из N0 называется переодическим, если существуют числа q, k, n0N0 , такие, что pn+k- pn=q для всех nn0.

Теорема. Пусть А={a} и LA* . Язык L регулярен тогда и только тогда, когда существует такое периодическое подмножество Р из N0, что L={ap | pP}.

Доказательство. Пусть L регулярен. Тогда существует такой акакцептор А=(Z, {a},, z0, E), что L=W(A). Покажем zi=(z0, ai) для iN0. Так как множество Z конечно, найдутся такие m, nN0, что m>n и zm=zn. Тогда

Zm+1= (z0, am+1)=( (z0, am), a)=(zm, a)=(zn, a)=…=zn+1

В общем, zm+j=zn+j для всех jN0, т.е lm: zl+(m-n)=zl, откуда lmrN0: zl+r(m-n)=zl. Покажим

M:={kN0 | k<m ^ zkE}, N:={lN0 | ml<n ^ zl E}.

Тогда

W(A){ak | kM } {a l+r(m-n) | lN ^ rN0}

Это показывает, что множество P:={pN0 | apW(A)}=M{l+r(m-n) | lN ^ rN0} периодично.

3.2 Автоматы Бучи

Теперь в данной работе вводится понятие «Автоматы Бучи». Автомат Бучи - с 5 элементами = (Q, A, E, I, F) где:

1) (Q, A, E) автомат

2) I и F - подмножества Q, названного набором начальных состояний и набором конечных состояний.

Пусть А = (Q, A, E, I, F) является автоматом Бучи. Говорим что бесконечный путь в A является начальным, если I и F бесконечны. Набор бесконечных слов, названных A, является набором, обозначенным L(A), лейблов бесконечных успешных путей в A. В случае, где F конечен и в особенности если A - конечный автомат, L(A). Набор X из бесконечных слов являются распознаваемыми, если там существует конечный Бучи автомат А таким образом, что X = L(A).

Автомат Бучи А= (Q, A, E, I, F), детерминирован, если у него есть детерминированные переходы и если I - единичный, то есть если A содержит точно одно начальное состояние i.

Автомат Бучи A = (Q, A, E, I, F) называют ко-детерминированным, имеет cо-детерминированные переходы и если какое-нибудь слово в A - метка самого большего заключительного пути. A однозначный, если каждое слово в A - лейбл в большинстве одного бесконечного пути. В частности каждое слово в L (A) определяет уникальный успешный бесконечный путь.

Детерминированные переходы	Кодетерминированные переходы	однозначный
Запрещенная конфигурация:	Запрещенная конфигурация:	Запрещенная конфигурация: где u - слово



Рис 1. Ко-детерминированный автомат Бучи

У нас имеется L (A) = a(a*b), который является набором бесконечных слов, начинающихся с a и содержащих бесконечное число возникновений b.

логика предикат автомат бучи

3.3 Автоматы и бесконечные слова

Рис.2. Другой ко-детерминированный автомат Бучи.

L +(A) = {a, b}+ и L (A) = {a, b}* a. Этот автомат также cо-детерминированный.

Рис.3. - однозначный автомат.

Он не детерминирован, так как у него есть два начальных состояния, и он не cо-детерминирован.

Лемма 1 Любое непустое распознаваемое подмножеств A содержит в конечном счете периодическое слово.

Доказательство. Пусть X непустое распознаваемое подмножество названное автоматом Бучи А = (E, I, F). X непустое, и p = p0 p1 p 2…., где qF, и где p1, p2, …пути от q до q. Путь p0 p1 p1 p1… в конечном счете периодическое слово. Пусть А = (E, I, F) автоматом Бучи. q называют доступным если есть (возможно пусто) конечный начальный путь в окончании в q. Подавление всех "бесполезных" элементов автомата Бучи всегда дает упорядоченный автомат.

(a) Автоматы A и A' являются подмножеством A,

(b) если A детерминирован, то A' тоже детерминирован.

(c) если A конечено, то A' тоже конечно.

Доказательство. (a) Пусть А = (Q, A, E, я, F) автомат Бучи, а P набором элементов. Пусть А = (P, A, E', IP, FP), где E'= E (P A P), тогда

L (A') L (A).

Наоборот, пусть u = a0,a1… L (A). Есть заключительный путь p=q0q1q2….

с u таким образом, что q0I. Множество q0, q1... доступны. Таким образом, p - путь в A' и u L (A'). Следовательно L (A) = L (A').

(b) Если A детерминирован, то автомат (P, A, E') детерминирован. Таким образом, I P - единственный. Поэтому A' детерминирован.

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

Рис.4. Завершение автомата Рис.2.

Автоматы и бесконечные слова

Теперь доказываем аналог теоремы Клини для бесконечных слов.

Теорема. Подмножество A является распознаваемым, тогда и только тогда, когда - рациональный.

Доказательство. Пусть X из A и пусть А=(E, I, F) конечный автомат Бучи, признающий X. Тогда

показывает, что - рациональный и L (E, I, f) и L+ (E, f, f) являются рациональными подмножествами A*.

Обратное. Пусть - рациональный и пусть А = (Q, A, E, i, f) и A' = (Q', A', E', I', f') два нормализованных автомата, таким образом что X = L+(A) и X' = L+ (A')

Рис 5. Автомат, признающий X (X).

B = ((QQ') \{i', f'}, T, i, f), где T = E E0 E1 E2

E0={(f, a, f) | (i', a, f')E'}

E1={(f, a, f) | qQ'\{i', f' } и (i', a. q )E'}

E2={(q, a,f) | qQ'\{i', f'} и (q, a, f')E'}

Это показывает, что X (X') является распознаваемым. Чтобы закончить доказательство теоремы, необходимо доказать что класс из распознаваемых подмножеств A устойчив. Пусть тогда Y и Y' два распознаваемых подмножествами A, названного конечным автоматом Бучи A = (Q, A, E, I, F) и A'= (Q', A', E', I', F'). Можно предположить, что Q и Q' являются несвязными, и таким образом мы можем идентифицировать E и E ` с подмножествами (Q Q') A (Q Q'). От сюда имеем формулу:

таким образом Y Y' признан конечным автоматом (Q Q', A, E `E, II', FF').

Следствие 5. Если X распознаваемое подмножество B, то -1 (X) подмножество A.

Доказательство. Пусть B = (Q, B, E, I, F) быть автоматом Бучи. Пусть

где E' = E1 E2, с E1={((q,i),a,(q',0)) | i{0, 1 и E2={((q,i),a,(q',1)) | i{0, 1}}

Пусть u =а0а1…. является словом в A и пусть для всех n0, vn =(an). Тогда u принадлежит А тогда и только тогда, когда там существует путь в Q{0,1} и таким образом путь

p=(q0,0)(q1,1)(q2,2)….

проходящий бесконечно часто в Q {1}. По определению E' это означает то, что там существует последовательность последовательных путей в B:

q0q1q2….

Пример 5 Пусть :{a, b, c}+ {a, b}+ является определенным изоморфизмом полугруппы (a) = a, (b) = ab (c) = babaab и пусть X = (ababa).



Рис 6. Автомат, признающий (ababa).

Рис 7. Автомат, признающий -1((ababa)).

3.4 Детерминированные автоматы Бучи

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

Описание подмножеств признанного детерминированными автоматами Бучи идет с введением нового оператора. Для подмножества L для A*, пусть

={uA | у u есть бесконечно много приставок в L }

Оператор L играет роль, подобную L L, теперь это позволяет определять бесконечные слова от конечных.

Следующий пример дает ценность для простых наборов L.

Пример 1.

(а) если L=a*b , тогда =

(в) если L=(ab)+, тогда =(ab)

(c) если L=(a*b)+ = (a+b)*b.

Заключение

В данной работе были изучены методы исследования распознаваемых языков, основанных на монадической логике второго порядка. Рассмотрены основные этапы истории развития логики, основные понятия монадической логики второго порядка, приложения монадической логики второго порядка к теории языков, разобран раздел «Автоматы Бучи».

Приложение

Предикат - это функция с областью значений {0,1} (или «Ложь» и «Истина»), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M он характеризует либо как «истинную», либо как «ложную»

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

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

Общность - единство, неразрывность.

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

Список использованных источников

1 Булос Дж, Джеффри Р. Вычислимость и логика 1994 - 396с., ил.

2 http://www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html

3 http://sdo.uspi.ru/mathem&inform/lek2/lek_2.htm

4 http://inf.1september.ru/2002/1/arist.htm

Размещено на Allbest.ru