кр одмита

5.1 Алгебра высказываний

Высказывание – некоторое утверждение, относительно которого нас интересует только его истинность или ложность.

Высказывание называют простым (элементарным), если его истинность не зависит от истинности других высказываний. Высказывание называют сложным (составным), если оно зависит от истинности других высказываний.

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

Определяются эти операции таблицами истинности. Например, операции «дизъюнкция» соответствует сложное высказывание, которое ложно тогда и только тогда, когдаA ложно и B ложно

A	B	A\/B
Л	Л	Л
Л	И	И
И	Л	И
И	И	И

В дальнейшем каждое простое высказывание можно связать с некоторой двоичной переменной.

Поэтому сложное высказывание можно связать с некоторой двоичной (логической) функцией.

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

Запишем таблицу истинности операций алгебры высказываний:

A	B	A\/B	A/\B	AB	A↔B	A B
0	0	0	0	1	1	0
0	1	1	0	1	0	1
1	0	1	0	0	0	1
1	1	1	1	1	1	0

Любое сложное высказывание можно представить в виде некоторой формулы. Дадим определение формулы:

Каждый символ a, b, c… есть формула;
Если А и В – формулы, то формулами являются А*В, А\/В, где * - любая операция из других формул нет.

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

Вычисление по формуле продемонстрируем на следующем примере:

a	b	c	ab	(ab)c				F
0	0	0	0	0	1	1	1	1
0	0	1	0	0	1	1	1	1
0	1	0	1	0	1	1	1	1
0	1	1	1	1	0	1	1	1
1	0	0	1	0	1	0	0	0
1	0	1	1	1	0	0	0	1
1	1	0	0	0	1	0	0	0
1	1	1	0	0	1	0	1	1

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

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

Установить тип формулы можно с помощью таблиц истинности. При большом числе переменных x_i (при большом числе простых высказываний) таблицы истинности f(x₁,…,x_n) функций, соответствующих этим формулам, очень громоздки. Установить тип формулы (выполнима, тавтология, противоречие) удобно с помощью нормальных форм. Для каждой формулы алгебры высказываний можно найти множества КНФ и ДНФ.

Для этого нужно:

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

А →С=C, А С=АС

Заменить знак отрицания относящийся ко всему выражению на знаки относящиеся к отдельным переменным (используя закон де Моргана).

Избавиться от знаков двойного отрицания. = А
Применить, если нужно, закон дистрибутивности и формулы поглощения. AAВ = A, A(AС) = A

Пример: Пусть S = (А →С)↔( →). Построим КНФ для этой формулы.

1) Избавимся от знаков импликации, получим (C)↔().

2) Учитывая, что = А , имеем: S = (С)↔(A) .

3) Избавимся от знака двойной импликации:

S = (((A))((C)).

4) Применим закон де Моргана: = ; =.

Получим S =(C(A))((C) ).

5) Избавимся от двойных отрицаний = А, = В в формуле S. Учитывая закон ассоциативности операции дизъюнкции внутренние скобки опустим:

S = (AA)(CB).

6) Применим формулу поглощения: AA = A; B = Получим S = (A)(C).

Получили КНФ для исходной формулы.

Теорема 1: формула алгебры высказываний является тождественно истинной, когда каждый множитель её КНФ содержит пару слагаемых, одно из которых является элементарным высказыванием, а другое его отрицанием.

Теорема 2: формула алгебры высказываний является тождественно ложной, когда каждый множитель её ДНФ содержит пару сомножителей, один из которых является элементарным высказыванием, а другое его отрицанием.

Между формулами можно установить отношение формально импликации (=>). Формулы А и В находятся в отношении формальной импликации, точнее А имплицируем В (А=>В), если формула В истинна на всех наборах переменных, на которых истинна формула А. В таких случаях говорим, что формула В логически следует из формулы А.

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

Рассмотрим основные тавтологии использования высказываний.

1.Закон тождествия:

Содержание