Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Posobie_po_diskretnoy_matematike.docx
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
2 Мб
Скачать
☆

Булева алгебра

2.1. Логика высказываний

Любая научная теория воспринимается нами как некоторая система понятий и утверждений. Истинность каждого утверждения нуждается в доказательстве, которое в математике проводится с использованием логических средств. Именно эти логические средства изучает раздел математики, называемый математической логикой. Исходным понятием математической логики является понятие высказывания.

Под высказыванием принято понимать повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно.

Например, предложение « » - истинное высказывание. Предложение « » - ложное высказывание. Предложения « » и «Студенты, ходите на лекции!» высказываниями не являются.

В математической логике интересуются не содержанием высказывания, а его истинностным значением, т.е. его истинностью или ложностью. Для истинностных значений будем использовать следующие обозначения: «1» для истинности и «0» для ложности. Введем в рассмотрение основные логические связки:

Название

Прочтение

Обозначение

Отрицание

не

Конъюнкция

и

Дизъюнкция

или

Импликация

если … то

Эквиваленция

тогда и только тогда, когда

Используя логические связки, из одного или двух высказываний можно образовать новое высказывание, осуществив тем самым логическую операцию. При этом истинностные значения образованных высказываний определяются только истинностными значениями составляющих их высказываний, а не их смыслом.

Пусть и высказывания. Введем основные логические операции над высказываниями.

Название

Обозначение

Прочтение

Когда высказывание, полученное в результате операции, истинно

Когда высказывание, полученное в результате операции, ложно

Отрицание

( )

не

если ложно

если истинно

Конъюнкция

и

и

и оба истинны

в остальных случаях

Дизъюнкция

и

или

в остальных случаях

и оба ложны

Импликация

и

если , то

( влечет ,

из следует )

в остальных случаях

истинно, ложно

Эквиваленция

и

тогда и только тогда когда

( эквивалентно )

и имеют одинаковые значения истинности

в остальных случаях

Операции удобно задавать с помощью таблиц истинности.

0

0

1

0

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

0

1

1

1

1

Высказывательными переменными будем называть такие переменные, значениями которых могут быть любые высказывания. Обозначать высказывательные переменные будем заглавными буквами латинского алфавита и так далее.

Выражения, содержащие логические операции, назовем формулами. Для каждой формулы можно составить таблицу истинности.

Пример 1. Составить таблицу истинности формулы .

0

0

1

1

1

1

1

0

1

1

0

1

1

1

1

0

0

1

0

0

1

1

1

1

0

0

1

1

Таким образом, значение истинности данной формулы равно 1 при любых значениях истинности высказывательных переменных. Формулы, обладающие таким свойством, называются тавтологиями.

Значение тавтологий состоит, в частности, в том, что они дают правильные способы умозаключений. Например, схема логического умозаключения, выражаемого тавтологией , часто используется в математике и носит название «доказательство от противного».

Упражнение. Показать, что следующие формулы являются тавтологиями:

1. .

2. .

Определение. Две формулы и алгебры высказываний называются равносильными, если при любых значениях истинности переменных истинностные значения высказываний и совпадают.

То, что формулы и равносильны, обозначают так: .

Пример 2. Доказать равносильность формул и .

Для каждой из данных формул составим таблицу истинности.

0

0

1

1

0

1

1

1

1

0

0

0

1

1

0

1

0

0

1

0

1

1

1

0

0

1

1

1

Сравнивая таблицы, видим, что указанные формулы равносильны.

Существует связь между понятием тавтологии и понятием равносильности формул. Она заключается в следующем: формулы и равносильны тогда и только тогда, когда формула является тавтологией.

Утверждение. Пусть - произвольные высказывания. Имеют место равносильности:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ; 8. ;

9. ; 10. ;

11. ; 12. ;

13. ; 14. ;

15. ; 16. ;

17. ; 18. ;

19. .

В качестве упражнения рекомендуем самостоятельно доказать перечисленные равносильности, взяв за образец решение примера 2.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]