жуть задаватися будь-якими логічними виразами, в тому числі і які не є ДНФ-виразами! І тут у допитливого учня може виникнути питання: а чому так зроблено? Як бути, якщо фільтр не є ДНФ-виразом? Це що, недогляд розробників, або тут є якийсь резон? p>
На жаль, "призначена для користувача" інформатика (мабуть слідом за розробниками програмного продукту), дуже не любить відповідати на подібні питання. А даремно. Ми вважаємо, що шкільна інформатика повинна не тільки відповідати на ці питання, але і стимулювати їх появу в учнів. Виявляється, резон є. Справа в тому, що всяке логічне вираз еквівалентно деякого ДНФ-виразу. І ми це зараз доведемо. А заодно дамо та алгоритм відомості довільного логічного виразу до ДНФ-виразів. p align=center> Зведення довільного логічного виразу до ДНФ-виразів.
Визначення 4 . Нехай Х і У - логічні вираження з однаковими наборами атомів. Скажімо, що Х і У рівносильні , якщо вони приймають однакові значення для будь-якого набору значень вхідних в них атомів. p> Символічно еквівалентність виразів Х і У позначається як ХГ› У.
Лемма 1 . Нехай Х і У - довільні логічні вирази. Тоді NOT (Х OR У) Г› (NOT Х) AND (NOT У)
Доказ . Ми тільки що побудували таблицю істинності для NOT (Х OR У). Побудуйте таку ж таблицю для Г› (NOT Х) AND (NOT У) і порівняйте обидві таблиці. br/>
Лемма 2 . Нехай Х і У - довільні логічні вирази. Тоді NOT (Х AND У) Г› (NOT Х) OR (NOT У). p> Доказ : аналогічно доведенню леми 1.
Лема 3 . Нехай Х, У і Z-довільні логічні вираження. Тоді Х AND (У OR Z) Г› (Х AND У) OR (Х AND Z). p> Доказ : побудуйте таблиці істинності для обох виразів.
Теорема 2. Всяке логічне вираження еквівалентно деякого ДНФ-виразу. p> Ескіз докази. Ідея докази дуже проста. Спочатку ми з допомогою лем 1 і 2 заганяємо все NOT всередину AND та OR, а потім, за допомогою леми 3 - усі AND всередину OR. Формальний опис цієї процедури досить громіздке і тому ми обмежимося прикладом. Нехай Х, У і Z- довільні атоми. Тоді Х AND NOT (У AND Z) Г› Х AND (NOT У OR NOT Z) Г› (Х AND NOT У) OR (Х AND NOT Z). p align=center> Висновок .
Отже, ми переконалися, що фільтр - це просто логічне вираз, а фільтрування - вибір кортежів, на яких цей вислів істинно. Фільтр записується на бланку QBE. Цей бланк пристосований для запису ДНФ-виразів. Такий вибір не випадковий: будь логічне вираження еквівалентно деякого ДНФ-виразу. Такі, на наш погляд, основні ідеї, лежать в основі реалізації фільтра в Access.
Зазначимо, до речі, що в Access існують ще й інші конструкції, ідейно дуже близькі до фільтру, але оформлені, часом, абсолютно по-іншому. Зокрема, це ЗАПИТИ НА ВИДАЛЕННЯ (див. [6]), а також УМОВИ НА ЗНАЧЕННЯ, що задаються або у властивостях таблиці, або в Властивості поля. Співвідношення фільтра, умови на значення і ЗАПИТУ НА ВИДАЛЕННЯ можна пояснити так. Кож...
