Brainscape's Knowledge GenomeTM

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


See full index

CS3105 AI > 2: Logic > Flashcards

2: Logic Flashcards

1
Q

What is logical resolution?

A

A rule of inference that can be repeatedly applied to a set of sentences in propositional or first-order logic to allow a proposition to be proven or refuted.

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

What is Curry-Howard Isomorphism?

A

The idea that computer programs can be seen to be equivalent to mathematical proofs under certain circumstances.

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

What is Cook’s Theorem?

A

The satisfiability problem is NP-complete. In NP: can nondeterministically solve it in polynomial time; NP-complete: any other problem in NP can be reduced to from the satisfiability problem.

Since the satisfiability problem leads to propositional logic, we can, therefore, say that propositional logic is NP-complete.

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

What is Propositional Logic?

A

A branch of logic examining propositions, which are true or false.

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

What is Robbins Algebra?

A

A simple algebraic syntax and logical system with only binary (⋁) and unary (¬) operations.

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

What is Robbins’ Conjecture?

A

That every Robbin’s algebra is a Boolean algebra.

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

What rules must Robbins algebra obey?

A
  1. Associativity
    • a ⋁ (b ⋁ c) = (a ⋁ b) ⋁ c
  2. Commutativity
    • a ⋁ b = b ⋁ a
  3. Robbins’ Equation
    • ¬(¬(a ⋁ b) ⋁ ¬(a ⋁ ¬b)) = ¬a
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What did the proving of Robbin’s conjecture show?

A

It was proven with automated AI techniques in 1996, showing that computers can outperform mathematicians in some areas. The proof wasn’t long, just difficult to find.

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

What is automated reasoning?

A

An area of computer science involving using computers to perform tasks relating to fact verification, especially in application to tasks are difficult for humans to perform or solve. With AI it almost always involves logical reasoning in proving mathematical hypotheses or logical propositions.

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

What is logic?

A

Reasoning conducted or assessed according to strict principles of validity. The systematic use of symbolic and mathematical techniques to determine the forms of valid deductive argument.

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

What is symbolic logic?

A

The branch of logic involving the use of symbols to denote propositions, terms, and relations in order to assist reasoning. The symbols can usually be processed to relate them to the real world, and are chosen to model the real world.

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

Why are there multiple types of logic?

A
  1. different logical systems would be more efficient and easy to use in certain applications; often involves the tradeoff between the expressive power of a logical system and the ease of reasoning in it: ease of writing and accuracy of writing things equating to what we wish to express.
  2. Different logical systems give us different results for the same problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is ontology?

A

The study of “the nature and essence of things or of existence”. The branch of metaphysics that studies the nature of existence or being as such.

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

What is epistemology?

A

The study and theory of knowledge, especially with regard to its methods, validity, and scope, and the distinction between justified belief and opinion.

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

What are epistemological commitments?

A

The different types of knowledge that are possible

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

What are the symbols of Propositional Logic?

A
  1. NOT
    ¬
  2. AND
    ∧, ∩
  3. OR
    ∨, ∪
  4. XOR
    ⨁, ⊻
  5. Implication
    ⇒
  6. Equivalence
    ↔
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does it mean for two propositional formulae to be equivalent?

A

Two logical expressions are said to be equivalent if they have the same value in all circumstances.

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

What does it mean for a formula to be valid?

A

Every possible way of assigning T/F values to the variables makes the formula true

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

What does it mean for a formula to be satisfiable?

A

At least one way of assigning T/F values to the variables makes the formula true

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

What is CNF?

A

Conjunctive Normal Form is a form of propositional logic formula that involves certain syntactic restrictions. CNF formulae are made of conjoined (ANDed) clauses, each clause being made up of disjointed (ORed) literals.

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

What is the value of an empty CNF clause?

A

False

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

What is the value of an empty set of CNF clauses?

A

True

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

What is First Order Logic?

A

A set of logical systems that uses quantified variables in sentences to assess propositions. First order statements about atoms are only about the atoms, whereas second-order statements can also be about first-order statements, third order ones can also be about second-order ones, etc.

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

What is FOPL?

A

A set of logical systems that uses quantified atoms, functions, predicates, and sentences to assess predicates. First order statements about atoms are only about the atoms, whereas second-order statements can also be about first-order statements, third order ones can also be about second-order ones, etc.

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

What are FOPL formulae compromised of?

A

Terms (atoms and variables), functions, predicates, connectives, and quantifiers.

26
Q

What are FOPL predicates?

A

A statement that may be true or false depending on the values of its variables, that can be ~ thought of as a truth function.

27
Q

What are FOPL sentences? What are atomic and complex sentences?

A

A statement that we can legally make which can
have a truth value (true or false). Atomic sentences are predicates applied to the correct number of terms or na equality between terms. Complex sentences are built from other sentences using connectives like propositional connectives (and, or, not, implies, equivalence) and quantifiers (for all, exists).

28
Q

How do you convert from FOPL to CNF?

A
  1. Eliminate connectives, inc implications, other than AND, OR, and NOT
    a) Implication written as ⇒
    b) Change implications to a NOT and an OR
    - A ⇒ B → ¬ A ∨ B
  2. Move negations inwards
    a) ! (! A || B) → A & (! B)
    b) ! [A ((! B) || C)] → [ A B & (! C)]
  3. Standardise quantified variable names apart
    a) each variable has diff name inside each bracketed “scope block”
    b) rename as letters from A
  4. Skolemise existentially quantified variables:
    a) existentially quantified variable is an ∃-based variable inside one or more ∀
  5. Drop universal quantifiers
    a) remove all ∀ operations
    b) don’t replace with anything
  6. Distribute ⋀ over ⋁
    a) ⋀ joining clauses, ⋁ within clauses
    b) A or B → A and (B or not B)
    c) A and ! B → A or B
  7. tidy up
    a) remove tautologies
    b) Remove true/false constants
29
Q

What is Inferential Equivalence in CNF?

A

When you convert from FOPL to CNF, the original sentence is not fully equivalent to the CNF formula it is converted into, meaning that the CNF sentence unsatisfiable iff the original is unsatisfiable.

This is unlike when you convert from propositional logic to CNF, in which the original sentence is fully equivalent to the CNF formula.

30
Q

How do semantics relate to FOPL?

A

The semantics of logic involves identifying and interpreting sensible contexts in logic. Contexts relate to a model and allow you to know if certain conditions are true.

31
Q

What are models in relation to FOPL?

A

Representations of the contexts that allow us to analyse the truth of sentences in logic.

32
Q

What are interpretations in relation to FOPL?

A

Methods of understanding the meaning of logic sentences in a given context of a given model.

33
Q

What is an atomic sentence in FOPL?

A

Atomic sentences are predicates applied to the correct number of terms or an equality operation between terms.

34
Q

When are atomic FOPL sentences without any variables true?

A

If and only if the objects referred to by the terms in the atomic sentence satisfy the relation referred to by the sentence.

35
Q

What is equality in FOPL?

A

A = B is true if A is the same object as B (same “pointers”).

36
Q

What is Entailment?

A

???

37
Q

What is semantic entailment in FOPL?

A

???

38
Q

What is Gödel’s Completeness Theorem?

A

???

39
Q

What does it mean for a logical method to be sound?

A

???

40
Q

What does it mean for a logical method to be complete?

A

???

41
Q

Is resolution sound? Is resolution complete?

A

Yes. Yes.

42
Q

How do you resolve a set of propositional logic clauses?

A

Think of each clause in a clause set and repeatedly seek complimentary literals in different clauses, forming new ones called resolvent clauses by combining the 2 source clauses with the complimentary literals removed. Repeat this until an empty clause is formed showing the proposition to be false or until no more resolvent clauses can be made, showing the proposition to be true.

43
Q

How do you resolve a set of FOPL clauses?

A

Convert them all into CNF, and join them with AND operations into a single formula. Then repeatedly eliminate

44
Q

What are existential terms in FOPL?

A

Terms (atoms and variables) relating to their own existence, defined by an ∃ operator inside one or more ∀ symbols.

45
Q

What are universal variables in FOPL?

A

Variables (identifiable elements subject to changes in value) which are present throughout an entire statement.

46
Q

How can you distinguish universal variables and existential terms in FOPL?

A

We use universals starting with capitals, existentials with lower case.

But Russell & Norvig do the opposite: existentials starting with capitals, universals with lower case.

47
Q

What is a substitution with respect to clauses? What is it aka?

A

When you replace all the terms in a clause with new variables. The original terms must not contain any existing variables but must be able to contain new ones. The clause Cφ or SUBST(C, φ) is deduced by substitution from the original clause C.

Substitution is aka Universal Instantiation by Russell & Norvig.

48
Q

What is Unification?

A

???

49
Q

What is a Unifier substitution?

A

???

50
Q

What is a Most General Unifier?

A

???

51
Q

What is the Unification Algorithm?

A

???

52
Q

What is the UNIFY-VARIABLE algorithm?

A

???

53
Q

What is Binary Resolution?

A

???

54
Q

What is Factoring?

A

???

55
Q

What is EQP?

A

???

56
Q

What is Equality Reasoning?

A

???

57
Q

What is Demodulation?

A

???

58
Q

What is Paramodulation?

A

???

59
Q

What is Unification? What is Associative-Commutative Unification?

A

???

60
Q

What is Automated Theorem Proving?

A

???

61
Q

What is the Resolution Inference Rule?

A

???

62
Q

What is a substitution?

A

When you convert from a clause containing functions and variables to another with only constants.

CS3105 AI (8 decks)

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