- •Дискретная математика
- •Введение
- •1. Введение в теорию множеств
- •1.1. Множества
- •Основные понятия
- •Операции над множествами
- •Свойства операций объединения и пересечения
- •1.2. Отношения
- •1.2.1. Бинарные отношения. Основные определения
- •1.2.2. Свойства бинарных отношений
- •2. Теория графов
- •2.1. Основные понятия
- •2.2. Способы задания графов
- •2.4. Сети и их свойства1
- •3. Введение в математическую логику
- •3.1. Логика высказываний
- •3.1.1. Высказывания
- •3.1.1.1. Понятие высказывания
- •2.1.1.2. Логические связки
- •1.1.3. Условные высказывания
- •1.1.4. Эквивалентные высказывания
- •3.1.2. Аксиоматические системы
- •3.1.2.1. Умозаключения
- •3.1.3. Полнота в логике высказываний
- •3.1.3.1. Эквивалентные замены логических связок
- •3.2. Логика предикатов
- •3.2.1. Определение предиката
- •3.2.2. Кванторы. Их свойства и применение
- •3.2.2.1. Квантор всеобщности и квантор существования
- •4. Прикладная теория алгоритмов
- •4.1. Алгоритм: определение и основные свойства
- •4.2. Реализация управляющих алгоритмов
- •4.3. Формализация понятия алгоритма
- •4.4. Машина Тьюринга
- •4.5. Свойства машины Тьюринга
- •4.6. Реализация машины Тьюринга
- •4.7. Формальные системы и алгоритмы.
- •5. Комбинаторный анализ
- •5.1. Основное правило комбинаторики
- •5.2. Правило суммы
- •5.3. Правило прямого произведения
- •5.4. Перестановки
- •5.5. Число различных k-элементарных подмножеств n-элементарного множества
- •5.6. Число подмножеств данного множества
- •5.7. Размещение элементов множества
- •5.7. Размещения с повторениями
- •5.8. Размещения без повторений
- •5.9. Комбинации элементов с повторениями
- •6. Языки и грамматики
- •6.1. Основные определения
- •6.2. Формальные грамматики
- •6.3. Грамматики с ограничениями на правила
- •6.4. Способы записи синтаксиса языка
- •Метаязык Хомского
- •Метаязык Хомского-Щутценберже
- •Бэкуса-Наура формы (бнф)
- •Список рекомендуемой литературы
1.1.3. Условные высказывания
Допустим, некто утверждает, что если случится одно событие, то случится и другое. Предположим, отец говорит сыну: "Если в этом семестре ты сдашь все экзамены на «отлично», я куплю тебе машину". Заметьте, что высказывание имеет вид: если р, то q, где р — высказывание В этом семестре ты сдашь все экзамены на «отлично», а q — высказывание Я куплю тебе машину. Сложное высказывание мы обозначим символически через . Спрашивается, при каких условиях отец говорит правду? Предположим, высказывания р и q истинны. В этом случае счастливый студент получает отличные оценки по всем предметам, и приятно удивленный отец покупает ему машину. Естественно, ни у кого не вызывает сомнения тот факт, что высказывание отца было истинным. Однако существуют еще три других случая, которые необходимо рассмотреть. Допустим, студент действительно добился отличных результатов, а отец не купил ему машину. Самое мягкое, что можно сказать об отце в таком случае, — это то, что он солгал. Следовательно, если р истинно, а q ложно, то ложно. Допустим теперь, что студент не получил положительные оценки, но отец тем не менее купил ему машину. В этом случае отец предстает очень щедрым, но его никак нельзя назвать лжецом. Следовательно, если р ложно и q истинно, то высказывание если р, то q (т.е. ) истинно. Наконец, предположим, что студент не добился отличных результатов, и отец не купил ему машину.
Поскольку студент не выполнил свою часть соглашения, отец тоже свободен от обязательств. Таким образом, если р и q ложны, то считается истинным. Итак, единственный случай, когда отец солгал, — это когда он дал обещание и не выполнил его.
Таким образом, таблица истинности для высказывания имеет вид
Случай |
p |
q |
|
1 |
T |
T |
T |
2 |
T |
F |
F |
3 |
F |
T |
T |
4 |
F |
F |
T |
Символ называется импликацией, или условной связкой.
Может показаться, что носит характер причинно-следственной связи, но это не является необходимым. Чтобы увидеть отсутствие причины и следствия в импликации, вернемся к примеру, в котором р есть высказывание Джейн управляет автомобилем, а q — утверждение У Боба русые волосы. Тогда высказывание Если Джейн управляет автомобилем, то у Боба русые волосы запишется как
если p, то q
или как
.
То, что Джейн управляет автомобилем, никак причинно не связано с тем, что Боб русоволосый. Однако нужно помнить, что истинность или ложность бинарного сложного высказывания зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой-либо связи.
Рассмотрим следующий пример. Требуется найти таблицу истинности для выражения
.
Используя таблицу истинности для , приведенную выше, построим сначала таблицы истинности для и , учитывая, что импликация ложна только в случае, когда .
Теперь используем таблицу для , чтобы получить для высказывания
таблицу истинности
Случай |
p |
q |
r |
(p |
|
q) |
|
(q |
|
r) |
1 |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
2 |
T |
T |
F |
T |
T |
T |
F |
T |
F |
F |
3 |
T |
F |
T |
T |
F |
F |
F |
F |
T |
T |
4 |
T |
F |
F |
T |
F |
F |
F |
F |
T |
F |
5 |
F |
T |
T |
F |
T |
T |
T |
T |
T |
T |
6 |
F |
T |
F |
F |
T |
T |
F |
T |
T |
F |
7 |
F |
F |
T |
F |
T |
F |
T |
F |
F |
T |
8 |
F |
F |
F |
F |
T |
F |
T |
F |
T |
F |
|
|
|
|
1 |
2 |
1 |
* |
1 |
2 |
1 |
Высказывание вида обозначается через . Символ называется эквиваленцией. Эквиваленция также иногда обозначается как (не следует путать с унарной операцией отрицания).
Очевидно, таблица истинности для определяет таблицу истинности для . Непосредственно из определения вытекает, что эквиваленция истинна только в случае, когда р и q имеют одинаковые истинностные значения.
Может возникнуть вопрос о том, как интерпретировать такие выражения, как , , и , в которых отсутствуют скобки. Во избежание неоднозначности лучше всегда использовать скобки. Однако здесь, как и в алгебре, имеется приоритет выполнения операций. Операции выполняются в следующей последовательности: ~, , , , . Поэтому указанные выражения можно интерпретировать как , , и .