PL Flashcards
What is the goal of logic? (3)
- state statements which are know to be true - called “knowledge base”
- state statements that describe the current state of the world - called “premises”
- state statements for which we want to check whether they are true - called “conclusions”
What are 2 elements of propositional logic?
propositional logic: simple statements + complex statements
why is propositional logic a “weak” language?
-> which form of logic does not have those problems?
- letters just describe complete states - we cannot talk about individuals
- we cannot talk about properties of individuals or relationships between individuals
- generalisations, patterns or regularities cannot easily be expressed
-> first order logic is expressive enough to represent this kind of information
what are tautologies?
> what are those also called?
tautologies: a statement where any combination of the arguments evaluates to the statement being TRUE
> those are also called “valid” statements
what are contradictions?
> what are those also called?
contradictions: a statement where any combination of arguments evaluates to the statement being FALSE
> those are also called “invalid” statements
when is a statement called satisfiable?
a statement is called satisfiable when it is neither a tautology nor a contradiction
> statement evaluates to TRUE for some combination of argument values and FALSE for others
why is it impossible to construct a SAT solver that solves all problems fast?
why do modern SAT solvers perform well anyway?
satisfiability problems are NP-complete.
> the amount of possible variable assignments grows exponentially
> however, search space only has to be fully searched in worst cases, which do not occur often
what is a unit clause?
a clause of length 1
what is a pure literal?
literal p is pure if not(p) appears nowhere
empty clause is trivially….?
empty set of clauses if trivially…?
empty clause is trivially false
> at least one of the arguments has to be true
empty set of clauses is trivially true
> all of these have to be true
what is DLCS/DLIS?
how does it work?
DLCS: dynamic largest combined sum
- pick v with highest CN(v) + CP(v)
- if CP(v) > CN(v) set v = 1 else v = 0
DLIS: dynamic largest individual sum
- pick v with highest CN(v) or highest CP(v)
- if CP(v) > CN(v) set v = 1 else v = 0
how does the Jeroslow-Wang heuristic work?
pretty much the same as DLCS/DLIS, but different weighting system for the occurences in clauses
> occurences in small clauses are weighted higher
how does MOMS heuristic work?
MOMS: maximum occurences in clauses of minimal size
> preference is given tto clauses with large numbers of x or x’ in them
> focus on the currently smallest size clauses
