Введение задачи Изложить все рассматриваемые вопросы по возможности как можно более просто, но не проще чем это требуется для специалиста высшей квалификации. - презентация

1 Введение

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

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

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

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

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

7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24

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

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

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

28

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

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

31

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

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

34

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

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

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

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

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

40 Запись 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

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