Введение в математическую логику и теорию алгоритмов Лекция 3 Алексей Львович Семенов

План Логика высказываний Структуры Логика отношений Что значит определить отношение? Примеры определимости Пространства определимости 2

3 Логика высказываний (повт.) Построение сложных высказываний из простых Для простых – существенна только их истинность. О чем высказывания – не существенно и не видно. Значение сложного высказывания (формулы) определяется значением его частей. В конце концов – «атомных» высказываний.

4 Синтаксис логики высказываний (повт.) Индуктивное определение (построение) формулы Л огические константы 0 и 1 – формулы. И мена высказываний А 1, А 2,… – формулы. (Номера начинаются с 1.) Если Ф, Ψ – формулы, – связка: (конъюнкция), (дизъюнкция), (импликация), (эквивалентность), то Ф, (Ф Ψ) – формулы.

5 Семантика логики высказываний (повт.) Индуктивное определение (вычисление) значения формулы в (при) заданной интерпретации B N. 1. Значением логической константы является она сама. 2. Значением имени высказывания A i является i. 3. Значением: - формулы является отрицание значения, т.е. Зн = 1 - Зн. - формулы ( ), где,,,, является (заданный таблично) результат применения к значениям формул,. Значение формулы – функция B N B. Если наибольший номер переменной в формуле равен n, то формула задает функцию B n B.

6 Построение формулы логики высказываний по булевой функции (решение задачи) В длинной конъюнкции и дизъюнкции будем опускать скобки. i, i аналогично выражениям a i, a i, если формула – одна, то выражение совпадает с ней, если последовательность пустая: = 0, = 1. Где функция, задаваемая формулой А 1 А 2 А 3, равна 1? - Только при значении =. Фиксируем натуральное число n. Обозначения: = 1, …, n ; A = A 1, …, A n, (0, A i ) = A i (1, A i ) = A i (, A) = ( i, A i ) Теорема о совершенной дизъюнктивной нормальной форме. Всякая функция f : B n B задается формулой: (, A) по всем, для кот орых f ( ) = 1 (если пусто, то 0) Это – СДНФ. ( Д.Н.Ф. …)

7 Отношения (повт.) Множество D – область. n-местное отношение (n-местное свойство) на D – любое подмножество в D n, при n = 0 – логическая константа. N-местное (бесконечноместное) отношение – подмножество в D N. Отношение – отображение (характеристическая функция) D в B = {0,1}. Примеры 2-местное отношение равенства – множество всех пар, x D. Отношения на натуральных числах: следования y = x+1 порядка x < y сложения x + y = z

8 Логика отношений Синтаксис. 1. Начало Последовательность (обыкновенно, но не обязательно, конечная) имен отношений Pr = {P 1, P 2, …}, каждому имени сопоставлено его количество аргументов. Сигнатура =, или конечный отрезок Pr. Часто используются также имена операций (функций), можно сводить функции к отношениям, см. выше. В последней части лекции мы вернемся к операциям. Семантика 1. Начало Структура данной сигнатуры – это набор, где Зн ставит в соответствие каждому имени отношения некоторое отношение на D (с нужным числом аргументов).

9 Примеры структур Семантика и синтаксис Упорядоченное множество рациональных чисел: Q Q, {

10 Логика отношений Синтаксис 2. Продолжение Фиксируем последовательность свободных переменных FVar = x 1, x 2,… Атомные формулы Если P – имя n-местного отношения и t 1, …, t n – свободные переменные, то P(t 1,…,t n ) – атомная формула. (Если P – имя 0-местного отношения, то P – атомная формула.) Если t 1, t 2 – свободные переменные, то t 1 = t 2 – атомная формула. Примеры: P 2 (x 1, x 2, x 2 ), x 3 = x 5, P 3 – атомные формулы, если P 2 – имя трехместного отношения, а P 3 – имя 0-местного отношения.

11 Логика отношений. 2. Атомные формулы Семантика 2. Продолжение Пусть задана структура:, здесь Зн определена на символах отношений из, и интерпретация = 1, 2,... из D N. Зн свободной переменной – это элемент D: Зн x i = это i Зн атомной формулы – элемент B. - Зн P(t 1, …, t n ) – применяем Зн P к Зн t 1, …, Зн t n. -Зн t 1 = t 2 – совпадение Зн t 1 и Зн t 2. Значение атомной формулы в данной структуре – это отображение D N B, то есть N-местное отношение, принимает все возможные значения; если наибольший номер переменной в формуле равен n, то с атомной формулой сопоставляется n-местное отношение.

12 Логика отношений. 3. Бескванторные синтаксис и семантика Формула (заданной сигнатуры), индуктивное определение: Атомные формулы – формулы. Если, - формулы,,,,, то ( ), ( ) – формулы. Семантика. Пусть задана структура: и интерпретация = 1, 2,… из D N. Зн формулы определяется индуктивно. Зн атомной формулы P(t 1, …, t n ) – было. Зн( ), где,,,, – это результат применения к Зн, Зн. Зн = 1- Зн … Значение формулы – отображение D N в B. Далее мы определим формулы с кванторами и семантику для них.

13 Примеры (задачи): Упорядоченное множество рациональных чисел: Q Q, { > }, Зн Зн – обычное. Как наглядно представить: (x y) (x y y>z) (x

Как определить семантику формул с кванторами? Кванторы: – квантор всеобщности, «для всех» – квантор существования, «существует» Нужно «подставить все возможные значения вместо переменной x». Трудность: z (x

15 Логика отношений Замена: A [ u / x ] означает результат замены в слове A всех вхождений символа x на слово u (если x не входит в A, то результат – A). Синтаксис 3. Окончание Фиксируем упорядоченный алфавит связанных переменных BVar =. Формула (заданной сигнатуры), индуктивное определение: Атомные формулы – формулы. Если, – формулы,,,,, то, ( ) – формулы. Если – формула, x – свободная переменная (x FVar), u – связанная переменная (u BVar), не входящая в, то ( u [u/x]), ( u [u/x]), – формулы (в эти формулы x не входит). Анализ. Тонкость – восстановление свободной переменной – берем первую не использованную. Сокращения. Опускание внешних скобок Вместо u v пишем u,v

16 Логика отношений Семантика 3 (окончание построения). Пусть задана структура: и интерпретация = 1, 2,… из D. Зн формулы B определяется индуктивно. Зн атомной формулы P(t 1, …, t n ) – было. Зн( ), где,,, – результат применения к Зн, Зн. Зн = 1 - Зн. Зн u [u/x i ] = Зн по всем, совпадающи м с на всех местах, кроме i–го. ( В осстановление, т.е. x i, по кванторной формуле – см. выше. )

17 Логика отношений Задана структура M =. Значение формулы зависит только от значений ее (свободных) переменных (соответствующих членов последовательности ). Если все свободные переменные имеют номера, не более n, то выражает n-местное отношение на D. Это отношение определимо (или выразимо) в M. Задача изучения отношений, определимых в данной структуре

18 Примеры определимых отношений Структура, +, × - натуральные числа, сложение, умножение. x – чётное число y (x=y+y) x =1 y (x × y = y) x делит y z (y = x × z) x < y z (y = x + z) (y = x) Ост (x, y) = v (0 v < y) t (x = y × t + v )

19 КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ (Сунь Цзы, IV век до н.э., исследование календаря, «Искусство войны») Т. Пусть u 1, …, u n – попарно взаимно простые натуральные числа, и пусть v 1, …,v n – такие натуральные числа (остатки), что 0 v k < u k для всех k. Тогда найдётся p такое, что 0 p < u 1 …u n и Ост(p, u k ) = v k для всех k. Д. Количество возможных цепочек остатков v 1, …, v n равно u 1 …u n, то есть количеству таких чисел p, что 0 p < u 1 …u n. Разные числа из указанного диапазона дают разные цепочки остатков, значит, каждая цепочка остатков встречается (и ровно один раз). (Пусть p и q дают одинаковые цепочки остатков, тогда их разность делится на все u k, а в силу взаимной простоты чисел u k, и на их произведение u 1 …u n.)

20 Кодирование цепочек чисел Как можно кодировать цепочки чисел с помощью чисел? (Или, хотя бы, с помощью цепочек ограниченной длины.) Китайская теорема об остатках. Чтобы получить цепочку из n чисел, используется число p, которое и оказывается кодом. Нужна какая-нибудь цепочка из n попарно взаимно простых чисел. Как ее получить без того, чтобы не вернуться к кодированию произвольных цепочек?

21 Кодирование цепочки чисел Попробуем взять в качестве u i арифметическую прогрессию: u i = y i +z, где i = 1,… n. Задача. Подобрать y, z чтобы обеспечить взаимную простоту. v 1, …,v n найдутся такие p (из китайской теоремы), y (разность прогрессии), что v i является остатком от деления p на 1+y(1+ i ). Обозначим β (x, y, i ) = Ост(x, 1+y(1+ i )). Бета-функция Гёделя

22 Кодирование цепочки чисел Удобно кодировать вместе с элементами цепочки и её длину. Её можно ставить в начале цепочки. Итак, для любого набора натуральных чисел v 1, …,v n можно подобрать числа x, y такие, что β (x, y, 0) = n, β (x, y, 1) = v 1, β (x, y, 2) = v 2, … β (x, y, n) = v n. Чем это может нам помочь при определении «естественных» отношений?

23 Определимость отношений Задача. Отношение m = 2 n определимо? Найдётся цепочка длины n, первый элемент которой 1, каждый следующий вдвое больше предыдущего, а последний – это m… Задача. Все функции, вычислимые алгоритмами, определимы…

24 Пространства определимости Фиксируем множество D. Множество отношений R. Дадим всем отношениям из R имена из, то есть зададим Зн. Структура S =. Множество всех отношений, определимых в структуре S, назовем замыканием R. Замыкание C(R) определяется R (а не выбором имен). CC(R) = C(R). Замкнутое множество – совпадающее с замыканием, пространство определимости.

25 Алгебра пространств определимости Замыкание монотонно по включению множеств. Задача. Пересечение пространств – замкнуто. Объединение пространств = замыкание теоретико-множественного объединения.

26 Операции Имена операций Алфавит имен объектов Ob={a 0, a 1, a 2,… } Задача. Определить термы – выражения… Задача. Построить синтаксис и семантику для термов. Задача. Построить синтаксис и семантику для логики отношений и операций.

27 Логика отношений Замкнутая формула – формула без свободных переменных. Фиксируем структуру. Замкнутая формула истинна (Зн = 1) или ложна (Зн = 0) в данной структуре. Множество истинных замкнутых формул – теория структуры. Для теории структуры может существовать алгоритм выяснения истинности. Логику отношений часто называют логикой предикатов.

28 Просеминар по математической логике и информатике пятница, 16:45–18:20, аудитория 16–22 3 октября