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

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

Сторінка 1

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страницы: 1 2

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

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

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

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

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

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

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

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