Высказывания и операции над ними. Формулы

Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно.

Например, утверждение " 2 > 0" является высказыванием и оно истинно, а утверждение " 2 < 0" - ложно, утверждение " x² + y² = z²" высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением. Условимся, значение истинности высказывания обозначать 1, если высказывание истинно, и 0, если высказывание ложно, что в точности соответствует значениям переменных булевых функций.

Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A₁, A₂, .... Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний.

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

Обозначим через B = {0, 1} – множество высказываний. Определим операции на множестве B.

Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (Ø А) и является унарной операцией.

Пусть А и В - некоторые высказывания, введем бинарные операции над ними.

Конъюнкцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда истинны оба высказывания A и B. Обозначается конъюнкция - A B (А& В).

Дизъюнкцией высказываний A и B называется высказывание, которое принимает значение истина, если истинно хотя бы одно из высказываний A или B. Обозначается дизъюнкция - A B.

Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается А®В.

Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - А~В (Аº В).

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

 

A	B	Ø A	AÙ B	AÚ B	A®B	A~B

Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X₁, X₂, ..., X_n.

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

1) логические константы 0 и 1;

2) пропозициональные переменные;

3) если А и В – формулы, то каждое из выражений Ø ( А), ( А) Ù ( В ), ( А) Ú ( В ), ( А) ® ( В ), ( А) ~ ( В ) есть формула;

4) других формул, кроме построенных по пп. 1) - 3), нет.

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

Для формулы построенной по п. 3 формулы A и B называются подформулами. Число скобок в формуле можно сократить, Порядок выполнения операций в формуле определяется их приоритетом. Список логических операций в порядке убывания приоритета: ~. Изменение порядка выполнения операций, как и в алгебраических операциях, производится с помощью круглых скобок.

Пусть U – формула над высказывательными переменными X₁, X₂, ..., X_n, обозначается U (X₁, X₂, ..., X_n). Набор конкретных значений высказывательных переменных X₁, X₂, ..., X_n называется интерпретацией формулы U и обозначаетсяI( U ).

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение 1 (существует интерпритация I( U ), на которой формула истинна).

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение 0 (существует интерпритация I( U ), на которой формула ложна).

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных (формула истинна на всех интерпретациях).

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных (формула ложна на всех интерпретациях).

Формулы А и В называются эквивалентными (обозначается А º В ), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В.

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

2. Следование, эквивалентность и преобразование формул

Введем на множестве M отношения следования и эквивалентности.

Формула B следует из формулы A (обозначается A B ), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A.

Теорема 2.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула A B.

Доказательство. Пусть формула B следует из формулы A. Импликация A B ложна только на тех интерпретациях, на которых формула А истинна, а В ложна, что невозможно в силу условия.

Покажем обратное. Пусть A B – тождественно истинна, тогда если на некоторой интерпретации формула А истинна, то и формула В истинна на ней, что и означает A B.

Формула A эквивалентна формуле B (обозначается A º B ), если они следуют друг из друга, то есть A B и B A. Легко показать, что это определение эквивалентно определению, введенному в п.1.

Теорема 2.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула A ~ B.

Доказательство аналогично доказательству теоремы 2.1.

Приведем список основных тавтологий, выражающих свойства логических операций.

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

X Ù Y º Y Ù X, X Ú Y º YÚ X.

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

(X Ù Y)Ù Z º X Ù (YÙ Z), (XÚ Y)Ú Z º XÚ (YÚ Z).

3. Идемпотентность:

XÙ X º X, XÚ X º X.

4. Законы поглощения:

XÚ (X Y) º X, X (XÚ Y) º X.

5. Взаимная дистрибутивность конъюнкции и дизъюнкции:

X Ù (YÚ Z) º (X Ù Y)Ú (X Ù Z), XÚ (YÙ Z) º (XÚ Y)Ù (XÚ Z).

6. Свойства констант:

XÙ 0 º Л, XÙ 1 º X,

XÚ 0 º X, XÚ 1 º 1.

7. Законы де Моргана:

, .

8. Инволютивность:

.

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

º 0.

10. Закон исключенного третьего:

º 1.

Эквивалентность большинства из этих формул непосредственно следует из определения операций или проверяется построением таблиц истинности.

Пусть U – некоторая формула, в которую входит переменная X или подформула А, что обозначается U (¼, X, ¼ ) или U (¼, А, ¼ ). Пусть В – некоторая формула. Запись U (¼, X, ¼ ){ В //X} обозначает формулу, полученную из формулы U подстановкой формулы В вместо всех вхождений переменной X, а U (¼, А, ¼ ){ В / А } – формулу, полученную из формулы U подстановкой формулы В вместо некоторых (в частности, вместо одного) вхождений подформулы А.

Теорема 2.3 (правило подстановки). Если U (¼, X, ¼ ) – тавтология и В – любая формула, то U (¼, X, ¼ ){ В //X} – тавтология.

Теорема 2.4 (правило замены). Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если U (¼, А, ¼ ) и A º B, то U º V = U (¼, А, ¼ ){ В / А }.

Например, так как A®B º , то (A®B)Ù C º ( )Ù C.

Следствие. Если U~A и V~B, то:

1) U V º A B;

2) U V º A B;

3) U V º A B;

4) ( U ~ V ) º ( A ~ B );

5) U º A.

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

Примеры.

1. Докажем 1-й из законов поглощения XÚ (X Y) º X.

.

При доказательстве использовано правило замены.

2. Упростить формулу .

Так как º X в силу подстановки в закон поглощения, тогда, используя правило замены получим

º .

Приведем еще несколько эквивалентностей, имеющих широкое применение.

11. .

12. .

13. Законы склеивания

, .

Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [ U ].

Определение. Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным.

Теорема 2.5. Каждый класс эквивалентности [ U ] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V.

Доказательство теоремы проведём конструктивно, то есть определим порядок построения приведенной формулы.

1. Удаляются операции импликация и эквиваленция по формулам 11, 12.

2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.

3. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.

Таким образом, проверить эквивалентность формул, тождественную истинность и ложность формулы или упростить ее можно с помощью этого алгоритма.

Приведенная формула для данного класса эквивалентности не является единственной.

Задание. Упростить формулу .

Решение. º

º º º A.

Определение. Формула U^d называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот.

Теорема 2.6 (принцип двойственности). Пусть U ( ) – приведенная формула, тогда

U^d ( ) = U( ).

Доказательство. Число логических операций в формуле U называется рангом формулы и обозначается r( U ).Проведем доказательство индукцией по k = r( U ).

1⁰. k = 0. В этом случае U = X_i, следовательно, U^d = X_i º º Ø U ( ).

2 ⁰. Предположим, что теорема верна при k £ m.

3 ⁰. Покажем, что она верна при k = m + 1.

Пусть U₁ и U₂ – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна.

Возможны следующие случаи

а) U = Ø U₁;

б) U = U₁ Ù U₂;

в) U = U₁ Ú U₂.

Случай а) эквивалентен условию 1⁰ и при нем теорема верна. В случаях б) и в) заменим в каждой из U_i конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): U^d = U Ú U и в): U^d = U Ù U .

В силу законов де Моргана и предположения индукции будем иметь в случае б):

U^d = U Ú U = (Ø U₁ ( )) Ú (Ø U₂ ( )) º

º Ø ( U₁ ( ) Ù U₂ ( )) = Ø U ( ).

В случае в) выкладки аналогичны. Теорема доказана.

Следствие. Если U – ТИ-формула, то U^d – ТЛ-формула.

Теорема 2.7. Если U º V, то U^d º V^d.

Доказательство. Если U º V, то (Ø U ) º (Ø V ). Значит, в силу теоремы 2.6, U^d (Х₁, …, Х_n) = Ø U ( ) и V^d (Х₁, …, Х_n) = Ø V ( ).

Отсюда: U^d = (Ø U ( )) º (Ø V ( )) = Ø V^d. В силу транзитивности эквиваленции, получим U^d º V^d , что и требовалось доказать.

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

Поделиться: