Методические рекомендации по дисциплине "Элементы математической логики"

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ Государственное автономное профессиональное образовательное учреждение города Москвы «ТЕХНОЛОГИЧЕСКИЙ КОЛЛЕДЖ № 24» МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ по проведению и оформлению практической работы  по дисциплине «Элементы математической логики» для студентов специальности  09.02.04 «Информационные системы (по отраслям)» Москва 2016 Рассмотрено предметной цикловой методической комиссией  ЕН Протокол № ___ от ___________ 2016 г Председатель ЦМК ___________ Пятаева Е.В. Составитель:             Чернышова Г.Б. Рецензент: Мельникова С.М. Настоящие методические рекомендации определяют общие требования, структуру и   правила   оформления   практических   работ   в   соответствии   с   действующими стандартами.   Методические   рекомендации   по   проведению   и   оформлению практических   работ   предназначены   для   использования   студентами   СПО   при выполнении практических работ по дисциплине «Элементы математической логики». Содержание   методических   рекомендаций   охватывает   следующие   разделы программы: теория множеств, формулы логики, булевы функции, предикаты элементы теории алгоритмов. Для   студентов   колледжей,   обучающихся   по   специальности   09.02.04 «Информационные системы (по отраслям)». 2 Введение……………………………………………………..…..………4 1. Пояснительная записка……………………………………………5 1.1. Назначение методических указаний………..……...……………5 1.2.  Требования к знаниям и умениям при выполнении практических работ.……………..…………………………………..6 1.3. Правила выполнения практических работ………… …………..5 1.4.  Критерии оценок…………………… ……………………...……7 2. Перечень практических работ……………………………...…….9 2.1 Практическая работа №1………….……………………………10 2.2 Практическая работа №2………………………………..………14 2.3 Практическая работа №3………………………………………..18 2.4 Практическая работа №4………………………………………..21 2.5 Практическая работа №5………………………………………..26 2.6 Практическая работа №6………………………………………..29 2.7 Практическая работа №7………………………………………..31 2.8 Практическая работа №8………………………………………..33 Список использованной литературы…………..……………36  3. Введение 3 Одним   из   основных   видов   учебных   занятий   является   практическое занятие, которое направлено на формирование учебных и профессиональных практических умений. Состав и содержание практического занятия определяется его ведущей дидактической целью ­ формирование практических умений:  профессиональных   ­  выполнять   определенные   действия,   операции, необходимые в последующем в профессиональной деятельности;  учебных  ­ решать задачи по математической логике, необходимые в последующей учебной деятельности. Состав и содержание практических занятий направлены на реализацию государственных требований к минимуму содержания и уровню подготовки выпускников.   Они   охватывают   весь   круг   профессиональных   умений,   на подготовку   к   которым   ориентирована   конкретная   дисциплина   и   вся подготовка специалиста. В   практических   работах   указана   цель,   пояснения   (основные определения   и   формулы),   примеры     с   подробными   решениями,   порядок выполнения работы, список литературы.  При выполнении  работы  студент самостоятельно выбирает способ выполнения каждого задания. На   практических   занятиях   студенты   овладевают   первоначальными профессиональными   умениями   и   навыками,   которые   в   дальнейшем   будут закрепляться в процессе обучения.  Тематика, содержание и количество часов, отводимое на практические занятия,   отражены   в   рабочей   программе   дисциплины   «Элементы математической логики». Состав практических заданий планируется с таким расчетом,   чтобы   за   отведенное   время   студенты   смогли   их   качественно выполнить. Методические рекомендации по проведению практических занятий  содержат: 4 1. ­ ­ ­ ­ 2. Инструкцию к выполнению практических работ, включающую: цель работы; пояснения (теория, формулы, основные понятия); порядок выполнения заданий; учебную литературу. Критерии оценки выполненных работ.  Практические сопровождающиеся   методическими рекомендациями,   применительно   к   конкретным   специальностям   включая   работы,   подбор дополнительных примеров и  задач. Все   это   повышает   ответственность   каждого   студента   за самостоятельное выполнение полного объема практических работ, повышает качество подготовки студента. 1. Пояснительная записка 1.1.Назначение методических указаний При   изучении   учебной   дисциплины   наряду   с   теоретическими занятиями необходимо проведение практических занятий.  Практические занятия относятся к основным видам учебных занятий. Они составляют важную   часть   профессиональной   практической   подготовки   студентов   и проводятся в конце изучения определенной темы. Цель   проведения   практических   занятий   –   закрепление   знаний студентов   по   основным   вопросам   учебной   дисциплины   «Элементы математической логики».   Практические   занятия   способствуют   интенсификации   учебного процесса,   более   осмысленному   изучению   материала,   превращению фрагментарных   знаний   студентов   в   системные.   Они   способствуют развитию познавательной деятельности студентов, развивают логическое 5 мышление,   умение   интерпретировать   теоретический   материал   для решения поставленной задачи. Выполнение   практических   заданий   требует   предварительной подготовки в виде повторения теоретических вопросов. Содержание практических занятий охватывает весь круг умений, на формирование которых ориентирована данная дисциплина. Методические указания   по   выполнению   практических   работ   учебной   дисциплины «Элементы   математической   логики»   составлены   с   учётом   требований рабочей программы и её содержания. 1.2.  Требования   к   знаниям   и   умениям   при   выполнении практических работ В   результате   выполнения   практических   работ,   предусмотренных программой по данной специальности, студент должен  знать: основные принципы математической логики, теории множеств и теории алгоритмов; формулы логики высказываний; методы минимизации эквивалентных преобразований; уметь: формировать   задачи   логического   характера   и   применять   средства математической логики для их решения; основы языка и алгебры предикатов. Практические   работы   рассчитаны   на   выполнение   в   течение   двух академических часов. 1.3. Правила выполнения практических работ 1.   Студент   допускается   к   выполнению   практической   работы   при отсутствии задолженности по предшествующей практической работе.  6 2. Работу следует выполнить в тетради для практических работ.  3. В работе необходимо  указать дату ее выполнения.     4. Не допускается выполнение работы в неполном объеме. 5.   Законченная   и   оформленная   работа   сдается   преподавателю   и засчитывается. 6.   Если   работа   выполнена   не   верно,   то   ее   аккуратно   перечеркивают   и выполняют   заново.   При   мелких   исправлениях   неправильный   символ (буква,   число)     аккуратно   зачеркивают   и   над   ним   пишут   правильный символ (буква, число).  7. Вспомогательные расчеты можно выполнить на отдельных листах.  8. Если студент не выполнил практическую работу или часть работы, то он может   выполнить   работу   или   оставшуюся   часть   во   внеурочное   время, согласованное с преподавателем. 9.   Оценку   по   практической   работе   студент   получает,   с   учетом   срока выполнения работы, если: ­   задание   выполнено   правильно   и   в   полном   объеме,  в   соответствии   с требованиями к выполнению работы; ­ студент может пояснить выполнение любого этапа работы. Зачет  по   практическим   работам   студент   получает   при   условии выполнения всех предусмотренной программой практических  работ после сдачи отчетов по работам. 1.4. Критерии оценок.  Оценка   «5»   ставится:   практическая   работа   выполнена   в   полном   с   соблюдением   в   соответствии   с   заданием, объеме,   последовательности выполнения, расчеты выполнены без ошибок, самостоятельно; работа оформлена аккуратно. 7  Оценка   «4»   ставится:   практическая   работа   выполнена   в   полном   с   соблюдением   частично   с   помощью объеме, последовательности   выполнения,     в   соответствии   с   заданием, преподавателя, расчетах; работа оформлена аккуратно.   присутствуют   незначительные   ошибки   при  Оценка   «3»   ставится:   практическая   работа   выполнена   в   полном   в   соответствии   с   заданием,   частично   с   помощью   присутствуют   ошибки   при   расчетах;   по объеме,   преподавателя, оформлению работы имеются замечания.  Оценка   «2»   ставится:   студент   не   подготовился   к   практической работе,   при   расчетах   допустил   грубые   ошибки,   по   оформлению работы имеются множественные замечания. Виды ошибок Грубые ошибки     1. Незнание определений основных понятий, законов, правил, основных положений теории, формул, общепринятых символов обозначения.     2. Неумение выделить в ответе главное.          3.   Неумение   применять   знания   для   решения   задач;   неправильно сформулированные   вопросы   задачи   или   неверные   объяснения   хода   ее решения; незнание приемов решения задач, аналогичных ранее решенных в классе, ошибки, показывающие неправильное понимание условия задачи или неправильное истолкование решения.      4.    Неумение читать и строить таблицы.     5. Неумение использовать полученные данные для выводов.  Негрубые ошибки     1. Неточности формулировок, определений, понятий, законов.     2. Неточности в построении таблиц истинности. 8 3. Нерациональный выбор хода решения. Недочеты        1. Нерациональные записи, нерациональные приемы преобразований и решений примеров.      2. Ошибки в преобразованиях и составлении таблиц, если эти ошибки грубо не искажают реальность полученного результата.      3. Отдельные погрешности в формулировке вопроса или ответа.   4. Небрежное выполнение записей.  2.  Перечень практических работ. Номер работы Наименование работы 1 2 3 4 5 6 7 8 Решение задач. Построение таблиц истинности. Упрощение   формул   логики   с   помощью равносильных преобразований Представление   булевой   функции   в   виде совершенной   ДНФ,   совершенной   КНФ, минимальной ДНФ. на Проверка принадлежность к классам Т0, T1, S, L, М;   функции     булевой проверка   множества   булевых   функций   на полноту Определение   логического   значения   для высказываний,   построение   отрицаний   к предикатам Рекурсивные функции Совпадения   класса   всех   нормально вычислимых   функций   с   классом   всех функций, вычислимых по Тьюрингу 9 Кол­во часов 2 2 2 2 2 2 2 2 Практическая работа №1 Тема: «Решение задач на выполнение теоретико­множественных операций» Продолжительность 2 часа Цель занятия: закрепление знаний студентов по теории множеств и умений выполнять действия над множествами. 1. Вопросы для обсуждения: Понятие множества; Операции пересечения, объединения и дополнения; Декартово произведение и декартова степень множества. 2. Методические рекомендации по теме занятия:       Одним из основных исходных понятий математики является понятие множества   и   его   элементов.   Множество   состоит   из   элементов. Множества обозначаются большими латинскими буквами: A; B; C..., а их элементы ­ малыми буквами: a,b,c,…        Если a является элементом множества A или, что то же самое, a принадлежит   множеству   A,     то   применяют   запись   aA;  в   противном случае пишут aA.       Два множества A и B равны  (A=B), если они состоят из одних и тех же элементов. Если множества A и B не равны, то применяется запись A  B. 10 Множество,   содержащее   конечное   число   элементов,   называется конечным,   в   противном   случае   множество   называется   бесконечным. Конечное   множество,   содержащее   n   элементов,   называется   n­ множеством.             Множество,   не   содержащее   элементов,   называется   пустым   и обозначается  .   Предположим,   что   все   множества   являются подмножествами некоторого множества U. Такое множества называют универсальным множеством. Рис.1 a b Если   каждый   элемент   аВ   и   аА,   то   В   называется   подмножеством множества А (рис.1,а). Записывают:  ВА.   Свойства включения 1. А А;    2. если  А В  и  ВС,  то АС  (рис. 1,b); 3. из двух включений ВА и А В следует, что А=В. Принято   считать,   что   пустое   множество   является   подмножеством любого множества. Если  В А  и при этом ВА, то этому соответствует запись В  А и В называется собственным подмножеством А.  Для   описания   множества   A,   состоящего   из   элементов   a1,a2,...,an,... применяется   запись   A={a1,a2,...,an,...},   причём  порядок  элементов   в фигурных скобках не имеет значения. 11 Множество можно задано так:   перечислением элементов;  указанием свойств, которым элементы должны удовлетворять. {x ∈A | x обладает свойством P(x)}       Объединением двух множеств А и В называется множество вида:  AB ={a / a A  или  a B} (рис.2,а).       Пересечением двух множеств А и В называется множество вида:  AB={a / a A  и   a B} (рис.2,b).       Если множества А и В  не имеют общих элементов, то AB=. Рис.2 a b Свойства операций объединения и пересечения 1. AB = ВА, AB = ВА (коммутативность); 2. (AB)С = A(BС),  (AB)С = A(BС) (ассоциативность).   3. A(BC)= (AB)  (AС); A(BC)= (AB)  (AС)  (дистрибутивность). Разность множеств А и В определяется следующим образом:   A\B ={a / aA и aB} (рис. 1.3, а). Рис.3 a b 12 Разность   не   обладает   свойством   коммутативности;   эта   операция также не является и ассоциативной.        Пользуясь понятием универсального множества, можно определить дополнение  A  ко множеству А,  как разность вида:   = U \ A (рис. 1.3, A б).            Симметрическая разность или кольцевая множеств сумма А и В определяется следующим образом:  A ⊕ B = (A\B) ∪ (В\А) Пример. Пусть в качестве универсального множества выступает множество  целых чисел Z и пусть А ­ это множество всех чётных чисел. Тогда  ­ это  A множество всех нечётных чисел. Пример. Найти A ∪ B, A ∩ B, A\B,  A × B, B × A. А = {7; 8; 9}, B = {7; 8; 10} Решение: A ∪ B = {7; 8; 9} ∪ {7; 8; 10}={7; 8; 9, 10} A ∩ B = {7; 8; 9} ∩ {7; 8; 10}={7; 8}  A × B  = {7; 8; 9} ∩ {7; 8; 10}={(7;7); (7;8); (7;10); (8;7); (8;8); (8;10); (9;7); (9;8); (9;10)} B × A  =   {7;   8;   10} ∩ {7;   8;   9}={(7;7);   (7;8);   (7;9);   (8;7);   (8;8);   (8;10); (10;7); (10;8); (10;9)} A\B = {7; 8; 9} ¿ {7; 8; 10}={9} 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками: 13 [6] Гл.1. §1.1, стр.14­45   4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Основы теории множеств». Подготовьте устные ответы на вопросы: а) Что понимают под множеством? b) Способы задания множеств. c) Какое множество называют пустым? Универсальным? d) Действия над множествами. e) Законы действий над множествами. Просмотрите образцы примеров. 5. Решите следующие задания: 1. Дано множество А = {х|x =  n3+7 n3+15 ; n ∈N }. Напишите три числа,  которые принадлежат множеству А. 2.Дано множество чисел х: А = {х|x =  n2+1 n2+4 ; n ∈N }. Определите,  принадлежат ли числа   2 5 ;    5 6 ;  ­  2 3  множеству А. 3.Найти равные среди следующих множеств: А = {1; 3; 6}, B = {3; 6; 9},  C = {3; 2; 6}, D = {2; 3; 6}, E = {6; 2; 3}, F = {6; 9; 3}. 4.Даны множества:  Р = {x| x ∈N,x<20,x−нечетноечисло}; Q = {x| x ∈N,x<20,x−четноечисло}; S = {x| x ∈N,x<20,x−¿  делится на 3}; T = {x| x ∈N,x<20,x−¿  делится на 4}. Перечислите все элементы данных множеств и множеств: Q ∩ T; Q ∩ S; P ∩ S; 14 P ∩Q ;  Q ∩S∩T . 5.Определить множества A ∪ B, A ∩ B, A\B, B\A, A ⊕ B a) A = {x| 0 ¿x<2 }, B = {x| 1 ≤x≤3 }; б)A = {x|  x2−¿  3x ¿ 0}, B = {x|  x2 6.Начертить фигуры, изображающие множества A = {(x,y) ∈R2 B = {(x,y) ∈R2 | x2 + y2 ≤ 1}, | x2 + (y – 1)2 ≤ 1}, где  R2  – 4x + 3 ≥ 0}.  – вещественная плоскость.  Какие фигуры изображают множества A ∪ B, A ∩ B,  R2 7.Пусть А = {­4; ­3; ­2; ­1; 0; 1; 2},B = {4; 3; 2; 1; 0; ­2}. Найти A ∪ B, A ∩ \A? B, A\B, B\A. 8. Для множеств A = {3,4} и B = {1, 2, 6} найти декартово произведение A x  B,   B x A  и  декартову степень  A x A, B x В. 6.  Задание:  [6] стр.44, №1 – 6 Практическая работа №2 Тема: «Построение таблиц истинности» Продолжительность 2 часа Цель занятия: закрепление знаний студентов по теории множеств и умений выполнять действия над множествами. 1. Вопросы для обсуждения: Понятие высказывания.  Основные логические операции Тождественно­истинные формулы Понятие элементарной конъюнкции, дизъюнкции.  2. Методические рекомендации по теме занятия Основные логические операции над высказываниями. 15 Высказывание ­ это такое предложение, которое либо истинно, либо ложно.  Истинное высказывание обозначают символом «1», ложное символом «0». Пример:  какие предложения являются высказываниями? 1) Кислород – газ; 2) Луна есть спутник Марса; 3) Студент физического факультета университета. Ответ:   высказывание   1)   является   истинным   высказыванием, высказывание 2) является ложным высказыванием, высказывание 3) не является высказыванием, т.к. о студенте ничего не утверждается. Отрицанием   высказывания   х   называется   высказывание,   которое истинно тогда и только тогда, когда высказывание х ложно.  х 1 0 x 0 1 Конъюнкцией   двух   высказываний   х   и  y  называется   высказывание, истинное тогда и только тогда, когда истинны оба высказывания х и y.  х 1 1 0 0 y 1 0 1 0 х  y 1 0 0 0 Дизъюнкцией   двух   высказываний   х   и  y  называется   высказывание, ложное тогда и только тогда, когда оба высказывания х и y ложны.  х 1 1 0 0 х  y 1 1 1 0 y 1 0 1 0 16 Импликацией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда высказывание х истинно, а y – ложно.  х 1 1 0 0 y 1 0 1 0 х  y 1 0 1 1 Эквиваленцией (эквивалентностью) двух высказываний х и y называется высказывание,   истинное   тогда   и   только   тогда,   когда   истинности высказываний х и y совпадают.  х 1 1 0 0 y 1 0 1 0 х y 1 0 0 1 На основе таблиц истинности основных логических операций можно составлять таблицы истинности для различных формул алгебры логики.  Пример:  построить таблицу истинности для формулы (х  ∧  y) →z ) (х  ∧  y) х  ∧  y x y z 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 →z 1 1 1 1 1 1 0 1 Пример:  доказать тождественную истинность для формулы (х    y) ∨ (y →x ) x y (х  y) (y →x ) (х  y) ∨ (y 17 →x ) 1 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 Ответ: данная формула является тавтологией. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками:  [1] Гл.1. §5 стр.45­48   4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Построение таблиц истинности». Подготовьте устные ответы на вопросы: а) Что называется высказыванием? b) Что называется отрицанием, конъюнкцией, дизъюнкцией, импликацией, эквиваленцией? c) Что называется тавтологией? Просмотрите образцы примеров. 5. Решите следующие задания: 1. 2. 3. 4. 5. 1. (X ∧Y¿∨X ; (X →¬Y¿→(¬(X∨Y)∧Z) ; (X →Y¿∧(¬X∨Y) ; (X →(Y→Z)¿→((X→Y)→(X→Z)) ; (P ⟷Q¿→(P∧Q) Доказать тождественную истинность формул: P →(Q→P∧Q) ; 18 2. 3. 4. 5. (P →Q¿→((P→¬Q)→¬P); (P →R¿→((Q→R)→(P∨Q→R)) ; (Q →R¿→(P∨Q→P∨R) ; (¬Q →¬P¿→((¬Q→P)→Q) 6.  Задание:  [1] Гл.1. §5    Практическая работа №3 Тема: «Упрощение формул логики с помощью равносильных  преобразований» Продолжительность 2 часа Цель занятия: закрепление знаний студентов по теории множеств и умений выполнять действия над множествами. 1. Вопросы для обсуждения: Равносильные формулы.  Законы логики Теоретико­множественные соотношения 2. Методические рекомендации по теме занятия Две   формулы   алгебры   логики   называются  равносильными  или эквивалентными,   если   совпадают   их   таблицы   истинности. Равносильность   логических   формул   можно   установить   при   помощи   их  1) таблиц истинности. Пример.  С   помощью   таблиц   истинности   проверить,   являются   ли равносильными формулы  x  x (  и  . x  x  y y ) 19 Решение. Составим таблицы истинности для каждой из формул А и В. x 1 1 0 0 x 1 1 0 0 y 1 0 1 0 y 1 0 1 0 x 0 0 1 1 x 0 0 1 1 y 0 1 0 1  y x 0 0 0 1 x  x ( y ) 0 0 1 1 x  y x  y x  x  y 1 1 1 0 0 0 0 1 0 0 1 1 Ответ: данные формулы являются равносильными. 2) Равносильность логических формул можно установить, используя основные равносильности между формулами. Для   упрощения   записи   формул   принят   ряд   соглашений.   Скобки   можно опускать, придерживаясь следующего порядка действий: 1. 2. 3. выполняем действия в скобках;  отрицание;   конъюнкция.  Если над формулой стоит знак отрицания, то скобки тоже опускаются. Пример.  Упростить логическую формулу:  x    y x . ( x  y ) Решение.  Используем основные равносильности:  x   y  x  ( y  x )          x y x x y x 20         . y x y x x x x y Ответ:  x  y. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками:   [1] Гл.1. §4 стр.44­45   4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Основы теории множеств». Подготовьте устные ответы на вопросы: а) Какие формулы называются равносильными? b) Отношения равносильности. c) Основные эквивалентности между формулами Просмотрите образцы примеров. 5.Решите следующие задания: A ∧ (A ∨ C) ∧ (B ∨ C) ∾ (A ∧ B) ∨ (A ∧ C); A∨(B∧A)∾A; Доказать равносильности: 1. ¬(A →B¿∾A∧¬B ; 2. 3. 4.A∨(B∧C)∾(A∨B)∧(A∨C); (A∨B)∧(¬A∨¬B)∾A∨B; 5.(A∧B)∨¿ Применяя равносильные преобразования, привести следующие формулы к  более простой форме: 1. (P →Q¿→((P→¬Q)→¬P) ; 2.¬((P⟷¬Q)∨R)∧Q; 21 3.(P⟷Q)→(¬P→Q); 4.¬((P→Q)∧P)∧(¬P∨¬Q). 6.  Задание:  [1] Гл.1. §4   Практическая работа №4 Тема: «Представление булевой функции в виде совершенной ДНФ,  совершенной КНФ, минимальной ДНФ» Продолжительность 2 часа Цель занятия: закрепление умения приводить формулы алгебры логики к СДНФ и СКНФ и минимизировать их с помощью законов алгебры логики, развитие логического и творческого мышления студентов, самостоятельной деятельности, вычислительных навыков. 1. Вопросы для обсуждения: понятие булевой функции; способы задания булевой функции; алгоритм приведения к  СДНФ; алгоритм приведения к  СКНФ. 2. Методические рекомендации по теме занятия;  Булевой функцией от одного аргумента называется функция f, заданная на множестве   из   двух   элементов   и   принимающая   значения   в   том   же двухэлементном множестве. Совершенной   дизъюнктивной   нормальной   формой  (СДНФ)   булевой функции называется ДНФ, в которой: 1. 2. различны все члены дизъюнкции; различны все члены каждой конъюнкции; ни одна конъюнкция не содержит одновременно переменную и отрицание 3. этой переменной; 22 4. каждая конъюнкция содержит все переменные, входящие в формулу, т.е. cn , где дизъюнкция имеет вид  F(x1,  x2, … ,  xn) =   ¿F(c1,…,cn)=1x1 c1∧…∧xn берется по всем наборам с =  (c1,…,cn)  из 0 и 1, для которых F(c) = 1. Совершенной   конъюнктивной   нормальной   формой  (СКНФ)   булевой функции называется КНФ, в которой: 1. 2. различны все члены конъюнкции; различны все члены каждой дизъюнкции; ни одна дизъюнкция не содержит одновременно переменную и отрицание 3. этой переменной; 4. каждая дизъюнкция содержит все переменные, входящие в формулу, т.е. cn , где дизъюнкция имеет вид  F(x1,  x2, … ,  xn) =   ¿F(c1,…,cn)=0x1 c1∨…∨xn берется по всем наборам с =  (c1,…,cn)  из 0 и 1, для которых F(c) = 0. Два способа приведения к совершенным нормальным формам. 1) Алгоритм приведения к СДНФ (аналитический). 1. 2. привести формулу с помощью равносильных преобразований  к ДНФ.  удалить   члены   дизъюнкции,   содержащие   переменную   вместе   с   ее отрицанием (если такие окажутся); 3. из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного; 4. из   одинаковых   членов   каждой   конъюнкции   (если   такие   окажутся) удалить все, кроме одного; 5. если в какой­нибудь конъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции 23 член    x  i x i    и применить закон дистрибутивности конъюнкции относительно дизъюнкции; если   в   полученной   дизъюнкции   окажутся   одинаковые   члены, 6. воспользоваться предписанием из п. 3. Полученная формула и является СДНФ данной формулы. Пример.  Привести   формулу   к   СДНФ   с   помощью   равносильных преобразований:   x   xy  y . Решение.   x   xy   xy x y  yx  y . yx Алгоритм приведения к СКНФ (аналитический). 1. привести формулу с помощью равносильных преобразований к КНФ.  удалить   члены   конъюнкции,   содержащие   переменную   вместе   с   ее 2. отрицанием (если такие окажутся); из одинаковых членов конъюнкции (если такие окажутся) удалить все, 3. кроме одного; из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить 4. все, кроме одного; 5. если в какой­нибудь дизъюнкции не содержится переменной  xi  из числа переменных, входящих  в  исходную  формулу, добавить   к  этой  дизъюнкции член    x  i x i    и применить закон дистрибутивности дизъюнкции относительно конъюнкции; 6. если   в   полученной   конъюнкции   окажутся   одинаковые   члены, воспользоваться предписанием из п. 3. 24 Полученная формула и является СКНФ данной формулы. Пример.  Привести   формулу   к   СКНФ   с   помощью   равносильных преобразований:  .  yx  z Решение.     z y    yx x     xz x   yzz   z   z  x    x   y xz xx   y   xz   xz y  yy  y   xz   xz   xz   xz  y y   y y   y y   .z  z  2) Алгоритм приведения к СДНФ (табличный). Строим   таблицу   значений   формулы.   Рассматриваем   только   те   строки,   в которых   значение   формулы   равно   единице.   Каждой   такой   строке соответствует   конъюнкция   всех   аргументов   (без   повторений).   Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций. Пример. Построить СДНФ для формулы логики высказываний:    x F  .xyy Решение. Строим таблицу истинности для формулы F: № 0 1 2 3 x 0 0 1 1 y 0 1 0 1 СДНФ (1): № 3: F = x y. x y 1 1 0 1 F=(x y)xy 0 0 0 1 Алгоритм приведения к СКНФ (табличный). Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой   такой   строке   соответствует   дизъюнкция   всех   переменных   (без повторений).   Причем   аргумент,   принимающий   значение   0,   берется   без 25 отрицания,   значение   1   –   с   отрицанием.   Наконец,   образуют   конъюнкцию полученных дизъюнкций. Пример. Построить СКНФ для формулы логики высказываний:    x F  .xyy Решение. Строим таблицу значений. № 0 1 2 3 x 0 0 1 1 y 0 1 0 1 F=(x y)xy 0 0 0 1 СКНФ (0): № 0, 1, 2:   x F  xy   xy  .y Минимальной   ДНФ   (МДНФ)  функции  f(x1,  x2,   …,  xn)  называется   ДНФ, реализующая   функцию  f  и   содержащая   минимальное   число   символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками:  [1] гл.2. §10,  стр.104 ­ 105   4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Функции алгебры логики». Подготовьте устные ответы на вопросы: а) Что такое ДНФ? b) Чем отличается ДНФ от СДНФ? а) Что такое КНФ? b) Чем отличается КНФ от СКНФ? c) Алгоритмы приведения к СДНФ и СКНФ. Просмотрите образцы примеров. 26 Решите следующие задания: Найти СДНФ двумя способами: 1. (x ∧ y) ∨ z; 2. (x  ↔  z)  →  (x ∧  3. (x  ↔  y) ∧ (y  ↔  z) ∧ (z  ↔  t). Найти СКНФ двумя способами: 1. (x ∨ y) ∧ z; 2. ( 3. (x ∧ ((y ∧ z) ∨ t)) ∨  ´´x∨´y ) ∧ (x  →  (y ∧ z)); ´y ); ´t . 6.  Задание:  [1] гл.2. §9 ­ 10  Практическая работа №5 Тема: «Проверка булевой функции на принадлежность к классам Т0, T1, S,  L, М; проверка множества булевых функций на полноту» Продолжительность 2 часа Цель занятия: закрепление знаний студентов по теории множеств и умений выполнять действия над множествами. 1) Вопросы для обсуждения: Понятие высказывания.  Основные логические операции Тождественно­истинные формулы Понятие элементарной конъюнкции, дизъюнкции.  2) Методические рекомендации по теме занятия Теорема Поста  (признак полноты системы булевых функций). Для того чтобы система булевых функций {f1, …,  fm} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T0,  T1,  L,  M,  S  нашлась   хотя   бы   одна   функция  fi  из   системы,   не принадлежащая этому классу. 27 Пример.  Выяснить   к   каким   функционально   замкнутым   классам принадлежит булева функция f=01001110, используя теорему Поста. Решение. Строим таблицу значений и треугольник Паскаля: Слагаемые  полинома  Жегалкина 1 x3 x2 x2x3 x1 x1 x3 x1 x2 x1 x2 x3 x 1 x 2 x 3 f g Треугольник Паскаля 0 0 0 0 0 f = 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 Полином Жегалкина имеет вид: f = x3 + x2x3 + x1 + x1 x3. 1. 2. 3. f(0, 0, 0) = 0  fT0; f(1, 1, 1) = 1  fT1; f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются  противоположными, то f  S; 4. так как в полиноме Жегалкина присутствуют слагаемые,  представляющие собой конъюнкцию нескольких переменных, то f  L; 28 5. сокращенная ДНФ функции имеет вид:   f  xx 1 2  xx 1 3  xx 2 3 , так как она содержит отрицания, то f  M. Сведем полученные данные: T 0 T 1 S L M f + - - - - Пример. Доказать полноту системы {+, , 1}. Решение. Введем обозначения: f1 = x1 + x2, f2 = x1 x2, f3 = 1. Построим единую  таблицу для функций. Слагаемы е № х 1 х 2 f1 =  х1+х2 1 х2 х1 х1х2 0 0 0 0 1 0 1 1 2 1 0 1 3 1 1 0 Полином Жегалкина: f2  =х1х2 0   Паскал я 0 1 1 0 1 0 1 1 1 1 1 0 1 f3  =1 1 1 1 1   Паскал я   Паскал я 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 f f f 1 2 3 x 2 x 1  ;   x 1 x 2 .1 xx 21 ; T 1 L M S f T 0 + - + - - f 1 f 2 + + - + - 29 - + + + - f 3 Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, , 1} является полной. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками: [1] гл.2 §11,  с.106­110 4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите   тему   по   конспекту:   «Основные   классы   функций.   Полнота множества. Теорема Поста». Подготовьте устные ответы на вопросы: а) Сформулируйте признак полноты системы булевых функций. b) Какая функция называется монотонной? c) Какая функция называется линейной? Просмотрите образцы примеров. 5. Решите следующие задания: 1. Исследовать на полноту системы булевых функций: 1) { ↔ , ∨, 0} 2) { → ,  ∙  , 0} 3) { ⊕ ,  ∙  , ↔} 2. К каким функционально замкнутым классам принадлежит булева функция: 1) f = 11000101 2) f = 11110100 3) f = 01001010 6.  Задание:  [1] гл.2 §10­11  30 Практическая работа №6 Тема:  «Определение   логического   значения   для   высказываний,   построение отрицаний к предикатам» Продолжительность 2 часа Цель   занятия:  закрепление   знаний   студентов   по   предикатам   и   умений выполнять действия над предикатами, развитие логического и творческого мышления студентов, самостоятельной деятельности. 1. Вопросы для обсуждения: понятие предиката; логические операции над предикатами; кванторные операции над предикатами. 2. Методические рекомендации по теме занятия: К   предикатам   применимы   все   операции   исчисления   высказываний: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция и для них справедливы все эквивалентности исчисления высказываний. Правила перестановки кванторов.   Стоящие рядом одноименные кванторы можно переставлять местами.                    yPx xPy  yPx xPy Формулы   называют  равносильными,   если   при   любых   подстановках предметных   постоянных   они   принимают   одинаковое   значение.   Если   две формулы F1 и F2 равносильны, т.е. F1=F2, то они эквивалентны. Равносильности логики предикатов. Комбинация кванторов: 1.  xPy ,( yx  yPx ,( yx ) ; ) 31 2.  3.   yPx ,( yx )  xPy ,( yx ) ;  yPx ,( yx )  xPy ,( yx ) . Комбинация кванторов и отрицаний: .1  xA )( x  )( xAx .2  xA )( x  )( xAx .3  xA )( x  )( xAx .4  xA )( x  )( xAx ; ; ; . Пример: Если Р2 (х; a):= "х находится на a" и a = ”стол”, то формулы: а) x (  Р2 (х; a)):= "для всех х верно, что х не находится на a “; б)   x ( Р2 (х; a)):= "не для каждого х верно, что х находится на a”; в)   x ( Р2 (х; a)):= “не существует х, для которого верно, что х находится на a”. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками:  [1] гл.4 §20,  с.157­164 4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Предикаты». Подготовьте устные ответы на вопросы: а) Что называется предикатом? b) Понятие одноместного и двухместного предиката. 32 c)   Что   называется   областью   определения   и   множеством   истинности предиката? d) Логические операции над предикатами. e) Кванторные операции над предикатами. Просмотрите образцы примеров. 5.Решите следующие задания: Выразить области истинности предиката   через области истинности yxP ,( ) предикатов   и  yxB ,( ) , если: ,( yxA ) 1.  yxP ,( )  yxA ,( ) ;        2.   yxP ,( )  ,( yxA ,(&) yxB ) ; 3.    yxP ,( )  ,( yxA )  yxB ,( ) ;            Найти отрицание следующих формул: 1.  2.  3.  4.  5.  xAx &)( ( ;           &B(x) )C(x)  )( ( xAx  yB ( y )) ;  )( ( xAx  yB ( y )) ;                    xRx )( (  ( xQ )) ;  zyxPzyx ), ,( (  , zyxQ ,( )) ;  33 6.  ( yxRyx ,( . )  ,( yxL )) 6.  Задание:  [1] гл.4 §18­20  Практическая работа №7 Тема: «Рекурсивные функции» Продолжительность 2 часа Цель занятия:  закрепление   знаний   и   умений   студентов   по   вычислимым функциям   и   алгоритмам,   развитие   логического   мышления   студентов, самостоятельной деятельности. 1. Вопросы для обсуждения: определение Машины Тьюринга; устройство машины Тьюринга; рекурсивные функции.  2. Методические рекомендации по теме занятия:              Функция  , ( xxf 1 2 ,..., nx ) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операции суперпозиции, схем примитивной рекурсии и ­ оператора. Функция xxf ( , 1 2 ,..., nx )   ­   называется  общерекурсивной,  если   она   частично рекурсивна и всюду определена. Пример. Простейшие функции  (х)λ  и О(х),  In m ( x1,x2,…,xn ) частично рекурсивны, а т.к. они всюду определены на множестве всех натуральных чисел, то они и общерекурсивны. 34 Пример.  Функция   Ck (x)  (постоянная   и   Ck (x)=  k)  получается   как λ (О(х))   =   1,   и   суперпозиция   функций   (х)   и   О(х).   и   т.д.   Значит,   функция  Ck   частично   рекурсивна.   Но λ ( (О(х)))=   2   Действительно,  λ λ функция  Ck (x) всюду определена, а поэтому она и общерекурсивна. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками: [1] гл.7 §33,  с.347­349 4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Вычислимые функции и алгоритмы». Подготовьте устные ответы на вопросы: а) Что называется машиной Тьюринга? b) Что называется частично рекурсивной функцией? c) Сформулируйте тезис Тьюринга? Просмотрите образцы примеров. 5. Решите следующие задания: Доказать, что функции общерекурсивны: 1.   Р(х,у) = х ∙ у; 2.   G(х,у) =  хy ; 3.    δ (x) =  {x−1, еслих>0, 4.    х  ∸  у =  {x−у, еслих>0, 5.    |х−у| ; 6.   x!. 6.  Задание:  [1] гл.7 §33 0, еслих=0; 0, еслих=0;    (усеченная разность) 35 Практическая работа №8 Тема: «Совпадения класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу» Продолжительность 2 часа Цель занятия:  закрепление знаний студентов по нормально вычислимым функциям   развитие   логического   и   творческого   мышления   студентов, самостоятельной деятельности. 1. Вопросы для обсуждения: марковские подстановки;  нормальные алгоритмы и применение их к словам; нормально вычислимые функции и принцип нормализации Маркова. 2. Методические рекомендации по теме занятия:           Понятие   нормально   вычислимой   функции   равносильно   понятию функции,   вычислимой   по   Тьюрингу,   и   понятию   частично   рекурсивной функции.  Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.  Всякая нормально вычислимая функция вычислима по Тьюрингу. Следующие   классы   функций   (заданных   на   натуральных   числах   и принимающих натуральные значения) совпадают: a) класс всех функций, вычислимых по Тьюрингу; b) класс всех частично рекурсивных функций; c) класс всех нормально вычислимых функций. Пример.  Пусть для слов в алфавите А = {a,  b,  c  d} задана следующая марковская подстановка:  bc  →  a. Примените ее к слову abcddacba. Решение.  Для   применения   марковской   подстановки  P → Q  к   данному слову важно обнаружить в данном слове первое вхождение подслова  Р  и заменить его словом  Q.  Здесь подслово  Р  входит в данное слово только один раз. 36 Для нашей подстановки получаем результат: aaddacba. 3. Рекомендации по подготовке к занятию.  При подготовке к занятию ознакомьтесь с источниками: [1] гл.7 §34,с.356 4. Порядок выполнения работы. Запишите в тетради название, цель работы. Повторите тему по конспекту: «Построение таблиц истинности». Подготовьте устные ответы на вопросы: а) Что называется? b) Как задается марковская подстановка? c) В каких случаях марковская подстановка не применима к слову? Просмотрите образцы примеров. 5. Решите следующие задания: Каждую   из   следующих   марковских   подстановок   примените   к   словам ddacbabc и cbabcdac.  1) ab  →  dc; 2) bc  →  a; 3) dd  →  bb; 4) ac  →  dc; 5) cb  →  d; 6) dac  →  acd; 7) b  →  a; 8) a  →  bd. 6.  Задание:  [1] гл.7 §34 с.357  37 Список использованной литературы: 1. Игошин   В.И.   Математическая   логика   и   теория   алгоритмов.   М.: «Академия». 2008г. 2. Игошин В.И. Задачи и упражнения по математической логике и теории  алгоритмов. М.: «Академия». 2007г. 3. Пономарев В.Ф.   Математическая   логика.   Учебное   пособие   – Калининград: КГТУ, 2001г. 38