Формулы логики высказываний, их свойства

Если переходить к сравнениям, то элементарные высказывания в логике высказывания рассматриваются как не расчленяемые «атомы», а составные высказывания — как «молекулы'', образованные из «атомов» применением к ним логических операций. Логика высказываний интересуется единственным свойством элементарных высказываний их значением истинности, составные же высказывания изучаются ею со стороны их структуры, отражающей способ, которым они образованы. Структура составных высказываний определяет зависимость их значений истинности от значений истинности составляющих элементарных высказываний.

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

Существуют правила построения формул логики высказываний /5/:

• 1. Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
• 2. Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи ((Ф1)), ((Ф1)(Ф2)), ((Ф1)(Ф2)), ((Ф1)>(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2, к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

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

Например, высказывание: «Если 20 делится на 2 и на 5, то 20 делится на 10», формализуется в виде (А ^ B) > C. Такая же формула соответствует предложению: «если в четырехугольнике две противоположные стороны равны и параллельны, то этот четырехугольник — параллелограмм «.

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

• 1) А, В, С и т. д. — символы для обозначения высказываний;
• 2) 1 и 0 — символы, обозначающие логические константы «истина», «ложь»;

• 3) — символы, логические операции;
• 4) (,) — скобки, вспомогательные символы, служащие для указания порядка выполнения операций.

Формула алгебры высказываний принимает одно из двух значений (0 или 1) в зависимости от простых высказываний и от связи между ними.

Истинность или ложность высказывания мы будем задавать таблицей истинности.

Составление истинностных таблиц происходит по следующему правилу:

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

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

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

Пример 1:

Пример 2: Вычислить значение функции:

при.

• 1)
• 2)
• 3)
• 4)
• 5)

Две формулы, А и В будем называть равносильными (А=В или), если они имеют одинаковые таблицы истинности. Будем считать две таблицы истинности одинаковыми, если у них одинаковые последние (результирующие) столбцы.

Пример:

В логике высказываний будем считать, что равносильные формулы задают одно и то же высказывание. Может оказаться, что в последнем столбце таблицы истинности стоят одни единицы или нули. Будем называть такое высказывание тождественно-истинным (тавтологией) соответственно тождественно-ложным (противоречием) и обозначать 1 и 0. Из определения следует, что для проверки равносильности формул нужно построить их таблицы истинности и сравнить Пример:

Формулы и являются тождественно-истинными: