Глава 3.Логика высказываний

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

3.1. Основные понятия

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

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

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

Отрицанием(инверсией) высказыванияPназывается высказывание, истинное тогда и только тогда, когда высказываниеPложно. Обозначается^P.

Конъюнкцией(операцией «И»,логическим произведением) двух высказыванийPи Qназывается высказывание, истинное тогда и только тогда, когда истинны оба высказывания. ОбозначаетсяPQ.

Дизъюнкцией(операцией «ИЛИ»,логической суммой) двух высказываний Pи Qназывается высказывание, ложное тогда и только тогда, когда оба высказывания ложны. ОбозначаетсяPQ.

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

Эквивалентностью (эквиваленцией,равнозначностью) двух высказываний Pи Qназывается высказывание, истинное тогда и только тогда, когда истинностные значенияPиQ совпадают. ОбозначаетсяPQ.

Неравнозначностью (исключающим «ИЛИ»,сложением по модулю 2) двух высказываний Pи Qназывается высказывание, истинное тогда и только тогда, когда истинностные значенияPиQ не совпадают. ОбозначаетсяPQ.

Алфавит логики высказыванийсодержит следующие символы: высказывательные переменные – обычно заглавные латинские буквы; логические символы^,,,,,; символы скобок (, ).

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

1) любая высказывательная переменная – формула;

2) если A и B – формулы, то ^A, AB, AB, AB, AB, AB, (A) – формулы;

3.2. Алгебра логики высказываний

Если каждой высказывательной переменной, входящей в формулу, придавать истинностное значение И и Л, то формула будет определять истинностную функцию, т.е. функцию, определенную на множестве(n– число высказывательных переменных) со значениями в множестве {И, Л}. Если, кроме того, принять И=1, Л=0, то любую формулу логики высказываний можно интерпретировать как формулу логики переключательных функций. По аналогии с переключательными функциями, для любого высказывания можно построить таблицу истинности.

Упорядоченный набор высказывательных переменных <X₁,X₂, ...,X_k> назовемспискомпеременных формулыA, если все переменные формулыAсодержатся в этом наборе. В списке переменных формулыAчасть переменных может быть фиктивной, т.е. может не входить в формулуAявно. Очевидно, что если список переменных для формулыAсодержитkпеременных, то таблица истинности для формулыAбудет содержать 2^kстрок.

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

– тавтология(тождественно-истинная формула– ТИФ);

– выполнимая формула(условно-истинная формула– УИФ);

– опровержимая формула (условно-ложная формула – УЛФ);

– невыполнимая формула (тождественно-ложная формула – ТЛФ).

Алгебра логики позволяет легко проверять правильность рассуждений, состоящих из высказываний. Для этого надо построить логическую формулу умозаключения следующим образом: все посылки следует соединить связкой «и» (), и полученную обобщенную посылку – связкой «если …, то…» (). Если логическая формула умозаключения – ТИФ, то заключение верно, в противном случае неверно. Например, еслиP₁,P₂, ...,P_n– посылки, аD– заключение, то для определения правильности рассуждения по схеме, т.е. утверждения о том, что из данных посылок P₁,P₂, ...,P_nследует заключение D, требуется установить тождественную истинность формулы (P₁P₂...P_n)D.