Формализация умозаключений в логике предикатов

Введение
Логика как наука о мышлении является одной из древнейших наук, возникших более двух тысяч лет тому назад, в 4 веке до н.э. в Индии, Китае и достигшей своего расцвета в Древней Греции. Логика – это философская дисциплина о формах, в которых протекает мышление, наука о законах правильного мышления или наука о законах которым подчиняется правильное мышление. Формальная логика – это наука (или дисциплина), изучающая законы формального мышления. Таким образом, логика, в сущности, исследует законы мышления. Ко второй половине 19 в. сложилась символическая логика или математическая логика, ряд идей который был сформулирован еще в 18 веке нем. мыслителем Г. В. Лейбницем. Символическая логика возникла как результат применения математических методов к логике, точнее к некоторым ее разделам, прежде всего к умозаключению и доказательству.Математическая логика – раздел современной формальной логики, в котором логические выводы исследуются посредством логических исчислений на основе математического языка, аксиоматизации и формализации.Математическую логику можно условно разделить на логику высказываний, логику предикатов, исчисление высказываний и исчисление предикатов. Умозаключения и логические выводы можно исследовать как средствами логики высказываний, так и средствами логики предикатов.В реферате рассмотрим, как можно использовать логику предикатов для формализации и доказательства умозаключений.1 Основные понятия логики предикатов1.1 Формулы логики предикатовПусть А – множество объектов произвольной природы (предметная область предиката), n-местный предикат – произвольное отображение , .Пример 1. Предикат A(x) =«x ≤ 2» на множестве X = R – одноместный. Предикат B(x, y) =«xy > 0» на множестве X = – двуместный.Если X = {0,1}, то n-местный предикат является n-местной булевой функцией. Нульместный предикат представляет собой высказывание.Поскольку множество значений любого предиката лежит во множестве {0,1}, то с предикатами можно производить все операции алгебры логики, и все известные свойства логических операций обобщаются для предикатов. Рассмотрим эти свойства (для удобства в свойствах записываются одноместные предикаты):1. Коммутативность: P(x)Q(x) = Q(x) P(x), P(x) Q(x) = Q(x) P(x).2. Ассоциативность: P(x) (Q(x) R(x))=(P(x) Q(x)) R(x), P(x) (Q(x) R(x))=(P(x) Q(x)) R(x).3. Дистрибутивность: P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)), P(x) (Q(x) R(x))=(P(x) Q(x)) (P(x) R(x)).4. Идемпотентность: P(x) P(x) = P(x), P(x) P(x) = P(x).5. Закон двойного отрицания: ¬¬P(x) = P(x).6. Закон исключения третьего: P(x) ¬P(x) = 1.7. Закон противоречия: P(x) ¬P(x) = 0 .8. Законы де Моргана: ¬(P(x) Q(x)) = ¬P(x) ¬Q(x), ¬(P(x) Q(x)) = ¬P(x) ¬Q(x).9. Свойства операций с логическими константами: P(x) 1 = 1, P(x) 0= P(x), P(x) 1= P(x), P(x) 0 = 0.Здесь P(x), Q(x) и R(x) – любые предикаты,– объединение предикатов,– пересечение предикатов, – следствие предикатов, – эквиваленция предикатов. Для предикатов определены операции специального вида, которые называются кванторами.Пусть дан n-местный предикат на множестве X, означающий, что для набора выполнено свойство A, и пусть – одна из переменных. Тогда запись означает, что для всех значений переменной свойство A выполнено. Символ называется квантором всеобщности (общности). Предикат является (n-1)-местным. Он зависит от переменных . Если дан одноместный предикат P(x), то утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.Для n-местного предиката на множестве X и переменной запись означает, что существует значение переменной , для которой свойство A выполнено. Символ называется квантором существования. Предикат является (n-1)-местным, зависит от переменных , для одноместного предиката P(x) утверждение xP(x) представляет собой нульместный предикат, то есть истинное или ложное высказывание.Пример 2. На множестве X = R дан предикат A(x) =«x≤2». Высказывание x(x ≤ 2) – ложно, x(x ≤ 2) – истинно.Запись xA (xA) не подразумевает, что в формуле A есть переменная x.Переменная x называется переменной в кванторе, а A – областью действия квантора.Имеют место эквивалентности:1) ;2) ;3) ;4) ;5) ;6) ;7) ;8) ;9) x(P(x) Q(x)) =xP(x) xQ(x);10) x(P(x) Q(x)) = xP(x) xQ(x);11) xP(x)xQ(x) = xP(x)yQ( y) =x(P(x) yQ( y)) == xy (P(x) Q( y));12) xP(x) xQ(x) = xP(x) yQ( y) =x(P(x) yQ( y)) ==xy (P(x) Q( y)).Предикат тождественно истинный (тождественно ложный), если при всех возможных значениях переменных он принимает значение 1(0).1.2 Применение предикатов для записи предложенийС помощью предикатов можно записывать различные предложения, в том числе математические утверждения.При этом квантор «» обозначает слова – «любой», «все», «каждый», квантор «» обозначает слова – «существует», «некоторый», «какой-либо», сочетание «» – значит «не все», «» – «никакой».Предложение разбивается на логические части, выбираются переменные, свойства предметных переменных записываются одноместным (двухместным, трехместным) предикатом с помощью кванторов.Пример 3. Записать предложение «Любые две непараллельные прямые пересекаются в одной точке» с помощью предикатов.Решение:Предметные переменные – прямая, точка, свойства – пересекается в точке.Предикаты:P(x) – x прямая,Q(x) – x точка,L(x,y,z) – x и y пересекаются в z.Предложение запишется в виде: .Пример 4. Записать предложение «Не все то золото, что блестит» с помощью предикатов.Решение:Предметная переменная – золото, свойства – блестит.Предикаты:P(x) – x – золото,Q(x) – x – блестит.Предложение запишется в виде: .Запись обозначает – «не все золото блестит», что является ложным.1.3 Предваренная, приведенная и сколемовская формы формул логики предикатовРассмотрим предикат P(x), для него верны формулы пронесения отрицания через кванторы:Предикатная формула находится в приведенной форме, если в ней использованы только кванторные операции, а также операции инверсии, конъюнкции, дизъюнкции, причем инверсия относится только к предикатным буквам.Предикатная формула находится в предваренной форме (предваренной нормальной форме), если она имеет вид , где – кванторы всеобщности или существования, а формула A находится в приведенной форме и не содержит кванторов.Пример 5. Записать формулу А в предваренной нормальной форме: A = xy P(x, y) →xy Q(x, y) R(x).Решение: A = xy P(x, y) x y Q(x, y) R(x) == xy P(x, y) xy Q(x, y) R(x) == xy P(x, y) xy Q(x, y) R(x).Полученная формула записана в приведенной форме. Для того чтобы квантор всеобщности можно было вынести за скобки, переобозначим переменные и выполним преобразования:A = ty P(t, y) zy Q(z, y) R(x) == t(y P(t, y) zy Q(z, y) R(x)) == tz (y P(t, y) y Q(z, y) R(x)) == tzy( P(t, y) y Q(z, y) R(x)) – предваренная форма.Пример 6. Записать формулу в предваренной нормальной форме: .Решение:= ========= ===.Это преобразование предназначено для исключения из предикатных формул кванторов существования при сохранении семантики.Рассмотрим формулу , поскольку квантор существования находится внутри области действия квантора всеобщности, допускается, что х, который «существует», может зависеть от значения у. Пусть эта зависимость определяется явно с помощью некоторой функции f(у), отображающей каждое значение у в х, который существует. Такая функция называется функцией Сколема. С её помощью формула примет вид .Общее правило исключения из предикатной формулы квантора существования состоит в замене всюду в ней переменной, относящейся к квантору существования, функцией Сколема, аргументами которой служат переменные, относящиеся к тем кванторам всеобщности, области действия которых охватывают область действия исключаемого квантора существования. Функции Сколема не должны совпадать с теми буквами, которые уже имеются в формуле.Пример 7. Приведем к сколемовской форме формулу.Приоритетность действий кванторов, имеющихся в префиксной форме представления, определяются слева направо, следовательно: .Аналогично ;Если переменная, связанная квантором существования, является крайней слева, то она заменяется на константу. Если подобным образом исключить связанные квантором существования переменные, то любые другие переменные, которые встречаются в формуле, будут связаны только квантором всеобщности и поэтому уже не понадобится пояснять это обстоятельство связыванием переменных кванторами. Иначе говоря, так как порядок расположения кванторов всеобщности несущественен, то можно эти кванторы явным образом не указывать (то есть опустить). Такое формальное представление предикатных формул называют сколемовской нормальной формой.Любое выражение, записанное в СКНФ (сколемовской конъюнктивной нормальной форме), можно представить в виде конъюнкции конечного множества дизъюнкций предикатов и (или) их отрицаний. Для этого необходимо к СКНФ несколько раз применить правило.Клаузальной формой называется часть сколемовской формы, ограниченная скобками (часть предикатов, связанных дизъюнкцией). Если, например, если сколемовская форма имеет вид:,то части формулы, соединенные конъюнкцией, образуют множество:.Таким образом, КНФ исходной формулы можно разложить на предложения. Множество предложений, полученных в результате разложения, называется клаузальным множеством. Поскольку любое предложение совершенно независимо от всех других, то между этими предложениями отсутствуют какие-либо взаимосвязи. Поэтому в общем нельзя говорить об эквивалентности формулы логики предикатов и клаузального множества.2 Проверка умозаключений средствами логики предикатов2.1 Понятие умозаключенияУмозаключение, или рассуждение, представляет собой наиболее совершенное логическое строение. Вид деятельности человеческого мышления, в ходе которого мы получаем новые суждения из других, называется умозаключением: мы заключаем своим умом. С помощью многообразных видов умозаключений мы можем получать (также) новые знания. Мы уже знаем, что суждения – это мысль, следовательно, умозаключение – это последовательность мыслей. Суждения (мысли), из которых выводится последнее суждение, называются посылками. Суждение (мысль), которое выводится из предыдущих суждений, называется заключением. Таким образом, в умозаключении можно различить два элемента: посылки и заключение. Третий элемент структуры умозаключения в речи явно не выражается. Этим третьим элементом во внешней структуре умозаключения заключается логическая связка, под которой понимаются слова, указывающие на наличие логической связи между соединяемыми ими суждениями. Обычно в качестве логической связки выступают слова: «следовательно, поэтому, так как, ибо, значит» и т. д. Эти слова являются для нас знаками, сигнализирующими о наличии в тексте или речи умозаключения.Итак, умозаключение – форма мышления, в которой из одного или нескольких суждений (посылок) на основании определенных правил вывода получается новое суждение (заключение), с необходимостью или определенной степенью вероятности следующее из них.Как известно, условиями истинности заключения являются истинность посылок и логическая правильность вывода.С правилами различных видов умозаключений знакомит формальная логика.Умозаключения делятся на дедуктивные, индуктивные и умозаключения по аналогии.Дедуктивные умозаключения – те умозаключения, у которых между посылками и заключениями имеется отношение логического следования. Правила дедуктивного вывода определяются характером посылок, которые могут быть простыми (категорическими) или сложными суждениями. В зависимости от количества посылок дедуктивные выводы из категорических суждений делятся на непосредственные, в которых заключение выводится из одной посылки, и опосредованные, в которых заключение выводится из двух посылок.Непосредственными умозаключениями называются дедуктивные умозаключения, делаемые из одной посылки. К ним в традиционной логике относятся следующие: превращение, обращение, противопоставление предикату и умозаключения по логическому квадрату.Математическая логика дает формальный аппарат, с помощью которого в определенных частях логики можно выводить следствие из данных посылок. Используя этот аппарат, мы можем, имея некоторые данные, получить из них новые сведения, непосредственно не очевидные, но заключенные в этой информации, или же можем выводить логические следствия, вытекающие из данной информации (в недедуктивном умозаключении; в дедуктивном умозаключении).2.2 Виды умозаключенийНепосредственное умозаключениеПолучение выводов из категорических суждений посредством их преобразования и есть, в сущности, непосредственное умозаключение. К непосредственным умозаключениям относятся:превращения;обращения;противопоставления предикату;умозаключения по «логическому квадрату».Превращение – вид непосредственного умозаключения, при  котором изменяется качество посылки без изменения ее количества, при этом предикат заключения является отрицанием предиката посылки.По качеству связи категорические суждения делятся на утвердительные и отрицательные, например: S есть P, S не есть не  P.Обращением называется умозаключение, в котором в заключении (в новом суждении) субъектом является предикат, а предикатом - субъекта исходного суждения, т. е. происходит перемена мест субъекта и предиката при сохранении качества суждения: S есть P -> P есть S.Противопоставление предикату – это непосредственное умозаключение, при котором (в заключении) предикатом является субъект, субъектом – понятие, противоречащее предикату исходного суждения, и связка меняется на противоположную. Например: S есть P. -> не-P не есть S.Иными словами, мы делаем таким образом: 1) вместо P берем не P; 2) меняем местами S и не-P; 3) связку меняем на противоположную.Например, дано суждение: "Все львы - хищные животные". В результате противопоставления предикату получим суждение: "Ни одно нехищное животное не является львом". Противопоставление предикату можно рассматривать как результат двух последовательных непосредственных умозаключений – сначала превращения, затем обращения превращенного суждения.СиллогизмыПростой категорический силлогизм (простое дедуктивное умозаключение) – такое умозаключение, в котором заключение и посылки являются простыми категорическими суждениями. Проанализируем структуру силлогизма. Понятия, входящие в состав силлогизма, называются терминами силлогизма. Различают меньший, больший и средний термины. Меньший термин – понятие, которое в заключении является субъектом и обозначается буквой «S». Больший термин – понятие, которое в заключении является предикатом и обозначается «Р». Средний термин – понятие, которое входит в обе посылки и не входит в заключение, обозначается буквой «М». Схема силлогизма: «Все М есть Р. S есть М. S есть Р».Объединенная классификация простых категорических суждений«А» – общеутвердительные суждения. Их структура «Все S есть Р».«I» – частноутвердительные суждения - «Некоторые S есть Р».«Е» – общеотрицательные суждения - «Ни одно S не есть Р».«О» – частноотрицательные суждения - «Некоторые S не есть Р».Для иллюстрации отношений между простыми категорическими суждениями используется логический квадрат.Рисунок 1 – Логический квадратСуждения называются совместимыми по истине, если они оба одновременно могут быть истинными. Отношения совместимости по истине: подчинение (отношения между А и I, Е и О), частичной совместимости (отношения между I и О). Суждения называются несовместимыми по истине, если они не могут быть одновременно истинными. Отношения несовместимости по истине: противоположность (между А и Е) и противоречиеЗакономерности по логическому квадрату– При отношениях подчинения действует следующая закономерность: если истинно общее (А или Е), то истинно частное (I или О); если ложно частное (I или О), то ложно общее (А или Е). – При частичной совместимости: оба суждения могут быть одновременно истинными, но не могут быть одновременно ложными, поэтому: если одно ложное, то другое обязательно истинное. – При отношениях противоположности действует следующая закономерность: оба суждения могут быть одновременно ложными, но не могут быть одновременно истинными. Поэтому, если одно из них истинное, то другое - обязательно ложное. При противоречии оба суждения не могут быть одновременно ни истинными, ни ложными. Значит, если одно из них истинное, то другое обязательно ложное, и наоборот.Пример 9. Определите тип суждения «Некоторые студенты нашей группы пошли в кино» (А, Е, I, О). Сформулируйте стандартную форму данного суждения и остальных суждений с теми же субъектом и предикатом. Считая данное суждение истинным, определите истинность, ложность или неопределенность остальных суждений с теми же субъектом и предикатом по логическому квадрату. Решение:Суждение «Некоторые студенты нашей группы пошли в кино» - частноутвердительное ( I );А: «Все студенты нашей группы пошли в кино» - неопределенное;Е: «Ни один студент нашей группы не пошел в кино» - ложь.О: «Некоторые студенты нашей группы не пошли в кино» - неопределенное.Пример 10. Произведите отрицание суждения «Некоторые студенты нашей группы пошли в кино» таким образом, чтобы результат отрицания не содержал внешних знаков отрицания (с помощью логического квадрата). Решение: Для суждения типа I противоречащим является суждение типа Е: «Ни один студент нашей группы не пошел в кино».По «логическому квадрату» можно вывести следующие умозаключения:а) умозаключения от подчиняющего к подчиненному (то есть по субординации) – от истинности общеутвердительного мы заключаем к истинности частноутвердительного;б) умозаключение от подчиненного к подчиняющему (то есть по обратной субординации) – от ложности частноутвердительного мы заключаем к ложности общеутвердительного;в) умозаключение противоречия (контрадикторности) – от ложности общеутвердительного суждения: «все люди читают газеты» заключаем к истинности частноотрицательного: «Некоторые люди не читают газет»;г) умозаключение противоположности (контрарности) – от истинности общеутвердительного суждения «все растения суть организмы» заключает к ложности противоположного суждения: «ни одно растение не есть организм»;д) умозаключение субконтрарности – от ложности частноутвердительного суждения: «некоторые люди всеведущи» заключаем к истинности частноотрицательного «некоторые люди не суть всеведущи».Пример 11. Произведите отрицание суждения «Некоторые студенты нашей группы пошли в кино» таким образом, чтобы результат отрицания не содержал внешних знаков отрицания (с помощью логического квадрата). Решение: Для суждения типа I противоречащим является суждение типа Е: «Ни один студент нашей группы не пошел в кино».Пример 12. Установите, в каком отношении находятся следующие простые суждения: Все взрослые когда-то были детьми. Некоторые взрослые когда-то были детьми.Решение: Выделим субъекты и предикаты суждений и запишем формулы.1.Все взрослые (S) когда-то были детьми (P) - общеутвердительное суждение – SAP.Некоторые взрослые когда-то были детьми – частноутвердительное суждение – SIP.По логическому квадрату определяем, что простые суждения находятся в отношении подчинения.2.3 Дедуктивные умозаключения в логике предикатовПерейдём к рассмотрению опосредованных умозаключений и из них, прежде всего, рассмотрим дедуктивные умозаключения. Дедуктивные умозаключения – те умозаключения, у которых между посылками и заключениями имеется отношение логического следования. Логическое следствие из данных посылок есть высказывание, которое не может быть ложным, когда эти посылки истинны. Дедуктивным называется умозаключение, в котором истинность посылок должна гарантировать истинность заключения.Пусть A1, A2, …, An, B – дедуктивные умозаключения.Умозаключение в логике предикатов формализуются в виде:A1, A2, …, An ├ B.Если объединить посылки этого умозаключения при помощи конъюнкции, то мы получим следующее отношение логического следования между суждениями: A1 &A2 … &An -> B.Формула B называется логическим следствием формул A1, A2, …, An.Для проверки умозаключений в логике предикатов можно применять несколько способов: проверка общезначимости формулы A1 &A2 … &An -> B;метод резолюций;круги Эйлера-Венна.Сущность метода резолюций состоит в проверке того факта, содержит ли клазуальное множество пустое предложение, если не содержащее литер. Если клазуальное множество содержит пустое предложение, то множество противоречиво (невыполнимо). Правило резолюций: контрарная пара литер и удаляется из множества, а из оставшихся частей формируется новое предложение (например из и выводится ). Предложение, вновь сформированное из клауз называется резольвентой. Например, из клауз: ,, получится резольвента .Если при выводе предложений получены два однолитерных дизъюнкта, образующих контрарную пару, то их резольвентой будет пустой дизъюнкт. Так как наличие пустого дизъюнкта означает, что клазуальное множество является ложным, то невыполнимость исходного утверждения, сформулированного в виде отрицания, доказывает истинность выдвинутого предположения.Алгоритм метода резолюций в исчислении предикатов отличается тем, что формулу логики предикатов необходимо привести к сколемовской форме, затем матрицу формы (предикаты без кванторов) привести к КНФ с помощью законов упрощения формул. После чего также выделяется список дизъюнктов, к которому применяется правило резолюций.Пример 13. Методом резолюций проверить умозаключение├ .Решение:Выводимость данной формулы по методу резолюций следует из противоречивости множества Г: ,.Приведем все формулы из Г к КНФ: Г: ,.Клазуальное множество дизъюнктов: S: ,.Построим возможный резолютивный вывод нуля из Г:resresПустой дизъюнкт получен, следовательно набор формул Г противоречив, откуда следует, что формула выводима из гипотез .Пример 14. Проверить умозаключение методом резолюций и с помощью кругов Эйлера-Венна.Некоторые С не есть D. Все А суть не D. Все В суть С. Следовательно, все В суть А.Обозначим предикаты: A(х) – х принадлежит AB(х) – х принадлежит BС(х) – х принадлежит СD(х) – х принадлежит DЗапишем формулы логики предикатов к посылкам и заключению:∃x Cx&¬Dx, ∀x Ax→¬Dx, ∀x Bx→Cx - ∀x Bx→Ax. Проверим рассуждение методом резолюций.Приведем формулу ¬∀x Bx→Ax& ∃x Cx&¬Dx & ∀x Ax→¬Dx & ∀x Bx→Cx к сколемовской стандартной форме и составим множество дизъюнктов.¬∀x ¬Bx∨Ax& ∃x Cx&¬Dx & ∀x ¬Ax∨¬Dx & ∀x ¬Bx∨Cx ≡ ≡∃x¬ ¬Bx∨Ax& ∃x Cx&¬Dx & ∀x ¬Ax∨¬Dx & ∀x ¬Bx∨Cx ≡≡∃x Bx&¬Ax& ∃x Cx&¬Dx & ∀x ¬Ax∨¬Dx & ∀x ¬Bx∨Cx ≡≡∃t Bt&¬At& ∃s Cs&¬Ds & ∀x ¬Ax∨¬Dx & ∀x ¬Bx∨Cx ≡≡∃t∃s∀x (Bt&¬At&Cs&¬Ds & ¬Ax∨¬Dx&¬Bx∨Cx≡ ≡∀x (Ba&¬Aa&Cb&¬Db & ¬Ax∨¬Dx&¬Bx∨Cx Множество дизъюнктов:Ba,¬Aa, Cb,¬Db, ¬Ax∨¬Dx , ¬Bx∨CxПроведем унификацию дизъюнктов:Ba, ¬Bx∨Cx подстановкой а//х: Ba, ¬Ba∨Ca, резольвентой дизъюнктов будет: Cа.Проведем унификацию дизъюнктов:Сb, ¬Bx∨Cx подстановкой b//х: Сb, ¬Bb∨Cb, резольвентой дизъюнктов будет: ¬Bb.Поскольку не получается вывести пустой дизъюнкт, рассуждение не верно.Изобразим множества кругами Эйлера –Венна (множества С и D пересекаются (либо D – подмножество С), множества А и D не пересекаются, В – подмножество С.Рисунок 2 – Круги Эйлера-ВеннаИз расположения множеств согласно посылкам, не следует, что В - подмножество А, рассуждение неверно.
Заключение

В данном реферате были рассмотрены основные понятия логики предикатов, способы построения и формы формул логики предикатов; способы и примеры применения предикатов для записи предложений и умозаключений. Приведены примеры средствами логики предикатов проверки дедуктивных умозаключений методом резолюций. Можно сделать вывод: умозаключение – важный этап мышления, изучаемые как средствами логики, психологии, математической логики.В зависимости от вида умозаключения применяются различные способы его проверки: логический квадрат, силлогизмы, средства логики высказываний и логики предикатов и другие.
Список использованных источников
Аляев, Ю. А. Дискретная математика и математическая логика / С. Ф. Тюрин. - М.: Финансы и статистика, 2006. - 368 с.Битюцкий, В. П. Математическая логика. Исчисления высказываний и предикатов : методическое пособие по дисциплине «Математическая логика и теория алгоритмов» / В. П. Битюцкий, Н. В. Папуловская. - Екатеринбург : ГОУ ВПО УГТУ−УПИ, 2005 – 83 с.Балюкевич, Э. Л. Математическая логика и теория алгоритмов : учебно-практическое пособие / Л. Ф. Ковалева  - М. : Евразийский открытый институт, 2009. – 189 с.Жаркова, Ю. С. Математическая логика : учеб. пособие / Ю. С. Жаркова; Мордов. гос. пед. ин-т. - Саранск, 2011. - 66 с.Игошин, В. И. Задачи и упражнения по математической логике и теории алгоритмов : учебное пособие для студентов высших учебных заведений / В. И. Игошин. – М. : «Академия», 2007. – 304 с.Колмогоров, А. Н. Математическая логика. Введение в математическую логику : учеб. пособие / А. Н. Колмогоров, А. Г. Драгалин. - 4-е изд., обновл. - М. : Едиториал УРСС, 2013. - 234 с. Тихомирова, А. Н. Практикум по теории алгоритмов : учебное пособие / А. Н. Тихомирова, Н. В. Сафоненко. - М. : МИФИ, 2011. - 132 с. Просветов, Г. И. Дискретная математика: задачи и решения : учеб. - практ. пособие / Г. И. Просветов. - 2-е изд., доп. - М. : Альфа-Пресс, 2014. - 239 с. Судоплатов, С. В. Математическая логика и теория алгоритмов : учебник / С. В. Судоплатов, Е. В. Овчинникова. - 3-е изд. - Новосибирск : Изд-во НГТУ, 2012. - 255 с. Роганова, Н. А. Функциональное программирование: учебное пособие для студентов высших учебных заведений – М.: ГИНФО, 2002. – 260 с.Успенский, В. А. Вводный курс математической логики / Н. К. Верещагин, В. Е. Плиско - 2-е изд. - М.: ФИЗМАТЛИТ, 2004. - 128 с.