Контрольные вопросы

1. Алфавит, формулы, система аксиомных схем, правило вывода теории L.

2. Формальное доказательство и формальный вывод.

3. Свойства отношения выводимости.

4. Метод доказательства теоремы дедукции.

5. Непротиворечивость теории L.

6. Правила введения и удаления логических операторов.

7. Полнота теории L.

8. Адекватность теории L алгебре высказываний.

9. Разрешимость теории L.

10. Независимость аксиом теории L.

Задания для самостоятельного выполнения

1. Укажите выводом какой формулы и из каких посылок является следующая последовательность формул:

   1. АС, (АС)((ВС)(АВС)), (ВС)(АВС), ВС, АВС, АВ, С.

   2. (АВ)((АВ)А), АВ, (АВ)А, АВ,А.

   3. (АВ)((ВА)(А~В)), АВ, (ВА)(А~В), ВА, А~В.

   4. (АВ)(ВА), АВ, ВА, В, А.

2. Постройте данный вывод и результирующий вывод, применяя метод доказательства теоремы дедукции:

1. A, B├ AB

2. PQ├ P

3. P├ P Q

4. AB, BA├ AB

5. PQ├ PQ

6. АВ, АВ├ А

3. Постройте данный вывод и результирующий вывод, применяя метод доказательства теоремы дедукции:

1. CA, CB, C├ AB

2. AB, A(BC)├ C

3. AB, BC├ AC

4. (AC)C, AB, BC├ C

5. AB, B├ A

6. AB, CE, BE├ AC

7. А ~В, В С├ АС

8. АС, ВА├ ВС

9. ВА, А├ В

10. AB, AB├ AB

11. AB, B├ A

12. AB, BC├ AC

13. A├ BB

14. AB, CB├ A

4. Постройте доказательства:

   1. АAA

   2. AAА

   3. A (AА)

   4. AВAВ

   5. (BB)

5. Дано доказательство:

(А  (ВA))  ((A  ((ВA)  A)) (А  A))	1.
А  (ВA)	2. АС1
(A  ((ВA)  A))  (А  A)	3. МР(F2,F1)
A  ((ВA)  A)	4.
А  A	5. МР(F4,F3)
├A А	6. ОФД (1-5) – определение формального доказательства

Дополните его до доказательства формулы AА.

6. Установите существование доказательств следующих формул:

   1. ├ (АВ)(ВС)(АС)

   2. ├ (А(ВС))(АВС)

   3. ├ (АВС)(А(ВС))

   4. ├ А(ВАВ)

   5. ├ (АВ)(А(АВ))

7. Установите следующие выводимости:

1. A,B├ AB

2. AB, A├ B

3. (AB),B├ AB

4. ABC, DA, DEB├ DEC

5. AB, AB├ С

6. B, AC, A(BC)├ AB

7. AB,B├ A

8. AB, BC├ AC

9. AB, AB├ C

10. ABC, DB, DC├ A

11. AB, AC├ BC

12. ABC, AB├ C

13. ABC,C├ AB

14. ABC,C├ AB

15. AB,BA├ C

16. B, AB├ (BA)

17. AB, CB├ A

18. AB, CD,BD├ AC

19. AB,CD,BD├ AC

20. ABC, AC├ B

21. AB, CD, AC,BD├ BA.

8. Установите следующие доказуемости:

   1. AAА

   2. AАBА

   3. А(ВС) АВС

   4. АВВА

   5. (АВ)АВ

   6. (АВ)(ВА)

   7. A(ВС)(AВ)С

   8. A(ВС)(AВ)С

   9. AАВ AВ

   10. АВ(АВ)

   11. АВ(АВ)

   12. (АВ)АВ

   13. АВАВ

   14. A (ВС)(AВ)(АС)

   15. A(ВС)(AВ)(АС)

Литература

1. Латотин Л.А., Макаренков Ю.А., Николаева В.В., Столяр А.А. Математическая логика. – Минск: «Вышейшая школа». 1991.

2. Лихтарников Л.М., Сукачева Т.Г. Математическая логика: курс лекций, задачник-практикум и решения. – СПб.:[б.и.], 1999.

3. Игошин В.И. Задачник-практикум по математической логике. – М.: Просвещение, 1986.