Свойства операций над множествами
1.
– коммутативность;
2.
– ассоциативность;
3.
– дистрибутивность;
4.
– идемпотентность;
5.
– двойное отрицание;
6.
– закон Моргана;
7.
- законы поглощения.
Определение
13.
Символы
и
,
U
и
называются двойственными.
Методом таблиц Буля легко показать, что имеет место принцип двойственности: при замене в любом свойстве входящих в него символов на двойственные, оно остается верным.
Пример. Докажем, например, закон Моргана.
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
ЭЛЕМЕНТЫ ЛОГИКИ
"Всё наше достоинство заключено в мысли".
Б. Паскаль.
"Но если не грешить против разума, нельзя
вообще ни к чему прийти".
А. Эйнштейн.
Н. Бурбаки начинает свою книгу «Начала математики» так: «Со времён греков говорить «математика» значит говорить «доказательство»». В этом пункте мы обсудим, на чём основано понятие доказательства.
2.1. Высказывания
Определение 1. Высказыванием называется любое верифицируемое повествовательное предложение, т.е. предложение, относительно которого можно утверждать истинно оно или ложно.
Пример «
»
– высказывание; «сегодня хорошая погода»
– не высказывание (для кого как!).
Определение 2. Предложение, содержащее переменную и обращающееся в высказывание при подстановке конкретных значений называют высказывательной формой.
Пример.
Определение 3. Множество всех возможных истинных интерпретаций высказывания называется смысловым полем (интерпретация – это форма представления информации).
Смысловое поле задано на своём универсуме – множестве всех возможных интерпретаций. Это позволяет высказывания, как и множества, изображать кругами Эйлера. В этом случае характеристическая функция для высказываний имеет вид:
.
A – высказывание, а – его интерпретация.
Определение
4. Сложным называется
высказывание, составленное из простых
с помощью логических операций:
–
неверно, что;
–
конъюнкция;
–
дизъюнкция;
–
импликация;
–
эквивалентность; и кванторов:
–
существует,
–
для всех,
- тавтология
(всегда истинно).
Опишем эти операции, используя понятие смыслового поля:
или
А – неверно,
что А;
– дизъюнкция
(«или»), совокупность (disjunctio
– различие);
– конъюнкция
(«и»), система (conjunctio
– союз);
–
импликация, теорема
(implictio
– тесно связывать);
–
эквивалентность
(или
).
Это описание позволяет составить таблицы истинности для этих операций.
A |
B |
|
|
|
|
|
и |
и |
л |
и |
и |
и |
и |
и |
л |
л |
и |
л |
л |
л |
л |
и |
и |
и |
л |
и |
л |
л |
л |
и |
л |
л |
и |
и |
Теперь можно точно дать определения.
Определение 5 Дизъюнкцией двух высказываний и называется новое сложное высказывание , которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний или .
Определение 6. Конъюнкцией двух высказываний … (самостоятельно)
Определение 7. Эквиваленцией … (самостоятельно).
Определение 8. Импликацией двух высказываний и называется новое сложное высказывание , которое ложно тогда и только тогда, когда высказывание истинно, а высказывание ложно.
Импликация
называется ещё теоремой.
Тогда говорят, что
достаточное
условие для
,
– необходимое
условие для
.
Теорема
называется прямой,
– обратной,
–
противоположная прямой,
– противоположная обратной. Используя
таблицы истинности, докажем три важных
факта:
Теорема 1.Теорема эквивалентна теореме .
Теорема 2.Теорема эквивалентна .
Теорема
3.Теорема
эквивалентна дизъюнкции
.
Доказательство:
|
|
|
|
|
|
|
|
|
и |
и |
и |
л |
л |
и |
и |
и |
и |
и |
л |
л |
л |
и |
и |
и |
л |
л |
л |
и |
и |
и |
л |
л |
л |
и |
и |
л |
л |
и |
и |
и |
и |
и |
и |
и |
■
Теоремы 1 и 2 называют законом контрапозиции, а теорему 3 – дизъюнктивной формой импликации.