1 Логика (Математическая логика и теория алгоритмов) Ассистент кафедры МиИ Виноградова Марина Николаевна. - презентация

1 1 Логика (Математическая логика и теория алгоритмов) Ассистент кафедры МиИ Виноградова Марина Николаевна

2 2 Логика – наука, которая изучает, каким образом человек выражает мысли и делает выводы и как всё это можно представить формально.

3 3 Разделы логики: Теория множеств; Логика высказываний; Логика предикатов; Алгебраическая логика; Интуиционистская логика; Модальная логика; Логика неполных знаний; Логика ограниченных ресурсов; Динамическая логика; Вероятностная и нечёткая логика и пр.

4 4 1.1 Введение в теорию множеств Множество - совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое. Объекты, которые образуют множество, будем называть элементами множества и обозначать, как правило, малыми буквами латинского алфавита. М={m 1,m 2,m 3,m 4 }

5 5 m принадлежит М, то m M, m не является элементом M, m M Примеры: N = {1,2,3….} – множество натуральных чисел; А = {х: |Sin x|=1} – множество решений уравнения |Sin x|=1. Множества бывают конечными и бесконечными. Число элементов в конечном множестве М наз. мощностью М - |M| Если множество не содержит элементов, то это пустое множество - или V.

6 6 Конечные множества разделяются на счетные - если элементы нумеруются с помощью натурального ряда чисел несчетные – если нельзя пронумеровать Примеры: множество четных чисел – счетное, множество действительных чисел – несчетное

7 7 Конечные и счетные множества называются дискретными множествами. Дискретная математика – математика дискретных множеств.

8 8 Множество М' называется подмножеством множества М тогда и только тогда, когда любой элемент множества М' принадлежит множеству М: М' М (m M' m M) Множества А и В равны(равносильны), если их элементы совпадают: А В и В А А=В

9 9 Любое множество есть подмножество самого себя - несобственное Если А В и А В, то А - собственное, строгое или истинное подмножество В: А В Пример: Пусть А={а 1, а 2, а 3 }. Подмножества {а 1, а 2, а 3 } и Ø – несобственные подмножества А. Собственные: {а 1 }, {а 2 }, {а 3 }, {а 1, а 2 }, {а 1, а 3 }, {а 2, а 3 }.

10 10 Число подмножеств любого конечного множества, содержащего n элементов, равно 2 n Множество А - множество-степень (или множество всех подмножеств) (2 A ), если оно включает все возможные подмножества этого множества. Пример А = {1,2,3}; 2 А = {Ø,{1},{2},{3},{1,2},{1,3},{2,3},A}

11 11 Множество всех элементов, которые могут встретиться в данном исследовании, называют универсальным - обозначают U или I.

12 12 Способы задания множеств: 1. Перечислением (списком своих элементов) М={m 1,m 2,m 3,m 4 } 2. Задание свойств - имеется некоторое свойство p, такое, что для каждого элемента а множества А можно установить обладает ли а свойством p или нет А={a| a=p}

13 13 Свойства множеств: 1., V – конечное множество Множество всех элементов – универсальное U, I 2. Из определения множества следует, что в нем не должно быть неразличимых элементов, например: М={2,2,3,5} – 1 и 2 элемент одинаковы. 3. местоположение элемента в множестве строго не определено

14 Операции над множествами. Диаграммы Эйлера-Венна универсальное множество совместныенесовместные

15 15 Объединение множеств А и В (сумма множеств А и В) - множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В: А В=А+В={х | х А или х В}. Операция верна для любого количества множеств. А В=В А; (А В) С=А (В С) А А=АА =АА I=I А (А В), но неверно А (А В), запись а (А В)

16 16

17 17 Пересечение множеств А и В(произведение множеств А и В) - множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству А, так и множеству В: А В=А·В={х| х А и х В}. Операция верна для любого количества множеств. А В=В А;(А В) С=А (В С) А А=АА А I=А

18 18

19 19 Множества А и В находятся в общем положении, если выполняются три условия: существует элемент множества А, не принадлежащий В; существует элемент множества В, не принадлежащий А; существует элемент принадлежащий как А, так и В. Между А и В может быть пять отношений: 1.А=В, тогда А В=А=В; 2. А В, тогда А В=А; 3. В А, тогда А В=В; 4. Когда А и В - несовместные, тогда А В= ; 5. Множества А и В в общем положении. (верно только для двух множеств)

20 20 Разность множеств А и В - это множество, состоящее из всех тех и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В: А\В={x|x A и x B} А\В В\А А\ =АА\I= Если А\В=, то можно записать А В. Симметрическая разность множеств А и В – множество А В=АВ=(А\В) (В\А) А В=В АА (В С)=(А В) С

21 21

22 22 Операция дополнения – дополнение множества А до универсального множества I. _ А={x|x I и x A} _ _ А А= А А=I _ _ А\В={x|x А и x B}={x|x A и x B}=A B

23 23

24 24 Для алгебры множеств верны законы: 1. Коммутативный А В=В А; А В=В А 2. Ассоциативный А В С=А (В С)=(А В) С А В С=А (В С)=(А В) С 3. Дистрибутивный А (В С)=(А В) (А С) (А В) (А С)=А (В С) 4. Закон идемпотентности А А=А = 5. Закон двойного отрицания А=А

25 25 ____ _ _ ___ _ _ 6. Законы де Моргана А В = А В А В=А В _ _ 7. Законы склеивания (А В) (А В)=А; (А В) (А В)=А 8. Законы поглощения А (А В)=А; А (А В)=А _ _ 9. Законы Порецкого А (А В)=А В А (А В)=А В Следствия основных законов : _ _ А I=A ; A I=I ; A A= ; A A=I ; A = ; A =A

26 26 Порядок выполнения операций: дополнение пересечение объединение

27 27 Практические занятия Упражнение А={2,3,4,10}, В={1,2,10,12}, С={1,9,10}. а) AB+BC=Dб) (A+C) \ (BA)=E AB={2,10}, BC={1,10} и D={1,2,10}. A+C={1,2,3,4,10,12}, BA={2,10} и Е={1,3,4,12}.

28 28 Упражнение Пусть множество А состоит из точек M(x,y) плоскости, для которых |x|3 и |y|5, множество В – из точек плоскости, для которых x 2 +y 2 25, С – из точек плоскости, для которых x

29 29 Упражнение (решение) Как следует из условия множество А - прямоугольник, В – круг(О(0;0),R=5), С – полуплоскость AB\С – обрезанный прямоугольник

30 30 Упражнение A+АB=А(A+В)А=А формулы поглощения: АB А в первой формуле и А A+В во второй

31 31 Упражнение Упростить выражение

32 32 Упражнение (продолжение)

33 33 Упражнение Среди 100 деталей прошли обработку на первом станке 42 штуки, на втором – 30 штук, а на третьем – 28. Причем на первом и втором станках обработано 5 деталей, на первом и третьем – 10 деталей, на втором и третьем – 8 деталей, на всех трех станках обработано три детали. Сколько деталей обработано на первом станке и сколько деталей не обработано ни на одном из станков?

34 34 Упражнение множество всех деталей равно 100; А –на первом станке, В – на втором, С – на третьем 1: n(АВС)=3 2: n(АВ)- n(АВС)=5-3=2 3: n(АС) – n(АВС)=10-3=7 4: n(ВС) – n(АВС)=8-3=5 5: 42-(3+2+7)=30 6: 30-(3+2+5)=20 7: 28-(3+7+5)=13

35 35 Системы множеств. Булеаном В(х) множества Х называется множество всех подмножеств множества Х. Пример:Х={0,1} B(X)={, {0},{1},{0,1}}. Разбиением R(X) множества Х называется система его подмножеств, в объединении дающая множество Х. Пример: Х={1,2,3,4,5} R1(X)={{1,2},{3,4,5}}, R2(x)={{1},{2,5},{3},{4}} Покрытием P(X) множества Х называется система его непустых подмножеств, в объединении дающая множество Х. Пример: Х={1,2,3,4,5} P1(X)={{1},{1,2,3},{3,4,5}}, P2(X)={{1,2},{2,3,4},{5}}

36 36 Упражнение Лекции по экономике посещают 20 студентов, по математике – 30. Найти число студентов, посещающих лекции по экономике или математике, если 1) лекции проходят в одно и то же время, 2) лекции проходят в разные часы и 10 студентов слушают оба курса.

37 Векторы и прямое произведение Упорядоченная пара определяется как совокупность, состоящая из 2-х элементов x и y, расположенных в определённом порядке.

38 38 1. Список, вектор, кортеж – упорядоченная совокупность объектов, причём объекты могут совпадать - порядок следования объектов (I=1,…,n ). Упорядоченное n-элементное множество, или список, рассматривается как точка в воображаемом n-мерном пространстве. При этом компоненты n-элементного кортежа рассматриваются как проекции этого кортежа на соответствующие оси n-мерного пространства

39 39 Пр 1 (а 1, а 2, а 3 )=а 1 Пр 2 (а 1, а 2, а 3 )=а 2 Пр 3 (а 1, а 2, а 3 )=а 3 Пример: М={(1,2,3,4,5),(2,1,3,5,5),(3,3,3,3,3)} Тогда Пр 2 М={2,1,3}, Пр 2,4 М={(2,4),(1,5),(3,3)}

40 40 2. Прямым произведением множеств А и В(декартово произведение множеств) называют множество, обозначаемое А В и состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству А, а вторая множеству В, элементами прямого произведения являются двухэлементные кортежи вида (а,b) А В В А Пример: А={1,2,3} B={2,3,1} C={3,1,2} A B C={(1,2,3),(1,3,3),(1,1,3),…}

41 41 Если А и В- множества вещественных чисел, то прямое произведение А В графически можно изобразить в виде прямоугольника. Произведение 3-х множеств вещественных чисел графически выглядит как куб.

42 42 3. Бинарным отношением на множестве A называется произвольное подмножество R, где. Пример: (из таблицы реляционных баз данных) -бинарная таблица х – столбец, определяет свойства объекта, у – строка, определяет экземпляр объекта.

43 43 Областью определения DR отношения R назыв стр 14

44 44 Операции на отношениях Приведенные ниже операции являются системными, то есть определяют возможные действия, неважно над чем производимые. Объединение состоит из всех пар, таких что или Пересечение состоит из всех пар, таких что и

45 45 Произведение состоит из таких пар, для каждой из которых существует элемент с, такой что и Дополнение отношение, состоящее из всех пар, принадлежащих множеству- степени, но не принадлежащую R Обратное отношение R -1 - отношение, которое состоит из пар, таких что

46 46 Свойства отношений Отношения R называется рефлексивным, если для любого а М имеет место а R а. Отношение R называется антирефлексивным, если ни для какого а М не выполняется а R а. Отношение и «иметь общий делитель» рефлексивны, отношение < и «быть сыном» антирефлексивны. Главная диагональ матрицы рефлексивных отношений содержит только 1.

47 47 Отношение R называется симметричным, если для пары (а,b) М 2 из а R b следует b R a (иначе говоря, для любой пары R выполняется либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: сij=cji для любых i и j. Отношение R называется антисимметричным, если из ai R aj и aj R ai следует, что ai=aj. Пример антисимметричного отношения - отношение : действительно, если a b и b a, то a=b. Отношение R симметрично тогда и только тогда, когда R=R -1.

48 48 Отношение R называется транзитивным, если для любых a, b, c из aRb и bRc следует aRc. Отношение = - транзитивно, a=b и b=c, следует a=c. Отношение «быть сыном»- нетранзитивно - а сын b, b сын с, не следует а сын с.

49 49 Для любого отношения R отношение Ȓ, называемое транзитивным замыканием, определяется следующим образом: a Ȓ b, если в М существует цепочка из n элементов а=а 1, а 2,…, а n-1, а n =b, в которой между соседними элементами выполнено R: a R а 2, а 2 R а 3,…, а n-1 R b. Если R транзитивно, то R= Ȓ и Ȓ =R.

50 50 Пример: Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т.д.

51 51 Отношение эквивалентности. Отношение называется отношением эквивалентности (обозначается (~)), если оно рефлексивно, симметрично и транзитивно. Пример: Отношение равенства (=) на любом множестве является отношением эквивалентности. Равенство - минимальное отношение эквивалентности. Формулу вида (a+b)(a-b)=a 2 -b 2 обычно называют отношением равносильности и определяют следующим образом: формулы равносильны, если они задают одну и ту же функцию.

52 52 Пусть на множестве М задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент а 1 М и образуем класс (подмножество М) с 1, состоящий из а 1 и всех элементов, эквивалентных а 1 ; затем выберем элемент а 2 с 1 и образуем класс с 2, состоящий из а 2 и всех элементов, эквивалентных а 2, и т.д.

53 53 Получится система классов с 1, с 2,…, (возможно бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т.е. ci=M. Эта система классов обладает следующими свойствами: –Она образует разбиение, т.е. классы попарно не пересекаются; –Любые два элемента из одного класса эквивалентны; –Любые два элемента из разных классов неэквивалентны.

54 54 Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности R. Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению к R. Мощность этой системы называется индексом разбиения.

55 55 Отношение порядка. Отношение называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно: х х – истина (рефлексивность); х y и y x x=y (антисимметричность); x y и y z x z (транзитивность).

56 56 Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно: x

57 57 Элементы a,b сравнимы по отношению порядка R, если выполняется a R b или b R a. Множество М, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае. Отношения и, полностью упорядочивают множества. Примеры: 1)Отношение подчиненности на предприятии задает строгий частичный порядок. В нем несравнимыми являются сотрудники разных отделов; 2)Русский алфавит- строгий полный порядок.

58 58 Отношение доминирования. Если x доминирует над y, то обозначает x>>y, т.е. x значительно превосходит y. Между элементами множества имеет место отношение доминирования, если эти элементы обладают следующими свойствами: 1)Никакой индивидуум не может доминировать над самим собой, т.е. х>>х ложно; 2)В каждой паре индивидуумов в точности один индивидуум доминирует над другим, т.е. х>>y и y>>x взаимоисключается.

59 59 В отношении доминирования свойство х

60 Соответствия и функции Если М= A B, то Пр 1 М=А, а Пр 2 М=В. Соответствием между множествами А и В – называется подмножество G A B. Если (а, b) є G, то говорят, что b соответствует а при соответствии G. Множество Пр 1 G - область определения соответствия, множество Пр 2 G – область значений соответствия

61 61 Если Пр 1 G =А, то соответствие называется всюду определенным или полностью определенным (в противном случае соответствие называется частичным); если Пр 2 G =В, то соответствие называется сюръективным Множество всех b B, соответствующих элементу а А - образ а в В при соответствии G Множество всех а, которым соответствует b, - прообраз b в А при соответствии G

62 62 Соответствие G - функциональное (или однозначное), если образом любого элемента из Пр 1 G является единственный элемент из Пр 2 G. Соответствие G между А и В - взаимно однозначное, если оно всюду определено, сюръективно, функционально, и прообразом любого элемента из Пр 2 G является единственный элемент из Пр 1 G

63 63 Примеры: 1)Англо-русский словарь - не является функциональным, не полностью определенное 2)Позиция на шахматной доске представляет собой взаимно однозначное соответствие между множеством оставшихся на доске фигур и множеством занятых ими полей 3)Соответствие телефонов и номеров. Это соответствие обладает всеми свойствами взаимно однозначного соответствия кроме - сюръективности. Так как не все номера соответствуют телефонам (есть пустые номера).

64 64 Множества равномощны, если между их элементами можно установить взаимно однозначное соответствие. Множества равномощные с N - счетные, т.е. между множеством существует взаимно однозначное соответствие с натуральным рядом чисел. Множество всех действительных чисел, даже определенных на отрезке, не является счетным. Мощность несчетных множеств наз. континуум; множества такой мощности - континуальные.

65 65 Композиция соответствий - последовательное применение двух соответствий. Композиция соответствий есть операция с тремя множествами X,Y,Z на которых определены два соответствия. Например: Если 1-ое соответствие определяет распределение водителей по автомашинам, 2 –ое соответствие определяет распределение автомашин по маршрутам, то композиция соответствий определяет распределение водителей по маршрутам.

66 66 Отображение: записывается Г: А В. ГА - образ А в В Бинарное отношение f называется функцией (отображением), если из пары и следует у = z Область определения функции обозначается Df Область значений функции обозначается Rf

67 67 Функция называется инъективной, если для любых х 1, х 2, у из у=f(x1) и у=f(x2) следует, что х 1 = х 2

68 68 Функция называется сюръективной, если для любого элемента y Y существует элемент х Х, такой, что у=f(x)

69 69 Функция называется биективной, если функция одновременно инъективна и сюръективна

70 70 Способы задания функций. 1.Табличный- самый простой способ задания функции. Таблица это конечные списки пар (х,f(x)). 2.Формула, описывающая функцию как суперпозицию других исходных функций. 3. Если А и В множества вещественных чисел, то элементы (а,b) f можно изобразить в виде точек на плоскости. Совокупность таких точек представляет собой график функции. 4. Рекурсивная процедура задает функцию f, которую вычисляют последовательно по этапам, например, n!. 5. Возможны описания функции, которые не содержат способа вычисления функции, значение определяется сразу.

71 71 Практические занятия Упражнение Установить биективное отображение между множеством точек плоскости и множеством точек сферы, из которой выброшена одна точка.

72 72 множество точек плоскости Р, множество точек сферы – М, точка А выброшена из сферы, x M, y P Соединить точку В лучом с точкой «х» и получить соответствующую точку «y», или точку В соединить с точкой «y» и получить соответствующую точку «х», т.е. «х»«y».

73 73

74 74 Математическая логика Высказывание – предложение, относительно которого можно утверждать, истинно оно или ложно. «5>1», «13 делится на 5» – высказывания. Дадим определение формулы алгебры высказываний: 1) отдельно стоящая буква A, B, C,..., X, Y, Z – формула. 2) если А, В – формулы, то формулами являются и (А), (В), (А В), (А В), (АВ), (АВ). 3) Других формул нет.

75 75 Две формулы алгебры высказываний называются равносильными, если на всех одинаковых наборах значений составляющих переменных высказываний они принимают одинаковые значения 1 или 0. Логическая функция f(х 1,х 2,…,х n ) – это функция, принимающая значение 0,1, от логических переменных (х 1,х 2,…,х n ), х i є{1,0}.

76 76 Всякая логическая функция n переменных может быть задана таблицей – истинности: в левой части - 2 n наборов значений переменных, в правой части значения функции

77 77 1. Дизъюнкция - логическая операция, которая определяет логическое соединение двух логических высказываний с помощью союза ИЛИ. Названия: дизъюнкция, логическое сложение, «ИЛИ». Обозначается знаками, +. Значение составного высказывания =1, если хотя бы значение одного высказывания =1 А В А v В

78 78 2. Конъюнкция (логическое умножение) - определяет соединение двух логических высказываний с помощью союза И. Обозначение: &,,, или как умножение без знака. Значение составного высказывания=0, если хотя бы значение одного высказывания =0 А В А & В

79 79 3. Отрицание или инверсия (или функция «НЕ»). А А Равносильна операции дополнения на множествах I и. Обозначается, х, х, х. Значение функции противоположно значению х.

80 80 4.Импликация, логическое следование. Обозначается х 1 х 2, х 1 х 2. Читается «если х 1, то х 2». Операцию импликации можно разложить: f=х 1 х 2= х 1+х 2= (х 1 х 2 ) А В А => В

81 81 5. Функция Вебба или стрелка Пирса. Еще называется отрицание дизъюнкции, «ИЛИ-НЕ». f=х 1 х 2=х 1 х 2= (х 1+х 2). Значение составного высказывания =0, если значение хотя бы одного высказывания =1 Х1Х1 Х2Х2 Х 1 Х

82 82 6. Функция Шеффера (штрих Шеффера) или «И-НЕ». f=x1|x2= x1+ x2= (x1x2). Значение составного высказывания =1, если значение хотя бы одного высказывания = 0 Х1Х1 Х2Х2 Х 1 |Х

83 83 7. Функция эквивалентности или равнозначности. f=x1~x2=x1 x2= x1 x2+x1x2. Значение составного высказывания =1, если значения высказываний равны, и значение составного высказывания =0, если значения высказываний не равны А В А В

84 84 8. Функция «сложение по модулю 2» или функция неравнозначности. f=x1 x2=x1 x2= x1x2+x1 x2 Значение составного высказывания будет =1, если значения высказываний не равны, и будет =0, если значения высказываний равны Х1Х1 Х2Х2 Х 1 Х

85 85 Порядок выполнения логических операций в сложном логическом выражении: 1. инверсия ; 2. конъюнкция & (или ^); 3. дизъюнкция v; 4. импликация =>; 5. эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

86 86 Основные свойства булевых операций: Ассоциативность: х 1 (х 2 х 3 )=(х 1 х 2 )х 3 х 1 +(х 2 +х 3 )=(х 1 +х 2 )+х 3 ; Коммутативность: х 1 х 2 =х 2 х 1 х 1 +х 2 =х 2 +х 1 ; Дистрибутивность дизъюнкции относительно конъюнкции: х 1 +(х 2 х 3 )=(х 1 +х 2 )(х 1 +х 3 ); Дистрибутивность конъюнкции относительно дизъюнкции: х 1 (х 2 +х 3 )=х 1 х 2 +х 1 х 3 ;

87 87 Идемпотентность: хх=х х+х=х; Двойного отрицания: х=х; Свойства констант: х·1=х х·0=0 х+1=1 х+0=х 0=1 1=0; Правила де Моргана: (х 1 х 2 )= х 1 + х 2 (х 1 +х 2 )= х 1 х 2 ; Закон противоречия: х х=0; Закон «исключения третьего»: х+ х=1.

88 88 Упрощение формул: 1. Поглощение: x+xy=x x(x+y)=x Докажем х+xy=x(1+y)=x·1=x x(x+y)=xx+xy=x+xy=x; 2. Склеивание: xy+x y=x Докажем xy+x y=x(y+ y)=x·1=x; 3. x+ xy=x+y 4. Обобщенное склеивание: хz+y z+xy = xz+y z

89 89 Рассмотрим пример построения таблицы истинности для следующего сложного (составного) логического выражения D = А & (В v С). Сначала нужно установить число строк и столбцов такой таблицы, то есть спланировать форму таблицы. Число переменных в формуле равно n=3, следовательно, таблица истинности будет содержать 2 n =2 3 =8 и одна строка для «шапки» таблицы.

90 90 ABCAB v CА & (В v С)

91 91 Функция f(x 1,... x i-1, x i, x i+1,... x n ) существенно зависит от переменной x i, если найдутся два набора σ 1,σ 2 отличающиеся только одной переменной x i такие, что f(σ 1 )f(σ 2 ). В этом случае переменная x i является существенной переменной и фиктивной в противном случае.

92 92 Виды формул алгебры высказываний и их классификации Формула А называется общезначимой (тождественно истинной, тавтологией), если во всех своих интерпретациях она принимает значение «истина» (1). Формула А называется невыполнимой (тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение «ложь» (0). Формула А называется нейтральной, если она не является ни общезначимой, ни невыполнимой. Формула А называется выполнимой, если она общезначимая или нейтральная. Формула А называется необщезначимой, если она невыполнимая или нейтральная.

93 93 Проверка правильности рассуждений Говорят, что из P следует Q, если Q истинно всякий раз, когда истинно P; Q называют следствием P. Две формулы алгебры высказываний называются равносильными (эквивалентными), если на всех одинаковых наборах значений составляющих переменных высказываний они принимают одинаковые значения 1 или 0.

94 94 Методы установления общезначимости формул 1. Метод построения таблиц истинности Для каждой формулы выделяются атомы и подформулы, затем вычисляется значение самой формулы. Пример: Общезначима ли формула: A, B, C – атомы; 1, 2, 3, 4, 5, 6 – подформулы

95 95 Таблица истинности в своем последнем столбце содержит только 1, значит, эта формула общезначима. АВС

96 96 2. Метод от противного Под логическим уравнением будем понимать равенство вида f1=f2, где f1 и f2 – формулы алгебры высказываний или одно из истинных значений (1 или 0). Решить логическое уравнение означает найти все те наборы истинностных значений атомов, входящих хотя бы в одну из формул f1 или f2, при которых имеет место равенство f1 = f2.

97 97 Пример: Общезначима ли формула Допустим, что данная формула не общезначима. Тогда должен существовать хотя бы один набор значений формул А, В, С, при котором формула примет значение 0, т.е. должно иметь решение логическое уравнение:

98 98 По определению истинности импликации имеем единственный ложный набор 1 0, тогда: Значит, наше допущение о том, что формула не общезначима – неверно.

99 99 3. Метод равносильных преобразований (или натурального исчисления) Сущность метода состоит в применении различных законов и равносильностей математической логики. В итоге, после преобразований, общезначимая формула будет упрощена до значения «истина».

100 100 Полные системы связок Система связок логики высказываний называется полной, если всякая формула логики высказываний равносильна некоторой формуле, содержащей лишь связки этой системы.

101 101 Пример Проиллюстрировать полноту связок (V,¯) S1=x ӯ V(yx); S2=xy V z Очевидно, в данных формулах нужно заменить все связки, кроме (V,¯) а) Преобразуем S1 Применяя формулу поглощения, получим

102 102

103 Совершенные нормальные формы. Разложение функций по переменным

104 104 Элементарной называется нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые.

105 105 Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ). Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ).

106 106 Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

107 107 Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно, с отрицанием).

108 108

109 109 Теорема алгебры логики Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ. Константа 0 может быть представлена только СКНФ, а константа 1 только СДНФ

110 110 Для каждой формулы алгебры высказываний можно найти множество ДНФ и КНФ. Для этого нужно: 1. Избавиться от всех логических операций, содержащихся в формуле, заменив их основными – конъюнкцией, дизъюнкцией, отрицанием, используя равносильные формулы:

111 Заменить знак отрицания выражения, знаками отрицания, относящимся к отдельным переменным высказываниям на основании формул: 3. Избавиться от знаков двойного отрицания на основании равенства 4. Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности.

112 112

113 113

114 114 Алгоритм получения СКНФ по таблице истинности 1. Отметить те строки таблицы истинности, в последнем столбце которых стоит 0:

115 Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание:

116 Все полученные дизъюнкции связать в конъюнкцию:

117 117 Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики:

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

119 119 Исчисление высказываний методом естественного вывода Рассмотрим задачу доказательства того, что заключение следует из некоторых посылок. Пример: доказать, что следует из Запишем эту задачу в следующем виде. Посылка: Заключение:

120 120 Ход рассуждений: свойство конъюнкции заключается в том, что если истинно, то истинны p и g; свойство дизъюнкции заключается в том, что для любого r истинно, если g истинно, так что истинно. поскольку и p и истинны, по свойству конъюнкции также истинно.

121 121 Формальное доказательство: Из получить В каждой строке записывается высказывание, которое истинно. Справа от высказывания записывается объяснение, как выведена его истинность. 1.пос p св., 1 3. g св., 1 4. св., 3 5. св., 2, 4

122 122 Правила вывода Метод естественного вывода содержит десять правил. В этом методе имеется по два правила вывода для каждой из пяти операций,,,,. Правило введения обозначается через I, правило удаления – Е. 1. – I: Если Е 1,…,Е n встречаются на предшествующих строках доказательства и доказано, что они истинны, то их конъюнкция может быть записана в данной строке и Е 1... Е n – истинно.

123 – Е: Если Е 1 … Е n встречается на пред ыдущих строках и оно истинно, то Е i можно записать в данной строке и Е i - истинно. 3. – I: Если на предшествующей строке записано Е i и оно истинно, то в данной строке можно записать Е 1 … Е n и оно истинно.

124 – Е: Если на предшествующей строке встречается дизъюнкция и если на предшествующих строках для каждого дизъюнктивного члена Е i стоят Е i Е, то на данной строке доказательства можно записать Е и оно истинно.

125 – Е: Если импликация и ее посылка встречаются в предшествующих строках, то в данной строке можно записать заключение импликации и оно истинно. 6. – I: 7. – Е: 8. – I:

126 126 Доказательство от противного 9. - I: Если «» доказано для некоторого высказывания Е 1, то можно написать на очередной строке доказательства Е: Если «» доказано для некоторого высказывания Е 1, то Е можно написать на очередной строке доказательства.

127 127 Минимизация формул алгебры высказываний Цель минимизации: сократить число операций и получить более простую функцию по отношению к исходной 1. С помощью эквивалентностей и упрощений не всегда получается минимальная функция сначала привести функцию к ДНФ

128 Геометрическая минимизация

129 129

130 Методы минимизации: 1)Метод Квайна. Этапы метода: 1.1. По таблице истинности или с помощью разложения по всем переменным получить СДНФ. Провести склеивание элементарных конъюнкций 1.2. Проверим полученную функцию на покрытие

131 131 Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

132 132 Аналогично для КНФ: Возможность поглощения следует из очевидных равенств

133 133

134 134

135 135 2)Метод карт Карно Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Каждая из входных переменных делит карту Карно на две разные части, в одной из которых значение этой переменной равно 1, а в другой 0. Число клеток карты Карно равно числу таблицы истинности, т.е. 2 n, где n – число входных переменных.

136 136 Карты Карно для одной и двух переменных:

137 137

138 138

139 139

140 140 Наборы значений переменных для клеток, стоящих рядом (соседние клетки), отличаются значением лишь одной переменной. Минимизация функции по карте Карно в классе ДНФ заключается в покрытии ее единиц минимальным количеством максимальных правильных контуров. Контуры могут пересекаться, но не могут включатся друг в друга

141 141 Правильные контуры для карты 4-х переменных Двухклеточный – две соседние клетки, содержащие единицы Четырехклеточный – квадрат из четырех соседних клеток, содержащие единицы Восьмиклеточный – куб из соседних клеток, содержащие единицы Сверхкуб(гиперкуб) – соответствует вырожденной функции четырех переменных (нет ни одного нуля). Используется для функций 5 и более переменных.

142 142

143 143 F(х 1,х 2, х 3,х 4 )=0000 v 0010 v 0101 v 1101 Наборы 0000 и 0010 склеиваются по переменным х 1,х 2,х 4 (00-0); Наборы 0101 и по переменным х 2,х 3,х 4 (-101) В итоге: F(х 1,х 2, х 3,х 4 )=

144 144

145 145

146 146 Пример У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников. Для краткости обозначим родственников Коли через буквы: мама х 1 папа х 2 дедушка х 3 бабушка х 4 Условимся обозначать согласие родственников единицей, не согласие нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять f = 1, Коля гулять не идёт f = 0. Составим таблицу истинности:

147 147

148 148

149 149

150 150 Полнота Любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные) хi, операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки (,)

151 151 Система функции S - функционально полная система, если любая логическая функция может быть представлена формулой над S, т.е. является суперпозицией функции из S. Система S - базис, если теряется полнота S при удалении хотя бы одной функции. Пример: Системы S1 = {&, ¯} и S2 = {V, ¯} функционально полны

152 152 Техническая реализация базисных функций основана на использовании различных физических явлений, например, импликация и коимпликация – магнитных, функции Шеффера и Вебба (Пирса) – явлений в полупроводниках.

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

154 154 Логические элементы компьютера & 11 & НЕ(инвертор) ИИЛИ ИЛИ-НЕ (Функция Вебба или стрелка Пирса) И-НЕ (функция Шеффера) значок инверсии

155 155 Логические элементы компьютера Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ. & И:И: НЕ: & & ИЛИ: & & &

156 156 Составление схем последняя операция - ИЛИ & 1 & & И И

157 157 Триггер (англ. trigger – защёлка) Триггер – это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ. Самый распространенный тип триггера – RS-триггер 1 1 основной выход вспомогательный выход reset, сброс set, установка обратные связи SRQ режим хранение запрещен сброс установка 1 0 0

158 158 Полусумматор Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа. Σ сумма перенос ABPS &1&&

159 159 Сумматор Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда. Σ сумма перенос ABCPS

160 160 Многоразрядный сумматор это логическая схема, способная складывать два n-разрядных двоичных числа. перенос Σ Σ Σ

161 161 Логические основы компьютеров Логические задачи

162 162 Метод рассуждений Задача 1. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты договора, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы: Россия "Проект не наш (1), проект не США (2)"; США "Проект не России (1), проект Китая (2)"; Китай "Проект не наш (1), проект России (2)". Один из них оба раза говорил правду; второй – оба раза говорил неправду, третий один раз сказал правду, а другой раз неправду. Кто что сказал? (1)(2) Россия США Китай проект России (?) – + – – + + (1)(2) Россия США Китай проект США (?) + – (1)(2) Россия США Китай проект Китая (?) + –

163 163 Табличный метод Задача 2. Дочерей Василия Лоханкина зовут Даша, Анфиса и Лариса. У них разные профессии и они живут в разных городах: одна в Ростове, вторая – в Париже и третья – в Москве. Известно, что Даша живет не в Париже, а Лариса – не в Ростове, парижанка – не актриса, в Ростове живет певица, Лариса – не балерина. Париж РостовМосква ПевицаБалерина Актриса Даша Анфиса Лариса В каждой строке и в каждом столбце может быть только одна единица! ! Много вариантов. Есть точные данные. Много вариантов. Есть точные данные.

164 164 Задача Эйнштейна Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному человеку отличной от другого национальности. Каждый жилец пьет только один определенный напиток, курит определенную марку сигарет и держит животное. Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты и не держит одинаковых животных. Известно, что: 1. Англичанин живет в красном доме. 2. Швед держит собаку. 3. Датчанин пьет чай. 4. Зеленой дом стоит слева от белого. 5. Жилец зеленого дома пьет кофе. 6.Человек, который курит Pallmall, держит птицу. 7. Жилец среднего дома пьет молоко. 8. Жилец из желтого дома курит Dunhill. 9. Норвежец живет в первом доме. 10. Курильщик Marlboro живет около того, кто держит кошку. 11.Человек, который содержит лошадь, живет около того, кто курит Dunhill. 12. Курильщик Winfield пьет пиво. 13. Норвежец живет около голубого дома. 14. Немец курит Rothmans. 15. Курильщик Marlboro живет по соседству с человеком, который пьет воду. Вопрос: У кого живет рыба?

165 165 Использование алгебры логики Задача 3. Следующие два высказывания истинны: 1. Неверно, что если корабль A вышел в море, то корабль C – нет. 2. В море вышел корабль B или корабль C, но не оба вместе. Определить, какие корабли вышли в море. … если корабль A вышел в море, то корабль C – нет. 1. Неверно, что если корабль A вышел в море, то корабль C – нет. 2. В море вышел корабль B или корабль C, но не оба вместе. Решение:

166 166 Использование алгебры логики Задача 4. Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Мастер по ремонту сказал, что с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось? Решение: A – неисправен процессор, B – память, C – винчестер хозяин: сын: мастер: Если ошибся хозяин: Если ошибся сын: Если ошибся мастер: В общем случае: Несколько решений! !

167 167 Логические схемы - Моделирование алгебры высказываний с помощью релейно-контактных схем В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. Переключательная схема (релейно- контактная схема ) это схематическое изображение некоторого устройства, состоящего из переключателей(контактов) и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал. Каждый переключатель имеет только два состояния: замкнутое и разомкнутое

168 168 Логическая функция - функция проводимости электрической цепи Основные логические связки моделируются следующими элементарными схемами: V

169 169 Упражнение Построить функцию проводимости следующей схемы: F(x,y,z)=(x ˅ y)z ˅ (z ˅ y)