Математическая логика

    И, наконец, в седьмом столбике записываем результат выполнения итоговой операции эквиваленции . При этом используем результаты предыдущей операции и операции (шестой и пятый столбики):

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

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

    В логике говорят, что два предложения  равносильны, если они одновременно истинны, либо одновременно ложны. Слово  «одновременно» в этой фразе неоднозначно. Так, для предложений «Завтра будет вторник» и «Вчера было воскресенье» это слово имеет буквальный смысл: в понедельник они оба истинны, а в остальные дни недели – оба ложны. Для уравнений «х = 2» и «2х = 4» «одновременно» означает «при одних и тех же значениях переменной». Прогнозы «Завтра будет дождь» и «Неверно, что завтра не будет дождя» одновременно подтвердятся (окажутся истинными) либо не подтвердятся (окажутся ложными). В сущности, это один и тот же прогноз, выраженный в двух разных формах, которые можно представить формулами Х и . Эти формулы одновременно принимают значение «истина» либо значение «ложь». Для проверки достаточно составить таблицу истинности:

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

    Формулы F₁ и F₂ называются равносильными, если их эквиваленция – тавтология.

    Равносильность двух формул записывается так: (читается: формула F₁ равносильна формуле F₂).

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

    Пример. Выяснить, являются ли формулы равносильными:

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

    I. - закон тождества (утверждает, что мысль, заключенная в некотором высказывании, остается (считается) неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует).

    II. - закон противоречия (никакое предложение не может быть истинным одновременно со своим отрицанием).

    III. - закон исключенного третьего (закон альтернативы).

    IV. - закон двойного отрицания.

    V. ; - законы тождества (или идемпотентности (на латинском языке «idem» означает «то же», а «potentia» - «сила»)).

    VI. ; - законы коммутативности (переместительности).

    VI. ; - законы ассоциативности (сочетательности).

    VII. ; - законы дистрибутивности (распределительности).

    VIII ; - законы де Моргана (английский логик, 1806-1871).

    Законы  логики используются для упрощения  сложных формул и для доказательства тождественной истинности или ложности формул. 

Контрольные вопросы: 

1. Дайте определение  высказывания и высказывательной формы.
2. Перечислите основные логические связки.
3. Дайте определение логической операции.
4. Дайте определение негации, конъюнкции, дизъюнкции, импликации и эквиваленции.
5. Какие переменные называются пропозициональными?
6. Сформулируйте определение формулы логики высказываний.
7. Опишите процедуру формализации высказываний.
8. Для чего нужна таблица истинности?
9. Опишите алгоритм составления таблицы истинности.
10. Какие формулы называются тавтологиями, противоречиями, выполнимыми (опровержимыми)?
11. Какие формулы называются равносильными?
12. Сформулируйте несколько основных законов логики.
13. Для чего нужны законы логики?