13372-1 (662961), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

((pq)p)p

((pq)p)p V.1

((pq)p)p V.1

(((p)q)p)p IV.1

((pq)p)p VII.1

(p(pq))p I.2

pp XI.4

pp V.1

pp I.2

T IX.1

Таким образом

((pq)p)p - тавтология.

5.2.3. Доказательство: правила вывода.

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

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

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

Таблица 5.10.

Правила вывода

I.	Введение	II.	Введение
	[p]		pq
III.	Удаление p	IV.	Удаление
1.	(Modus ponens)	1.
2.	q (Modus tollens)	2.
V.	Введение	VI.	Удаление
1.	[p]	1. 2.	p
VII.	Введение	VIII.	Введение
1.	p	1. 2.
IX.	Удаление	X.	Удаление
1. 2.		1.	[p] [q] r

Доказательство в исчислении высказываний есть по существу последовательность преобразований высказывания р с целью показать, что р общезначимо. Каждый шаг в доказательстве есть либо уже доказанное высказывание, либо высказывание, истинное по предположению и вводимое для последующих шагов. Каждый шаг , который является предположением, заключается в скобки [ ]. Все другие шаги должны быть доказаны. Последним шагом в доказательстве должно быть само высказывание р.

Докажем высказывание

[p]

p

Правило I

Первым шагом мы делаем предположение, что р - общезначима. Тогда второй шаг непосредственно следует из первого. Раз мы предположили общезначимость р на первом шаге, то мы используем этот факт на втором. На третьем шаге мы используем правила вывода I, которое устанавливает общезначимость высказывания .

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

Присмотревшись внимательно к правилам вывода, можно увидеть, что они хорошо согласуются с нашей интуицией. Например, возьмём правило VIII. Если на предыдущих шагах была доказана общезначимость высказываний p и q, то очевидно что высказывание - тоже общезначимо.

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

5.2.4. Некоторые приёмы доказательства.

Дедуктивный вывод.

Доказать

[p] - Предположение

[q] - Предположение

р - 1.

- I, 2, 3

- I, 1, 4

Мы предположили общезначимость утверждений p и q и воспользовавшись правилом I. введение .

Использование правила Моdus Рonens. Это правило хорошо работает когда надо доказать высказывания типа “Если в этом кинотеатре дают “Анаконду”, то я куплю билеты.” Если кто-то сделал это утверждение и вы увидели, что в кинотеатре идет “Анаконда”, то вы можете заключить, что этот человек купил билеты.

Доказать

- Предположение

- IX. Удаление , 1

r - IX. Удаление , 1

р - III. Моdus Рonens, 2, 3

p q - IX. Удаление , 1

q - III. Моdus Рonens. 4, 5

- I. Введение , 1, 6

Использование Моdus Tollens.

Доказать

- Предположение

p q - IX. Удаление , 1

q - IX. Удаление , 1

p - III.2. Modus Tollens, 2, 3

- I. Введение , 1, 4

Использование Введения и Удаления .

Докажем

- Предположение

p q - IX. Удаление , 1

q - IX. Удаление , 1

[p] - Предположение

q - III. Моdus Ðonens, 4, 2

q - 3

F - VI. Удаление , 5, 6

p - V. Введение 4, 7

- I. Введение 1, 8

Доказательство от противного.

На использовании правила V. Введение основан часто используемый прием доказательства - доказательство от противного. Мы его уже использовали несколько раз. Его идея состоит в следующем.

Пусть мы хотим доказать общезначимость высказывания Q :

“Треугольник со сторонами 2, 3, 4 - не прямоугольный.”

Предположим, что Q - общезначимо, т.е треугольник со сторонами 2, 3, 4 - прямоугольный. Тогда, используя теорему Пифагора, мы можем утверждать, что 4+9=16 , но 4+9 16. Отсюда, используя правило VI.1 Удаление , получаем F. Имея F и предположение об общезначимости Q, с помощью правила V, получаем общезначимость (Q). Откуда, с использованием правила VII из таблицы 5.8., получаем общезначимость Q.

Доказать

- Предположение

- Закон импликации V.1, 1

- Закон Де Моргана IV.1

q - IX.2. Удаление , 3

- IX.1. Удаление , 3

- IX.1. Удаление , 5

p - IX.2. Удаление , 6

q - III.1. Моdus Рonens, 6, 7

F - V.1 Удаление , 4, 8

- V. Введение , 1, 9

Пример.

Во вторник, когда случилось ограбление, либо Петров был в операционном зале банка, либо Сидорова в бухгалтерии банка. Петрова никогда не видели в операционном зале без Иванова. Иванов покидал банк во вторник только когда он с Сидоровой ездил на встречу с клиентами. Если в ограблении участвовал Ерошкин, Иванова не было бы в банке. Ограбление произошло во вторник. Мог ли Ерошкин быть грабителем?

Обозначим:

p= Петров был в операционном зале;

q= Cидорова была в бухгалтерии;

s= Иванов был в операционном зале;

h= Ерошкин участвовал в ограблении;

u= Ограбление случилось во вторник.

Тогда исходные утверждения можно записать так:

u(pq)

ps

sq

hs

u

Из 1, 5 п. Modus ponens получаем pq

Предположим [q]

Из 3, 7 п. Modus Tollens получаем s

Из 7, 8 и “введение “получаем qs

Из 4, 10 п. Modus Tollens h

Итак, Ерошкин не мог участвовать в ограблении.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/

Характеристики

Список файлов реферата