Математическая логика и теория алгоритмов

1.

МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ

2.

ПОНЯТИЕ ВЫСКАЗЫВАНИЯ
• Высказыванием называется любое
повествовательное предложение, либо
истинно либо ложно.
ИСТИНА
ВЫСКАЗЫВАНИЕ
ЛОЖЬ

3.

ПРИМЕРЫ
1.
2.
3.
4.
5.
6.
7.
ВЫСКАЗЫВАНИЯ
Сократ – человек
2+2=4
5>7
2+3=6
7<10
Волга впадает в
Каспийское море.
Париж столица Англии.
НЕ ВЫСКАЗЫВАНИЯ
• 2+5
• x>y , где x и y
переменные
• 3x=2
• Зачем я учусь?
• Закрой дверь!
• Sin x=1
• x+y=z

4.

ОБОЗНАЧЕНИЯ ВЫСКАЗЫВАНИЙ
• Высказывания будем обозначать
заглавными латинскими буквами
• A, B, C, D
• Результат высказывания - ИСТИНА (И) или
ЛОЖЬ (Л)
A
И
Л

5.

ОПЕРАЦИИ НАД ВЫСКАЗЫВАНИЯМИ
1
┐
отрицание
3
2
&
конъюнкция
˅
дизъюнкция
4
5
⟹
≡
импликация
эквивалентность

6.

ОТРИЦАНИЕ

7.

КОНЪЮНКЦИЯ

8.

ДИЗЪЮНКЦИЯ

9.

ИМПЛИКАЦИЯ

10.

ЭКВИВАЛЕНТНОСТЬ

11.

ПРОПОЗИЦИОНАЛЬТНЫЕ ФОРМЫ
(ФОРМУЛЫ ЛОГИКИ ВЫСКАЗЫВАНИЙ)
СВЯЗКИ
┐ & ˅ ≡
ВЫССКАЗЫВАНИЯ
A, B, C…
Пропозициональная форма

12.

Задание: выбрать
пропозициональные формы

13.

Таблицы истинности
пропозициональной формы

14.

Задание: составить таблицы истинности
для пропозициональных форм