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

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

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

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

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

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

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

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

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

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

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

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

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

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

Х YZX&Y(X&Y) Z

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

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

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

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

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

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

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

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

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

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

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