МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Лекции
ДИСКРЕТНАЯ МАТЕМАТИКА
5 семестр
Лектор
Москва, 2010/2011
Лекция № 1.
БУЛЕВЫ ФУНКЦИИ (ФАЛ).
2. Правило перестановки мест посылок.
├
4
1. 
├
условие выводимости 1
2. ├
условие выводимости 1
3. ├
MP(1,2)
4. ├
условие выводимости 1
5. ├
MP(3,4)
6. ├
теорема дедукции
7. ├
теорема дедукции
3
3. Правило объединения посылок.
├
4. Правило разъединения посылок.
├
Свойства системы аксиом:
1. Непротиворечивость.
2. Полнота.
3. Независимость.
╞ Общезначимость (знак тождественной истинности).
Теорема 1.
Теорема состоятельности.
Любая выводимая ППФ (теорема) общезначима.
4Все аксиомы – суть общезначимые ППФ. Правила вывода устроены так, что из общезначимых ППФ получаем всегда общезначимые. Таким образом, все теоремы – общезначимые ППФ.3
Лемма 1.
Пусть A – ППФ и 
– буквы, в неё входящие. Пусть дано некоторое распределение истинностных значений всех букв в ППФ A. Пусть 
Тогда из 
├
.
4Докажем методом математической индукции по числу логических связок в ППФ А.
1. 
├
├
2. Пусть лемма верна при числе логических связок 
.
Докажем, что она верна и при 
.
2.1. Пусть А есть 
.
2.1.1. Пусть B – истина, тогда 
.
По индуктивному предположению:
├
├
10 аксиома
├
МР
├
2.1.2. Пусть B – ложь, тогда 
.
По индуктивному предположению:
├
├
2.2. Пусть А имеет вид 
.
2.2.1. Пусть A – истина, тогда .
По индуктивному предположению:
├
├
├ МР
├
2.2.2. Пусть 
.
По индуктивному предположению:
├
├
1 аксиома
├ МР
├
2.2.3. Пусть B – истина, C – ложь, тогда 
.
По индуктивному предположению:
├
├
├
теорема дедукции
├
2xMP
├
3
Теорема 2.
Теорема о полноте (в широком смысле).
Любая общезначимая ППФ является теоремой (выводима).
4Предположим, что А – суть общезначимая ППФ и в неё входят. Тогда по лемме 1 ├.
1. Пусть 
– истина, тогда 
├; 
├
.
2. Пусть – ложь, тогда 
├; ├
.
├
├ MP
Повторяем k – 1 раз. Получаем А как ППФ.3
Замечание.
Кроме понятия полноты в широком смысле существует понятие полноты в узком смысле.
Теорема 3.
О непротиворечивости.
Логическое высказывание непротиворечиво, т. е. нельзя одновременно вывести и и 
.
Определение 1.
Аксиома независима, если она не выводима из остальных аксиом формальных систем.
Определение 2.
Система аксиом независима, если любая аксиома этой системы независима, т. е. не выводима из остальных.
Лекция № 2.
БУЛЕВЫ ФУНКЦИИ (ФАЛ).
├
4Считаем, что все логические связки имеют стандартную истинностную таблицу.
Утверждение 
есть .
Тогда первые 8 аксиом остаются общезначимыми. Проверим 9, 10 и 11 аксиомы.
9-ая аксиома не общезначимая ППФ.
├
общезначима.3
Основные понятия
логики предикатов (ЛП) I-ого порядка.
До сих пор рассматривали сложные высказывания как простые.
Пусть M – некоторое множество различных предметов 
, высказывание об отдельном предмете 
, о двух предметах 
и нескольких предметах 
.
Пример.
– 5 – чётное число (ложь).
– 4 – чётное число (истина).
Определение 1.
n-местный предикат 
, где 
– предметная переменная.
Предикатом называется логическое высказывание при фиксировании своих аргументов.
Введём две операции:
1. 
«Все (каждый, любой) x обладают свойством P – истина».
2. 
«Существует x, обладающее свойством P – истина».
3. 
Пусть имеется формула A, тогда в выражении формула А называется областью действия.
Определение 2.
Вхождение x в данную формулу A называется связанным, если x является переменной, стоящей под знаком квантора и находится в области его действия. В противном случае вхождение переменной x свободно.
Определение 3.
Переменная называется свободной (связанной) для данной формулы, если её вхождение в данную формулу свободно (связано).
Пример.
, x – связанная, y – свободная.
В общем случае 
понимается как утверждение о том, что для любых значений, придаваемых переменным 
из области определения, зависит только от свободных переменных, входящих в формулу A.
Выражение 
понимается как утверждение о том, что существует, по крайней мере, 1 способ замены переменных 
своими значениями из области определения A такой, что истинность формулы A будет зависеть только от свободных переменных, входящих в эту формулу.
Проблемы перевода с естественного языка в логику – основная проблема искусственного интеллекта.
Двойственность кванторов.
Не для всех x 
истина. Значит, что существует x, где ложь, а не истина.
Не существует x, где истина. Значит, для всех x ложь, а не истина.
Определение формулы.
Определение 4.
Термом будем называть любую предметную переменную или константу. Под термом будем понимать функциональную букву 
– терм.
Определение 5.
Атомарной формулой (атомом) будем называть любое переменное высказывание (из числа логических высказываний) или предикат. Предикат 
– атомарная формула.
Определение 5.
Любой атом – формула.
Если A и B – формулы, то 
тоже формулы.
Других формул нет.
Таким образом, вся логика высказываний входит в логику предикатов. Логика предикатов занимается теорией вывода.
Определение 6.
Интерпретацией будем называть систему, состоящую из непустого множества D, называемого областью интерпретации (универсумом), и некоторого соответствия предметной букве.
n-местное отношение, т. е. 
.
Каждой n-местную функцию, т. е. 
.
Каждой константе любой предикат из D 
.
Замечание.
В данной интерпретации любая формула без свободных переменных есть высказывание. А любая формула со свободными переменными – отношение, которое может быть или истинным или ложным.
Лекция № 3.
БУЛЕВЫ ФУНКЦИИ (ФАЛ).
Три типа формул:
1. Общезначимая ППФ – истинна при любой интерпретации.
2. Противоречивая ППФ – ложна при любой интерпретации.
3. Остальные (выполнимые) истинны хотя бы при одной интерпретации.
Пример.
1. ╞
«Из общего следует частное».
4Докажем от противного.
Имеем область интерпретации D, где принимает значение «ложь».
╞
– ложь.
Для всех x истинна, но 
, где 
– ложь. 
D быть не может. 3
2. ╞
«Из частного следует тоже частное».
4Докажем от противного.
Имеем область интерпретации D, где принимает значение «ложь».
╞
– ложь.
Возможно только, если x = y. Противоречие. 3
Теорема 1.
а) ╞
б) ╞
4Вычисление значений формул 
для данного присвоения значений переменных состоит из вычислений значений логической функцией, поставленной в соответствие этой A, а значение всей формулы совпадает с вычислениями из примеров 1 и 2.3
Следствие.
╞
, то ╞
.
╞
(из частного не следует общее).
Теорема 2.
Пусть x – некоторая предметная переменная и B – формула, не имеющая свободного вхождения x. A(x) – формула.
а) ╞
, то ╞
б) ╞
, то ╞
4а) Пусть для некоторой D, где B принимает значение ложь. По определению импликации (понятно). Пусть имеется D, где B принимает значение истины. А если A(x) истина, то тоже истина 
.
б) Доказывается аналогично.3
Следствие.
╞, то ╞
4
1. ╞
1 аксиома
2. ╞
3. ╞ MP(1,2)
Применяя теорему 2а можем на А(x) навесить квантор общности.
4. ╞
5. ╞
, где ╞
6. ╞ MP(4,5)
3
Логика предикатов как формальная система.
Термы.
– счётное множество предметных переменных.
– непустое конечное или счётное множество предметных символов.
– пустое, конечное или счётное множество функциональных символов
– пустое, конечное или счётное множество предметных констант.
Логические связки: 
Кванторы: 
Вспомогательные символы: 
Других термов нет.
Правила построения ППФ.
1) Любая атомарная ППФ – суть атом (атомарная формула) ППФ, переменная логики высказывания или предикат.
2) Если А и B – ППФ и x – предметная переменная, то 
– ППФ.
3) Других правил нет.
Система аксиом.
11 аксиом.
12. 
13. 
1) Все аксиомы суть теоремы (выводимы).
2) Правило подстановки, но имеем дело с такой подстановкой термов 
вместо 
в формулу A. После подстановки 
будет свободна для этих термов.
3) Правило обобщения (Gen). Если выводимо ├, где B не имеет свободного вхождения x, то ├.
4) Правило конкретизации (Ex). Если выводимо ├, где B не имеет свободного вхождения x, то ├.
5) Modus ponens (MP).
6) Если A – теорема, имеющая квантор 
или 
, то теоремой будет A’, полученная из A путём замены одной связанной переменной буквами отличными от букв связанных переменных.
7) Других нет.
Будем считать, что некоторая ППФ 
├ (далее для краткости ├).
1. ├
2. ├, то ├
3. ├
и ├
, то ├
4. ├
, если и не имеют свободного вхождения x, то ├
5. ├
, то ├
6. ├, то ├
, получено из B путём подстановки вместо свободных вхождений в B переменных.
7. ├, то ├, получено из B переименованием связанных переменных.
Теорема Дедукции.
Если ├, то ├
,
├
1. ├
9 аксиома
2. ├
подстановка
3. 
├ MP
4. ├
т. дедукции
5. ├
т. дедукции
6. ├
силлогизм(2,5)
Правило соединения посылок:
├
├
1. 
├
2. ├
3 аксиома
3. ├
4. ├ MP(1,2)
5. ├
условие 1
6. ├ MP(4,5)
7. ├ MP(1,3)
8. ├ MP(6,7)
9. ├
├
1. ├
5 аксиома
2. ├
подстановка
3. ├
4. ├
MP(2,3)
5. ├
подстановка
6. ├
7. ├
силлогизм(5,6)
8. ├
подстановка
9. ├ следствие теоремы дедукции
(правило перестановки мест посылок)
1. 2. 3. 4. 5. 6. 7. 8. ├ 9. ├ 10. ├ 11. ├ 12. ├ 13. ├ |
├
├
├
├
