Математическая логика и теория алгоритмов Доцент каф. АОИ, к.т.н. Перемитина Татьяна Олеговна Алгебра высказываний. - презентация

1 Математическая логика и теория алгоритмов Доцент каф. АОИ, к.т.н. Перемитина Татьяна Олеговна Алгебра высказываний

2 2 Простые и сложные высказывания. Логические операций и их приоритет. Формулы алгебры высказываний. Построение таблиц истинности.

3 Высказывание – повествовательное предложение, для которого имеет смысл говорить о его истинности или ложности. В русском языке высказывания выражаются повествовательными предложениями. Москва – столица России Побудительные и вопросительные предложения высказываниями не являются. Без стука не входить ! Высказывание Но не всякое повествовательное предложение является высказыванием ( не является высказыванием – субъективное восприятие ). Каша – самое вкусное блюдо 3

4 4 Простые высказывания

5 5 Среди следующих предложений выделить те, которые являются высказываниями, и установить, истинны они или ложны. A.Сумма углов в треугольнике равна 180. B.Летайте самолетами Аэрофлота ! C.Солнечная система насчитывает 12 планет. D.Сегодня самый счастливый день. Задача 1

6 6 A.Сумма углов в треугольнике равна 180. B.Летайте самолетами Аэрофлота ! C.Солнечная система насчитывает 12 планет. D.Сегодня самый счастливый день. Решение

7 7 Сложные (составные) высказывания строятся из простых с помощью логических операций. Логические операции (в порядке убывания приоритета): Сложные высказывания

8 Логические операции 8 Связка Варианты символов Наименование операции не Отрицание и Конъюнкция или Дизъюнкция Если,… то Импликация тогда и только тогда Эквиваленция

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

10 10 Х - « я поеду автобусом », Y – « автобус опоздает », Z – « я пропущу назначенную встречу ». « Если я поеду автобусом и автобус опоздает, то я пропущу назначенную встречу ». Введение логических переменных

11 11 « Если Х и Y, то Z » « Если я поеду автобусом и автобус опоздает, то я пропущу назначенную встречу ». Построение формулы алгебры высказываний

12 XY X X&YX&Y X Y Таблица истинности логических операций

13 Алгоритм построения Подсчитать n – число переменных в выражении Подсчитать общее число логических операций в выражении Установить последовательность выполнения логических операций Определить число столбцов в таблице Заполнить шапку таблицы, включив в неё переменные и операции Определить число строк в таблице без шапки : m =2 n Выписать наборы входных переменных Провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью 13

14 14 Построение таблицы истинности Число переменных n=3, Число логических операций m=2: 1)X&Y, 2)(X&Y) Z.

15 Х YZX&Y(X&Y) Z

16 X V ˥ X n = 1, m = 2 1 = 2. Приоритет операций : ˥, V Пример построения таблицы истинности 16 Х ˥X˥XX V ˥XX V ˥X

17 17 X & ˥ X n = 1, m = 2 1 = 2. Приоритет операций : ˥, & Пример построения таблицы истинности Х ˥X˥XX & ˥XX & ˥X

18 Классификация формул алгебры высказываний 18 Выполнимые формулы Тождественно истинные формулы ( тавтологии ) Тождественно ложные формулы ( противоречия )

19 19 К какому классу формул относится формула X&Y& ˥ X ? Классификация формул алгебры высказываний Шаг 1. Строим таблицу истинности. Шаг 2. По последнему вектор-столбцу таблицы определяем к какому классу данная формула относится.

20 X&Y& ˥X n = 2, m = 2 2 = 4. Пример построения таблицы истинности 20 Х Y ˥X˥X X&Y X&Y& ˥ X Формула X&Y& ˥X является тождественно ложной.

21 Формализуйте, укажите приоритет логических операций, постройте таблицу истинности, укажите к какому классу формул алгебры высказываний относится : « Если число делится на 2 и не делится на 3, то оно не делится на 6». 21 Задача 2

22 22 Х - « число делится на 2 », Y – « число делится на 3 », Z – « число делится на 6 ». «Если число делится на 2 и не делится на 3, то оно не делится на 6». Решение

23 « Если Х и не Y, то не Z » «Если число делится на 2 и не делится на 3, то оно не делится на 6». Решение

24 Х YZ ˥Y˥Y ˥Z˥ZX& ˥ Y(X& ˥ Y) ˥ Z

25 К какому классу формул относится формула X V ˥ XY? а) Выполнимая; б) Тождественно истинная; в) Тождественно ложная. 25 Задача 3

26 Спасибо за внимание! 26