1.      Алгебра высказываний как модель алгебры Буля, ее аксиоматическое задание. Принцип двойственности и теорема двойственности.

Алгебра высказываний как модель алгебры Буля, её аксиоматическое задание. Принцип двойственности и теорема двойственности.

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

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

Операции над высказываниями:

1. Операция конъюнкции ( /\ ).

Конъюнкцией двух высказываний, А и В, называется новое высказывание, обозначаемое (A /\ B), которое истинно тогда и только тогда, когда высказывания A и B истинны одновременно, и ложно во всех остальных случаях. Конъюнкции соответствует логическая связка "и". Запись (A /\ B) читается: A и B; A конъюнкция B.

2. Операция дизъюнкции ( \/ ).

Дизъюнкцией двух высказываний, А и В, называется новое высказывание, обозначаемое (A \/ B), которое истинно только тогда, когда истинно, по крайней мере, одно из высказываний, A или B, и ложно в единственном случае, когда оба высказывания, А и В, ложны. Дизъюнкции соответствует связка "или". Запись (A \/ B) читается: A или B; A дизъюнкция B.

3. Операция следования или импликации ( → )

Импликацией (следованием) двух высказываний, А и В, называется новое высказывание, обозначаемое (A → B), которое ложно тогда и только тогда, когда A - истинно, а B - ложно, во всех остальных случаях высказывание (A→B) истинно.

В высказывании (A → B) A - называется посылкой или антецедентом, B - следствием или консеквентом.

Импликация (A → B) в разговорной речи имеет несколько разночтений: если A, то B;из A следует B;A влечет B;B следует из A;A достаточно для B;B необходимо для A.

4. Операция эквивалентности ( ↔ )

Эквивалентностью двух высказываний, A и B, называется новое высказывание, обозначаемое (A ↔ B), которое имеет значение ложь тогда и только тогда, когда A - истинно, а B - ложно или A - ложно, а B - истинно. А значение истина тогда и только тогда, когда одновременно оба высказывания, A и B, либо истинны, либо ложны.

Эквивалентность (A ↔ B) в разговорной речи имеет несколько разночтений: A необходимо и достаточно для B; A тогда и только тогда, когда B; A эквивалентно B; A равносильно B; из A следует B , а из B следует A.

5. Операция отрицания ( ¬ )Отрицанием высказывания A называется новое высказывание, обозначаемое ¬A, которое истинно тогда и только тогда, когда ложно A, и ложно тогда и только тогда, когда A истинно.

Отрицанию соответствует логическая связка "не". Запись ¬A читается: не А; неверно, что А.

 Таблица истинности основных операций

А	B	А /\ В	А \/ В	А→В	А↔В	¬A
И	И	И	И	И	И	Л
Л	И	Л	И	И	Л	И
И	Л	Л	И	Л	Л	Л
Л	Л	Л	Л	И	И	И

     

Алгеброй Буля называется непустое множество, содержащее, по крайней мере, два элемента и замкнутое относительно 2-ух бинарных операций: /\ и \/, удовлетворяющих законам: коммутативности (1), ассоциативности (2), дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции (3), идемпотентности (4), сокращения (5), поглощения (6), противоречия для конъюнкции и исключения третьего для дизъюнкции (7), законам де Моргана (8) и закону двойного отрицания (9).

1.   x +  y = y + x

 x *  y = y * x

2.    x + ( y + z ) = (x + y) + z  

      x * ( y * z ) = (x * y) * z

3.   (x + y) * z  = (x * z) + (y * z)  

      (x * y) + z  = (x + z) * (y + z)  

4.      x * x = x

         x + x =x

5.    x * И = x

        x + Л  = x

6.     x * Л = Л

        x + И = И

              _

7.     x * x  = Л

               _

        x + x = И

8.  

      

9.  

10. x * (y + x) = x

      x + (y * x) = x

Алгебра высказываний <V; /\, \/, ¬>  является примером алгебры Буля.

Алгебра высказываний <V; /\, \/, ¬>   - это непустое множество, где заданы бинарные операции : «и», «или», «не», имеется хотя бы одна константа u Î V(множеству атомарных высказываний)  и выполняются тождества (1-10).

Двойственность

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

Формулы α и α* называются двойственными, если одна из них получается из другой заменой констант "И" и "Л" на двойственные им константы "Л" и "И" соответственно, и каждой операции /\ на двойственную ей операцию \/ , а \/ - на операцию /\.

Теорема 1.Если α(X1, X2, ..., Xn) и α*(X1, X2, ..., Xn) двойственные формулы, то отрицание формулы α(X1, X2, ..., Xn) равносильно формуле, полученной из α*( X1, X2, ..., Xn) с помощью замены всех переменных на их отрицание, т.е. ¬α(X1, X2, ..., Xn) ≡ α*(¬X1, ¬X2, ..., ¬Xn).

Теорема двойственности (закон двойственности) (Теорема 2)

Если формулы β(X1, X2, ..., Xn).и α(X1, X2, ..., Xn) равносильны, то двойственные им формулы β*( X1, X2, ..., Xn).и α*( X1, X2, ..., Xn) тоже равносильны.

β(X1, X2, ..., Xn). ≡ α(X1, X2, ..., Xn)

β*(X1, X2, ..., Xn). ≡ α*( X1, X2, ..., Xn)

Доказательство.

По условию доказываемой теоремы:

β(X1, X2, ..., Xn). ≡ α(X1, X2, ..., Xn) (1).

По условию теоремы 1: β*(¬X1, ¬X2, ..., ¬Xn) ≡ ¬β(X1, X2, ..., Xn), откуда

β*(¬(¬X1), ¬(¬X2), ..., ¬(¬Xn)) ≡ ¬β(¬X1, ¬X2, ..., ¬Xn), следовательно

β*(X1, X2, ..., Xn) ≡ ¬β(¬X1, ¬X2, ..., ¬Xn)  (2).

Аналогично, α*(X1, X2, ..., Xn) ≡ ¬α(¬X1, ¬X2, ..., ¬Xn)  (3).

Из (1) следует, что ¬β(X1, X2, ..., Xn). ≡ ¬α(X1, X2, ..., Xn), откуда

¬β(¬X1, ¬X2, ..., ¬Xn). ≡ ¬α(¬X1, ¬X2, ..., ¬Xn)  (4). По свойству равносильности [β*(X1, X2, ..., Xn) и α*(X1, X2, ..., Xn) равносильны соответственно выражениям ¬β(¬X1, ¬X2, ..., ¬Xn).и ¬α(¬X1, ¬X2, ..., ¬Xn), которые являются равносильными] β*(x1, x2, ..., xn). ≡ α*(x1, x2, ..., xn), что и требовалось доказать.

Закон двойственности "наполовину уменьшает работу математикам": если уже доказана некоторая равносильность, то справедливость другой, полученной из первой двойственными преобразованиями, уже не нужно доказывать, она будет выполняться.