Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

333 > Chapter 16 > Flashcards

Chapter 16 Flashcards

1
Q

Other name for Logic programming languages

A

Declarative Programming languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How are logic programs expressed?

A

Form of symbolic logic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is it declarative or procedural?

A

Declarative: Only specify the form of results

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a proposition?

A

Logical statement that can be true or false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does a proposition consist of?

A

1+ objects and Relationships among objects

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the 3 basic needs of formal logic?

A

Express propositions
Express relationships between propositions
Describe how new propositions can be inferred from other propositions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is 1st order predicate calculus.

A

Form of symbolic logic that is used for logic programming

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Object representation in predicate calculus

A

Represent objects in propositions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a constant in predicate calculus?

A

A symbol that represents a particular object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a variable in predicate calculus?

A

A symbol that can represent different objects at different times

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Is variables in imperative languages the same as in predicate calculus?

A

No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the 2 types of propositions?

A

Atomic propositions
Compound propositions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How does atomic propositions differ from compound propositions?

A

Compound propositions represent mathematical relations (written like mathematical functions)

Atomic propositions are represented by compound terms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the 2 parts of a compound term?

A

Functor (function symbol that names the relation)

Ordered list of parameters (tuples)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Example of a compound term:

A

student(jon)
like(seth, osx)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the 2 forms of propositions?

A

Fact: (assumed to be true)
Query: Truth of a proposition is to be determined

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Example of fact and query

A

Fact = Jon is a student
Query = Can you prove that Jon is a student?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are compound propositions?

A

2+ atomic propositions where atomic propositions are connected by operators

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the 5 logical Operators?

A

negation
conjunction
disjunction
equivalence
implication

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How many logical operators are there?

A

5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are the quantifiers and and what do they mean?

A

Universal (upside down A) AX.P -> For all X, P is True

Existential (Backwards E) EX.P -> There exists a value of X such that P is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

How do we infer facts from known propositions?

A

Using resolution since resolution is an inference principle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What does the unification process do?

A

Finds values for variables in propositions that allow the matching process to succeed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is instantiation?

A

Assigning temporary values to variables to allow unification to succeed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What happens if matching fails when instantiating a variable?

A

You backtrack and instantiate the variable with a different value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Steps of Proof by Contradiction

A

Hypotheses (set of assumed propositions)
Theorem (new proposition we want to infer)
Goal (Negation of theorem stated as a proposition)
Proof by contradiction (Theorem proved by finding an inconsistency with the goal)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What are Horn Clauses?

A

An “if-then” statement

28
Q

What are the different types of Horn Clauses?

A

Headed (single atomic propositions on the left)
Headless (Empty left side)

29
Q

Headed Horn Clause example

A

Rich(X) ∨ WorksHard(X) ∧ OwnsBusiness(X)

Rich(X) (Someone is rich) is true if WorksHard(X) (they work hard) and OwnsBusiness(X) (they own a business) are both true.

30
Q

Headless Horn Clause

A

father(bob, jake)
bob is the father of jake

31
Q

What type of clauses are
1) Facts
2) Queries
3) Rules

A

1+2) Headless
3) Headed

32
Q

Which is simpler, Logic programming semantics or imperative language semantics?

A

Logic programming

33
Q

Overview of logic programming

A

Programs only state the form of the result (not how its computed)
Uses predicate calculus (descriptive

34
Q

Difference between imperative and logic using a “Sort the list” example

A

imperative = Describe Alg. to sort the list. Computer executes the steps of the Alg

Logic = describe the characteristics of a sorted list

35
Q

Why was prolog designed?

A

For natural language processing

36
Q

When was prolog designed?

A

1970s

37
Q

A constant, variable or structure describes what in prolog?

A

A term

38
Q

What is a constant in prolog?

A

An atom on int

39
Q

What do atoms consist of in Prolog?

A

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

40
Q

What do variables consist of in Prolog?

A

String of letters, digits and underscores starting with a uppercase letter

41
Q

What are the kind of statements in prolog?

A

Fact, Rule and Goal statements

42
Q

Example of a fact statement:

A

male(bill)

43
Q

Example of a specific rule statement:

A

(right side = if part, left = then part)
ancestor(mary, shelly) :- mother(mary, shelly).

44
Q

Example of a general rule

A

parent(X,Y) :- mother(X,Y).
X is parent of Y if X is mother of Y
or
sibling(X,Y) :- mother (M,X), mother, (M,Y), father(F,X), father(F,Y).

45
Q

Example of a goal statement (the statement that you want to prove)

A

?- man(fred)

46
Q

What are the different inferencing approaches in prolog?

A

Bottom-up/”forward chaining” = begin with facts and rules. attempt to find sequence of matches that leads to goal (building toward goal)

Top-down/backward chaining = begin with goal, attempt to find sequence of matches that leads to facts (break down)

47
Q

What is used when there are multiple sub goals in prolog?

A

Breadth-first search and DFS

48
Q

What is the problem with backtracking?

A

Can take lots of time and space

49
Q

What does the tracing model do in prolog?

A

Display variable instantiations at each step

50
Q

What are the 4 events of the tracing model?

A

Call (beginning of attempt to satisfy goal)
Exit (When a goal has been satisfied)
Redo (when backtracking occurs)
Fail (when goal fails)

51
Q

What does the “is” operator do in prolog?

A

Assigns variable a value
A is B/17 + C

52
Q

What is the difference between the LHS and RHS of the “is” operator in prolog?

A

RHS must be instantiated
LFS must NOT be instantiated

53
Q

Is Sum is Sum + number legal in prolog?

A

No. 1) it is not an assignment statement
2) LHS and RHS cannot be both instantiated and not instantiated

54
Q

Simple Arithmetic Example in Prolog

A

distance(X,Y) :- speed(X,Speed),time(X,Time),
Y is Speed * Time.

55
Q

What are the different types of list structures in Prolog?

A

Simple list: [apple, prune]
Complex list: [[a,b],son(x,bob)]
Empty list: []
List with head x and tail y: [X|Y]

56
Q

What is “_” in prolog?

A

An anonymous variable (is used to “ignore” something like the head of a list for example)

57
Q

What does the “member” proposition do in prolog?

A

Checks if X is a member of Y (member(X,Y))
It is also built in “function”

58
Q

What does append do in prolog?

A

Appends X to Y and makes list Z
append(X,Y,Z)

59
Q

What does the reverse proposition do in Prolog?

A

Reverses the list X and stores it in Y
reverse(X, Y)

60
Q

What are the deficiencies of Prolog?

A

Resolution order control
Closed-world assumption
The negation problem
Intrinsic limitations

61
Q

Why is resolution order control a deficiency of Prolog?

A

It has a unpredictable execution. (the order of execution isnt constant so it might take unexpected routes to the goal)
Programmer can affect efficiency by placing more likely success rules higher up in program

62
Q

Why is the negation problem a deficiency of Prolog?

A

It relies on Horn Clauses. If info is missing the closed-world assumption cant determine truth or falsehood. Which can lead to incomplete negation

63
Q

How is a cut denoted in prolog and what does it do?

A

Denoted by ! and subgoals to the left of the cut cannot be re-satisfied through backtracking

64
Q

What is the problem with closed world assumptions?

A

If the program answers false it isnt necessarily false but could also maybe just not be proven

65
Q

What is the problem with intrinsic limitations?

A

Some tasks are impossible to specify efficiently

66
Q

What are some applications of Logic Programming?

A

RDMS
Expert systems
Natural language processing

333 (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions