Читать онлайн «Математическая логика»

ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра автоматизированных систем обработки информации и управления МАТЕМАТИЧЕСКАЯ ЛОГИКА Методические указания по курсу ''Основы дискретной математики'' для студентов специальности 220200 Пермь 1998  -1- Математическая логика Математическая логика наряду с теорией множеств составляет фундамент со- временной математики. Математическая логика занимается анализом методом рассуждений. В рамках курса «Основы теории систем» рассматриваются начальные понятия алгебраического и исчисленческого аспектов многообразной отрасли математики – современной математической логики. В данных методических указаниях рассматриваются вопросы алгебры логики, дана краткая теоретическая справка по соответствующим разделам ло- гики и приведены примеры. Алгебра высказываний в простейшем своём виде используется в дисцип- линах, связанных с программированием (при формировании логических усло- вий). Алгебраические преобразования и минимизация преобразований необхо- димы при создании комбинированных схем ЭВМ и других дискретных уст- ройств. Язык предикатов позволяет обеспечить качественно новый уровень ло- гических рассуждений и преобразований. Язык и алгебра предикатов широко используются при описании и исследовании сложных систем. АЛГЕБРА ВЫСКАЗЫВАНИЙ. Высказывание – повествовательное предложение, о котором можно ска- зать, истинно оно или ложно. Значение «истинно» и «ложно» обычно обознача- ются I или 0, или И и Л, или T и F. Высказывания будем обозначать любыми буквами, возможно с индексами. Из простейших (элементарных или атомарных) высказываний с помощью логических операций строятся сложные высказыва- ния (формулы алгебры высказываний). Операции логики высказываний можно задать с помощью табл. 1 Таблица 1. А В ¬А А ∨ В А&B A→B A~B A⊕B A | B A↓B 0 0 I 0 0 I I 0 I I 0 I I I 0 I 0 I I 0 I 0 0 I 0 0 0 I I 0 I I 0 I I I I 0 0 0 Содержательно логические операции обычно интерпретируют следую- щим образом: отрицание (инверсия) ¬ (− ) − «не» дизъюнкция ∨ (+ ) − «или» конъюнкция & ( ⋅ ,∧ ) − «и» импликация → (⊃ ) − «если … , то» эквивалентность ~ (↔ ) − «тогда и только тогда» (или «эквивалентно»)  -2- Математическая логика неравнозначность (сумма по модулю 2) ⊕ - «исключающее или» штрих Шеффера | - «и - не» стрелка Пирса ↓ - «или - не» Примем соглашение относительно силы связывания ряда операций (упо- рядочив по убыванию): ¬, &, ∨, →, ~ .