49Принцип полной дизъюнкции в предикатной форме

Теорема об обратимости импликаций

Пусть справедливо следующее (m ³ 2):

("x)(P₁(x) ® Q₁(x)), ("x)(P₂(x) ® Q₂(x)), ... , ("x)(P_m(x) ® Q_m(x)).

Причем для посылок известно, что истинно утверждение ("x)(P₁(x) Ú P₂(x) Ú ... Ú P_m(x)), а следствия попарно исключают друг друга, т.е. истинны все высказывания Ø($x)(Q_i(x) Ù Q_j(x)) (i, j=1,…, m, i ¹ j).

Тогда справедливы и обратные импликации:

("x)(Q₁(x) ® P₁ (x)), ("x)(Q₂(x) ® P₂(x)), ... , ("x)(Q_m(x) ® P_m(x)).

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

Теорема.

Пусть справедливо следующее:

("x)(P(x) ® Q₁(x)), ("x)(ØP(x) ® Q₂(x)), причем следствия Q₁(x) и Q₂(x) исключают друг друга, т.е. истинно высказывание Ø($x)(Q₁(x) Ù Q₂(x)).

Тогда справедливы обратные теоремы:

("x)(Q₁(x) ® P(x)), ("x)(Q₂(x) ® ØP(x)).

50Метод (полной) математической индукции

• Специальный метод, применяемый для доказательства истинности утверждений типа ("x Î N)(P(x)), т.е. ("x) (x Î N ® P(x)). Такие утверждения выражают тот факт, что некоторое свойство P присуще каждому натуральному числу.

• Формальная основа — аксиома индукции, выражающая свойства естественного отношения порядка, имеющегося на множестве всех натуральных чисел.

• Если свойством P обладает число 1 и для всякого натурального числа из того, что оно обладает этим свойством, следует, что и непосредственно следующее за ним натуральное число также обладает им, то и всякое натуральное число обладает свойством P.

• Символически: (P(1) Ù ("x) (P(x) ® P(x+1))) ®("y)(P(y)).

• Логическая схема доказательства методом математической индукции:

(1) P(1) — устанавливается проверкой; (2) ("x) (P(x) ® P(x+1)) — доказывается;

(3) P(1) Ù ("x) (P(x) ® P(x+1)) — из (1) и (2) по правилу введения конъюнкции;

(4) (P(1) Ù ("x)(P(x) ® P(x+1))) ®("y)(P(y)) — аксиома индукции; (5) ("y)(P(y)) — из (3) и (4) по МР.

• P(1) — основание индукции;

• предположение об истинности P(x) — предположение индукции;

• доказательство истинности P(x+1) — шаг индукции.

51Необходимые и достаточные условия

• Пусть некоторая теорема имеет вид

("x) (P(x) ® Q(x)). Это означает, что предикат P(x) ® Q(x) тождественно истинен, т.е. его множество истинности (P® Q)⁺ = U =(Ø P)⁺ È Q⁺ . Следовательно, P⁺ Í Q⁺, а значит предикат Q(x) является следствием предиката P(x).

• ("x) (P(x) ® Q(x)) означает, что условие P(x) является достаточным для Q(x), а Q(x) — необходимым для P(x).

52Понятия формальной системы и формального вывода. Аксиоматическая (формальная) теория и принципы ее построения.

Формальные системы (ФС) – это совокупность чисто абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания, т.е. семантики.

Формальная теория Т состоит из следующих компонент:

1. Множества знаков, образующих алфавит языка теории.

2. Множества слов, составленных из знаков алфавита, называемых формулами.

3. Подмножества формул всего множества формул, называемых аксиомами.

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

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

53Вывод и выводимость в формальной теории. Разрешимые и неразрешимые формулы. Доказательство и доказуемость. Теорема формальной теории.

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

Формальная теория Т состоит из следующих компонент:

1. Множества знаков, образующих алфавит языка теории.

2. Множества слов, составленных из знаков алфавита, называемых формулами.

3. Подмножества формул всего множества формул, называемых аксиомами.

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

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

Пусть F1,…,Fn,G – формулы теории. Если существует такое правило вывода R, что (F1,…,Fn,G) принадлежит R, то говорят, что формула G непосредственно выводима из F1,…,Fn по правилу вывода R. (F1,…,Fn – посылки, G – заключение).

Выводом формулы G из формул F1,…,Fn в форм теории Т называется такая последовательность формул Е1,..,Ек, что Ек= G, а любая другая либо является аксиомой, либо исходной формулой, либо непосредственно выводима из ранее полученных формул. Если G выводима из F1,…,Fn в теории Т, то F1,…,Fn – гипотезы. Теорема – формула, выводимая только из аксиом, без гипотез).

Формальное доказательство формулы А в теории Т — это конечная последовательность формул

А1, А2, ...,Аn, где каждая формула Ai является либо аксиомой, либо получена из предыдущих с помощью одного из правил вывода, а Ап — это формула А.

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

|– А (|– читается как «доказуемо А» или «А теорема». Знак |– введен в 1879 г. немецким логиком Готлобом Фреге).

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