Основные понятия и определения алгебры высказываний. Двойственность

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «Основные понятия и определения алгебры
высказываний. Двойственность»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2. ФИКСАЦИЯ ЗНАЧЕНИЙ В ФОРМУЛЕ

Теорема 1 (о фиксации значений в
формуле)
Если F(x1, x2,…, xn) – формула алгебры
высказываний, где x1,x2,...,xn– высказывательные
переменные формулы, то при фиксации значений всех
высказывательных переменных (т.е. при подстановке
вместо них высказываний) формула алгебры
высказываний превращается в высказывание. Т.е.
формула
алгебры
высказываний
является
отображением множества наборов значений
высказывательных переменных в высказывания.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
2

3. ПОДСТАНОВКА ФОРМУЛ В ФОРМУЛУ

Пусть
f2(x1,x2,...,xn) ,..., fm(x1,x2,...,xn)
формулы алгебры высказываний.
–
Подстановкой формул fi в формулу F будем
называть следующую конструкцию:
Ф(x1,x2,...,xn)≡F(f2(x1,x2,...,xn),...,fm(x1,x2,...,xn))
т.е. все вхождения заменяются на
fi(x1,x2,...,xn),…, fm(x1,x2,...,xn)
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
3

4. ПОДСТАНОВКА ФОРМУЛ В ФОРМУЛУ

Теорема 2 (теорема
формул в формулу):
о
подстановке
Если F и fi – формулы алгебры высказываний, то и
F(f2(x1,x2,...,xn),...,fm(x1,x2,...,xn)) – формула алгебры
высказываний.
При этом говорят, что она получена из
формулы F подстановкой формул fi вместо её
переменных.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
4

5. РАВНОСИЛЬНОСТЬ ФОРМУЛ

Две формулы алгебры высказываний,
называются равносильными ( ≡ ), если
истинностные значения этих формул
совпадают.
Две
формулы
равносильны,
если
столбцы f1 и f2 их таблиц истинности
совпадают.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
5

6. РАВНОСИЛЬНОСТЬ ФОРМУЛ

Теорема 3 (о равносильной подстановке)
Пусть
тогда
F(f2(x1,x2,...,xn),...,fm(x1,x2,...,xn) ≡ G(g2(x1,x2,...,xn),...,gm(x1,x2,...,xn)
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
6

7. ОПРЕДЕЛЕНИЕ БУЛЕВОЙ ФОРМУЛЫ

Булевы формулы - формулы
алгебры высказываний:
-определенные на
множестве{0,1};
- принимающие значения на
множестве {0,1} .
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
7

8. БУЛЕВА ФОРМУЛА АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Теорема 4
Для
любой
формулы
алгебры
высказываний
существует
равносильная ей булева формула
алгебры высказываний.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
8

9. РАНГ ФОРМУЛЫ

Ранг формулы – число логических операций,
встречающихся в формуле, причём, каждая операция
считается столько раз, сколько встречается.
Пример:
ранг этой формулы 6.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
9

10. БУЛЕВА ФОРМУЛА АЛГЕБРЫ ВЫСКАЗЫВАНИЙ

Доказательство: (индукцией по рангу формулы).
0 шаг (случай формулы нулевого ранга):
rang(f ) = 0. Все формулы ранга 0 – это символы логических
переменных, константы 0 и 1.Все это булевы формулы.
1 шаг (случай формул ранга 1):
Все формулы ранга 1 имеют конструкции:
1) ¬ ▲ ,
3) ▲& ■ ,
5) ▲ ■ ,
2) ▲v ■ ,
4) ▲ ■ ,
где ▲, ■ – формулы нулевого ранга, и значит, булевы формулы.
Тогда 1 – 3 также булевы формулы. Очевидно, в случае 4,5
имеет место:
▲ ■≡ v■
▲ ■≡ ▲■ v
В результате получены булевы формулы.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
10

11. РАВНОСИЛЬНОСТЬ ФОРМУЛ

2 шаг (индуктивный переход):
Пусть rang(f ) = n+1. Выделим в f последнюю операцию,
тогда f имеет одну из следующих конструкций:
1) ¬ ▲ ,
3) ▲& ■ ,
5) ▲ ■ ,
2) ▲v ■ ,
4) ▲ ■ ,
где ▲, ■ – формулы ранга, меньшего или равного n.
Для ▲ и ■ справедливо предположение индукции, т.е. ¬ ▲ ≡ ¬ ▲б
, ■ ≡ ■б , где ▲б и ■б - булевы формулы алгебры высказываний,
тогда
¬ ▲ ≡ ¬ ▲б
▲ v ■ ≡ ▲б v ■б
▲& ■ ≡ ▲б & ■б
▲ ■ ≡ ▲б v ■б
▲ ■ ≡ ▲б■б v
б
б
Так как справа булевы формулы, то индуктивный переход
доказан, а, следовательно, теорема доказана.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
11

12. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Пусть f(x1,x2,...,xn)– формула алгебры
высказываний.
Двойственной к ней будем называть
формулу f*(x1,x2,...,xn), определённую
следующим образом:
Из закона двойного отрицания:
(f*)* ≡ f
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
12

13. ПРИМЕР

Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
13

14. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Теорема 1 (закон двойственности):
Формулы f1(x1,x2,...,xn) и f2(x1,x2,...,xn) равносильны
тогда и только тогда, когда
равносильны двойственные формулы
f1*(x1,x2,...,xn) и f2*(x1,x2,...,xn), т.е.
f1(x1,x2,...,xn) ≡ f2(x1,x2,...,xn)
f1*(x1,x2,...,xn) ≡ f2*(x1,x2,...,xn)
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
14

15. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Для доказательства закона двойственности установим
связь между таблицами истинности формулы и двойственной к
ней.
Столбец значений f* может быть получен из столбца f с
помощью инвертирования, т.е. симметрией относительно
середины и отрицания.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
15

16. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Теорема 2 (общий принцип двойственности):
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
16

17. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Теорема 3 (принцип двойственности для
булевых формул):
Двойственная формула к булевой формуле может
быть получена заменой констант 0 на 1, 1 на 0, &
на v , v на & и сохранением структуры формулы
(т.е. соответствующего порядка действий).
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
17

18. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Доказательство (метод индукции по рангу
формулы):
0 шаг (случай ранга 0)
Формулы 0 ранга это 0,1,x. Мы знаем что
0*≡1, 1*≡0, x*≡x, т.е. утверждение теоремы
выполнено.
1 шаг (случай ранга 1)
Все булевы формулы имеют вид: ¬ ▲, ▲v
■, ▲&■, где ▲, ■ – булевы формулы ранга 0.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
18

19. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
Применим общий принцип двойственности:
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
19

20. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ 

ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ
2 шаг (индуктивный переход):
Пусть rang(f)=n+1.
Выделим в f последнюю операцию, тогда f имеет один
из следующих видов: ¬ ▲, ▲ V ■, ▲&■, где ▲, ■ – булевы
формулы ранга меньшего или равного n, тогда по
предположению индукции ▲* и ■* получаются из ▲ и ■ по
предписанным теоремой правилам.
Тогда, повторяя рассуждения первого шага имеем:
Индуктивный переход доказан и следовательно, и вся
теорема доказана.
Курс «Математическая Логика и Теория Алгоритмов»
Тема «Основные понятия и определения алгебры высказываний. Двойственность»
20

21.

СПАСИБО ЗА ВНИМАНИЕ
© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013