Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2018-01-29 | 812 |
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. Схемы аксиом ИВ независимы.
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!