Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою.

Доведення. Достатньо впевнитися в тому, що аксіоми АП1‒ АП5 – загальнозначущі формули, і показати, що застосування правил виведення АП1‒ АП3 до загальнозначущих формул приводить до одержання тільки загальнозначущих формул.

Загальнозначущість аксіом АП1‒ АП3 (вони ж А1‒ А3) було розглянуто в 2.1, 2.2. Покажемо загальнозначущість формули Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru x А (х) → А (у) (аксіома АП4). Припустимо, що ця формула загальнозначуща, тоді одержимо, що у задовільній предметній області є такий набір значень предметних змінних, при якому Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru x А (х) =I, а А (у) = X. Але оскільки є значення предметних змінних, при яких формула А набуває хибного значення X, тоді згідно з квантором загальності формула Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru x А (х) також повинна набувати значення X. Виникла суперечність і доводить загальнозначущість формули Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А (х) → А (у), звідки випливає і загальнозначущість аксіоми АП4. При доведенні аксіоми АП5 припустимо, що формула Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi (А → В) → (А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi В) незагальнозначуща. Тоді при деякій інтерпретації формула А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi В набуде значення X, а Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi (А → В) – значення I. Якщо А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi В = X, то А = I, а Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi В = X. Оскільки Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xi (А → В) = I, то для будь-якого xi при В = X повинне виконуватися А = I.Із суперечності для істинного значення формули А випливає справедливість загальнозначущості аксіоми АП5, що й необхідно було довести.

Теорема 3.6.2.Числення предикатів першого порядку ПLє несуперечною теорією.

Доведення. Припустимо, що для деякої формули А в теорії ПLє дві теореми А і Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru А. Із факту загальнозначущості будь-якої із цих теорем отримаємо, що А= I і Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru А= I, але одночасно цього не може бути, що й потрібно було довести.

Теорема 3.6.3. Якщо формула В не залежить від формули А при доведенні Г, А ├ В, то Г ├ В.

Доведення. Доведення виконаємо індукцією за довжиною виведення Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , …, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = В. При n = 1 маємо Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = = B і B або належить Г Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru {A}, або є аксіомою. Але В не може збігатися з А внаслідок незалежності В від А. Отже,

Г ├ В.

Нехай теорема справедлива для всіх формул В, довжина виведення яких менша n. Якщо В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Г або В – аксіома, то Г ├ В. Якщо ж В – безпосередній наслідок деяких формул із Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , …, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru (однієї або двох) і оскільки В не залежить від А, то від А не залежить жодна із цих формул. Але тоді за припущенням індукції, із Г виводяться формули (одна або дві), а разом з ними – і формула В, що й по-трібно було довести.

Теорема 3.6.4 (теорема дедукції). Нехай Г, А ├ В і при цьому нехай існує таке виведення В із Г, А, в якому жодне застосування правила узагальнення до формул, які залежать від А в цьому виведенні, не зв’язується квантором загальності формули А. Тоді Г ├ А → В.

Доведення. Доведення проводиться індукцією за довжиною виведення Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , …, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = В. При n = 1 існують дві можливості:

а) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Г або є аксіомою;

б) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = А.

У першому випадку а) А → В, оскільки це випливає з аксіоми АП1, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru → ( А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) за правилом МР.

У випадку б), коли А = Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , то Г ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ruТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , оскільки А → А – тавтологія.

Нехай тепер теорема справедлива для всіх і < n. Припустимо, що існують індекси k і j, менші і, і що Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru → ® Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . Тоді за припущенням індукції Г ├ А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru і Г ├ А → ® ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ruТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Але за аксіомою АП2 маємо А→( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ruТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) → → ((А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) → (А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru )) і за правилом МР отримаємо, що Г ├ А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru .

Припустимо, що існує такий індекс j < i, що Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = = Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xk B. Тоді за припущенням індукції Г ├ А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru і або Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru не залежить від А, або xk не є вільною змінною формули А. Якщо Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru не залежить від А, то за теоремою 7.2.1

Г ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru і, застосовуючи правило узагальнення, отримаємо Г ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru хk Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . За схемою аксіоми АП1 знаходимо, що Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru → ®(А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) і А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ‒ за правилом МР. За припущенням індукції Г├ А→ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , за правилом узагальнення Г├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xk А → ® В і, нарешті, за правилом МР отримаємо Г ├ А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru xk Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , тобто Г ├ А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , що й потрібно було довести.

Наслідок 3.6.1. Якщо Г, А ├ В й існує виведення В без застосування правила узагальнення до вільних змінних формули А, то Г ├ А → В.

Наслідок 3.6.2.Якщо формула А замкнена і Г,А├ В, то Г ├ А → В.

Приклад 3.6.1.Довести, що ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А.

Розв’язання. Застосуємо предикатні аксіоми, правило МР та узагальнення:

а) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А – гіпотеза ;

б) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А – аксіома АП4 ;

в) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А – МР із а), б) ;

г) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А → А – аксіома АП4 ;

д) А – МР із в), г) ;

е) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А – правило узагальнення із д) ;

є) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А – правило узагальнення із е) .

Теорема 3.6.5 .Якщо формули А (х) і А (у) подібні, то├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А (х) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А (у).

Доведення. Використовуючи аксіому АП4, маємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А (х) → А (у). Виходячи з умови теореми 3.6.5 і скориставшись правилом узагальнення, отримаємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А (х) → А (у)). За схемою аксіоми АП5 маємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А(х)→ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А (у). Аналогічно доводять і формулу

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А (у) → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А (х). Для цього необхідно скористатися тавтологією А → ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru В → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru (А → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru В) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru А→(В→

→ АÙ B), унаслідок чого отримаємо Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А(х) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у А(у).

Теорема 3.6.6 (теорема еквівалентності). Якщо формула В є підформулою А і формула Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru отримана з формули А заміною яких-небудь (можливо, жодного) входжень В формулою С і якщо будь-яка змінна формули В або формули С, що є одночасно пов’язаною змінною формули А, зустрічаються у списку Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ,…, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , то

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → (А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ).

Доведення. Доведення виконаємо індукцією за числом зв’язок і кванторів у А. Зауважимо, що якщо жодне входження В насправді не змінюється, то А збігається з Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru і формула, яку потрібно вивести, є окремим випадком тавтології В → (А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru А). Якщо В збігається з А і це єдине входження замінюється на С, то формула, яку необхідно вивести, виводиться із аксіоми АП4. Отже, необхідно вважати, що В є власна підформула формули А і принаймні одне входження В замінюється.

Тепер припустимо, що теорема справедлива для будь-якої формули з меншим числом кванторів і логічних зв’язків, ніж у А.

Випадок 1.А – елементарна формула. Тоді В не може бути власною підформулою формули А.

Випадок 2.А має вигляд Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru D. Тоді нехай A/ є Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . За припущенням індукції ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уkТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С)®(D Û Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Звідси за допомогою тавтології А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru В → ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru А → → Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru В) отримаємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → (А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ).

Випадок 3.А має вигляд D → E. Нехай Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru = Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ruТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . За припущенням індукції

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → ( D Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) і ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → (Е Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Застосовуючи тавтологію (( А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru В) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru (C Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru D)) → ((A → C) Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru (B → D)),

отримаємо ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ruТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → (А Û Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ).

Випадок 4.А має вигляд Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru x D. Тоді Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru є Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru x Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . За припущенням індукції ├"y1"y2…"уkТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С)→(D Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Змінна х не є вільною змінною формули

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С). Якщо припустимо, що це так, то х входила б вільно в В або С, і оскільки х пов’язана в А, то х входила б до переліку Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ,…, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru і була б пов’яза-ною змінною в Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С), а це суперечить умові. Застосовуючи тепер аксіому АП5, отримаємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → ( D Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Використовуючи Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х ( А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru D) → ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х D), маємо Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х (D Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru )→ → ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru хD Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ). Користуючись транзитивністю імплікації, остаточно отримаємо

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уkТеорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → ( Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru хD Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ) або Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у1 Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у2Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru уk ( В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С) → (А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru ), що й потрібно було довести.

Теорема 3.6.7 (теорема про заміну). Нехай формули А, Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , В і С задовольняють умови теореми еквівалентності. Тоді якщо ├ В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С, то├ А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru , а якщо ├ В Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru С і ├ А, то ├ Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru . Ця теорема є простим наслідком теореми еквівалентності.

Теорема 3.6.8 (теорема перейменування пов’язаних змінних). Якщо Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х В (х) є підформулою формули А, формула В (у) подібна формулі В(х) і Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru отримана з А заміною хоча б одного входження Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х В(х) у А на Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у В(у), то ├ А Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru .

Доведення. Доведення випливає з теорем 3.6.5 і 3.6.7.

Контрольні запитання

1. Які додаткові нові логічні поняття введені в логіку предикатів і з якою метою?

2. Дайте визначення поняття «предикат».

3. Що називають п-місним предикатом?

4. Що називають порядком предиката?

5. Що називають нульмісним предикатом?

6. Наведіть приклади функціональних символів.

7. Який функціональний символ називають п-місним?

8. Дайте визначення поняття «терма».

9. Що розуміють під предметною областю?

10. Дайте визначення понять «предметна константа» і «предметна змінна».

11. Дайте визначення квантора загальності.

12. Що розуміють під квантором існування?

13. Як позначають квантори загальності та існування?

14. Які змінні називають зв’язаними, а які – вільними?

15. Як залежить значення предиката від зв’язаних або вільних змінних?

16. Поясніть призначення зв’язаних змінних.

17. До яких наслідків призводить застосування квантора за однією із змінних тримісного предиката?

18. Коли предикат Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru у Р ( х,у ) набуває значення ”Істина”?

19. Коли предикат Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою. - student2.ru х Р ( х,у ) набуває значення ”Істина”?

20. Що називають формулою у логіці предикатів?

21. Яку формулу називають атомарною?

22. Що розуміють під областю дії квантора?

23. Що таке інтерпретація формули логіки предикатів?

24. Запишіть правила, згідно з якими формула логіки предикатів може набути істинного або хибного значення.

25. Порівняйте поняття інтерпретації у логіці висловлювань і логіці предикатів.

26. Що таке рівносильність формул логіки предикатів?

27. Як впливає область інтерпретації на рівносильність формул логіки предикатів?

28. Як впливають на рівносильність вільні й зв’язані змінні у формулах логіки предикатів?

29. До якого наслідку призводить перенесення квантора на початок формули?

30. Які додаткові закони й тотожності існують у логіці предикатів порівняно з логікою висловлювань?

31. Поясніть суть заміни зв’язаної змінної.

32. Сформулюйте комутативні властивості кванторів.

33. Сформулюйте дистрибутивні властивості кванторів.

34. Яким чином можна обійти обмеження дистрибутивних властивостей кванторів?

35. Запишіть формули закону де Моргана для кванторів.

36. Яке числення називають численням предикатів першого порядку?

37. Які властивості числення предикатів першого порядку ви знаєте?

38. Довести, що будь-яке числення предикатів першого порядку є несуперечною теорією.

39. Сформулюйте умови теореми еквівалентності формул у численні предикатів першого порядку.

Наши рекомендации