Презентация "Логические выражения и операции"

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

Булева алгебра

Двоичное кодирование – все виды информации кодируются с помощью 0 и 1.

Задача – разработать оптимальные правила обработки таких данных.

Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).

Почему "логика"? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Логические высказывания

Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

Высказывание или нет ?

• Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?
• Сейчас идет дождь.
• Жирафы летят на север.
• История – интересный предмет.
• У квадрата – 10 сторон и все разные.
• Красиво!
• В городе N живут 2 миллиона человек.
• Который час?

Обозначение высказываний

A – Сейчас идет дождь.

B – Форточка открыта.

простые высказывания (элементарные)

Любое высказывание может быть ложно (0) или истинно (1).

Составные высказывания строятся из простых с помощью логических связок (операций) " и ", " или ", " не ", " если … то ", " тогда и только тогда " и др.

Сейчас идет дождь и открыта форточка.

A и B

A или не B

Сейчас идет дождь или форточка закрыта.

Если сейчас идет дождь, то форточка открыта.

если A, то B

не A и B

Сейчас нет дождя и форточка открыта.

A тогда и только

Дождь идет тогда и только тогда, когда открыта форточка.

тогда, когда B

Операция НЕ (инверсия)

Если высказывание A истинно, то " не А " ложно, и наоборот.

также: , not A (Паскаль), ! A (Си)

А

не А

0

1

таблица истинности операции НЕ

1

0

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

Операция И (логическое умножение, конъюнкция)

Высказывание " A и B " истинно тогда и только тогда, когда А и B истинны одновременно.

также: A·B , A  B , A and B (Паскаль), A && B (Си)

A

B

А и B

0

1

2

3

0

0

0

0

0

1

0

1

0

1

1

1

конъюнкция – от лат. conjunctio — соединение

Операция ИЛИ (логическое сложение, дизъюнкция)

Высказывание " A или B " истинно тогда, когда истинно А или B , или оба вместе.

также: A+B , A  B , A or B (Паскаль), A || B (Си)

A

B

А или B

0

0

0

1

0

1

1

1

0

1

1

1

дизъюнкция – от лат. disjunctio — разъединение

7

Операция "исключающее ИЛИ"

Высказывание " A  B " истинно тогда, когда истинно А или B , но не оба одновременно .

также: A xor B (Паскаль), A ^ B (Си)

A

B

А  B

0

0

0

1

1

0

арифметическое сложение, 1+1=2

1

1

0

остаток

1

1

0

сложение по модулю 2: А  B = (A + B) mod 2

7

8

Свойства операции "исключающее ИЛИ"

0

A  A =

( A  B)  B =

A

A  0 =

A  1 =

?

A

A

0

B

0

0

1

1

1

0

А  B

1

0

0

0

0

1

0

1

1

1

1

1

0

0

0

0

0

8

9

Импликация ("если …, то …")

Высказывание " A  B " истинно, если не исключено, что из А следует B .

A – "Работник хорошо работает".

B – "У работника хорошая зарплата".

A

0

B

0

А  B

0

1

1

1

0

1

1

1

0

1

9

Эквиваленция ("тогда и только тогда, …")

Высказывание " A  B " истинно тогда и только тогда, когда А и B равны.

A

B

0

0

А  B

0

1

1

1

0

0

1

1

0

1

Составление таблиц истинности

A

B

0

0

A ·B

0

1

1

0

1

X

1

0

1

1

0

0

1

2

3

0

1

0

1

0

0

1

1

1

0

0

1

Логические выражения могут быть:

• тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)
• тождественно истинными (всегда 1, тавтология)
• тождественно ложными (всегда 0, противоречие)
• вычислимыми (зависят от исходных данных)

12

Составление таблиц истинности

A

B

0

C

0

0

0

A∙B

0

0

0

1

A∙C

1

1

B∙C

0

1

X

1

0

1

0

0

1

1

1

1

1

0

1

0

0

1

2

3

4

5

6

7

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

1

1

0

0

0

1

1

0

1

1

1

1

12

13