Алгебра высказываний. Определение высказывания. Таблица истинности для высказываний. Логические тождества. (Лекция 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