Доказательство свойств формул по индукции

Предмет математической логики

Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, по-существу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения – единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями.

Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику.

Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина – ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика'').

Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.

Формальная система определена, если:

1. Задан алфавит (множество символов, используемых для построения формул).
2. Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).
3. Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.
4. Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.

Пример формальной системы

Рассмотрим пример простой, ``игрушечной'' формальной системы.

Пример формальной системы. Популярная формальная система (DH) определяется следующим образом:

1. Алфавит: {M,I,U}.
2. Формулы: любая последовательность символов данного алфавита.
3. Одна аксиома: MI.
4. Правила вывода:
• правило 1: из формулы вида mI можно получить mIU.
• правило 2: из формулы вида Mm можно получить Mmm.
• правило 3: подстроку III можно заменить на U.
• правило 3: подстроку UU можно заменить на пустую строку.

символом m в первом и во втором правиле обозначается произвольное слово.

Приведём пример построения вывода:

MI (аксиома), MII (правило 2), MIIII (правило 2), MIIIIU (правило 1), MIUU (правило 3), MI (правило 4).

Определите, можно ли получить формулу MU с помощью правил вывода из аксиомы.



Структура раздела

Раздел ``математическая логика'' состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка).

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

По поводу используемой нотации. Текст построен на последовательности задач. Большинство задач состоит в доказательстве некоторых утверждений. Для некоторых задач имеются указания для решения. Для отдельных приведено решение. Некоторые задачи служат для подготовки читателя к следующим задачам – для номеров таких вспомогательных задач используется курсив. В тексте мы часто используем шаблон ``для <объекты> : <свойство>''. Здесь ``:'' является сокращением слов ``выполняется следующее:''.

Аксиоматический метод

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

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

Аксиомы натуральных чисел

Мы рассматриваем множество w объектов называемых натуральными числами. Одно из натуральных чисел называется нулём и обозначается 0 . Для любого натурального числа n одно из натуральных чисел называется следующим за числом n и обозначается n' .

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

Аксиома 1.Для любого натурального числа n: n'№ 0.

Аксиома 2.Для любых натуральных чисел m и n: если m'=n', то m = n.

Аксиома 3.Пусть A является подмножеством множества w со следующими свойствами:

1. 0 О A;

2. для любого натурального числа n: если n О A, то n' О A.

Тогда A = w.

Эти аксиомы были введены Джузеппе Пеано в 1889 году.

Начальные задачи

Определения.1 = 0', 2 = 1', 3 = 2', 4 = 3' .

В каждой из следующих задач получите данное утверждение из аксиом.

1.12 № 4.

 

см. Решение

1.2n' № n.

Решение. Рассмотрим множество A натуральных чисел n таких, что n' № n. Наша цель – показать, что A = w, и мы сделаем это, используя аксиому 3. Сначала нам надо проверить, что 0 О A, то есть 0' № 0. Это следует из аксиомы 1. Теперь возьмём любое натуральное число n и предположим, что n О A, то есть n' № n. Нам надо вывести из этого предположения, что n'О A – это значит, что n'' № n'. Предположим, что n''= n'. Тогда, по аксиоме 2, n'= n, а это противоречит тому, что n' № n.

Это доказательство, разумеется, ``доказательство по индукции''. Условия 1 и 2 аксиомы 3 являются ``базисом'' и ``индуктивным шагом''. Аксиома 3, которая служит для построения доказательств подобных этому, называется аксиомой индукции.

1.3Если n № 0, то существует натуральное число m такое, что n = m'. см. Указания

1.4Такое число m единственно.

Сложение

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

1.5 Существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = 3,

f(n') = f (n)'.

см. Указания

1.6 Для любого m существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = m,

f(n') = f(n)'.

1.7Существует функция g из w ґ w в w такая, что

g(m, 0) = m,

g(m, n') = g(m, n).

1.8Такая функция g единственна. см. Указания

Определение 1 (Сумма).Для этой функции g число g(m, n) называется суммой m и n и обозначается m + n .

Так, для любых натуральных чисел m и n:

m + 0 = m, m + n'= (m + n)'.

(1)

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

1.92 + 2 = 4.

1.10n'= n + 1. см. Указания

1.11(k + m) + n = k + (m + n). ^* см. Указания

1.12 0 + n = n. см. Указания

1.13 m'+ n = m + n'. см. Указания

1.14m + n = n + m. ^* см. Указания

1.15Если k + m = k + n, то m = n. ^*

Порядок

Определение 2 (Порядок).Мы пишем m Ј n , если для некоторого k: n = m + k.

1.160 Ј n.

см. Решение

1.17n Ј n. ^*

1.18n Ј n'.

1.19n Ј 0 тогда и только тогда, когда n = 0. см. Указания

1.20Если k Ј m и m Ј n, то k Ј n. ^* см. Указания

1.21Если m Ј n и n Ј m, то m = n. ^*

1.22Если m Ј n и m № n, то m'Ј n.

1.23Для любых m и n: m Ј n или n Ј m. ^* см. Указания

1.24k + m Ј k + n тогда и только тогда, когда m Ј n.

Определение 3.Мы пишем m < n , если m Ј n и m № n.

1.252 < 4.

1.26Любые натуральные числа m и n удовлетворяют по крайней мере одному из условий: m = n, m < n, n < m.

1.27Любые натуральные числа m и n удовлетворяют в точности одному из этих условий.

1.28Для любых натуральных чисел m и n, следующие условия эквивалентны:

1. m Ј n,

2. m < n или m = n,

3. m < n'.

Наименьший элемент

Определение 4 (Наименьший элемент).Элемент n множества A натуральных чисел называется его наименьшим элементом, если для любого элемента m из A n Ј m.

1.29Любое множество натуральных чисел имеет не более одного наименьшего элемента.

1.30 Для любого множества A натуральных чисел если 0 О A, то 0 является наименьшим элементом A.

1.31 Для любого множества A натуральных чисел если 1 О A, то A имеет наименьший элемент.

1.32Любое непустое множество натуральных чисел имеет единственный наименьший элемент.

Умножение

1.33 Для любого m существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = 0,

f(n + 1) = f(n) + m.

1.34Существует функция g из w ґ w в w такая, что

g(m, 0) = 0,

g(m, n + 1) = g(m, n) + m.

1.35Такая функция g единственна.

Определение 5 (Произведение).Для этой функции g число g(m, n) называется произведением m и n и обозначается m · n .

Так, для любых натуральных чисел m и n

m · 0 = 0, m · (n + 1) = (m · n) + m.

(2)

1.362 · 2 = 4.

1.37m · n = n · m. см. Указания

1.38m · n = 0 тогда и только тогда, когда m = 0 или n = 0. см. Указания

Системы Пеано

Определение 6 (Система Пеано).Тройка <W, a, s> , где W – множество, a – элемент из W, а s – функция из W в W называется системой Пеано, если

• для любого x О W: s(x) № a,
• для любых x, y О W: если s(x) = s(y), то x = y,
• для любого подмножества A множества W если

1. a О A и

2. s(x) О A всегда, когда x О A,

тогда A = W.

Используя это определение, аксиомы 1–3 можно сформулировать кратко, сказав, что тройка <w, 0, s₀>, где s₀ обозначает функцию следования^*, является системой Пеано.

1.39Определите систему Пеано <W, a, s> такую, что W = w \ {0}.

1.40Найдите изоморфизм между системой Пеано <w, 0, s₀> и системой Пеано, построенной в решении задачи 1.39.

1.41Для любой системы Пеано <W, a, s> существует изоморфизм между <w, 0, s₀> и <W, a, s>. см. Указания

Таким образом, любая система Пеано изоморфна системе натуральных чисел. В этом смысле аксиомы 1–3 дают полную характеризацию натуральных чисел^*.

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

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

Объектный язык и метаязык

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

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

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы (отрицание), & (конъюнкция), Ъ (дизъюнкция) и Й (импликация) называются пропозициональными связками; – унарная связка, а другие – бинарные.

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

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

Определение 7.Множество X строк замкнуто относительно правил построения (для логики высказываний), если

• каждый атом принадлежит X,
• для любой строки F, если F принадлежит X, то F тоже принадлежит,
• для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G).

2.1Укажите два примера множества строк: одно замкнутое, другое не замкнутое относительно правил построения.

Определение 8 (Формула).Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

2.2Множество формул замкнуто относительно правил построения.

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

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура – это {p, q}.

2.3Является ли формулой (p & q)?

2.4Является ли формулой (p)?

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

Доказательство свойств формул по индукции

 

Разбор формул

 

Семантика

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

Определение 10 (Интерпретация).Символы л,и (``ложь'', ``истина'') называются истиностными значениями. Интерпретация пропозициональной сигнатуры s есть функция из s в {л,и}.

Если s конечна, тогда интерпретация может быть определена таблицей её значений, например:

p q л и

(3)

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

Прежде всего нам надо связать функцию с каждой пропозициональной связкой – функцию из {л,и} в {л,и} с унарной связкой и функцию из {л,и}ґ {л,и} в {л,и} с каждой бинарной связкой. Функции определяются следующими таблицами:

x (x) л и и л

x y &(x, y) Ъ(x, y) Й(x, y) л л л л и л и л и и и л л и л и и и и и

^*

Для любой формулы F и любой интерпретации I истиностное значение F^I , назначенное формуле F интерпретацией I, определяется как значение суперпозиции соответствующих булевых функций, а именно, следующим образом:

• F^I = I(F) если F – атом,
• (F )^I = (F^I),
• (F Д G)^I = Д(F^I,G^I) для каждой бинарной связки Д.

Заметим, что это определение рекурсивно: (F)^I определяется через F^I и (F Д G)^I – через F^I и G^I.

Если F^I = и, мы говорим, что формула F истинна при интерпретации I (символически I |= F ).

2.10Найдите формулу F такую, что (3) – единственная интерпретация, при которой F истинна.

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

p	q
л	л	л
л	и	и
и	л	л
и	и	л

2.11Для любых формул F₁,...,F_n (n і 1) и любой интерпретации I

(F₁ & ··· & F_n)^I = и тогда и только тогда, когда F^I₁ = ··· = F^I_n = и.

2.12Сформулируйте и докажите подобный факт для дизъюнкции F₁ Ъ ··· Ъ F_n.

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура конечна: s = { p₁, ..., p_n}.

2.13 Для любой интерпретации I существует формула F такая, что I – единственная интерпретация, при которой F истинна.

2.14Для любой функции a из интерпретаций в истинстные значения существует формула F такая, что для всех интерпретаций I: F^I = a(I).

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

Нормальные формы

Определение 11 (Эквивалентность).Формула F эквивалентна формуле G, если F^I = G^I для любой интерпретации I.

В задачах 2.16, 2.18 и 2.20 мы вводим несколько ``нормальных форм'' таких, что любая пропозициональная формула может быть эквивалентно трансформирована в любую из этих форм.

2.15 Покажите, что для атомов p и q

• каждая из формул p & q, p Й q эквивалентна формуле, не содержащей связок, кроме Ъ и ,
• каждая из формул p Ъ q, p Й q эквивалентна формуле, не содержащей связок, кроме & и ,
• каждая из формул p & q, p Ъ q эквивалентна формуле, не содержащей связок, кроме Й и .

2.16Любая формула эквивалентна

• формуле, не содержащей связок, кроме Ъ и ,
• формуле, не содержащей связок, кроме & и ,
• формуле, не содержащей связок, кроме Й и .

В сочетании с результатом задачи 2.14 этот факт показывает, что множества { Ъ, }, { &, } и { Й, } – ``полные'' множества связок – они достаточны для выражения любой таблицы истинности. С другой стороны, множество { Ъ, &, Й } не ``полное'':

2.17Предполагая, что p – атом, покажите что любая формула, эквивалентная p, содержит по крайней мере одно отрицание. см. Указания

Литерал – это атом или отрицание атома. Элементарная конъюнкция – это формула вида L₁& ··· & L_n (n і 1), где L₁,...,L_n – литералы. Будем говорить, что формула находится в дизъюнктивной нормальной форме, если она имеет вид C₁ Ъ ··· Ъ C_m (m і 1), где C₁, ..., C_m – элементарные конъюнкции.

2.18Любая формула эквивалентна некоторой формуле в дизъюнктивной нормальной форме.

Элементарная дизъюнкция – это формула вида L₁ Ъ ··· Ъ L_n (n і 1), где L₁,...,L_n – литералы. Будем говорить. что формула находится в конъюнктивной нормальной форме, если она имеет вид D₁ & ··· & D_m (m і 1), где D₁, ..., D_m – элементарные дизъюнкции.

2.19 Пусть F – формула в дизъюнктивной нормальной форме. Покажите, что F эквивалентно некоторой формуле в конъюнктивной нормальной форме.

2.20Любая формула эквивалентна некоторой формуле в конъюнктивной нормальной форме.

Выполнимость

Определение 12 (Выполнимость).Если существует интерпретация, при которой формула F истинна, мы говорим, что F выполнима.

Эта терминология применима также к множествам формул: множество G формул выполнимо, если существует интерпретация, при которой истинны все формулы G.

2.21Пусть G – множество литералов. Покажем, что G выполнимо тогда и только тогда, когда не существует атома A, для которого и A и A принадлежат G.

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

Логическое следование

Мы сейчас определим в контексте логики высказываний, когда формула F ``следует'' из множества формул G. Идея следования центральна в логике: в любой формальной аксиоматической теории ``теорема'' – это формула, которая следует из аксиом.

Определение 13 (Логическое следование).Формула F (логически) следует из множества формул G (или множество формул G влечёт формулу F, символически, G |= F ), если для каждой интерпретации, при которой все формулы G истинны, формула F также истинна.^*

Про формулы, которые логически следуют из G будем говорить ``логическое следствие G''.

2.22Предполагая, что p и q – атомы, определите

• следует ли q из (множества состоящего из) p и p Й q,
• следует ли q из p и p Й q.

2.23G влечёт F тогда и только тогда, когда G И { F } не выполнимо.

Определение 14 (Тавтология).Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.^*

Понятие тавтологии ``двойственно'' понятию выполнимой формулы: F – тавтология тогда и только тогда, когда F не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F є G – тавтология.

2.24Определить, какие из следующих формул являются тавтологиями: (p Й q) Ъ (q Й p), ((p Й q) Й p) Й p, ((p є q) є r) є (p є (q є r)).

2.25Для любых формул F, G₁,...,G_n (n і 1) : F следует из { G₁,..., G_n } тогда и только тогда, когда (G₁ & ··· & G_n) Й F – тавтология.

Пропозициональный вывод

Существует другое определение следования, которое выглядит совершенно отличающимся от данного выше, но в действительности эквивалентное ему. В соответствие с этим определением, G влечёт F, если F может быть выведено из G с использованием определенного набора ``правил вывода''. Первое определение, основанное на интерпретации, – ``семантическое'', второе, основанное на понятии вывода – ``синтаксическое'' или ``дедуктивное''.

О корректности, полноте и разрешимости

Выводы в логике высказываний – наш основной объект изучения до конца данной части.

Вывод строятся из конструкций, которые называются ``секвенциями''.

Определение 15 (Секвенция).Секвенция – это выражение вида G |– F (``F при посылках G'') или G |– ^ (``посылки G противоречивы''), где F – формула и G – конечное множество формул. ^*

Мы определим, какие секвенции рассматриваются ``начальными'', и опишем несколько ``правил вывода'' для порождения новых секвенций из секвенций, порождённых ранее. Начальные секвенции называются аксиомами.

Определение 16 (Аксиомы).Аксиомы в исчислении высказываний имеют вид

{ F } |– F.

Мы определим 12 правил вывода, и удобно вводить их постепенно.

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

Определение 17 (Дерево доказательства).Дерево доказательства определим рекурсивно:

1. Деревом доказательства является пустое дерево доказательства, состоящее только из корня – аксиомы.

2. Пусть T₁, ..., T_k – деревья доказательства с корнями R₁, ..., R_k. Тогда

T1 ... Tk

S

3. (где S – некоторая секвенция) – дерево доказательства, если S может быть получена из R₁, ..., R_k с помощью одного из правил вывода. Корнем такого дерева является S.

Определение 18 (Доказуемая секвенция).Если существует дерево доказательства с корнем R, то R называют доказуемой секвенцией. Если этот корень имеет вид G |– F, то говорят о выводе формулы F из G.

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

---

Дата добавления: 2018-02-28; просмотров: 561; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!