Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2018-01-29 | 808 |
5.00
из
|
Заказать работу |
|
|
Теорема 3. Пусть φ, ψ, χ ‑формулы ИВ. Тогда имеют место эквивалентности:
1) φ∧φ≡φ, φ∨φ≡φ (законы идемпотентности);
2) φ∧ψ≡ψ∧φ, φ∨ψ≡ψ∨φ (законы коммутативности);
3) (φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);
4) φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)
5) (φ∧ψ)≡φ∨ψ, (φ∨ψ)≡φ∧ψ (законы де Моргана);
6) φ≡φ (закон двойного отрицания);
7) φ→ψ≡φ∨ψ;
8) φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);
9) φ∨(φ∧ψ)≡φ∨ψ, φ∨(φ∧ψ)≡φ∨ψ;
10) φ∧(φ∨ψ)≡φ∧ψ, φ∧(φ∨ψ)≡φ∧ψ.
11) ├φ∨φ.
Доказательство. В примере 15 показано, что φ├φ, покажем, что φ├φ. По теореме о дедукции φ├φ φ→φ (аксиома), значит, φ├φ.
Докажем закон де Моргана (φ∧ψ)≡φ∨ψ. Строим квазивывод формулы (φ∧ψ)→φ∨ψ:
1) ((φ∨ψ)→φ)→(((φ∨ψ)→ψ)→((φ∨ψ)→φ∧ψ)) (схема аксиом 5);
2) φ→φ∨ψ (схема аксиом 6);
3) (φ∨ψ)→φ (к п. 2 применили пример 15);
4) φ→φ (схема аксиом 10);
5) (φ∨ψ)→φ (к пп. 3 и 4 применили пример 13);
6) (φ∨ψ)→ψ (получается аналогично формуле 5);
7) ((φ∨ψ)→ψ)→((φ∨ψ)→φ∧ψ) (к пп.5 и 1 применили правило вывода);
8) (φ∨ψ)→φ∧ψ (кпп. 6 и 7 применили правило вывода);
9) (φ∧ψ)→(φ∨ψ) (к п. 7 применили пример 15);
10) (φ∨ψ)→(φ∨ψ) (схема аксиом 10);
|
11) (φ∧ψ)→φ∨ψ (к пп. 9 и 10 применили пример 13).
Строим квазивывод формулы φ∨ψ→(φ∧ψ):
1) (φ→(φ∧ψ))→((ψ→(φ∧ψ))→((φ∨ψ)→(φ∧ψ))) (схема аксиом 8);
2) φ∧ψ→φ (схема аксиом 3);
3) φ→(φ∧ψ) (к п. 2 применили пример 15);
4) φ∧ψ→ψ (схема аксиом 4);
5) ψ→(φ∧ψ) (к п. 4 применили пример 15);
6) (ψ→(φ∧ψ))→((φ∨ψ)→(φ∧ψ)) (к пп. 3 и 1 применили правило вывода);
7) (φ∨ψ)→(φ∧ψ) (к 5 и 6 применили правило вывода).
Таким образом, закон де Моргана (φ∧ψ)≡φ∨ψ доказан.
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ╞φ), если φ(x1,…,xn) – тождественно истинная формула как формула алгебры высказываний.
Теорема 4 (о полноте). Формула φ ИВ доказуема тогда и только тогда, когда φ тождественно истинна:
├φ ╞φ.
Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности ≡ в АВ и ИВ совпадают.
Пример 6. Доказать, что φ├φ.
По теореме о дедукции это равносильно тому, что ├φ→φ. В свою очередь, по теореме о полноте, достаточно доказать, что ╞φ→φ. Составляя таблицу истинности для формулы φ→φ, убеждаемся, что φ→φ тождественно истинна и, следовательно, доказуема.
Исчисление называется противоречивым, если любая формула данного исчисления доказуема в этом исчислении.
Исчисление называется непротиворечивым, если оно не является противоречивым
Теорема 5 (о непротиворечивости). ИВ непротиворечиво.
Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х∧х. Следовательно, ИВ непротиворечиво.
|
Множество формул Г называется противоречивым, если Г├x∧x. Если Г ‑ противоречивое множество формул, то будем обозначать этот факт через Г К Множество формул Г называется непротиворечивым, если Г не является противоречивым множеством.
Утверждение 3. Формула φ выводима из множества формул Г тогда и только тогда, когда множество Г∨{φ}‑ противоречиво:
Г├φ Г,φ├.
Доказательство. Поскольку отношение эквивалентности ≡ в АВ и ИВ совпадают, то φ≡φ→x∧x в ИВ. Пусть Г={φ0,…, φn}. Тогда, пользуясь утверждением 2, следствием 1 и теоремой о замене, получаем
Г├φ φ0∧…∧φn├φ ├φ0∧…∧φn→φ ├φ0∧…∧φn→(φ→x∧x)
φ0∧…∧φn,φ├x∧x Г∨{φ}├x∧x,
что и доказывает утверждение.
Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы. Доказательство следующей теоремы не приводится в виду его громоздкости.
Теорема 6. Схемы аксиом ИВ независимы.
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!