Головна

 Предикати. |  Равносильность і проходження предикатів. |  Застосування логічних зв'язок |  Контрольні завдання. |

Равносильности і тотожно істинні імплікації логіки предикатів, що містять квантори

  1.  Exercise II. Переведіть пропозиції, що містять Participle I.
  2.  II. ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ
  3.  Азотовмісні пятічленниє гетероцикли
  4.  Азотовмісні пятічленниє гетероцикли
  5.  азотовмісні сполуки
  6.  Азотовмісні сполуки нафт
  7.  Аксіоми алгебри логіки.

Неважко переконатися, що мають місце такі равносильности:

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

1) ;

2) .

вираз кванторів одного через інший

3) ;

4) ;

закони пронесення кванторів через кон'юнкцію і диз'юнкцію

5) ;

6) ;

7) ;

8) ;

закони перенесення кванторів через імплікації

9) ;

10) ;

11) ;

12) ;

закони коммутативности для кванторів

13) ;

14) ;

тотожно істинні імплікації

15) ;

16) ;

17) .

Доведемо деякі з цих тотожностей.

1) нехай  - Предикат, визначений на множині М. Для доведення істинності тотожності  потрібно переконатися, що обидві частини еквівалентності одночасно істинними або одночасно хибні. Справді, висловлювання  істинно тоді і тільки тоді, коли висловлювання  помилково, що можливо тоді і тільки тоді, коли предикат  Спростовано. Далі, опровержімие предиката  означає здійснимість його заперечення  , Що рівносильно істинності висловлювання  . Отже, висловлювання  істинно тоді і тільки тоді, коли істинно висловлювання  , Що і доводить тотожність.

Тотожність 2) пропонується перевірити самостійно.

Тотожності 3) і 4) випливають безпосередньо з тотожностей 1) і 2) і закону подвійного заперечення.

5) нехай предикати и  визначені на деякій множині М. Доведемо його істинність  . висловлювання  істинно тоді і тільки тоді, коли предикат  тотожно істинний, що на можливо тоді і тільки тоді, коли обидва предиката и  тотожно істинні. Далі, тотожна істинність предикатів и  рівносильна істинності висловлювань и  відповідно, що рівносильно істинності їх кон'юнкції  . Отже, ліва і права частини тотожності одночасно істинними і одночасно помилкові, що доводить його істинність.

Тотожності 6) і 7) пропонується довести як вправа.

8) У цьому тотожність  - Нульместний предикат (конкретне висловлювання), а  - Предикат, визначений на множині М. Доведемо його істинність  . Дійсно, висловлювання  істинно тоді і тільки тоді, коли предикат  виконаємо. Останнє можливо, якщо і тільки якщо предикати и  здійснимі. (Нагадаємо, що під здійсненне нульместного предиката (висловлювання) розуміється його істинність.) Далі, здійсненність предиката  і істинність висловлювання  рівносильні істинності висловлювань и  , А значить, і істинності їх кон'юнкції  . Це і доводить тотожність.

9) нехай  - Предикат, визначений на множині М. Відзначимо, що предикат  в тождествах 9), 10), 11), і 12) може бути не тільки нульместним, але і будь-яким п-місцевим, важливо лише, щоб у нього не входила предметна змінна х. Тобто  має вигляд  і визначено на безлічі  . Для стислості будемо вважати, що  - Одномісний предикат .

Припустимо, що дане тотожність  не є істинним. В цьому випадку предикат (від у)  - Спростовано, тобто звертається в помилкове висловлювання при підстановці замість предметної змінної у деякого конкретного предмета :

.

Еквівалентність помилкова, якщо її члени беруть різні значення істинності, тобто тут можуть представитися дві можливості:

перша

 ; (1)

 (2)

і друга

 ; (3)

 (4)

Розглянемо першу можливість. З формули (2), за визначенням імплікації, маємо

 ; (5)

 . (6)

Далі, з формули (5) і за визначенням квантора існування робимо висновок, що предикат  виконаємо, тобто для деякого

 . (7)

Повернемося до співвідношення (1). За визначенням квантора спільності предикат  тотожно істинний. Зокрема, якщо замість предметної змінної х підставити  , То отримаємо справжнє висловлювання  . Але, з огляду на (6) і (7), отримуємо  . Протиріччя.

Розглянемо другу можливість, виражену в співвідношеннях (3), (4). З формули (3), на підставі визначення квантора спільності, слід, що предикат  Спростовано, тобто  для деякого  . Тоді за визначенням імплікації отримаємо

,  . (8)

З огляду на друге з співвідношень (8), зі співвідношення (4) робимо висновок, що  . Останнє означає тотожну хибність предиката  . Зокрема, для предмета  маємо  , Що суперечить першому з співвідношень (8).

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

Тотожності 10), 11) довести самостійно.

12) нехай  - Предикат, визначений на множині М, а  - На безлічі  . Припустимо, що дане тотожність  не є істинним. Тоді предикат (від у)  Спростовано, Спростовано, тобто звертається в помилкове висловлювання при підстановці замість предметної змінної у деякого конкретного предмета :

,

Еквівалентність помилкова в двох випадках. По перше, коли

 ; (1)

 , (2)

і, по-друге, коли

 ; (3)

 . (4)

Розглянемо перший випадок. Зі співвідношення (2), за визначенням імплікації, робимо висновок:

 ; (5)

 . (6)

Співвідношення (6) свідчить про те, що предикат  тотожно хибна. Далі, співвідношення (1) показує, що предикат  виконаємо. З огляду на співвідношення (5), отримуємо: існує такий елемент  , що  . Останнє суперечить доведеною вище тотожною хибності предиката  . Отримати протиріччя в другому випадку, вираженому в співвідношеннях (3), (4), пропонується самостійно. Таким чином, розглядається тотожність справедливо.

Тотожності 13), 14) і імплікації 15), 16 доведіть самостійно.

17) нехай предикат  , Певний на безлічі  , Припустимо, що імплікація  помилкова, тоді

 ; (1)

 . (2)

Зі співвідношення (1) за визначенням квантора існування випливає, що предикат (від у)  виконаємо, тобто  для деякого  . Останнє, за визначенням квантора спільності, означає, що предикат  тотожно істинний на  . Отже, тотожне істинним на  буде і одномісний (від х) предикат  . Але тоді, за визначенням квантора спільності,  , Що суперечить співвідношенню (2). Отже, дана імплікація тотожно істинна.

 



 квантори |  обмежені предикати
© um.co.ua - учбові матеріали та реферати