WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

Pages:   || 2 |

«ИЗБРАННЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ В УТВЕРЖДЕНИЯХ И УПРАЖНЕНИЯХ Пособие для студентов, обучающихся по специальности 1-31 03 04 «Информатика» МИНСК БГУ УДК 519.1 (0.75.8) ББК 22.176я73-1 М87 ...»

-- [ Страница 1 ] --

В. А. Мощенский

ИЗБРАННЫЕ ГЛАВЫ

ДИСКРЕТНОЙ

МАТЕМАТИКИ

В УТВЕРЖДЕНИЯХ

И УПРАЖНЕНИЯХ

Пособие для студентов,

обучающихся по специальности

1-31 03 04 «Информатика»

МИНСК

БГУ

УДК 519.1 (0.75.8)

ББК 22.176я73-1

М87

Рекомендовано ученым советом

факультета прикладной математики и информатики

6 декабря 2011 г., протокол № 3

Р e ц е н з е н т ы:

доктор физико-математических наук, профессор А. Н. Курбацкий;

кандидат физико-математических наук, профессор А. И. Павловский Мощенский, В. А.

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

1-31 03 04 «Информатика». – Минск : БГУ, 2012. – 168 c.

ISBN 978-985-518-659-6.

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

Для студентов факультета прикладной математики и информатики БГУ.

УДК 519.1 (0.75.8) ББК 22.176я73-1 © Мощенский В. А., 2012 ISBN 978-985-518-659-6 © БГУ, 2012

ПРЕДИСЛОВИЕ



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

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

К особенностям этого раздела можно отнести:

• разнообразные равносильные преобразования формул логики высказываний;

• большое количество решенных примеров;

• описание алгоритма построения выводов формул исчисления высказываний (выводимые формулы обозначены *, а свойства выводов – °);

• построение для каждого натурального n ( n 2) формулы логики предикатов, истинностной в любой интерпретации с областью по мощности не более n 1.

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

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

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

По сути, этот раздел можно назвать вторым изданием (исправленным и дополненным упражнениями) работ [4] и [5].

Автор выражает признательность рецензентам А. Н. Курбацкому и А. И. Павловскому, а также В. М. Котову и с благодарностью примет все конструктивные замечания.

1. ЭЛЕМЕНТЫ

МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

1.1. ВЫСКАЗЫВАНИЯ И ОПЕРАЦИИ НАД НИМИ

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

Например, высказываниями являются «Луна – естественный спутник Земли» (истинное), «5 4» (истинное), «для каждого действительного числа x x 2 0» (истинное), «существует целое число m такое, что m 2 = 5» (ложное) и др.

Но не каждое повествовательное предложение является высказыванием. Например, «сегодня хорошая погода» не считается высказыванием из-за субъективности понятия «хорошая погода». Математические определения также не относят к высказываниям, и поэтому об определениях не говорят, что они истинны или ложны.

Рассмотрим повествовательное предложение: «Я лгу», – говорит некто. Случай истинности (ложности) этого предложения влечет его ложность (истинность). Этот факт называется парадоксом лжеца.

Другой пример аналогичной ситуации следующий: «Деревенский парикмахер бреет тех и только тех, кто не бреется сам. Бреет ли он сам себя?»

Индивидуальные высказывания будем обозначать v,, vi и i (i 1). Еще условимся о следующем: если некоторое высказывание v() истинно (ложно), то будем говорить, что оно имеет истинностное значение «истина» («ложь»), и писать (v) = 1 (() = 0).

Например, (3 2) = 1, а (1 = 4) = 0.

Значением высказывания будем называть его истинностное значение и в дальнейшем отождествлять высказывание с его значением.

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

Высказывание, не являющееся составным, называется простым.

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

Отрицанием высказывания v называется высказывание, обозначаемое через v (или ¬v ), которое истинно тогда и только тогда, когда v ложно.

Это определение запишем в виде следующей таблицы (табл. 1).

Таблица 1 v v Выражение v (и ¬v) читается «не v». Высказывания «не v», «не верно, что v» передают высказывание v.

Пусть v и – некоторые высказывания. Тогда их дизъюнкция обозначается через v (читается: «v или »), их конъюнкция – через v (читается: «v или »), другие обозначения: v &, v, v; их импликация – через v (читается: «v влечет »), и v называется посылкой, а – заключением; их эквиваленция – через v (читается: «v эквивалентно »).

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

Таблица 2 v v v v v

Высказывания «v или », «v либо », «или v, или », «v и/или », «по крайней мере, одно из высказываний v и истинно» передают высказывание v.

Высказывания «v и », «и v, и », «одновременно оба высказывания v и истинны» передают высказывание v.

Высказывания v означают то же, что и высказывания «если v, то », «из v вытекает », «v только тогда, когда », «v есть достаточное условие для », « при условии, что v», «, если v», « есть необходимое условие для v», « тогда, когда v», «для того чтобы v, необходимо, чтобы », «для того чтобы, достаточно, чтобы v».

Высказывания «v тогда и только тогда, когда », «v есть необходимое и достаточное условие для », «для того чтобы v, необходимо и достаточно, чтобы » означают высказывание v.

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

Определения всех операций, кроме импликации, выглядят естественно. Данное определение импликации вызывало поток возражений у философов; они приводили пример импликации: «если 2 2, то существуют ведьмы» (она истинна по определению), и утверждали, что математики доказывают существование ведьм. Конечно, существование ведьм этим не доказывается. Принятое определение импликации отражает многие реальные ситуации и, что важнее всего, позволяет сокращать математические утверждения. Вот типичный пример. Хорошо известно следующее утверждение: каждый корень уравнения f ( x) = g ( x) является и корнем уравнения f 2 ( x) = g 2 ( x).





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

если первое уравнение имеет корни и a есть его корень, то a является и корнем второго уравнения; что намного длиннее первого варианта.

Таблицы 1 и 2 и им подобные называются истинностными таблицами.

З а м е ч а н и е. Операции конъюнкции и дизъюнкции определяют и для n (n 2) высказываний v1, v2,..., vn : v1 v2... vn и v1 v2... vn, первое из которых истинно тогда и только тогда, когда все vi истинные, а второе ложно тогда и только тогда, когда все vi ложные.

Пример 1.1.

Пусть v1 = v2 = 1, v3 = 0 и есть составное высказывание ((v1 v2 ) v3 ) (v2 v3 ).

Найдем его значение при указанных значениях vi. Под знаками логических операций напишем значения соответствующих высказываний:

((v1 v2 ) v3 ) (v2 v3 ), т. е. это составное высказывание истинно.

Если бы v1 = v3 = 0, v2 = 1, то данное составное высказывание имело бы значение 0.

Пример 1.2.

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

Здесь простыми высказываниями являются: 1) Петр опоздает (v1 );

2) Петр пойдет на первый час первой лекции (v2 ); 3) Петр доволен (v3 );

в скобках указаны их обозначения.

В этом составном высказывании встречаются все упомянутые союзы, кроме «a », который в этом случае передает конъюнкцию. Поэтому символическая запись следующая: ((v1 v2 ) v3 ) (v1 v3 ).

Пример 1.3 (задача о туристе).

Турист направлялся к озеру и дошел до перекрестка, откуда одна дорога вела к озеру, а другая – нет.

Какая из дорог шла к озеру, он не знал. На перекрестке сидели двое парней. Один из них всегда говорил правду, а второй – всегда лгал.

На каждый вопрос они отвечали «да» или «нет». Все это было известно туристу, но он не знал, кто из них говорит правду. Тогда турист спросил каждого из парней об одном и том же и по их ответам безошибочно решил, какая дорога ведет к озеру. Какой это был вопрос?

Решение. Очевидно, что вопрос должен быть составным высказыванием, в котором одно простое высказывание имеет известное туристу значение. Эта подсказка помогает прийти к следующему: верно, что 2 2 = 5 и что дорога, идущая налево, ведет к озеру? Обозначим первое высказывание (т. е. 2 2 = 5) из этой конъюнкции через v, а второе – через, причем v = 0. Для высказывания имеются две возможности: 1) = 0; 2) = 1. Рассмотрим каждую из них.

В первом случае парень, говорящий правду, скажет, что (v ) = 0, а лгун – (v ) = 0, так как он будет инвертировать все значения (ведь у него v = 1, = 1 и v = 1).

Во втором случае говорящий правду ответит, что (v ) = 0, а лгун – (v ) = 1, так как на самом деле v = 0, = 1, (v ) = 0, а лгун должен все значения изменить на противоположные. Из рассмотрения этих случаев вытекает, что если ответы различные, то дорога выбрана правильно.

Пример 1.4.

В некоторых математических утверждениях высказывание v заменяют на v (и обратно). На основании этого и истинностных таблиц для отрицания и дизъюнкции получим табл. 3.

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

Таблица 3 v v v v Упражнения

1. Найти значения следующих составных высказываний:

а) (v1 ¬(v2 v3 )) (v1 v2 v3 );

б) (v1 (v2 v3 )) ((v1 v2 ) (v1 v3 )) на всевозможных наборах значений трех высказываний.

2. Построить истинностную таблицу для союза «или» в разделительном смысле.

3. В задаче о туристе можно:

а) задать одному из парней два вопроса;

б) спросить только одного парня и по ответам точно определить нужную дорогу. Какие это будут вопросы? (Указание: случай а) тривиален, а в случае б) следует спросить: «Сказал бы второй парень, что эта дорога ведет к озеру?»)

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

а) 3 – иррациональное число, или существует рациональное число, не являющееся целым;

б) Петр встанет, и он или Иван уйдет;

в) Петр встанет и уйдет, или Иван уйдет;

г) Петр ходит в кино только тогда, когда там показывают комедию;

д) студент не может заниматься, если он устал или голоден;

е) для того чтобы натуральное число a было нечетным, достаточно, чтобы a было простым и больше 2;

ж) необходимым условием сходимости последовательности S является ограниченность S ;

з) в степи не будет пыльных бурь тогда и только тогда, когда будут лесозащитные полосы; если лесозащитных полос не будет, то пыльные бури уничтожат посевы и нанесут урон хозяйству;

и) или Петр пойдет на дискотеку, а Иван не пойдет; или Петр не пойдет на дискотеку, и Иван приятно проведет время.

1.2. ФОРМУЛЫ ЛОГИКИ ВЫСКАЗЫВАНИЙ.

ТАВТОЛОГИИ

Формулы логики высказываний (ФЛВ) будем строить из следующих списков символов:

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

2) ¬,,,, – символы логических операций;

3) p, q, r, s, p1, q1, r1, s1, p2,... – бесконечный список букв (высказывательные переменные, или просто переменные);

4) (,) – скобки (вспомогательные символы).

Некоторые конечные последовательности из этих символов будем называть ФЛВ. Их понятие определим индуктивно.

Индуктивное определение формул логики высказываний

1. Каждая константа и каждая переменная есть ФЛВ.

2–6. Если A и B являются ФЛВ, тогда (¬A), ( A B), ( A B), ( A B ) и ( A B ) – также ФЛВ.

Определение закончено. В этом определении п. 1 задает так называемые исходные ФЛВ, а пп. 2–6 являются правилами построения новых ФЛВ из заданных. Такие ФЛВ будем называть ФЛВ в базисе {0, 1, ¬,,,, }.

Пример 1.5.

Исходные ФЛВ – это 0, 1, p, q, r, s, p1, q3, r5, s101 и др.; неисходными ФЛВ являются (¬ r ), ( p (¬ q)),( p (q r )), (( p q ) ((r1 ) ( s1 s2 ))) и др.

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

Чтобы упростить записи ФЛВ, условимся о следующем старшинстве операций: 1) ¬; 2) ; 3) ; 4) ; 5).

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

Например, неисходные ФЛВ из примера 1.5 теперь можно записать ¬ r, p ¬ q, p ( q r ), p q r1 s1 s2.

Пример 1.6.

Договоримся писать ¬A, AB, AB, AB и AB вместо (¬A), ( A B), ( A B ), ( A B ) и ( A B ) соответственно.

Тогда скобки в ФЛВ не будут нужны и каждая ФЛВ однозначно представится в такой записи, называемой бесскобочной или польской (докажите это математической индукцией по числу логических символов в ФЛВ). Например, ФЛВ p p q и p q (r p) в бесскобочной записи запишутся так: ¬p p ¬ q и p q ¬ rp.

Пусть x1, x2,..., xn – список попарно различных переменных.

(В этом случае x1, x2,..., xn – буквы (их называют метапеременными), которые мы употребляем как имена для (высказывательных) переменных, если не будем ограничивать наши рассуждения использованием конкретных переменных.) ФЛВ, в которой не встречается переменных, отличных от x1, x2,..., xn, будем обозначать через A( x1, x2,..., xn ), или B ( x1, x2,..., xn ), или C ( x1, x2,..., xn ) (возможно, со штрихами, звездочками и нижними индексами); в этом обозначении часть переменных не всегда входит явно в формулу A.

Например, ФЛВ p (q p ) можем обозначить через A( p, q ) или B ( p, q, r ), но не через A1 ( p ).

Пусть A( x1, x2,..., xn ) – некоторая ФЛВ и v1, v2,..., vn – произвольные высказывания. Поскольку мы отождествляем высказывания с их значениями, то можем считать, что каждые vi есть 0 или 1. После замены в A( x1, x2,..., xn ) каждой xi на vi (1 i n) получим высказывание A(v1, v2,..., vn ), значения 0 или 1 которого будем считать значением ФЛВ A( x1, x2,..., xn ) на наборе (v1, v2,..., vn ) значений переменных x1, x2,..., xn.

Значения ФЛВ для всех возможных наборов значений ее переменных удобно приводить в виде таблицы, которая называется истинностной таблицей этой формулы. Если данная ФЛВ имеет n различных переменных, тогда ее истинностная таблица содержит 2n строк. В табл. 4 перечислены все значения двух ФЛВ: r. p (q r ) и ¬( p q ) p q.

Таблица 4 r p q ¬( p q ) pq r. p (q r ) П р и м е ч а н и е. В этой таблице мы не вычисляли для первой ФЛВ значение заключения, если значение посылки было 0.

ФЛВ, значение которой на каждом наборе значений ее переменных есть 1 (соответственно 0), называется тавтологией (соответственно противоречием).

Например, вторая формула из табл. 4 есть тавтология, а противоречием является p. p.

Обычно пишут A (читается: «тавтология A»), если ФЛВ A есть тавтология. Например, ¬ ( p q) p q.

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

Пример 1.7.

Иногда проще убедиться, что данная ФЛВ есть тавтология методом от противного (нежели строить ее истинностную таблицу). Например, докажем, что p (q p ). Допустим, что для некоторых высказываний v и будет (v ( v)) = 0. Отсюда v = 1 и ( v) = 0, а значит, = 1 и v = 0. Получили v = 1 и v = 0 – противоречие. Следовательно, указанная формула – тавтология.

Заметим, что ФЛВ A является тавтологией тогда и только тогда, когда ¬A есть противоречие.

Высказывание (в каком-нибудь естественном языке, например в русском), которое получается из некоторой тавтологии путем подстановки высказываний (естественного языка) вместо ее переменных при условии, что вхождения одной и той же переменной замещаются одним и тем же высказыванием, называется логически истинным (в логике высказываний). О таком высказывании можно утверждать, что оно истинно уже в силу только своей структуры. Например, следующее высказывание: «студент пишет ручкой или карандашом, и не пишет карандашом, то он пишет ручкой», которое получается подстановкой в тавтологию (( p q ) q) p.

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

Например, логически ложным является высказывание «5 4 и 5 4», получаемое из противоречия p p.

Сформулируем еще несколько утверждений о тавтологиях.

Лемма 1.1.

Если A и A B, то B.

Допустив, что верны посылки и ложно заключение, т. е. ФЛВ B принимает значение 0 на хотя бы одном наборе значений переменных, приходим к тому, что A B не тавтология.

Лемма 1.2.

Если A и A содержит переменные x1, x2,..., xn, а ФЛВ B получается из A подстановкой произвольных ФЛВ A1, A2,..., An вместо x1, x2,..., xn соответственно, то B, т. е. подстановка в тавтологию дает тавтологию.

Доказательство. Пусть A и B получается из A описанным способом. Зададим для всех переменных формулы B (число которых m) произвольный набор их значений (v1, v2,..., vm ). Тогда формулы A1, A2,..., An примут некоторые значения 1, 2,..., n соответственно. Если же переменным формулы A x1, x2,..., xn придать значения 1, 2,..., n соответственно, то полученное значение А будет совпадать со значением B на наборе (v1, v2,..., vm ). Так как A, то и B. Лемма доказана.

Лемма 1.3.

Пусть ФЛВ A содержит не менее одного вхождения ФЛВ B. Если ФЛВ A1 получается из A подстановкой ФЛВ C вместо одного или большего числа вхождений B, то ( B C ) ( A A1 ).

Доказательство. Пусть выполняются условия этой леммы. Рассмотрим произвольный набор значений переменных формулы, тавтологичность которой утверждается. Если значения формул B и C на этом наборе различны, то ФЛВ ( B C ) имеет значение 0 на рассматриваемом наборе и тогда импликация ( B C ) ( A A1 ) имеет значение 1. Если же значения B и C совпадают, то совпадают и значения формул A и A1, так как A1 отличается от A тем, что на некоторых местах вместо B содержится C. Таким образом, значения формул ( B C ) и ( A A1 ) есть 1, поэтому значение ( B C ) ( A A1 ) также есть 1. Лемма доказана.

–  –  –

Таблица 5 1 v 1 (v ) (v 1 ) v Итак, согласно табл. 5 эти составные высказывания при любых значениях v, и 1 принимают одинаковые значения (столбцы 5 и 6 совпадают). Следовательно, равносильность (1.8) верна.

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

Пример 1.10.

Выведем второй закон де Моргана из его первого.

В первый закон де Моргана вместо A подставляем ¬A, а вместо B ¬B. Получим ¬(¬A ¬B ) ¬¬A ¬¬B. Но согласно (1.11) имеем ¬¬A ¬¬B A B, а по транзитивности равносильностей – ¬( ¬A ¬B) A B. Тогда ¬¬( A ¬B ) ¬( A B ), и, устраняя двойное отрицание, получаем второй закон де Моргана.

Пример 1.11.

Выведем первый закон расщепления, используя очевидные равносильности A 1 A и 1 B ¬B. Имеем A A 1 A ( B ¬B ) A B A ¬B, где на последнем шаге применили дистрибутивность относительно.

Аналогично можно вывести второй закон расщепления, используя A A 0 и 0 B ¬B.

Если имеем A1 A2, A2 A3,..., Am 1 Am, то согласно транзитивA1 Am ; в таком случае ради простоты будем писать ности A1 A2,..., Am 1 Am.

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

Лемма 1.4 (о построении других равносильностей).

Пусть A B и C – произвольная ФЛВ, тогда ¬A ¬B, A C B C, C A C B, A C B C, C A C B, A C B C, C A C B, A C B C, C A C B.

Доказательство тривиально, потому что значения ФЛВ A, B и C на произвольном наборе значений их переменных будут такие:

значения A и B равны v, а значение C есть ; тогда значение каждой из доказываемых равносильностей, кроме первой, есть v или v, где – двухместная операция.

Лемма 1.5 (о замене переменной).

Пусть A B и C – произвольная ФЛВ, в которой выделено одно вхождение переменной xi.

Пусть C A (CB ) получается из C заменой этого вхождения xi на ФЛВ A( B ). Тогда C A = CB.

Доказательство. Пусть выполняются условия этой леммы, где A, B, C – некоторые ФЛВ. Доказательство приведем математической индукцией по числу n логических символов (операций) в ФЛВ C.

Базис n = 0 тривиален, так как в этом случае ФЛВ C совпадает с переменной xi и доказываемая равносильность есть A B, т. е.

условие.

Пусть лемма доказана для ФЛВ с числом логических символов, меньшим n, и пусть C – ФЛВ с ровно n логическими символами.

Тогда она имеет вид ¬D, или D F, или D F, или D F, или D F, причем в первом случае выделенное вхождение переменной xi содержится в D, а в остальных случаях – либо в D, либо в F, но не в D и F одновременно.

Рассмотрим, например, случай, когда C имеет вид D F, а выделенное вхождение x i содержится в F. Заменяя xi в этом вхождении в F на A и B, получим ФЛВ FA и FB соответственно. Тогда C A есть D FA, а CB – D FB. Так как в F логических символов меньше n, то индуктивному предположению FA FB. Теперь применим лемму 1.4 в случае C A C B, где C есть D, A есть FA и B есть FB, что даст C A CB. Остальные случаи рассматриваются аналогично. Лемма доказана.

Правило равносильных преобразований

Пусть C A – ФЛВ, в которой имеется вхождение ФЛВ A, а CB получается из C A заменой A в этом вхождении на B. Тогда если A B, то C A CB.

Это утверждение есть непосредственное следствие леммы 1.5.

В самом деле, возьмем некоторую переменную xi и из C A построим ФЛВ C заменой A на xi. Объявляя это вхождение xi в C выделенным, получим, что формулы C, A, B, C A и CB удовлетворяют условиям леммы 1.5. Следовательно, C A CB.

Пример 1.12.

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

Пример 1.13.

Пусть M – некоторое непустое множество и Yi (i 1) – его произвольные подмножества. Если b M, то каждое выражение b Yi есть высказывание.

Например, если M = {0,1, 2,3, 4}, Y1 = {0, 4}, Y2 = {1, 2,3}, Y3 = {1, 4}, то (3 Y1 ) = 0, а (3 Y2 ) = 1.

Условимся рассматривать ФЛВ в базисе {¬,, } от переменных p1, p2,..., pn,.... Пусть A – произвольная такая формула и b M.

Через A(b) обозначим высказывание, получаемое из A заменой каждой переменной pi на высказывание b Y1. Например, если A = p1 ¬( p2 p3 ), то A(b) = b Y1 ¬(b Y2 b Y3 ).

Наконец, через Z A обозначим выражение, получаемое из ФЛВ A путем замены каждого pi на Yi и символов ¬,, на символы,, операций дополнения (до множества M), пересечения, объединения соответственно. Очевидно, что Z A – некоторое подмножество множества M. Для предыдущего примера имеем Z A = Y1 (Y2 Y3 ) = {0, 4} ({1, 2,3} {1, 4}) = = {0, 4} {1, 2,3, 4} = {0, 4} {0} = {0}.

Теорема 1.2 (о ФЛВ и множествах).

Для каждой ФЛВ A рассматриваемого вида, каждого непустого множества M, некоторого его элемента b и произвольных его подмножеств Y1, Y2,… высказывание A(b) истинно тогда и только тогда, когда b Z A.

Доказательство приводится в [12, с. 16].

Сформулируем следующие следствия из этой теоремы:

1) если A, то Z A = M ;

2) если ¬A, то Z A = ;

3) если A B, то Z A = Z B.

Например, из первого закона де Моргана, который в этом рассмотрении следует записать ¬( p1 p2 ) ¬p1 ¬p2, получаем Y1 Y2 = Y1 Y2.

Таким образом, равносильности ФЛВ (считая, что A есть A 1) позволяют доказывать равенства множеств.

Пример 1.14.

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

Для обеспечения хорошей сортировки топлива было предъявлено дополнительное требование:

каждый раз в помещение склада впускается только один грузовик и открывается лишь одна шахта. Спрашивается, имеет ли этот механизм также следующее свойство: если не въехал в помещение склада грузовик с углем, то шахта для угля не откроется; а если не въехал грузовик с коксом, то не откроется шахта для кокса?

Решение. Запишем условия действия этого склада символически, употребляя буквы для простых высказываний и логические символы. Обозначим через v высказывание «грузовик с углем прибыл на склад», а через – аналогичное высказывание о грузовике с коксом;

через v1 – высказывание «шахта открыта для угля», а через 1 – аналогичное для кокса. Тогда условия запишутся так:

v v1, 1; (1) (v ) (v ) – (2) дизъюнкция выражает условие, что на складе находится не более одного грузовика;

(v1 1 ) (v1 1 ) – (3) дизъюнкция показывает, что всегда открыто не более одной шахты.

Поставленный в задаче вопрос запишется так:

v1 v1, 1. (4) Требуется выяснить, следует ли истинность высказываний (4) из истинности высказываний (1), (2), (3).

Используем равносильность (1.16), выражающую через ¬,,, заменив в ней A на v, а B – на. Получим v v v (знак между высказываниями показывает, что их значения совпадают), а так как, то имеем v v v.

Но согласно (2) получаем, что (v ) = 1, т. е. значения высказываний v и совпадают. Аналогично согласно (3) получим (v1 1 ) = 1, т. е. значения высказываний v1 и 1 также совпадают.

Следовательно, первое высказывание из (1) дает ( 1 ) = 1.

Далее, если значения v и совпадают, то совпадают и значения v и ; аналогично из совпадения значений v1 и 1. Отсюда и из второго высказывания из (1) получаем (v v1 ) = 1. Таким образом, мы имеем утвердительные ответы на вопросы задачи. (Здесь сознательно не применен метод, использованный в примере 1.8.) Упражнения

1. Вывести равносильность:

а) (1.12) из (1.13) (в примере 1.10 выведена (1.13) из (1.12));

б) (1.7) из (1.8);

в) (1.8) из (1.7) (в пунктах б) и в) применить метод, использованный в примере 1.10).

2. Пусть A есть ФЛВ в базисе {¬,, } (т. е. содержит только эти логические символы и переменные) и A получается из A заменой в A всюду на и обратно и каждой переменной ее отрицанием. Показать, что A ¬ A. Найти A для:

а) ( p q ) r ( s p s );

б) p q s q s.

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

4. Перед судом стоят три человека, из которых каждый может быть или туземцем, или колонистом. Судья знает, что туземцы всегда отвечают на вопросы правдиво, а колонисты всегда лгут. Однако судья не знает, кто из них туземец, а кто – колонист. Он спрашивает первого, но не понимает ответа. Поэтому он спрашивает второго, а потом третьего о том, что ответил первый. Второй говорит, что первый сказал, что он туземец. Третий говорит, что первый назвал себя колонистом. Кем были второй и третий подсудимые? (Указание: убедиться, что первый допрашиваемый был туземец.)

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

1.5. ДВОЙСТВЕННОСТЬ.

НОРМАЛЬНЫЕ ФОРМЫ

Сначала будем рассматривать ФЛВ только в базисе {¬,, }. На множестве таких ФЛВ введем бинарное отношение двойственности и покажем, как с его помощью можно доказывать равносильность ФЛВ.

ФЛВ A называется двойственной для ФЛВ A, если A получается из A заменой в ней всюду на и на.

Например, если A = ( p q) r, B = ¬(q r ) (q s ), то A = p q r, B = ¬(q r ) q s.

Заметим, что отношение двойственности симметрично.

Лемма 1.6. Пусть A( x1, x2, …, xn ) и A ( x1, x2, …, xn ) – двойственные ФЛВ. Тогда:

1) ¬ A( x1, x2, …, xn ) A ( x1, x2, …, xn );

2) A ( x1, x2, …, xn ) тогда и только тогда, когда ¬ A( x1, x2, …, xn ).

Утверждение 1) следует из законов де Моргана. Для доказательства утверждения 2) следует заметить, что A( x1, …, xn ) тогда и только тогда, когда A( x1, …, xn ), а затем использовать утверждение 1) этой леммы.

Лемма 1.7. Пусть A и B – ФЛВ в базисе {¬,, }. Тогда:

1) если A B, то B A ;

2) если A B, то A B, а значит, если A B, то A B (закон двойственности).

Сначала докажем утверждение 1). Пусть A и B – ФЛВ рассматриваемого вида и является тавтологией ФЛВ A B. Имеем A B ¬¬( A B) (по равносильности (1.17)) ¬¬(¬A B ).

Теперь по утверждению 1) леммы 1.6. из ¬¬(¬A B) следует (¬(¬A B )), т. е. ¬(¬A B ). Отсюда по первому закону де Моргана ¬B A и по равносильности (1.17) имеем B A.

Утверждение 2) этой леммы непосредственно следует из утверждения 1), равносильности (1.16) и того, что тавтологичность эквиваленции означает равносильность ее формул. Лемма доказана.

Например, согласно закону двойственности из одного закона де Моргана получаем другой, из одной дистрибутивности – другую и т. п.

Теперь начнем рассматривать ФЛВ в общем виде.

Если x – переменная и a есть 0 или 1, то через x a обозначим ФЛВ x a x a. Очевидна следующая лемма.

Лемма 1.8 (о формуле x a ).

ФЛВ x a имеет значение 1 тогда и только тогда, когда x = a.

–  –  –

которой называется совершенной дизъюнктивной нормальной формой (кратко СДНФ) ФЛВ A( x1, x2, …, xn ).

Пример 1.15.

Пусть (0,1,0), (1,0,1), (1,1,1) есть все наборы, на которых ФЛВ A( p, q, r ) равна 1. Тогда ее СДНФ есть

–  –  –

которой называется совершенной конъюнктивной нормальной формой (кратко СКНФ) ФЛВ A( x1, x2, …, xn ).

Пример 1.16.

Пусть (0,0,1), (1,1,0), (1,0,1), (1,1,0) есть все наборы, на которых ФЛВ B ( p, q, r ) равна 0. Тогда ее СКНФ суть

–  –  –

= ( p q r ) ( p q r ) ( p q r ) ( p q r ).

Из этих совершенных нормальных форм вытекает следующее следствие.

Следствие 1.3. Для любой ФЛВ существует ей равносильная ФЛВ в базисе {¬,, }, или, другими словами, система логических операций {¬,, } является полной.

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

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

Например, ДНФ являются x1x3, x2 x3 x1 x2, xn x1 x2 x4 x3 x4, а КНФ – x1 x3 x4, ( x1 x3 )( x2 x3 x4 ).

ДНФ, которая задает ФЛВ, неравносильную 0, можно преобразовать в СДНФ путем ввода недостающих переменных в элементарных конъюнкциях. Например, если в элементарной конъюнкции K нет переменной x, то ее ввод следующий: K K 1 K ( x x) Kx K x.

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

Например, если элементарная дизъюнкция D не содержит переменной x, то ее ввод следующий:

D D 0 D x x ( D x) ( D x).

Еще докажем, что система логических операций {¬, } также является полной.

Теорема 1.3 (об импликативном разложении по одной переменной).

Для любой ФЛВ A( x1, x2, …, xn ) имеет место равносильность

–  –  –

Доказательство. Пусть A( x1, x2, …, xn ) – некоторая ФЛВ. Убедимся, что доказываемая равносильность имеет место при x1 = 1 и x1 = 0.

При x1 = 1 в ее левой части получаем A(1, x2,..., xn ), а в правой –

–  –  –

б) ( p q ) ( p q r );

в) ( p q )( p r ) q r ;

г) ( p r )q ( p r q)(r s ).

2. Привести примеры четырех равносильностей (из числа перечисленных в п. 1.4.), справедливость которых можно доказать, используя закон двойственности.

3. Построить СДНФ, СКНФ и СИНФ для следующих ФЛВ:

а) p q q s;

б) ¬( p q ) p s;

в) p q q s;

г) ¬( ¬( p q) q r );

д) (¬p ¬q ) (q r );

е) ( p q) (q s r ).

4. Следующие ДНФ преобразовать в им равносильные СДНФ:

а) pq pqr pr ;

б) pqr pr q;

в) pq pqr qrs pqrs.

5. Следующие КНФ преобразовать в им равносильные СКНФ:

а) ( p q )(q r );

б) ( p r )(q s )(r s );

в) ( p q r )( p q )( p s );

г) ( p q r s )( p s )(q r )( p q ).

6. Пусть A есть ФЛВ в базисе {}. Доказать, что A является тавтологией тогда и только тогда, когда каждая переменная из A входит четное число раз. (Указание: ввести x y = ¬( x y ) и тогда ¬x x 1, x x 0, x 0 x.)

7. Пусть A есть ФЛВ в базисе {¬, }. Доказать, что A является тавтологией тогда и только тогда, когда каждая переменная и символ ¬ входят в нее четное число раз.

8. Доказать, что каждая из следующих систем логических операций: {¬, }, {¬, }, {/}, {}, где p / q = p q (штрих Шеффера), p q = p q (стрелка Пирса), является полной.

9. Доказать, что каждая из следующих систем логических операций: {, }, {, }, {¬, } не является полной.

1.6. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ Основным методом в математической логике является аксиоматический метод. Проиллюстрируем его на логике высказываний, получая исчисление высказываний (ИВ).

–  –  –

Упражнения

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

2. Построить соответствующие последовательности для каждого из следующих утверждений:

а) ¬¬A (¬¬A A) (Указание: в 2* заменить A на ¬A, B – на ¬¬¬B и использовать сначала аксиому (A3), а затем после МП – аксиому (A2).);

б) ¬¬A A (Указание: использовать предыдущее утверждение и аксиому (A2).);

в) A ¬¬A (Указание: использовать предыдущее утверждение при замене A на ¬A и аксиому (A3).);

г) A ( B B ) (Указание: использовать 1*.);

д) A ( B (C C ));

е) ( B C ) (( A B ) ( A C )) (Указание: использовать соответствующие аксиомы по (A1) и (A2), начиная с аксиомы ( B C ) ( A ( B C )).);

ж) ( A B ) (( B C ) ( A C )) (Указание: использовать предыдущее утверждение.).

3. Доказать: если A ( B C ), то B ( A C ) (Указание:

использовать аксиомы (A1) и (A2).).

1.6.2. Вывод из гипотез Обобщим понятие вывода: введем понятие «вывод из гипотез».

Пусть – некоторое конечное множество формул ИВ, возможно, пустое. Выводом формулы B из называется та же последовательность, что и в выводе формулы B с дополнительным условием:

наличие некоторой формулы в этой последовательности обосновывается ее принадлежностью к. В таком случае будем писать B или, если = { A1, A2, …, An }, то A1, A2, …, An B и формулы множества называть гипотезами.

Например, последовательность A B, A, B есть A B, A B, но не A B B. Из этого определения следует: B означает, что формула B выводима из пустого множества гипотез.

Установим несколько свойств вывода из гипотез. Пусть – любое конечное множество формул (возможно, пустое) и A, B, C, A1, A2, …, An – произвольные формулы.

Тогда имеют место следующие свойства:

1°., B B.

Требуемая последовательность есть B или B, B.

2°. Если B, то, A B.

Вывод B из гипотез есть одновременно и вывод ее из расширенного множества гипотез.

3°. Если, A, C B, то, C, A B.

В перечне гипотез их порядок роли не играет.

4°. Если, A, A B, то, A B.

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

5°. Если, A B и B, то B; в частности, если, A B и A, то B.

В самом деле, в последовательность формул, подтверждающую факт, A B, вместо вхождения A (если оно имеется) можно подставить соответствующую последовательность, имеющуюся по условию A (или A ).

6°. Если Ai для каждого i (1 i n) и A1, A2, …, An B, то B.

Если A1, A2, …, An B, то согласно свойству 2° будет, A1, A2, …, An B. Осталось использовать свойство 5°.

7°. Если A B, то, A B.

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

8°. Теорема дедукции. Если, A B, то A B.

Доказательство. Пусть выполняется условие этого свойства и последовательность B1, B2, …, Bi, …, Bm, (1.22) где Bm есть B, есть вывод B из гипотез, A. По этой последовательности построим последовательность A B1, A B2, …, A Bi, …, A Bm, (1.23) которую путем добавления конечного числа формул преобразуем в вывод A B из гипотез. Эти формулы будут последовательно вставляться перед каждой A Bi (1 i m) из последовательности (1.23) следующим образом. Если выполним все вставки, предшествующие A Bi, получим последовательность, которая, если ее рассматривать до A Bi, будет выводом A Bi из гипотез. Поэтому, выполнив все вставки, предшествующие A Bm, получим вывод ее из гипотез, т. е. A B.

Теперь рассмотрим формулу A Bi из последовательности (1.23) и при i 1 допустим, что все требуемые вставки перед формулой A Bi 1 уже выполнены. Формулы, которые вставляются перед A Bi, зависят от того, на основе чего Bi содержится в последовательности (1.22), т. е. Bi будет или 1) аксиомой, или 2) одной из формул, или 3) формулой A, или 4) непосредственным следствием из B j и Bk по МП, где j i и k i, а m 3.

Рассмотрим каждый из этих случаев.

1) Поскольку Bi есть аксиома, то перед A Bi вставим Bi и Bi ( A Bi ). Получим следующую последовательность, заканчивающуюся формулой A Bi :

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

2) В этом случае вставляем те же формулы, что и в 1), но наличие Bi в последовательности (1.24) объясняется тем, что она одна из формул системы.

3) Здесь A Bi есть A A и перед A Bi вставляем первые четыре формулы из вывода 1*.

4) В этом случае Bi есть непосредственное следствие по МП из формул B j и Bk, где j i и k i, значит, B j есть Bk Bi. Поскольку j i и k i, то вставки перед A B j (т. е. A ( Bk Bi )) и A Bk уже сделаны, т. е. имеем A ( Bk Bi ) и A Bk.

Перед A Bi вставляем следующие формулы:

( A ( Bk Bi )) (( A Bk ) ( A Bi )), ( A Bk ) ( A Bi ), первая из которых есть аксиома по (A2), а вторая – непосредственное следствие по МП из нее и A Bi. Теорема доказана.

Следствие 1.5 (обобщенная теорема дедукции)., A B тогда и только тогда, когда A B.

Из теоремы дедукции (ТД) получаем следствие.

Следствие 1.6. Если A1, A2, …, An ( n 1) и B – формулы ИВ и A1, A2, …, An B, то A1 ( A2 (...( An B )...)).

Следствие 1.6 устанавливает связь понятий «вывод» и «вывод из гипотез» и иногда помогает строить выводы формул по соответствующему выводу из гипотез.

Пример 1.17.

Вывод формулы A ( A (( A B) B )) согласно 3* имеет 15 формул, и их включение в эту последовательность требовало некоторых соображений. Но ее вывод можно построить чисто механически, если использовать ТД. В самом деле, имеем A, A B B, откуда по следствию 1.6 получаем A (( A B) B), вывод которой строится чисто механически, так как в доказательстве ТД вставки формул четко определены. Затем получим A A (( A B ) B), откуда A A ( A (( A B) B )), и снова вставки формул, согласно доказательству ТД, дадут требуемый вывод исходной формулы. Правда, этот путь построения выводов может дать весьма длинные последовательности. Например, для A ( B B ) существует вывод из семи формул, а построение для нее вывода, согласно доказательству ТД, дает последовательность из 15 формул. Иногда и поиск множества и формулы A из ТД довольно непростой.

Например, для доказательства:

(( A B ) A) A (теорема Пирса), используя ТД (для нее исходные гипотезы – это ( A B ) A, ¬( A B ), ¬A, A, ¬B ).

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

Введем логические связки, и, полагая:

A B означает ¬A B;

A B означает ¬( A ¬B);

A B означает ( A B ) ( B A) (заметим, что эти пары образуют равносильные формулы).

9°. A B, B C A C 1.

В самом деле, имеем A B, B C, A C, поскольку есть последовательность A B, B C, A, B, C, и осталось применить ТД.

Здесь мы продолжаем нумерацию выводимых формул и свойств выводов.

4*. A ¬A.

Действительно, учитывая наше определение, формула A ¬A есть ¬A ¬A, а это частный случай 1*.

10°. A A B и B A B (введение дизъюнкции, или – введ.).

Докажем только первое свойство. Заметим, что A B есть ¬A B, и следовательно, требуется доказать: A ¬A B, что следует из 2*, 7°, 3° и ТД.

11°. A ¬¬A (введение двойного отрицания, или ¬¬ – введ.).

Необходимо доказать, что A ¬¬A (это несложно), и применить 7°.

12°. ¬¬A A (удаление двойного отрицания, или ¬¬ – удал.).

Это утверждение следует из того, что ¬¬A A, и свойства 7°.

13°. A, B A B.

14°. ¬A, A B.

15°. A, ¬B ¬( A B ) (вытекает из очевидных утверждений:

A, ¬B, A B ¬B и A, ¬B, A B B и свойства ¬ – введ. (см.

упражнение 5.6 к этому пункту)).

–  –  –

Упражнения

1. Доказать, что в ИВ не все его формулы выводимы.

2. Исчисление высказываний называется непротиворечивым в смысле Поста, если никакая переменная не является выводимой. Доказать, что ИВ непротиворечиво в смысле Поста.

3. Доказать, что не будет полным исчисление, получаемое из рассмотренного ИВ путем удаления: а) аксиомы (A2); б) аксиомы (A3).

1.7. ЛОГИКА ПРЕДИКАТОВ Язык логики высказываний – самый простой язык. Он не является достаточным для математики. Например, в рамках логики высказываний мы не сможем сделать вывод о логической истинности следующего простого рассуждения: «Каждое натуральное число и непосредственно следующее за ним (в натуральном ряду) являются корнями соответствующего квадратного уравнения. Число 5 – натуральное. Следовательно, 5 и его непосредственный последователь (т. е. 6) являются корнями соответствующего квадратного уравнения».

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

1.7.1. Предикаты Рассмотрим повествовательное предложение, содержащее параметр x: «x есть простое число». Вместо буквы (переменной) x будем подставлять натуральные числа больше 1: а) 2 есть простое число; б) 3 есть простое число; в) 4 есть простое число и т. д. Итак, согласно этим примерам получаем высказывания: в случаях а) и б) со значением 1 («истина»), в случае в) – со значением 0 («ложь») и т. д.

Так как высказывания мы отождествляем с их значениями, то можно сказать, что данное предложение задает функцию, значениями аргумента которой являются натуральные числа, а значениями функции – 0 и 1. Если эту функцию обозначить через R ( x), то ее можно задать равенством R ( x) = (x есть простое число).

Функция R( x) есть одноместный предикат, который при x = 0 и x = 1 не определен.

Общее определение предиката следующее: предикатом называется функция, аргументы которой принимают значения из некоторого множества, а сама функция – значения 0 («ложь») или 1 («истина»).

Предикат называется n-местным ( n = 1, 2,... ), если соответствующая функция есть функция от n аргументов. Часто одноместный предикат называют свойством. Например, S (n) = (для некоторого натурального числа k выполнено n = 2k ) – свойство четности натуральных чисел.

В дальнейшем условимся рассматривать только всюду определенные предикаты. Если дан такой предикат R ( x1, x2,..., xn ) (или R ( x n )), аргументы которого принимают значения из некоторого множества M, то будем говорить, что дан предикат R ( x n ) на множестве M (зависящий от переменных x1, x2,..., xn ). Если при xi = ai (1 i n), где ai из M, R (a1, a2,..., an ) = 1 (соответственно R (a1, a2,..., an ) = 0), то будем говорить, что набор или точка (a1, a2,..., an ) удовлетворяет (соответственно не удовлетворяет) этому предикату.

Пусть R ( x n ) – произвольный предикат на некотором множестве M. Этот предикат называется тождественно-истинным (тождественно-ложным), если любой набор значений переменных ему удовлетворяет (не удовлетворяет); выполнимым, если существует хотя бы один набор значений переменных, который ему удовлетворяет.

Ясно, что каждый тождественно-истинный предикат является выполнимым, а тождественно-ложный не является.

Пусть R ( x n ) и S ( x n ) – два предиката (от одних и тех же переменных), заданные на одном и том же множестве. Предикат S ( x n ) называется следствием предиката R ( x n ), если любой набор, который удовлетворяет R ( x n ), удовлетворяет и S ( x n ).

Например, если R ( x 2 ) = ( x1 x2 5) и S ( x 2 ) = ( x1 x2 5) – два, то S ( x 2 ) есть следствие R ( x 2 ).

предиката на Два предиката R ( x n ) и S ( x n ) на одном и том же множестве (от одних и тех же переменных) называются равносильными, если их значения на любом наборе значений переменных совпадают; в этом случае будем писать R ( x n ) S ( x n ) (читается: «R ( x n ) равносильно S ( x n )»).

Справедливо следующее очевидное утверждение.

Теорема 1.6 (о равносильных предикатах).

Два предиката R ( x n ) и S ( x n ), заданные на одном и том же множестве, являются равносильными тогда и только тогда, когда каждый из них есть следствие другого.

Упражнения

1. Придумать по два предиката разной местности на множестве на каждый из трех типов.

2. Привести примеры предикатов на таких, что:

а) R ( x ) не тождественно-истинный, а R ( x1,5) тождественноистинный;

б) S ( x3 ) и S ( x1, x2,7) выполнимые, а S ( x1, x2,7) не тождественно-истинный;

в) T ( x 2 ) выполнимый, а T ( x1,3) тождественно-ложный.

3. Привести два примера n-местных предикатов на, только один из которых есть следствие другого.

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

Пример 1.18.

Пусть R ( x) = ( x 1), Q( x, y ) = ( x y ), S ( x, y ) = ( xy 0) – предикаты на множестве. Тогда ¬ R ( x) = ¬( x 1) или ¬ R( x) = = ¬( x 1) – одноместный предикат, являющийся отрицанием предиката R ( x); каждый из предикатов Q ( x, y ) S ( x, y ), Q( x, y ) S ( x, y ), R ( x) Q ( x, y ), Q ( x, y ) S ( x, y ) является двухместным.

Например, R (3) Q(3,1) = 1 0 = 0, а Q (2, 4) S (2, 4) = 1 1 = 1.

Заметим, что предикат T ( x, y ) = (Q ( x, y ) Q ( y, x) Q( x, x)) является тождественно-истинным.

Сформулируем простейшие свойства этих операций.

Теорема 1.7 (об отрицании предиката).

Предикат ¬ R( x n ) на множестве M является тождественно-истинным тогда и только тогда, когда предикат R ( x n ) на множестве M тождественно-ложный.

Теорема 1.8 (о конъюнкции предикатов).

Предикат R ( x n ) Q( x n ) на множестве M является тождественно-истинным тогда и только тогда, когда оба эти предиката на M тождественно-истинны.

Теорема 1.9 (о дизъюнкции предикатов).

Предикат R ( x n ) Q( x n ) на множестве M является тождественно-ложным тогда и только тогда, когда оба эти предиката на M тождественно-ложны.

Теорема 1.10 (о тождественной ложности импликации предикатов).

Предикат R ( x n ) Q ( x n ) на множестве M является тождественно-ложным тогда и только тогда, когда R ( x n ) тождественноистинный, а Q ( x n ) тождественно-ложный предикаты на M.

Теорема 1.11 (о тождественной истинности импликации предикатов).

Предикат R ( x n ) Q ( x n ) на множестве M является тождественно-истинным тогда и только тогда, когда Q ( x n ) есть следствие R ( x n ).

Теорема 1.12 (об эквиваленции предикатов).

Предикат R ( x n ) Q ( x n ) на множестве M является тождественно-истинным тогда и только тогда, когда эти предикаты равносильны.

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

Операция применения квантора общности Пусть R ( x n ) – некоторый n-местный предикат на множестве

M (n 1). Результатом применения к нему квантора xi (1 i n) называется (n – 1)-местный предикат, обозначаемый xi R ( x n ) (читается:

«для каждого xi R ( x n )»), на множестве M, зависящий от переменных x1, …, xi 1, xi +1, …, xn, значение которого на данном наборе (a1, …, ai 1, ai +1, …, an ) значений этих переменных равно 1 тогда и только тогда, когда одноместный предикат R (a1, …, ai 1, xi, ai +1, …, an ) является тождественно-истинным.

Отметим, что если R ( x1 ) – одноместный предикат на M, то x1R ( x1 ) есть нульместный предикат, т. е. высказывание, которое называют универсальным высказыванием, соответствующим предикату R ( x1 ). Из этого определения следует, что универсальное высказывание истинно тогда и только тогда, когда соответствующий предикат тождественно-истинный.

Операция применения квантора существования Пусть R ( x n ) – некоторый n-местный предикат на множестве M (n 1). Результатом применения к нему квантора xi (1 i n) называется (n – 1)-местный предикат, обозначаемый xi R( x n ) (читается: «существует xi, что R ( x n )»), на множестве M, зависящий от переменных x1, …, xi 1, xi +1, …, xn, значение которого на данном наборе (a1, …, ai 1, ai +1, …, an ) значений этих переменных равно 0 тогда и только тогда, когда одноместный предикат R (a1, …, ai 1, xi, ai +1, …, an ) является тождественно-ложным.

Отметим, что если R ( x1 ) – одноместный предикат на M, то x1R( x1 ) есть нульместный предикат, т. е. высказывание, которое называют экзистенциональным высказыванием, соответствующим предикату R ( x1 ). Из этого определения следует, что экзистенциональное высказывание ложно тогда и только тогда, когда соответствующий предикат тождественно-ложный.

Подчеркнем, что предикаты xi R ( x n ) и xi R ( x n ) не зависят от переменной xi, т. е. при получении каких-либо их значений вместо xi никакое значение не подставляется. Такая переменная называется

–  –  –

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

Высказывание «от перестановки слагаемых сумма не меняется»

в логике высказываний символически запишется как ¬v, а в логике предикатов как xyz ( z = x + y z = y + x).

Высказывание «последовательность x1, x2,..., xn,... имеет предел a» (простое в логике высказываний) на языке предикатов запишется ( 0 N n(n N | xn a| )).

Утверждение о непрерывности функции f ( x) в точке x0 запишется ( 0 ( 0 x(| x x0 | | f ( x) f ( x0 )| ))).

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

введем одноместный предикат Q ( x) = (x есть действительное число) и двухместные предикаты x = y и x y. Теперь это высказывание запишется так: xy (Q ( x) Q ( y ) ( x = y ) ( x y ) ( y x)).

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

Упражнения

1. Доказать теоремы 1.6–1.14 и равносильности (1.28) и (1.29).

2. Придумать два предиката R ( x 2 ) и Q ( x 2 ) на множестве таких, что предикат:

а) R ( x 2 ) Q( x 2 ) тождественно-ложный, но каждый из предикатов R ( x 2 ) и Q ( x 2 ) не является тождественно-ложным;

б) R ( x 2 ) Q( x 2 ) тождественно-истинный, но каждый из предикатов R ( x 2 ) и Q ( x 2 ) не является тождественно-истинным;

в) R ( x 2 ) Q( x 2 ) тождественно-ложный и один из предикатов R ( x 2 ) и Q ( x 2 ) есть отрицание другого.

3. Даны некоторые предикаты R ( x 2 ) и Q ( x 2 ) на множестве {a, b, c}. Для следующих предикатов найти им равносильные, не содержащие кванторов:

а) x1R ( x 2 ) x2Q( x 2 );

б) x1R ( x 2 ) x2Q( x 2 );

в) x1x2 ( R ( x 2 ) Q( x 2 ));

г) x1x2 R( x 2 ) x2Q ( x 2 );

д) x1x2 R( x 2 ) x2x1R( x 2 );

е) x1x2 R( x 2 ) x2x1R ( x 2 ).

4. Найти значение высказывания xy ( x y ), где предикат x y на множестве: 1) натуральных чисел; 2) целых чисел, и значения следующих высказываний, образованных из предикатов на множестве целых чисел:

а) xy ( x + y = 5);

б) xyz ( xy = z );

в) xy ( xy = x);

г) xyz ( xz = y );

д) xyz ( xyz = y z );

е) xyz ( xz = y );

ж) xyz (( xz = y ) ( yz = x)).

5. Записать на языке предикатов следующие высказывания:

а) каждое положительное действительное число является квадратом другого;

б) натуральное число, которое делится на 9, разделится на 3;

в) две прямые, параллельные третьей, параллельны между собой;

г) если две прямые на плоскости не параллельны, то они имеют общую точку, притом только одну;

д) через две различные точки плоскости проходит прямая, и только одна;

е) каждый предикат является тождественно-ложным или выполнимым;

ж) над одним предикатом может быть выполнена только одна из операций:,, ¬ ;

з) над некоторым предикатом некоторые операции дают высказывания.

1.7.3. Формулы логики предикатов.

Интерпретации

Алфавит формул логики предикатов (ФЛП) следующий:

1) символы предметных переменных: x, y, z, x1, y1, z1, x2,...;

2) предикатные буквы (символы): Pjn (n, j 1);

3) предметные константы: a1, a2,..., an,...;

4) функциональные буквы (символы): fi k (k, i 1);

5) символы логических операций: ¬,,,,,, ;

6) скобки и запятая: ), (.

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

Индуктивное определение терма

1. Каждая переменная и каждая константа есть терм.

2. Если fi n – функциональная буква и t1, t2,..., tn – термы, то fi n (t1, t2,..., tn ) есть терм.

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

Например, термами являются x, y, z, x 1, x2, x3, a1, a2, f11 (a1 ), f 2 ( x1 ),

f31 ( x2 ), f12 ( x1, a2 ), f 22 ( f 2 ( x1 ); f12 ( x1, a2 )), f13 ( x1, x1, x1 ) и др.

Индуктивное определение ФЛП (с одновременным определением свободных связанных переменных)

1. Если Pi n – предикатная буква и t1, t2,..., tn – необязательно различные термы, то Pi n (t1, t2,..., tn ) – ФЛП, которая называется атомарной (или простой). В атомарной ФЛП все переменные свободные, связанных нет.

2. Если A – ФЛП, то (¬A) – также ФЛП. Свободные и связанные переменные формулы (¬A) совпадают со свободными и связанными переменными формулы A соответственно.

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

4. Пусть A – ФЛП, которая содержит свободную переменную u.

Тогда (uA), (uA) (1.30) также ФЛП. Переменная u в них связанная. Остальные переменные, которые в формуле A свободные (связанные), являются свободными (связанными) и в формулах из (1.30), в которых ФЛП A назовем областью действия кванторов.

Определение закончено. Так, определенные ФЛП называются предикатными формулами в сигнатуре {Pjn n, j 1} { fi m m, i 1} {ai i 1}.

Сохраним вышепринятое соглашение об опускании скобок в ФЛП и дополним его еще одним: кванторы связывают сильнее, чем другие операции. Например, вместо ((xP1 ( x)) P 2 ( y, z )) и y ((xP 2 ( y, x)) (xP22 ( x, y ))) будем писать xP1 ( x) P 2 ( y, z ) и y (xP 2 ( y, x) xP22 ( x, y )) соответственно.

Еще согласимся вместо (Q1u1 (Q2u2 (...(Q n un A)...))), где Qi – кванторы, писать Q1u1Q2u2...Qnun A.

Например, вместо (x(y (zP 3 ( x, y, z )))) пишем xyzP3 ( x, y, z ).

ФЛП, которая не содержит свободных переменных, называется замкнутой.

Например, такие формулы, как вышеприведенная и следующая x( P1 ( x) yP 2 ( x, y )) замкнуты, но не x( P22 ( x, y1 ) yP 2 ( x, y )).

ФЛП имеет значение только тогда, когда мы придадим некоторый смысл всем символам (другими словами, проинтерпретируем все символы), которые она содержит. (Интерпретация – толкование, объяснение, раскрытие смысла чего-л.2) Под интерпретацией понимается пара I = M,, где M – непустое множество (называемое областью интерпретации), а – отображение. Это отображение каждому предикатному символу Pi n сопоставляет некоторый предикат Si : M n {0,1} (т. е. ( Pi n ) = Si ), каждому функциональному символу fi K сопоставляет некоторую функцию Fi : M K M (т. е.

( fi K ) = Fi ) и каждой предметной константе ai – некоторый элемент (ai ) из множества M.

При данной интерпретации каждая ФЛП после указанного в ней сопоставления и того, что символы ¬,,,, и кванторы обозначают определенные выше операции над предикатами (это также элемент интерпретации), превратится в соответствующий предикат, Словарь русского языка: в 4 т. / АН СССР, Ин-т рус. яз.; под ред.

А. П. Евгеньевой. 2-е изд., испр. и доп. М., 1981–1984. Т. 1. С. 673.

где переменные пробегают множества M. Поэтому при каждой интерпретации замкнутая ФЛП даст высказывание, а ФЛП со свободными переменными – некоторый предикат на множестве M.

Пример 1.20. Рассмотрим следующие ФЛП:

1) P 2 ( x, a1 ); 3) x P 2 ( x, y );

–  –  –

3. Условимся рассматривать ФЛП в следующей сигнатуре: {P 3, P23}.

Пусть имеется следующая их интерпретация:

I1 =,, где ( P3 ) = ( x + y = z ), ( P23 ) = ( x y = z ). Написать соответствующие

ФЛП, которые в I1 имеют значение 1 тогда и только тогда, когда:

а) x = 0; б) x = 1; в) x = 2; г) x – четное число; д) x – простое число;

е) x y; ж) x = y; з) x делит y. (Ответы приводятся в [9, с. 64].) 1.7.4. Равносильность предикатных формул.

Основные равносильности Пусть ФЛП F и G имеют одно и то же множество свободных переменных.

Тогда F и G называются:

1) равносильными в данной интерпретации, если в этой интерпретации они представляют равносильные предикаты;

2) равносильными на множестве M, если они равносильны во всех интерпретациях с областью M (в этом случае пишем F M G;

читается: «F равносильна на M G»);

3) равносильными (в логике предикатов), если они равносильны на всех множествах (в этом случае пишем F G ).

Например, легко убедиться, что xP1 ( x) M1 xP1 ( x) при M1 = {a} и xP1 ( x) M 2 xP1 ( x), если M 2 = {a, b}. В самом деле, данная равносильность вытекает из того, что на одноэлементном множестве M1 каждый предикат есть тождественно-истинный либо тождественно-ложный.

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

1. Каждая равносильность формул логики высказываний определяет соответствующую равносильность ФЛП. Определяет в том смысле, что если в ФЛВ из данной равносильности все вхождения переменных заменить на ФЛП, причем каждое вхождение одной и той же переменной заменить на одну и ту же ФЛП, то получим равносильность предикатных формул (если замена удовлетворяет определению формулы).

Например, из равносильности p (q r ) p q p r формул логики высказываний согласно утверждению 1 получаем F (G H ) F G F H равносильность логики предикатов (когда F (G H ) есть ФЛП), где F, G и H – произвольные предикатные формулы.

Доказательство утверждения 1 очевидно.

2. Переименование связанных переменных. Заменяя связанную переменную u формулы F другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получаем формулу, равносильную F, т. е. uA(u ) A() и uA(u ) A(), что легко проверить.

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

В данной интерпретации значение ФЛП F на наборе (a1, a2,..., an ) своих свободных переменных u1, u2,..., un будем обозначать выражением F ( a1, a2,..., an ).

–  –  –

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

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

Например, приведенными формулами являются:

P1 ( x) P 2 ( x, y ), ¬ P1 ( x) y P 2 ( x, y ), y¬P 3 ( x, x, y ) yP 2 ( y, x),

–  –  –

Приведенная формула, которая равносильна данной ФЛП, называется приведенной формой данной ФЛП.

Теорема 1.15 (о приведенной форме).

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

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

Пример 1.21.

Построить приведенную форму для ФЛП

–  –  –

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

Например, нормальную форму имеют следующие ФЛП:

–  –  –

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

Теорема 1.16 (о нормальной форме).

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

Пример 1.22.

Для формулы y¬ P 2 ( x, y ) yP22 ( x, y ) ее нормальную форму можно получить по равносильности (1.39), что дает y (¬ P 2 ( x, y ) P22 ( x, y )). Но можно поступить и по-другому.

Равносильность (1.35) сразу применить нельзя, поскольку B содержит переменную y. В таком случае сначала переименуем одну связанную переменную, а затем вынесем кванторы, что даст y¬ P 2 ( x, y ) yP22 ( x, y ) y¬ P 2 ( x, y ) zP22 ( x, z )

–  –  –

универсального высказывания следует, что для каждого j (1 j n) выполнено следующее: если R j (a j ) = 1, то Ri ( a j ) = 0 для всех i j, т. е. если какой-то из рассматриваемых предикатов в данной точке имеет значение 1, то все другие предикаты в этой же точке должны принимать значение 0. Поскольку каждый из этих предикатов выполнимый, то M n для получения истинного высказывания. Следовательно, ФЛП Fn не выполнима в каждой интерпретации J1 = M1,, если M 1 n 1. Тогда ФЛП H n = ¬Fn является искомой (n 2).

Пример 1.25. Докажем, что следующая предикатная формула:

G =xyz ( P 2 ( x, x) ( P 2 ( x, z ) P 2 ( x, y ) P 2 ( y, z ))) yzP 2 ( y, z ) –

–  –  –

Из равенств (1.57) и (1.58) следует, что i (a ) i +1 (a).

Поскольку в (1.56) a, b и c – произвольные элементы из M, то пусть a = c = i (a ), b = i +1 ( a) и получим ( R (i (a ), i ( a)) R(i (a), i +1 (a)) R (i +1 ( a), i (a ))) = 1.

Отсюда согласно (1.57) и (1.58) имеем R (i +1 ( a ), i (a )) = 1, и поскольку i – произвольное число, то R (i + 2 (a ), i +1 (a )) = 1, а из этого равенства с учетом (1.58) следует i (a) i + 2 (a ). Если предположить, что уже доказано i (a) i + K ( a) при K 1 и R (i + K (a ), i +1 (a )) = 1, тогда из (1.56) получаем (при a = i + K (a ), c = i +1 (a ), b = i + K +1 (a)) i (a) i + K +1 (a).

Следовательно, множество M бесконечное.

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

Теорема 1.17 (теорема Чёрча).

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

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

Другой класс предикатных формул, для которых проблема разрешения имеет решение, составляют формулы, построенные только из одноместных предикатных символов. Оказывается, для общезначимости такой формулы достаточно убедиться в ее истинности в каждой интерпретации, где мощность области интерпретации ограничена [9, с. 76].

–  –  –

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

Аксиомы исчисления предикатов Каковы бы ни были формулы логики предикатов A, B и C, следующие выражения, если они удовлетворяют определению ФЛП, являются аксиомами:

(А1) A ( B A);

(А2) ( A ( B A)) (( A B ) ( A C ));

(А3) (¬ A ¬ B ) ( B A), а также следующие два:

(А4) u A(u ) A(t ), где A(u ) – ФЛП, содержащая переменную u свободно, и A(u ) не содержит переменной t, а A(t ) получается подстановкой t вместо всех свободных вхождений u в A(u ) (на самом деле, t может удовлетворять более общему условию, чем быть переменной);

(А5) A(t ) u A(u ), где A(u ) и A(t ) те же, что и в аксиоме (А4).

Заметим, что аксиомы (А1)–(А3) являются обобщениями соответствующих аксиом исчисления высказываний.

Правилами вывода в исчислении предикатов являются:

1) модус поненс: из A B и A следует B (то же, что и в исчислении высказываний);

2) правило связывания квантором общности: из B A(u ) следует B uA(u ), если B не содержит переменной u;

3) правило связывания квантором существования: из A(u ) B следует u A(u ) B, если B не содержит переменной u;

4) правило переименования связанной переменной: связанную переменную формулы A можно заменить (во всех ее вхождениях) на другую переменную, не являющуюся свободной в A (но чтобы полученное выражение оказалось формулой; например, из xyA( x, y ) нельзя получить xx A( x, x)).

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

Основными теоремами исчисления предикатов являются следующие.

Теорема 1.18 (о выводимой формуле).

Каждая выводимая в исчислении предикатов формула общезначима.

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

1.11 и 1.12, и правила вывода, примененные к общезначимым формулам, дают общезначимые).

Согласно этой теореме невозможно вывести одновременно A и ¬ A. Поэтому верно следующее.

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

Теорема исчисления предикатов с самым сложным доказательством – это теорема Гёделя о полноте.

Теорема 1.19 (теорема Гёделя о полноте).

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

Теорема Гёделя о полноте подчеркивает важность аксиоматического метода в математике (учитывая теорему Чёрча о неразрешимости проблемы общезначимости).

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

Теорема 1.20 (теорема Гёделя о неполноте).

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

–  –  –

2.2. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ.

БИНАРНЫЕ ОТНОШЕНИЯ. ФУНКЦИИ

Упорядоченная пара (или набор длины 2) из элементов a и b, взятых именно в этом порядке, обозначается (a, b) и полагается (a, b) = { a},{a, b} { }.

Из этого определения вытекает, что (a, b) = (c, d ) тогда и только тогда, когда (a = c) и (b = d ).

Пусть уже определено понятие набора длины n: (a1, a2,..., an ) (или a1, a2,..., an ), n 2. Тогда набор длины n + 1 из элементов a1, a2,..., an, an +1, взятых именно в этом порядке, обозначается a1, a2,..., an, an +1, и полагается

–  –  –

Доказательство индукцией по n. При n = 2 легко проверить, что A1 A2 = A1 A2 = Ai. Предположив, что утверждение верно при i =1 n, в индуктивном переходе используется равенство (a1, a2,..., an, an +1 ) = ((a1, a2,..., an ), an +1 ).

Пример 2.9.

Доказать, что для любых множеств A, B и C верно равенство ( A \ B ) C = ( A C ) \ ( B C ).

Докажем только одно включение, а именно, что правая часть равенства включена в левую.

Пусть (m, n) (( A C ) \ ( B C )). Тогда (m, n) A C и (m, n) B C, откуда m A, n C, а m B. Следовательно, m A \ B и, значит, (m, n) ( A \ B) C. Итак, доказано ( A C ) \ ( B C ) ( A \ B) C.

Пример 2.10.

Пусть A, B и ( A B ) ( B A) = C D. Доказать, что A = B = C = D.

Пусть выполняются три этих условия, и допустим, что A B.

Тогда, не умаляя общности, можно считать, что найдется элемент m, который из A, но не из B. Поэтому множество A B содержит пары (m, x), где x m, а B A – пары ( y, m), где y m. Эти множества не пусты из-за первых двух условий. Значит, пара (m, n) ( A B ) ( B A). Но из третьего условия следует, что пары (m, x) и ( y, m) принадлежат C D, а значит, m C и m D; откуда (m, m) C D. Получаем противоречие с третьим условием. Следовательно, A = B. Тогда ( A B ) ( B A) = A A и по третьему условию A A = C D. Поэтому C = D = A.

Любое подмножество множества M n называется n-местным отношением, где M – произвольное множество, n 1.

Бинарным называется 2-местное отношение. Если – n-местное отношение, то через M обозначим множество, состоящее только из всех компонент всех наборов из, и его будем называть областью задания отношения. Еще будем говорить, что является n-местным отношением в множестве M, если M M. Если – бинарное отношение в множестве M и множество из всех первых компонент из всех пар из есть M, то будем говорить, что есть бинарное отношение на M. Например, если = {(1,1),(1,0),(2, 2)}, то M = {0,1, 2}, но не является бинарным отношением на M ; если же =, то M = и является бинарным отношением на.

Если – бинарное отношение, то вместо (a, b) часто пишут ab.

Бинарное отношение на множестве M называется:

1) тождественным, если = {(a, a ) a M };

2) полным, если = M 2 ;

3) пустым, если = ;

4) рефлексивным, если для каждого a из M выполнено aa;

5) антирефлексивным, если для каждого a из M выполнено (a, a) ;

6) симметричным, если из ab следует ba;

7) антисимметричным, если при a b из a b следует (b, a) ;

8) транзитивным, если из a b и b c следует a c;

9) связанным, если для любых неравных a и b из M выполнено a b или b c.

Пример 2.11.

Какими свойствами обладает конечное отношение = {(1, 2,(2,1),(1,1),(2, 2),(3,3)}? Его область задания M = {1, 2,3}, и оно является отношением на этом множестве.

Отношение является:

1) нетождественным, так как 1 2;

2) неполным, так как (1,3) ;

3) непустым;

4) рефлексивным, так как 11, 2 2, 33;

5) не антирефлексивным;

6) симметричным;

7) не антисимметричным;

8) транзитивным;

9) несвязанным, так как (1,3) и (3,1).

Пример 2.12.

Какими свойствами обладает (бесконечное) отношение = {(a, b) a b }?

Сначала найдем область задания. Ясно, что M. Теперь возьмем любое рациональное число p из. Имеем p p = 0 и 0, следовательно, pp. Значит, p M, поэтому M. Итак, M = и – бинарное отношение на, так как первые компоненты его пар составляют множество.

Отношение является:

1) нетождественным, так как 3 4;

2) неполным, так как, ;

3) непустым;

выполнено pp;

4) рефлексивным, так как для любого p из

5) не антирефлексивным;

6) симметричным, так как ab означает, что a b есть целое число, но тогда число b a также целое, поэтому ba;

7) не антисимметричным;

8) транзитивны, так как из ab и bc следует ac; в самом деле, посылки означают a b и b c – целые числа, но тогда их сумма, равная a c, – также целое число;

9) несвязанным, так как, и,.

Пример 2.13.

Какими свойствами обладает (бесконечное) отношение = {( x, y ) 2 y 0}?

x Снова очевидно, что M. Проверим, будет ли произвольное действительное число x компонентой некоторой пары из. Если x 0, то x x 0 и, значит, xx; число нуль не будет компонентой никакой пары из. Следовательно, M = \{0} и является отношением на M.

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

Отношение рефлексивно, так как для любого ненулевого действительного числа x выполнено x x 0; оно также симметрично из-за коммутативности операции умножения. Теперь о транзитивности. Пусть ab и bc, значит, ab 0 и bc 0; откуда следует, что числа a, b и c одного знака. Следовательно, ac 0 и транзитивно.

Пусть бинарное отношение является одновременно рефлексивным и транзитивным. Если оно еще симметричное, то называется отношением эквивалентности; а если же оно антисимметричное, то называется частичным порядком на M, а само множество M – частично упорядоченным (этим отношением ).

Например, отношения в примерах 2.12 и 2.13 являются отношениями эквивалентности, а отношения {( x, y )M 2 x y}, где M {,,, }, являются частичными порядками, значит, множества,, и частично упорядочены отношением «меньше».

Частичный порядок на M, в котором два любых элемента сравнимы, называется линейным. Частичные порядки «меньше» – линейные.

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

Пример 2.14.

Для любого непустого множества X определим бинарное отношение ( X ) = {( A, B ) A P ( X ) B P ( X ) ( A B )}, т. е.

( X ) состоит из всех тех и только тех пар ( A, B), что A B, а A и B являются подмножествами X. Имеем ({0,1}) = {(, ),(,{0}),(,{1}),(,{0,1}), ({0},{0,1}),({1},{0,1}),({0,1},{0,1})}.

Отношение ( x) рефлексивно и транзитивно согласно свойствам (2.2) и (2.3). Убедимся, что ( X ) антисимметрично. Пусть A B и ( A, B) ( x), т. е. A B, но в этом случае A B, поэтому B не будет подмножеством A и, значит, ( B, A) ( X ). Если же | X | 2, то ( X ) не будет линейным.

Установим связь между отношениями эквивалентности на множестве M и его разбиениями. А именно, если R – разбиение множества M, то отношение R, состоящее только из всех пар ( x, y ) таких, что найдется класс Bi из R, который содержит элементы и y, есть отношение эквивалентности. Кроме того, если R1 и R2 – различные разбиения, то R1 R2. Например, если M = {0,1, 2} и R1 = {{0,1},{2}}, а R2 = {{0},{1, 2}}, то R1 = {(0,0),(0,1),(1,0),(1,1),(2, 2)}, R2 = {(0,0),(1,1),(1, 2),(2,1),(2, 2)}.

Обратно, пусть – отношение эквивалентности на непустом множестве M. Для каждого a из M построим множество a = = {x M (a, x) } – класс эквивалентности отношения, порожденный элементом a.

Пример 2.15.

Если – отношение эквивалентности и a b, то a = b ; если же (a, b), то a b =.

Для доказательства равенства классов используем свойство (2.5).

Пусть m a, т. е. верно am. По симметричности получаем

ba, а по транзитивности – ba, т. е. m b. Значит, доказано:

a b. Обратное включение доказывается аналогично.

Осталось доказать пустоту пересечения, если (a, b). Допустим противное, т. е. найдется m такое, что m a b. Отсюда m a и m b, значит, am и bm и, используя симметричность и транзитивность, получаем ab. Противоречие.

Можно убедиться, что система S = {a a M } есть разбиение множества M и s =. Например, для отношения из примера

2.13 имеются только два различных класса эквивалентности среди множеств a ; а именно, 5 = {x 5 x 0} – множество всех положительных действительных чисел и 4 = {x (4) x 0} – множество всех отрицательных действительных чисел. Ясно, что система S = {5, 4 } есть разбиение M и S =.

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

Если f – функция, то множество D f всех ее первых компонент всех пар называется ее областью определения, а множество R f всех ее вторых компонент всех пар – областью значений.

Например, функциями являются y = x 2 + 1}, {(1,1),(2,3),(3, 2)}, {( x, y ) {(( x, y ), z ) z = 2 x + 5 y}, но не {(1,1),(1,3),(3, 2)}, {( x, y ) | x| = | y|}.

–  –  –

3.1. ОСНОВНЫЕ ПОНЯТИЯ Здесь конечные множества символов называются алфавитами, а их элементы – буквами. Конечная последовательность букв (из данного алфавита) называется словом (в данном алфавите). Пустое слово обозначается через (читается: «ламбда»). Множество всех слов в алфавите A обозначается через A (включая пустое слово), а A+ есть A без.

Определение 3.1. Порождающей грамматикой (или -грамматикой) называется упорядоченная четверка = V,W, J, R, где V и W – непересекающиеся непустые конечные алфавиты, причем V (W ) – алфавит основных (вспомогательных) символов, J – начальный символ и J из W, а R – конечное (непустое) множество слов вида, называемых правилами, где и – различные слова в алфавите V U W и символ не принадлежит V U W.

Пример 3.1.

1 = {a, b},{J }, J,{J a J b, J ab} есть -грамматика.

Согласимся, что a n есть a a … a (n раз, n 1) и a 0 есть, а A 1 2... n означает A 1, A 2, …, A n ; заметим, что (a b) n a nb n при n 2.

С учетом этих соглашений грамматика 1 запишется следующим образом: 1 = {a, b},{J }, J,{J a J b a b}.

Определение 3.2.

Индуктивное определение выводимых слов грамматики = V,W, J, R :

1) J – выводимое слово этой грамматики ;

2) если – выводимое слово и есть правило из R, то

– также выводимое слово и будем писать.

Определение закончено, т. е. других правил построения выводимых слов нет. Например, слова J, a J b, a n Jb n ( n 2), a 2b 2 выводимы в 1, причем последнее слово есть слово из основных символов.

Определение 3.3. Множество всевозможных слов из основных символов, выводимых в грамматике, называется языком, порождаемым, и обозначается L( ).

Пример 3.2.

Убедимся, что L(1 ) = {a nb n n 1}. В самом деле, каждое выводимое слово в 1, содержащее основные символы, имеет вид a n Jb n (n 1). Чтобы получить слово из основных символов, следует использовать правило J a b, что дает a n +1b n +1, где n 1.

С учетом вывода J, a b получаем указанное равенство для L(1 ), так как других видов выводимых слов с основными символами, кроме a n Jb n (n 1), нет.

Определение 3.4. Последовательность слов W1,W2, …,Wn называется выводом слова Wn из слова W1 в грамматике (символически W1 Wn ), если для каждого i (1 i n) выполнено Wi Wi +1.

n n m m Например, имеем a J b a J b, где n m.

Определение 3.5. П-грамматика = V,W, J, R называется:

1) грамматикой непосредственно составляющих или НС-грамматикой, если каждое ее правило имеет вид A, где слова, и из V W, и A W ;

2) контекстно-свободной или КС-грамматикой, если каждое ее правило имеет вид A, где A W и (V W ) ;

3) автоматной или А-грамматикой, если каждое ее правило имеет вид A aB или A a, где A и B из W, a из V.

П-, ПС-, КС- и А-языками называются языки, порождаемые соответственно П-, ПС-, КС- и А-грамматиками, которые еще называются грамматиками типа 0, 1, 2 и 3 соответственно.

Ясно, что грамматика типа i (i 1) является и грамматикой типа i 1.

Например, грамматика 1 из примера 3.1 является КС-грамматикой (или грамматикой типа 2), но не А-грамматикой (или грамматикой типа 3).

Еще заметим, что язык L(1 ) может быть задан и П-грамматикой (или грамматикой типа 0) со следующими правилами: J aJb, aJb ab, которая не является НС-грамматикой (или грамматикой типа 1; почему?).

Пример 3.3. Рассмотрим следующую грамматику:

2 = {0,1,...,9},{J, A}, J, {J 0 1... 9 1A 2 A... 9 A, A 0 1... 9 0 A 1A 2 A... 9 A}.

Это А-грамматика. Каждое слово из порождаемого ею языка есть последовательность цифр 0, 1, …, причем если слово длины не менее 2, то оно не может начинаться с нуля из-за правил J dA, где d 1.

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

Пример 3.4. Рассмотрим КС-грамматику:

3 = {0,1},{J }, J, {J JJ 0 J 11J 0 10 01}.

Ясно, что любое слово из языка L( 3 ) есть слово длины 2k (k 1) и содержит равное число нулей и единиц; множество из всех таких двоичных слов обозначим через D. Остается убедиться, что L( 3 ) содержит все слова из D. Для этого докажем, что каждое слово из D может иметь один из трех вариантов: 1) 01; 2) 1 0; 3), где, и – слова из множества D, причем может быть пустым.

В самом деле, если слово из D и оно не вида 1) и 2), то оно имеет вид 0 x0 или 1 y1. Поскольку оно имеет равное число нулей и единиц, то как слово 0 x0, так и слово 1 y1 будут вида 3).

Теперь равенство L( 3 ) = D доказывается индукцией по длине выводов (длина вывода – это число применений правил). Базис: слова длины 2 из D, очевидно, выводимы в 3.

Индуктивное предположение: пусть уже доказано, что в 3 выводимы все слова из D длины 2n (n 1).

Индуктивный приход. Рассмотрим некоторое слово z из D длины 2n + 2. Если z = 01 или z = 1 0, где слово длины 2n, то для вывода z следует использовать правило J 0 J 1 или J 1J 0 и индуктивное предположение. Если z =, т. е. вида 3), то каждое из слов и длины не более 2n; тогда, используя индуктивное предположение и правило J JJ, получим вывод z. Значит, L( 3 ) = D.

Пример 3.5.

Какой язык порождает П-грамматика 4 = {a, b, c},{J, B}, J,{J aJBc abc, cB Bc, bB b 2 } ?

В этой грамматике с начальным символом имеются два правила:

1) J aJBc; 2) J abc. Использование в выводе второго правила дает слово abc из основного алфавита, и только его. Значит, другие слова из основного алфавита будут получаться использованием в выводах n (n 1) раз первого правила, что дает J, aJBc, a 2 JBcBc,..., a n J ( Bc) n.

Символ J можно устранить только по второму правилу и в продолжение построенного вывода получим слово a n +1bc( Bc) n. Чтобы из него получить слово из основного алфавита, нужно устранить вспомогательный символ B. Символ B «дает» основной символ, если можно применить правило bB b 2. В последнем слове символ b расположен непосредственно правее подслова из (n + 1)-й буквы a и он не меняет своего положения ни по одному из правил. Следовательно, буквы B должны к нему передвигаться, что позволяет правило cB Bc. Значит, в продолжение рассматриваемого вывода получим слово a n +1bB n c n +1, а из него за n шагов – слово a n +1b n +1c n +1.

Итак, L( 4 ) = {a nb n c n n 1}, так как никаких других выводов в этой грамматике нет.

Упражнения

1. К какому типу принадлежат грамматики со следующими правилами (здесь и в дальнейшем основные буквы строчные, а вспомогательные прописные, J – начальный символ):

а) J aA, A bB, B a;

б) J Ja Jb a b ;

в) J aJa bJb c;

г) J AB, A aAb ab, B cBd cd ;

д) J aIAC abC, CA BA, BA BC, BC AC, bA bb, C c;

е) J aIBC abC, CB BC, bB b 2, C c ?

2. Определить языки, порождаемые грамматиками со следующими правилами:

а) J J 0 J 1... J 9 0 1... 9;

б) J aJb acb ;

в) J a 2 Jb 2, a 2 Jb 2 a 2cb 2 ;

г) J 1A A1 A1A, A AA 0 A11A0 10 01;

д) J abJ abB, B cJ c;

е) J JJ 101J 110 J 011J 10 J 11J 0111J 0 01J 11J 10 110 101 011;

ж) J 1J 1 0 J 0 0 1;

з) J aJBc | aABc, A aAb | ab, cB Bc, bB b 2;

и) J 0 A A0 A0 A, A AA 0 A11A0 10 01;

к) J 1J 1 0 J 0 00 11.

3.2. ВАЖНЫЕ ПРИМЕРЫ Как и в предыдущих примерах, символы из основного алфавита будут обозначаться строчными латинскими буквами и арабскими цифрами, а символы из вспомогательного алфавита – прописными латинскими буквами; все они могут быть с индексами. Начальный символ всегда будет J. Это позволит нам ограничиться выписыванием только множества правил приводимых грамматик.

Пример 3.6.

а) Каждый (непустой) конечный язык {1, 2,..., n }, где i = ai1ai 2...aiK (и его длина | i | 1), порождается А-грамматиi кой с множеством правил {J ai1 Ai1, Ai1 ai 2 Ai 2,..., AiK 1 aiK 1 i n}, i i где Aij Aml, если i m или j l. Заметим, что в этой грамматике каждое слово i выводится с помощью «своих» вспомогательных символов.

б) Пустой язык порождается следующей А-грамматикой с правилом J aJ.

Следствие 3.1. Каждый конечный язык, не содержащий пустого слова, является А-языком.

Покажем, что имеются и бесконечные А-языки.

Пример 3.7.

а) Язык {a nb mc k n, m, k 1} является бесконечным и порождается А-грамматикой с правилами J aJ aB, B bB bC, C cC c.

–  –  –

где i – фиксированные непустые слова в основном алфавите (подчеркнем, что никакого соотношения между ni не имеется, т. е. нет n1 = n2 или n1 n3 и т. п.).

Пример 3.8. Построить А-грамматики, порождающие все двоичные слова, которые:

а) заканчиваются двумя нулями;

б) имеют нечетное число единиц.

Для случая а), очевидно, ее правила следующие:

J 0 J 1J 0 A, A 0.

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

Поэтому правила искомой А-грамматики следующие:

J 0 J 1A 1, A 0 A 0 B 1C, B 1C, C 0C 1B 1.

Назовем простейшей записью натурального числа n (n 1) слово 1n.

Пример 3.9.

Для любых натуральных чисел k и l, где k 1 и 0 l k 1, множество {1kn +l n 1} (арифметическая прогрессия) является А-языком.

В самом деле, пусть заданы некоторые указанные k и l. Тогда в искомой грамматике с правилами J 1A1, A1 1A2,..., Ak 1 1J 1B, B 1B, B1 1B2,..., B l 1 1 сначала из J выводим слово 1kn J или 1kn B, после чего получаем 1k (n +1) J или 1kn1l = 1kn +l (так как при l 1; при l = 1 последние l правил заменяются правилом B 1, а при l = 0 последние l правил удаляются и правило Ak 1 1B заменяется на правило Ak 1 1).

Пример 3.10.

Построить КС-грамматику, порождающую язык {(aa) n b m a (ba) m (bb) n n, m 1}.

В примере 3.1 одновременно появлялись буквы a и b, давая слова a nb n. Поскольку в этом языке есть подслова (aa) n,(bb) n и b m (ba ) m, то они должны одновременно появляться.

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

J aaJbb aaCbb, C bCba bDba, D a.

З а м е ч а н и е. КС-языком является каждый язык вида {11 22... nk 0 nk+1... 22k 1 n1k i (ni 1)}, nn n k k 2 где i (0 i k ) – фиксированные непустые слова в основном алфавите.

Если x и y – слова, то их умножением называется слово xy, получаемое дописыванием к слову x справа слова y.

Умножением языков L и M (взятых именно в этом порядке) называется язык LM = {xy x L y M }.

Лемма 3.1 (об объединении и умножении КС-языков).

Объединение и умножение КС-языков есть КС-язык.

Доказательство. Пусть L и M – КС-языки. В их грамматиках символы из вспомогательных алфавитов переобозначим так, чтобы получились непересекающиеся множества. Тогда объединение таких их правил с добавлением J J1 J 2 или J J1J 2 дает желаемое.

Теперь выясним, будет ли пересечение двух КС-языков всегда КС-языком. Ясно, что {a nb n n 1} и {a nb n n 3} – КС-языки и их пересечение равно второму из них, т. е. есть КС-язык (правила соответствующей грамматики такие: J a J b a3b3 ).

Еще рассмотрим языки L = {a nb n a m n, m 1} и M = {a mb n a n m, n 1}.

Они порождаются КС-грамматиками с множествами правил {J Ja Aa, A a Ab ab} и {J a J a A, A b Aa ba} соответственно. Их пересечение L M = {a nb n a n n 1}, для которого правила порождающей грамматики легко получить из примера 3.5. Ниже докажем, что язык L M не порождается ни одной КС-грамматикой.

Следствие 3.2. Пересечение КС-языков не всегда есть КС-язык.

Пример 3.11.

a) Язык {a mb n 1 m n} является КС-языком.

В соответствующей грамматике должны быть правила одновременного появления букв a и b и наращивания буквы b. Поэтому они могут быть следующими: J Jb Ab, A a Ab a b.

б) Язык {a mb n m n} также КС-язык. Неравенство m n означает, что: 1) m n; 2) m n. Поэтому в случае 1) необходимо учесть возможность m = 0, а в случае 2) – n = 0, а затем использовать предыдущий пример.

Пример 3.12.

Построить грамматику, порождающую язык {a mb m a n m 1 и 1 n m}.

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

Учитывая пример 3.5, приходим к следующим правилам искомой грамматики:

J a J Ba aba a Aba, A aAb ab, aB Ba, bB b 2.

Ясно, что все слова вида a nb n a n будут выведены. Чтобы получить слова из языка при m n, следует в выводах после n 1 раз применения правила J a JBa использовать правило J a Aba, а затем m n раз – правила с буквой A в левой части. Можно доказать, что языки {a nb n a n n 1} и из примера 3.12 не являются КС-языками.

Пример 3.13.

Построить грамматику, порождающую L = {a nb mc k ((n m) ( m k )) (m, n, k 1)}.

Согласно определению суммы по mod2 язык L будет содержать только те слова, в которых: 1) n m и m k ; 2) n m и m k, т. е.

L представляется в виде объединения двух следующих непересекающихся множеств:

L1 = {a nb mc k (n m) (m k ) (m, n, k 1)},

–  –  –

DC CD, E E ( = B, C, D ), Ee e 2, bB b 2, cC c 2.

Очевидно, что при n = 1 соответствующее слово из этого языка выводимо. Чтобы получить соответствующее слово из этого языка при n 1, следует применить один раз правило J aFBCDe, затем – n 2 раза правило F aFBCDE (если n 3 ) и после один раз правило F abcDE ; получим слово a nbcDE ( BCDE ) n 2 BCDe. По другим правилам сначала E «передвигается» к основной букве e (являющейся крайней справа), затем B – к основной букве b (которая находится после подслова a n ), после чего C – к основной букве c (левее которой подслово из буквы b) и, наконец, D заменяются на d (этот порядок передвижений существенен). Иных выводов в этой грамматике не существует. Есть и другой вариант, в котором используется метод пастуха.

Пример 3.16. Язык {a n n 1} порождается грамматикой со следующими правилами:

J ABBDF, BD DCB, BC CB, AD AAH, HC AH, HB BH, HF BBDF, DF a, B a, A a, J a (считаем, что эти правила занумерованы числами от 1 до 11 в порядке их перечня).

Вывод в этой грамматике моделирует формулу (n + 1) 2 = n 2 + 2n + 1, т. е., чтобы получить слово a ( n +1), нужно к полученному слову a n дописать слова a 2n и a, дающие слово a 2 n +1. Это осуществляется с помощью следующего цикла, который начинается после применения правила 1, приводящего к слову ABBDF (левее буквы D только буквы B и A ). Каждое вхождение B в соседстве справа с D порождает C, оставляя D крайним слева (правило 2), что позволяет достичь подслово AD, которое порождает две буквы A и «новую»

букву H (правило 4). Эта буква H каждую соседнюю с ней справа букву C заменяет на A, сохраняя себя правее ее (правило 5); далее H движется направо (правило 6) до буквы F и после применения правила 7 заканчивается цикл (ведь снова левее буквы D только буквы B и A ). После окончания цикла можно начинать новый или применить правила 8–11, получая слово из рассматриваемого языка.

После всех этих примеров ответим на вопрос: «какие языки порождаются всевозможными грамматиками?» Для этого введем следующее понятие. Множество A называется рекурсивно перечислимым, если A = или существует общерекурсивная (т. е. всюду определенная и вычислимая) функция f, для которой A является множеством ее значений. Здесь следует учесть, что имеются как числовые общерекурсивные функции (и для них A – множество чисел), так и «словарные» общерекурсивные функции (и для них A – множество слов). Ответ на поставленный вопрос гласит [2, c.

49]:

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

В заключение очертим один подход [7, с. 204] к построению вычислимых словарных функций в алфавите из p букв.

Сначала определим нумерацию слов в этом алфавите. Буквы этого алфавита взаимно-однозначно отобразим на множестве из чисел 1, 2,..., p и букву, сопоставленную числу i, обозначим a j (1 j p ).

Номером (непустого) слова r = ais... ai1 ai0 назовем число c(r ) = i0 + i1 p +... + is p s – p-ичное разложение числа c(r ) с цифрами 1, 2,..., p (оно отличается от записи чисел в p-ичной системе счисления тем, что есть цифра p и нет цифры 0). Ясно, что каждое натуральное число n (n 1) имеет единственное p-ичное разложение (в соответствующем алгоритме деления на p вместо остатка нуль берется p ). Пустому слову сопоставим число нуль.

Символами c(r ) и n условимся обозначать номер слова r и слово, имеющее номер n соответственно.

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

Числовая n-местная функция f называется функцией, представляющей словарную функцию F в нумерации, если F (x1,..., xn ) = f ( x1,..., xn ) для всех наборов ( x1,..., xn ) с натуральными компонентами, а значит, f ( x1,..., xn ) = c( F (x1,..., xn )) и F (r1,..., rn ) = f (c(r1 ),..., c(rn )).

Очевидно, что каждая словарная функция обладает единственной представляющей числовой функцией (и обратно).

Словарная функция F называется вычислимой (т. е. примитивно рекурсивной, или общерекурсивной, или частично-рекурсивной), если таковой является ее представляющая числовая функция.

Например, словарные функции Fi (r ) = rai (1 i p) – примитивно рекурсивны, так как их представляющие числовые – это fi ( x) = px + i.

–  –  –

3.3. НЕКОТОРЫЕ СВОЙСТВА ГРАММАТИК

В правиле слово () называется его левой (правой) частью.

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

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

Лемма 3.2 (о бесповторных выводах).

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

Напомним, что если – слово, то число его букв (длина) обозначается через ; длина пустого слова есть 0.

Лемма 3.3 (о разрастании А-языков).

Пусть L есть А-язык. Тогда существует такая натуральная константа p, что если L и p, то слово можно представить в виде xyz, т. е. = xyz, где 0 y p и xy i z L для всех i 1 (эту бесконечную последовательность слов будем называть серией).

Существуют бесконечные А-языки, которые совпадают с серией из леммы 3.3 (например, А-язык {ab n a n 1}) так и А-языки, которые не могут совпадать с указанной серией (например, А-язык {(ab) n (ba ) m n, m 1}). Но и в А-языке, который совпадает с серией из леммы 3.3, можно указать другую серию, с ним не совпадающую.

Так, для рассмотренного А-языка {ab n a n 1} можно выбрать p = 5 и взять = ab 4 a, 5, и, положив x = ab, y = b, z = b 2 a, получить = xyz, но серия abbib 2 a для всех i (i 1) не совпадает с этим языком.

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

Продемонстрируем это на примере языка {a nb n n 1}. Допустим, что этот язык автоматный.

Тогда можно применить лемму 3.3 и для каждого достаточно большого n и любого i (i 1) при подходящих словах x, y, z, где y.

Мы имели бы a nb n = xyz и xy i z каждый раз вида a r b r. Но если в слове a nb n (которое есть xyz ) непустое подслово y состоит только из a (т. е. y = a s, x = a n s, z = b n ) или только из b (т. е. x = a n, y = b s, z = b n s ), то ни при каком i (i 1) слово xy i z не может иметь вида a r b r. Если же подслово y состоит из букв a и b, то y = a sbt, x = a n s, z = b n t и снова слово xy i z не будет вида a r b r при i 1. Итак, рассматриваемый язык не есть А-язык, но согласно примеру 3.2 он есть КС-язык. Отсюда и с учетом того, что каждый Аязык есть и КС-язык, получаем утверждение.

Теорема 3.1 (о включении А-языков).

Множество всех А-языков является собственным подмножеством множества всех КС-языков.

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

Лемма 3.4 (о разрастании КС-языков).

Если L есть КС-язык, тогда существует такое натуральное число p, что если z L и z p, то слово z может быть записано в виде uvwxy, где vx, w 1, vwx p и для любого натурального i (i 1) выполнено условие uvi wxi y L.

Сделаем два замечания. Во-первых, из этой леммы не вытекает, что конечный КС-язык будет и бесконечным, потому что в случае конечности выберем p большее, чем длина каждого слова из конечного КС-языка. Во-вторых, для некоторых КС-языков слово w из леммы 3.4 может быть пустым, т. е. w = 0; например, для КС-языка {a nb n n 1}, но не для КС-языка {(ab) n aa(ba ) n n 1}. Но для каждого КС-языка при выборе соответствующего p это слово w будет не пустым; например, для того же языка {a nb n n 1} слова a nb n при p = 3 можно представлять в виде ai abbi, а при большем p и в виде ai ( ab) 2 bi.

Используя эту лемму, докажем, что язык {a nb n a n n 1}, упомянутый в примере 3.12, не является КС-языком. Допустим, что он есть КС-язык. Тогда согласно лемме 3.4 для каждого достаточно большого n и любого i (i 1) при подходящих словах u, v, w, x, y, где vx, мы имели бы a nb n a n = uvwxy и uvi wxi y вида a r b r a r. Но если в слове a nb n a n каждое из его подслов v и x состоит только из a или только из b, то при каждом i (i 1) слово uvi wxi y не может иметь вида a r b r a r. Если же v или x содержат обе буквы a и b, то уже слово uv 2 wx 2 y не будет вида a r b r a r (ведь, например, при v = a sbt { } имеем v 2 = a sbt a sbt ). Итак, язык a nb n a n n 1 не есть КС-язык. Но поскольку он может быть порожден НС-грамматикой (на что укажем ниже) и каждый КС-язык является и НС-языком, то доказали следующее утверждение.

Теорема 3.2 (о включении КС-языков).

Множество всех КС-языков является собственным подмножеством множества всех НС-языков.

Две грамматики 1 и 2 называются эквивалентными, если порождаемые ими языки равны.

Лемма 3.5 (о грамматиках, в левых частях правил которых нет вспомогательных символов).

Для каждой грамматики 1 может быть построена эквивалентная ей грамматика 2, левые части правил которой не содержат вхождений основных символов.

Доказательство. Пусть 1 = V,W, J, R – произвольная грамматика. Каждой букве a из V сопоставим букву A, где A VUW, причем если a1 a2, то A1 A2. Положим V = { A a V }, R = { A a a V } и пусть еще R получается из R заменой каждого a в ее правилах на A. Тогда 2 = V,V W, J, R R есть искомая. Лемма доказана.

Пример 3.17.

Выше (перед примером 3.3) было показано, что язык {a nb n n 1} порождается грамматикой {a, b},{J }, J,{J a Jb, a Jb ab}.

Используя лемму 3.5, построим эквивалентную ей грамматику без основных символов в левых частях правил.

Получаем V = { A, B}, R = { A a, B b}, R = {J AJB, AJB AB}, и значит, множество R R есть все правила искомой грамматики.

Например, вывод в ней слова a 2b 2 – это последовательность J, AJB, A AJB B, A AB B, aAB B, aaB B, aabB, aabb.

Правило грамматики назовем неукорачивающим, если 1 || ||, а в противном случае – укорачивающим. Грамматика, каждое правило которой неукорачивающее, называется неукорачивающей. Например, каждая из грамматик типа 1–3 есть неукорачивающая.

Теорема 3.3 (о НС-языках).

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

Доказательство. Так как каждая НС-грамматика является неукорачивающей, то нужно доказать только достаточность. Считаем, что в данной неукорачивающей грамматике в левой части каждого правила нет основных символов. Каждое ее правило A1 A2... An B1B2...Bq, где

n q, заменяется на ему эквивалентные 2n правил искомой НС-грамматики:

A1 A2 … An D1 A2 … An, D1 A2 … An D1D2 A3 … An,…, D1D2 … Dn 1 An D1D2 … Dn 1Dn, D1D2 … Dn B1D2 … Dn,

–  –  –

Заметим, что вспомогательные символы D1, D2,..., Dn для каждого правила A1 A2 … An B1B2 … Bq свои. Теорема доказана.

Пример 3.18.

Пример 3.12 содержит правила для языка nnn {a b a n 1}, а именно J aJBa aba, aB Ba, bB b 2. Подчеркнем, что эти правила П-грамматики. Но так как они являются неукорачивающими, то согласно теореме 3.3 для этого языка может быть построена и НС-грамматика. Итак, язык {a nb n a n n 1} есть НС-язык.

В определении НС-грамматики требование непустоты слова, вставляемого вместо вспомогательного символа в правилах, является весьма существенным. Снятие этого ограничения приводит к понятию обобщенной НС-грамматики (ОНС-грамматики); таковой была грамматика в примере 3.17.

Теорема 3.4 (о П- и ОНС-грамматиках).

Для каждой П-грамматики может быть построена эквивалентная ей ОНС-грамматика.

Доказательство. Пусть – некоторая П-грамматика. Будем считать, что есть грамматика, удовлетворяющая лемме 3.5. Рассмотрим некоторое правило Yi zi. Пусть – искомая ОНС-грамматика.

1. Если Yi, то в правила включаем такую совокупность правил: A Azi, A zi A для каждого вспомогательного символа A грамматики.

2. Если Yi = 1, то такое правило будет и правилом грамматики.

3. Если Yi = A1 A2 … Ar (r 1), то правило A1 A2 … Ar zi заменяем на серию ему эквивалентных правил аналогично тому, как это было сделано в доказательстве теоремы 3.3 (только в этой серии некоторые вспомогательные символы будут заменяться на ). Теорема доказана.

Пример 3.19.

Преобразовать два правила AB a и BA AB в правила ОНС-грамматики (эквивалентной исходной, содержащей эти два правила).

Имеем следующие серии:

1) AB D1B1, D1B D1D2, D1D2 D2, D2 a;

2) BA C1 A, C1 A C1C2, C1C2 AC2, AC2 AB.

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

Назовем КС-грамматику в нормальной форме, если каждое ее правило имеет вид A BC или A a, где A, B и C – вспомогательные символы, а символ a – основной.

Теорема 3.5 (о нормальной форме КС-грамматик).

Для каждой КС-грамматики может быть построена ей эквивалентная КС-грамматика в нормальной форме.

Доказательство простое (после исключения правил вида АВ).

Проиллюстрируем его на примере.

Пример 3.20.

Для КС-грамматики с правилами J A, A B, B aBb ab построить ей эквивалентную КС-грамматику в нормальной форме.

После исключения указанных правил получаем правила J aJb ab.

Правило J aJB заменяется на такую серию:

J A1 A2, A1 a, A2 JB;

правило J ab – на J B1B2, B1 a, B2 b.

Упражнения

1. Привести примеры двух А-языков, которые совпадают и не совпадают соответственно с серией из леммы 3.3.

2. Привести примеры двух КС-языков, которые совпадают и не совпадают соответственно с серией из леммы 3.4.

3. Язык из примера 3.18 задать:

а) грамматикой без основных символов в левых частях правил;

б) НС-грамматикой.

4. Можно ли задать каждый НС-язык ОНС-грамматикой с хотя бы одним укорачивающим правилом?

5. Преобразовать неукорачивающие правила DAB AbAC, ABA BAB, AB BAA в эквивалентные правила НС-грамматики.

6. Правила П-грамматики ABA Ba, BA ABA, AA B заменить на правила ей эквивалентной ОНС-грамматики.

7. Для следующих КС-грамматик с правилами:

а) J b JaJB;

б) J a 2 Jb 2 a 2b 2;

в) J J1J 2, J1 bJ1a b 2 a 2, J 2 b 2 J 2 a b 2 a;

г) J a 2 Jb 2 a 2 Ab 2, A baAab baab построить им эквивалентные КС-грамматики в нормальной форме.

3.4. ГРАММАТИЧЕСКИЙ РАЗБОР Здесь мы выясним соотношение между классами НС- и ОНС-языков. Для этого рассмотрим следующую проблему.

Задача грамматического разбора (или синтаксического анализа) заключается в следующем: указать алгоритм, с помощью которого для любой грамматики и любого слова x из основных символов можно за конечное число шагов выяснить: x L( ) или нет.

Теорема 3.6 (о распознавании НС-языков).

Существует алгоритм, с помощью которого для любой НС-грамматики и любого слова x в основном алфавите этой грамматики за конечное число действий можно решить: x L( ) или нет.

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

Пусть задано некоторое слово x в основном алгоритме рассматриваемой НС-грамматики и длина этого слова есть m. Тогда существует конечное число (зависящее, в общем случае, от m и чисел основных и вспомогательных символов в ) бесповторных выводов конечной длины в, в которых последние слова в объединенном алфавите имеют длины не больше m0, где m0 m; число m0 будет не больше m плюс максимальная длина правых частей правил рассматриваемой грамматики, так как она неукорачивающая. Если среди последних слов таких выводов нет слова x, то оно не может появиться и ни в каких других выводах этой грамматики из-за ее неукорачивающих правил. Теорема доказана.

З а м е ч а н и е. Верхней оценкой числа используемых правил в алгоритме, описанных в доказательстве теоремы 3.6, является экспонента. Для собственного подкласса НС-грамматик, каковым является класс КС-грамматик, был описан [12, с. 344] алгоритм распознавания за O (n3 ) шагов, причем в нем произвольные КС-грамматики рассматривались в нормальной форме.

Теперь перейдем к грамматическому разбору П-грамматик. Для этого нам понадобится понятие ассоциативного исчисления (АИ).

АИ задается:

1) конечным (непустым) алфавитом;

2) конечной (непустой) системой подстановок (читается:

« взаимно переходит в »), где и – различные слова в алфавите A, причем подстановка означает два следующих правила: и ; знак « » не принадлежит алфавиту A.

Например, АИ Ц задается алфавитом Z = {a, b, c, d, e} и подстановками ac ca, ad da, bc cb, bd db, eca ce, edb de, cdca cdcae, caaa aaa, daaa aaa [11, c. 173].

Слово A называется непосредственно выводимым из слова B в АИ J (символически B A ), если в этом исчислении имеется J подстановка P Q такая, что или A имеет вид P, а B – вид Q, или A имеет Q, а B – вид P.

Например, aaa caaa, daaa aaa. Слова A и B называЦ Ц ются эквивалентными в АИ J, если найдется такая последовательность слов x1, x2,..., xn (n 2), что x1 = A, xn = B и xi xi +1 для J каждого i (1 i n).

Например, в АИ Ц эквивалентны слова: 1) caaa и daaa; 2) aaa и aaa; в самом деле, имеются последовательности: 1) caaa, aaa, daaa;

2) aaa, daaa, aaa.

Теорема 3.7 (Цейтина [11]).

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

По АИ Ц построим грамматику M 0 типа нуль: M 0 = Z,{J }, J, R, где R состоит из всех подстановок АИ Ц и еще одного следующего правила: J aaa (эта грамматика – упрощение грамматики M ) [10, с. 84].

Рассмотрим выводы в этой грамматике. В каждом из них первые два слова – это слова J и aaa. Поэтому если вывод состоит не менее, чем из трех слов, то выводимое слово такого вывода будет эквивалентно слову aaa в АИ Ц. Но, как показано выше, слова aaa и aaa также эквивалентны в АИ Ц. Следовательно, каждое слово из языка, порождаемого грамматикой M 0, будет эквивалентно слову aaa в АИ Ц.

Поэтому согласно теореме Цейтина имеет место следующая теорема.

Теорема 3.8 (о грамматическом разборе для П-грамматик).

Проблема грамматического разбора для П-грамматик алгоритмически неразрешима.

Из этой теоремы непосредственно вытекает следующее.

Следствие 3.3. Множество всех НС-языков является собственным подмножеством множества всех П-языков.

–  –  –

{J (¬ J ) ( J J ) ( J J ) ( J J ) ( J J ) (xi J )(xi J ), где 1 i n и числа r и t также фиксированные; эта грамматика порождает все формулы логики предикатов от фиксированных множеств термов и предикатных символов без условий на свободные и связанные переменные и применения кванторов;

г) V,{J }, J, R, где V = {a1, a2, …, ak, a1 1, a2 1, …, ak 1}, R содержит правила {J Jai Jai1J Jai1Jai J 1 i k} и J ; эта грамматика порождает множество всех слов в алфавите V, равных 1 в свободной группе с образующими a1, a2,..., ak (т. е. таких, которые могут быть преобразованы в последовательным вычеркиванием подслов вида ai ai1 и ai1ai ), и язык, ею порождаемый, называется языком Дикка.

3. Показать, что в грамматике M 0 выводимы:

а) любое слово в алфавите {a, c, d }, содержащее ровно три буквы a;

б) некоторые слова в алфавите Z, содержащие все пять букв этого алфавита.

4.3 Построить КС-грамматики, порождающие:

а) {a nb m (m n) (m n есть четное число)};

–  –  –

г) {x {a, b}+ x для любого из{a, b}+ }.

4. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

И ОСНОВНЫЕ МЕТОДЫ ИХ РЕШЕНИЯ

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

Пусть f (n) обозначает число сравнений пар чисел в алгоритме поиска данного числа в упорядоченном массиве из n чисел, n 1.

Тогда для алгоритма, который сравнивает данное число с числом из середины исходного массива, а затем на следующем этапе рассматn ривает соответствующий его подмассив из чисел, получаем, что f (1) = 1 и n f (n) = f + 1 (4.1) при n 2.

Далее, пусть S (n) есть число сравнений пар букв слова x = x1x2 … xn, где n 1, xi A и A 2, в алгоритме, который определяет, является ли слово x симметричным, т. е. для каждого ли i (1 i n) выполняется равенство xi = xn i +1. Если в этом алгоритме выполняется такое попарное сравнение букв, то имеем S (1) = 0, S (2) = 1 и S (n) = S (n 2) + 1 (4.2) при n 3.

Равенства вида (4.1) и (4.2) называются рекуррентными соотношениями (от лат. recurrere – возвращаться) и играют большую роль в теории сложности вычислений. Они позволяют данную задачу свести к ее подзадаче от меньшего значения параметра. Поэтому, последовательно уменьшая значение параметра, можно прийти к подзадаче, имеющей простое решение. Важной задачей является и построение решения рекуррентного соотношения (PC), т. е. нахождение функции, удовлетворяющей этому PC.

–  –  –

4.2. ЛИНЕЙНЫЕ ОДНОРОДНЫЕ

РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ

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

PC вида f ( n + k ) = d1 f (n + k 1) + d 2 f (n + k 2) +... + d k f (n), (4.7) где d1, d 2,..., d k – некоторые действительные (возможно, комплексные) числа, называются линейными однородными PC с постоянными коэффициентами.

Последовательности, являющиеся решениями линейных однородных PC с постоянными коэффициентами, называются возвратными.

Примерами возвратных последовательностей могут быть прогрессии:

1) геометрическая – a(0) = a, a(1) = aq, a(2) = aq 2,..., являющаяся решением PC f (n) = qf (n 1) при n 1 и f (0) = a;

2) арифметическая – a(0) = a, a(1) = a + d, a(2) = a + 2d,..., являющаяся решением PC f ( n) = 2 f (n 1) f (n 2) при n 2 и f (0) = a, f (1) = a + d.

Теорема 4.1 (о сумме двух решений).

Если a (n) и b(n) являются частными решениями PC (4.7), то для любых действительных чисел m и r последовательность m a (n) + r b( n) также есть решение PC (4.7).

Доказательство. Пусть последовательности a (n) и b(n) есть частные решения PC (4.7), т. е.

a(n + k ) d1a(n + k 1) d 2 a (n + k 2)... d k a(n) = 0 и b(n + k ) d1b(n + k 1) d 2b(n + k 2)... d k b(n) = 0.

Тогда, умножив эти равенства на числа m и r соответственно и сложив их, получаем m (a (n + k ) d1a (n + k 1) d 2 a(n + k 2)... d k a (n)) + + r (b(n + k ) d1b( n + k 1) d 2b(n + k 2)... d k b(n)) = = m 0 + r 0 = 0, т. е. последовательность m a (n) + r b( n) также является решением PC (4.7). Доказательство завершено.

Для PC (4.7) составим алгебраическое уравнение p ( x) x k d1x k 1 d 2 x k 2... d k 1 x d k = 0, (4.8) которое называется его характеристическим уравнением.

Теорема 4.2 (о корне характеристического уравнения).

Пусть r есть корень характеристического уравнения (4.8).

1. Тогда функция r n является решением PC (4.7).



Pages:   || 2 |
Похожие работы:

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное бюджетное образовательное учреждение высшего образования "ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ" Кафедр...»

«Ю.И.Шемакин НАЧАЛА КОМПЬЮТЕРНОЙ ЛИНГВИСТИКИ МОСКВА Издательство МГОУ А/О Росвузнаука ББК "1.1 Ш 21 ' УДК 519.76:007 Шемякин Ю.И. Начала компьютерной лингвистики: Учеб. пособие. М.: Иэдво МГОУ, А/О Росвузнаука, 1992. ISBN 5-7045-0132-Х В учебном пособии определяется предмет компьют...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ" Факультет прикладной информатики УТВЕРЖДАЮ Декан факультета прикладной инф...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ КАФЕДРА РАДИОЭЛЕКТРОННЫХ СРЕДСТВ М.С. ГУРСКИЙ ЛАБОРАТОРНЫЙ ПРАКТИКУМ по курсу ИСПЫТАНИЯ, КОНТРОЛЬ И СЕРТИФИКАЦИЯ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ для студентов специальности “Проекти...»

«Основы информационных технологий В. Е. Алексеев В. А. Таланов ГРАФЫ И АЛГОРИТМЫ. СТРУКТУРЫ ДАННЫХ. МОДЕЛИ ВЫЧИСЛЕНИЙ Учебник Рекомендовано Научно-методическим советом по прикладной математике и информатике УМО университетов РФ в качестве учебника для студентов, обучающихся по сп...»

«ИНТЕРВАЛЬНЫЕ МЕТОДЫ ДОКАЗАТЕЛЬНЫХ ВЫЧИСЛЕНИЙ Решение систем линейных уравнений С.П. Шарый Институт вычислительных технологий СО РАН г. Новосибирск I. Постановка задачи и терминология Доказательные вычисления Константин Иванович Баб...»

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

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

«ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ В МАГИСТРАТУРУ ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 09.04.01 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА В 2017 ГОДУ 1. Базы данных Назначения и основные компоненты системы баз данных. Понятия базы данных, 1. банка данны...»

«Задания открытой олимпиады для школьников по информатике города Липецка "СуперБит" 4 классы. Апрель 2015. Вариант 1. Время выполнения: 40 минут. Количество задач: 10 № Текст задания ВарианПравильны Баллов ты й ответ за ответов задани е Задача. Давайте познакомимся СЕЛЁДОЧК Дорогой др...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ Курсовая работа Коллаборативная фильтрация с учетом временного фактора Выполнил: Студент 4 курса Гомзин Андрей Геннадьевич Научный руководитель: Коршунов...»

«1 Министерство связи и массовых коммуникаций Российской Федерации на 01.07.2012г. ПАСПОРТ ИНФОРМАТИЗАЦИИ СУБЪЕКТА РОССИЙСКОЙ ФЕДЕРАЦИИ Администрация МО "Нерюнгринский район" (официальное название субъекта РФ) Дата заполнения (актуализации) “ 23 ” июля 2012 г. Заполнил (внёс изменение) Овчарова...»

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

«Journal of Siberian Federal University. Engineering & Technologies 3 (2008 1) 247-255 ~~~ УДК 669. 017 Влияние термической и термоциклической обработки на структуру и свойства мартенситно-стареющей стали Виталий С. Биронта, Генри...»

«80 вычислительные методы и программирование. 2017. Т. 18 УДК 519:63.4:532.51.5 О КОМБИНИРОВАНИИ СПОСОБОВ УСКОРЕНИЯ СХОДИМОСТИ ИТЕРАЦИОННЫХ ПРОЦЕССОВ ПРИ ЧИСЛЕННОМ РЕШЕНИИ УРАВНЕНИЙ НАВЬЕ–СТОКСА Е. В. Ворожцов1, В. П. Шапеев2,3 Рассматривается п...»

«ИНФОРМАТИКА Конспект лекций Автор: доцент, к.ф.м.н. Шевелев Г.Е. Дата актуализации: 01.11.2016 г. Информация и информатика 1. Информация в материальном мире Мы живем в материальном мире и окружены физическими телами либо физическими полями....»

«Глава 9 Иерархия моделей автоматов В предыдущих разделах настоящей работы показано, что в моделях одного автомата для фиксации его внутренних состояний достаточно иметь одну многозначную ячейку памяти "П" (рис. 9.1). При этом необходимо отметить, что граф переходов описывает алго­ р...»

«МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН, КОМПЛЕКСОВ И КОМПЬЮТЕРНЫХ СЕТЕЙ УДК 519.216:621.391 ОБОБЩЕННЫЕ ФУНКЦИИ И ПРЕОБРАЗОВАНИЯ ХАРТЛИ В МНОГООСНОВНЫХ СИСТЕМАХ СЧИСЛЕ...»

«1 Место дисциплины в структуре образовательной программы Дисциплина Операционные системы является дисциплиной по выбору вариативной части. Рабочая программа составлена в соответствии с требованиями Федерального государственного образовательного стандарта высшег...»

«Инструкция к Pandora DXL 3910 Программирование системы Таблица I Общие программируемые настройки системы Уровень I-7 Автоматическая постановка на охрану Уровень I-6 Функции радиометки 2,4 Ггц Уровень I-8 Датчики температуры Уровень I-9 Настройки RF-модуля Уровень I-2 Общие настройки Уровень I-3 Указа...»

«ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА №5 ПРИЛОЖЕНИЕ Сентябрь 2012 Секция 6 ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ МАТЕМАТИКЕ УДК 519.1 НУМЕРАЦИЯ ИНВОЛЮЦИЙ Л. Н. Андреева, В. А. Потеряева Пусть задано конечное множество X. Отображение q : X X со свойством инволютивности x, y X(q(x) = y q(y) = x) называе...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.