Формулы логики высказываний. Равносильность формул

Определение 1.2. Формула логики высказываний определяется индуктивно следующим образом:

1. Любая высказывательная переменная, а также константы И, Л есть формула.

2. Если A и B – формулы, то Ø А, AVB, A& B, АÉ B, А~B есть формулы.

3. Ничто, кроме указанного в пунктах 1 – 2, не есть формула.

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

Равносильность формул A и B будем обозначать следующтм образом: A º B.

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

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

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

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

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

б) AVB º BVA (для дизъюнкции).

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

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

б) AV(BVC) º (AVB)VC (для дизъюнкции).

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

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

б) AV(B& C) º (AVB)& (AVC) (для дизъюнкции относительно конъюнкции).

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

а) Ø (A& B) º Ø AVØ B (отрицание конъюнкции есть дизъюнкция отрицаний);

б) Ø (AVB) º Ø A& Ø B (отрицание дизъюнкции есть конъюнкция отрицаний).

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

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

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

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

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

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

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

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

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

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

Ø (Ø A) º A.

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

а)A& И º A; б) A& Л º Л; в)AVИ º И; г) AV0 º A; д) Ø Л º И; е) Ø È º Л.

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

A& Ø A º Л.

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

AVØ A º И.

12. AÉ B º Ø AVB º Ø (A& Ø B).

13. A~B º (AÉ B)& (BÉ A) º (A& B) V (Ø A& Ø B) º (АVØ B)& (Ø AVB).

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

Справедливы также обобщенные законы дистрибутивности и обобщенные законы де Моргана:

14. (A₁VA₂V...VA_n)& (B₁VB₂V...VB_m) º

A₁& B₁VA₁& B₂V...VA₁& B_mV...VA_n& B₁VA_n& B₂V...VA_n& B_m.

15. (A₁& A₂&...& A_n)V(B₁& B₂&...& B_m) º

(A₁VB₁)& (A₁VB₂)&...& (A₁VB_m)&...& (A_nVB₁)& (A_nVB₂)&...& (A_nVB_m).

16. Ø (A₁& A₂&...& A_n) º Ø A₁VØ A₂V...VØ A_n.

17. Ø (A₁VA₂V...VA_n) º Ø A₁& Ø A₂&...& Ø A_n

В равносильностях 1 – 17 в качестве A, B, A_i, B_i могут быть подставлены любые формулы и, в частности, переменные.

Пример 1.9.

Доказать равносильность формул логики высказываний:

(АÉ B) & (A V B) º B.

Преобразуем левую часть, последовательно используя равносильности 12, 14, 10, 5а, 9г, 6б:

(АÉ B) & (A V B) º (Ø А V B) & (A V B) º Ø А & A V Ø А & B V B & А V B & B º Ø А & B V B & А V B º B.

Равносильность доказана.

 

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

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

Пример 1.10.

Рассмотрим простые высказывания:.

A = " Будет холодное лето".

B = " Будет дождливое лето".

C = " Будет засушливое лето".

D = " Будет хороший урожай".

Формула (A& B V C) É Ø D соответствует сложному высказыванию:

''Если будет холодное и дождливое или засушливое лето, урожай будет плохим".

Язык логики высказываний удобен для записи математических утверждений. Всякая теорема имеет вид импликации: А É B (прямая теорема); B É А (обратная теорема); Ø B É Ø А (противоположная теорема).

Пример 1.11.

A = “Треугольник прямоугольный”.

B = “Квадрат одной стороны равен сумме квадратов двух других сторон”

А É B (прямая теорема) = “Если треугольник прямоугольный, то квадрат одной стороны равен сумме квадратов двух других сторон”.

B É А (обратная теорема) = “Если квадрат одной стороны равен сумме квадратов двух других сторон, то треугольник прямоугольный”.

Ø B É Ø А (противоположная теорема) = “Если квадрат одной стороны не равен сумме квадратов двух других сторон, то треугольник не прямоугольный”.

В данном случае все три теоремы верны.

Равносильность А É B º Ø B É Ø А есть основание метода доказательства от противного. Например, для доказательства теоремы: “Если треугольник равнобедренный, то углы при основании равны” (А É B) достаточно доказать теорему: “Если углы при основании не равны, то треугольник не равнобедренный” (Ø B É Ø А).

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

Пример 1.12.

Дано высказывание “Если политик обещает невыполнимое, то он обманывает людей”:

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

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

Введем следующие высказывания:

A = ”Политик обещает невыполнимое”.

B = “Политик обманывает людей”.

Данное нам высказывание может быть записано в виде формулы: АÉ B.

Построим отрицание высказывания, воспользовавшись равносильностью 12:

Ø (АÉ B) º A& Ø B.

На естественном языке это может быть выражено следующим образом:

“Политик обещает невыполнимое, но он не обманывает людей”.

 

Тождественно-истинные и тождественно-ложные формулы. Проблема

Разрешимости

Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.

Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.

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

Теорема 1.1 . Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в любую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание.

Теорема 1.2 . Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в любую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание.

Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной.

Пример 1.13.

Доказать, что формула F = (А É B) É ((C V А) É (C V B)) является тождественно-истинной.

Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(АÉ B) É ((CVА) É (CVB)) º Ø (АÉ B) V ((CVА) É (CVB)) º (А& Ø B) V Ø (CVА) V (CV B) º (А& Ø B) V (Ø C& Ø А) V (CVB) º (А VØ C)& (АV Ø А) & (Ø BVØ C) & (Ø B VØ А) V (CVB) º (АVØ C)& (Ø BVØ C)& (Ø BVØ А)V(CVB) º (АVØ CVCVB)& (Ø BVØ CVCVB)& (Ø BVØ АVCVB).

В первую дизъюнкцию входят C и Ø C. Во вторую – B и Ø B, C и Ø C. в третью – B и Ø B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.14.

Установить, является ли тождественно-истинной данная формула логики высказываний: f(A, B) = (А& (АÉ B)) É B.

1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А& (АÉ B)) É B º (А& (Ø АVB) É B º Ø (А& (Ø АVB) É B º Ø АVØ (Ø (АVB)VB º Ø АV(А& B)VB º (Ø АVB)VА& Ø B º (Ø АVBVА)& (Ø АVB Ø B).

В первую дизъюнкцию входят A и Ø A. Во вторую – B и Ø B, поэтому формула является тождественно истинной, f(A, B) º И.

2) Составим таблицу истинности f(A, B) (таблица 1.6):

Таблица 1.6

А B	АÉ B	А& (АÉ B)	(А& (АÉ B))É B
Л Л Л И И Л И И	И И Л И	Л Л Л И	И И И И

 

Из таблицы 1.6 видно, что f(A, B) º И.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: