Логика высказываний

Лекции по математической логике (6 семестр) Лекция 1. Логика высказываний 1.1. Высказывания. Операции над высказываниями. Высказыванием называется повествовательное предложение, которое либо истинно, либо ложно. Если высказывание P истинно (ложно), то P имеет истинностное значение 1 (соответственно, 0). Функцией истинности называется функция, значениями которой и значениями аргументов которой являются истинностные значения 1 и 0. Слова вида "не", "и", "или", "если…то", "тогда и только тогда, когда" и др. называются логическими связками, они используется для составления сложных высказываний из менее сложных высказываний. Действия по построению сложных высказываний при помощи логических связок называются операциями над высказываниями, или логическими операциями. Каждая логическая операция имеет свою функцию истинности, которая определяется соответствующей таблицей истинности. Отрицание P высказывания P – это высказывание "Неверно, что P", такое, что оно истинно (ложно), если P ложно (соответственно, истинно). P P 1 1 Табл. 1. Таблица истинности отрицания Дизъюнкция PQ высказываний P и Q – это высказывание "P или Q", такое, что оно истинно (ложно), если хотя бы одно из P и Q истинно (одновременно оба P и Q ложны). Конъюнкция PQ высказываний P и Q – это высказывание "P или Q", такое, что оно истинно (ложно), если хотя бы одно из P и Q ложно (одновременно оба P и Q истинны). Импликация PQ высказываний P и Q – это высказывание "если P, то Q ", такое, что оно истинно (ложно), если P ложно или Q истинно (P истинно и Q ложно). Эквивалентность PQ высказываний P и Q – это высказывание "P если и только если Q ", такое, что оно истинно (ложно), если либо оба истинны, либо оба ложны (соответственно, одно из P и Q истинно, а другое – ложно). P Q PQ PQ PQ PQ 1 1 1 1 1 1 1 1 1 1 1 1 1 Табл. 2. Таблицы истинности дизъюнкции, конъюнкции, импликации, эквивалентности 1.2. Пропозициональные формулы. Переменная, значениями которой являются истинностные значения 1 и 0, называется пропозициональной (ПП). Формула называется пропозициональной (ПФ), если построена в точности по следующим правилам: 1) ПП – это ПФ; 2) A – это ПФ, если A – ПФ; 3) (AB), (AB), (AB), (AB) – это ПФ, если A и B – ПФ. Пусть p1, …, pn – все ПП, входящие в состав ПФ A. Заменив в формуле A переменные p1, …, pn, на значения 1, 0, и выполнив логические операции, встречающиеся при построении A, мы найдем истинностное значение формулы A. Чтобы найти значение A, надо построить ее таблицу истинности. Пример 1. Построим таблицу истинности для ПФ A(pq)(pq), где p, q – ПП. Последовательно строятся ПФ: pq, p, pq, (pq)(pq) (внешние скобки не записываются), и последовательно вычисляются их истинностные значения. Допустим, что p1, q0. Тогда p0, pq1, pq0, (pq)(pq)0. Мы видим, что при любом распределении истинностных значений ПП p, q можно вычислить истинностное значение ПФ A(pq)(pq). Результаты вычислений можно представить в виде следующей таблицы истинности: 1 p 1 1 q 1 1 p 1 1 pq 1 1 1 pq 1 1 1 Табл. 3. Таблица истинности формулы A 1 1 1.3. Тавтологии. Противоречия. Пропозициональная формула (ПФ) A называется тавтологией (противоречием), если A1 (A0) при любом распределении истинностных значений пропозициональных переменных (ПП) входящих в состав формулы A. Некоторые ПФ не являются ни тавтологиями, ни противоречиями, например, ПП. Тавтология AA – это закон третьего исключенного (любое утверждение либо истинно (1-й случай), либо ложно (2-й случай), и какой-либо 3-й случай исключается). Противоречие AA – это закон противоречия (любое утверждение не может быть одновременно и истинным, и ложным). Несколько замечаний:  отрицание A – тавтология, если и только если A – противоречие;  конъюнкция AB – тавтология, если и только оба A и B являются тавтологиями;  дизъюнкция AB – тавтология, если хотя бы одно из A и B является тавтологией;  дизъюнкция AB может быть тавтологией, даже если ни одно из A и B не является тавтологией. Пример 2. (pp)(qq) – тавтология. Пример 3. p(qq) – тавтология. Пример 4. p(pq) – тавтология. Тавтологии могут быть доказаны при помощи таблиц истинности, равносильных преобразований, методом рассуждения от противного. 1.4. Равносильные формулы. Две пропозициональные формулы A и B называются равносильными, если истинностные значения A и B равны при любом распределении истинностных значений пропозициональных переменных p1,…,pn, входящих в состав формул A и B. При этом мы записываем AB. Из определений равносильных формул, тавтологии и эквивалентности следует Предложение 1. Пропозициональные формулы A и B равносильны, если и только если пропозициональная формула AB – тавтология. Пример 5. Равносильность (AB)AB можно доказать построением таблицы: A B (AB) AB A B AB 1 1 1 1 1 1 1 1 1 1 1 1 1 Табл. 4. Таблица истинности формул (AB) и AB. Равносильность верна, если доказано, что ее левая и правая части одновременно истинны (тогда они также одновременно ложны): действительно, (AB)1 равносильно AB0 по определению отрицания, AB0 равносильно AB0 по определению дизъюнкции, AB0 равносильно AB1 по определению отрицания, AB1 равносильно формул AB1 по определению конъюнкции. Равносильности получаются также при помощи преобразований булевой алгебры. 1.5. Логические следствия. Говорят, что пропозициональная формула B логически следует из пропозициональных формул A1,…,Am (или B – логическое следствие A1,…,Am), если при любом распределении истинностных значений пропозициональных переменных 2 формул A1,…,Am,B как только формулы A1,…,Am становятся истинными, так и формула B становится истинной. Запись A1A2…AmB будет обозначать формулу, состоящую из m импликаций, и с правосторонним расположением скобок (m1): A1A2…AmBA1(A2…(AmB)…). Из определений логического следствия, тавтологии и импликации следует Предложение 2. Пропозициональная формула B логически следует из пропозициональных формул A1,…,Am, тогда и только тогда, когда пропозициональная формула A1(A2…(AmB)…) – тавтология. В частности: 1) формула B логически следует из формулы A, если и только если формула AB является тавтологией; 2) формула B логически следует из формул A1 и A2, если и только если формула A1(A2B), (или формула (A1A2)B), является тавтологией. И для импликации A1A2…AmB, и логического следования B из пропозициональных формул A1,…,Am, формулы A1,…,Am называются посылками, а формула B – заключением. Доказать, что формула B логически следует из формул A1,…,Am, можно следующими способами: а) построением таблицы истинности формул A1,…,Am,B; б) по определению, предположив, что A1…Am1, показать, что B1; в) методом рассуждения от противного: предположив, что A1…Am1, а B0, получить противоречие. Пример 6. Построением таблицы истинности можно доказать, что из формул AB и BC логически следует формула AC (табл. 5). A B C AB BC AC 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Табл. 5. Таблица истинности формул AB, BC и AC. Пример 7. Доказать (по определению логического следствия), что из формул AB, AC и BD логически следует формула CD. Доказательство. Пусть AB1, AC1 и BD1. По определению конъюнкции A1, B1, далее, по определению импликации C1, D1, и в завершение, по определению конъюнкции CD1. Пример 3. Доказать методом рассуждения от противного, что из формул AB, AC и BD логически следует формула CD. Доказательство. Пусть AB1, AC1, BD1. Предположим, что CD0. По определению дизъюнкции C0, D0, далее, по определению импликации A0, B0, и, по определению дизъюнкции AB0. Противоречие, значит, неверно, что CD0, т.е. верно, что CD1. 3 Лекция 2. Дизъюнктивные и конъюнктивные нормальные формы 2.1. Свойства отрицания. Законы де Моргана. AA закон двойного отрицания (отрицание отрицания высказывания равносильно самому высказыванию). Законы де Моргана: (AB)AB (отрицание дизъюнкции равносильно конъюнкции отрицаний) и (AB)AB (отрицание конъюнкции равносильно дизъюнкции отрицаний). Все теоремы, кроме теорем существования, имеют вид импликации AB. Следующая равносильность применяется при опровержении теорем: (AB)AB. Отрицание эквивалентности A и B равносильно эквивалентности одного из A и B отрицанию другого, а также операции «либо, либо» (иначе, сложению по модулю 2): (AB)ABABAB, где ABAB(mod2). 2.2. Свойства дизъюнкции и конъюнкции. При тождественном преобразовании формул используются следующие законы логики (или законы булевой алгебры): законы идемпотентности AAA и AAA; законы коммутативности ABBA и ABBA; законы ассоциативности (AB)CA(BC) и (AB)CA(BC); законы дистрибутивности (AB)C(AC)(BC) и (AB)C(AC)(BC); законы поглощения (AB)BB и (AB)BB. 2.3. Дизъюнкция и конъюнкция n формул. Дизъюнкцией n высказываний A1,…,An называется высказывание A1…An, которое истинно (ложно), если хотя бы одно из A1,…,An истинно, и ложно, если все A1,…,An ложны. Конъюнкцией n высказываний A1,…,An называется высказывание A1…An, которое истинно, если все A1,…,An истинны и ложно, если хотя бы одно из A1,…,An ложно. Пример 1. ABCD((AB)C)D. Отсюда видно, что дизъюнкцию и конъюнкцию n формул можно представить соответственно через дизъюнкцию и конъюнкцию двух формул. Выполняются относительно n-местной дизъюнкции и конъюнкции. Пример 2. E(ABCD)(EA)(EB)(EC)(ED). Отсюда видно, что имеет место закон дистрибутивности конъюнкции относительно n-местной дизъюнкции (и закон дистрибутивности дизъюнкции относительно n-местной конъюнкции). Пример 3. (ABCD)ABCD. Отсюда видно, что имеют место законы де Моргана для n-местных операций  и . 2.4. Дизъюнктивные и конъюнктивные нормальные формы. Определим одновременно две нормальные формы. Пропозициональная формула A, содержащая n переменных p1,…,pn, называется дизъюнктивной (конъюнктивной) нормальной формой, сокращенно, ДНФ (соответственно, КНФ), если: 1) переменная pi и ее отрицание pi является ДНФ (КНФ) (i1,…,n); 2) конъюнкция (дизъюнкция) двух и более формул, полученных по правилам 1 и 2, является ДНФ (КНФ); 3) дизъюнкция (конъюнкция) формул двух и более формул, полученных по правилам 1-3, является ДНФ (КНФ). Пример 4. p1, p1p2, (p1p2)(p3(p1p2)) – ДНФ. Формула A, составленная при помощи связок , , , равносильна некоторой формуле B – ДНФ (КНФ). Формула A преобразуется в формулу B при помощи законов дистрибутивности, де Моргана и двойного отрицания. 2.5. Функции истинности. Функция yf(x1,…,xn) называется функцией истинности, если переменные x1,…,xn и функция y являются истинностными значениями 1 и 0. 4 Каждой логической связке * соответствует своя функция истинности, определяемая таблицей истинности этой логической операции и которую мы обозначим также *. Каждой пропозициональной формуле A с пропозициональными переменными x1,…,xn также соответствует функция истинности yfA(x1,…,xn), определяемая таблицей истинности формулы A. Пример 5. Тавтологии соответствует функция истинности x1x1, а противоречию – функция истинности x1x1. Существует 22n функций истинности от n переменных. Пример 6. Функции истинности одной переменной – всего 4 (рис. 4). f1(x) f2(x) f3(x) f4(x) x 1 1 1 1 1 Табл. 6. Таблица одноместных функций истинности f1(x)1 – единичная функция, f2(x)x – тождественная функция, f3(x)x – отрицание, f4(x)0 – нулевая функция. Пример 7. Функций истинности двух переменных – всего 16 (рис. 5). f1(x,y) f2(x,y) f3(x,y) f4(x,y) f5(x,y) f6(x,y) f7(x,y) f8(x,y) x y 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 f9(x,y) f10(x,y) f11(x,y) f12(x,y) f13(x,y) f14(x,y) f15(x,y) f16(x,y) x y 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 Табл. 7. Таблица двухместных функций истинности Перечислим функции f1 – f16 по парам (функция и ее отрицание): f1(x,y)1, f16(x,y)0 – постоянные (единичная и нулевая) функции, функция проекции f4(x,y)x, ее отрицание f13(x,y)x, функция проекции f6(x,y)y, ее отрицание f11(x,y)y, дизъюнкция f2(x,y)xy, стрелка Пирса f9(x,y)xy(xy), конъюнкция f8(x,y)xy, штрих Шеффера f15(x,y)xy(xy), импликация f5(x,y)xy, ее отрицание f12(x,y)(xy), обратная импликация f3(x,y)yx, ее отрицание f12(x,y)(yx), эквивалентность f7(x,y)xy, разделительная дизъюнкция, или сложение по модулю 2, f10(x,y)(xy)xy. 2.6. Совершенные дизъюнктивные и конъюнктивные нормальные формы. Дизъюнктом от n переменных p1,…,pn называется конъюнкция A1…An, в которой Ai есть переменная pi или ее отрицание pi, i1,…,n. Конъюнктом от n переменных p1,…,pn называется дизъюнкция A1…An, в которой Ai есть переменная pi или ее отрицание pi, i1,…,n. Всего существует 22n1 дизъюнктов (конъюнктов) от n переменных. Пример 8. Все дизъюнкты от 2 переменных p и q: pq, pq, pq, pq. Дизъюнкция (конъюнкция) некоторых, попарно различных, дизъюнктов (конъюнктов) от n переменных p1,…,pn называется совершенной дизъюнктивной (конъюнктивной) нормальной формой n переменных p1,…,pn, сокращенно, СДНФ (СКНФ). 5 Теорема 1. Для любой пропозициональной формулы A, содержащей переменные p1,…,pn и отличной от противоречия (A0), существует формула B, которая является СДНФ от переменных p1,…,pn, и равносильна A, т.е. AB. Доказательство. Пронумеруем строки таблицы истинности формулы A от 1 до 2n, обозначим через pi1, …, pin, Ai истинностные значения переменных p1, …, pn и формулы A в i-й строке таблицы, где i1,…,2n. Для каждой i-й строки, в которой hi1, определим: pij*pj, если pij1, pij*pj, если pij0, для всех индексов i1,…,2n, j1,…,n. Для определенности, предположим, что формула A истинна в первых m строках таблицы истинности (1mn), а в остальных 2nm строках ложна. дизъюнкты p1 … … pj pn A p11 … p1j … p1n 1 p11…p1j…p1n … … … … … … … pm1 … … 1 pmj pmn pm1…p1j…p1n … … нет pm1,1 pm1,j pm1,n … … … … … … … p2n,1 p2n,j p2n,n … … нет Табл. 8. Таблица истинности формулы A для определения дизъюнктов BСДНФ A Определим, теперь, искомую формулу B как дизъюнкцию избранных дизъюнктов: B(p11*…p1j…p1n*)…(pm1*…p1j…pmn*). Нетрудно увидеть, что (табл. 9): pij*1 тогда и только тогда, когда pjpij. (1) pij1 pij0 pij*pjpij1 pij*pjpij01 pjpij pij*pjpij10 pij*pjpij00 pjpij Табл. 9. Все случаи к доказательству эквивалентности (1) Пояснения к таблице 9: в 1-м столбце отмечено, что переменная pj принимает истинностное значение pij или противоположное ему значение pij; в двух других столбцах, вначале, пишем, какой вид по определению имеет формула pij*; затем последовательно подставим значение переменной pj и значение pij. Докажем, AB: B1 равносильно тому, что pi1*…pin*1 для некоторого i, 1im, равносильно тому, что pij*1 для всех j1,…,n, для некоторого i, 1im, равносильно, в силу (1), тому, что pjpij для всех j1,…,n, для некоторого i, 1im, равносильно тому, что значение A вычисляется в некоторой i-й строке, 1im, равносильно тому, что A1. pij*1, если и только если xjxij. (1) Теорема 2. Для любой пропозициональной формулы A, содержащей переменные p1,…,pn и отличной от тавтологии (A1), существует формула C, которая является СКНФ от переменных p1,…,pn, и равносильна A, т.е. AC. Доказательство можно провести двумя способами. 1-й способ: в таблице 9 в оставшихся строках вместо дизъюнктов выписать конъюнкты и рассмотреть их конъюнкцию. 2-й способ: применить теорему 1 к формуле BC, затем использовать законы де Моргана и двойного отрицания. 6 Лекция 3. Релейно-контактные схемы. Полные системы связок 3.1. Релейно-контактные схемы. Рассмотрим электрические схемы, в которых двухпозиционные переключатели (выключатели) соединяются последовательно или параллельно. У электрических схем имеются различные технические реализации, по виду одной из них они называются релейно-контактными. Каждый выключатель либо включен, либо выключен, т.е. либо ток идет, либо тока нет. Поведение электрической цепи с выключаетелем подобно присваиванию пропозиональной букве A истинностного значения: A либо истинно, либо ложно, т.е. либо A1, либо A0. Каждому выключателю поставим в соответстве пропозициональную букву, и обозначим их одинаково: выключателю A соответствует буква A. Рассмотрим электрические схемы, в которых выключатели соединяются последовательно или параллельно. Будем считать, что: одинаково обозначенные выключатели одновременно либо включены, либо выключены; выключатель обозначается A, если пропускает ток тогда и только тогда, когда выключатель A ток не пропускает. Каждой последовательно-параллельной схеме поставим в соответствие пропозициональную формулу, составленную из пропозициональных букв и связок , , . Обозначим их одинаково: электрической схеме F будет соответствовать формула F. Параллельному (последовательному) соединению двух электрических схем X и Y соответствует дизъюнкция XY (конъюнкция XY) двух соответствующих формул X и Y. Две электрические схемы F и G эквивалентны, если равносильны соответствующие им формулы F и G. Чтобы упростить электрическую схему (заменить более простой, эквивалентной ей, схемой), достаточно упростить соответствующую ей формулу. Задача 1. Упростить релейно-контактную схему F (рис. 1). Рис. 1. Релейно-контактная схема F Решение. Составим формулу F, соответствующую заданной схеме F: F(AC)(BC)(ABC)(C(B(AC))). Упростим формулу F, применяя свойства операций дизъюнкции и конъюнкции: в силу дистрибутивности конъюнкции относительно дизъюнкции, F(AB(AB))C)(CB)(CAC)), F((ABA)(ABB))C)(CB)(CAC). По свойствам единицы и нуля, F((1(ABB))C)(CB)0. Далее, F(ABB)C)(CB)(ABBB)C)1CC. Рис. 2. Ответ к задаче 1 Построим электрическую схему (рис. 2), соответствующую полученной формуле, которая будет эквивалентной схеме F. 7 3.2. Логические вентили. Логический вентиль (или логический элемент) – это базовый элемент цифровой системы, выполняющий элементарную логическую операцию. Логические элементы оперируют с сигналами, представляющими собой электрические импульсы. Сигнал имеет значение 1, если есть импульс, и имеет значение 0, если нет импульса. На входы логического элемента поступают сигналы – значения аргументов логической функции, а на выходе появляется значение самой логической функции. На рис. 3 показан0, как работают основные логические элементы. Рис. 3. Работа инвертора (НЕ), дизъюнктора (ИЛИ) и конъюнктора (И) 3.3. Определимость в терминах системы функций. Говорят, что функция истинности h определима в терминах функций истинности f1, …, fm, если h(x1,…,xn)g(y1,…,ym), где g{f1,…,fm}, каждый из аргументов y1,…,ym есть или одна из переменных x1, …, xn, или функция вида G(x1,…,xn), которая уже является определимой в терминах g1,…,gs. Заметим, что логическая связка – это тоже функция истинности. Пример 1. Импликация  определима в терминах , , так как xyxy. Пример 2. Эквивалентность  определима в терминах , , так как xy(xy)(yx). Если функция h определима в терминах функций f1, …, fm, то h(x1,…,xn) равно выражению, построенному из переменных x1, …, xn при помощи функций f1, …, fm. Если каждая из функций f1, …, fm определима в терминах функций g1,…,gs, то после соответствующих замен получим, что функция h определима в терминах функций g1,…,gs. Теорема 1. Пусть функция h определима в терминах функций f1, …, fm, а каждая из функций f1, …, fm определима в терминах функций g1,…,gs. Тогда функция h определима в терминах функций g1,…,gs. Пример 3. Эквивалентность  определима в терминах , , . Действительно, из примеров 1 и 2 следует, что xy(xy)(yx)(xy)(yx). 3.3. Полные системы связок. Система функций истинности f1, …, fm называется полной системой связок, если все функции истинности h определимы в терминах f1, …, fk. Теорема 2. Система связок , ,  полная. Доказательство. Возвращаясь к доказательству теорем о существовании СДНФ и СКНФ, мы видим, что для каждой функции истинности h, по ее таблице истинности, можно представить в виде функции, определенной в терминах , , . Пример 4. Система связок ,  полная. Действительно, в силу теоремы 2, любая функция истинности h определима в терминах , , , а конъюнкция определима в терминах , , так как xy(xy). Отсюда, в силу теоремы 1, следует, что любая функция истинности h определима в терминах , . Пример 5. Система связок , , ,  не полная. Так как 111, 111, 111, 111, то для любой функции истинности h, определимой в терминах связок , , , , верно, что h(1,…,1)1. Но 10, значит, отрицание не определимо в терминах связок , , , , и система связок , , , , не полная. 8 Лекция 4. Исчисление высказываний 4.1. Формальные системы. Центральным объектом математической логики являются теории первого порядка, или, более общо, формальные системы, которые соединяют аксиоматический метод и метод формальных языков. Чтобы определить формальную систему S, надо указать следующие 4 множества:  множество символов системы S;  множество формул системы S;  множество аксиом системы S;  множество правил вывода системы S. Множество символов конечное или счетное, но непустое. Конечная последовательность символов называется словом (или строкой). Множество формул является непустым подмножеством множества слов. Должны быть указаны правила построения формул. Множество аксиом является непустым подмножеством множества формул. Каждое правило вывода есть (m1)-местное отношение между формулами (m1). Если A1, …, Am, B – формулы,  – (m1)-местное правило вывода, (A1,…,Am,B), то, говорят, что B выводится (или следует) из A1, …, Am, при этом формулы A1,…,Am называются посылками, а формула B – заключением правила . Говорят, что формула B выводится (или доказывается) из множества формул  (гипотез), если B является аксиомой, или гипотезой, или заключением правила вывода, каждая посылка которого выводится из множества . Если формула B выводится из множества , то можно построить конечную последовательность формул с последней формулой B, так, что каждая формула есть аксиома, или гипотеза, или заключение правила вывода, посылки которого предшествуют этой формуле в этой последовательности. Если , то формула B называется теоремой (или, говорят, что формула B доказуема). Если {A1,…,Am}, то отношение "B выводится из множества " называется производным правилом вывода "из формул A1,…,Am выводится формула B". Для краткости в доказательствах теорем и производных правил вывода, конечно, могут быть использованы ранее доказанные теоремы и производные правила вывода. 4.2. Исчисление высказываний Формальные системы в пропозициональной логике называются исчислениями высказываний. Определим исчисление высказываний, которое обозначим L. Символы L – пропозициональные переменные p1, p2, …, и логические связки ,  (остальные связки определяются через , ). Слова в L – это конечные последовательности его символов. Формулами исчисления L являются следующие слова в L: 1) переменные p1, p2, …; 2) слово вида A, где A – формула исчисления L; 3) слово вида AB, где A и B – формулы исчисления L. Вместо префиксной записи AB обычно используется инфиксная запись (AB), для которой необходимы скобки. Аксиомами исчисления L являются формулы L следующих видов: A1 A(BA); A2 (A(BC))((AB)(AC)); A3 (BA)((BA)B). В этих аксиомах A, B и C – произвольные формулы исчисления L. Правило вывода в исчислении L одно – это правило отделения MP (modus ponens): из формул A и AB выводится формула B. Множество теорем исчисления L – это подмножество множества формул исчисления L, для которых имеется вывод. Дадим другое, равносильное, определение. Формула исчисления L является теоремой исчисления L, если: 1) является одной из аксиом A1 – A3; 9 2) является заключением правила MP, посылки которого уже являются теоремами исчисления L. При изучении формальных систем следует различать два класса теорем: "внутренних" теорем системы и "внешних" теорем о самой системе. Приведем пример "внутренней" теоремы исчисления L. В исчислении L имеют место следующая теорема: AA. Доказательство (построением вывода). 1. (A((AA)A))(((AA)A)(AA)) A2 2. A((AA)A) A1 3. ((AA)A)(AA) MP, 2, 1 4. A(AA) A1 5. AA MP, 4, 3 Приведем 2 примера "внешней" теоремы об исчислении L. В силу правила MP справедливо следующее утверждение: Теорема 1. Пусть AB выводится из . Тогда B выводится из {A}. Обратное утверждение (теорема дедукции) мы приведем ее без доказательства. Теорема 2. Пусть B выводится из {A}. Тогда AB выводится из . 4.3. Непротиворечивость исчисления высказываний. Основные свойства исчислений высказываний: непротиворечивость, полнота, независимость аксиом. Формальная система S называется противоречивой (непротиворечивой), если в S противоречие является (не является) теоремой S. Следующая теорема называется теоремой истинности. Теорема 3. Каждая теорема исчисления L является тавтологией. Доказательство. Применим индукцию по определению теорем исчисления L. По таблицам истинности, можно проверить, что аксиомы A1, A2, A3 являются тавтологиями. Заключение B правила MP по определению является теоремой, если теоремами являются его посылки A и AB. Индуктивное предположение у нас такое, что для теорем A и AB доказано, что они тавтологии. Из формул A и AB логически следует формула B. Значит, и формула B –тавтология. Следовательно, все теоремы исчисления L – тавтологии. Следствие. Исчисление высказываний L непротиворечиво. Доказательство. Если бы противоречие было теоремой исчисления L, то по теореме 3, оно было бы тавтологией, что невозможно. 4.4. Полнота исчисления высказываний. Формальные системы могут быть полными с различных точек зрения. Мы примем следующее определение. Исчисление высказываний полное, если любая его формула является теоремой, если и только если она является тавтологией. Приведем без доказательства утверждение, обратное к теореме 3. Теорема 4. Каждая тавтология является теоремой исчисления L. Соединяя теоремы 3 и 4, получим следующее утверждение. Теорема полноты. В исчислении L каждая формула является теоремой, если и только если она является тавтологией. 4.5. Независимость аксиом исчисления высказываний. Аксиома A формальной системы S независима (правило вывода  независимо), если не является теоремой (производным правилом вывода) в формальной системе, полученной из S исключением A (). Иначе, аксиома зависима (правило вывода зависимо), если из остальных аксиом и правил. Правило MP независимо, так как теорема pp, где p – пропозициональная переменная, не является никаким частным случаем аксиом A1, A2, A3. Чтобы доказать независимость аксиомы, скажем A1, надо найти такое оценивание формул новыми "истинностными значениями", что аксиомы A2 и A3 и их следствия будут "истинными", а аксиома A1 нет. 10 Лекция 5. Логика предикатов 5.1. Свободные и связанные переменные. Вхождение переменной x в предложении P называется свободным (связанным), если в этом вхождении переменную x можно заменить (нельзя заменить) ее допустимым значением. Переменная x в предложении P называется свободной (связанной), если в предложении P имеется свободное (связанное) вхождение переменной x. Предложение PP(x1,…,xn), содержащее n свободных переменных x1,…,xn называется n-местным предикатом. n-местный предикат PP(x1,…,xn) при замене всех свободных вхождений некоторой переменной, скажем, xn, ее допустимым значением an, обращается в (n1)-местный предикат QQ(x1,…,xn1)P(x1,…,xn1,an) (n1). Одноместный предикат PP(x) при замене всех свободных вхождений переменной x ее допустимым значением a обращается в высказывание QP(a). Например, трехместный предикат xyxz при замене x2 обращается в двухместный предикат 2y2z. 5.2. Операции над предикатами. Логические связки , , , , , применяются для построения из одних предикатов других, более сложных по структуре. Для простоты предположим, что все переменные в рассматриваемых предикатах имеют одно и то же множество допустимых значений (область определения) D. При замене всех свободных вхождений переменной xi ее допустимыми значениями aiD, где i=1,…,n, n-местный предикат P(x1,…,xn) обращается в высказывание P(a1,…,an). Отрицанием PP(x1,…,xn) предиката PP(x1,…,xn) называется предикат, полученный из P при помощи частицы "не", при этом для любых a1,…,anD высказывание P(a1,…,an) является отрицанием высказывания P(a1,…,an). Рассмотрим два предиката PP(x1,…,xn) и QQ(x1,…,xn), в которых некоторые переменные x1, …, xn могут быть связанными. Дизъюнкцией PQP(x1,…,xn)Q(x1,…,xn) предикатов PP(x1,…,xn) и QQ(x1,…,xn) называется предикат, полученный из P и Q при помощи частицы "или". При этом для любых a1,…,anD высказывание PQ(a1,…,an) является дизъюнкцией высказываний P(a1,…,an) и Q(a1,…,an). Квантор существования x – это словосочетание "существует x, такой, что". Подтверждением предложения P при помощи x называется новое предложение "существует x, такой, что P". Квантор всеобщности x – это словосочетание "для всех x". Обобщением предложения P при помощи x называется новое предложение "для всех x верно, что P". Рассмотрим операции навешивания кванторов x и x к n-местному предикату PP(x1,…,xn), т.е. предикату P сопоставим предикаты xP и xP. Если переменная x{x1,…,xn}, то навешивание кванторов x и x не влияют на смысл предиката P. Пусть переменная x совпадает с одним из переменных x1, …, xn, скажем, xxn. Тогда (n1)-местные предикаты E(x1,…,xn1)xP(x1,…,xn) и A(x1,…,xn1)xP(x1,…,xn) имеют новый смысл, чем PP(x1,…,xn). Для краткости, допустим, что PP(x) – одноместный предикат. В общем случае, можно считать, что переменные x1, …, xn1 заменены некоторыми своими допустимыми значениями, xnx. Тогда: xP(x)1, если P(a)1 для некоторого aD, xP(x)0, если P(a)0 для всех aD; xP(x)1, если P(a)1 для всех aD, xP(x)0, если P(a)0 для некоторого aD. 5.3. Отношения между предикатами. Два предиката P и Q называются равносильными (PQ), если при замене переменных любыми их допустимыми значениями предикаты P и Q обращаются в высказывания с одинаковыми истинностными значениями. Говорят, что предикат Q логически следует из предиката P (PQ), если при замене переменных любыми их допустимыми значениями предикаты P и Q обращаются в два высказывания, так, что когда первое из них истинно, то и второе истинно. 11 5.4. Свойства кванторов. Подтверждение и обобщение при помощи переменной x можно рассматривать как обобщение дизъюнкции и конъюнкции соответственно. Пусть D{a1,…,an} – область допустимых значений переменной x, PP(x). Тогда: xP(x)P(a1)…P(an) и xP(x)P(a1)…P(an). Перечислим основные свойства кванторов: 1) Пусть предикат A не содержит свободных вхождений переменной x. Тогда AxBx(AB), AxBx(AB), AxBx(AB), AxBx(AB). 2) Подтверждение дизъюнкций равносильно дизъюнкции подтверждений, и обобщение конъюнкций равносильно конъюнкции обобщений: x(A(x)B(x))xA(x)xB(x), x(A(x)B(x))xA(x)xB(x). 3) Из подтверждения конъюнкции следует конъюнкция подтверждений, а из дизъюнкции обобщений – обобщение дизъюнкций: x(A(x)B(x))xA(x)xB(x), xA(x)xB(x)x(A(x)B(x)). 4) Однородные кванторы можно переставлять местами: xyA(x,y)yxA(x,y), xyA(x,y)yxA(x,y). 5) Из подтверждения обобщения следует обобщение подтверждения: xyA(x,y)yxA(x,y). 6) Отрицание подтверждения равносильно обобщению отрицания, и отрицание обобщения равносильно подтверждению отрицания: xA(x)xA(x), xA(x)xA(x). Пример 1. Докажем первую из равносильносьей пункта 6: xA(x) (по смыслу квантора существования)  неверно, что существует aD, такое, что A(a)  (по здравому смыслу)  для всех aD неверно, что A(a)  (по определению отрицания))  для всех aD верно, что A(a)  (по смыслу квантора всеобщности) xA(x). 5.5. Виды предикатов. Пусть M – непустое подмножество множества допустимых значений D предиката PP(x1,…,xn). Предикат P называется: 1) тождественно истинным (тождественно ложным) предикатом на множестве M, если при замене переменных любыми их допустимыми значениями предикат P обращается в истинное (ложное) высказывание; 2) выполнимым (опровержимым) предикатом на множестве M, если при замене переменных некоторыми их допустимыми значениями предикат P обращается в истинное (ложное) высказывание. Если MD, то говорят просто о тождественно истинных, тождественно ложных, выполнимых и опровержимых предикатах. Из определений следует, что существует три вида предикатов:  тождественно истинные, иначе неопровержимые;  тождественно истинные, иначе невыполнимые;  неопровержимые и невыполнимые. 5.6. Ограниченные кванторы определяются так, чтобы свойства кванторов перешли на ограниченные кванторы: xM P(x)x(xMP(x)), xM P(x)x(xMP(x)). Пример 2. Свойство отрицания квантора всеобщности переносится и на ограниченные кванторы: xM P(x)xM P(x). Доказательство равносильности: xM P(x) (определение ограниченного подтверждения) x(xMP(x)) (отрицание подтверждения) x(xMP(x)) (отрицание импликации) x(xMP(x)) (определение ограниченного обобщения) xM P(x). 12 Лекция 6. Язык логики предикатов При построении языка логики предикатов мы переходим от математических предложений с конкретными операциями и отношениями к абстрактным формулам, в которых функциональные и предикатные символы обозначают произвольные операции и отношения. Обратный переход осуществляется при определении интерпретации языка. 6.1. Символы логики предикатов. Через L обозначим язык логики предикатов первого порядка. Перечислим символы, используемые для построения язык L: 1) переменные; 2) константы; 3) n-арные функциональные символы (n1); 4) n-арные предикатные символы (n1); 5) логические связки , , , , ; 6) кванторы , . Среди бинарных предикатных символов языка L может быть задан символ равенства. Если хотят указать наличие или отсутствие символа равенства в языке L, то язык L могут назвать языком L с равенством или без равенства. В любом случае, множество предикатных символов должно быть непустым. Переменные, логические связки, кванторы и равенство называются логическими символами, а константы, функциональные и предикатные символы, кроме равенства, – нелогическими символами. Все языки логики первого порядка имеют одно и то же множество логических символов и различные множества нелогических символов. Далее мы рассматриваем только языки первого порядка с равенством. Пример 1. Язык L0 с пустым множеством нелогических символов. Пример 2. Язык LL(G) теории групп, нелогическими символами которого являются бинарный функциональный символ , константа n, унарный функциональный символ . Пример 3. Язык LL(S) системы аксиом Пеано, у которого нелогические символы – это константа 0 и унарный функциональный символ s. 6.2. Формулы логики предикатов. Приведем определение термов, т.е. алгебраических выражений, и формул логики предикатов (первого порядка): 1) переменная x есть терм; 2) константа e есть терм; 3) слово вида ft1...tn есть терм, если f есть n-арный функциональный символ, а t1, ..., tn ранее определенные термы; 4) слово вида Pt1...tn есть формула, если P есть n-арный предикатный символ, а t1, ..., tn – термы; 5) слова вида A, AB, AB, AB, AB являются формулами, если A, B ранее определенные формулы; 6) слова вида xA, xA являются формулами, если x – переменная, а A есть ранее определенная формула. 6.3. Интерпретации формул логики предикатов. Интерпретация I языка L – это непустое множество I, на котором для каждого нелогического символа заданы следующие алгебраические объекты: элемент eI для каждой константы e из L; n-местная функция fI:InI для каждого n-арного функционального символа f из L; n-местное отношение PIIn для каждого n-арного предикатного символа P из L. Оценка (иначе интерпретация) v переменных языка L – это некоторое отображение v множества X всех переменных языка L в I. Пара (I,v), состоящая из интерпретации I нелогических символов языка L и некоторой оценки v переменных языка L называется интерпретацией I при оценке v. Обозначение: Iv. 13 Через vx обозначим любую оценку следующего вида: vx(и)v(и), если их, и vx(и) любое, если их. Определим по индукции значение Iv(t) терма t и истинностное значение Iv(A) формулы A языка L в интерпретации I при оценке v: Iv(x)v(x) для переменной x из L; Iv(e)eI для константы e из L; Iv(ft1…tn)fI(Iv(t1),…,Iv(tn)) для терма ft1…tn из L; Iv(Pt1…tn)1,если PI(Iv(t1),…,Iv(tn)) истинно, и Iv(Pt1…tn)0,если PI(Iv(t1),…,Iv(tn)) ложно, для предиката Pt1…tn из L (кроме t1t2); Iv(t1t2)1, если Iv(t1)Iv(t2), и Iv(t1t2)0, если Iv(t1)Iv(t2), для равенства t1t2; для отрицания и импликации значения Iv(В), Iv(ВС) находим по таблицам истинности в зависимости от значений Iv(В), Iv(С) (аналогично для других связок); Iv(хВ)1, если Ivх(В)1 для всех Ivх, и Iv(хВ)0, если Ivх(В)0 для некоторого Ivх, для обобщения xB из L (аналогично для подтверждения). 6.4. Виды формул логики предикатов. Формула A языка L называется:  тождественно истинной в интерпретации I, если Iv(A)1 при любой оценке v;  выполнимой в интерпретации I, если Iv(A)1 при некоторой оценке v;  опровержимой в интерпретации I, если Iv(A)0 при некоторой оценке v;  тождественно ложной в интерпретации I, если Iv(A)0 при любой оценке v. Для каждой интерпретации I формулы подразделяются на 3 вида: тождественно истинные, выполнимые и опровержимые, тождественно ложные. Пример: в одноэлементной интерпретации формула xy истинна и формула xy ложна, а в интерпретации с более чем одним элементом обе эти формулы выполнимы и опровержимы. Формула A языка L называется:  логически общезначимой, если A истинна в каждой интерпретации I;  выполнимой, если A истинна в некоторой интерпретации I;  опровержимой, если A ложна в некоторой интерпретации I;  пртиворечием, если A ложна в каждой интерпретации I. Формулы подразделяются на 3 вида: логически общезначимые, выполнимые и опровержимые, противоречия. Пример: формула xx истинна, формула xx ложна, а формулы xy и xy и выполнимы, и опровержимы. Пример. Пусть P – бинарный предикатный символ. Тогда: 1) формула P(x,y)P(x,y) логически общезначима по определению связки ; 2) формула xyP(x,y)yxP(x,y) логически общезначима по смыслу квантора всеобщности; 3) формула P(x,y)P(x,y) выполнима, так как предложение xyxy истинно на одноэлементном множестве; 4) формула P(x,y)P(x,y) опровержима, так как предложение xyxy не истинно на двухэлементном множестве; 5) формула (P(x,y)P(x,y))) – противоречие по определению связок , . 6.5. Свободные и связанные вхождения переменных. Вхождение переменной x в формуле A связано (свободно), если (не) является частью формулы A вида xB или xB. Запись Ax[t] обозначает формулу, которая получается из формулы A заменой каждого свободного вхождения переменной x термом t; при этом предполагается, что терм t допустим для подстановки в A вместо x, т.е. формула A не содержит подформул вида yB, или yB, где y – переменная из t. Приведем пример, показывающий необходимость ограничения допустимости термов для подстановки вместо переменных. Пусть P – унарный предикатный символ, Ay(P(x)P(y)), ty. Тогда формула Ax[t] имеет вид y yy, и получается, что формула A выполнима, а формула Ax[t] невыполнима. 14 Лекция 7. Теории первого порядка 7.1. Определение теории первого порядка. Чтобы определить формальную систему F, надо определить язык LL(F) системы F, в частности, правила построения формул, и указать аксиомы и правила вывода системы F, чтобы можно было устанавливать, какие из формул являются теоремами системы F. Определим теории первого порядка. Язык L(T) теории первого порядка T – это язык первого порядка L. Аксиомы теории первого порядка T подразделяются на аксиомы логические и нелогические. Логическими аксиомами теорий первого порядка являются формулы вида: A1 A(BA); A2 (A(BC))((AB)(AC)); A3 (BA)((BA)B); A4 xAAx[t], если терм t допустим для подстановки вместо x в A; A5 xx; A6 x1y1…xnynfx1…xnfy1…yn, где f – n-арный функциональный символ; A7 x1y1…xnynPx1…xnPy1…y, где P – n-арный предикатный символ. Два основных правила вывода: MP Из A и AB следует B. Из AB следует AxB, если переменная x свободна в A. () Нелогические аксиомы – это некоторые формулы, желательно выполнимые. Теории первого порядка отличаются различными языками или различными нелогическими аксиомами. Значит, чтобы задать теорию первого порядка T, достаточно указать множества нелогических символов и нелогических аксиом теории T. 7.2. Модели теории первого порядка. Интерпретация M теории первого порядка T называется моделью теории T, если в M истинны все нелогические аксиомы теории T. Формула теории первого порядка T называется истинной в теории T, если она истинна в любой модели теории T. Примеры теорий первого порядка и их моделей: Пример 1. Теория T0 с пустыми множествами нелогических символов и аксиом. Моделью теории T0 является любое непустое множество. Пример 2. Теория групп G языка L(G) с тремя аксиомами: x,y,z (xy)zx(yz); x xnx; x xxn. Моделью теории G является любая группа, например, аддитивная группа всех действительных чисел и мультипликативная группа всех ненулевых действительных чисел. Пример 3. Система Пеано S языка L(S) с тремя аксиомами: x sx0; x,y (sxsyxy); [P(0)x(P(x)P(sx))]xP(x). Моделью теории S – это множество {, {}, {,{}}, {,{},{,{}}}, ...} с унарной операцией sxx{x}. 7.3. Теоремы в теориях первого порядка. Пусть P – тавтология с пропозициональными переменными p1,…,pn, а A – формула, полученная из P заменой каждого вхождения переменой pi формулой Bi для всех i1,…,n. Формула A называется частным случаем тавтологии P. Поскольку теории первого порядка содержат аксиомы A1-A3 и правило MP, то из исчисления высказываний можно перенести следующую теорему. Теорема о тавтологии. Пусть формула A теории T является частным случаем некоторой тавтологии. Тогда A – теорема теории T. Если формула A1…AnB теории T – частный случай тавтологии, то формула B называется тавтологическим следствием формул A1-An. Из теоремы о тавтологии следует 15 Теорема о тавтологическом следствии. Пусть формула B является тавтологическим следствием формул A1-An –теорем теории T. Тогда B – тоже теорема теории T. Аксиома (A4) называется аксиомой подстановки для квантора . Докажем теорему подстановки для квантора : (T1) Ax[t]xA. Доказательство построим в виде вывода: 1. xAAx[t] (A4) 2. Ax[t]xA тавтологическое следствие 3. Ax[t]xA определение квантора  Правило () называется правилом введения квантора . Докажем правило введения квантора  (переменная x не свободна в B): () ABxAB, Доказательство построим в виде вывода: 1. AB гипотеза 2. BA тавтологическое следствие 3. BxA правило () 4. xAB тавтологическое следствие 5. xAB определение квантора  Следующее правило называется правилом обобщения: (P1) AxA. Доказательство построим в виде вывода: 1. A гипотеза 2. xAA тавтологическое следствие 3. xAxA правило () 4. xA тавтологическое следствие Следующее правило называется правилом подстановки: (P2) AAx[t]. Доказательство построим в виде вывода: 1. A гипотеза 2. xA (P1) 3. xAAx[t] (A4) 4. Ax[t] (MP) Формула Ax1…xnA называется замыканием формулы A, если x1,…,xn – все переменные, свободные в A. Из определения истинностного значения формулы – обобщения следует, что формула A и ее замыкание A логически эквивалентны: AA. Теорема о замыкании. Замыкание A является теоремой теории T Ттогда и только тогда, когда формула A является теоремой теории T. Доказательство. 1) Если формула A является теоремой теории T, то n раз применив правило обобщения (P1), получим, что A тоже является теоремой теории T. 2) Пусть A – теорема теории T.. Тогда запишем n аксиом подстановки (A4): x1x2x3…xn1xnAx2x3…xn1xnA; x2x3…xn1xnAx3…xn1xnA; …………………………………….. xn1xnAxnA; xnAA. Применив n раз правило (MP), получим, что A является теоремой теории T. Формула без свободных вхождений переменных называется замкнутой. Для замкнутой формулы A теории T либо сама формула, либо ее отрицание A истинны в теории T. Однако, может случиться, что ни A, ни A не являются теоремами теории T. 16 Лекция 8. Свойства теорий первого порядка 8.1. Противоречивые теории. Теория T противоречива, если в ней выводится противоречие, например, формула вида AA. Так как из противоречия логически следует любая формула, то в противоречивой теории все формулы являются теоремами. Пример. Следующие две теории противоречивы. 1) Теория с пустым множеством нелогических символов и с одной нелогической аксиомой xx. 2) Теория с двумя нелогическими символами – с константой c и с бинарным предикатным символом P, а также с одной нелогической аксиомой x,y(P(x,y)P(x,c)). 8.2. Непротиворечивые теории. Теория T называется непротиворечивой, если в теории T не выводимо противоречие. Теорема истинности. Любая теорема теории первого порядка T является истинной в теории T. Доказательство. Нетрудно проверить, что логические аксиомы (A1)-(A7) являются логически общезначимыми формулами, а правила вывода (MP) и () являются логическими следствиями. Нелогические аксиомы истинны в теории T по определению модели теории T. Следовательно, все аксиомы теории T истинны в теории T, и по правилам вывода новые теоремы будут истинными формулами. Следствие. Если теория T имеет модель, то она непротиворечива. Доказательство. Если теория T имеет модель M, а противоречие AA выводимо в теории T, то по теореме истинности формула AA истинна в теории T, что невозможно. 8.3. Полные теории. Теория T обладает свойством полноты в широком смысле, если каждая формула A теории T, истинная в теории T, является теоремой теории T. Теория T обладает свойством полноты в узком смысле, если теория T непротиворечива и для каждой замкнутой формулы A теории T, одна из двух формул A и A является теоремой теории T. При этом теория T называется полной теорией. Из свойства полноты в узком смысле следует свойство полноты в широком смысле. В теореме Гёделя о полноте для произвольных теорий первого порядка утверждается свойство полноты в широком смысле. Приведем две эквивалентные формулировки теоремы Гёделя о полноте. I. Любая формула А теории Т является теоремой теории Т тогда и только тошда, когда формула А истинна в теории Т. II. Теория Т непротиворечива тогда и только тошда, когда теория Т имеет модель. Нелогическими аксиомами формальной арифметики являются четыре аксиомы: x0x; xsys(xy); x00; xsyxyx; Приведем две теоремы Гёделя о неполноте формальной арифметики. I теорема Гёделя о неполноте. Любое непротиворечивое расширение формальной арифметики неполно. II теорема Гёделя о неполноте. В формальной арифметике N можно построить формулу, которая интерпретируются «N непротиворечива» и которая недоказуема и неопрвержима в N. 8.4. Разрешимые теории. Проблема разрешимости для теории T. Существует ли алгоритм, который для любой формулы A из теории T за конечное число шагов решает: формула A является теоремой из теории T или нет? При положительном решении этой проблемы теория T называется разрешимой. Теорема Черча. Любое непротиворечивое расширение формальной арифметики N (в частности, сама теория N) неразрешимо. 17 Лекции по теории алгоритмов (7 семестр) Лекция 1. Алгоритмы и рекурсивные функции Неформально алгоритм определяет вычислительный процесс построения величин, причем имеются возможности для записи начальных данных величин, промежуточных результатов и заключительного результата, если выполнены следующие требования: 1) вычислительный процесс можно разбить на шаги (дискретность); 2) каждый последующий шаг однозначно зависит от предыдущих шагов (детерминированность); 3) начальные величины выбираются из счетного множества (массовость); 4) вычислительный процесс имеет цель – нахождение величины, удовлетворяющей условиям поставленной задачи (результативность). Неформальное определение алгоритма достаточно для решения задач на построение некоторого алгоритма. Формальное определение алгоритма необходимо для решения многих задач, в которых доказывается, что искомого алгоритма не существует. С понятием алгоритма тесно связано понятие вычислимой функции. Пусть A и B – два потенциально бесконечных множества. Функция f:AB называется вычислимой, если существует алгоритм, который определяет вычислительный процесс, начинающийся с любой величины xA, и такой, что: либо останавливается за конечное число шагов с заключительной величиной yB (тогда, когда f(x) определено и равно y); либо не останавливается или останавливается без определения заключительной величины (тогда, когда f(x) не определено). В теории алгоритмов натуральный ряд начинается с нуля: N{0,1,2,…,n,…}. Числовой функцией будем называть n-местную функцию f:NnN, n0. Не все числовые функции являются вычислимыми. Операции над числовыми функциями называются операторами. Чтобы построить невычислимую числовую функцию, надо точно определить понятие числовой функции. Наиболее известным уточнением понятия вычислимой функции является понятие рекурсивной функции. Исходные рекурсивные функции: одноместные нулевая функция o(x)0 и функция следования s(x)x1; n-местные функции проекции Iin(x1,...,xn)xi (n0, i1,…,n). Для построения новых рекурсивных функций используются m-местный оператор подстановки (суперпозиции) Sm, двухместный оператор примитивной рекурсии R, одноместный оператор минимизации M. Говорят, что n-местная функция h получена из m-местной функции g и (m1) nместных функций f1, …, fm1 при помощи оператора подстановки (суперпозиции) Sm и пишут hSmgf1…fm1, m1, n0, если для всех x1,...,xnN выполняется следующее условие: h(x1,...,xn)g(f1(x1,...,xn),…,fm1(x1,...,xn)). (1) Условие (1) означает, что h(x1,...,xn) определено и равно z, если g1(x1,...,xn) определено и равно y1, g2(x1,...,xn) определено и равно y2, ………………………………………, gm1(x1,...,xn) определено и равно ym1, f(y1,…,ym1) определено и равно z; иначе h(x1,...,xn) не определено. В частности, при m1 функция hS2gf является композицией функций f и g, т.е. h(x1,...,xn)g(f(x1,...,xn)) для всех x1,...,xnN. Говорят, что n-местная функция h получена из (n1)-местной функции f и (n1)местной функции g при помощи оператора примитивной рекурсии R и пишут hRfg, n0, если для всех x1,…,xn1,kN, k0, выполняется следующая схема рекурсии: h(x1,…,xn1,0)f(x1,…,xn1), (2) 18 h(x1,…,xn1,k)g(x1,…,xn1,k1,h(x1,…,xn1,k1)). (3) Условия (2) и (3) означают, что h(x1,...,xn1,k) определено и равно zk, если f(x1,…,xn1) определено и равно z0, g(x1,…,xn1,0,z0) определено и равно z1, g(x1,…,xn1,1,z1) определено и равно z2, ………………………………………………., g(x1,…,xn1,k1,zk1)) определено и равно zk; иначе h(x1,...,xn1,k) не определено. Если n1, то считается, что функция f(x1,…,xn1)c будет константой (т.е. будет числом cN). В информатике оператору R соответствует цикл for ("для"). Запись yP(x1,…,xn,y) означает "наименьшее y, такое, что отношение P(x1,…,xn,y) истинно" (-оператор). При этом предполагается, что для всех x1,…,xnN если отношение P(x1,…,xn,y) определено для yN, то отношение P(x1,…,xn,k) определено и для всех ky. Говорят, что n-местная функция g получена из n-местной функции f при помощи оператора минимизации M и пишут gMf, n0, если для всех x1,…,xn1,xn,yN g(x1,…,xn)yf(x1,…,xn1,y)xn. (4) Условие (4) означает, что g(x1,...,xn) определено и равно y, если f(x1,…,xn1,0) определено и не равно xn, f(x1,…,xn1,1) определено и не равно xn, …………………………….….……………, f(x1,…,xn1,y1) определено и не равно xn, f(x1,…,xn1,y) определено и равно xn; иначе g(x1,…,xn) не определено. В частности, если n1 и функция f – биекция, то функция gMf является обратной функцией: gf1, т.е. yg(x)xf(y) для всех x,yN. В информатике оператору M соответствует цикл while ("пока"). Числовая функция называется рекурсивной (примитивно рекурсивной), если: (I) нулевая функция o рекурсивна (примитивно рекурсивна); (II) функция следования s рекурсивна (примитивно рекурсивна); (III) функции проекции Iin рекурсивны (примитивно рекурсивны); (IV) если функции g, f1, …, fm рекурсивны (примитивно рекурсивны), то функция m hS gf1…fm1 рекурсивна (примитивно рекурсивна); (V) если функции f, g рекурсивны (примитивно рекурсивны), то функция hRfg рекурсивна (примитивно рекурсивна); (VI) если функция f рекурсивна, то функция gMf рекурсивна. Используя интуитивное определение алгоритма, доказывается: Теорема 1. Любая рекурсивная функция вычислима. Утверждение, обратное к теореме 1, не доказывается как теорема и не принимается как аксиома, а является законом, полученным из практики: Тезис Чёрча. Любая вычислимая функция рекурсивна. Приведем основные доводы в пользу принятия тезиса Черча: 1) все те вычислимые функции, которые встречаются на практике, оказываются рекурсивными функциями; 2) методы построения вычислимых функций являются также методом построениярекурсивных функций; 3) каждое уточнение понятия алгоритма определяет свой класс вычислимых функций, и все они совпадают с классом рекурсивных функций; 4) успешное исследование вычислимых функций, как рекурсивных функций, в компьютерных науках. 19 Лекция 2. Построение рекурсивных функций Мы приведем новые примеры рекурсивных функций, являющихся также примитивно рекурсивными функциями (за исключением тех, которые приведены в теореме 8). Применение оператора подстановки Sm Теорема 2. Постоянная функция cnk(x1,…,xn)k рекурсивная. Доказательство проведем, без потери общности, в частном случае, при n2, k3. Представим функцию c23(x,y)3 при помощи оператора подстановки и исходных рекурсивных функций: c23(x,y)s(s(s(o(I12(x,y))))), или в следующем операторном выражении c23S2sS2sS2sS2oI12. Значит, функция c23 построена, исходя из рекурсивных функций s, o, I12 при помощи оператора S2, т.е. функция c23 тоже рекурсивна. ฀ Теорема 3. Если функция g получена из рекурсивной функции f(x1,…,xn) заменой отдельных переменных x1, …, xn на некоторые числа или прибавлением к отдельным переменным x1, …, xn некоторых чисел, то g – тоже рекурсивная функция. Доказательство проведем, без потери общности, в частном случае. Пусть f(x,y) – рекурсивная функция, а g(x)f(x,1), h(x,y)f(x,y1). Легко увидеть, что g(x)f(I11(x),s(o(x))), h(x,y)f(I12(x,y),s(I22(x,y))), или в операторном выражении gS3fI12S2so, hS3fI12S2sI22. Значит, функции g и h построены, исходя из рекурсивных функций f, I12, I22, s, o при помощи операторов S3, S2, т.е. функции g и h тоже рекурсивны. ฀ Теорема 4. Пусть g(x1,…,xn)f(y1,…,ym), f – рекурсивная функция, x1,…,xn – различные переменные, {y1,…,ym}{x1,…,xn}. Тогда g – тоже рекурсивная функция. Доказательство. Легко увидеть, что g(x1,…,xn)f(Ini1(x1,…,x),…,Inim(x1,…,xn)), где y1xi1, …, ymxim, 1i1,…,imn, или в операторном выражении gSm1fIni1…Inim. Значит, функция g построена, исходя из рекурсивных функций f, Ini1, …, Inim при помощи оператора Sm1, т.е. функция g тоже рекурсивна. ฀ В силу теоремы 4, функция от переменных x1, …, xn, полученная из рекурсивной функции от переменных y1, …, ym, будет рекурсивной, если последовательность y1, …, ym получена из последовательности x1, …, xn перестановкой, повторением или удалением некоторых переменных из списка переменных x1, …, xn. Задача 1. Пусть f(x,y,z) – рекурсивная функция, функции g,h,k определены следующим образом: g(x,y,z)f(y,z,x), h(x,y)f(x,x,y), k(x,y,z,u)f(y,x,z) для всех x,y,z,uN. Докажите, что функции g,h,k рекурсивны (без применения теоремы 4, но по методу доказательства теоремы 4). Применение оператора примитивной рекурсии R Приведем схему примитивной рекурсии R для одноместной функции: h(0)f0const, h(k)g(k1,h(k1)), где k0. Определим функцию сигнум: Определим функцию антисигнум: Теорема 5. Сигнум и антисигнум – рекурсивные функции. Доказательство. По схеме рекурсии для одноместной функции (k0): sg(0)0, sg(k)1s(o(I12(k1,sg(k1)))). Таким образом, sgR0S2sS2oI12, т.е. функция sg построена исходя из функций s, o при помощи операторов R, S2, значит, она рекурсивна. Аналогично доказывается, что антисигнум – рекурсивная функция ฀ 20 Приведем схему примитивной рекурсии R для двухместной функции: h(x,0)f(x), h(x,k)g(x,k1,h(x,k1)), где k0. Теорема 6. Сложение fсл(x,y)xy – рекурсивная функция. Доказательство. По схеме рекурсии для двухместной функции: fсл(x,0)x0xI11(x), fсл(x,y)x((y1)1)(x(y1))1s(I33(x,y1,fсл(x,y1))). Таким образом, fслRI11S2sI33, т.е. функция fсл построена исходя из функций s, I33, при помощи операторов R, S2, значит, она рекурсивна. ฀ Теорема 7. Умножение fумн(x,y)xy – рекурсивная функция. Доказательство. По схеме рекурсии для двухместной функции: fумн(x,0)x00o(x), fумн(x,y)x((y1)1)(x(y1))xS3fслI33I13(x,y1,fумн(x,y1))). Таким образом, fумнRoS3fслI33I13, т.е. функция fумн построена исходя из функций o, fсл, I11, I33, при помощи операторов R, S3, значит, она рекурсивна. ฀ Применение оператора минимизации M Примитивно рекурсивные функции, как следует из определения, всюду определенные. Рекурсивные функции, вообще говоря, могут быть не всюду определенными. Рекурсивные функции также называются частично рекурсивными функциями. Теорема 8. Функции x, x1, x1, x1x2 не всюду определены и рекурсивны. Доказательство. 1) Mo(x)x. Действительно, функция yyo(y)x определена при x0 (равна 0) и не определена при x0, также как и функция yx. 2) Ms(x)x1. Действительно, функция yyo(y)x не определена при x0 и определена при x0 (равна x1), также как и функция yx1. 3) Функция S2Mos(x)Mo(s(x))(x1)x1 нигде не определена. 4) Вычитание Mfсл(x1,x2) y[x1yx2]x1x2 определено только при x1x2. ฀ Две всюду определенные функции, тесно связанные с вычитанием Усеченная разность x y определяется следующим образом: x y0, если xy, x yxy, если xy. Заметим, что x y0xy, или x y0xy. Модуль разности |xy| является композицией функций модуля и вычитания: |xy|xy, если xy, |xy|yx, если xy. Заметим, что |xy|0xy, или |xy|0xy. Теорема 9. Функция усеченной разности рекурсивна. Доказательство. 1) Докажем, что функция f1(x)x 1 рекурсивна: f1(0)0 10, f1(k)k 1k1I12(k1,f1(k1)), где k1. 2) Докажем, что функция fу.р.(x,y)x y рекурсивна: x 0xI11(x), x yx ((y1)1)(x (y1)) 1f1(I33(x,y1,x (y1))). Осталось доказать тождество a (bc)(a b) c: если abc, то ab, abc, и a (bc)a(bc)(ab)c(ab) c(a b) c; если babc, то abc, и a (bc)0(ab) c(a b) c; если ab, то abc, и a (bc)00 c(a b) c. ฀ Теорема 10. Модуль разности является рекурсивной функцией. Доказательство. |xy|(x y)(y x), т.е. |xy|S3fслfу.р.S3fу.рI22I12. ฀ 21 Лекция 3. Рекурсивные отношения и новые операторы Отношение может быть рассмотрено как множество и как предикат (предложение). Характеристической функцией отношения (предиката) P(x1,…,xn), x1,…,xnN, называется функция P, такая, что: P(x1,…,xn)1, если отношение P(x1,…,xn) истинно; P(x1,…,xn)0, если отношение P(x1,…,xn) ложно. Отношение P называется рекурсивным (разрешимым), если его характеристическая функция P рекурсивна (вычислима). Теорема 11. Пусть P(x1,…,xn) и Q(x1,…,xn) – рекурсивные отношения. Тогда отношения P(x1,…,xn) и P(x1,…,xn)Q(x1,…,xn) тоже рекурсивны. Доказательство. По условию, PP(x1,…,xn) и QQ(x1,…,xn) – рекурсивные функции. Тогда P1P1 P, PQPQ – тоже рекурсивные функции. ฀ Дизъюнкция, импликация и другие логические операции представимы в терминах конъюнкции и импликации, поэтому для них тоже справедливо утверждение теоремы 11. Теорема 12. Отношения xy и xy рекурсивны. Доказательство. Так как xy|xy|0|xy|1, то характеристическая функция (x,y)sg|xy| рекурсивна, и отношение xy рекурсивно. Аналогично, через антисигнум, доказывается рекурсивность равенства. ฀ Теорема 13. Отношения порядка xy и xy рекурсивны. Доказательство. Так как xyx y0sg(x y)1, то характеристическая функция (x,y)sg(x y) рекурсивна, и отношение xy рекурсивно. ฀ Аналогично, через антисигнум, доказывается рекурсивность отношения xy. ฀ Теорема 14. Отношения порядка xy и xy рекурсивны. Доказательство. (x,y)(I22(x,y),I12(x,y)), (x,y)(I22(x,y),I12(x,y)). ฀ Далее рассмотрим новые операторы, которые являются новыми способами построения рекурсивных функций. Ограниченные суммы и произведения Суммы и произведения трех и более чисел – рекурсивные функции. Например, функция f3(x,y,z)xyz рекурсивна: f3S3fI13S3fI23I33. Неограниченная сумма и произведения if(i)f(0)f(1)…f(i)… и неограниченное произведение if(i)f(0)f(1)…f(i)…, вообще говоря, не рекурсивны. Пусть f(x1,…,xm,i) – заданная (вещественная) функция, vN. Для краткости вместо f(x1,…,xm,i) пишем f(i). Функции ivf(i)f(0)f(1)…f(v1) и ivf(i)f(0)f(1)…f(v1) называются ограниченной суммой и ограниченным произведением соответственно. Теорема 15. Пусть f(x1,…,xn1,v) – рекурсивная функция. Тогда также рекурсивны функции f(v)ivf(i) и f(v)ivf(i). Доказательство. f(0)f(0), f(v)f(v1)f(v); f(0)f(0), f(v)f(v1)f(v). ฀ Операции iv и iv – это новые операторы для построения рекурсивных функций. Кусочно-заданные функции Пусть g1(x), g2(x), …, gm1(x), gm(x) – заданные (вещественные) функции. Напомним, что функция f(x) называется кусочно-заданной, если f(x)g1(x), если xx1, f(x)g2(x), если x1xx2, …, f(x)gm1(x), если xm1xxm, f(x)gm(x), если xxm. Теорема 16. Пусть g1(x), …, gm(x) – рекурсивные функции, P1(x), …, Pm(x) – рекурсивные отношения, из которых ровно одно истинно для любого xN. Тогда также рекурсивна функция f(x), такая, что f(x)g1(x), если P1(x) истинно, ………………………………., f(x)gm(x), если Pm(x) истинно. 22 Доказательство. Если p1(x), …, pm(x) – характеристические функции отношений P1(x), …, Pm(x), то функция f(x)g1(x)p1(x)…gm(x)pm(x) рекурсивна. ฀ Ограниченные кванторы Рассмотрим отношения с ограниченными кванторами. Допустим, что на множестве N определено n-местное отношение P(x1,…,xn1,x). Определим два n-местных отношения (xv)P(x1,…,xn1,x) и (xv)P(x1,…,xn1,x), где vN: подтверждение (xv)P(x1,…,xn1,x) истинно, если P(x1,…,xn1,x) истинно для некоторого значения xv, и ложно, если отношение P(x1,…,xn1,x) ложно для всех значений xv; обобщение (xv)P(x1,…,xm,x) истинно, если истинно P(x1,…,xm,x) для всех значений xv, и ложно, если отношение P(x1,…,xm,x) ложно для некоторого значения xv. Теорема 17. Пусть P(x1,…,xn1,x) – рекурсивное отношение. Тогда отношения подтверждения (xv)P(x1,…,xn1,x) и обобщения (xv)P(x1,…,xm,x) тоже рекурсивны. Доказательство. По условию характеристическая функция p(x1,…,xn1,x) отношения P(x1,…,xn1,x) рекурсивна. Пусть q(x1,…,xn1,v) и r(x1,…,xn1,v) – характеристические функции отношений (xv)P(x1,…,xn1,x) и (xv)P(x1,…,xm,x) соответственно. Тогда: q(x1,…,xn1,v)sgivf(x1,…,xn1,i), r(x1,…,xn1,v)ivf(x1,…,xn1,i). ฀ Ограниченный -оператор Рассмотрим ограниченный -оператор, который применим для построения рекурсивных функций. Пусть на множестве N задано (n1)-местное отношение P(x1,…,xn,y), vN, и если P(x1,…,xn,y) определено для некоторого числа yv, то оно определено и для всех чисел iy. Определим новую n-местную функцию (yv)P(x1,…,xn,y) следующим образом: y(yv)P(x1,…,xn,y) есть наименьшее число yv, такое, что отношение P(x1,…,xn,y) истинно, если для некоторого числа yv отношение P(x1,…,xn,y) истинно; (yv)P(x1,…,xn,y)0, если для всех чисел yv отношение P(x1,…,xn,y) ложно. Теорема 18. Пусть f(x1,…,xn1,y) – рекурсивная функция, и если f(x1,…,xn1,y) определено для некоторого числа yv, то f(x1,…,xn1,i) определено и для всех чисел iy. Тогда функция g(x1,…,xn)(yv)f(x1,…,xn1,y)xn рекурсивна. Доказательство. Мы, без потери общности, считаем, что n1, xnx (параметров нет). Предположим, что f(0)x, f(1)x, …, f(i1)x, f(i)x, где 0iy. Тогда: sg|f(0)x|1, sg|f(1)x|1, …, sg|f(i1)x|1, sg|f(i)x|0, jksg|f(j)x|1, если ki, и jksg|f(j)x|0, если ki; kvjksg|f(j)x|i, sgkvjksg|f(j)x|1. Если f(i)x для всех iy, то sgkvjksg|f(j)x|0. Значит, функция sgkvjksg|f(j)x| является характеристической для функции g. И эта функция рекурсивна, в силу теорем 5, 10 и 15. ฀ Другая форма оператора минимизации Теорема 19. Пусть f(x1,…,xn) – рекурсивная функция, n2. Тогда рекурсивна функция h(x1,…,xn1), такая, что для всех x1,…,xn1,yN, h(x1,…,xn1)yf(x1,…,xn1,y)0. Доказательство. Пусть g(x1,…,xn,xn1)|f(x1,…,xn1,xn1)xn|. Ясно, что g(x1,…,xn,y)0f(x1,…,xn1,y)xn. Тогда yg(x1,…,xn,y)0yf(x1,…,xn1,y)xn. Также из (1) следует, что g(x1,…,xn1,0,xn1)|f(x1,…,xn1,xn1)0|f(x1,…,xn1,xn1). h(x1,…,xn1)yf(x1,…,xn1,y)0yg(x1,…,xn1,0,y)0 (получается из yg(x1,…,xn,y)0 при помощи оператора подстановки и функций проекции и нулевой функции). ฀ 23 Лекция 4. Универсальные функции. Теорема о параметризации Каждой рекурсивной функции h присвоим номер (h)N. Так как определение оператора примитивной рекурсии для одноместной функции использует числа, то каждому числу cN тоже присвоим номер (c)N. Запись zn означает строку, состоящую из n одинаковых цифр z, n0. Значение (h) мы получим в виде строки цифр, которую будем рассматривать как число в десятичной системе счисления. (0)0, (c)1c, если c0, (o)2, (s)3, (Iin)4n5i, (Smgf1…fm1)6m1(g)(f1)…(fm), (Rfg)7(g)(f), (Mf)8(f). По этому определению каждая рекурсивная функция получает свой номер, даже, получает бесконечно много номеров. Например, нулевая функция получит номера 2, 622, 62622, 6262622 и т.д. Не все числа будут номерами рекурсивных функций, например, числа 0, 1, 22, 33, 46, 62, 701, 80, 9. Но для любого числа можно определить является ли оно номером рекурсивной функции, и если является номером (h) рекурсивной функции h, то можно однозначно определить эту функцию h. Нумерацией множества M называется сюръекция F:NM множества N всех натуральных чисел на множество M. Если F(i)a, iN, aM, то мы говорим, что элемент a имеет индекс i, и пишем aai. Элементы множества M можно представить в виде последовательности a0, a1, a2, …, ai, … Пусть теперь n – множество всех n-местных рекурсивных функций. Построим нумерацию множества n. Для каждого числа iN определим функцию F(i)n следующим образом: если i() является номером рекурсивной функции n, то F(i); если i не является номером рекурсивной функции, или i() является номером рекурсивной функции m, mn, то F(i)o. Тогда все n-местные рекурсивные функции представим в виде последовательности 0, 1, 2, …, i, … (1) Последовательность (1) содержит все n-местные рекурсивные функции. Примеры рекурсивных функций с индексами в последовательности (1): 1o, 2o, 3s, 45I11, 6823S2Mos, 704455R0I22o, 82Mo, 83Ms. Вернемся к построению нумерации F множества n всех n-местных рекурсивных функций. Мы указали алгоритм построения функции F, значит, F – вычислимая функция. Однако функция F не является рекурсивной функцией: ее образы – не числа, а функции. Следующее понятие не является нумерацией множества n, но является рекурсивной функцией, определяющей некоторым образом нумерацию функций из n. Пусть C – это счетное множество n-местных рекурсивных функций, т.е. Cn. Определим понятие универсальной функции для класса C. Сечением (n1)-местной функции u (по переменной x) называется n-местная функция ux, xN, такая, что ux(x1,…,xn)u(x,x1,…,xn) для всех x1,…,xnN. Универсальной функцией для класса C называется (n1)-местная числовая функция u, если выполнены следующие 2 условия: 1) xN uxC (класс C содержит любое сечение функции u); 2) fC xN fux (любая функция класса C есть сечение функции u). Значит, сечения универсальной функции представляют собой нумерацию всех рекурсивных функций класса C: Cu0,u1,…,ui,…. 24 Пример. Функция проекции I1n1(k,x1,…,xn) является универсальной функцией для класса всех n-местных постоянных функций ckn(x1,…,xn)k, kN. Понятие универсальной функции введено для рассмотрения нумераций классов всех n-местных примитивно рекурсивных, общерекурсивных и рекурсивных функций. Общерекурсивной функцией называется всюду определенная рекурсивная функция. Теорема 20. Универсальная функция для всех n-местных примитивно рекурсивных (общерекурсивных) функций не является примитивно рекурсивной (общерекурсивной). Доказательство. Пусть некоторая примитивно рекурсивная функция u(x,x1,…,xn) является универсальной функцией для класса всех n-местных примитивно рекурсивных функций. Тогда определим новую n-местную функцию следующим образом: предположим, что g(x1,…,xn)u(x1,x1,…,xn)1 для всех x1,…,xnN. Функция g примитивно рекурсивна, но отличается от каждой n-местной примитивно рекурсивной функции ux хотя бы в одной точке xx1. Значит, примитивно рекурсивная функция не может быть универсальной функцией для класса всех n-местных примитивно рекурсивных функций. ฀ Следующие две теоремы мы рассмотрим без доказательства [1, с.104 и с. 122]. Теорема I. Существует общерекурсивная универсальная функция D(x,x1,…,xn) для класса всех n-местных примитивно рекурсивных функций. Теорема II. Существует рекурсивная универсальная функция U(x,x1,…,xn) для класса всех n-местных рекурсивных функций. Универсальная функция D (теорема I) является примером общерекурсивной, но не примитивно рекурсивной функции. Другой пример – функция Аккермана. Универсальная функция U (теорема II) такова, что все его сечения образуют последовательность всех n-местных рекурсивных функций U0, U1, U2, …, Ui, … (2) где функция Ui, определена следующим образом: Ui(x1,…,xn)U(i,x1,…,xn), i,x1,…,xnN. Обе последовательности (1) и (2) являются нумерациями множества n, обе последовательности можно применить при построении невычислимых функций, но при применении последовательности (2) используется, что универсальная функция рекурсивна. Каждое из сечений fx, xN, вычислимой функции f является также вычислимой функцией. Значит, существует номер iN, такой, что fxui. Следующая теорема показывает, что номер i можно эффективно вычислить по x. Следующую теорему мы рассмотрим без доказательства [2, с.88]. Теорема о параметризации. Пусть f(x,t) – рекурсивная функция. Тогда существует общерекурсивная функция s(x), такая, что f(x,t)Us(x)(t) для любых x,tN. Эта теорема может быть обобщена [2, с.90]: s-m-n – теорема. Для всех m,n1 существует общерекурсивная (m1)-местная функция s, такая, что Ui(x1,…,xm,y1,…,yn)Us(i,x1,…,xm)(y1,…,yn). Теорема 21. Пусть P(x,x1,…,xn) – разрешимое отношение, s(x) – общерекурсивная функция. Тогда отношение P(s(x),x1,…,xn) тоже разрешимо. Доказательство. Пусть p(x,x1,…,xn) – характеристическая функция отношения P(x,x1,…,xn), а q(x,x1,…,xn) – характеристическая функция отношения P(k(x),x1,…,xn). Ясно, что q(x,x1,…,xn)p(s(x),x1,…,xn). Если функция p(x,x1,…,xn) рекурсивна, то функция q(x,x1,…,xn) тоже рекурсивна, так как qSn2pS2kIn11In12…In1n1. ฀ В силу теоремы 22, если s(x) – всюду определенная рекурсивная функция, то из неразрешимости проблемы P(s(x)) следует неразрешимость проблемы P(x). 1. Мальцев А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. – 2-е изд. – М.: Наука, 1986. – 368 с. 2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд. – М.: Мир, 1983. – 256 с. 25 Лекция 5. Невычислимые функции. Неразрешимые проблемы Применим нумерацию (1) к построению невычислимой функции. Для краткости, без потери общности, будем считать, что n1, т.е. допустим, что (1) – последовательность всех одноместных рекурсивных функций. Теорема 19. Существует невычислимая числовая функция. Доказательство. Определим новую числовую функцию : (x)x(x)1, если x(x) определено; (x)0, если x(x) не определено. Функция  отличается от каждой функции i в последовательности (1). Действительно, (x)i(x) хотя бы в точке xi: либо значения (i)i(i)1 и i(i) не совпадают, либо (i) определено, а i(i) не определено. Поскольку все рекурсивные функции принадлежат (1), то  не является рекурсивной функций. В силу тезиса Чёрча,  не является вычислимой функцией. ฀ Задача, в которой доказывается, что некоторое отношение неразрешимо, называется также неразрешимой проблемой. Применим нумерацию (1) к доказательству неразрешимости проблем. Теорема 22. Проблема "x(y)0", x,yN, неразрешима. Доказательство. 1) Вначале рассмотрим проблему "x(x)0". Предположим, что отношение "x(x)0" разрешимо, т.е. следующая функция p(x) рекурсивна: p(x)1, если x(x)0; p(x)0, если x(x)0. В силу предположения, pi для некоторого индекса iN. Тогда: если i(i)0, то p(i)1, i(i)1; если i(i)0, то p(i)0, i(i)0. Получается противоречие: i(i)0 и i(i)0. Значит, проблема "x(x)0" неразрешима. 2) Теперь рассмотрим проблему "x(y)0". Предположим, что отношение "x(y)0" разрешимо, т.е. следующая функция q(x) рекурсивна: q(x,y)1, если x(y)0; q(x,y)0, если x(y)0. Тогда функция p(x)q(x,x) рекурсивна: pS3qI11I11. Это противоречит пункту 1. Значит, проблема "x(y)0" неразрешима. ฀ Теорема 22 показывает, что невозможно написать программу, которая для каждой одноместной вычислимой функции f и для каждого числа xN определяла бы f(x)0 или нет. Для отдельно взятой функции i(n) отношение "i(n)0" может быть разрешимым. Для любой всюду определенной функции, например, для нулевой функции отношение "o(n)0" разрешимо. Теорема 23. Проблема "x(y) определено", x,yN, неразрешима. Доказательство. 1) Вначале докажем, что проблема «x(x) определено» неразрешима. Предположим, что отношение «x(x) определено» разрешимо, т.е. рекурсивна его характеристическая функция p(x): p(x)1, если x(x) определено; p(x)0, если x(x) не определено. Чтобы получить противоречие, рассмотрим функцию p(x). Эта функция рекурсивная, она формально получается как композиция двух рекурсивных функций Mo и p, т.е. p(x)Mo(p(x)), или, pS2Mop. Значит, функция p рекурсивна, принадлежит последовательности (1), и pi для некоторого индекса iN. Тогда: 26 если i(i) определено, то p(i)1, i(i)p(i)1, i(i) не определено; если i(i) не определено, то p(i)0, i(i)p(i)0, i(i) определено. Получается противоречие: i(i) определено и i(i) не определено. Значит, проблема "x(x) определено" неразрешима. 2) Теперь докажем, что проблема "x(y) определено" неразрешима. Предположим, что отношение "x(y) определено" разрешимо, т.е. рекурсивна его характеристическая функция q(x): q(x,y)1, если x(y) определено; q(x,y)0, если x(y) не определено. Тогда функция p(x)q(x,x) рекурсивна: pS3qI11I11. Это противоречит пункту 1. Значит, проблема «x(y) определено» неразрешима. ฀ Теорема 23 показывает, что невозможно написать программу, которая для каждой одноместной вычислимой функции f и для каждого числа xN определяла бы f(x) определено или нет. Для отдельно взятой функции i(n) отношение "i(n) определено" может быть разрешимым. Для любой всюду определенной функции, например, для нулевой функции отношение "o(n) определено" разрешимо. Применим теорему II и теорему о параметризации для доказательства теорем неразрешимости. При этом сечения Ux универсальной функции U будем обозначать x, xN (с целью для удобства последовательного изложения проблем неразрешимости). В следующей теореме две проблемы неразрешимости одинаково доказываются. Теорема 24. Следующие две проблемы неразрешимы: 1) «x – нулевая функция»; 2) «x – всюду определенная функция». Доказательство. Функция f(x,y)o(x(x)), x,yN, рекурсивная: fS2oS3UI21I21. По теореме о параметризации f(x,y)k(x)(y) для некоторой общерекурсивной функции k(x). Если x(x) определено, то f(x,y)0 для всех yN, k(x)(y)0 для всех yN, значит, k(x)o [k(x) – всюду определенная функция]. Если x(x) не определено, то f(x,y) не определено для всех yN, k(x)(y) не определено для всех yN, значит, k(x)o [k(x) – не всюду определенная функция]. Значит, x(x) определено  k(x)o [k(x) – всюду определенная функция]. Так как отношение «x(x) определено» неразрешимо в силу теоремы 21, то отношение «k(x) – нулевая функция» [«k(x) – всюду определенная функция»] тоже неразрешимо. Отсюда, в силу теоремы 21, следует, что отношение «x – нулевая функция» [«x – всюду определенная функция»] тоже неразрешимо. ฀ Теорема 24 показывает, что невозможно написать программу, которая для каждой одноместной вычислимой функции f определяла бы: 1) f – нулевая функция или нет; 2) f – всюду определенная функция или нет. 27 Лекция 6. Вычислимые по Тьюрингу функции Машина Тьюринга – это абстрактная вычислительная машина, является уточнением понятия алгоритма. Машина Тьюринга состоит из ленты, исполнителя, внешнего алфавита A, множества внутренних состояний Q и программы. Лента разделена на ячейки и бесконечна в обе стороны. Каждая ячейка может быть заполнена не более чем одним символом из алфавита A. Число заполненных ячеек конечно. Внешний алфавит A содержит конечное множество символов: A{a0,a1,…,am}. Один из символов (например, a0) алфавита A используется для обозначения пустой ячейки. Машина Тьюринга имеет конечное множество внутренних состояний: Q{q0,q1,…,qn}. Один из состояний (например, q0) называется заключительным. Исполнитель в каждый момент дискретного времени наблюдает за одной из ячеек, считывает символ ячейки, может менять символ в ячейке и двигаться влево или вправо вдоль ленты на одну ячейку. Программа машины Тьюринга – это конечный список команд машины Тьюринга. Каждая команда машины Тьюринга является упорядоченной четверкой вида qiaj*ql, где * есть один из символов ak, L, R, далее, i,j,k,lN, i0, aj,akA, qi.qlQ, L, R – символы направления движения (налево, направо). Главное условие в программе машины Тьюринга: для каждой пары qiaj существует не более одной команды вида qiaj*ql. В каждый момент времени машина находится в состоянии qi, а исполнитель считывает символ aj с некоторой ячейки и выполняет команду qiaj*ql. Заменяет в ячейке символ aj на символ ak, если * есть ak, или двигается вдоль ленты на одну ячейку влево или вправо, если * есть соответственно L или R. Машина переходит в состояние ql. В настоящее время используются команды машины Тьюринга в виде упорядоченных пятерок qiajakDql, где D есть один из символов S (на месте), L, R. Машинное слово – это строка s1...sn из символов, расположенных последовательно на ячейках некоторого отрезка ленты, содержащего все заполненные ячейки. Конфигурация машины Тьюринга – это слово вида s1...qisj...sn, где s1...sj...sn – машинное слово, а qi –внутреннее состояние машины в данный момент времени. Символ qi расположен слева от символа sj, считываемого исполнителем в данный момент времени. При этом машина выполняет команду, начинающуюся с пары qisj, и переходит к следующей конфигурации, согласно следующим правилам: конфигурация до применения команда конфигурация после применения команды команды qiajakSql s1...smqiajsm2...sn s1...smqiaksm2...sn qiajakLql s1...smqiajsm2...sn s1...qismqiaksm2...sn qiajakRql s1...smqiajsm2...sn s1...smakqism2...sn qiajakLql qiajsm2...sn qia0aksm2...sn s1...smqiaj s1...smakqia0 qiajakRql Рассматривают три типа основных задач на машине Тьюринга: 1) вычисление функций в непозиционной единичной системе счислении; 2) вычисление функций в позиционных b-ичных системах счислении (q2); 3) преобразование слов в некотором алфавите. В единичной системе счисления число mN представляется в виде строки 1m, состоящей из m единиц. Числовая n-местная функция f(x1,x2,…,xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая в процессе вычисления начальную конфигурацию q11x11_1x21_…_1xn1: либо преобразует в конфигурацию q01y1 (останавливается в заключительном состоянии) тогда, когда значение f(x1,…,xn) определено и равно y; либо останавливается не в заключительном состоянии (нет команды для очередной конфигурации!) или не останавливается тогда, когда значение f(x1,…,xn) не определено. 28 Лекция 7. Невычислимые по Тьюрингу функции. Проблема остановки Рассмотрим все машины Тьюринга, у которых: 0, 1 – внешние символы, l, r, sn – символы, обозначающие движение, q0, q1, q2, … – символы, обозначающие внутренние состояния. Каждая машина Тьюринга однозначно определяется программой, состоящей из 2s команд – пятерок вида aiqjakdql, где ai{_,1}, qj{q1,…,qm,…}, d{l,r,s}, ak{0,1}, ql{q0,q1,…,qm,…}, причем, в некоторых командах тройка akdql отсутствует (пустая клетка в табличной форме программы, обозначенная ). Программу машины Тьюринга представим в виде следующей последовательности: 1q1a11D11q110q1a21sD21q211q2a12D12q120q2a22D22q22…1qsa1sD1sq1s0qsa2sD2sq2s. (1) Каждому символу из множества A{0,1,L,R,S,,q0,q1,q2,…} присвоим номер: символ q0 q1 … … _ 1 qm L R S  m номер 2 3 … 3 …. 1 4 5 6 7 Каждому слову в алфавите A присваивается номер по следующему правилу: если символы b1, b2, …, bt имеют номера u1, u2, …, ut, то слову b1b2…bt присваивается номер u1u2…ut. Последовательность (1) тоже получает номер i, тем самым, если программа машины T получает номер i, то и машина T будет с номером (индексом) i: TTi. Пример. Пусть машина Тьюринга T вычисляет нулевую функцию: q1 q2 1 1Rq2 _Rq2 _ _Sq0 Тогда: TT1315330371330533033062. Построенная нами нумерация машин Тьюринга является не всюду определенным, но является взаимно однозначным, отображением. Чтобы преобразовать нумерацию во всюду определенную и взаимно однозначное отображение, для числа i, не являющегося его индексом никакой машины, будем считать, что Ti вычисляет нулевую функцию. Теперь, можно построить нумерацию n-местных вычислимых по Тьюрингу функций. Определим n-местную функцию i, n0, следующим образом. Допустим, что машина Ti начинает работу с начальной конфигурации q11x11_…_1xn1. Тогда: i(x1,…,xn)y, если Ti останавливается с заключительной конфигурацией q0y, i(x1,…,xn) не определено, если Ti не останавливается или останавливается не в заключительном состоянии q0. Пример функции, невычислимой по Тьюрингу Определим новую n-местную функцию  следующим образом: (i,x2,…,xn)i(i,x2,…,xn)1, если i(i,x2,…,xn) определено, (i,x2,…,xn)0, если i(i,x2,…,xn) не определено. Теорема 25. Функция  невычислимая. Доказательство (диагональный метод). Так как последовательность T0, T1, T2, … содержит все машины Тьюринга (необходимых для определения функций, вычислимых по Тьюрингу), то последовательность 0, 1, 2, … содержит все n-местные вычислимые 29 по Тьюрингу функции. Функция  по своему определению отличается от каждой функции i хотя бы в точке (i,x2,…,xn). Значит, функция  является невычислимой по Тьюрингу функцией. В силу тезиса Тьюринга, функция  является невычислимой функцией. ฀ Неразрешимость проблемы самоприменимости Определим функцию f(x) следующим образом: f(x)1, если машина Tx с начальной конфигурацией q11x1 останавливается, f(x)0, если машина Tx с начальной конфигурацией q11x1 не останавливается. Проблема самоприменимости. Является ли функция r(x) вычислимой? Теорема 26. Функция f(x) является невычислимой по Тьюрингу. Доказательство. Допустим, что машина T с внутренними состояниями q0, q1, …, qm определяет применимость машины с индексом x к числу x, т.е. вычисляет функцию f(x). Она останавливается на конфигурации q011, если машина Tx останавливается при входе x, и останавливается на конфигурации q01, если машина Tx не останавливается при входе x. Построим новую машину Тьюринга T, которая совпадает с машиной T, кроме следующих исключений: добавляются новые внутренние состояния qm1 и qm2; в командах программы машины T состояние q0 заменяется на qm1; в программу машины T добавляются команды 1qm11Rqm2, 1qm21Sqm2, 0qm20Sq0. Машина T, как все машины Тьюринга, имеет некоторый номер z, т.е. TTz. Допустим, что машина TTz останавливается при входе z. Тогда: а) машина T останавливается на конфигурации q011; б) машина TTz останавливается на конфигурации qm111; в) по команде 1qm11Rqm2, машина TTz останавливается на конфигурации 1qm21; г) бесконечно выполняется команда 1qm21Sqm2, машина TzT не останавливается. Допустим, что машина TTz не останавливается при входе z. Тогда: а) машина T останавливается на конфигурации q01, б) машина TTz останавливается на конфигурации qm11; в) по команде 1qm11Rqm2, машина TTz останавливается на конфигурации 1qm2; г) по команде 0qm20Sq0, машина TzT останавливается на конфигурации 1q0. В любом случае получается, что машина TzT одновременно останавливается и не останавливается, что есть противоречие. Полученное противоречие показывает, что машины T, вычисляющей функцию f(x), не существует. ฀ Неразрешимость проблемы остановки Определим функцию g(x,y) следующим образом: g(x,y)1, если машина Tx с начальной конфигурацией q11y1 останавливается, g(x,y)0, если машина Tx с начальной конфигурацией q11y1 не останавливается. Теорема 27. Функция g(x,y) является невычислимой по Тьюрингу. Доказательство. Допустим, 2) Если бы была вычислима функция g(x,y), то была бы вычислима и функция f(x)g(x,x). Лекция 8. Меры сложности алгоритмов Меры сложности машины Тьюринга Временной сложностью машины T называется функция tT(x), или t(x), xN, равная числу шагов машины T, сделанных в процессе работы машины T при входе x. Емкостной сложностью машины T называется функция sT(x), или s(x), xN, равная числу ячеек ленты машины T, посещаемых в процессе работы машины T при входе x. Допустим, что функция f(x) вычисляется машиной T, а t(x) и s(x) – временная и емкостная сложности, оп30 ределяемые для машины T при вычислении функции f(x). Нам понадобится понятие графика h функции h: h{(x,y)|yh(x)}. Отметим свойства, общие для функций сложности: (B1) для любого xN функции сложности t(x) и s(x) определены тогда и только тогда, когда определена функция f(x); (B2) графики t и s функций сложности t(x) и s(x) являются разрешимыми множествами, а график f вычислимой функции f(x) является только перечислимым множеством. Напомним, что множество ANN:  разрешимо, если существует вычислимая функция p(x,y), x,yN, равная 1, если (x,y)A, и равная 0, если (x,y)A;  перечислимо, если существует вычислимая функция p(x,y), x,yN, равная 1, если (x,y)A, и неопределенная, если (x,y)A, Абстрактная мера сложности и машинно-независимые теоремы Пусть f(x1,…,xn)i(x1,…,xn), iN, – произвольная функция из последовательности всех вычислимых по Тьюрингу n–местных функций. Для краткости, пусть будет n1, т.е. рассмотрим функцию f(x)i(x), iN. Функция t называется абстрактной мерой сложности семейства функций f, если выполнены аксиомы Блюма (B1) и (B2). Временная и емкостная сложности машин Тьюринга являются абстрактными мерами сложности (удовлетворяют аксиомам Блюма). Многие свойства сложности вычислимых функций не зависят вида вычисляющих их машин, программ или алгоритмов. Результаты о мерах сложности, которые выводятся из свойств вычислимых функций и аксиом Блюма, называются машинно-независимыми. Чтобы доказать машинно-независимые теоремы, используются:  нумерация i всех рекурсивных функций;  теорема о существовании универсальной функции для класса функций i;  теорема параметризации (или s-m-n-теорема);  две аксиомы Блюма. Далее через ti(x) обозначим меру сложности функции f(x), если f(x)i(x). Говорят, что f(x)g(x), xN, почти всюду, если существует x0N, такое, что для всех xN, из xx0 следует f(x)g(x). Приведем без доказательства две машинно-независимые теоремы о сложности. Следующая теорема показывает, что существуют произвольно сложные вычислимые функции [2, стр. 224]. Теорема о верхней границе сложности. Пусть b(x) – всюду определенная вычислимая функция. Тогда существует всюду определенная вычислимая функция f(x), принимающая только значения 0,1, такая, что ti(x)b(x) почти всюду. Для любой рекурсивной функции есть бесконечно много машин Тьюринга, ее вычисляющих. Некоторые рекурсивные функции настолько каверзные, что любой вычисляющей их машине требуется очень длительное время. Это значит, верхняя граница меры сложности может быть больше почти всюду любой общерекурсивной функции. Следующая теорема утверждает, что существует функция, которая не обязана иметь самый быстрый индекс. Теорема ускорения Блюма. Для всякой общерекурсивной функция r(x) существует общерекурсивная функция f(x) со значениями 0,1, которая вычисляется машиной Тьюринга Ti, и для которой найдется машина Тьюринга Tj, вычисляющая тоже функцию f(x), такая, что r(tj(x))ti(x) для всех xx0 для некоторого числа x0. Если, например, r(x)2x, то запись 2tj(x)ti(x) означает, что для любой машины, вычисляющей f(x), существует другая машина, вычисляющая f(x), экспоненциально быстрее почти для всех входов. 31 Классы сложности алгоритмов Классы задач, решаемых за полиномиальное время. Рассмотрим функции вида f:VB, где V – множество слов в данном алфавите, а B1,0. Допустим, что функция f вычисляется машиной Тьюринга T. Сложность функции f определяется как функция CT(n) от nN: CT(n)max{tT(v)|длина слова v равна n}, где tT(v) – число шагов, сделанных машиной T, вычисляющей значение f(v), максимум берется на множестве всех слов из V длины n. Алгоритмическую задачу можно представить функцией вида f:VB. Задача входит в класс P, если найдется машина Т и найдется полином P(n), такая, что CT(n)P(n) для всех nN. Примеры задач из класса P: сложение, умножение, деление, взятие остатка от деления, умножения матриц, нахождение эйлерова цикла на графе. В класс NP входят задачи, ответы на которые проверяются за полиномиальное время, но не решаемые за полиномиальное время. Ясно, что PNP. PNP – важная нерешенная проблема. Лекция 9. Машина Поста. Нормальные алгоритмы Маркова. Машины с неограниченными регистрами. 9.1. Машины Поста функции, вычислимые по Посту. В машине Поста имеется лента, разбитая на ячейки, и бесконечная в обе стороны, а также каретка, способная считывать символ с обозреваемой ячейки, заменять этот символ и двигаться вдоль ленты на одну ячейку вправо или влево. Каждая ячейка ленты либо пустая, либо содержит символ 1. Мы считаем, что пустая ячейка содержит символ 0. Записывать символ 0 – это значит стереть с ячейки символ 1. Программа состоит из пронумерованных команд. Команды рассматриваем следующих пяти видов:  i (переместить каретку вправо и перейти к команде с номером i);  i (переместить каретку влево и перейти к команде с номером i); 0i (записать в обозреваемую ячейку 0 и перейти к команде с номером i); 1i (записать в обозреваемую ячейку 1 и перейти к команде с номером i); ?i,n (если текущая ячейка содержит 0, то перейти к команде с номером i, иначе перейти к команде n; . (остановить программу). Номер команды перехода в командах , , 0 и 1 можно не указывать, при этом происходит переход к следующей команде. Работа начинается с выполнения команды с номером 1, останавливается с результатом для команды с точкой и без результата для невыполнимой команды. Числовая n-местная функция f(x1,…,xn) называется вычислимой по Посту, если существует машина Поста, которая слово на ленте 11..10...011…1 (слова из меток 1 состоят соответственно из x11,…,xn1 меток 1): преобразует в слово из y1 меток 1, если f(x1,…,xn) определено и равно y, останавливается без результата или не останавливается, если f(x1,…,xn) не определено. Пример 1. Программа Поста для вычисления функции сигнума sg(x): 1 5 ? 6,7  2 ? 3,4 6 . 3 . 7 0,4 4  32 Пример 2. Программа Поста для вычисления сложения xy: 1 ? 3,2 6  2 7 1 3 1 8  4 ? 6,5 9 5 10 . 4 9.2. Нормальные алгоритмы Маркова. Нормальный алгоритм Маркова (НАМ) над конечным алфавитом V состоит из подстановок (команд) двух видов: ab и ab. (a,bV). Оба вида подстановок объединяются в следующем обозначении: ab(.). Программа НАМ представляет собой конечный список подстановок: a1b1 (.); a2b2 (.); ………… anbn (.). На вход подается слово u в алфавите V, которое преобразуется подстановками программы. Допустим, что слово u преобразовано (пока) в слово u в алфавите V. Если в u не содержит ни одного из вхождений a1, …, an, то программа останавливается с результатом в u. Предположим, что aibi (.) первая из подстановок программы, для которой ai входит в u (i1,…,n). Тогда первое вхождение ai в u заменяется на bi. Если эта постановка с точкой, то программа останавливается с полученным результатом. Иначе этот процесс продолжается. Некоторые из ai и bi могут быть пустыми. Пример 3. НАМ для вычисления функции сигнума sg(x): 1 b1b 2 a1b 3 1a 4 a1. 5 b11. Пример 4. НАМ для вычисления сложения xy: 1 a*a 2 a11a 3 a. 4 1a 9.3. Машины с неограниченными регистрами. МНР – это лента, бесконечная в одну сторону и разбитая на ячейки, которые называются регистрами и обозначаются R1,R2,… Каждый регистр содержит некоторое неотрицательное целое число. Содержимое регистра Rn обозначается rn, причем, только в конечном числе регистров rn0. Программа МНР – это конечный список команд I1,I2,…,Is 4-х видов: команда обнуления Z(n) (по этой команде rn:0), команда прибавления единицы S(n) (по этой команде rn:rn1), команда переадресации T(m,n) (по этой команде rn:rm), команда условного перехода J(m,n,q). Работа МНР начинается с выполнения команды I1. Допустим, что МНР выполняет команду Ik, k1,2,…,s. Если Ik одна из трех т.н. арифметических команд Z(n), S(n) или T(m,n), то МНР меняет соответствующим образом содержимое регистра Rn и переходит к следующей команде Ik1. Если же IkJ(m,n,q), то МНР при rnrm переходит к команде Iq и 33 при rnrm переходит к следующей команде Ik1. МНР останавливается тогда, когда нет команды для выполнения. Конфигурацией МНР называется слово, составленное из символов на регистрах ленты, включая все ненулевые символы. Функция f(x1,…,xn) называется вычислимой МНР, если существует МНР, которая, начиная работу с конфигурацией x1…xn000…, останавливается с конфигурацией y…, если f(x1,…,xn) определено и равно y, и не останавливается, если f(x1,…,xn) не определенно. Пример 5. Программа МНР для вычисления функции сигнума sg(x): команды конфигурации 0000 (x1)000 I1 J(1,2,4) 0000 (x1)000 I2 Z(1) 0000 I3 S(1) 1000 Пример 6. Программа МНР для вычисления сложения xy: команды конфигурации x000 xy00 I1 J(2,3,5) x000 xy00 … (x1)y10 (xy1)y10 (xy)yy0 I2 S(1) … (x1)y00 (x2)y10 (xy)y(y1)0 I3 S(3) … (x1)y10 (x2)y20 (xy)yy0 I4 J(1,1,1) … (x1)y10 (x2)y20 (xy)yy0 34