Тема_1_Понятие_высказывания_Основные_логические_операции. Тема1 Понятие высказывания. Основные логические операции. Формулы логики. Таблица истинности и методика её построения. Законы логики. Равносильные преобразования
 Скачать 0.78 Mb.
|
|
Тема-1: Понятие высказывания. Основные логические операции. Формулы логики. Таблица истинности и методика её построения. Законы логики. Равносильные преобразования. Москва 2022 г. Дискретная математика – это новое направление в математике, объединяющее отдельные её разделы: - математическая логика; - теория множеств; - теория графов; - теория кодирования; - теория автоматов. Дискретная математика, изучает свойства абстрактных дискретных объектов, имеющих прерывный (дискретный) характер в отличие от объектов, изучаемых классической математикой и носящих непрерывный характер. Если простыми словами: Дискретная математика – это наука, которая изучает математические объекты, принимающие отдельные (дискретные) значения. Слово «дискретность» в переводе с лат. языка (discretus) – обозначает прерывность, разделённость, онопротивопоставляемое непрерывности. Например, линия непрерывна (на определённом промежутке), пунктир – прерывистая линия, поэтому пунктир можно назвать дискретной линией: Дискретный сигнал: Сигналы могут быть аналоговыми, они непрерывны, а могут быть прерывистыми – дискретными, т.е. изменяются во времени, принимая то или иное значение из возможных. Цифровой и дискретный сигнал – это не одно и то же!!! Цифровой сигнал также состоит из отдельных значений, но не является прерывистым. Это можно проиллюстрировать на следующей схеме: Правила математической логики определяют методы обоснования математических утверждений. Греческий философ Аристотель был пионером логических рассуждений. Логика высказываний связана с утверждениями, которым могут быть присвоены значения истинности «истина» и «ложь». Понятие высказывания. Логические операции над высказываниями Под высказыванием понимают всякое повествовательное предложение, относительно которого можно сказать, истинно оно или ложно в данных условиях. Логическими значениями высказываний являются «истина» и «ложь». Примеры высказываний: 1) «Число 2 - чётное» 4). «Пифагор – математик» 2) «Число10 делится на5 » 5). «Самара – город на Днепре» 3) «11 < 0 » 6). «Собака – животное» Высказывания: 1), 2), 4), 6) - истинны, а высказывания: 3), 5) - ложны. Обозначают конкретные высказывания начальными заглавными буквами латинского алфавита A, B, C, D, …, А1 , А2, …, а их значения, то есть «истину» и «ложь», соответственно «1» и «0». Высказывания, представляющие собой одно утверждение, принято называть простыми или элементарными. Примерами элементарных высказываний являются высказывания, которые были рассмотрены выше: 1) – 6): 1) «Число 2 - чётное»; 2) «Число10 делится на5 » и т.д. Высказывания, которые получаются из элементарных с помощью логических связок: «и», «или», «если…, то…», «не» , «тогда и только тогда» принято называть «сложными» или «составными». Например: «Число 2 – чётное и число 10 делится на 5», «Если Пифагор – математик, то Самара – город на Днепре» Перечислим таблицы истинности логических операций: – таблица НЕ (отрицания ( )); – таблица И (конъюнкции ( ^ )); – таблица ИЛИ (дизъюнкции (v )); – импликационная таблица ( ; – таблица эквиваленции ( ). Логические операции над высказываниями 1. Конъюнкция: Конъюнкцией двух высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда высказывания А и В истинны. Конъюнкцию высказываний А и В обозначают: А&В (или В), читают «А и В». (логическое умножение). Высказывания А и В называют членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:
Например, для высказываний А: «2 ˂ 7» , В: «7 ˂ 12» их конъюнкцией будет высказывание В: «2 ˂ 7 ˂ 12» которое, очевидно, истинно. 2. Дизъюнкция: Дизъюнкцией двух высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда хотя бы одно из высказываний А или В истинно. Дизъюнкцию высказываний А и В обозначают: АvВ, читают: «А или В» (логическое сложение). Высказывания А и В называют членами дизъюнкции. Логические значения дизъюнкции описываются следующей таблицей истинности:
Например, для высказываний А: «2˂ 7» и В: «2=7» их дизъюнкцией будет высказывание АvВ: «2 ≤ 7» , которое, очевидно, истинно. 3. Импликация: Импликацией двух высказываний А и В называется высказывание, которое ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно. Импликацию высказываний А и В обозначают: А В , читают: «если А, то В» или «из А следует В». Высказывание А называют условием или посылкой импликации, а высказывание В - следствием или заключением. Логические значения импликации описываются следующей таблицей истинности:
Символ ( ) - символ деление нацело!!! Например, для высказываний А: «126» и В: «125» их импликацией будет высказывание АВ: «Если 126, то 125» которое, очевидно, ложно, так как высказывание А истинно, а высказывание В ложно. 4. Отрицание: Отрицанием высказывания А называется такое высказывание, которое истинно, если высказывание А - ложно, и ложно, если высказывание А истинно. Отрицание высказывания А обозначают: или А , читают: « не А» или «неверно, что А». Логические значения высказывания описываются следующей таблицей истинности:
Например, для высказывания А: «0 ˂ 3» его отрицанием является высказывание : «не верно, что 0 ˂ 3» или «0 ≥ 3», которое, очевидно, является ложным. 5. Эквиваленция: Эквиваленцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда высказывания А и В либо одновременно истинны, либо одновременно ложны. Эквиваленцию высказываний А и В обозначают АВ, читают: «А тогда и только тогда, когда В». Высказывания А и В называют членами эквиваленции. Логические значения эквиваленции описываются следующей таблицей истинности:
Например, для высказываний А: «6012» , В: «605» их эквиваленцией является высказывание АВ: «6012 , тогда и только тогда, когда 605» , которое, очевидно, является истинным. Определение: Формулами алгебры высказываний называются: 1). любые элементарные (простые) высказывания: а, b, c… ; 2). если А и В – формулы, то формулами также являются выражения вида: Никаких других формул нет!!!! В частности, формулой является любая логическая операция, например, логическое умножение а . Обратите внимание на второй пункт – он позволяет рекурсивным образом «создать» сколь угодно длинную формулу. Поскольку – формулы, то – тоже формула; так как – формулы, то – тоже формула и т.д. Формулой не является, например, запись – и здесь прослеживается очевидная аналогия с «алгебраическим мусором» 2⸱ +3 , из которого не понятно – нужно ли числа складывать или умножать. Логическую формулу можно рассматривать, как логическую функцию. Запишем в функциональном виде ту же конъюнкцию: Элементарные высказывания а и b в этом случае играют роль аргументов (независимых переменных), которые в классической логике могут принимать два значения: истина или ложь. Далее для удобства будем называть простые высказывания переменными. Таблица, описывающая логическую формулу (функцию) называется, таблицей истинности:
Принцип формирования таблицы истинности таков: «на входе» нужно перечислить все возможные комбинации истины и лжи, которые могут принимать элементарные высказывания (аргументы). В данном случае в формулу входят два высказывания, и нетрудно выяснить, что таких комбинаций четыре. «На выходе» получаем соответствующие логические значения всей формулы (функции). В «непростых случаях» нужно соблюдать порядок выполнения логических операций: – в первую очередь выполняется отрицание ( ); – во вторую очередь – конъюнкция ( ); – затем – дизъюнкция ( ); – потом импликация ( ); – и, наконец, низший приоритет имеет эквиваленция ( ). Так, например, запись подразумевает, что сначала нужно осуществить логическое умножение , а затем – логическое сложение: . Как в «обычной» алгебре – «сначала умножаем, а затем складываем». Порядок действий можно изменить привычным способом – скобками: – здесь в первую очередь выполняется дизъюнкция и только потом более «сильная» операция. Пример: Составим таблицу истинности для формулы . В данную формулу входят два элементарных высказывания и «на входе» нужно перечислить все возможные комбинации единиц и нулей: А теперь вспомним импликацию: В итоге сравниваем итоговые колонки у двух последних таблиц – они совпадают!!! Таким образом, мы выразили импликацию через базовые логические операции. В алгебре высказываний такие формулы называются равносильными или тождественными: (три горизонтальные чёрточки – это значок тождества). Сформулируем общее определение: две формулы называются равносильными (тождественными), если они принимают одинаковые значения при любом наборе значений, входящих в эти формулы переменных (элементарных высказываний). Также говорят, что «формулы равносильны, если совпадают их таблицы истинности». Домашнее задание Домашнее задание Используемая литература: 1.Спирина М.С., Спирин П.А. Дискретная математика. – М.: ОИЦ «Академия». 2020. 2.Спирина М.С., Спирин П.А. Дискретная математика. Сборник задач с алгоритмами решений. –М.: ОИЦ «Академия», 2019. 3. С.А. Канцедал. Дискретная математика : учеб. пособие / —М: ФОРУМ : ИНФРА-М, 2019. —224 с 4. А.И. Гусева, В.С. Киреев, А.Н. Тихомирова. Дискретная математика : учебник / —М.: КУРС: ИНФРА-М, 2020.— 208 с. 5. Баврин, И. И. Математика : учебник и практикум для СПО / И. И. Баврин. — 2-е изд., перераб. и доп. — Москва : Юрайт, 2020. Спасибо за внимание |