74190

Logic programming languages and tools

Лекция

Информатика, кибернетика и программирование

User specifies the specifictions of solution nd the computer derives the execution sequence for tht solution: Let us hve irline flight informtion of the form: flightflight_number from_city to_city deprture_time rrivl_time Then ll the flights from Wshington DC to Snt Clr cn be specified s either direct flights or s flights with n intermedite stop: flightflight_number DC Snt Clr deprture_time rrivl_time or flightflight_number DC X deprt1 rrive1 flightflight_number X Los ngles deprt2 rrive2 deprt2 =rrive130 Unlike...

Английский

2014-12-29

38 KB

0 чел.

Lecture 9. Logic programming languages and tools. Part 1.1

Logic programming language application areas include natural language processing, expert systems, specifications checking, theorem proving, and control systems (among others).

9.1 Definitions

Logic programming languages, also called declarative languages, differ substantially from the other programming languages we have discussed. Declarative rather than procedural: only specifications of results are stated (not detailed procedures for producing them). Most importantly, logic programs do not specify the execution sequence as in most in the case of other language paradigms. User specifies the specifications of a solution and the computer derives the execution sequence for that solution:

Let us have airline flight information of the form:

flight(flight_number, from_city, to_city, departure_time, arrival_time)

Then all the flights from Washington DC to Santa Clara can be specified as either direct flights or as flights with an intermediate stop:

flight(flight_number, DC, Santa Clara, departure_time, arrival_time)

or

flight(flight_number, DC, X, depart1, arrive1)

flight(flight_number, X, Los Angles, depart2, arrive2)

depart2>=arrive1+30

Unlike imperative and functional programming, where implementation is done using a mapping, logic programming uses relations:

  •  In imperative and functional, we say

Given a value x compute mapping(a), i.e. square(4)

  •  In logic programming, we have

Given a value x and y, determine whether x is related to y is true

Consider the relation ParentOf as follows:

ParentOf(X,Y) where X is parent of Y

ParentOf(john, Mary) - John is parent of Mary

Horn clause. Horn clause can have only two forms:

  •  headed: single atomic proposition on left side
  •  headless: empty left side (used to state facts)

A Horn clause is an IF clause and not IFF (if and only if).

Formally,

A0 IF A1 AND A2 AND A3 AND … AND An

Each Ai is a simple assertion of the form Ri(…) where Ri is a relation name.

Informally, this clause means that, if A1, …, An are all true, then we can infer that A0 is also true. But, we cannot conversely infer that A0 is false just because some Ai turns out to be false.

9.2 Logic Programs

A logic program is a collection of Horn clauses.

Basic elements are:

  •  Term: a constant, variable, or structure
  •  Constant: an atom or an integer
  •  Atom: symbolic value of Prolog

Atom consists of either:

 a string of letters, digits, and underscores beginning with a lowercase letter

 a string of printable ASCII characters delimited by apostrophes

  •  Statement:

 fact statements

 rule statements

 query (or goal) statements

  •  Fact statements:

 concrete relations among objects

 used for the hypotheses

 structure:

functor(parameter list)

 headless horn clauses

student(paul).

junior(mary).

  •  Rule statements

 a pattern of relationships among the database objects.

 used for the hypotheses ƒ headed horn clause

 right side: antecedent (if part)

May be single term or conjunction

 Left side: consequent (then part)

Must be single term

 Conjunction: multiple terms separated by logical AND operations (implied)

 Example:

parent(kim,kathy):-mother(kim,kathy).

 Can use variables (universal objects) to generalize meaning:

parent(X,Y):- mother(X,Y).

sibling(X,Y):- mother(M,X), mother(M,Y), father(F,X), father(F,Y).

  •  Query (or Goal) statements

 It is the theorem is in form of proposition that we want a system to prove or disprove

 Same format as headless Horn

student(james)

A logic program consists of a database of the following:

  •  Fact statements
  •  Rule statements

9.3 Inferencing Process

9.3.1 User query

Computation in a logic program consists of testing a given assertion (query) A. The testing of a query A can be implemented by a process called matching, satisfying, or resolution. The facts and the rules of the program are used to determine which substitutions for variables in the query (called unification) are consistent with the information in the database. If we can infer from the clauses of the program that A is true, then we say that A succeeds. Otherwise, we say that A fails. Note that this does not mean that A is false. For example, Prolog as an interpreter, prompts the user for an input query and outputs the truth value (“yes”) or falsity (“no”) of that query and an assignment to the variables of the query that make the query true (that unifies the query).

If a goal is a compound proposition, each of the facts is a subgoal. To prove a goal is true, must find a chain of inference rules and/or facts. For query Q:

B :- A

C :- B

Q :- P

Process of answering a query is called matching, satisfying, or resolution. Resolution types:

  •  Bottom-up resolution, forward chaining. Begin with facts and rules of database and attempt to find sequence that leads to goal. This works well with a large set of possibly correct answers
  •  Top-down resolution, backward chaining. Begin with goal and attempt to find sequence that leads to set of facts in database. This works well with a small set of possibly correct answers

Prolog implementations use backward chaining.

9.3.2 Query Processing

1) If the program contains a fact ‘A0’, such that A0 matches A, then we immediately conclude that A succeeds.

2) If the program contains a clause ‘A0 if A1 and … and An’ such that A0 matches A, then we proceed by testing A1 and…and An separately as (sub)queries.

a) There are two approaches:

 depth-first search: find a complete proof for the first condition before working on others (Prolog uses depth-first search)

 breadth-first search: work on all conditions in parallel

b) If all succeed, then we conclude that A succeeds. If one of the Ai fails, then we must backtrack, i.e., give up the attempt to use this particular clause and try another clause instead.

c) Only we have exhausted all clauses whose left-hand sides match A can we conclude that A fails.

9.3.3 Unification in resolution

Unification is the process of finding values for variables in propositions that allows matching process to succeed. To unify two expressions U and V, we need to find substitutions for the variables occurring in U and V that makes the two expressions identical. Generally, it is denoted by σ and written as Uσ = Vσ.

Example 1. To unify the two expressions: R1(X,John) with f(g(John), Z) bind X to g(John) and Z to John to get f(g(John), John) as the unified instance of both expressions.

If the database contains the fact ParentOf(John, Mary) then the unification of the following query:

ParentOf(X,Mary)=ParentOf(John,Y)

would be

ParentOf(John,Mary) 

where X is substituted by John and Y is substituted by Mary.

Example 2.

There are 6 facts in the database. The fact mother(anna,peter) states that Anna is Peter’s mother, and so on. The fact father(joe,peter) states that Joe is Peter’s father, and so on.

mother(anna,peter).

mother(anna,clara).

mother(mary,anna).

father(joe,peter).

father(jim,clara).

father(tom,joe).

There are 2 rules:

grandmother(X,Y) :- mother(X,Z), mother(Z,Y).

grandfather (X,Y) :- father (X,Z), father(Z,Y).

The rule grandmother(X,Y) states that X is a grandmother of Y if and only if X is a mother of Z and that Z is a mother of Y.

The rule grandfather(X,Y) states that X is a grandfather of Y if and only if X is a father of Z and that Z is a father of Y.

The goal:

?- grandfather(tom,X).

asks, whose grandfather is Tom.

According to the rule and facts the answer is

X=peter

So Tom is Peter’s grandfather.

The goal:

?- grandmother(X,peter).

asks, who is Tom’s grandmother.

According to the rule and facts the answer is

X=mary

So Mary is Peter’s grandmother.

Example 3. The programmer supplies a list of facts and rules:

Rules:

  •  Eagle has feather.
  •  Eagle has beak.
  •  Eagle has two legs.
  •  Betty eats vegetables.
  •  Chicken eats seeds.
  •  Chicken has two legs.

Facts:

  •  If someone eats meat then it is a carnivore.
  •  If someone has feather then it is a bird.
  •  If someone eats X then X is food.

Finally, the programmer can ask questions based on those facts and rules, such as:

  •  Is eagle a bird?
  •  Is chicken a bird?

The language engine then tries to apply the rules to answer the questions, e.g.:

  •  Yes (meat is a food).
  •  Yes (eagle and chicken are bird).

Note that the answers are based only on the available information.

1 http://www.seas.gwu.edu/~bell/csci210/lectures/lp.pdf


 

А также другие работы, которые могут Вас заинтересовать

78505. Психологические факторы готовности студентов к развитию интеллектуальной сферы школьников 53.43 KB
  В современных условиях интеллектуальному развитию школьников придаётся особое значение наряду с другими развивающими целями и задачами обучения. Развитие интеллектуальной сферы школьников рассматривается многими исследователями как условие пронизывающее весь учебный процесс. В этой связи своевременным становится вопрос о специальной подготовке будущих учителей к работе по развитию интеллектуальной сферы школьников.
78506. Решение психологических задач как средство повышения качества профессиональной подготовки воспитателей дошкольных образовательных учреждений 60.47 KB
  В преподавании психологии могут применяться задачи на установление соответствия между теоретическими понятиями и закономерностями и примерами их использования задачи по психологическому анализу поведения литературных героев или известных людей задачи по психологическому анализу частных жизненных или учебных ситуаций и др. Первоначальные попытки создать задачи по психологии работы А. Задачи широко используются при изучении общей возрастной педагогической психологии в вузах Сборник задач по общей психологии 1974; Ф. Задачи по детской...
78507. Психологическая компетентность воспитателя дошкольного образовательного учреждения 64.96 KB
  В психологии общепринятой является точка зрения согласно которой понятие компетентность включает знания умения навыки а также способы выполнения деятельности. Огарев понимает компетентность как устойчивую способность к деятельности со знанием дела. Автор отмечает что компетентность является категорией оценочной и характеризует человека как субъекта специализированной деятельности где развитие способностей человека дает ему возможность выполнять квалифицированную работу принимать ответственные решения в проблемных ситуациях...
78508. Обучение пересказу литературных текстов детей дошкольного возраста 79.55 KB
  Познавательное речевое и физическое развитие детей дошкольного возраста А. Науменко Обучение пересказу литературных текстов детей дошкольного возраста В настоящее время все меньше и меньше внимания педагоги на занятиях по развитию речи уделяют обучению пересказу литературных текстов детей дошкольного возраста. Ведь грамотно построенное занятие по обучению детей пересказу оказывает влияние на все стороны развития личности ребёнка: умственное нравственное эстетическое и конечно речевое развитие. Вопросы обучения пересказыванию детей...
78509. Режимные процессы как средство обогащения словарного запаса детей первой младшей группы 60.02 KB
  Режимные процессы как средство обогащения словарного запаса детей первой младшей группы Необходимость взаимосвязи разных сторон речи при обучении родному языку очевидна. Цель исследования: выявление значимости целенаправленного педагогического воздействия на обогащение и активизацию словаря детей третьего года жизни при проведении режимных процессов. Предмет исследования – режимные процессы как средство обогащения словаря детей первой младшей группы. Гипотеза исследования на обогащение и активизацию словаря детей третьего года...
78510. Объединение сетей средствами сетевого и транспортного уровней: протоколы, адресация, маршрутизация 26 KB
  Это отличает их от протоколов канального уровня которые передают пакеты только получателям в той же ЛВС. Для сетевого уровня необходима адресация. Протоколы сетевого уровня многоуровневой модели сетевого взаимодействия отвечают за передачу данных от отправителя к получателю по интерсети. Самый популярный протокол сетевого уровня – протокол IP IPадрес привязывается к сетевому адаптеру который выполняет упаковку пакета данных транспортного уровня в дейтаграмму идентификацию систем в сети по их IPадресам определение наиболее эффективного...
78511. Основные типы аппаратных сетевых устройств: назначение, принципы функционирования, характеристики 28 KB
  Поэтому адаптеру необходим буфер для временного хранения данных прибывающих от компьютера или из сети в то время когда адаптер занят формированием кадра и его подготовкой к обработке. Концентратор обычно имеет несколько портов к которым с помощью отдельных физических сегментов кабеля подключаются конечные узлы сети – компьютеры. Концентратор объединяет отдельные физические сегменты сети в единую разделяемую среду доступ к которой осуществляется в соответствии с протоколов локальных сетей. Приемопередатчики трансиверы и повторители...
78512. Технологии удаленного доступа и глобальных сетевых связей 37 KB
  Понятие удаленного доступа к сети включает различные типы и варианты подсоединения одиночных компьютеров либо малых домашних или офисных сетей к территориально отдаленным крупным сетям. Подключение к глобальной сети может осуществляться одним из способов: удаленный доступ по коммутируемой телефонной линии. Наиболее развитыми но не единственными сетями такого типа являются так называемые сети с интегральными услугами ISDN цифровые сети с интегральными услугами в которых не только осуществлен переход к полностью цифровой форме передачи...
78513. Назначение и функции операционных систем, их архитектурные типы, классификация и основные семейства 27.5 KB
  ОС – это комплекс управляющих и обрабатывающих программ, который, с одной стороны, выступает как интерфейс между пользователем и аппаратными компонентами вычислительных машин и вычислительных систем, а с другой стороны предназначен для эффективного управления вычислительными процессами