Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Определение 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) º Ø AB (отрицание конъюнкции есть дизъюнкция отрицаний);

б) Ø (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) & (AB) º A (2–ой закон расщепления).

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

Ø (Ø A) º A.

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

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

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

A& Ø A º Л.

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

AA º И.

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

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

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

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

14. (A1VA2V...VAn)& (B1VB2V...VBm) º

A1& B1VA1& B2V...VA1& BmV...VAn& B1VAn& B2V...VAn& Bm.

15. (A1& A2&...& An)V(B1& B2&...& Bm) º

(A1VB1)& (A1VB2)&...& (A1VBm)&...& (AnVB1)& (AnVB2)&...& (AnVBm).

16. Ø (A1& A2&...& An) º Ø A1A2V...VØ An.

17. Ø (A1VA2V...VAn) º Ø A1& Ø A2&...& Ø An

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

Пример 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) º (АC)& (АV Ø А) & (Ø BC) & (Ø BА) V (CVB) º (АC)& (Ø BC)& (Ø BА)V(CVB) º (АCVCVB)& (Ø BCVCVB)& (Ø BА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) º И.

 


Поделиться:



Последнее изменение этой страницы: 2017-03-14; Просмотров: 1345; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.04 с.)
Главная | Случайная страница | Обратная связь