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


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

 

Отрицанием ┐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) Говорят что F1≡ F2 (равносильны), если λ(F1)≡λ(F2). Другими словами равносильные формулы на каждом наборе переменных принимают значение истины или лжи одновременно.

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

 

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

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

б) симметричность: если F1≡ F2 , то F2≡ F1.

в) транзитивность: если F1≡ F2, F2≡ F3, то F1≡ F3.

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

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

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(…,xj,…), то |–F(…,U(y1,…,yn),…).

В самом деле, значение истинности формулы 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, а это как раз означает их равносильность

 









Последнее изменение этой страницы: 2016-04-19; Нарушение авторского права страницы

infopedia.su не принадлежат авторские права, размещенных материалов. Все права принадлежать их авторам. Обратная связь