Методические рекомендации по изучению дисциплины (стр. 1 )

Министерство образования и науки Республики Казахстан

Павлодарский государственный университет им. С. Торайгырова

Кафедра математики

мЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Дискретная математика и математическая логика

для студентов специальности 050601 «Математика»

Составитель:

д. п.н., профессор ПГУ

Павлодар

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО ТЕМАМ:

Тема 1. Исчисление высказываний и логика предикатов.

Пусть  – некоторое (конечное или бесконечное) множество формул исчисления высказываний.

Выводом (или доказательством) из называется такая конечная последовательность формул

, (1)

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

Число , при этом, называется длиной вывода.

Формулы из множества обычно называются гипотезами (или посылками) и, в связи с этим, вывод (1) из называется выводом из гипотез или из посылок.

Понятие формулы, выводимой из гипотез, даётся следующим образом: формула А называется выводимой из гипотез , если существует такой вывод из этих гипотез, последней формулой которого является формула А, то есть .

В дальнейшем, запись |–А будет обозначать, что формула А выводима из множества гипотез . В частности, |–А означает, что А – выводимая в исчислении высказываний формула. Запись будет обозначать, что формула А не выводима из гипотез .

Упражнение 1.

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

а) если длина вывода формулы А из гипотез равна 1, то А является или выводимой формулой, в частности, аксиомой исчисления высказываний или одной из гипотез;

б) если |– А и , то |– А, в частности, если |–А, то |– А;

в) |– А тогда и только тогда, когда существует такое конечное подмножество множества , что |– А;

г) если последовательность формул является выводом из , то и любой её начальный отрезок () также является выводом из ;

д) каждая формула любого вывода из гипотез является выводимой из этих гипотез;

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

Пример 1.

Покажем, что если |– А, то существует такое конечное подмножество , что |– А. Действительно, пусть |– А, - вывод формулы А из гипотез и () все гипотезы из , которые используются в этом выводе. Положим . Тогда  – конечное подмножество множества и |–А.

Пример 2.

Покажем, что:

а) |– ;

б) |– ;

в) |– ;

г) |– ;

д)  |– ;

е) |– ;

для любых формул А;В;С исчисления высказываний.

Действительно:

а)  – гипотеза;

 – выводимая формула;

 – выводимая формула;

 – выводимая формула;

;

;

.

в) Обозначая через R произвольную, выводимую в исчислении высказываний формулу, будем иметь:

 – выводимая формула;

 – первая гипотеза;

 – вторая гипотеза;

 – выводимая формула;

 – выводимая формула;

;

;

 – выводимая формула;

;

;

.

д)   – первая гипотеза;

 – вторая гипотеза;

 – выводимая формула;

 – выводимая формула;

;

;

;

.

Упражнение 2.

Построить выводы из посылок, указанных в пунктах б), г), е).

Пример 3.

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

Действительно, это множество определяется следующим образом:

шаг 0. Формулами этого шага являются все формулы из (то есть все гипотезы) и все теоремы исчисления высказываний.

Предполагая, что все выводимые из гипотез формулы шага t уже определены, переходим к определению формул шага , выводимых из гипотез .

шаг (t+1). Формулами этого шага являются формулы, которые можно получить не более чем однократным применением правила заключения к некоторым из формул шага t.

Обозначая через множество всех формул шага i (), получаем:

а) ;

б) .

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

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

а) провести базис индукции, то есть проверить или доказать, что всякая, выводимая из гипотез формула А, длина вывода из которой равна 1 , обладает свойством С.

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

в) осуществить индукционный шаг, то есть доказать, что всякая, выводимая из гипотез формула А, длина вывода из которой равна , обладает свойством С.

Упражнение 3.

Доказать теорему о дедукции: если |– В, то |– для любого множества гипотез и любых формул А и В исчисления высказываний.

Пример 4.

Покажем, что из теоремы о дедукции нетрудно получить важное следствие: если

|– В, то |–,

то есть если формула В выводима из гипотез , то формула

выводима в исчислении высказываний.

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

а) Базис индукции . Нужно показать, что если |– В, то |–. Это утверждение получается из теоремы о дедукции при и .

б) Индукционное предложение . Пусть теорема доказана, в случае, когда число гипотез равно , то есть если |–, то

|–

для любых гипотез и любой формулы , выводимой из этих гипотез.

в) Индукционный шаг . Предположим теперь, что |– . Полагая , имеем: |–. Отсюда, по теореме о дедукции, получаем, что |–  или |– . Применив, далее, индукционное предложение, при ; и , получаем:

|–,

что и завершает доказательство следствия.

Пример 5.

Покажем, что последовательность формул - является выводом формулы С из посылок и , то есть ; |– С, где

 

 

 

 

;

;

;

.

Действительно:

 – выводимая в исчислении высказываний формула;

 – первая гипотеза;

 – вторая гипотеза;

;

;

;

В качестве следствия из теоремы о дедукции отсюда получаем, что формула

выводима в исчислении высказываний.

Процедура преобразования вывода формулы В из гипотез в вывод формулы из гипотез позволяет сформулировать следующее правило:

S;  А |– В

S |– (А®В).

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

Пусть  – любое множество формул и  – произвольные формулы исчисления высказываний. Далее приводятся наиболее применяемые производные правила:

1. Правило повторения посылки: ; А |– А.

2. Правило введения посылки: если S |– А, то S; В |– А.

3. Правило удаления посылки: если S; А |– В и S |– А, то S |– В.

4. Правило силлогизма: если S |– А1; S |– А2;…; S |– Аt и  |– В, то S |– В.

5. Правило введения импликации: если S; А |– В, то S |– (А®В).

6. Правило удаления импликации: если S |– А®В, то S; А |– В .

7. Правило введения конъюнкции: если S; А |– В и S; А |– С,

то S; А |– (В & C).

8. Правило удаления конъюнкции: S; А & B|– A и S; А & B |– B.

9. Правило введения дизъюнкции: S; А|– A Ú В и S; B |– А Ú B.

10. Правило удаления дизъюнкции: если S; А |– С и S; В |– С,

то S; А Ú В |– C.

11. Правило контрапозиции: если S; А |– В, то S; |– .

12. Правило введения отрицания: если S; А |– В и S; А |– ,

то S |–.

13. Правило удаления двойного отрицания: S; |– А.

14. Правило введения двойного отрицания: S; А |– .

15. Правило перестановки посылок: если S; А; В|– С, то S; В; А |– С.

16. Правило соединения посылок: S; (А ® (В ® С) |– ((А & B) ® С).

17. Правило разъединения посылок: S; ((А&B)®С) |– (А® (В® С).

Пример 1.

Докажем, некоторые из приведённых правил.

Правило

 – вывод формулы из гипотез ;

 – гипотеза;

 – .

Последовательность формул представляет собой вывод формулы В из гипотез , .

Правило .

По условию мы имеем вывод формулы В из гипотез ; и вывод формулы С из гипотез ; . Эти выводы, как показано выше, могут быть преобразованы в выводы формул и из гипотез . С использованием этих выводов, построим вывод формулы из гипотез ; .

 – вывод формулы из гипотез ;

 – вывод формулы из гипотез ;

 – выводимая формула;

 –  ;

 –  ;

 – гипотеза;

 – .

Правило .

Построим, для примера, вывод формулы А из гипотез ; .

 – гипотеза;

 –  выводимая формула;

 –  .

Правило .

Аналогично тому, как это сделано в доказательстве правила , получаем выводы формул и из гипотез . С использованием этих выводов, построим вывод формулы из гипотез .

 – вывод формулы из гипотез ;

 – вывод формулы из гипотез ;

 – выводимая формула;

 –  ;

 –  ;

 – выводимая формула;

 – ;

– выводимая формула;

 – .

Правило .

Предварительно построим вывод формулы С из гипотез ; ; .

  – первая гипотеза;

 – вторая гипотеза;

 – выводимая формула;

 – выводимая формула;

 – ;