Функциональное и логическое программирование

Федеральное агентство по образованию РФ ГОУ ВПО Пермский государственный технический университет кафедра ИТАС КУЗНЕЦОВ Д.Б. КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ Функциональное и логическое программирование Для студентов направления «Информатика и вычислительная техника» (230100) Специальности АСОИУ, ЭВТ, ПОВТ дневной, заочной и дистанционной форм обучения 2008 1 Составители: Д.Б. Кузнецов Конспект лекций по дисциплине «Функциональное и логическое программирование»: для студентов направления «Информатика и вычислительная техника» (230100), специальностей АСОИУ, ЭВТ, ПОВТ дневной, заочной и дистанционной форм обучения / ПГТУ. – Пермь: 2008. утверждено на заседании кафедры ИТАС 6 февраля 2008г. протокол №20/ ПГТУ. – Пермь: 2008. 2 Виды программирования Программирование Императивное Процедурное Декларативное (математическая логика) Функциональное Логическое История науки Математическая логика, возникшая почти 100 лет назад в связи с внутренними потребностями математики, нашла применение в теоретическом (и практическом) программировании и, судя по всему, взаимодействие этих двух наук в недалеком будущем сможет принести новые плоды. Причины, по которым программисты обратились к математической логике, а логики заинтересовались программированием, имеют довольно глубокие корни. Следует, наверное, вспомнить, что математическая логика занимается построением формальных языков, предназначенных для представления таких фундаментальных понятий, как функция, отношение, аксиома, доказательство, и изучением основанных на этих языках логических и логико-математических исчислений. Именно в недрах математической логики были найдены математически точные понятия алгоритма и вычислимой функции, развита семантика формальных языков и теорий, построены системы логического вывода – и все это, заметим, было сделано в 30-40-х годах, т.е. еще в “докомпьютерную эру”. Программирование также имеет дело с формальными языками – языками программирования, являющимися средствами общения человека и компьютера. В своем стремлении сделать эти средства удобными и естественными для человека вычислительная наука не могла пройти мимо тех языков описания вычислимых функций и отношений, которые были созданы в рамках математической логики с учетом многовекового математического опыта. В результате появились принципиально новые языки функционального и логического программирования: Лисп, Рефал, ML, Миранда, Пролог и другие – особенно активно разрабатываемые в последнее десятилетие. С другой стороны, языки высокого уровня нуждаются в детально проработанной семантике, которая выходит на первый план при написании трансляторов. И здесь идеи и аппарат математической логики, уже занимавшейся проблемами семантики, оказались весьма кстати. Поначалу для формализации смысла программ использовалось известное логикам еще с 30-х годов λ -исчисление А.Чёрча, а затем абстрактным базисом денотационной 3 семантики стала мощная и элегантная теория областей, развитая Д.Скоттом. Важное значение приобретает теория логического вывода, причем не только в задачах искусственного интеллекта, но и как средство рассуждения о программах и доказательства их свойств (скажем, правильности относительно спецификации) или, наоборот, как метод построения правильных программ (например, путем их извлечения из конструктивных доказательств). В заключение, приведем цитату Д.Гриса «Мне лучше всего было бы пройти хороший курс логики десять лет назад». Введение Традиционные процедурные языки предназначаются для описания процессов вычислений на Фоннеймоновской машине. ЦП память Каждое действие программы – это изменение оперативной памяти. Мы описываем не формулы для решения задачи, мы описываем процесс, т.е. как задача должна решаться. Подобные программы сложны для понимания и доказательств. Функциональное программирование было задумано как альтернатива процедурному программированию (в конце 50-х годов). Функциональная программа представляет собой некоторое выражение (в математическом смысле); выполнение программы означает вычисление значения этого выражения. Другими словами, функциональные программы соответствуют математическим объектам (позволяют производить строгие суждения – правильно/неправильно). Результат работы императивной (процедурной) программы полностью и однозначно определен ее входом, можно сказать, что финальное состояние (или любое промежуточное) представляют собой некоторую функцию (в математическом смысле) от начального состояния, т.е. σ ' = f (σ) , где σ' - новое значение состояния после завершения программы, включающее в себя то, что можно рассматривать как “результат” работы программы. Во время исполнения каждая команда изменяет свое состояние; следовательно, состояние проходит через некоторую конечную последовательность значений: σ = σ 0 → σ 1 → σ 2 → σ 3 → ... → σ n = σ ' . В функциональном программировании используется именно такая точка зрения: программа представляет собой выражение, соответствующее функции f . Функциональные языки программирования поддерживают построение таких выражений, предоставляя широкий выбор соответствующих языковых конструкций. Рассмотрим кратко языки функционального программирования:  Lisp (Лисп) – базируется на λ - исчислении (определенная формализация понятия функции): для обработки списков (используют в графических и текстовых редакторах), для задач искусственного интеллекта;  Рефал – базируется на нормальных алгорифмах Маркова; 4  Миранда – комбинаторная логика ⇒ Haskell (Haskell-98). Процесс написания программ сродни математическому мышлению. Функциональный подход имеет ряд преимуществ перед императивным. Как было сказано выше, функциональные программы более непосредственно соответствуют математическим объектам, и следовательно, позволяют проводить строгие рассуждения. Установить значение императивной программы, т.е. той функции, вычисление которой она реализует, может оказаться довольно трудно. Напротив, значение функциональной программы может быть выведено практически непосредственно. Рассмотрим на примере: Нахождение факториала на языке функционального и процедурного программирования: n!= n ⋅ (n − 1) ⋅ (n − 2) ⋅ . . ⋅ 1;  1, n = 0; fact(n) =   n ⋅ fact(n − 1), n > 0. 1) язык Си (процедурный): int fact (int n) { int x = 1; while (n > 0) { x = x * n; n = n - 1; } return (x); } 2) язык Haskell (функциональный): fact n = if n = = 0 then 1 else n * fact(n - 1) Практически сразу видно, что программа на языке Haskell соответствует частичной функции нахождения факториала. Однако, для программы на языке Си это соответствие не очевидно. 5 Сравним функциональный и императивный подходы, заметив следующие свойства: Программирование Процедурное 1) переменные Именованные ячейки изменяемые константы. 2) циклы Циклы есть. Функциональное памяти, Настоящие переменные (в частности не используется оператор присваивания). Не может быть циклов (нет счетчика); используются рекурсивные функции вместо циклов. 3) программа – это … Последовательное изменение памяти. Вычисление функции. Последовательное выполнение команд бессмысленно, поскольку одна команда не может повлиять на выполнение следующей (т.к. негде сохранять промежуточные значения). 4) функции При вызове функции возможны побочные эффекты (два вызова одной о той же функции с одними и теми же аргументами могут дать разные результаты; изменение значений глобальных переменных). Функции используются широко, могут даже использоваться в качестве аргументов для других функций и возвращать в качестве результата; побочных эффектов нет. Из этого следует, что вычисление любого выражения не может иметь никаких побочных эффектов, и значит, порядок выполнения его подвыражений не оказывает влияния на результат. Таким образом, функциональные программы легко поддаются распараллеливанию, поскольку отдельные компоненты выражений могут вычисляться одновременно. λ- исчисление Подобно тому, как теория машин Тьюринга является основой императивных языков программирования, λ - исчисление служит базисом и математическим “фундаментом”, на котором основаны все функциональные языки программирования. λ - исчисление было изобретено в начале 30-х годов логиком А.Чёрчем, который надеялся использовать его для формализма для обоснования математики. Вскоре были обнаружены проблемы, делающие невозможным его использование в 6 этом качестве (сейчас есть основания полагать, что это не совсем верно) и λ исчисление осталось как один из способов формализации понятия алгоритма. В математике, когда необходимо говорить о какой-либо функции, принято давать этой функции некоторое имя и впоследствии использовать его, как, например, в следующем утверждении: Пусть f : R → R определяется следующим выражением:  0, x = 0;  f ( x) =  2 1  x ⋅ sin x 2 , x ≠ 0. Тогда f ' ( x) не интегрируема на интервале [0,1] . Многие языки программирования также допускают определение функций только с присваиванием им некоторых имён. Например, в языке Си функция всегда должна иметь имя. Это кажется естественным, однако поскольку в функциональном программировании функции используются повсеместно, такой подход может привести к серьёзным затруднениям. Представьте себе, что мы должны оперировать с арифметическими выражениями в подобном стиле: Пусть x = 2 и y = 4 . Тогда xx = y . f (x) Функция от х Значение функции в точке х λ - нотация позволяет определять функции с той же лёгкостью, что и другие математические объекты. λ - выражением будем называть конструкцию вида: λx. f ( x ) Использование λ - нотации позволяет чётко разделить случаи, когда под выражением типа f (x ) мы понимаем саму функцию f и ее значение в точке x . Кроме того, λ -нотация позволяет формализовать практически все виды математической нотации. Если начать с констант и переменных и строить выражения только с помощью λ - выражений и применений функций к аргументам, то можно представить очень сложные математические выражения. Пример: λx.x 2 - представляет собой функцию, возводящую свой аргумент в квадрат. λx.2 x + a - от a не зависит. Язык λ - исчисления: λ - абстракция x1 , x 2 ,..., x n - символы переменных c1 , c 2 ,... - символы констант M ∗ N (применение аргумента к функции); - аппликация ∗ математическая запись аппликации. Символ ∗ иногда опускают, т.е. MN . 7 M (N ) - λ -терм: 1) переменная или константа; 2) λx.M , где х – переменная, M - λ -терм; 3) M ∗ N - λ -терм, если M и N - λ -термы Правила вывода: • Если M=N, то N=M (симметричность); • Если M=N, N=P, то M=P (транзитивность); • Если M=N, то MP=NP; • Если M=N, то λx.M = λx.N ; Конверсия λ - исчисление основано на операциях конверсии, которые позволяют переходить от одного терма к другому, эквивалентному ему. По сложившейся традиции эти конверсии обозначают греческими буквами α, β . Они определяются следующим образом: α -конверсия: λx.M = (λy.M ) xy - х заменяем на у (можем в функции менять имя переменной). Пример: λx.2 x + a = (λy.2 y + a ) β -конверсия: (λx.M ) N = M Nx (λx.M ) N = P - β -редекс - все вхождения х меняем на N. MN =Q Q Преобразование P в Q – это β -редукция: P  β Редукция – “уменьшение” (в большинстве случаев λ -терм укорачивается). Примеры: 9 + 8; 1) (λx.x + 8)(9)  β a + 8; 2) (λx.x + 8)(a)  β x + y + a + t; 3) (λz.x + y + z + t )(a)  β β -нормальная форма – это λ -терм без редексов (когда выполнены все β - редукции). 4) (λx.((λy.xy)u ))(λv.v)  β (λx.( xu ))(λv.v)  β (λv.v )u u; β 5) 8 (λx.((λy.xy )u ))(λv.v)  β (λy.(λv.v) y )u )  β ((λy. y )u ) u; β Теорема Чёрча-Россера для β -редукции: β -нормальная форма единственна. M , P N , то ∃T : M T , N T . Если P  β β β β (λx.xx)(λx.xx); 6) (λx.xx)(λx.xx)  β Но, не для каждого λ -терма существует β -нормальная форма. Поправка: Теорема верна, если для λ -терма существует β -нормальная форма. Операция каррирования позволяет записать функции нескольких аргументов в обычной λ -нотации. Идея заключается в том, чтобы использовать выражения вида λxy.x + y . Такое выражение можно рассматривать как функцию R → ( R → R) , т.е. если его применить к одному аргументу, результатом будет функция, которая затем принимает другой аргумент. Таким образом: (λxy.x + y )12 = (λy.1 + y ) 2 =1 + 2 . λx.(λy.E ) ≡ λxy.E - важен порядок параметров. ∗ ( x +1) = 8 - 8 записывается в следующую ячейку за х ( x[1] =8 - более понятный вариант). Упражнение: умножение на 3 через операцию сложения a ∗3 ( a + ( a + a )) (λx.a + x )( a + a ) (λx.a + x )((λx.a + x ) a ); (λz.(λyt. y ( yt ))(λx.z + x )( z ))  β (λz.(λx.z + x )(λx.z + x )( z ))  β (λz.z + ((λx.z + x )( z )))  β (λz.z + ( z + z )). Свободные и связанные переменные Переменные в λ -выражениях могут быть свободными и связанными. В выражении вида x 2 + x переменная x является свободной; его значение зависит от значения переменной x и в общем случае ее нельзя переименовать. Однако в таких x n выражениях как ∑i i =1 или ∫sin ydy переменные i и y являются связанными; если вместо i везде использовать обозначение j , то значение выражения изменится. Следует понимать, что в каком-либо подвыражении переменная может быть свободной (как в выражении под интегралом), однако во всём выражении она связана какой-либо операцией связывания переменной, такой как операция 9 суммирования. Та часть выражения, которая находится “внутри” операции связывания, называется областью видимости переменной. x →M λx.M Любое вхождение переменной x в терм λx.M называется связанным (по средствам λx ). Пример: λx.x + y , x – связанная переменная; y – свободная переменная. Комбинаторы Терм без свободных вхождений переменных, называется замкнутым или комбинатором. Замкнутый терм имеет фиксированный смысл независимо от значения любых переменных. В теории комбинаторов установлено, что с помощью нескольких базовых комбинаторов и переменных можно выразить любой терм без применения операции λ -абстракции. 1 I = λx.x тождественный комбинатор IX X 2 B = λxyz.x ( yz ) композиция BFGX F (GX ) 3 C =λxyz.xzy коммутатор CFXY FYX 4 K = λxy.x образование константы KXY X 5 W = λxy.xyy дублирование WFX FXX 6 S = λxyz.xz ( yz ) подстановка и композиция SFGX FXGX 7 y = λf .(λx. f ( xx ))(λx. f ( xx ))комбинатор неподвижной точки (для организации рекурсии) Пример: (λ x.x)(8) 8 β   тождественный комбинатор I 8 8  β (λf .(λx. f ( xx))(λx. f ( xx)))( z )  β (λx.z ( xx))(λx.z ( xx))  β z (λx.z ( xx)(λx.z ( xx))) Нумерация Чёрча n-кратная композиция x( x( x...( xy ) ) ) xn y Zn 10 __ или n β β β β β β Yf f ( yf ) β _ Z0=0λxy. (ноль раз произведена операция над y) __ 0 xy y β __ Z n = n = λxy.x n y __ n xy x n y (x, взятое n-раз от y) β Комбинатор прибавления единицы __ σ = λuxy.x(uxy ) Добавление единицы к числу Чёрча: __ __ ______ σ n n + 1 β (λuxy.x (uxy ))(λxy.x n y ) Пример: (λuxy.x(uxy ))(λxy.x n y ) ...λxy.x n +1 y β (λxy.x((λxy.x y ) xy )) λxy.x( x n y ) n β β λxy.x n +1 β y Комбинатор упорядоченной пары (проверка на ноль) D = λxyz.z ( Ky ) x __ DXY 0 X β ______ DXY ( n + 1) Y β Комбинатор примитивной рекурсии __ R = λxyu.u (Qy )( D 0 x)1 __ __ __ Q = λyv.D (σ (v 0 ))( y (v 0 )(v1)) __ RGX 0 X β ______ __ __ RGX ( n +1) G n ( RGX n ) β 11 12 Способы организации рекурсии 1. Самовызов (функция вызывает сама себя) ∣x =nil ,0 длина x =¿  ∣x≠nil ,длина  x −1 1 2. Рекурсия с накапливающимся параметром длина1( x, l ) = x =nil , l x ≠nil , длина1(cdr ( x ), l +1) где x – список, l – его длина. Не вызываем ни какую функцию, меняем только параметр. И в результате выдаём этот параметр. Доходим до пустого x и возвращаем l. Недостаток: не задано l. 3. Вспомогательные функции длина ( x ) = длина1( x,0) Программа обращения списка: Функция обращения: obr(x)=if x=nil then x else obr1(x,nil) obr1(x,y)=if x=nil then y else obr1(cdr(x), cons(car(x),y)) x y На языке LISP: (obr1 (cdr x) (print (cons (car x) y))) Функции высших порядков - функции, у которых в качестве аргумента выступает функция. Пусть есть список: (5 8 4) Необходимо увеличить каждый элемент списка на единицу, т.е. функция должна вернуть: (6 9 5) S ( x) = x =nil , x , x ≠ nil , cons (car ( x ) +1, S (cdr ( x ))) Отладка: S(5 8 4) S(8 4) S(4) S() На языке LISP: (defun S(x) (if x 13 cons(6, S(8 4)) cons(9, S(4)) cons(5, S()) () где x – список (cons (+ (car x) 1) (S (cdr x)) ) nil)) В результате каждый элемент списка увеличится на единицу. x f(x) С помощью функции отображается другой список. Вызов функции: ((lambda (x) (+ x 3)) 7) 7 + 3 = 10 λ -нотация: (λx.x + 3)7  β Обобщим функцию: (defun otobr(x f) (if x (cons (f (car x)) (otobr (cdr x) f)) nil) Например: (otobr ‘(7 3) (lambda (x) (+ x 3))) В результате получим: 10 6 Чтобы каждый раз не писать lambda (x) (+ x 3)), присвоим значение: (setq ft (lambda (x) (* x 2))) (otobr ‘(4 8) ft) В результате получим: 8 16 Комбинаторная логика Комбинаторная логика позволяет избежать использования переменных, усложняющих λ -исчисление. Комбинатор - λ -терм без свободных переменных. связанных I = λx.x Ix = x I 5 = 5 (λx.x )5 = 5 1) в комбинаторной логике часто используют два комбинатора S и K, называемых базисными комбинаторами. K - λxy.x - KXY = X S - SFGX = FX (GX ) 14 2) аппликация: M ∗ N или MN 3) левоассоциативность: KLM = (( KL) M ) Языки, которые основываются на комбинаторной логике: ML (Milner, 1984 год) Миранда (Turner, 1985 год) Из этих языков был “собран” язык Haskell (98). Для работы с языком Haskell используется: интерпретатор HUGS компилятор ghc интерпретатор ghci >2+2 4 >let pi=3.14 3.14 Примечание: let пишется в интерпретаторе ghci, в компиляторе нет let. >let area r=pi*r^2 >area 7 153.93 >let umn a b =a*b (использование функции умножение с двумя аргументами) Списки: >let spis=[7,2,3] >1:9:spis [1,9,7,2,3] (добавляем в начало списка) Примечание: буквы пишутся в одиночных кавычках. Пример: Создадим файл fac.hs. 15 В файле напишем функцию вычисления факториала: fac::Integer -> Integer fac 0 = 1 fac n | n>0 = n*fac(n-1) Другой вариант: fac n = if n>0 then n*fac(n-1) else 1 Получаем: >:l fac.hs >fac 5 120 >fac (6) 720 Зададим в качестве аргументов функцию: >let twice f x = f(f(x)) или: >let twice f x = f f x >let pl1 x = x+1 >twice pl1 7 9 Выразим тождественный комбинатор через S и K: Ix = x I = SKK SFGX = FX (GX ) KXY = X >let k x y = x >let s x y z = x z (y z) или: >let s x y z = x(z, y(z)) >let I x = s k k x >i 9 9 Алгорифмы Маркова. Язык Рефал. Пример1: 16 Запишем правила ba → ab →• На входе строчка: abab Сначала используем первое правило ( ba → ab ) до тех пор, пока оно подходит, только потом переходим ко второму правилу. Получаем: aabb Пример2: Вычислить сумму палочек: |||+||+||| Правила: |+ → +| +→ →• Язык Рефал a →b →• Функция: a_на_b e1ae2 → e1b < a _ на _ b e2 > - Произвольные выражения (набор символов) Выход из рекурсии: e1 → e1 e1 , e 2 Пример1: Вместо слова приииветтттт написать слово привет: выч_один S2S2 e1 → e1 e1 S 2 S 2 e3 → e1 < выч _ один S 2 e3 > одинаковые символы Пример2: Определить слово полиндром или нет: Например, слово потоп 17 S1e2 S1 →< полиндром → Да S1 → Да e2 > e1 → Нет Введение в логическое программирование 18 В логическом программировании используются логические функции. Обычная и логическая функции не отличаются аргументами. f ( x) = ( x + 5) функция в функциональном программировании f ( x ) = ( x > 5) функция в логическом программировании (возвращает значение истина или ложь). Функция преобразует одну область в другую. В логике функции называются предикатами. Предикаты Под предикатом будем понимать логическую функцию, аргументы которой могут принимать значения из некоторой предметной области, а сама функция принимать значения истина или ложь. Предикаты бывают одноместные P ( x) , двухместные P( x, y ) и т.д. Ноль-местный предикат – это высказывание (его значение не зависит от аргумента). Пример: x > 5 - предикат 4 > 5 - высказывание (можно утверждать относительно него false) У предикатов бывают кванторы: Квантор всеобщности: ∀xP( x) Квантор существования: ∃xP (x) Предикат + Квантор = Предикат ∀x ( x > 5) false (ложный предикат); ∃x ( x > 5) true Метод резолюций - аксиоматическая теория первого порядка, которая использует доказательство от противного. Теорию изобрел Дж.Робинсон в 1965 году. В теории используется язык предикатов. Метод основывается на: 1. формализации задачи, получаем некоторые записи в форме предикатов. 2. предваренной нормальной форме (ПНФ); переводим предикаты в ПНФ. 3. сколемизации (определенные правила по отбрасыванию кванторов). 4. получении дизъюнктов (между дизъюнктами значки &, а в самих дизъюнктах - \/). 5. добавлении в систему отрицания выводимой формулы. 6. выполнении резолюций: 6.1. унификация (приведение предикатов к единой форме); 6.2. принцип силлогизма. 19 Рассмотрим подробнее каждый пункт метода. 1. Формализация задачи: из задания, данного нам, мы должны формализовать его, мы должны описать, что нам нужно, а не как решить. Пример: (данный пример будет использоваться в дальнейшем) Даны предложения 1) Кто ходит в гости по утрам, тот поступает мудро. 2) У кого есть воздушный шарик, тот ходит в гости по утрам. 3) Воздушный шарик есть у пятачка. (1) Вопрос: Кто поступает мудро? 1) Разбиваем на аксиомы. В данном примере предложения построены так, что каждое предложение соответствует аксиоме. А1) Кто ходит в гости по утрам, тот поступает мудро. А2) У кого есть воздушный шарик, тот ходит в гости по утрам. А3) Воздушный шарик есть у пятачка. 2) Выбор предикатов: Замечание: Предиката от предиката P ( R ( x)) не бывает. Г(х) – х ходит в гости по утрам М(х) – х поступает мудро Ш(х) – х владеет воздушным шариком Составим из предикатов аксиомы: А1) ∀xГ ( х) →М ( х) А2) ∀хШ ( х) → Г ( х) А3) Ш (пятачок ) Вопрос) ∃хМ ( х) 2. ПНФ. Все кванторы должны находиться слева, знаки отрицания должны стоять непосредственно у самих предикатов. Знаки между предикатами должны быть только & или \/. __ Правила: x → y = x ∨ y ¬∀xP( x ) = ∃x¬P ( x ) Примеры: 1) ∀xP( x) & ∃xR( x) = ∀xP( x) & ∃yR( y ) = ∀x∃y ( P ( x) & R ( y ))  a)∀ x(P(x) & R(x)) 2) ∀ xP( x) & ∀ xR( x) =   b)∀ x∀ y(P(x) & R( y)) 20 3) ¬∀x (∀yP ( x, y ) ∨¬∃zR ( z ) →Q ( x ) & ∀yM ( x, y )) = = ¬∀x (¬(∀yP ( x, y ) ∨¬∃zR ( z )) ∨Q ( x ) & ∀yM ( x, y )) = = ∃x ((∀yP ( x, y ) ∨¬∃zR ( z )) & (¬Q ( x ) ∨¬∀yM ( x, y ))) = = ∃x ((∀yP ( x, y ) ∨∀z¬R ( z )) & (¬Q ( x ) ∨∃t¬M ( x, t ))) = = ∃x∀y∀z∃t (( P ( x, y ) ∨¬R ( z )) & (¬Q ( x ) ∨¬M ( x, t ))) Вернёмся к примеру (1): А1) ∀x¬Г ( х ) ∨ М ( х) А2) ∀х¬Ш ( х) ∨ Г ( х) А3) Ш (пятачок ) Вопрос) ∃хМ ( х) 3. Сколемизация: отбросить все кванторы (кванторы всеобщности просто отбрасываются, а переменные, которые были связаны с квантором существования, заменяются либо на константы Сколема, либо на функции Сколема: на константу, если левее не было квантора всеобщности, иначе на функцию от всех переменных, стоящих слева в кванторе всеобщности). Примеры: ∃x∀y∃zP ( x, y , z ) = P ( a c , y, f c ∀x∀y∃zP ( x, y , z ) = P ( x, y , f ( x, y )) c ( y )); 4. Получение дизъюнктов: ( P ( x ) ∨ R ( x )) & (G ( x ) ∨ K ( x)) ( P ( x ) ∨ R ( x )) - первый дизъюнкт (G ( x ) ∨ K ( x )) - второй дизъюнкт P( x) ∨ R ( x) & G ( x) = ( P( x) ∨ R( x)) & ( P ( x) ∨ G ( x )) (по дистрибутивному закону) В примере (1) получаем: Д1) ¬Г ( х) ∨ М ( х) Д2) ¬Ш ( х) ∨ Г ( х) Д3) Ш (пятачок ) ¬∃хМ ( х ) = ∀х¬М ( х ) ¬М ( х ) Д4) ¬М ( х ) ∨ Отв ( х ) Из двух дизъюнктов получаем третий и т.д. В результате получаем пустой дизъюнкт. Принцип силлогизма: А → В, В → С ├ А → С 21 ¬А ∨ В получаем ¬А ∨ С ¬В ∨С Вопрос: Д3) Ш (пятачок ) Д5) ¬Ш (пятачок ) Д3-Д5: пустой дизъюнкт ¬А ∨ В ∨ ¬С ¬В ∨ D ∨ Е ¬А( х ) ∨ В ( х ) ¬В ( у ) ∨С ( у ) получаем ¬А ∨ ¬С ∨ D ∨ Е разные аргументы у предикатов, следовательно используем унификацию. Переменная заменяется либо на переменную, либо на константу, либо на функцию. у меняем на х: получим ¬А( х) ∨С ( х) . Для примера (1): Д1-Д2: Д5 ¬Ш ( х) ∨ М ( х) Д3-Д5: Д6 М (пятачок ) меняем х на пятачок Д4-Д6: пустой дизъюнкт ∨ Отв(пятачок ) Хорновская логическая программа Хорновская логическая программа состоит из фактов и формул. 1) факты имеют вид: <предикат>(<константы>) Ш(пятачок) 2) формулы должны быть вида: А1 & A2 & ... & An → A0 ¬A1 ∨ ¬A2 ∨ ... ∨ ¬An ∨ A0 (только один предикат без отрицания) Перепишем: A0 : −A1 , A2 , A3 ,..., An A0 22 if A1 , A2 , A3 ,..., An Выполняем логические функции и получаем логическую функцию A0 . Язык Prolog <предикат>(<термы>). <предикат>(<термы>):−<предикаты>. это факт это правила или формулы Интерпретатор: swi-prolog Компилятор: gprolog 1. факты и правила оформляются в виде отдельного файла (prog.pl) 2. включается программа в командной строчке $swipl 3. подключаем файл: ?-consult(prog). 4. теперь можно задавать вопросы: ?-<предикат>(<термы>). Программа на Прологе (предикаты пишутся строчными буквами, переменные прописными): Файл shar.pl : m(X) := g(X). g(X) := s(X). s(‘Pyatak’). В командной строчке: $swipl ?-consult(shar). ?-m(X). x=Pyatak Yes ?-g(‘Pyatak’). Yes ?-s(‘Vinny’). No ?- спросили есть ли у Винни-Пуха шарик Предикаты с двумя аргументами catty(‘Murka’). mouse(‘Mikky’). fish(‘Mintay’). 23 eat(X,Y):-catty(X),mouse(Y). eat(X,Y):-catty(X),fish(Y). ?-eat(X,’Mintay’). X=Murka Трассировка: ?-trace. ?-m(X). call m(_G283) call g(_G283) call s(_G283) exit s(Pyatak) exit g(Pyatak) exit m(Pyatak) 24 (Кто есть минтай?) (для примера с Пятачком)