Элементы математической логики
Вопросы
1. Что такое база данных?
2. Что такое реляционные базы данных?
3. Что такое сортировка данных?
4. Как упорядочивается информация в базах данных?
5. Что такое запросы к базам данных?
6. Как строятся сложносоставные запросы?
7. Как обновляется информация в базах данных?
Задания
1. Составьте базу данных «Телефонный справочник» с телефонами своих друзей и родных с указанием фамилий и имен. Упорядочите базу данных по фамилиям.
2. Составьте базу данных о своих родных: маме, папе, сестрах, братьях, дедушках и бабушках с указанием их дней рождения и месте работы или учебы. Упорядочите базу данных по возрасту и приведите примеры запросов.
3. Составьте базу данных о своих друзьях с указанием их возраста, места учебы, профессий и любимых увлечений. Упорядочите базу данных в алфавитном порядке по именам друзей и приведите примеры запросов.
4. Составьте базу данных по своей успеваемости, включая оценки по математике и информатике. Упорядочите базу данных в порядке убывания оценок по:
а) математике; б) информатике.
5. Составьте по журналу успеваемости базу данных по следующим предметам:
а) математике; в) физике;
б) информатике; г) литературе.
Укажите запросы на поиск студентов, не имеющих:
а) ни одной двойки; в) ни одной тройки;
б) ни одной четверки; г) ни одной пятерки.
Принципы поиска и обработки информации в ЭВМ основываются на законах математической логики, поскольку компьютеры — это автоматические устройства, принципы работы которых базируются на элементарных законах двоичной логики.
Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 0 и 1. Вся обработка информации в ЭВМ всех ее логических блоков, логических схем и устройств опиралась и будет опираться на законы и принципы математической логики.
Логика — это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств. Примеры суждений: «снег белый», «2 х 2 = 5», «Земля круглая», «информатика — лженаука», «Интернет — международная сеть».
Математическая логика — это математическая дисциплина, изучающая технику доказательств. Компьютеры, как и математики, требуют точности и строгости в определениях, описаниях, доказательствах и обоснованиях, чем они отличаются от обычных нормальных людей. И на них нельзя обижаться.
Отличие вычислительных операций и математических суждений от обычных человеческих действий и высказываний состоит в следующем. Вычислительные операции и математические суждения всегда предполагают однозначную интерпретацию, в то время как действия и высказывания людей зачастую допускают многозначную художественную трактовку.
Суждения и в математике, и на практике могут быть истинными или ложными. На практике истинность или ложность суждений проверяется их соответствием действительности, а в математике — опровержениями либо доказательством.
Пример истинного суждения — «снег белый». Пример ложного суждения — «генетика — лженаука». Пример суждений, истинность которых до сих пор до конца еще не установлена: «машина может думать», «на Марсе есть жизнь», «информатика — наука».
Работа ЭВМ как автоматических устройств основана исключительно на однозначных правилах выполнения команд, программ и алгоритмах обработки данных. Тем самым работа компьютеров, а также всех вычислительных устройств, систем и сетей допускает верификацию — строгую однозначную проверку правильности их работы.
Все сложные логические элементы и блоки вычислительных машин и устройств конструируются из простейших логических элементов с помощью логических операций «И» (AND), «ИЛИ» (OR) и «НЕ» (NOT). В математической логике для этих операций обычно используются обозначения — & («И»), V («ИЛИ»)и — («НЕ»).
Наглядной иллюстрацией этих логических связок служат следующие диаграммы:
Отрицаниене А истинно или ложно в зависимости от истинности исходного суждения А. Свойства отрицанияне как логической связки можно описать таблицей истинности:
Таблица истинности:
Свойства отрицаний:
НЕ1:Отрицание ложно, если суждение истинно.
НЕ2:Отрицание истинно, если суждение ложно.
Для понимания роли отрицаний в языках запросов важно уметь выражать их в позитивной форме. Приведем примеры отрицания математических неравенств и их эквивалентные позитивные переформулировки:
не (х = 0) ≡ (х ≠ 0);
не (х ≠ 0) ≡ (х = 0);
не (х > 0) ≡ (х ≤ 0);
не (х < 0) ≡ (х ≥ 0);
не (х ≥ 0) ≡ (х < 0);
не (х ≤ 0) ≡ (х > 0).
Для общего понимания математических суждений, утверждений и отрицаний необходимо иметь представления обобщих законах математики и математической логики в частности. Первым среди общих законов математической логики явлется
Закон двойного отрицания:
не (не А) = А.
Отрицание отрицания равносильно исходному утверждению.
Логическая связка и в математической логике называется конъюнкцией. Таблица истинностиконъюнкции:
Свойства конъюнкции:
И1:Конъюнкция А и В истинна, когда истинны оба суждения.
И2:Конъюнкция А и В ложна, когда ложно хотя бы одно из суждений А или В.
Логическая связкаили в математической логике называется дизъюнкцией. Таблица истинностидизъюнкции:
Свойства дизъюнкции:
ИЛИ1:Дизъюнкция А или Вистинна, когда истинно любое из суждений А или В.
ИЛИ2:Дизъюнкция А или Вложна, когда ложны оба суждения А и В.
Для понимания принципов поиска информации по запросам в базах данных и сети Интернет необходимо понимать математический смысл сложносоставных запросов с использованием логических операций «И» (AND), «ИЛИ» (OR)и«НЕ» (NOT).
Примеры сложносоставных запросов к базам данных и их эквивалентные позитивные переформулировки:
(признак ≠ 0) & не (х > 0) ≡ (признак (0)) & (х ≤0);
(число > 0) v не (у > 0) ≡ (число > 0) v (у ≤ 0).
Общие принципы отрицания дизъюнкций и конъюнкций в математической логике выражаются двумя закона де Моргана:
Закон отрицания конъюнкции:
не (А и В) = (не А) или (не В)
— отрицание конъюнкции суждений равносильно дизъюнкции отрицаний.
Закон отрицания дизъюнкции:
не (А или В) ((не А) и (не В))
— отрицание дизъюнкции суждений равносильно конъюнкции отрицаний.
Знание и использование данных трех общих законов логики позволяют полностью избавляться от негативных формулировок в запросах к базам данных и в общении друг с другом. Но еще важнее знание этих законов для понимания принципов и результатов поиска информации компьютерами.
Попробуйте проверить законы отрицания в запросах к Интернет и объясните результаты, полученные от различных поисковых систем:
запрос:«учебник -физика» — «учебник, но не по физике?»
запрос:«учебник -книга» — «учебник, но не книга?»
запрос:«-учебник информатика» — «не учебник, но по информатике?»
запрос:«-(-учебник)» — «неверно, что это не учебник» ??? .
Задача 1. Проверьте закон двойного отрицанияне (не А) ≡ А с помощью таблиц истинности.
Сравнение крайних столбцов показывает, что всюду, где высказывание А истинно, там же истинно и двойное отрицаниене (не А). И наоборот, всюду, где ложно А, там ложно и двойное отрицаниене (не А). Следовательно, двойное отрицание тождественно исходному высказыванию:не (не А) ≡ А.
Задача 2. Сравните с помощью таблиц истинности отрицание дизъюнкции и отрицание конъюнкциине (А и В) ине (Аили В).
Решение.