Введение

задачи Изложить все рассматриваемые вопросы по возможности как можно более просто, но не проще чем это требуется для специалиста высшей квалификации Практические проблемы проектирования и анализа информационных систем являются отправной точкой, а формальный аппарат – средством систематического решения этих проблем

Результат реализовывать простейший вид логического преобразования информации в произвольном базисе логических функций выделять в доказательных рассуждениях естественного языка логическую структуру, строить схемы формальных доказательств и проверять их правильность

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

Два основ­ных раздела логика высказываний логика предикатов

Два подхода алгебра логики логические исчисления

Высказывание - повествовательное предложение (утверждение, суждение), о котором имеет смысл говорить, что оно истинно или ложно

История развитая математической логики сформировалась в 4 в. до н.э. - Аристотель 17 в. Лейбниц - каждому высказыванию соответствовал символ, а рассуждения имели бы вид вычислений 19 в. Джордж Буль 1854 году "Исследование законов мышления" математическая логика - это логика, использующая язык и методы математики; во-вторых, математическая логика вызвана к жизни потребностями математики

19 в. Георг Кантор - теория множеств 1910 г. Эренфест П.С. указал на возможность применения аппарата булевой алгебры в телефонной связи для описания переключательных цепей г. Шестаков В. И., Шеннон Накасима и Хакадзава - труды о применении математической логики в цифровой технике.

Основы математической логики

Логическими высказываниями являются утвердительные предложения, относительно которых можно говорить об истинности или ложности. Если предложение истинно, то его значение истинности равно 1, если ложно – то 0.

"х 2 = 4" - не является высказыванием (-2. О, 2, 4) (-2) 2 = 4, 2 2 =4 Предложение, которое содержит хотя бы одну переменную и становится высказыванием при подстановке вместо всех переменных их значений, называют высказывательной или пропозициональной (ПФ) формой

Предикаты и кванторы cosх=1 Каждому значению "х" на множестве действительных чисел эта форма ставит в соответствие высказывание и, тем самым, одно из значений истинности {0,1}. Так значению х = 0, соответствует истинное высказывание cos0 = 1, при х = 2 соответствует истинное высказывание cos2 = 1, вообще всякому значению х кратному 2 х соответствует истинное высказывание, а всем остальным значениям ложные высказывания. Т.о. данная высказывательная форма задает отображение множества R действительных чисел на множество {1, 0} или {и, }, иначе говоря, задает функцию с областью определения R и множеством значений {1, 0}

Говорят, что определена некоторая функция, если, во- первых, зада­но некоторое множество, называемое областью определения функции или областью отправления, во-вторых, задано некоторое множество, назы­ваемое областью значений (прибытия) функции и, в- третьих, указанно определенное правило, с помощью которого каждому элементу, взятому из области определения, становится в соответствие некоторый элемент из области значений. Произвольный элемент взятый из области определения функции назы­вается аргументом и обозначается х. Правило соответствия обозначае­тся F, т.о. запись у=F(х) означает, что х - аргумент, у - функция, F - правило соответствия.

Функция, область определения которой задана множеством М, а все значения которой, принадлежат множеству {1, 0} называется предикатом.

Пример Если переменная х в высказывательной форме "Река х впадает в Каспийское море" принимает значение из множества М названий всевозможных рек, то эта форма задает предикат

Выражение "для всякого х" называется кванторам общности по переменной х (вместо х может быть любая другая переменная) и запи­сывается х (Ф (х)) Выражение, "существует х, такое что..." называется квантором существования по переменной х и обозначается х (Ф(х)), что означает существует значение "х" такое, что Ф(х) при этом значении - истинное высказывание. Переход от формы Ф(х) к высказыванию х (Ф(х)) или х (Ф(х)) называется операцией квантификацией формы Ф(х). Будем называть переменную "х" в Ф(х) после применения к ней операции квантификации связанной переменной. В отличие от связанных переменных, переменные в первоначальном смысле слова называются свободными переменными

Булевы функции, булевы константы Булевыми функциями (или функциями алгебры логики или истинностными функциями) называются функции, значения которых равны 0 или 1 и аргументы которых принимают только два значения 0 и 1

Выражения, содержащие одну или несколько переменных (аргументов), соединенных знаками логических операций, называются логическим формами Булевыми функциями, называются предикаты, все аргументы которых определены на множестве {0, 1}, интерпретируемые как {ложь, ис­ тина}.

Можно сказать, что понятие булевой функции является частным случаем понятия предиката Отличие – у булевой функции четко фиксирована как область определения {0, 1}, так и область значений функции {0, 1}, в то время как у предиката четко фиксирована только одна область значений {0, 1}, в то время как область определения задана произвольным множеством

Основные логические связи Будем называть высказывание простым (элементарным), если оно рассматривается нами как некое неделимое целое (аналогично атому или элементу множества). Обычно к ним относят высказывания, не содержащие логических связок. Сложным (составным) называется высказывание, составленное из про­стых с помощью логических связок

Отрицание (логическая связь "не") Записывается Р=Ā или в виде P= ¬A (Читается "Р есть не А"). Отрицанием называется сложное логическое высказывание Р, которое истинно, если А ложно и наоборот.

Условное обозначение инвертора

Диаграмма Венна

Конъюнкция Р = А Ù В; Р = А & В. (Читается Р есть А и В). Конъюнкция - сложное логическое высказывание, которое истинно только в случае истинности всех составляющих высказываний, в противном случае ложно. Операция конъюнкция часто называется логическим умножением или логической связью "и".

Диаграмма Венна A Ù 0 = 0; A Ù Ā = 0; A Ù 1 = A

Дизъюнкция Р = А V В (читается Р есть А или В). Дизъюнкция - это сложное логическое высказывание, которое ложно только в случае ложности всех составляющих высказываний, в противном случае истинно

Диаграмма Венна A v 1 = 1; A v Ā = 1

Импликация Импликацией высказываний А и В называется высказывание, обозначенное символами А Þ В, которое ложно тогда и только тогда, когда А истинно, а В ложно. Читается А влечет В либо "А имплицирует В", Запись А Þ В означает то же, что и высказывание : "если А то В", "из А вытекает В" "А есть достаточное условие для В",

1. Импликация с ложным антецедентом всегда истинна. 2. Импликация с истинным консеквентом всегда истинна. 3. Импликация ложна тогда и только тогда, когда ее антецедент истинный, а консеквент ложный.

диаграмма Венна

Эквиваленция или равнозначность Эквивалвниией высказываний А и В называется высказывание, обозначаемое символом А Ù В (или,, ), которое истинно тогда и только тогда, когда значения истинности высказываний А и В совпадают

Высказывания А и В называются равносильными., если (А В) = 1 говорят, что формулы F 1 и F 2 равносильны, если их эквиваленция F1 F2 - тавтология (тождественно истинное высказывание).

Диаграмма Венна

Запись F 1 F 2 читается : "формула F 1 равносильна формуле F 2 " А В (А В) (В А) Равносильность есть отношение между формулами (также как равенст­во отношение между числами, параллельность - отношение между прямыми). Отношение равносильности обладает следующими свойствами: рефлективности F F симметричности: если F 1 F 2 то F 2 F 1 транзитивности: если F 1 F 2 и F 2 F 3, то F 1 F 3

НЕ &И ИЛИ влечет совпадает