Логические операции над высказываниями

Наполним смыслом введенную выше символику. Будем называть высказыванием всякое повествовательное предложение, о содержании которого известно, истинно оно или ложно.

 

Отрицанием ┐P высказывания P называется новое высказывание, которое истинно тогда и только тогда, когда P ложно («не P»).

P	┐P
И	Л
Л	И

Операцией перехода от P к ┐P называется операция отрицания.

 

Дизъюнкцией P\/Q (“P или Q”) называется новое высказывание, которое истинно тогда и только тогда когда истинно хотя бы одно из высказываний. Переход от P и Q к их дизъюнкции называется операцией дизъюнкции.

P	Q	P\/Q
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

 

 

Конъюнкция P/\Q (“P и Q ”) приводит к новому высказыванию, которое истинно тогда и только тогда, когда истинно и P и Q. Операция конъюнкции есть операция перехода от P и Q к новому высказыванию P/\Q.

P	Q	P/\Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

 

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

а) Импликация P и Q строится как новое высказывание P→ Q, которое ложно лишь в том случае когда P – истина, а Q – ложь. (“из P следует Q”).

P	Q	P→Q
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

 

 

б) Эквиваленция порождает новое высказывание

P	Q	P↔Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

 

Истина тогда и только тогда, когда оба высказывания имеют одинаковый характер истинности.

 

в) Альтернативная дизъюнкция. (“или, или”).

P	Q	P∆Q
И	И	Л
И	Л	И
Л	И	И
Л	Л	Л

 

Функции истинности.

1) Множество всех высказываний с введенными в нем результатами логических операций называют алгеброй высказываний (АВ).

 

2) На АВ вводится функция истинности λ, которая каждому высказыванию А сопоставляет значение

λ(А)= 1, если А - истинно,

0, если А - ложно.

В терминах значений функции истинности все таблицы истинности могут быть записаны как матрицы, состоящие из единиц и нулей, например:

λ (А)	λ (В)	Λ(А\/В)

 

Классификация формул алгебры высказываний.

1) Если для данной формулы f λ(f)≡1, то формула f называется тождественно-истинной или тавтологией. Обозначение: ├f.

Пример: x\/┐x.

Формула, не являющаяся тавтологией, называется опровержимой, то есть для опровержения формулы найдется такой набор переменных, что λ(f)=0.

Пример: x\/x.

 

2) Формула f называется тождественно-ложной, если λ(f)≡0. Еще ее называют противоречие.

Пример: x/\┐x

Формула, не являющаяся тождественной ложью, называется выполнимой, то есть выполнение формулы F означает, что λ(F)=1.

Класс формул выполнимых шире класса тавтологий.

 

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

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

Примерами Булевых алгебр являются алгебра высказываний (АВ) и алгебра множеств.

Равносильные формулы.

 

1) Говорят что F₁≡ F₂ (равносильны), если λ(F₁)≡λ(F₂). Другими словами равносильные формулы на каждом наборе переменных принимают значение истины или лжи одновременно.

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

 

2) Свойства отношения равносильности:

а) рефлексивность: F≡ F.

б) симметричность: если F₁≡ F₂ , то F₂≡ F₁.

в) транзитивность: если F₁≡ F₂, F₂≡ F₃, то F₁≡ F₃.

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

Основные равносильности алгебры высказываний

1) Имеют место такие равносильности:

1) (F→G) ≡ (┐F\/G);

2) (F↔G) ≡ ((F→G) /\ (G→F));

3) (F∆G)≡ ┐(F↔G);

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

λ(F)	λ(G)	λ(F→G)	λ(┐F)	λ(┐F\/G)

Таблица показывает, что λ(F→G) ≡ λ(┐F\/G), а это и есть справедливость соотношения (1)

 

2) Законы Де-Моргана.

1) ┐(F/\G) ≡ ┐ F \/ ┐ G;

2) ┐(F \/ G) ≡ ┐ F/\ ┐ G.

Доказательство приводится, как и в предыдущем пункте, на основе таблиц истинности.

 

3) Основные равносильности АВ.

1. Закон двойственного отрицания: ┐┐F≡F;

2. Коммутативность(переместительный закон): P\/Q≡Q\/P; P/\Q≡Q/\P;

3. Ассоциативность(сочетательный закон): (P\/Q)\/F≡P\/(Q\/F); (P/\Q)/\F≡P/\(Q/\F);

4. Дистрибутивность: (P\/Q)/\F≡(P/\F)\/(Q/\F); (P/\Q)\/F≡(P\/F)/\(Q\/F);

5. F/\F≡F, F\/F≡F.

(x\/E)≡E

(x/\Е)≡x

(x\/Ø) ≡x

(x/\Ø) ≡Ø

Правило получения тавтологий

 

Правило получения новых тавтологий.

1. Правило подстановки.

Если в имеющуюся тавтологию F (|–F) вместо любой пропозиционной переменной написать произвольную формулу, то в результате получится новая тавтология, то есть если на |–F(…,x_j,…), то |–F(…,U(y₁,…,y_n),…).

В самом деле, значение истинности формулы U возможно одно из двух: истинно, ложно, как это было для пропозиционной переменной j-тое, но в этих обоих случаях формула F сохраняет по условию значение истины.

2. Если |–U и |–(U→V), то |–V. Правило заключения.

Предположим противное: λ(V) ≡0, тогда как согласно условию λ(U) ≡1, λ(U→V) ≡1. Но если U всегда принимает значение истины, то импликация не может быть истиной для ложного V, то есть мы вступили в противоречие с условием, а тогда должно быть λ(V) ≡1, то есть должно быть истинным, что и утверждалось.

 

Критерий равносильности

1) Теорема: F≡G тогда и только тогда, когда |–(F↔G)

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