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

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

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

;

;

;

;

;

.

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

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

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

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

Структура системи освіти
Шкільний обов'язок не є в Німеччині однорідним на всій її території. Різні рішення спостерігаються в окремих німецьких землях: 9 або 10 років навчання, починаючи від 6 року життя дитини. Як ...

Закономірності розвитку дитини з мовленнєвими порушеннями
Уся нескінченна різноманітність зовнішніх проявів мозкової діяльності зводиться тільки до одного явища – м’язової діяльності. Сміється дитина при вигляді іграшки, чи Ньютон створює світові ...

Майстри петриківського розпису
У Петриківці було багато селянок-майстринь, котрі розписували хати та виготовляли «мальовки» на продаж, але лише одній з них судилося зіграти винятково важливу роль у дальшому розвитку петр ...