Flashcards

LDS Definitions

SEZ McKelvey English 93 cards

Cards in this deck (93)

1What are the 3 components of a logic?Syntax (definition of the well-formed formulae of the logic)
Semantics (association of meaning and truth to the formulae)
Proof system (manipulation of formulate according to a system of rules)
2What are completeness and soundness?Completeness (all of the true formulae should be provable)
Soundness (a formula that is provable should be true)
3What are formal methods and model checking?Formal methods - use of mathematically-based techniques for hte specification and verification of computer systems (prove that programs have certain properties)
Model checking - branch of formal methods where computer system modelled as some mathematical strycytre (eg a finite state process), then a specific property that a system might have is expressed by some logic fomula
4What are propsitions and what are they represented by?-Declarative sentences that can be either true or false
-Propositions are represented by propositional variables (Bools, atoms) which can take a truth value
5What are the semantics of propsitional logic?All propositional variables take the value T or F
The value of a formula under some truth assignment is ascertained by using the truth tables for the logical connectives
6How many truth assignments and truth tables for a formula have?2^n truth assignments
2^2^n distinct truth tables
7What do satisfy, tautology, contradiction, literal mean?f satisfies a formula if the truth assignment makes the formula evaluate to T
a formula is a tautology if the truth assignment f makes the formula evaluate to T for every f
a formula is a contradiction if the truth assignment f makes the formula evaluate to F for every f
A literal is a propsitional variables or the negation of one
8When are two prop formulae logically equivalent?If they have identical truth tables.
9What are the generalised De Morgan's Laws?
10What are normal form results?A propositional formula in the form where it is built from literals using only /\ and \/ (negations only appear directly in front of variables to create literals)
11What are the generalised distributive laws?
12What is disjunctive normal form? What is conjunctive normal form?A disjunction of conjunctions of literals
A conjunction of disjunctions of literals
13What is the depth of a logic circuit?Maximal distance from any input to the output gate
14What is a proof system?-Defines the proofs (valid mathematical arguments) of the system
It is a collection of rules of interence
15What is an argument form in propsitional logic? When is it valid?A sequence of formulae (fig 1). Valid if whenever a truth assignment f is s.t.
16What is the rule of inference corresponding to the above argument?
17What is the proof system natural deduction?Consists of a collection of valid rules of inference and is used to obtain proofs of sequents (of the form x1,x2|- y)
18What is /\-introduction $What is /\-introduction$
19What is /\-elimination? $What is /\-elimination?$
20What is ¬¬-introduction?
21What is ¬¬-elimination?
22What does it mean if x1,x2|- y is proven?If x1 and x2 are true under some truth assignment, y is necessarily true under this truth assignment.
23What is => elimination?
24What is => introduction?
25What is \/-introduction? $What is \/-introduction?$
26What is \/-elimination? $What is \/-elimination?$
27What is ⊥-elimination?
28What is ¬-elimination?
29What is ¬-introduction?
30What is soundness and completeness within the context of natural deduction?
31What is a theorem in natural deduction?The formula y for which the sequent |- y is provable
32What is the rule of resolution?
33How do we go about resolution?-Given a propsitional formula X
-Take -X and rrite it in cnf as C1/\C2/\.../\Cn
-Start with the clauses C1,C2...Cn
-continually apply resolution rule to infer new clauses
-If we ever infer the empty clause, halt, output X is a theorem
-If we get to the point where we have not inferred the empty clause and we cannot infer any new clauses, halt, output X is not a theorem.
34Why isn't resolution always good at giving a quick answer?-In the worst case, Resolution involves an exponential number of applications
-A reason for this is that application of the resolution rule can result in a new clause of larger size
35What do SAT-solvers do? Compare and contrast with proof systems.Check whether or not a given formula of propositional logic is satisfiable, whereas proof systems aim to prove theorems
-Two tasks are different sides of the same coin
If X is satisfiable, then there is a t.a. making X true - and a t.a. making -X false. ie -X is not a tautology.
If -X is not a tautology, there is a t.a. making -X false, thus a t.a. making X true, thus X is satisfiable
X is satisfiable iff -X is not a tautology
36When are two sets X and Y equal?-Iff they contain exactly the same elements, or
for every x, x∈X implies x∈Y
for every x, x∈Y implies x∈X
37For any set S, what can we say about the ∅?The ∅⊆ S
(if ∅ is not a subset of S there must exist some x ∈ ∅ that is not in S, but such an x cannot exist as ∅ is empty, thus ∅ is a subset of S)
38If A⊆∅, what can we say about A?A = ∅
Suppose that A⊆ ∅ and let x∈ A
So, x ∈ ∅
39What is the power set of S?The set of all subsets of S
if S is of finite size n then P(S) is finite, of size 2^n
40What is the Cartesian product XxY{(x,y) : x ∈ X and y ∈ Y}
41What is the cartesian poduct of A1 x A2 x ... x An?{(a1,a2,...,an) : a ∈ Ai for all i = 1,2,...,n}
42Define disjoint setsTwo sets are disjoint if their intersection is the empty set
43What is the principle of inclusion-exclusion?
44What is the difference of A and B? What is the complement of A?1. Set containing all elements that are in A but not in B
2. Set containing all elements that are not in A.
45How can we use sets/venn diagrams to s give semantics to a formula of propositional logic?Interpret X by assigning sets to each propositional variable, /\ = intersection, \/ = union, negation = complement
46What is a binary relation from A to B?Set of ordered pairs where the first element comes from A and the second comes from B
47What does R(a,b) holds mean?(a,b) is in the binary relation R.
48how can functions be viewed as binary relations?if f : A->B then the graph of f is the binary relation {(a,f(a)) : a ∈ A} ⊆ AxB
49Can every binary relation from A to B be cnsidered to be the graph of a function?No. We need R to have the property that every element a of A appears in exactly 1 element (a,b) of R
If this is so, then f(a) = the unique element b ∈ B for which (a,b) ∈ R
50What is the arity of a relation that is a subset of A1xA2x...xAn?n
51What is the binary relation R on a set A?A relation from A to A (a subset of AxA)
52When is a binary relation reflexive?if (a,a) ∈ R, ∀a ∈ A
53When is a binary relation irreflexive?if (a,a) ∉ R, ∀a ∈ A
54When is a binary relation on A symmetric?if (a,b) ∈ R whenever (b,a) ∈ R, ∀a,b ∈ A
55When is a binary relation on A anti-symmetric?whenever (a,b), (b,a) ∈ R then a=b,b ∈ A
56When is a binary relation on A transitive?when (a,b),(b,c) ∈ R, then (a,c) ∈ R, ∀a,b,c ∈ A
57Let R ⊆ AxB and S ⊆ BxC be relations. What is the composite relation S ∘ R ⊆ AxC defined as?{(a,c) : a ∈ A, c ∈ C, ∃b ∈ B s.t. (a,b) ∈ R and (b,c) ∈ s}
58How do we define R^2 ie composed with itself?{(a,c) a, C ∈ A, ∃b ∈ A s.t. (a,b),(b,c) ∈ R}
59How do we project from an n-ary relation R s.t. R ⊆ A1 x A2 x ... x A n ?Choose i1,i2,...,im ∈ {1,2,...,n} where i1 < i2 < .... < im
Build the m-ary relation S ∈ Ai1 x Ai2 x ... x Ain by taking all those m-tuples that are obtained from some n-tuple of R by only including the elements in coponents i1,i2,...im
The relation S is the projection of R in components i1,i2,...im
60What is the reflexive closure of R?The smallest reflexive relation that contains R, obtained by adding to R all the pairs(x,x) that do not already lie in R.
61What is the symmetric closure of R?The smallest symmetric relation that contains R. It is obtained by adding to R all the pairs (x,y) for which (y,x) (but not (x,y)) lies in R
62What is the transitive closure of R?The smallest transitive relaiton that contains R. It is defined as
{(a,b) : a,b ∈ A, (a,b) ∈ R^n, for some n>=1} = U(n=1, infinity) R^n
63What is an equivalence relation?A relation is an equivalence relation if it is reflexive, symmetric, and transitive
if (a,b) ∈ R, then a and b are equivalent.
64Let a ∈ A. What is the equivalence class containing a?Written as [a]R, it is the set of all elements x that are equivalent to a.
65How can we write out the set A in terms of equivalence classes?A can be written as the disjoint union of distinct equivalence classes.
66What is a partial order? What is a poset?A binary relation that is reflexive, anti-symmetric, and transitive.
A set S together with a partial order R on S is a poset, written (S,R)
67If (S, <=) is some poset then what can we say about two elements of S?They are comparable if either a<=b or b<=a, and incomparable otherwise.
68What is a totally ordered/linearly ordered set?If (S,<=) is a poset and every two elements in S are comparable then S is a totally ordered set, with <= a total ordering.
69What is a well-ordered set?If (S,<=) is a poset and <= is a total ordering and every non-empty subset of S has a least element (under <=) then (S,<=) is a well-ordered set.
70If (A,<=a) and (B,<=b) are two posets then define the lexicographic ordering <= on AxB(a,b) <= (a',b') iff
a<=a a' and a !=a' or
a =a' and b<=b b'
with (a,b) = (a',b') iff a=a' and b=b'
(AxB,<=) is a poset.
71What is a function f from A to B?An assignment of an element of B to every element of A.
72What is the domain? codomain? image? pre-image?the set A
the set B
if f(a) = b then b is the image of a
the pre image of b is the subset {a : f(a) = b} of A
73What is a partial function?One such that either f(a) ∈ B or f(a) is undefined
74What's an injective function?For every a ∈ A and a' ∈ A
if f(a) = f(a') then a=a'
75What is a surjective function?every B ∈ B is such that there exists some a ∈ A s.t. f(a) = b
76What is a bijective function?One that is both injective and surjective.
77Suppose f: A-> B and g : B-> C are functios. What is the composition of g and f?g o f : A-> defined as (g o f)(x) = g(f(x))
78What is the inverse of a function f : A->B?f-1 : B-> A where
f-1(f(a)) = a, every a ∈ A
f(f-1(b)) = b, every b ∈ B
79When does f have an inverse?iff f is a bijection
80When do two sets have the same cardinality?iff there is a bijection from A to B
81When is a set countable? When is a set uncountable?If it is fintie or has the same cardinality as N. (aleph zero)
uncountable if it does not have cardinality aleph zero.
82What is the fundamental building block in first order logic and what is it?The predicate
A predicate symbol is just a symbol with an associated arity
83What is an atomic formula?Given a predicate symbol P of arity r and some variables x1,x2...xr
the formula P(x1,x2...xr) is an atomic formula
84How can we work out if P(x1,x2...xr) is true or false?We need to be given an r-ary relation P' over some domain D, and values v1,v2,...,v2 from D for x1,x2....,xr
85How do we build more complicated formulae from atomic formulae?Using connectives of propositional logic, formulae of the form x = y. These are called quantifier-free formulae.
We can add quantifiers (there exists an element, or for all elements) too, we can apply them to quantifier-free formulae even when there is more than one free variable in the formula.
86Syntax of atoms.If P is a relation symbol of arity r and y1,...,yr are variables or constants, then P(y1,...,yr) is an atom with free variables from y1,...,yr.
If C and D are constant symbols and x and y are variables then C=D, C=x, x=y are all atoms with free variables empty set, {x}, {x,y}
87What is the signature of a formula?Its finite set of predicate (relation) and constant symbols.
88How do we define constructions?if A and B are formulae with free variables free(A) and free(B), then
A\/B,A/\B, -A are formulae
with free variables free(A)Ufree(B), free(A)Ufree(B) and free(A)
If A is a formula with free variables free(A) then
∃x(A), ∀x(A)
are formulae, with free variables free(A)\{x}. x is a bound occurence.
89When is a formula a sentence?If it has no free variables.
90What is an interpretation for a first-order formula A?A domain of discourse D
a value from D for every free variable of A
A relation over D for every relation symbol involved in A
A value from D for every constnat symbol involved in A.
91When are two formulae logically equivalent?If they have the same set of models.
92What is prenex normal form?If a formula is written in the form
Q1x1Q2x2...QkxkA
where each Qi is a quantifier
each xi is a varible
the formula A is quantifier-free
93—