Математическая логика

Тема 3. Математическая логика Цель: получить представление о методах и средствах формальной логики для решения практических задач. Задание: 1. изучить материал данной лекции; 2. сделать краткий конспект, который необходимо представить к зачету; 3. подготовиться к письменному опросу по данной теме; 4. подготовиться к контрольной работе по данной теме. Понятие высказывания Центральным понятием математической логики является понятие "простого высказывания". Высказывание - это утвердительное повествовательное предложение, о котором точно можно сказать истинно оно или ложно. Логические значения высказываний это "истина" и "ложь", принятые обозначения "и", "л" или 1 и 0. пример: • Днепр река. • Рим - столица Италии. • Число 9 делится на 3 и 5. • Если студент окончил университет, то он получил высшее образование. Логические операции над высказываниями. Конъюнкция (логическое умножение) - сложное логическое выражение, которое истинно только в случае, когда истинны оба входящих в него простых выражения. Талица истинности для конъюнкции имеет следующий вид: А В А∧В 1 1 1 1 1 Логическая связка конъюнкции - союз "и". пример: Прочитай книгу и иди гулять. Дизъюнкция (логическое сложение) - сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно и если оба простых логических выражения ложны. Талица истинности для дизъюнкции имеет следующий вид: А В А∨В 1 1 1 1 1 1 1 Логическая связка дизъюнкции - союз "или". пример: В этом сезоне я хочу пойти на “Ромео и Джульетту” или на “Отелло”. Сложение по модулю 2 (логическое сложение, исключающее «или»,  строгая дизъюнкция) - булева сумма, значит "один или другой, но не оба вместе". Талица истинности для исключающей дизъюнкции имеет следующий вид: А В А⊕В 1 1 1 1 1 1 Логическая связка сложения по модулю 2 - союз "или", "либо...либо". пример: Она учится в Московском или в Санкт-Петербургском институте. Импликация (логическое следствие) - сложное логическое выражение, которое ложно только в случае, когда из истины следует ложь. Талица истинности для импликации имеет следующий вид: А В А→В 1 1 1 1 1 1 1 Логическая связка импликации - "если ... то", "когда ... тогда". пример: Если Днепр - река, то Бразилия - большой город. Эквиваленция - сложное логическое выражение, которое истинно только при одинаковых значениях истинности простых выражений, которые в него входят. Талица истинности для эквиваленции имеет следующий вид: А В А↔В 1 1 1 1 1 1 Логическая связка эквиваленции - "тогда и только тогда, когда", "если и только если". пример: Треугольник является равносторонним тогда и только тогда, когда он является равноугольным. Инверсия (логическое отрицание) - делает истинное высказывание ложным и, наоборот, ложное - истинным. Талица истинности для инверсии имеет следующий вид: А ¬А 1 1 Логическая связка инверсии - "не", "нет", "неверно". пример: Неверно, что 8 есть четное число. Штрих Шеффера - это бинарная операция, отрицающая логическое умножение, соответственно значение ложно тогда и только тогда, когда оба простые выражения истинны. Талица истинности для штриха Шеффера имеет следующий вид: А В А|В 1 1 1 1 1 1 1 Штрих Шеффера выражается в виде: А|В = ¬(А∧В) Стрелка Пирса - это бинарная операция, отрицающая логическое сложение, соответственно значение истинно тогда и только тогда, когда оба простые выражения ложны. Талица истинности для стрелки Пирса имеет следующий вид: А В А ↓ В 1 1 1 1 1 1 1 Штрих Шеффера выражается в виде: А ↓ В = ¬(А∨В) Порядок выполнения логических операций: 1. инверсия 2. конъюнкция 3. дизъюнкция 4. импликация 5. эквиваленция 6. штрих Шеффера 7. стрелка Пирса Чтобы изменить данный порядок необходимо использовать скобки. Для штриха Шеффера и стрелки Пирса приоритет не определен. Закон алгебры логики 1. закон тождества: А=А 2. закон непротиворечия: А∧=0 3. закон исключенного третьего: А∨=1 4. закон двойного отрицания: ¬ ¬А=А 5. законы констант: • 0= ¬1 • А∨0=А • А∨1=1 • А∧0=0 • А∧1=А 6. законы идемпотентности: • А∧А=А • А∨А=А 7. законы коммутативности: • А∧В=В∧А • А∨В=В∨А 8. законы ассоциативности: • А∧(В∧С)=(А∧В)∧С • А∨(В∨С)=(А∨В)∨С 9. законы дистрибутивности: • А∧(В∨С)=(А∧В)∨(А∧С) • А∨(В∧С)=(А∨В) ∧(А∨С) 10. законы поглощения: • А∧(А∨В)=А • А∨(А∧В)=А 11. законы де Моргана: • ¬(А∧В) = ¬А ∨ ¬В • ¬(А∨В) = ¬А ∧ ¬В 12. законы замены импликации: • А→В = ¬А∨В • А→В = ¬В → ¬А 13. законы замены эквивалентности: • А↔В = (А∧ ¬В)∨(¬А∧В) • А↔ ¬В = (А∨¬В) ∧(А∨В) • А↔В = (А→В) ∧ (В→А) Таблицы истинности и методика ее построения Любую логическую формулу можно записать с помощью таблицы истинности, она показывает, чему будет равно значение логического выражения при всевозможных комбинациях значения исходных переменных. Таблицы истинности задают логическую функцию. Сложные высказывания следует разбить на несколько простых, вычислив сначала значения этих промежуточных величин, и в итоге - окончательный результат. Количество комбинаций зависит от количества переменных и находится по формуле 2n, где n - количество переменных. Высказывание, которое истинно при любых значения переменных является тождественно истинным или тавтологией. Высказывание, которое всегда ложно является тождественно ложным или противоречием. Если 2выражения принимают одинаковые значения при всех значениях переменных их называют равносильными или тождественно равными. Алгоритм составления таблиц истинности 1. Найти количество строк в таблице: 2n, где n - количество переменных 2. Найти количество столбцов: количество переменных + количество логических операций. 3. Найти порядок выполнения логических операций. 4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных. пример: Найти количество строк и столбцов таблицы истинности для логического высказывания: ((А В) → (В  С))↔ Решение: Количество строк = 23=8 Количество столбцов = 3+5=8 Порядок действий: 1. А В 2. В  С 3. 1 → 2 4. 5. 3 ↔ 4 Составляем таблицу истинности: А В С А В В  С (А В) → (В  С) ((А В) → (В  С))↔ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Алгоритм упрощения формул с помощью равносильных преобразований 1. Заменить все "не базовые" операции (→, ↔, ⊕ и т.д.) на их выражения через базовые операции ¬, , . 2. Раскрыть инверсию сложных высказываний по законам де Моргана, чтобы операции инверсии остались только у отдельных переменных. 3. Использовать вынесение общего множителя за скобки, раскрыть скобки и другие законы алгебры логики, упростить выражение. пример: (А¬В)  (  (¬АС) = (А¬В)  ¬А  ¬В  (¬АС) = (А¬А¬В¬А)  ¬В  (¬АС) = ¬В  ¬А  ¬В  (¬АС) = ¬А  ¬В  (¬АС) = ¬В  ¬А  (¬АС) = ¬В  ¬А. В данном примере в последовательности были применены законы де Моргана: распределительный, исключение третьего, переместительный, повторение, и опять переместительный, а также закон поглощения. Алгоритм перевода высказываний с естественного языка на формальный 1. Выделить и обозначить простые высказывания. 2. Найти логические связки и заменить их на соответствующие логические операции. 3. Записать логическую формулу сложного высказывания. 4. Сделать проверку на соответствие полученной формулы исходному высказыванию. Алгоритм перевода высказывания с формального языка на естественный 1. Заменить логическую переменную простым высказыванием. 2. Логические операции заменить соответствующими логическими связками. 3. Составить предложение. Используя перевод естественной речи на язык математической логики, таблицы истинности, законы формальной логики в рассуждениях, а также теорию графов, можно решать текстовые задачи, встречающиеся в повседневной и профессиональной деятельности любого человека. Высказывательная форма. В математике часто встречаются предложения, содержащие одну или несколько переменных: х < 8, х + у = 10. Эти предложения не являются высказываниями, так как не имеет смысла вопрос, истинны они или ложны - это высказывательные формы. пример: Предложение «Число х – двузначное» не является высказыванием, т.к. относительно него нельзя определить: истинно это предложение или ложно. Но при подстановке конкретных значений вместо переменной оно обращается в истинное или ложное высказывание. Например, при х=7 мы получим ложное высказывание «Число 7-двузначное», а при х=27 - истинное высказывание «Число 27-двузначное». Такое предложение называют предикатом или высказывательной формой. Высказывание, которое содержит переменную, принимающую различные значения, причем подстановка любого из значений переменной превращает это предложение в высказывание, называется предикатом или высказывательной формой. Каждая высказывательная форма образует множество высказываний. пример: при подстановке различных значений вместо переменной в высказывательную форму «х+2=10» получаем однотипные высказывания: 8+2=10, 7+2=10, 6+2=10 и др. По числу переменных, входящих в высказывательную форму (предикат), их делят на одноместные, двухместные и т.д. и соответственно обозначают: А(х), В(х; у) и т.д. пример: предложения «Число х - однозначное» и «х+4=10» являются одноместными высказывательными формами (предикатами), а предложения «х > у» и «х + у =8» - двухместными высказывательными формами. Для каждой высказывательной формы нужно указать множество значений, которые может принимать переменная (переменные), входящая в эту высказывательную форму. Множество значений, которые может принимать переменная (переменные) высказывательной формы (предиката), называется областью определения высказывательной формы (предиката). Область определения высказывательной формы будем обозначать через Х и предикаты будем записывать с указанием области определения: А(х), хÎХ; В(х; у), х, уÎХ и т.д. Запись А(х), х Î Х, читают: «Высказывательная форма (предикат) А(х) задана на множестве Х». пример: 1. А(х): «Слово х - существительное», его областью определения будет множество слов русского языка. 2. В(х): «х+5=13», Х=R. 3. С(х): «Четырехугольник х - прямоугольник», Х - множество четырехугольников. 4. D(х; у): «х+у=7», Х=R или Х=N. Среди всех возможных значений переменной из области определения выделяют те, которые обращают высказывательную форму в истинное высказывание. Множество тех значений переменной из области определения высказывательной формы (предиката), при подстановке которых получаем истинные высказывания, называется множеством истинности высказывательной формы (предиката). Множество истинности высказывательной формы (предиката) будем обозначать буквой Т. Тогда, согласно определению, ТÌХ (множество Т является подмножеством множества Х). пример: 1. А(х): «Слово х - существительное», его множеством истинности является множество глаголов русского языка. 2. В(х): «х+8=13», Т={5}. 3. С(х): «Четырехугольник х - ромб», Т- множество ромбов. 4. D(х; у): «х+у=5». Множество истинности этого предиката может быть различным в зависимости от области определения. Если Х=R или Х=Z, то Т – множество пар чисел, сумма которых равна 5, причем это множество будет бесконечным. Если Х=N, то Т={(1;4), (2;3), (4;1), (3;2)}. 5. Q(х): «х<8», где хÎN, тогда Т={1;2;3;4;5;6;7}. Высказывательную форму, заданную на конечном множестве, можно задавать таблицей, в первой строке которой указываются элементы области определения, а во второй – истинно или ложно высказывание, получаемое из высказывательной формы при подстановке этих элементов вместо переменной. пример: пусть высказывательная форма А(х): «Число х - нечетно» задана на множестве Х={1; 2; 3; 4; 5; 6}. Так как высказывание «Число 2 - нечетно» ложно, то числу 2 будет соответствовать значение высказывательной формы «л» (ложь). Числу 1 соответствует истинное высказывание «Число 1- нечетно». Следовательно, высказывательная форма обращается в высказывание при подстановке конкретных значений из области определения вместо каждой переменной, входящей в форму. Но высказывательную форму можно превратить в высказывание и другим способом.