Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Оснащения врачебно-сестринской бригады.
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-09-30 | 319 |
5.00
из
|
Заказать работу |
|
|
Результаты двух последних теорем позволяют утверждать, что тогда и только тогда, когда . Таким образом установлена связь м/у доказуемостью и выводимостью. Определим связь м/у доказуемостью и общезначимостью:
тогда и только тогда, когда .
Введем определения:
Формульная аксиоматическая теория называется (просто) непротиворечивой, если ни для какой формулы А формулы А и не являются обе доказуемыми в ней.
Формульная аксиоматическая теория называется (просто) противоречивой, если существует формула А, для которой одновременно А и доказуемы в этой теории.
Теорема 4: Если , то для любой формулы Е.
По условию Е доказуема, то есть заканчивается конечная последовательность формул, являющихся или аксиомами, или функциями, полученными по правилу MP из некоторых двух предшествующих формул. Аксиомы, согласно правилу MP формула В получается из формул А и . Так как посылки А и общезначимы, то по определению импликации. Посылки обязательно будут , т.к. у первой формулы формального доказательства выводимой по MP посылками являются аксиомы. Таким образом, все формулы формального доказательства общезначимы, общезначима и последовательность формул.
Следствие
Исчисление высказываний непротиворечива
Допустим, что исчисление высказываний противоречива. Тогда по определению противоречивой формальной аксиоматические теории доказана существуют формула А, такая, что А и . Тогда по Т4 и . По определению тавтологии формула А общезначима, если в любой интерпретации она принимает значение И. Поэтому вывод и приводит к абсурду. Можно сделать вывод, что , если – противоречия.
Рассмотрим теорему обращения МТ5, определяющую связь с логическим следованием и выводимостью.
|
Метатеорема 5: Для любого конечного множества формул Г и для любых формул А, В, С справедливы правила (введения и удаления), приведенные ниже:
Введение | Удаление | |||||
Если Г, , то | ТД, ВИ | МР, УИ | ||||
ВК | 4,5 | УК1, УК2 | ||||
6,7 | , | ВД1, ВД2 | и , то | УД | ||
и , то | RA,BO | УДО СУО | ||||
, | ВЭ | УЭ1 УЭ2 |
Все правила доказываются с использованием АС и МР, из них уже доказаны 1 и 3. Правило 2 является исходящим правилом ИВ.
Докажем правило 8:
1. А
2. В
3.
4.
5.
6.
7.
8.
9.
10. С
1. Посылка
2. Посылка
3. ВИ(1)
4. ВИ(2)
5. АС6
6. МР (F1,F2)
7. AC8
8. MP(F3,F7)
9. MP(F1,F8)
10. MP(F6,F9)
Подобным образом доказываются остальные правила.
Надо отметить, что здесь речь идет о правилах вывода, а не о правилах следования. Они имеют разные доказательства, но тем не менее предложение равносильно , различие лишь в описании одних и тех же правил.
Доказанные правила описывают широко используемые рассуждения.
Чтобы доказать предложение линейной структуры , обычно доказывают по отдельности А и В, а затем говорят «теорема доказана», т.е. доказуема . То есть за фразой «теорема доказана» скрыт неявный переход от А и В к , т.е. правило ВК.
Например, при доказательстве предложения:
(1) «средняя линия трапеции параллельна основаниям и равна их полусумме» -
Доказывают каждое из предложений:
(2) «средняя линия трапеции параллельна основаниям» -(А)
(3) «средняя линия трапеции = n/сумме оснований» - (В)
и заканчивают доказательство словами «теорема доказана».
Правилам УК1,УК2 соответствуют предложения типа:
«Найдите среднюю линию трапеции с основанием А и С». Из предыдущих предложений – конечная (1) используют только его второй член В и находят среднюю линию трапеции 12/
Предложения, имеющие пир-ру эквиваленции обычно выражают оборотами «т. А и т. Т, к. В», «для того, чтобы А, необходимо и доказательство В», «если А, то В, и если В, то А» и некоторые уравнения.
Доказательство таких предложений распадается на две части:
|
1) Доказательство импликации
2) Доказательство импликации
После этого заключается, что предложение доказано, т.е. .
Полнота теории L.
В математике существует три важнейших математических проблемы:
Непротиворечивость,
полнота,
Разрешение.
Мы рассмотрим определение непротиворечивости. Введем понятие полноты.
Определение 1.19
Логической непротиворечивости исчислению называется полным относительно общезначимости, если в нем доказуема любая общезначимость формул.
Прежде чем установить полноту ИВ, необходимо доказать 4 лемма.
Лемма 1.1: Пусть д имеем логические операторы .
Для любой строки истинной таблицы любой из 5 операторов имеет место соответствия выводимость.
А | Выводимость |
1. И Л 2. Л И | |
А В | Выводимость |
3. И И И 4. И Л Л 5. Л Л Л 6. Л Л Л | |
А В | |
7. И И И 8. И Л Л 9. Л И И 10. Л Л Л | |
А В | Выводимость |
11. И И И 12. И Л Л 13. Л И И 14. Л Л И | |
А В | |
15. И И И 16. И Л Л 17. Л И Л 18. Л Л И |
Установим некоторые из выводимостей.
(1)
1. 1.Т1а
2. 2.Т1а
3. 3.ВО(1,2)
(9)
1. 1.Т1а
2. 2.ВД2
3. 3.Т1б(1,2)
Распространим свойство леммы 1.1 на случай произвольной формулы.
Лемма 1.2: Для любой формулы существует, содержащий атомы для любых из 2 строк ее истинной таблицы имеет место соответствия выводимость.
Доказательство данной леммы рассмотрим на л/з на конкретном примере.
Лемма 1.3: Если формула Е, содержащая атомы (и только их), общезначима, то .
Ø Пусть n=2.
E
И И И
И Л И
Л И И
Л Л И
1. ,
2. ,
3. ,
4. ,
5. , 5.УД(F1,F2)
6. , 6.УД(F3,F1)
7. , 7.УД(F5,F6)
Доказательство в общем случае получается в результате применения правила УД раз.
Лемма 1.4: для любой формулы.
Метатеорема 6: Если , то по лемме 1.4 (1.6)
Так как формула Е общезначимо, то по лемме 1.3 (1.7)
Из (1.6) и (1.7) по Т1б получим .
Следствие ИВ полна относительно общезначимости
Ø по определению полноты теория полна относительно общезначимости, если в ней доказуема любая общезначимая формула.
Согласно Т6 если формула общезначима, то формула доказуема.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!