Использование логических законов при работе с информацией

1.

ИСПОЛЬЗОВАНИЕ
ЛОГИЧЕСКИХ ЗАКОНОВ ПРИ
РАБОТЕ С ИНФОРМАЦИЕЙ

2.

Высказывания
• Определение 1. Высказыванием называется
предложение, которое может быть либо
истинным, либо ложным.
Примеры.
• 1. Предложение «Снег – белый» есть истинное
высказывание.
• 2. Предложение «Волга впадает в
Средиземное море» – ложное высказывание.
• 3. Предложение «2+2=10» – ложное
высказывание.

3.

Значение истинности
• Условимся
каждому
истинному
высказыванию сопоставлять число 1, а
ложному – число 0.
• Определение 2. Число
P называется
значением истинности высказывания Р.

4.

Операции над высказываниям
Условные обозначения логических связок

5.

Операции над высказываниям
Условные обозначения логических связок (продолжение)

6.

Операции над высказываниям
• 1. Отрицание высказывания
Определение 1. Отрицанием
высказывания Р называется новое
высказывание, обозначаемое P (читается:
«Не Р» или «Неверно, что Р»), которое
считается истинным, если высказывание
Р ложно, и ложным, если Р истинно.

7.

Операции над высказываниям
Значения истинности высказываний Р и P
связаны между собой, как указано в
следующей таблице:

8.

Операции над высказываниям
• 2. Конъюнкция высказываний
Определение 2. Конъюнкцией
высказываний Р и Q называется новое
высказывание, обозначаемое PÙQ
(читается «Р и Q»), которое считается
истинным, если истинны оба
высказывания Р и Q, и ложным во всех
остальных случаях.

9.

Операции над высказываниям
Таблица истинности для конъюнкции

10.

Операции над высказываниям
• 3. Дизъюнкция высказываний
Определение 3. Дизъюнкцией
высказываний Р и Q называется новое
высказывание, обозначаемое P ∨ Q
(читается «Р или Q»), которое истинно в
тех случаях, если истинно хотя бы одно
из высказываний Р или Q, и ложно, если
ложны оба высказывания Р и Q

11.

Операции над высказываниям
Таблица истинности для дизъюнкции

12.

Операции над высказываниям
• 4. Импликация высказываний
Определение 4. Импликацией
высказываний Р и Q называется
высказывание, обозначаемое P Þ Q
(читается: «Если Р, то Q», или «Из Р
следует Q», или «P влечет за собой Q»),
которое ложно лишь в том случае, если Р
истинно, a Q ложно.

13.

Операции над высказываниям
Таблица истинности для импликации

14.

Операции над высказываниям
• 5. Эквивалентность высказываний
Определение 5. Эквивалентностью
(или эквиваленцией) высказываний Р и Q
называется новое высказывание,
обозначаемое P Û Q (читается «P
эквивалентно Q», или «P тогда и только
тогда, когда Q»), которой истинно в том и
только в том случае, если Р и Q
одновременно Истинны или
одновременно ложны.

15.

Операции над высказываниям
Таблица истинности для эквивалентности

16.

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

17.

Формулы алгебры высказываний
Полное описание понятия формулы дают
следующие соглашения:
• 1°. Каждая отдельно взятая высказывательная
переменная есть формула.
• 2°. Если F1 и F2 – две формулы, то
выражения F1, F2 , ( F1 Ù F2 ) , ( F1 Û F2 ) , ( F1 Û F2 ) , ( F1 Û F2 )
также являются формулами.
• 3°. He существует никаких других формул,
кроме тех, которые получаются в результате
применения конечного числа раз пп.1° и 2°.

18.

Формулы алгебры высказываний
Пример

19.

Тавтологии
• Определение 1. Формула алгебры
высказываний F X1, X 2 ,..., X n
называется тождественно истинной
(или тавтологией), если ее значение
истинности равно 1 при любых значениях
истинности для X1, X 2 ,..., X n .
(
)

20.

Равносильность формул
• Определение. Две формулы F ( X1, X 2 ,..., X n )
и A( X1, X 2 ,..., X n ) алгебры высказываний
называются равносильными, если при
любых логических значениях переменных
X1, X 2 ,..., X n логические значения
высказываний F и A совпадают.
Например, формулы X Û Y и X ÚY Ù Y Ú X
равносильны
(
)(
)