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

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

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

;

;

;

;

;

.

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

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

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

Рекомендуємо почитати:

Основні прийоми каліграфічного письма
Графічні прийоми письма. В основі оволодіння письмом лежать рухові навички. Процес вироблення навички письма молодшого школяра передбачає формування як технічних, так і графічних навичок. П ...

Сутність поняття «колектив», «виховуючий колектив»
Дослідженням колективу займалися такі видатні педагоги як П.П. Блонський, С.Т. Шацький, Н.К. Крупська, В.А. Сухомлинський. Узагальнюючи їх ідеї можна зробити висновок, про те, що колектив в ...

Нерівність трикутника
Якщо точки й різні, то відстанню між ними називається довжина відрізку . Якщо точки й збігаються, то відстань між ними приймається рівною нулю. Теорема 8.1 (нерівність трикутника). Які б не ...