Логіка предикатів першого порядку. Алфавіт і формули. Істинність, інтерпретації, моделі. Нормальні форми в ЛППП

4.2.1 Мета занять

Засвоїти прийоми формалізації природно-мовних висловлень засобами ЛПП, способи визначення істинностних значень формул ЛПП при заданих інтерпретаціях. Опрацювати алгоритми приведення будь-якої формули ЛПП до ПНФ та ССФ.

4.2.2 Методичні вказівки з організації самостійної роботи студентів

Необхідно на прикладах засвоїти прийоми формалізації природно-мовних висловлювань засобами ЛПП, способи визначення істинностних значень формул ЛПП при заданих інтерпретаціях, основні тотожності ЛПП. Студенти повинні навчитися реалізовувати еквівалентні перетворення формул ЛПП, засвоїти алгоритми перетворення формул у попередню і скулемівську нормальні форми. Для закріплення матеріалу рекомендуємо використовувати наступну літературу: [6, с. 35-52; 8; 9, с. 191-241].

При вивченні теоретичного матеріалу зверніть увагу на такі основні положення. У логіці висловлень атом являє собою оповідальне речення, що може бути або істинне або хібне, але не те і інше разом. Атом розглядається як єдине ціле. Його структура й склад не аналізуються.

Однак є багато умовивідів, які не можуть бути розглянуті таким простим способом. Тому вводиться логіка першого порядку (логіка предикатів), що в порівнянні із логікою висловлень має ще три логічних поняття: терми, предикати та квантори. Більша частина повсякденної та математичної мови може бути формалізована логікою 1-го порядку. Предикат - це двозначна функція виду Р(х₁,...,х_n)=у, аргументи якої визначені в довільній множині М, що називається предметною областю, тобто х₁,...,х_nÎМ={a₁,...,a_m}, yÎ{0,1}, a₁,...,a_m - предмети. Задати предикат - означає вказати предметну область для кожної предметної змінної, а також значення предиката для кожного з можливих наборів значень аргументів.

Для побудови атомів логіки першого порядку використовуються наступні чотири типи символів:

1) індивідні символи або константи. Звичайно це імена об'єктів, такі як Джон, 3.

2) символи предметних змінних. Це звичайно малі літери x,y,z,..., можливо з індексами.

3) функціональні символи. Звичайно це малі літери f,g,h,... або осмислені слова з малих літер, такі як “ плюс ”, “ батько ”, та інш.

4) предикатні символи. Звичайно це прописні букви P,Q,R,... або осмислені слова із прописних букв, такі як БІЛЬШЕ або ЛЮБИТЬ.

Усяка функція або предикатний символ має певне число аргументів. Якщо функціональний символ f має n аргументів, то f називається n-місним функціональним символом. Индивідний символ або константа може розглядатися як функціональний символ без аргументів. Аналогічно, якщо предикатний символ Р має n аргументів, то Р називається n-місним предикатним символом. Наприклад, нам потрібно представити висловлення “х більше 3”. Спочатку визначимо двомісний предикат БІЛЬШЕ (х,у), що означає “х більше у”. Тоді висловлення “х більше 3” представляється виразом БІЛЬШЕ (х,3). Даний предикат задає бінарне відношення, тобто множину пар, у яких перше число більше 3. Відзначимо, що предикат визначається як функція, що приймає значення 1 (істина) на наборах, що задовольняють задане відношення v, і яке приймає значення 0 (хибність) на наборах, що не задовольняють v. Аналогічне висловлення “х любить у” можна представити за допомогою предиката ЛЮБИТЬ(х,у). Для позначення висловлень “х+у” і “Батько людини х” можна використовувати функціональні символи плюс(х,у) і батько(х). Речення “х+1 більше х” і “Батько Джона любить Джона” можна символічно представити у вигляді БІЛЬШЕ(плюс(х,1),х) і ЛЮБИТЬ(батько(Джон), Джон).

У логіці першого порядку терми визначаються рекурсивно в такий спосіб:

− константа є терм;

− змінна є терм;

− якщо F є n-місним функціональним символом і t₁,...,t_n - терми, то F(t₁,...,t_n) - терм. Ніяких термів, крім породжених застосуванням зазначених правил (1-3) немає. Наприклад, т.я. х і 1 – терми, а плюс - двомісний функціональний символ, то плюс(х,1) є терм.

Предикат є відображення, що відображає список констант в І або Х. Наприклад, БІЛЬШЕ є предикат. БІЛЬШЕ(5,3) є І, але БІЛЬШЕ(1,3) є Х. Якщо Р - n-місний предикатний символ і t₁,...,t_n- терми, то Р(t₁,...,t_n) - атом. У логіці першого порядку, як і в логіці висловлень, вводиться п'ять логічних зв’язок для побудови формул: . Для характеристики змінних вводиться два спеціальних символи " і $. " ¾ квантор загальності. Якщо х - змінна, то ("x) читається як “для всіх х”, “для кожного х” або “для всякого х”. $ - квантор існування, ($x) читається “існує х”, “для деяких х” або “принаймні для одного х”. ("x) і ($x) називають кванторними комплексами. Область дії квантора - та формула, до якої він застосовується. Наприклад, область дії квантора існування у формулі ("x)($y)МЕНШЕ(х,у) є МЕНШЕ(х,у), а область дії квантора загальності - формула ($y)МЕНШЕ(х,у). Область дії у кванторі ("x)(Q(x) R(x)) є (Q(x) R(x)).

Входження змінної х у формулу називається зв’язаним тоді і тільки тоді, коли воно збігається із входженням у кванторний комплекс ("x) або ($x) або перебуває в області дії такого комплексу. Входження змінної у формулу вільне тоді і тільки тоді, коли воно не є зв’язаним. Змінна вільна у формулі, якщо хоча б одне її входження в цю формулувільне. Змінна зв’язана у формулі, якщо хоча б одне її входження в цю формулу зв’язане. У формулі ("x)Р(х,у) змінна х, зв’язана тому що обидва входження х зв’язані. Однак змінна у вільна, тому що єдине входження у вільне. Змінна у формулі може бути вільною та зв’язаною одночасно. Наприклад, у вільна і зв'язана у формулі ("x)Р(х,у)Ù("y)Q(у).

Правильно побудовані формули (ППФ) або формули логіки першого порядку рекурсивно визначаються в такий спосіб:

1) атом є формула. (Відзначимо, що “атом” - скорочення для атомарної формули).

2) якщо F і G формули, то Ø(F), (FÚG), (FÙG), (F G) і (F G) – формули.

3) якщо F – формула, а х – вільна змінна в F, то ("x)F і ($x)F – формули.

Формули породжуються тільки кінцевим числом застосувань правил (1-3). Надалі круглі дужки у всіх формулах можуть бути опущені відповідно до угод, які були встановлені в логіці висловлень. (Пропозиціональним або логічним зв’язкам приписується спадний ранг у наступному порядку: ). Розширимо ці угоди, вважаючи, що квантори мають найменший ранг. Наприклад, ($x)AÚB позначає ((($x)A)Ú(B)).

У логіці висловлювань інтерпретація є приписування атомам істинностних значень. Щоб визначити інтерпретацію для формули логіки першого порядку, потрібно вказати предметну область (область значень предметних змінних) і значення констант, функціональних і предикатних символів, що зустрічаються у формулі. Інтерпретація формули F логіки першого порядку складається з непустої (предметної) області D і показ “оцінки” (значення) всіх констант, функціональних символів і предикатних символів, що зустрічаються в F:

− кожній константі ставлять у відповідність деякий елемент із D;

− кожному n-місному функціональному символу ставлять у відповідність відображення з Dⁿ в D. (Відмітимо, що Dⁿ ={(x₁,...,x_n)|x₁ÎD,...,x_nÎD});

− кожному n-місному предикатному символу ставлять у відповідність відображення Dⁿ в {І, Х} (або в {1,0}).

Для кожної інтерпретації формули на області D формула може одержати істинне значення І або Х відповідно до наступних правил:

а) якщо задані істинностні значення формул G і H, то істинностні значення формул ØG, (GÚH), (GÙH), (G H), (G H) здобуваються за допомогою таблиці 5.1.

б) ("x)G приймає значення 1, якщо G приймає значення 1 для кожного х з D; у противному випадку вона приймає значення 0.

("x)G(x)=

в) ($x)G приймає значення 1, якщо G приймає значення 1 хоча б для одного х з D; у противному випадку вона приймає значення 0.

($x)G(x)=

Крім того, у логіці першого порядку визначаються наступні поняття. Формула G несуперечлива (здійсненна) тоді й тільки тоді, коли існує така інтерпретація I, що G має значення 1 в I. Якщо формула G=1 в інтерпретації I, то говорять, що I є модель формули G і I задовольняє G. Формула G суперечлива (нездійсненна) тоді і тільки тоді, коли не існує інтерпретації, яка б задовольняла G. Формула G загальнозначуща тоді й тільки тоді, коли не існує ніякої інтерпретації, що не задовольняє формулі G. Формула G є логічним наслідком формул F₁,F₂,...,F_n тоді і тільки тоді, коли для кожної інтерпретації I, якщо F₁Ù...ÙF_n істинна в I, то G також істиннав I. Відношення між загальзначимістю (суперечливістю) і логічним наслідком, встановлені в теоремах 1, 2 логіки висловлень (див. п.3.3) вірні також і в логіці першого порядку. В дійсності логіка першого порядку може розглядатися як розширення логіки висловлень. Оскільки в логіці першого порядку є нескінченне число областей, то, взагалі кажучи, є нескінченне число інтерпретацій формули. Отже, на відміну від ЛВ, неможливо довести загальзначимість або суперечливість формули оцінкою формули при всіх можливих інтерпретаціях.

У логіці висловлень використовуються дві нормальні форми ¾ кон’юнктивна нормальна форма та диз'юнктивна нормальна форма. У логіці першого порядку також є нормальна форма, що називається “попередньою нормальною формою ” (ПНФ). Мета розглянення попередньої нормальної форми - спрощення процедури доведення. Формула F у логіці першого порядку перебуває у попередній нормальній формі тоді і тільки тоді, коли формула F має вигляд

де кожне (Q_ix_i), i=1,...,n, є або (" x_i) або ($ x_i), і М є формула, що не містить кванторів. (Q₁х₁)...(Q_nx_n) називається префіксом, а М - матрицею формули F. Приклади формул, що перебувають у ВНФ:

Важливим для приведення формул до ВНФ є поняття еквівалентності формул. Дві формули F і G еквівалентні (F=G) тоді і тільки тоді, коли істинностні значення F і G ті ж самі при будь-якій інтерпретації.

Основні пари еквівалентних формул, що представляють собою закони ЛВ, еквівалентні і в логіці першого порядку. Крім них існують і інші пари еквівалентних формул, що містять квантори. Це наступні тотожності, що називаються законами логіки першого порядку для кванторів:

1) закон заміни зв’язанних змінних:

Вводячи нові позначення для зв’язанних змінних, щоб уникнути так званої колізії змінних, варто вибрати букву, відсутню у формулі, тобто:

2) комутативні властивості кванторів

Необхідно пам'ятати, що однойменні квантори можна міняти місцями, а різнойменні не можна, тобто

4) дистрибутивні властивості кванторів

де G - формула, що не містить змінної х.

тобто квантор загальності " і квантор існування $ можна розподіляти по Ù та Ú відповідно. Однак квантор загальності " і квантор існування $ не можна розподіляти по Ú і Ù відповідно, тобто

У подібних цим випадках використовують наступні тотожності:

5) закони де Моргана для кванторів

Процедура перетворення довільної формули логіки першого порядкуу до ПНФ здійснюється за наступним алгоритмом:

крок 1. Використовуємо закони

щоб виключити логічні зв’язки та ;

крок 2. Повторно використовуємо закон

законы де Моргана

і закони

щоб підвести знаки заперечення до предикатних символів;

крок 3. Перейменовуємо зв’язані змінні, якщо це необхідно;

крок 4. Використовуємо закони

щоб винести квантори на початок формули для одержання ВНФ.

Крім ПНФ у ЛПП для пошуку доведень використовується так звана скулемівська стандартна форма (ССФ). Основні ідеї ССФ [6]:

− будь-яка формула логіки першого порядку може бути зведена до ВНФ, у якій матриця не містить ніяких кванторів, а префікс - це послідовність кванторів;

− оскільки матриця не містить кванторів, вона може бути зведена до КНФ;

− зберігаючи суперечливість формули, у ній можна елімінувати квантори існування шляхом використання скулемівських функцій.

Формула F, яка перебуває у ПНФ, має вигляд:

(Q₁x₁)(Q₂x₂)...(Q_nx_n)M, де M - це КНФ.

Нехай Q_r - квантор існування в префіксі (Q₁x₁)(Q₂x₂)...(Q_nx_n), . Тоді алгоритм переходу від ПНФ до ССФ описується наступною послідовністю кроків:

а) якщо ніякий квантор не стоїть в префіксі лівіше Q_r, вибираємо нову константу с, відмінну від інших констант, що входять у М, замінюємо всі входження x_r, що зустрічаються в М, на с, і викреслюємо (Q_rx_r) із префікса;

б) якщо Q_s... Q_s - список всіх кванторів , що зустрічаються лівіше Q_r, , вибираємо новий m-місний функціональний символ f, відмінний від інших функціональних символів, замінюємо всі x_r в М на та викреслюємо (Q_rx_r) з префікса;

в) кроки 1 і 2 застосовуємо до всіх кванторів у префіксі. Остання з отриманих формул є скулемівська стандартна форма або просто стандартна форма формули F. Константи та функції, що використовуються для заміни змінних квантора існування, називаються скулемівськими функціями.

Необхідно також знати наступні означення. Диз’юнкт є диз'юнкція літер. Іноді з метою зручності диз’юнкт позначають як множину літер. Наприклад, . Диз’юнкт, що містить r літер, називається r-літерним диз’юнктом. Однолітерний диз’юнкт називається одиничним диз’юнктом. Диз’юнкт, що не містить ніяких літер, називається пустим диз’юнктом. Пустий диз’юнкт завжди хибний, його позначають „ 0” або „ Х”. Вважають, що множина диз’юнктів S є кон’юнкція всіх диз’юнктів з S, де кожна змінна в S вважається керованою квантором загальності. Завдяки цій домовленості ССФ може бути просто зображена множиною диз’юнктів. Можна елімінувати (усунути) квантори існування, зберігаючи суперечливість формули. Це твердження доводиться в наступній теоремі.

Теорема 3. Нехай S - множина диз’юнктів, які являють собою ССФ формули F. Тоді F суперечлива (хибна) в тому і тільки тому випадку, коли S суперечлива (хибна).

Необхідно знати доведення цієї теореми (див. [6, с. 55-58]). Відзначимо, що формула може мати більш ніж одну стандартну форму. Для простоти при перетворенні формули F у стандартну форму S намагаються заміняти квантори скулемівськими функціями настільки простими, наскільки це можливо. Тоді для формули можна окремо одержати множину диз’юнктів S_i, де кожний S_i представляє стандартну форму F_i, i=1,...,n. Потім припускаємо, що . Опираючись на теорему 3, можна довести що F суперечлива тоді і тільки тоді, коли суперечлива S. Надалі для доведення теорем будемо використовувати процедуру спростування. На вході процедури спростування завжди стоїть множина S. Для множини диз’юнктів використовують терміни “нездійсненна” (“здійсненна”) замість “суперечлива” (“несуперечлива”).

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

1) що таке атоми логіки першого порядку? Наведіть приклади;

2) що таке терми, n-місні предикати? Наведіть приклади;

3) що таке кванторні комплекси? Наведіть приклади;

4) що таке вільна та зв’язанна змінні у формулах логіки першого порядку? Наведіть приклади;

5) за якою процедурою визначаються правильно побудовані формули в логіці першого порядку?

6) як визначається інтерпретація формули логіки першого порядку?

7) як визначається суперечливість, несуперечливість і загальзначимість формул логіки першого порядку?

8) як визначається логічний наслідок в логіці першого порядку? Наведіть приклади;

9) для перерахованих формул довести, що:

суперечлива;

загальнозначуща;

несуперечлива;

загальнозначуща.

10) для наступної інтерпретації (D={a,b}):

P(a,a)	P(a,b)	P(b,a)	P(b,b)

визначити істинностні значення наступних формул:

11) дано формулу А: :

довести, що ця формула завжди істинна, якщо область D містить тільки один елемент;

нехай D={a,b}. Знайти інтерпретацію з областю D, у якій А=0.

12) задано наступну інтерпретацію: Область: D={1,2}.

Значення констант а і b:

a	b

Значення функції f:

f(1)	f(2)

Значення предиката Р:

Р(1,1)	P(1,2)	P(2,1)	P(2,2)

Знайти істинностні значення наступних формул у зазначеній інтерпретації:

13) нехай F₁ і F₂ такі:

Довести, що ØP(a) є логічним висновком F₁ і F₂;

1) наведіть алгоритми приведення будь-якої формули ЛПП до ПНФ та ССФ;

2) наведіть означення диз’юнкта, одиничного диз’юнкта, пустого диз’юнкта.

16) Перетворити наступні формули у ВНФ:

17) Знайти ССФ для кожної з формул:

4.2.4 Приклади аудиторних і домашніх задач

Приклад 1. Записати наступні твердження у вигляді формул логіки першого порядку:

а) кожне раціональне число є дійсне число.

б) існує число, що є простим.

с) для кожного числа х існує таке число в, що x<y.

Розв’язок. Позначимо висловлення “х є просте число” через Р(х), “х є раціональне число” через Q(x), “х є дійсне число” через R(x) і “х менше у” через МЕНШЕ(х,у). Тоді зазначені ствердження відповідно можуть бути записані:

Приклад 2. Перевести твердження “Кожна людина смертна. Конфуцій - людина. Отже, Конфуцій смертний” у формулу ЛППП.

Розв’язок. Позначимо “х є людина” через ЛЮДИНА(х) і “х смертна” через СМЕРТНА(х). Тоді ствердження “Кожна людина смертна” може бути представлено формулою ("x)(ЛЮДИНА(х) СМЕРТНА(х)), ствердження “Конфуцій - людина” ¾ формулою ЛЮДИНА(Конфуцій) і “Конфуцій смертний” ¾ формулою СМЕРТНА(Конфуцій). Ствердження в цілому може бути представлено формулою

("x)(ЛЮДИНА(х) СМЕРТНА(х))Ù ЛЮДИНА(Конфуцій) СМЕРТНА(Конфуцій).

Приклад 3. Основні аксіоми натуральних чисел такі:

А₁: Для кожного числа існує одне і тільки одне число, що безпосередньо іде слідом за ним.

А₂: Немає числа, за яким безпосередньо іде 0.

А₃: Для кожного числа, відмінного від нуля, існує одне і тільки одне безпосередньо попереднє йому число.

Записати їх у вигляді формул логіки першого порядку.

Розв’язання. Нехай f (х) і g (х) представляють відповідно такі числа, що f (х) безпосередньо іде за х, а g (х) безпосередньо попереднє х. Нехай “х дорівнює у” позначається через Е(х,у). Тоді аксіоми можуть бути представлені наступними формулами:

₁: ("x)($y)(E(y, f (x))Ù("z)(E(z, f (x)) E(y,z))),

₂: (($x)E(0, f (x))),

₃: ("x)(ùE(x,0) ($y)(E(y, g (x))Ù("z)(E(z, g (x)) E(y,z))))).

Приклад 4. Дано формули ("x)Р(х) і ($x)ØР(х), і задана інтерпретація: D={1,2}, оцінка для Р така:

Р(1)	Р(2)

Визначити істинностні значення заданих формул.

Розв’язання. Легко переконатися, що ("x)Р(х) хибна в цій інтерпретації:

P(2)=0ÞP(x) 1Þ ("x)P(x)=0 по визначенню квантора загальності. (Þ - знак логічного слідування, який позначає “з А випливає В”). З іншого боку, ØР(2)=1 в цій інтерпретації, тобто маємо: ØР(2)=1ÞP(x) 0Þ Þ($x)ØР(x)=1, ($x)ØР(x) є істина в цій інтерпретації.

Приклад 5. Для формули ("x)($у)Р(х,у) задано інтерпретацію на області D={1,2}:

Р(1,1)	Р(1,2)	Р(2,1)	Р(2,2)

Визначити істинностне значення заданої формули.

Розв’язання. Якщо х=1, то ($у)Р(1,у)=1, т.я. при у=1 маємо: Р(1,1)=1, отже, Р(1,у) 0Þ($у)Р(1,у)=1. Якщо х=2, то ($у)Р(2,у)=1, т.я. при у=2 маємо: Р(2,2)=1, отже, Р(2,2) 0Þ($у)Р(2,у)=1. Отже, в даній інтерпретації для кожного х із D існує такий у, що Р(х,у)=1, тобто ("x)($у)Р(х,у) істинна в цій інтерпретації.

Приклад 6. Нехай формула G: ("x)(P(х) Q(f (x),a)). У формулі G є: одна константа а; один одномісний функціональний символ f; один одномісний предикатний символ Р; один двомісний предикатний символ Q. Задано інтерпретацію I формули G:

Оцінка для а:

а

Оцінка для f:

f(1)	f(2)

Оцінки для P і Q:

P(1)	P(2)	Q(1,1)	Q(1,2)	Q(2,1)	Q(2,2)

Визначити істинностні значення G у заданій інтерпретації.

Розв’язання. Якщо х=1, то Р(х) Q(f (x),a)=P(1) Q(f (1),a)==P(1) Q(2,1)=0 0=1.Якщо х=2, то P(x) Q(f (x),a)=P(2) Q(f (2),a)=P(2) Q(1,1)=1 1=1.Оскільки Р(х) Q(f (x), a) істинно для всіх елементів х з області D, то формула ("x)(P(х) Q(f (x),a)) істинна в інтерпретації I.

Приклад 7. Дано формули

F₁: ("x)(P(х) Q(x)),

F₂: P(a).

Довести, що формула Q(a) є логічним висновком формул F₁ і F₂.

Доведення. Розглянемо будь-яку інтерпретацію I, що задовольняє ("x)(P(х) Q(x))ÙР(а). Ясно, що в цій інтерпретації Р(а)=1. Нехай Q(a) 1 у цій інтерпретації, тоді ØP(a)ÚQ(a)=P(a) Q(a)=0 в I. Це значить, що ("x)(P(х) Q(x))=0 в I, а це неможливо. Отже, Q(а) повинна бути істинною в кожній інтерпретації, що задовольняє ("x)(P(х) Q(x))ÙР(а). Це значить, що Q(a) є логічним висновком F₁ і F₂.

Приклад 8. Привести формулу ("x)Р(х) ($x)Q(x) до ВНФ.

Розв’язання.

("x)P(x) ($x)Q(x) = Ø(("x)P(x)) Ú ($x)Q(x)=

($x) ØP(x) Ú($x)Q(x)=($x)(ØP(x)ÚQ(x)).

Отже, випереджена нормальна форма формули ("x)P(x)®($x)Q(x) - це ($x)(ØP(x)ÚQ(x)).

Приклад 9. Отримати ВНФ для формули

("x)("y)(($z)(P(x,z)ÙP(y,z)) ($u)Q(x,y,u)).

Розв’язання.

("x)("y)(($z)(P(x,z)ÙP(y,z)) ($u)Q(x,y,u))=

=("x)("y)(Ø ($z)(Px,z) ÙP(y,z)) Ú($u)Q(x,y,u))=

=("x)("y)(("z)(ØP(x,z) Ú ØP(y,z)) Ú ($u)Q(x,y,u))=

=("x)("y)("z)($u)(ØP(x,z) Ú ØP(y,z) ÚQ(x,y,u)).

Отже, остання формула є ВНФ першої.

Приклад 10. Покажемо застосування логіки першого порядку до розв’язання задач. Нехай дано дві аксіоми

А₁: ("x)(ЛЮДИНА(х) СМЕРТНИЙ(х)).

А₂: ЛЮДИНА(Конфуцій).

З А₁ і А₂ одержати, що Конфуцій смертний, тобто показати, що СМЕРТНИЙ(Конфуцій) є логічним наслідком А₁ і А₂.

Доведення. Ми маємо:

А₁ÙА₂: ("x)(ЛЮДИНА(х) СМЕРТНИЙ(х)) ÙЛЮДИНА(Конфуцій).

Якщо А₁ÙА₂ істинна в інтерпретації I, то обидві формули А₁ та А₂ істинні в I. Тому що (ЛЮДИНА(х) СМЕРТНИЙ(х)) істинна для всіх х, то, коли х заміняється на “Конфуцій”, (ЛЮДИНА(Конфуцій) СМЕРТНИЙ(Конфуцій)) істинна в I, тобто ØЛЮДИНА(Конфуцій) Ú СМЕРТНИЙ(Конфуцій) істинна в I. Однак ØЛЮДИНА(Конфуцій) хибна в I. Отже, СМЕРТНИЙ(Конфуцій) повинна бути істинною в I. Отже, ми показали, що СМЕРТНИЙ(Конфуцій) істинна в I, якщо (А₁ÙА₂) істинна в I. За визначенням СМЕРТНИЙ(Конфуцій) є логічним наслідком А₁ і А₂.

Приклад 11. Одержати ССФ формули ($x)("y)($u)("v)($w)P(x,y,z,u,v,w).

Розв’язання. Дана формула перебуває у випередженій нормальній формі. Скористаємося алгоритмом переходу від ВНФ до скулемівської стандартної форми. У даній формулі лівіше ($x) немає ніяких кванторів загальності, лівіше ($u) стоять ("y) та ("z), а лівіше ($w) стоять ("y), ("z) і ("v). Отже, ми можемо замінити змінну x на константу a, змінну u - на двомісну функцію f(y,z), змінну w - на тримісну функцію g(y,z,v). Таким чином, отримуємо наступну стандартну форму для заданої формули:

Приклад 12. Одержати ССФ для формули

Розв’язання. Спочатку приведемо матрицю до КНФ:

Потім, так як перед ($y) і ($z) є ("x), то змінні y і z заміняються відповідно одномісними функціями f(x) і g(x). Таким чином, одержуємо наступну ССФ:

Приклад 13. Нехай S - ССФ формули F. Якщо F суперечлива, то по теоремі 3 F=S. Якщо F несуперечлива, то F не еквівалентна S. Довести це твердження.

Доведення. Нехай, наприклад, . Зрозуміло, що S - стандартна форма формули F. Виберемо інтерпретацію I у такий спосіб:

Область: D={1,2}; а = 1; значення для P: Р(1) = 0, Р(2) = 1.

Тоді зрозуміло, що F істинна в I, оскільки P(x) ¹ Þ ($x)P(x)=1. Однак S ложна в I, оскільки a=1(P(a)=P(1)=0. Таким чином, F¹S.