Рівносильні формули. Нормальні форми

Нова педагогіка » Особливості контролю знань логіки предикатів » Рівносильні формули. Нормальні форми

Сторінка 1

Дві формули А і В називаються рівносильними , якщо кожна з них є логічним наслідком іншої.

Можна довести, що тоді і тільки тоді, коли ⊨.

В логіці предикатів рівносильними будуть формули, отримані з рівносильних формул алгебри висловлень підстановкою замість пропозиційних змінних довільних формул логіки предикатів (окремі випадки). Наприклад, рівносильними будуть формули

,

бо вони отримані з рівносильностей і за допомогою різних підстановок.

Крім окремих випадків у логіці предикатів є рівносильності, пов’язані з операцією навішування кванторів. Деякі рівносильності можна записати із тавтологій, що містять головну операцію , доведення яких здійснено у попередньому пункті. Варто пам’ятати рівносильності, що часто використовуються при рівносильних перетвореннях формул та при зведенні їх до нормальних форм:

-закони перейменування змінних;

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

-дистрибутивні закони (і тільки такі два!);

-закони перенесення кванторів через кон’юнкцію, тут і далі Qне містить вільного x;

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

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

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

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

Випереджена нормальна форма (ВНФ) довільної формули А логіки предикатів має вигляд , де -довільна сукупність кванторів (префікс формули А), а В-формула, яка не містить кванторів.

Теорема. Для кожної формули логіки предикатів існує зведена та випереджена нормальна форми.

Щоб отримати зведену форму, потрібно скористатися законами, що дозволяють виразити через , , та законами де Моргана. Після застосування дистрибутивних законів та законів пронесення кванторів через логічні операції (винесення кванторів за дужки) отримують випереджену форму. Тут буває необхідно перейменовувати змінні у області дії кванторів, але робити це треба так, щоб не трапилось «колізії». Для перейменовування краще використовувати імена змінних, які у формулі не зустрічаються. Потрібно пам’ятати, що вільні змінні не перейменовуються, а одна і та ж змінна у областях дії різних кванторів може перейменовуватись на різні змінні. Наприклад,

зведена форма даної формули. Квантор загальності та існування не можна винести за дужки (пронести через диз’юнкцію), бо змінна х входить в усі доданки. Перейменуємо в області дії першого квантора хнау, а в області другого на z. Далі по черзі пронесемо квантори через диз’юнкцію:

випереджена нормальна форма, яка рівносильна даній формулі.

При аналізі формул логіки предикатів на виконуваність зручно мати формулу, яка не містить кванторів існування, а її матриця представлена у кон’юнктивній нормальній формі (кнф). Вилучення кванторів існування із префікса ВНФ проводять за допомогою введення сколемівських сталих та сколемівських функцій за правилом:

Страницы: 1 2

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

Соціальна педагогіка в системі педагогічних наук
Соціальна педагогіка, проходячи складний період визначення своєї соціокультурної сутності в умовах інформаційного суспільства, вичленовування із загально педагогічного знання, вимагає акцен ...

Технологія розвитку критичного мислення
Технологія розвитку критичного мислення формує творче мислення, сприяє розвитку креативності. Критичне мислення необхідне під час розв’язування проблемних задач, формулювання висновків, оці ...

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

Викладання іноземної мови

Викладання іноземної мови

У ДНЗ навчання дітей англійської мови доцільно розпочинати з п'ятилітнього віку. Більшість дітей цього віку досягають інтелектуальної, вольової, мотиваційної та емоційної готовності вивчати другу мову у колективі. >>>

Copyright © 2019 - All Rights Reserved - www.edudirect.net