Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Чисто прямое доказательство




Фрагмент системы N, определяемый правилами [I] логического следования и правилом [ II. 1] построения прямого доказательства представляет собой один из вариантов исчисления положительной (или позитивной) логики. В данной теории изучаются логические законы и правила, не содержащие знака отрицания. С помощью этих законов и правил строятся чисто прямые доказательства. Поэтому положительную логику можно было также назвать логикой чисто прямого доказательства.

Перейдем к рассмотрению теорем и производных правил положительной логики.

Т2. A 1 ® (A 2 ®... (Аn ® A i)...), где i = l, 2,.... п.

Доказательство.

Ai допущ.

Как видно, оно состоит из единственной формулы, которая входит в Т2 в качестве антецедента и потому согласно п. 1 правила [II. 1] вписывается в доказательство в качестве допущения. Но так как данная формула совпадает с формулой, входящей в Т2 также и в качестве консеквента, то полученная последовательность из одной формулы Аi, согласно [II. 1], является доказательством формулы Т2.

Частными случаями Т2 являются следующие теоремы:

Т3. А ® (В ® А).

Т4. А ® А.

По-видимому, невозможно придумать более тривиальную теорему, чем Т2 или ее частные случаи. Тем не менее, трудно представить без них строгое построение логической теории. Они, как мы увидим, играют весьма существенную роль в обосновании принципов логики.

Мы предлагаем читателю в порядке упражнения найти опущенные доказательства теорем, приводимых в этом и следующих параграфах.

Т5. (А ® (В ® С)) ® ((А ® В) ® (А ® С)).

Т6. А ® (В ® (А Ù В)).

Т7. (А Ù В) ® А.

Т8. (А Ù В) ® В.

Т9. (А ® С) ® ((В ® С) ® ((А Ú В) ® С)).

Т10. А ® (А Ú В).

T11. В ® (А Ú В).

Т12. (А ® С) ® ((В ® D) ® ((А Ú В) ® (С Ú D))).

Доказательство.

1) А ® С допущ.;
2) В ® D допущ.;
3) А Ú В допущ.;
4) С ® (С Ú D) р.д.ф., Т10;
5) D ® (С Ú D) р.д. ф., Т11;
6) А ® (С Ú D) Сил. (1, 4);
7) В ® (С Ú D) Сил. (2, 5);
  С Ú D УД(3, 6, 7).

Относительно Т12 производно правило

 

Дил2 А Ú В A ® C B ® D,
  C Ú D

 

которое в традиционной логике известно под названием сложной конструктивной дилеммы. Правило позволяет из двух импликаций и дизъюнкции формул, совпадающих с их антецедентами, получить дизъюнкцию формул, совпадающих с консеквентами этих импликаций. Мы уже говорили, что основное правило УД называется простой конструктивной дилеммой. В нумерации дилемм мы присваиваем ему обозначение: Дил1.

Нахождение доказательств логических теорем существенно облегчается применением следующих двух производных правил построения доказательства. Первое из них называется: доказательство по частям (сокращенно: ДЧ), а второе— доказательство разбором случаев (сокращенно: PC).

Правило ДЧ формулируется так: для того чтобы доказать формулу вида

A 1 ® (A 2 ® ... (Аn ® 1 Ù С 2 ))...) (*)

достаточно построить

1) доказательство формулы

A 1 ® (A 2 ®... (Аn ® С 1)…) (**)

(часть 1) и

2) доказательство формулы

A 1 ® (A 2 ®... (Аn ® С 2)...) (***)

(часть 2).

Данное правило легко обосновывается с помощью правила [II. 1] построения прямого доказательства и правил УК и МП. Действительно, если построены доказательства формул (**) и (***), то, делая последние строками нового доказательства согласно п. 3 правила [II. 1], введя в качестве допущений формулы A 1, A 2,..., Аn согласно п. 1 этого же правила и пользуясь далее п. 3 правила [II. 1], мы с помощью МП' получаем формулы C 1, С 2, из которых в свою очередь по ВК выводим формулу

С 1 Ù С 2

Получением данной формулы мы завершаем построение требуемого доказательства формулы (*).

Согласно ДЧ нахождение доказательства формулы вида

А «В

сводится к построению доказательств следующих двух импликаций (прямой):

А ® В

и (обратной)

В ® А,

так как А «В является по определению конъюнкцией этих импликаций, т. е.

(А ® В)Ù(В ® А).

Правило PC формулируется следующим образом: для того чтобы доказать формулу вида

A 1 ® (A 2 ® ... (Аk ® ((B 1 Ú B 2 ) ® С))...), (*)

достаточно построить

1) доказательство формулы

A 1 ® (A 2 ® ... (Аk ® (B 1 ® С))...), (**)

(случай 1) и

2) доказательство формулы

A 1 ® (A 2 ® ... (Аk ® (B 2 ® С))...), (***)

(случай 2).

Очевидно, что обоснование правила PC должно состоять в указании способа построения доказательства формулы (*) при условии, что ранее построены доказательства формул (**), (***). В самом деле, используя правило [II. 1], мы пишем формулы (**), (***) в качестве ранее доказанных и A 1, A 2,..., Аk в качестве допущений. Затем по МП' мы получаем формулы

B 1 ® C,

B 2 ® С,

и, введя в качестве еще одного допущения формулу

B 1 Ú B 2,

по правилу УД пишем формулу

С.

Получением этой формулы завершается построение требуемого доказательства формулы (*).

Эвристическая ценность правил ДЧ, PC состоит в том, что они позволяют сводить задачу на поиск доказательства к более простым задачам. Правило ДЧ (соответственно PC) можно применять последовательно, разбивая вводимые в рассмотрение части (случаи) в свою очередь на подчасти (подслучаи) и т. д. Правила ДЧ и PC можно также применять совместно, комбинируя их друг с другом, как это иллюстрируется ниже.

Пример. Пользуясь правилами ДЧ и PC докажем следующую формулу:

(p Ú (q Ù r)) ® ((p Ú q) Ù (p Ú r)).

Доказательство.

Часть 1. (p Ú (q Ù r)) ® (p Ú q).

Случай 1.1. (р ® (p Ú q)), р. д. ф., Т10.

Случай 2.1. (q Ù r) ® (p Ú q).

1) q Ù r допущ.;
2) q УК (1);
  p Ú q ВД (2).

Часть 2. (p Ú (q Ù r)) ® (p Ú r).

Случай 2.1. p ® (p Ú r), р.д.ф., Т10.

Случай 2.2. (q Ù r) ® (p Ú r).

1) q Ù r допущ.;
2) r УК (1);
  p Ú r ВД (2).

 

Упражнения.

I. Постройте доказательство формулы:

1) ((Q ® R) ® (R ® S) ® ~ S) ® (~ Q Ù ~ R);

2) ((A Ú B) ® ~ C) ® (C Ú D) ® D;

3) (((~ X ® Y) ® (Z ® X) ®~ X) ® (Y Ù ~ Z);

4) ((E Ú ~ F) ® (F Ú (E Ú G)) ® ~ E) ® G;

5) ((P ® Q) Ù (Q ® P)) ® (R ® S) ® (P Ú R) ® (Q Ú S);

6) ((Q ® R) Ù (S ® T)) ® ((U ® V) Ù (W ® X)) ® (Q Ú U) ® (R Ú V);

7) ((A ® B) ® (C ® D) ® (A Ú C)) ® ((A Ù B) Ú (C Ù D));

8) (((H Ú I) ® (J Ù (K Ù L)) ® I) ® (J Ù K);

9) ((Y ® Z) ® (Z ® (Y ® (R Ú S)) ® (R «S)) ® (~ R Ú ~ S)) ® ~ Y;

10) (A ® B) ® (B ® C) ® (C ® A) ® (A ® ~ C) ® (~ A Ù ~ C).

II. Решите задачу, записав условие в символической форме и построив доказательство полученной формулы:

1.Если она получила телеграмму, то она полетела самолетом; если она полетела самолетом, то не опоздает на встречу. Но если телеграмма была неправильно адресована, тогда она опоздает навстречу. Либо она получила телеграмму, либо телеграмма была неправильно адресована. Значит, либо она полетела самолетом, либо она опоздает на встречу.

2.Если дождь будет продолжаться, то река поднимется. Если дождь будет продолжаться и река поднимется, то мост станет непригодным. Но если продолжение дождя делает мост непригодным, то одной единственной дороги для города недостаточно. Либо одной дороги для города недостаточно, либо разработчики городских дорог допустили ошибку. Значит, разработчики городских дорог допустили ошибку.

3.Так как Смит выиграл у полицейского в бильярд, то Смит — не полицейский. Смит выиграл у в бильярд полицейского. Если Джонс — машинист, то Джонс — не полицейский. Джонс — машинист. Если Смит — не полицейский, и Джонс тоже не полицейский, тогда полицейский — Робинсон. Если Джонс — машинист, а Робинсон — полицейский, тогда Смит — инженер. Значит, Смит — инженер.

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных