- •9. Вопросы к экзамену
- •10. Рекомендуемая литература
- •1. Основная литература
- •2. Дополнительная литература
- •Лекция № 2.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 3.
- •Основные вопросы, рассматриваемые на лекции:
- •Законы алгебры высказываний
- •Краткое содержание лекционного материала
- •Лекция № 4.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 5.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 6.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 7.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 8.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 9.
- •Основные вопросы, рассматриваемые на лекции:
- •Непротиворечивость исчисления высказываний
- •Независимость аксиом исчисления высказываний
- •Лекция № 10.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция №11.
- •Основные вопросы, рассматриваемые на лекции:
- •Операции над предикатами Краткое содержание лекционного материала
- •Лекция №12.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №13.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №14.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №15.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №15.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №16.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №18.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №19.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Практическое занятие №2 Тема: Запись предложений на языке пропозициональной логики
- •Практическое занятие №3 Тема: Тавтологии. Законы логики
- •Практическое занятие №4 Тема: Логическое следование
- •Практическое занятие №5 Тема: Равносильность формул
- •Практическое занятие №6 Тема: Дизъюнктивные и конъюнктивные нормальные формы
- •Практическое занятие №7 Тема: Виды теорем. Необходимые и достаточные условия
- •Практическое занятие №11 Тема: Полные системы связок
- •Практическое занятие №12 Тема: Построение выводов теорем
- •Практическое занятие №13 Тема: Независимость аксиом исчисления высказываний
- •Практическое занятие №14 Тема: Операции над предикатами
- •Практическое занятие №15 Тема: Интерпретации. Виды формул
- •Практическое занятие №16 Тема: Запись математических предложений на языке логики предикатов
- •Практическое занятие №17 Тема: Свойства обобщений и подтверждений
- •Практическое занятие №18 Тема: Логически общезначимые формулы
- •Практическое занятие №19 Тема: Отрицание формул
- •1. Мендельсон э. Введение в математическую логику. – м.: Наука, 1976. – 320 с.
- •2. Игошин в.И. Задачи и упражнения по математической логике и теории алгоритмов. - м.: Академия, 2007. – 304 с.
Лекция № 10.
Тема: ТЕОРЕМА ПОЛНОТЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Основные вопросы, рассматриваемые на лекции:
Лемма 1: S1A
Доказатьельство леммы 1 индукцией по формулам
Теорема полноты исчисления высказываний
Краткое содержание лекционного материала
Предположим, что в состав формулы A входят только следующие пропозициональные переменные p1,…,pn. Если дано некоторое распределение истинностных значений переменных p1,…,pn, то примем следующее обозначение: , где i1,…,n, и
Лемма 1. Имеет место следующее следствие системы S1:
S1A. (1)
Доказательство индукцией по формулам.
Если Api, i1,…,n, то Api, и (1) верно по определению следствия.
Пусть AB. Тогда по индуктивному предположению
S1B. (2)
Возможны два случая: BИ и BЛ.
Если BИ, AЛ, то AAB, BИ, BB, (1) следует из (2) и (P4).
Если AAB, BЛ, BB, то (1) есть (2).
Пусть ABC. Тогда по индуктивному предположению верно (2) и
S1C. (3)
Возможны три случая: BИ и CЛ; BЛ; CИ.
Если BИ и CЛ, то AЛ, AA(BC), BB, CC, (1) следует из (2) и (P8).
Если BЛ, то AИ, AABC, BB, (1) следует из (2) и (P5).
Если CИ, то AИ, AABC, CC, (1) следует из (3) и (P1).
Теорема полноты. Если A – тавтология, то S1A.
Доказательство. Так как A – тавтология, то AA.
В силу леммы 2, S1A, S1A.
В силу теоремы 4, S1 pnA, S1 pnA.
Отсюда и из (P6) следует, что S1A, и, аналогично получается, что S1A, …, S1A, S1A, S1A.
Лекция №11.
Тема: ПРЕДИКАТЫ И ОПЕРАЦИИ НАД НИМИ
Основные вопросы, рассматриваемые на лекции:
Определение n-местного предиката
Область определения и множество истинности предиката
Операции над предикатами Краткое содержание лекционного материала
n-местным предикатом AP(x1,…,xn) называется математическое предложение, содержащее n свободных переменных x1,…,xn. Говорят, что вхождение переменной в предложение или формулу свободно, если переменную можно заменять ее допустимым значением. Синонимы термина предикат: свойство, условие, отношение.
n-местный предикат AP(x1,…,xn) при замене всех свободных вхождений переменной xn ее допустимым значением dn обращается в (n1)-местный предикат BP(x1,…,xn1,dn)P(x1,…,xn1) (n1). Одноместный предикат AP(x) при замене всех свободных вхождений переменной x ее допустимым значением d обращается в высказывание AP(d).
Пусть D1,…,Dn – множества допустимых значений соответственно переменных x1,…,xn. Множество (декартово произведение)
DPD1…Dn(d1,…,dn)d1D1,…,dnDn
всех упорядоченных n-ок элементов множеств D1,…,Dn называется областью определения n-местного предиката P(x1,…,xn).
Множеством истинности n-местного предиката P(x1,…,xn) называется множество MP(d1,…,dn)DP(d1,…,dn)1 всех n-ок допустимых значений переменных x1,…,xn, при которых предикат P(x1,…,xn) истинен.
Например, если P(x,y) есть x2y213, а DPNN, то MP(2,3),(3,2).
Для одноместного предиката P(x) множество истинности есть множество MPdDPP(d)1допустимых значений переменной x, при котором предикат P(x) истинен.
Например, если P(x) есть x213, а DPN, то MP1,2,3.
Используя связки , , , , , из данных предикатов P(x1,…,xn) и Q(x1,…,xn) с общей областью определения D образуются новые предикаты с той же областью определения D.
Отрицание P(x1,…,xn) строится из P(x1,…,xn) при помощи связки , при этом для любой n-ки (a1,…,an)D.
Дизъюнкция P(x1,…,xn)Q(x1,…,xn) образуется из P(x1,…,xn) и Q(x1,…,xn) при помощи связки , при этом для любой n-ки (a1,…,an)D
Конъюнкция P(x1,…,xn)Q(x1,…,xn) составляется из P(x1,…,xn) и Q(x1,…,xn) при помощи связки , при этом для любой n-ки (a1,…,an)D
Легко увидеть, что , и .
Импликация P(x1,…,xn)Q(x1,…,xn) получается из P(x1,…,xn) и Q(x1,…,xn) при помощи связки , при этом для любой n-ки (a1,…,an)D
Эквивалентность P(x1,…,xn)Q(x1,…,xn) строится из P(x1,…,xn) и Q(x1,…,xn) при помощи связки , при этом для любой n-ки (a1,…,an)D
Для предикатов, кроме пропозициональных операций , , , , , существует операции навешивания кванторов.
Знак обозначает слова вида "существует", "некоторые" и т.п.
Знак обозначает слова вида "все", "для всякого" и т.п.
Квантор существования и общности – это символы x и x с некоторой переменной x.
Навешивание квантора xi или xi (i1,…,n) к предикату P(x1,…,xn), с n свободными переменными x1,…,xn, приводит, соответственно, к предикату xiP(x1,…,xn) или xi(x1,…,xn) уже с n1 свободными переменными x1,…,xi1,xi1,…,xn (переменная xi станет связанной).