E-Book Content
МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РФ ФЕДЕРАЛЬНОЕ АГЕНТСВО ПО ОБРАЗОВАНИЮ БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМ В.Г.ШУХОВА Математическая логика и теория алгоритмов Учебное пособие Терехов Д.В., Куценко Д.А. Белгород 2007 (v 1.0.0b) Учебное пособие посвящено изложению основ математической логике и теории алгоритмов. Учебное пособие предназначено для студентов, обучающихся по направлению «Информатика и вычислительная техника». Высказывания, логика высказываний Высказывание - это утверждение об изучаемых объектах имеющее однозначное и точно определенное значение. В русском языке высказывание представляет собой повествовательное предложение, о котором можно сказать, что оно сообщает нам нечто верное либо нечто совершенно неверное. Следовательно, высказывание может быть либо истинным, либо ложным. Иначе говоря, каждому высказыванию приписывается истинностное значение. В классической (двузначной) логике рассматривается всего два истинностных значения: Т – «истина» и ⊥ «ложь». Если даны два высказывания А и В, то логика, во-первых, говорит нам, как из них построить новое высказывание, а во-вторых, учит, как найти его истинностное значение, Для построения новых высказывании используются логические связки &, ∨, ⇒, ⇔, ¬ : A & B , A ∨ B , A ⇒ B , A ⇔ B , ¬ A , ¬B Связка & интерпретируется как союз «и» (конъюнкция); связка ∨ - «или» (дизъюнкция); связка ⇒ как глаголы «следует» (импликация); «вытекает», связка ⇔ - «тогда и только тогда, когда»; и, наконец, ¬ - понимается как отрицание высказывания А («не А»). Для установления истинностного применяют таблицы истинности: значения нового A B A& B A∨ B A⇒ B A⇔ B ¬A Т Т Т Т Т Т ⊥ Т ⊥ ⊥ Т ⊥ ⊥ ⊥