- •Конспект лекций по дисциплине «основы дискретной математики»
- •Лекция № 1. Дискретное и непрерывное
- •Лекция № 2. Системы счисления
- •Лекция № 3. Фракталы
- •3.1. Канторово множество
- •3.2. Ковер Серпинского и снежинка Коха
- •3.3. Стохастические фракталы
- •3.4. Энтропийная размерность
- •3.5. Фрактал Мандельброта
- •Лекция № 4. Основы математической логики
- •Набор истинностных значений 0001 в первой строке таблицы соответствует результатам операций:
- •Основные эквивалентности:
- •X(баскетболист(X)высокий(X))
- •X(личность(х)любит(х, грибы))
- •X любит(х, платить(налоги))
- •X(человек(X)смертный(X)),
- •Лекция № 5. Множества и подмножества
- •Лекция № 6. Математическая индукция
- •Лекция № 7. Комбинаторика
- •Лекция № 8. Числа фибоначчи и простые числа
- •Лекция № 9. Кодирование
- •Лекция № 10. Шифрование
Лекция № 4. Основы математической логики
Виды доказательства
Древние греки сформулировали основные правила логического доказательства. Они различали два вида доказательства: дедукцию и индукцию. Дедукция – это доказательство от общего к частному. Индукция – напротив, доказательство от частного к общему.
Рассмотрим классический пример. Задана так называемая большая посылка (или общее утверждение): «Все люди смертны». Также задана малая посылка (частное утверждение): «Сократ – человек». Из этих посылок методом дедукции легко получить заключение: «Сократ – смертен». В большой и малой посылках содержится достаточно информации, чтобы быть абсолютно уверенным в этом.
Если из малой посылки и заключения получают большую посылку, то такой метод доказательства называется индукцией. В малой посылке «Сократ – человек» и заключении «Сократ – смертен» не содержится достаточно информации, чтобы прийти к утверждению: «Все люди смертны». Мы можем рассматривать его только как гипотезу. Допустим, окажется, что смертен не только Сократ, но и Платон, который также является человеком. Степень нашей уверенности возрастает, однако она никогда не будет абсолютной, поскольку в будущем, возможно, родится человек, который будет жить вечно (а вдруг?).
Таким образом, дедукция обладает неоспоримым преимуществом перед индукцией. Однако научное знание, как правило, получают методом индукции, поскольку в готовом виде общие утверждения человеку никто не посылает, приходится основываться на частном опыте. Даже гениальные озарения являются результатом длительных наблюдений и размышлений.
Математики нового времени ввели еще один тип доказательства, неизвестный древнегреческим математикам, абдукцию. Это доказательство малой посылки, основанное на большой посылке и заключении. В нашем примере на основании утверждений: «Все люди смертны» и «Сократ – смертен», мы можем вывести методом абдукции утверждение, что: «Сократ – человек». Очевидно, что этот вид доказательства тоже не столь безупречен, как дедукция. Ведь Сократ вполне может оказаться котом или собакой, которые также смертны.
Логические высказывания, связки и операции
Высказывание – имеющее смысл языковое выражение, относительно которого можно утверждать, что оно либо истинно (True), либо ложно (False). Вместо слов True и False часто употребляются числа 1 и 0 соответственно.
Пример 4.1. Имеем два высказывания: «Дважды два четыре» и «3+5=9». Первое высказывание имеет истинное значение, а второе – ложное.
Если отвлечься от смысла высказывания, его можно обозначить буквой и рассматривать как переменную. Используя логические связки: «НЕ», «И», «ИЛИ», «ЕСЛИ ..., ТО...» и другие – можно из одних высказываний строить новые высказывания. Построение из заданных высказываний нового высказывания называется логической операцией.
Логические связки могут быть одноместные (унарные), двухместные (бинарные), трехместные (тернарные) и т. д. В алгебре логики логические операции чаще всего описываются с помощью таблиц истинности. Для одноместной операции «не» («инверсия») таблица истинности выглядит так.
Таблица 4.1.
«А» |
«не А» |
0 |
1 |
1 |
0 |
«Не А» обозначается как А, или Ā, или ~А, или !A. В табл. 2.2 приведены основные двухместные логические операции.
Таблица 4.2
Обозначение логической операции |
Другие обозначения логической операции |
Набор истинностных значений |
Название логической операции и связки |
Как читается выражение |
А B |
А &B АB АB min(А,B) |
0001 |
Конъюнкция, логическое умножение, логическое «И» |
А иB
|
А B |
А+B max(А,B)
|
0111 |
Дизъюнкция, логическое сложение, логическое «ИЛИ» |
А илиB
|
А B |
А B А B |
1101 |
Импликация, логическое следование |
Если А, то B; А имплицирует B; А влечетB |
А B |
А~ B А B А B |
1001 |
Эквиваленция, эквивалентность, равнозначность, тождественность |
А тогда и только тогда, когдаB; А эквивалентноB |
А B |
А+B АB
|
0110 |
Сумма по модулю 2, разделительная дизъюнкция, разделительное «ИЛИ» |
А плюсB; либо А, либо B |
А | B |
А B |
1110 |
Штрих Шеффера, антиконъюнкция |
Неверно, что А иB; А штрих ШеффераB |
АB |
А B А B |
1000 |
Стрелка Пирса, антидизъюнкция, функция Вебба, ф-я Даггера |
Ни А, ни B; А стрелка Пирса B |