теоррия. Кафедра автоматики и вычислительной
 Скачать 44 Kb.
|
 МИНОБРНАУКИ РОССИИ федеральное государственное бюджетное образовательное учреждение высшего образования «Вологодский государственный университет» (ВоГУ) КАФЕДРА АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ ДИСЦИПЛИНА: Логика и теория алгоритмов ЛАБОРАТОРНАЯ РАБОТА ПРОИЗВОДНЫЕ ПРАВИЛА ВЫВОДА Выполнил студент гр. 4Б09 ПО21/зу Иванов Илья Алексеевич Проверил преподаватель Дианов С. В. Вологда 2021 При необходимости вывести новые правила функциональной зависимости, являются так называемые производные правила вывода. Что это за правила, как они получаются? Известно, что если из одних правил, уже существующих, законными логическими методами вывести другие, то эти новые правила, называемые производными, можно использовать наряду с исходными правилами. Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга. Сформулируем производные правила вывода функциональных зависимостей в виде следующей теоремы. Теорема. Следующие правила являются производными от правил вывода Армстронга. Правило вывода 1. ├ Х ∪ Z → Х; Правило вывода 2. Х → Y, Х → Z ├ Х ∪ Y → Z; Правило вывода 3. Х → Y ∪ Z ├ Х → Y, Х → Z; Здесь X, Y, Z, W, так же как и в предыдущем случае, – произвольные подсхемы схемы отношения S. 1. Первое производное правило называется правилом тривиальности и читается следующим образом: «Выводится правило: “объединение подсхем X и Z функционально влечет за собой X”». Функциональная зависимость с левой частью, являющейся подмножеством правой части, называется тривиальной. Согласно правилу тривиальности ограничения тривиальной зависимости выполняются автоматически. Интересно, что правило тривиальности является обобщением правила рефлексивности и, как и последнее, могло бы быть получено непосредственно из определения ограничения функциональной зависимости. Тот факт, что это правило является производным, не случаен и связан с полнотой системы правил Армстронга. 2. Второе производное правило называется правилом аддитивности и читается следующим образом: «Если подсхема X функционально определяет подсхему Y, и X одновременно функционально определяет Z, то из этих правил выводится следующее правило: “X функционально определяет объединение подсхем Y и Z”». 3. Третье производное правило называется правилом проективности или правилом «обращение аддитивности». Оно читается следующим образом: «Если подсхема X функционально определяет объединение подсхем Y и Z, то из этого правила выводится правило: “X функционально определяет подсхему Y и одновременно X функционально определяет подсхему Z”», т. е., действительно, это производное правило является обращенным правилом аддитивности. Любопытно, что правила аддитивности и проективности применительно к функциональным зависимостям с одинаковыми левыми частями позволяют объединять или, наоборот, расщеплять правые части зависимости. При построении цепочек вывода после формулировки всех посылок применяется правило транзитивности с той целью, чтобы включить функциональную зависимость с правой частью, находящейся в заключении. Проведем доказательства перечисленных произвольных правил вывода. 1. Доказательство правила тривиальности. Проведем его, как и все последующие доказательства, по шагам: 1) имеем: Х → Х (из правила рефлексивности вывода Армстронга); 2) имеем далее: Х ∪ Z → Х (получаем, применяя сначала правило пополнения вывода Армстронга, а потом как следствие первого шага доказательства). Правило тривиальности доказано. 2. Проведем пошаговое доказательство правила аддитивности: 1) имеем: Х → Y (это посылка 1); 2) имеем: Х → Z (это посылка 2); 3) имеем: Y ∪ Z → Y ∪ Z (из правила рефлексивности вывода Армстронга); 4) имеем: Х ∪ Z → Y ∪ Z (получаем при помощи применения правила псевдотранзитивности вывода Армстронга, а потом как следствие первого и третьего шагов доказательства); 5) имеем: Х ∪ Х → Y ∪ Z (получаем, применяя правило псевдотранзитивности вывода Армстронга, а после следует из второго и четвертого шагов); 6) имеем Х → Y ∪ Z (следует из пятого шага). Правило аддитивности доказано. 3. И, наконец, проведем построение доказательства правила проективности: 1) имеем: Х → Y ∪ Z, Х → Y ∪ Z (это посылка); 2) имеем: Y → Y, Z → Z (выводится при помощи правила рефлексивности вывода Армстронга); 3) имеем: Y ∪ z → у, Y ∪ z → Z (получается из правила пополнения вывода Армстронга и следствием из второго шага доказательства); 4) имеем: Х → Y, Х → Z (получается, применением правила псевдотранзитивности вывода Армстронга, а затем как следствие из первого и третьего шагов доказательства). Правило проективности доказано. Все производные правила вывода доказаны. |