- •8 Комбинаторика
- •Рис.1.1. Операции над множествами (не закончено)
- •Булевой алгеброй является и алгебра логических функций Дадим определение алгебре логических функций.
- •Таблица 2.1
- •Таблица 2.2
- •Таблица 2.3
- •Покрывающий их интервал соответствует элементарной конъюнкции
- •4.3.Проверка правильности рассуждений
- •4.4. Нормальные формы формул алгебры высказываний.
- •4.6. Решение логических задач методом характеристичесого уравнения.
- •Основные тавтологии алгебры высказываний
- •Всякое высказывание логична следует из самого себя.
- •Если из а следует b, а b ложно, то а тоже ложно.
- •4.3.Проверка правильности рассуждений
- •6.5. Машины Тьюринга
- •7.Элементы теории автоматов
- •8 Комбинаторика
Всякое высказывание логична следует из самого себя. 2. Закон противоречия:
Всякое высказывание не м.б. одновременно истинным и ложным. 3. Закон исключения третьего:
Для всякого высказывания истинно либо оно само либо его отрицание. 4. Закон двойного отрицания:
Отрицание отрицания любого высказывания равносильно самому высказыванию. 5. Закон «истинно из чего угодно»:
Если а – истинное высказывание, то ф-ла (bÆa) – истинна. 6. Закон «из ложного что угодно»:
Если а – ложное высказывание, то из а следует всё, что угодно. 7. Закон modus ponens:
Если истинно то, что из а следует b, и а истинно , то b истинно. 8.Закон modus tollens:
Если из а следует b, а b ложно, то а тоже ложно.
9. Закон силлогизма:
Если из а следует b, а из b следует с, то из а следует с.
4.2. Логические отношения
Имеем два высказывания P и Q.
1. Отношение следствия (P=>Q). Говорим, что из P следует Q, если Q истинно всякий раз, когда истинно P. Q наз. следствием P.
Пусть P=AÆB, Q= A B. Следует ли P из Q? Следует ли из P высказывание Q?
A |
B |
P=AÆB |
Q=A B |
PÆQ |
QÆP |
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
0 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
Следовательно, из Q следует P.
Заметим, что между отношениями следствие и импликация существует тесная связь. Но это не одно и тоже. Импликация – сложное высказывание, составленное из двух данных, а следствие – отношение между двумя высказываниями. Импликация выражает отношение следствие только тогда, когда таблица истинности импликации содержит одну единицу. Отметим, что высказывания, связанные с импликацией, при отсутствии смысловой связи между посылкой и заключением могут звучать парадоксально. Например: « Если я не приду на лекцию, то река впадает в Белое море.» Звучит парадоксально. Между посылкой и заключением в подобных случаях не существует отношения следствия.
2. Два высказывания P и Q эквивалентны, если таблица истинности P Q
содержит только единицы. Импликация P=AÆB и импликация Q= B →A эквивалентны. Эти формулы в рассуждении заменяют друг друга.
3. Два высказывания P и Q называются несовместимыми, если не существует логической возможности, при которой оба высказывания были бы
одновременно истинными, т.е. при истинном значении одного из них другое обязательно ложно.
Чтобы установить совместимость высказывания, нужно построить их таблицы истинности. Если найдется хотя бы одна строка, в которой все высказывания