Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Визначення

Завдання

Запитання

1. Що розуміють під колізією змінних?

2. До яких наслідків може призвести перенесення квантора на початок формули? Наведіть приклади коректного і некоректного перенесення кванторів на початок формули.

3. Поясніть суть заміни зв'язаної змінної.

4. Сформулюйте комутативні властивості кванторів.

5. За дотримання якої умови правомірно використовування дистрибутивних властивостей кванторів?

6. Яким чином можна обійти обмеження дистрибутивних властивостей кванторів?

7. Запишіть формули закону де Моргана для кванторів.

1. Опустіть знаки заперечення безпосередньо на предикати або булеві змінні:

а) Ø($х) (Ø("y) (B(y)Ú ($z)С(z)) ÙØА(х)));

б) Ø("y) (Ø$х) (А(у, z)Ú B(x))Ú C(z));

в) Ø($x) (Ø"y) (A(x) ® B)) Ú C(x, y));

г) Ø("u) Ø("v)(P(u) ® Q(v) ® A(z)).

2. Встановіть, чи еквівалентні задані предикати:

а) ($х)(А(х) Ù ØВ(у))и ("z)(А(z) ® В(у));

б) ("x)((A(x) ® В(х)) Ù (А(х) ®ØВ(х))) и Ø($у) А(у).

3. Винести за дужки квантори:

а) ($ v) C(v, у)Ù (($х) А(х) Ú В);

б) ($х)($y) А(х, у) Ù ($х)($у) В(х, у);

в) ($х) А(х, у) Ú (("x) B(x)Ú ("y) С(у));

г) ($x)("y)A(x, у) Ù ($х)($z) (В(х, z) Ù ($y)A(x, у)).

4. Довести загальнозначущість таких формул:

а) ("x)P(x) ® ($y)P(y);

б) ("x)P(x) Ú (($y)ØP(y)).

5. Довести, що формула ("x)P(x) Ù ($у)ØР(у)суперечлива.

6. Довести, що формула Р(а)®Ø(($х)Р(х)) несуперечлива.

5.9. Випереджені нормальні форми і логічний висновок у логіці предикатів

Випереджена нормальна форма, алгоритм зведення до випередженої нормальної форми, правила видалення/введення квантора загальності/існування

В логіці висловлень було введено дві нормальні форми: кон'юнктивна і диз'юнктивна. В логіці предикатів вводиться третя нормальна форма, що називається випередженою нормальною формою.

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

Для перетворення виразів довільної форми у ВНФ необхідно по черзі виконати такі етапи перетворення.

1. Виключити логічні зв'язки еквіваленції (~) та імплікації (®), виразивши їх через операції диз'юнкції, кон'юнкції і заперечення за допомогою таких законів:

;

2. Опустити знаки операцій заперечення безпосередньо на предикати, використовуючи закон подвійного заперечення Ø(Ø F) = F і закони де Моргана Ø(F Ú G) = ØF ÙØG, Ø(F Ù G) = ØF Ú ØG, у тому числі для кванторів:

; .

3. Якщо необхідно, перейменувати зв'язані змінні.

4. Винести квантори на початок формули, використовуючи відповідні закони, для одержання випередженої нормальної форми.

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

Розв'язок. Спочатку виключимо імплікацію, потім опустимо знак операції заперечення безпосередньо на предикат і винесемо квантор на початок:

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

Розв'язок. Скористаємося наведеним вище алгоритмом.

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

Правило видалення квантора загальності

використовується для доведення істинності F(c),де с — довільно обраний елемент предметної області D, у якій справедливе "х F(x). Наприклад, із засновку «Всі студенти бажають одержувати добрі оцінки» робимо висновок: «Студент Петров бажає одержувати добрі оцінки».

Правило введення квантора загальності

стверджує істинність "х F(x), якщо доведена істинність F(c)для будь-якого с, тобто для всіх елементів с з розглянутої предметної області D.

Правило видалення квантора існуванняв істинній формулі $х F(x)полягає в позначенні імені елемента с (конкретного або гіпотетичного), для якого F(c)істинне:

Правило введення квантора існування

дозволяє вирішити, що $х F(x)є істинним, коли відомий деякий елемент с, для якого істинне F(c).

Крім наведених правил, у логіці предикатів у ході дедуктивного висновку можна використовувати всі правила, які застосовуються для дедуктивних висновків у логіці висловлень.

Приклад.Показати, що з тверджень «Всі у першій групі вивчають математику» і «Маша — студентка першої групи» маємо висновок: «Маша вивчає математику».

Розв'язок. Позначимо через F(x)предикат «х є студент першої групи», а через М(х) — «х вивчає математику». Тоді засновки можна записати у вигляді: "х (F(x)® М(х)) і F(Маша) відповідно, а потрібний висновок — М(Маша). Для одержання цього висновку необхідно здійснити таку послідовність дій:

1. "х (F(x)® М(х)) перший засновок.

2. F(Маша)® М(Маша) крок 1, правило видалення квантора ".

3. F(Маша) другий засновок.

4. М(Маша) кроки 2 і 3, правило відділення. Таким чином, одержано шуканий результат.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Завдання	\|	Завдання

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.009 сек.