Занятие 1. Суждение. Высказывание. Формализация высказывания. Простые высказывания. Сложные высказывания. Операции над сложными высказываниями. Таблицы истинности

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

Например, высказывание «Москва — сто­лица Российской Федерации» является истинным, а высказывание «Вол­га впадает в Черное море» — ложным.

Задание: укажите, какие из высказываний являются истинными и какие — ложными.

а) 3+2 = 5; б) 3< 2; в) 3х < 2; г) у² ≤ 0;

д) «Число слов в этом предложении равно семи»;

е) «Осень — лучшая пора года»;

ж) «Зна­ете ли вы украинскую ночь?»;

з) «В четырехугольнике противопо­ложные стороны конгруэнтны»;

и) «Во всяком четырехугольнике противоположные стороны конгруэнтны»;

к) «В некоторых четы­рехугольниках противоположные стороны конгруэнтны»;

л) «Су­ществует число х такое, что х² < 0»;

м) «Для всякого числа х |х| > 0»;

н) «В городе N более 100 000 жителей»;

о) «Существует наи­большее натуральное число»;

п) H₂0+S0₃=H₂S0₄.

Высказывания бывают:

1. Простыми – если в них нельзя выделить часть, которая сама является высказыванием и не совпадает по смыслу с исходными;

2. Составными – в противном случае.

Простые высказывания будем обозначать малыми буквами латинского алфавита, а факт истинности или ложности высказывания записывать собственно: а = 1 или а = 0.

Буквы, обозначающие переменные высказывания, будем называть высказывательными переменными.

Для конструирования составных высказываний из простых используют так называемые логические связки:

1. не; неверно, что;

2. и; а; но;

3. или; либо;

4. если, то;

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

 

Логические операции над высказываниями:

1. Отрицанием высказывания а называется новое высказывание, обозначаемое и читаемое не а, неверно, что а, которое является истинным тогда и только тогда, когда высказывание а ложно, и наоборот.

2. Конъюнкцией двух высказываний а и b называется новое высказывание, обозначаемое , которое истинно тогда и только тогда, когда оба высказывания истинны и ложное во всех остальных случаях.

3. Дизъюнкцией двух высказываний а и b называется высказывание, обозначаемое , которое является ложным тогда и только тогда, когда ложны оба высказывания и истинное во всех остальных случаях.

4. Импликацией двух высказываний а и b называется высказывание, обозначаемое , которое является ложным тогда и только тогда, когда 1-ое высказывание а истинно, а второе высказывание b – ложно.

5. Эквиваленцией двух высказываний а и b называется высказывание, обозначаемое , которое является истинным тогда и только тогда, когда оба высказывания принимают одинаковые значения истинности.

Под формулой в логике высказываний будем понимать:

- любое конкретное или любое переменное высказывание

- если а и b формулы, то формулами также являются

;

- других формул, кроме указанных выше, нет.

Под таблицей истинности будем понимать перечень всех логических возможностей формулы с указанием значений истинности самой формулы в каждой логической возможности.

a	b

Запишем определения логических операций в виде таблицы истинности:

а

 

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

Для любых формул A, B, C справедливы следующие равносильности:

1. Коммутативность.

а) A B º B A (для конъюнкции); б) A Ú B º B Ú A (для дизъюнкции).

2. Ассоциативность.

а) A (B C) º (A C) C (для конъюнкции);

б) A Ú (B Ú C) º (A Ú B) Ú C (для дизъюнкции).

3. Дистрибутивность.

а) A (B Ú C) º A B Ú A C (для конъюнкции относительно дизъюнкции);

б) A Ú(B C) º (A Ú B) (A Ú C) (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) º Ú (отрицание конъюнкции – дизъюнкция отрицаний);

б) º (отрицание дизъюнкции – конъюнкция отрицаний).

5. Идемпотентность.

а) A A º A (для конъюнкции); б) A Ú A º A (для дизъюнкции).

6. Поглощение.

а) A (A Ú B) º A (1– ый закон поглощения);

б) A Ú A B º A (2– ой закон поглощения).

7. Расщепление (склеивание).

а) A B Ú A () º A (1–ый закон расщепления);

б) (A Ú B) (A Ú º A (2–ой закон расщепления).

8. Двойное отрицание.

º A.

9. Свойства констант.

а) A 1 º A; б) A 0 º 0; в) A Ú1 º 1; г) A Ú 0 º A; д) º 1; е) º 0.

10. Закон противоречия.

A º 0.

11. Закон “исключенного третьего”.

A Ú º 1.

12. A B º Ú B.

13. A ~ B º (A B) (B A) º (A B) Ú ( .

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа «º».

Пример: