Доказательство клауз аксиоматический метод

Доказательство клауз аксиоматический метод

1. Доказать методом натурального исчисления истинность следующей клаузы:

2. Доказать аксиоматическим методом истинность клаузы:

A, B → D, C → D, A → (B ∨ C) ⇒ D.

1. B → D, C → D, B ∨ C ⇒ D,
2. B ∨ D, C ∨ D, B ∨ C ⇒ D,
3. (BC) ∨ D, B ∨ C ⇒ D,
4. (B ∨ C) → D, B ∨ C ⇒ D,
5. B ∨ C, D ⇒ D.

3. Доказать методом Вонга истинность следующей клаузы:

B → (D → C), D, C → (A ∨ B) ⇒ A ∨ B.

1. B ∨ D ∨ C, D, C ∨ A ∨ B ⇒ A ∨ B,
1.1. B, D, C ∨ A ∨ B, A ⇒ B,
1.2. D, D, C ∨ A ∨ B, A ⇒ B,
1.3. C, D, C ∨ A ∨ B ⇒ A ∨ B,
1.3.1. C, D, C ⇒ A ∨ B,
1.3.1. C, D, A, A ⇒ B,
1.3.1. C, D, B, A ⇒ B.

4. Доказать методом резолюций истинность следующей клаузы:

A → B, C → D, B → E, D → F, E → F, A → C ⇒ A.

5. Пусть задана система аксиом:

и правило отделения (modus ponens — МР):

С помощью этих аксиом и правила МР доказать справедливость закона рефлексивности:

Доказательство (символы «1 ⇒ » здесь и в следующем примере писать не будем):

1. A → ((А → A) → A), (А1)
2. (А → ((А → A) → A)) → ((А → (А → A)) → (А → A)), (А2)
3. (А → (А → A)) → (А → A), (1, 2, МР)
4. А → (А → A), (А1)
5. А → A. (3, 4, МР)

6. С помощью системы аксиом предыдущего примера доказать клаузу:

X, Y, Z → X, S → (Y ∨ Z), (T ∨ U) → S ⇒ T.

7. Составить легенды для приведенных ниже четырех клауз.

E, E → D, D → B ⇒ A → B.

A — Падение авторитета власти.
B — Политики, не способные управлять страной.
C — Нарастание анархии в обществе.
D — Высказывание абсурдных идей.
E — Появление безответственных политиков.

«Падение авторитета власти происходит тогда и только тогда, когда нарастает анархия в обществе (A

C). Нарастание анархии в обществе равносильно появлению на политической арене безответственных политиков (C

E). Появление подобных политиков приводит к тому, что они высказывают абсурдные идеи (E → D). Высказывание политиками таких идей демонстрирует неспособность их управлять страной (D → B). Итак, падение авторитета власти приводит к появлению политиков, не способных управлять страной (A → B)».

Клауза 2: A → B, B → E, A → C, C → D, D → F, E ∧ FA.

«Если человек занимается спортом (A), то он хочет быть здоровым (B). Хорошее здоровье (B) ведет к счастливой жизни (E). Кроме того, если человек занимается спортом (A), то он, как правило, стремится достичь высоких спортивных результатов (C). Наличие высоких результатов (C) позволяет одерживать победы на соревнованиях (D). Победы на соревнованиях (D) влекут за собой всеобщее признание (F). Однако человек не хочет жить счастливо и иметь всеобщее признание (E ∧ F). Значит, он не станет заниматься и спортом (A)».

Клауза 3: J → H, K → H, I → J, H → I, HJK.

«Если знать язык программирования (J), то можно составить рабочую программу (H). Рабочую программу можно также получить (H) при наличии знакомого программиста (K). Овладеть языком программирования (J) можно, обучаясь в институте (I). Если программа работает (H), то ее написал выпускник такого института (I). Но программа не работает (H). Это говорит о том, что желающий получить правильный результат не знает языка программирования (J) и не имеет знакомых программистов (K)».

Клауза 4: A → B, C → D, B ∧ D → E, A, EC.

«Все живое способно чувствовать (A → B). Всякое материальное тело занимает определенный объем (C → D). Если нечто занимает пространственный объем и способно чувствовать, то это нечто есть ни что иное, как живой организм (B ∧ D → E). Пусть существует нечто живое (A), но не являющееся организмом (E). Тогда следует вывод, что это нечто нематериально (C)».

8. Выше приведены легенды. Запишем клаузы, отвечающие содержанию этих легенд, для чего сформулируем необходимые посылки и два следствия: одно истинное, другое ложное. С помощью таблицы истинности найдем МНФ, минимальное и все трансверсальные покрытия (последнее задание выполнено только для варианта 21).

Для варианта 21 можно предложить следующую клаузу:

B, C → A, D → B, C → E, E ⇒ C → B.
A — Где-то что-то убыло.
B — Где-то что-то прибыло.
C — “Черная дыра” существует.
D — “Белая дыра” существует.
E — Невозможность ничего увидеть.

Исходную легенду допустимо трансформировать в близкую по смыслу и составить таблицу истинности (табл. 1.23): «Если в одном месте что-то убудет, то в другом что-то непременно прибудет, и наоборот (A

B). Если существует черная дыра, то в нее все проваливается, т.е. в ее окрестностях что-то убывает (C → A). Если существует белая дыра, то из нее в окружающее пространство должно прибывать вещество (D → B). Если существует черная дыра, то ее невозможно увидеть, так как она не излучает свет (C → E). Астроном ничего не увидел (E). Итак, белая дыра существует(D)». Это — ложное умозаключение. Истинным же заключением является, например, следующее: «Если существует черная дыра, то где-то в пространстве вселенной должно непременно появляться вещество (C → B)».

Читайте также:  Как создать дерево семьи

Из табл. 1.23 видно, что три единицы обобщенной посылки (Р) не покрываются единицами ложного следствия (D); единицы же истинного следствия (C → B) целиком накрывают единицы обобщенной посылки. По табл. 1. 23 составим СДНФ:

После преобразований получим следующую МДФ:

Минимальное покрытие: E.

Для варианта 22 можно составить следующую клаузу:

A → B, B → C, E → (B → D), D → F ⇒ (B ∧ A ∧ E) → F.

Введем следующие обозначения:

A — Возникновение перепада напряжения в сети.
B — Перегорание предохранителя.
C — Необходимость замены предохранителя.
D — Телевизор работает нормально.
E — Телевизор подключен к сети питания.
F — Я смотрю “Новости”.

«Если в сети был перепад напряжения, то сгорит предохранитель (P1 = A → B). Если предохранитель сгорел, то необходима его замены (P2 = B → C). Если телевизор включен в сеть, то он работает нормально при условии целостности предохранителя (P3 = E → (B → D)). Если телевизор работает нормально, я увижу “Новости” (P4 = D → F). Я увижу “Новости” при условии отсутствия перепада напряжения и подключения телевизора к сети питания (C1 = (A ∧ E) → F)».

Данное следствие является ложным. Истинным же следствием будет: «Я увижу “Новости” при условии целостности предохранителя, отсутствия перепада напряжения в сети и подключения телевизора к сети питания (C2 = (BA ∧ E) → F)».

Выделим ту строку табл. 1.24, для которой обобщенная посылка (Р) и истинное следствие (C2) принимают значения единицы, а ложное следствие (C1) — значение нуля.

Для варианта 23 допустимо составить следующую клаузу:

A → B, B → C, C → D, D → E ⇒ A → E.

A — Работа выполнена.
B — Отпуск на рыбалку.
C — Взять на рыбалку сына.
D — Рыбалку провести с лодкой.
E — На рыбалку поедут все вместе.

«Если работа выполнена, то начальство отпустит на рыбалку (A → B). Если отпустят на рыбалку, то обязательно возьмут на нее и сына (B → C). Если берут сына, значит надо брать лодку (C → D). Если брать с собой лодку, то поедут все вместе (D → E). Таким образом, если работа выполнена, то все вместе едут на рыбалку (A → E)».

Данное следствие является истинным. Ложным следствием является, очевидно, такое: «Если работа сделана, то все вместе на рыбалку не едут (A → E)».

Для варианта 24 составим следующую клаузу:

A — Уменьшение температуры.
B — Снижение давления.
C — Уменьшение объема.
D — Снижение скорости.
E — Падение уровня.

«Уменьшение температуры приводит к снижению давления и уменьшению объема (A → (B ∧ C)). Увеличение объема приводит к росту скорости потока (CD). Повышение давления приводит к падению уровня, если при этом уменьшать температуру (B → (A → E)). Снижение скорости приводит к уменьшению давления или росту температуры (D → (B ∨ A)). Технолог Иванов рассудил так: “Мне надо повысить давление при одновременном снижении скорости потока, поэтому я должен увеличить объем и температуру” ((AC) → (B ∧ D))».

Данное умозаключение является ложным. Истинным рассуждением будет, например, такое: «Уменьшение температуры и увеличение давления ведут к уменьшению объема ((A ∧ B) → C)».

Для варианта 25 составим клаузу:

A ∨ B ∨ C, (C ∧ D) → E, (A ∨ B) → E, C → D, ⇒ C → E.

A — Надеть брезентовые штаны.
B — Надеть шерстяное платье.
C — Надеть пиджак и юбку с разрезом.
D — Взять с собой сумку.
E — Великолепно смотрится.

«Я могу надеть на себя брезентовые штаны, или шерстяное платье, или пиджак и юбку с разрезом (A ∨ B ∨ C). Я буду выглядеть великолепно, если надену пиджак и юбку с разрезом и при этом возьму с собой сумку ((C ∧ D) → E). И наоборот, я буду выглядеть ужасно, если надену на себя брезентовые штаны или шерстяное платье ((A ∨ B) → E). Однако сумку надо брать обязательно, если надеть пиджак и юбку с разрезом (C → D). Итак, чтобы выглядеть великолепно, я выбираю последнее, т.е. надену на себя пиджак и юбку с разрезом (C → E)».

Данное заключение является истинным. Ложным может быть, например, такое: «Чтобы выглядеть великолепно, нужно надеть на себя брезентовые штаны (A → E)».

Близким к методу резолюций является метод Вонга, в котором тоже исполь­зуется сконструированная конъюнктивно-дизъюнктивная нормальная форма представления исходной клаузы, а аксиому порядка заменяет клауза Вонга.

здесь Xпробегает некоторые буквы, входящие в клаузу,aLиR— определенные комбинации дизъюнктов и конъюнктов.

Конструктивная процедура доказательства сводится к последовательному разбиению дизъюнктов или конъюнктов таким образом, чтобы слева и справа от метаимпликации появилась одна и та же буква X. Если в результате такого раз­биения все конечные клаузы приобретают вид клаузы Вонга, то и исходная клау­за была составлена верно. Разберем метод Вонга на примере доказательства справедливостиправила отделения:

Читайте также:  Выживалки на пк для слабых компьютеров

А, А -> В => В или A, -AvВ => В .

Здесь имеется только один дизъюнкт, который можно подвергнуть разбиению. После его разбиения получим две новых клаузы:

Вторая клауза удовлетворяет и аксиоме порядка и клаузе Вонга. В качестве Xв ней выступаетB,aL=AиR=0. Первая же клауза тоже будет удовлетворять необходи­мым требованиям, но только после того, как терм -А из левой части клаузы с противоположным знаком перенести в правую часть. Тогда будем иметь:

При большом числе букв в исходной клаузе прибегают к специальной нумерации производных клауз чтобы не запутаться. Пусть требуется установить справедли­вость следующей клаузы:

X v Y, (X -> Y) v U, Z -> (Y -> W) => (W -> X) -> (Z -> X).

Приведем ее в соответствующую конъюнктивно-дизъюнктивную нормаль­ную форму:

X v Y, -X v Y v U, -Z v -Y v W => W & -X; -Z; X .

Далее произведем разбиение первого дизъюнкта, в результате получим две производные клаузы:

X, -X v Y v U, -Z v –Y v W => W & -X; -Z; X

Y, -X v Y v U, -Z v –Y v W => W & -X; -Z; X

Клауза (1) отбрасывается, так как она удовлетворяет клаузе Вонга. Разбивая сле­дующий дизъюнкт клаузы (2), получаем еще три новых клаузы:

2.1. Y, -X, -Z v -Y v W => W & -X; -Z; X

2.2. Y, Y, -Z v -Y v W => W & -X; -Z; X

2.3. Y, U, -Z v -Y v W => W & -X; -Z; X

Клаузы (2. 1) и (2. 2) сводятся к одной клаузе —

Y, -Z v -Y v W => W & -X; -Z; X

Произведем ее разбиение:

2.1.2. Y, Y => W & -X; -Z; X

2.1.3. Y, W => W & -X; -Z; X

Первые две клаузы удовлетворяют клаузе Вонга. У клаузы (2.1.3) нужно разбивать конъюнкт:

2.1.3.1. Y, W => W; -Z; X

2.1.3.2. Y, W => -X; -Z; X

Теперь обе клаузы имеют вид клаузы Вонга.

Но у нас осталась еще ветвь (2.3). Она отличается от рассмотренной ветви (наличием непарного терма U, который, однако, не может повлиять на конечный результат, т.е. разбиение клаузы (2.3) практически полностью совпадает с разбиением клаузы (2.1). Следовательно, исходная клауза была записана верно.

Метод натурального исчисления

Недостатком метода Вонга, как и метода резолюций, является то, что исходная клауза обязательно должна иметь нормальную дизъюнктивную или конъктивную форму. Этот недостаток преодолен в методе натурального исчисления, к которому мы переходим.

Доказательный вывод в натуральном исчислении строится как упорядоченная цепь преобразований, связанных с удалением или введением логических связок на основе следующих десяти правил:

Аксиомат и ческий м е тод, способ построения научной теории, при котором в её основу кладутся некоторые исходные положения (суждения) — аксиомы, или постулаты, из которых все остальные утверждения этой науки (теоремы) должны выводиться чисто логическим путём, посредством доказательств. Назначение А. м. состоит в ограничении произвола при принятии научных суждений в качестве истин данной теории. Построение науки на основе А. м. обычно называется дедуктивным. Все понятия дедуктивной теории (кроме фиксированного числа первоначальных) вводятся посредством определений, выражающих (или разъясняющих) их через ранее введённые понятия. В той или иной мере дедуктивные доказательства, характерные для А. м., применяются во многих науках. Но, несмотря на попытки систематического применения А. м. к изложению философии (Б. Спиноза), социологии (Дж. Вико), политической экономии (К. Родбертус-Ягецов), биологии (Дж. Вуджер) и др. наук, главной областью его приложения до сих пор остаются математика и символическая логика, а также некоторые разделы физики (механика, термодинамика, электродинамика и др.).

А. м прошёл в своём историческом развитии 3 стадии. Первая связана с построением геометрии в Древней Греции. Основное сочинение этого периода — «Начала» Евклида (хотя, по-видимому, и до него Пифагор, которому приписывается открытие А. м., а затем Платон и его ученики немало сделали для развития геометрии на основе А. м.). В то время считалось, что в качестве аксиом должны выбираться суждения, истинность которых «самоочевидна», так что истинность теорем считалась гарантированной безупречностью самой логики. Но Евклиду не удалось ограничиться чисто логическими средствами при построении геометрии на основе аксиом. Он охотно прибегал к интуиции в вопросах, касающихся непрерывности, взаимного расположения и равенства геометрических объектов. Впрочем, во времена Евклида такие обращения к интуиции могли и не восприниматься как выход за пределы логики — прежде всего потому, что сама логика не была ещё аксиоматизирована (хотя частичная формализация логики, осуществленная Аристотелем и его последователями, и была некоторым приближением к аксиоматизации). Не было и достаточной отчётливости во введении первоначальных понятий и при определении новых понятий.

Начало второй стадии в истории А. м. связывают обычно с открытием Н. И. Лобачевским, Я. Больяй и К. Ф. Гауссом возможности построить непротиворечивым образом геометрию, исходя из систем аксиом, отличной от евклидовой. Это открытие разрушило убеждение в абсолютной («очевидной» или «априорной») истинности аксиом и основанных на них научных теорий. Теперь аксиомы стали пониматься просто как исходные положения данной теории, вопрос же об их истинности в том или ином смысле (и выбор в качестве аксиом) выходит за рамки аксиоматической теории как таковой и относится к её взаимоотношению с фактами, лежащими вне её. Появилось много (и притом различных) геометрических, арифметических и алгебраических теорий, которые строились средствами А. м. (работы Р. Дедекинда, Г. Грасмана и др.). Эта стадия развития А. м. завершилась созданием аксиоматических систем арифметики (Дж. Пеано, 1891), геометрии (Д. Гильберт, 1899), исчисления высказываний и предикатов (А. Н. Уайтхед и Б. Рассел, Англия, 1910) и аксиоматической теории множеств (Э. Цермело, 1908).

Читайте также:  Услуга гудок на теле2 выбор

Гильбертовская аксиоматизация геометрии позволила Ф. Клейну и А. Пуанкаре доказать непротиворечивость геометрии Лобачевского относительно евклидовой геометрии посредством указания интерпретации понятий и предложений неевклидовой геометрии в терминах геометрии Евклида, или, как говорят, построения модели первой средствами второй. Метод моделей (интерпретаций) стал с тех пор важнейшим методом установления относительной непротиворечивости аксиоматических теорий. В то же время со всей отчётливостью выявилось, что, кроме «естественной» интерпретации (т. е. той, ради уточнения и развития которой данная теория строилась), у аксиоматической теории могут быть и др. интерпретации, причём её можно с равным основанием считать «говорящей» о каждой из них.

Последовательное развитие этой идеи и стремление точно описать логические средства вывода теорем из аксиом привели Гильберта к концепции формального А. м., характерной для третьей, современной его стадии. Основная идея Гильберта — полная формализация языка науки, при которой её суждения рассматриваются просто как последовательности знаков (формулы), не имеющие как таковые никакого смысла (который они приобретают лишь при некоторой конкретной интерпретации). Это относится и к аксиомам — как общелогическим, так и специфическим для данной теории. Для вывода теорем из аксиом (и вообще одних формул из других) формулируются специальные правила вывода (например, т. н. правило modus ponens — «правило зачёркивания», позволяющее получить В из А и «А влечёт В»). Доказательство в такой теории (исчислении, или формальной системе) это просто последовательность формул, каждая из которых либо есть аксиома, либо получается из предыдущих формул последовательности по какому-либо правилу вывода. В отличие от таких формальных доказательств, свойства самой формальной системы в целом обсуждаются — а иногда их удаётся и доказать — содержательными средствами т. н. метатеории, т. е. теории, рассматривающей данную («предметную») теорию как предмет изучения. На языке метатеории (метаязыка) формулируются и правила вывода предметной теории. По замыслу Гильберта, в рамках созданной им теории доказательств, т.е. допуская в метатеории только т. н. финитные способы рассуждения (не использующие ссылки ни на какие объекты, не имеющие конечного построения), можно было бы доказать непротиворечивость и полноту всей классической математики (т. е. доказуемость каждой формулы, истинной при некоторой определённой интерпретации). Несмотря на ряд значительных результатов в этом направлении, гильбертовская программа в целом (её обычно называют формализмом) невыполнима, т. к., согласно важнейшему результату К. Гёделя (1931), всякая достаточно богатая непротиворечивая формальная система непременно неполна (т. н. теорема о неполноте). Теорема Гёделя свидетельствует об ограниченности А. м. (хотя определённые расширения допускаемых метатеоретических средств и позволили немецкому математику Г. Генцену, П. С. Новикову и др. математикам получить доказательство непротиворечивости формализованной арифметики).

А. м. подвержен также критике, исходящей из различных семантических (см. Логическая семантика) критериев. Так, интуиционисты (Л. Э. Я. Брауэр, Г. Вейль и др.) не признают обоснованности в применении к бесконечным множествам принципа исключенного третьего (см. Исключённого третьего принцип) между тем этот принцип не только берётся в качестве логической аксиомы в большинстве формальных теорий, но и используется по существу (хотя и неявно) в основных предпосылках гильбертовской программы, согласно которой непротиворечивость теории — достаточное условие её «истинности». Как и интуиционизм, конструктивное направление в математике (в СССР — А. А. Марков и Н. А. Шанин) считает назначением математики изучение не произвольных моделей непротиворечивых формальных систем, а лишь совокупностей объектов, допускающих в определённом смысле эффективное построение.

Ещё более существенные возражения против А. м. выдвигает ультраинтуиционистская критика, ставящая под сомнение единственность натурального ряда чисел и, тем самым, однозначную определённость понятия теоремы формальной системы. Согласно этой критике, А. м. основан на «принципе локальности для доказательств», предполагающем, что если аксиомы истинны и правила вывода сохраняют истинность, то истинными непременно должны быть и теоремы. Т. о., интуитивное обоснование общеупотребительного принципа математической индукции, согласно ультраинтуиционистской критике, содержит неустранимый порочный круг. Ультраинтуиционизм, не ограничиваясь критикой, предлагает и положительную программу преодоления указанных трудностей.

Лит.: Начала Евклида, пер. с греч., [т. 1 — 3], М. — Л., 1948 — 50; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957 (библ.); Новиков П. С., Элементы математической логики, М., 1959: Есенин-Вольпин А. С., Об аксиоматическом методе, «Вопросы философии», 1959, № 7; Садовский В. Н., Аксиоматич. метод построения науч. знания, в кн.: Филос. вопросы совр. формальной логики, М., 1962; Hilbert D., Bernays P., Grundlagen der Mathematik, Bd 1 — 2, В., 1934 — 39.

Ю. А. Гастев, А. С. Есенин-Вольпин.

Ссылка на основную публикацию
Джози маран ван хельсинг фото
Если вы хоть раз играли в «Need for Speed: Most Wanted», то точно знаете, кто такая Миа Таунсенд. Но известно...
Где находится товар с джум
Чтобы получать увемления об изменении статуса посылки, зарегистрируйтесь на сервисе ГдеПосылка и добавьте трекинг номер в список отслеживания. Если с...
Где находятся скачанные обновления windows 10
Операционная система Windows 10 не всегда удачно обновляется с первого раза. Процесс загрузки апдейтов может запускаться несколько раз, вследствие чего...
Джойстик xbox one elite
Новый геймпад для Windows 10 и Xbox One получил важные дополнительные возможности, но их реализация вызывает вопросы. С момента релиза...
Adblock detector