Nyhetsflöde

Hi

I got a question concerning the extra slides I showed in lecture 1.

I presented some background in the form of slides about om propositional (boolean) logic and predicate logic.from the course DD1350 (F2,F3,F4) autumn 2017. The same material in presented in the autumn 2018 in DD1351.

You can find material of this type on the net e.g. in wikipedia and on other sites.

I will summarize what of all this information is essential in this course,

but probably not before tomorow's exercise session.

If you want to look for info yourselves , you could use e.g. .search phrases like som "propositional logic".,"predicate logic",  "Natural deduction"

Best regards -Thomas S.

Summary of lecture week 7

How to  implement apply in Prolog. map_list as an example of "higher order programming" à la functional programming.

Meta programming. The primitives var, nonvar, ground.

arg and functor to construct and deconstruct terms.

How to collect all solutions in a list: The primitives findall, bagof and setof.

Self interpreters. The Vanilla prolog interpreter.

Expert systems in Prolog.

Summary of lecture week 6

DCG syntax (Definite clause grammar) to express context dependent grammars directly in Prolog.

How DCG rules are translated into Prolog clauses while xonsulting or compiling.

How you can say that DCG uses difference lists.

Use of DCG rules to write a program that models state transitions,e.g. ab interpretater for a programming language.

Summary of lecture week 5

Negation with the NAF-rule (negation as failure).

We defined the !-primitive (cut) and introduced "if-then-else"-syntax.

Search in graphs, and problem formulation med generate-and-test.

permute to generate all possible permutations of a list.

Some examples: N-queens, missionaries and cannibals,

Finding a path in a graph. Avoiding loops in graph search.

Different search methods for parallellism in Prolog was skipped.

All questions on the material are welcome! Use e-mail or this News feed.

Summary of the lecture week 4

Algorithms over trees and lists. A dictionary implementerad with a sorted open-ended binary tree. reverse, append, merge to keep lists sorted. Defining flatten on nested lists.

The accumulating parameter technique. append3. Considering the complexity. Using append3 to divide a list in three parts. Which is better ((app o app) o app)  or (app o (app o app))  (using o for relation composition)?

Difference lists. Implementing append for difference lists. Complexity. Consider similarities between using difference lists and the accumulating parameter technique.

Generalising an algorithm by defining separate clauses for representations and equality.

"abstract data types", keeping the represenation separated from the algorithm.

Summary of the lecture week 3

I presented the model theory for logic programs.

Important concepts:

Herbrand Universe (or term universe) is the set of objects that the program talks about. It is constructed by forming all possible terms using the constants and functors occurring in the program. This set might be finite or infinite.

Herbrand interpretation (or term interpretation) is a set of atoms formed from the Herbrand (term) universe and the repation symbols of the program.

Least Herbrand model. It is the smallest set (a Herbrand interpretation) containing exactly all true atoms in the program and nothing else.

I presented a method how to construct the Least Herbrand model using a fixpoint computation.

I introduced search trees, proofs and proof trees.

I mentioned the soundness and completeness of the SLD-resolution rule.

We then went over to some actual programs.

- proving some arithmetic axioms

- some simple algorithms over trees

I then introduced lists as a subset of structures

- list syntax

- the append relation and its uses:

1) to concatenate sequences represented as lists

2) using append "backwards" to find the initial (or final)  part of a list constructed by append and another list.

3) to use append to split a list in two parts.Non-deterministic execution giving all possible subdivisions of a list into two.

Post from the news feed on the course ID2213 logic programming

summary of lecture 2 :

I presented the unification algorithm that handles the equality theory in logic programming. 

I also showed how you normally describe the "declarative meaning" of logic programs  ("the model theory").

Prolog works using the proof rule Modus Ponens, i.e. to use implication in a proof together with unification of logical variables. This method for proof construction is called SLD resolution.

The unification algorithm generates equalities that are needed in order to prove the statement you are asking for.

When you describe this you speak about  "substitutions", a mapping of variables to their values.

This is also called the  "binding environment" and is the "values" you get as a result of an execution-

NB that substitutions are a way to describe what the program does, and they are not handled explicitly in programs.

Examples of programs where presented where unification is especially important:

- family relations with structured information about the individuals.

- The Zebra problem, a famous kind of puzzle where the reppresenation is important.

Please ask your questions about exercises in this thread! Then other students who might have the same kind of questions will see our discussion.

It is also possible to send me e-mail and I will answer as soon as possible.

Summary of lecture 1:

- general info about the course, learning objectives, examination, project, textbook, reading instructions in the course-PM, alternative literature, Prolog systems to use

- a little history about logic, its role in philosophy, automatic resoning, AI and in computer science

Logic was from the beginning a way to handle knowledge and to structure arguments.

Today the focus lies on formal proofs in mathematics and on mechanised  (computer based) reasoning.

In philosophical logic you  study proof systems. What strengths do they have? What can you prove?

How do you handle paradoxes and unprovable satatements? Is there a difference between truth and provability?

How can you defend an argument?

What do we know? Which statements have unambiguous truth values  ("true" T, or "false" F)=

- propositional logic (Boolean logic)

The connectives and their respective truth tables

conjunction ("and", "&", "^", ",")

disjunction ("or", "v", ";"),

implication ("if", "->", "<-", ":-"),

equivalence ("if and only if","iff", "<->"),

negation ("not", "\+")

- Predicate logic

logical variables

quantifiers,   "for all", "exists"

scope rules in predicates

Proof rules expressed with natural deduction.

- Logic programming: To use construction of logical proofs as a programming language

SImple Prolog programs.

A family database.(homework: to define some family relations).

What kind of data is there in Prolog? (constants and compound terms)

The syntax of Prolog statements (facts and rules defining relations)

- Abstract description of the execution of a Prolog program

The equality theory, what is a "substitution" (in the description)

The result of an execution is the answer "yes" or "no"

With a "yes" the system often delivers bindings for the unbound variables that are in the question (the "query") , a part of a substitution that we call the "binding environment".

This can be understood as a number of conditions:

("I constructed a proof of your statement and assumed that these variables have these values").

How the unification algorithm that handles this works and what programs "mean" declaratively (the "model theory") we bring up next time.

Have a nice weekend!

-Thomas

Still no schedule occurs. I plan to get the lectures synchronised with the course ID1213 so that they occur in the afternoon of the same day. All events in ID2213 are not duplicated in english in ID2213, but lectures are, more or less, even though the content might be covered in different fashion.