2.2.2. Класифікація формул логіки предикатів. Логічне слідування.

Приклад 1. Визначити, які з наведених виразів є формулами логіки предикатів (для формул вказати тип (відкрита чи замкнута) і назвати вільні та зв’язані входження змінних):

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

• а) Не формула, оскільки квантор загальності не навішується на формулу. b) Формула, у якій головною є операція імплікація, в області дії квантора загальності — елементарна формула Р(х) Формула відкрита, бо містить вільне входження х у висновку імплікації, с) Не формула, оскільки вираз у дужках містить змінну х, яка вже не є вільною.

d) Відкрита формула, у якій головною операцією є навішування квантора Існування по х, а змінна y є вільною, е) Відкрита формула, у якій головна операція - імплікація, у посилці змінні х та у зв’язані, а у висновку х вільна. f) Замкнута формула, оскільки всі змінні знаходяться в області дії кванторів за цими змінними. g) Не формула, оскільки вираз не є формулою.

h) Відкрита формула, у якій змінні х та z частково вільні (або частково зв’язані), а змінна y зв’язана. ◄

Приклад 2. Якою є формула у кожній інтерпретації:

а) ;

b) ;

c) .

►а) Уданій інтерпретації формула перетворюється на двомісний предикат , визначений на множині дійсних чисел. Це не тотожність, але існує, наприклад, набір x=1, y=0 з області інтерпретації M, на якому отримується істинне висловлення. Отже, в даній інтерпретації формула виконувана. b) У даній інтерпретації формула перетворюється па двомісний предикат , визначений на інтервалі (0;2 ]. Цей предикат рівносильний , який перетворюється в істинне висловлення, якщо або (тобто від’ємне), а це неможливо на даному інтервалі. Отже, в даній інтерпретації формула хибна. с) У даній інтерпретації формула перетворюється на двомісний предикат ,визначений на інтервалі (0;1]. При довільній підстановці замість xта yзначень з даного проміжку отримуємо істинне висловлення , як сума двох додатних доданків. Отже, в даній інтерпретації формула істинна.◄

Приклад 3. Проінтерпретувати кожну з формул:

1. та на множиніМ = {Іван, Петро}, якщо Р(х) — 'ім'я х містить 5 букв", у = Іван;

2. та на множиніМ = N, якщо Р(х) -"х <2";

3. та на множині M=N, якщо P(х) ="x<5" та Q(x) = " x> 6".[2, ст. 37]

►а)Підставляючи y= Іван замість вільного у маємо Отже, перша формула перетворюється у хибневисловлення. У другій формулі головна операція імплікація. Предикат Р(х) спростовний, тому і .b)Предикат Р(х) є виконуваним на М_, тому . Предикат теж виконуваний, тому . c) Предикат тотожно хибний, тому перша формула перетворюється нахибне висловлення. Кожен з предикатів P(x) та Q(x) є виконуваним, тому . ◄

Приклад 4. Предикат А(х,у) заданий на множині М = {1,2,3} таблицею:

y x	1	2	3
1	1	1	1
2	0	0	1
3	1	0	1

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

1. ; c) ;

2. ; d)

► а) При кожному значенні вільної змінної у операцію навішування квантора загальності по х на скінченній множині замінимо кон’юнкцією:

;

;

;

b) Аналогічно операцію навішування квантора існування замінимо диз’юнкцією: ;

;

c) ;

d)│ .◄

Приклад 5. Показати, що при інтерпретації формули на довільній одноелементній множині завжди отримується істинне висловлення, а на двоелементній — не завжди.

• Нехай є одноелементна множина М = {а}. Оскільки множина

значень довільного предиката складається з 0 та 1, то на цій множині можна задати лише два конкретних предикати: або .

Результат підстановки у формулу кожного з цих предикатів та у = а запишемо у таблиці:

P	y	Р(y)
	а	0	0	1
	а	1	1	1

Нехай є двоелементна множина М ={а,b}. На ній можна задати вже чотири різні предикати та так, що: . Усі можливі

інтерпретації запишемо у таблиці:

Р	y	Р(y)
	а	0	0	1
	b	0	0	1
	а	0	0	1
	b	1	0	0
	а	1	0	0
	b	0	0	1
	а	1	1	1
	b	1	1	1

Легко тепер наповнити інтерпретацію, у якій формула перетворюється на хибне висловлення, конкретним змістом. Нехай М = {5,6}, а . Тоді , і . ◄[26, ст.48]

Приклад 6. Встановити, чи виконувані формули логіки предикатів:

1. ; e) ;

2. ; f) ;

3. ; g) ;

4. ; h) .

а) Якщо формула має простий вигляд, то для доведення її виконуваності достатньо навести приклад хоча б однієї інтерпретації, у якій вона перетвориться на істинне висловлення. Щоб формула була істинним висловленням, потрібно щоб предикат був тотожно істинним. Наприклад, при , матимемо ,тому формула виконувана. b) Інколи потрібно провести аналіз формули, щоб отримати протиріччя або підказку, якою має бути інтерпретація. Припустимо, що дана замкнута формула виконувана, тобто існує деякий двомісний предикат , визначений на множині М, що формулаперетворюється у істинне висловлення: .

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

Бо . Припущення про те, що формула виконувана,

привело до протиріччя, отже, вона не виконувана і є суперечністю.с) Ця формула виконувана, оскільки вона виконувана у будь-якій інтерпретації з одноелементною множиною (див.приклад 5). d) Ця формула була б виконуваною, якби у деякій інтерпретації предикат був тотожно істинним. А це неможливо, оскільки при довільних значеннях з області інтерпретації висловлення . Отже, формула не виконувана. е) Нехай дана відкрита формула виконувана: існує предикат на множині М і елемент , що . Тоді за означенням кон’юнкції та . З другої умови випливає, що предикат тотожно істинний, тобто, перетворюється у істинне висловлення при всіх у, а, отже, і при , аз першої умови маємо . Отримали протиріччя, отже, формула не виконувана. f) Нехай формула виконувана, тобто існують предикати та , що . Це означає, що в області інтерпретації існує елемент х₀, що висловлення , тобто предикат тотожно істинний. Тут нема протиріччя. Достатньо вибрати тотожно хибний предикат і буде тотожно істинним при довільному . Наприклад, при ,визначених на множині дійсних чисел, та при довільному предикат В(у) тотожно істинний, бо при всіх   матимем:  . Отже, формула виконувана. g) Нехай виконувана: у деякій інтерпретації маємо

. Тобто предикат тотожно

істинний, при всіх з області інтерпретації . Це означає, що існує таке, що . Оскільки це

виконується при всіх , то предикат тотожно істинний. Тоді і . Отримали протиріччя. Формула не виконувана. h) Нехай виконувана: у деякій інтерпретації маємо

. Звідси існує , що . Далі існує у₀, що . Отже, предикат повинен бути таким, щоб для деяких та виконувалось: та . Це може бути довільний спростовний предикат, наприклад на множині натуральних чисел. Тоді існують, наприклад, та , що  . Отже, дана формула виконувана і її можна у даній

інтерпретації прочитати так: «Серед натуральних чисел є більші за 5 і не більші за 5». ◄

Приклад 7. Встановити, які з формул є тавтологіями логіки предикатів:

a) ;

b) ;

c) ;

d) ;

e) ;

f) .

►а) Очевидно, що формула не тавтологія, бо перетворюється у хибне висловлення, коли предикат Р(х) виконуваний і спростовний, тобто якщо і . Наприклад, Р(х)= "х-парне число" на множині N.b) Припустимо, що формула не тавтологія: існує на деякій множині М предикат , що , тобто і . З першого висловлення за означенням квантора існування випливає, що існує таке, що звідки випливає, що предикат (*) тотожно істинний. З другого висловлення випливає, що існує таке, що , а це означає, що предикат (**) тотожно хибний. Оскільки та належать області інтерпретації, то з (*) маємо а з (**) – що . Це протиріччя доводить, що формула тавтологія, с) Нехай Q(x,y)="x,y"на множині натуральних чисел. Тоді (для кожного натурального числа існує більше за нього) і (не існує найбільшого натурального числа). У даній інтерпретації формула перетворюється у хибне висловлення, тому не є тавтологією.d) Нехай дана відкрита формула не тавтологія: існують предикати і , що . Звідси та . Предикат не тотожно істинний, тому існує , що . Не отримали протиріччя, але маємо підказку, що інтерпретація, у якій формула перетвориться у хибне висловлення, повинна бути такою, щоб , і .

Наприклад, можна на множині натуральних чисел задати .Тоді . Отже, формула не тавтологія, е) Якби у деякій інтерпретації формула була хибною, то посилка імплікації , а висновок хибний.Це означає, що одне з висловлень або істинне. Тобто, один з предикатів або тотожно істинний. Тоді їх диз’юнкція тотожно істинний предикат, а тому висновок імплікації . Отже, при істинній посилці висновок не може бути хибним. Формула є тавтологією. f) Розглянемо інтерпретацію на множині натуральних чисел ="х—парне" та = "x-непарне". Тоді посилка = │"довільне число парне або непарне"│ = 1, а висновок = "довільне число парне"˅"довільне число непарне"|= . Формула у цій інтерпретації хибна, тому вона не тавтологія. ◄[25, ст.36]

Приклад 8. Довести, що формули є тавтологіями логіки предикатів (тут формулаА не містить вільних «змінних):

1. ;

2. ;

3. ;

4. ;

5. ;

6. .

а) Припустимо, що формула не тавтологія. Тобто існує предикат на деякій множині М і елемент , що . Тоді

і . З першої умови випливає, що тотожно істинний предикат, що суперечить другій умові. Отже, припущення не вірне, формула тавтологія. b) Якщо формула містить еквіваленцію, то доведення того, що вона істинна в будь-якій інтерпретації, можна проводити одним із шляхів, залежно від вигляду лівої і правої частинй:

1 1 0 0 1 1

↔ ↔ ↔

1 1 0 0 0 0

Наприклад, щоб довести, що ,розглянемо довільну інтерпретацію з предикатом на деякій множині М, на якій ліва частина перетворюється в істинне висловлення (за першою схемою). Тоді . За означенням навішування квантора загальності предикат - спростовний, тоді - виконуваний. Отже, - права частина в цій інтерпретації теж перетворюється в істинне висловлення. Навпаки, якщо права частина у деякій інтерпретації , то за означенням квантора існування виконуваний,отже, Р₀(х)- спростовний і . Тоді ліва частина теж Отримали, що у довільній інтерпретації ліва та права частини еквіваленції мають однакове логічне значення, тому формула є тавтологією, с) Нехай ліва частина формули у деякій інтерпретації - Тоді предикат тотожно істинний, а це можливо, лише коли кожен з предикатів Р(х) та Q(x)тотожно істинний. Тоді обидва висловлення та істинні, тому їх кон’юнкція у правій частині формули теж істинна . Навпаки (за першою схемою) міркуємо аналогічно. d) Нехай у деякій інтерпретації ліва частина формули хибна: . Тоді предикат тотожно хибний. ОскількиА не містить вільних змінних, то вона може перетворюватися як у істинне, так і в хибне висловлення. Якщо , то з хибності випливає, що P(x) тотожно хибний. Тоді і права частина .Якщо , то для будь-якого предиката Р(х) права частина теж 0. Навпаки, якщо справа , то або - і тоді тотожно хибний предикат і , або - і тоді Р(х) тотожно хибний, тотожно хибний і ліва частина теж . За другою схемою обидві частини формули мають однакове значення істинності у будь-якій інтерпретації, тому маємо тавтологію. е) За першою схемою, якщо , то існує елемент , що . При повинно , тобто Р(х) спростовний, і . При права частина істинна завжди . Навпаки доводимо аналогічно. f) Якщо зліва , то предикат тотожно істинний. При повинен бути тотожно істинним, тому і справа

При завжди матимемо . У другу сторону доводимо аналогічно. ◄

Приклад 9.Перевірити, чи правильні міркування:

1. всі ромби є паралелограмами. Всі квадрати - ромби. Отже, всі квадрати - паралелограми;

2. кожний ромб є паралелограмом. Деякі паралелограми - квадрати. Отже, деякі ромби — квадрати;

3. кожний математик мислить логічно. Той, хто мислить логічно, не робить логічних помилок. Іван робить логічні помилки. Отже, Іван - не математик.

►а) Введемо предикати М(х)= "x - ромб ", S(x)="x-квадрат " та P(x)= "x - паралелограм". Формулою дані міркування можна записати так: ⊨ . Маємо силогізм ААА першої фігури, який називають Barbara.Припустимо, що міркування не правильні(нема логічного слідування). Тобто, існує інтерпретація, у якій обидві посилки перетворюються в істинні висловлення, а висновок - у хибне : , а

Тоді предикати та тотожно істинні, а предикат спростовний. Тобто існує в області інтерпретації елемент , що , звідси а Оскільки повинно бути, що то . Тоді , а це перечить тому, що предикат тотожно істинний. Отримане про тиріччя доводить правильність міркувань. b) За допомогою предикатів прикладу а) дані міркування запишуться формулами:  ⊨ _. Тут встановлюється відношення між М та Sчерез Р. Це силогізм четвертої фігури AII. Припустимо, що міркування нелогічні.Тобто, існує інтерпретація, у якій а Тоді

Предикат тотожно істинний, предикат виконуваний, а предикат тотожно хибний. З виконуваності предиката випливає, що існує в області інтерпретації елемент , такий що , звідси і . Оскільки повинно бути, що , то . Тоді . Суперечності не отримали. Тому правильне припущення про нелогічність таких міркувань. Висловлення посилок та висновку можна ілюструвати кругами Ейлера. З ілюстрації міркувань для прикладів а) та b) видно, що у першому випадку висновок очевидний, а у другому з двох даних посилок випливає, що ромби можуть не бути квадратами. Щоб отримати висновок про те, що деякі ромби – квадрати, потрібно вибрати інші посилки. с) Введемо М(х)= “х-математик”, S(x)= “x-мислить логічно” та Р(х)= “x- робить логічні помилки”, І=Іван. Формулою дані міркування можна записати так :

⊨ . Нехай міркування нелогічні, тоді всі посилки істинні, а висновок хибний: , але . Звідси випливає, що предикати та тотожно істинні, і . Оскільки повинно , то . Тоді , а це суперечить тому, що предикат тотожно істинний. Отже, висновок у даних міркуваннях отримано правильно. Проілюструйте це за допомогою кругів Ейлера. ◄