Похожие презентации:
Алгебра высказываний. Определение высказывания. Таблица истинности для высказываний. Логические тождества. (Лекция 2)
1. Алгебра высказываний Лекция 2
Цель: Дать определение высказывания, таблицы истинности.Сформулировать основные логические тождества
2.
2. Определение высказывания.Таблица истинности для высказываний
Определение 1
Переменная А, принимающая два значения – 0 или 1, называется
логической (или булевой) переменной.
Обозначаться логические переменные будут заглавными
латинскими буквами с индексами или без них:
A, B , X ,Y , A2 ,C3 ,...
3.
Соглашение 1Если высказывание сконструировано из однотипных операций, то
они выполняются в порядке их следования.
К примеру,
A B C D
A B C D
Соглашение 2
Отрицание подразумевает скобки
Соглашение 3
Внешние скобки не ставятся.
4.
Соглашение 4Конъюнкция связывает сильнее, чем дизъюнкция.
Например,
A B C A B C
Соглашение 5
Дизъюнкция связывает сильнее, чем импликация.
Например,
A B C D A B C D
Соглашение 6
Импликация связывает сильнее, чем эквивалентность.
Например,
A B C A B C
5. Примеры
• 1)Избавиться от лишних скобок(( A ( B C)) ( AB C))
• Ответ A B C ( AB C)
• 2)Расставить порядок действий
4
A( B C) AC B C
5
1
7
2
3
6
6.
Если высказывание F построено из логических переменныхA1 , A2 ,... , An , то будем обозначать это высказывание:
F F A1 , A2 ,..., An
Определение 3
Таблица истинности для высказывания F A1 , A2 ,..., An имеет вид
A1
A2
… An-1
An
F(A1, A2,…, An-1, An)
0
0
…
0
0
F(0,0,…,0,0)
0
0
…
0
1
F(0,0,…,0,1)
…
…
…
…
…
…
1
1
…
1
0
F(1,1,…,1,0)
1
1
…
1
1
F(1,1,…,1,1)
Теорема
Наборов длины n из 0 и 1 существует 2n
7.
ПримерПостроить таблицу истинности для высказывания
(A C ) B A
A
B
C
C
A C
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
1
0
1
1
0
0
0
1
1
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
0
1
1
0
0
B A B A
F
8. 3. Равносильные высказывания.
Определение 1Высказывания F(A1,A2,…,An) и G(A1,A2,…,An) называются равносильными (или
просто равными), если для любого набора
1 , 2 ,..., n имеет место равенство: F 1 , 2 ,..., n G 1 , 2 ,..., n .
Обозначим
F A1 , A2 ,..., An G A1 , A2 ,..., An
Другими словами, два высказывания равны, если у них совпадают таблицы
истинности.
9.
ПримерыA B A B
Доказательство
A
B A B
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
A B
10. Основные логические тождества
Идемпотентные законы:1) A A A
2) A A A
Коммутативные законы:
3) A B
B A
4) A B B A
5) A B B A
Ассоциативные законы:
6) A B C A B C
7) A B C A B C
8) A B C A B C
11.
Дистрибутивные законы:9) A B C AB AC
10) A BC A B A C
Законы Моргана:
11) A B A B
12) A B A B
Закон двойного отрицания:
13) A A
Закон противоречия:
14) A A 0
Закон исключенного третьего:
15)
A A 1
Без названия:
16) A B AB A B A B B A
17) A B A B
12.
Законы поглощения:18) A AB A
Доказательство
A AB A (1 B) A 1 A
19) A AB A B
Доказательство
A AB ( A A)( A B) 1 ( A B) A B
20)
A A B AB
21) A ( A B) A
13.
Тождества, содержащие константы:A 0 A
A 1 1
A 0 0
A 1 A
A 0 A
A 1 1
0 A 1
1 A A
A 0 A
A 1 A