.121 WK 5-10 Flashcards
Why do we need predicate logic?
encompasses all of propositional logic + expands on its limitations
so it accounts for parts of propositions, links between parts of propositions + quantifiers
What is predicate logic split into?
syntax - notation for concepts + operators used to create formulae
semantics - meaning behind formulae
Explain concepts
terms - similar to subjects, expressed through nouns/pronouns, written as the lower case of the 1st letter
- argument of the predicate so
written as P(a)
predicates - properties/relations among terms, expressed through verbs, written as the upper case of the 1st letter
properties = “is property”
relations = “is the relation of”/”are related”
What are the types of operators?
connectives + quantifiers
What is an atomic formula?
consists of 1 predicate and 1<= terms
functions that take 1+ arguments (constants/variables) and returns true or false (Boolean)
What is a constant?
term desc. specific individual entities
What is a variable?
represents general terms (individuals of the same type or a class rather than specific individuals), written with lower case letters from end of alphabet
takes values from the universe of discourse - set of all entities that can replace a variable in an atomic formula
Atomic formulae can be…
closed/ground formulae - predicate’s arguments are only constants and so are propositions with truth values
OR
open/unground formulae - predicate’s arguments consist of at least 1 variable and so are not propositions as they have no truth value
What is arity of atomic formulae?
number of variables it takes as arguments
e.g. unary (1), binary (2) + n-ary (2+)
if arity…
== 0 - propostion
== 1 - properties
>= 2 = relationships
What are the 2 quantifiers?
universal - every/”for all” (equivalent to a conjunction with all the variables) - denoted by upside down A
negation = not all
existential - at least one/”there exists” (equivalent to a disjunction with all the variables) - denoted by a backwards E
negation = none
What are the rules of inference?
all of propositional plus…
- universal/existential instantiation
- universal/existential generalisation
What is universal + existential instantiation?
universal - if it is true for a variable it is true for a constant of that variable
existential - if it is true for a constant it is true for a constant of that variable
What is universal + existential generalisation?
universal - if it is true for any arbitrary x it is true for every x
existential - if it is true for a constant it is true for a constant of that variable
What is the difference between restricted + unrestricted quantifiers?
unrestricted quantifiers - all elements in the Universe of Discourse - use conjunction
e.g “Every man has 2 legs”
Ax (M(x) -> L(x))
restricted quantifiers - some elements in the Universe of Discourse (a subset) - use implication
e.g “There is a man who has 2 legs”
Ex (M(x) AND L(x))
What functions + properties are needed for a queue?
head + tail pointers
enqueue(item)
dequeue
isEmpty()
isFull() - if bounded
int data
element next
How does enqueue() work?
struct element el = new Element;
el.data = data
el.next = null
if (head == null){
head = el
}
else {
tmp = head
while (tmp.next != null){
tmp = tmp.next
}
tmp.next = el
}
How does dequeue work?
How to create a 2D array?
int array[x][y]
Pros + Cons of 2D arrays
+ random access - very fast
- fixed size (can only grow by copying elements - costly)
- insertion + deletion is costly
What properties + functions does a stack need?
top pointer
isEmpty()
isFull() if bounded
push()
pop()
element prev
int data
How does push(stack, x) work?
struct Element el = new Element
el.data = x
el.prev = null
if (isEmpty(stack)){
stack.top = el
}
else{
el.prev = stack.top
s.top = el
}
How does pop(stack) work?
if (isEmpty(stack)){
underflow error
}
else{
tmp = stack.top
stack.top = stack.top.prev
return tmp.data
}
iteration vs recursion
iteration :
+ memory usage is controlled explicitly by the programmer - stack overflow is less likely
+ can execute more quickly - no overhead from stack frame creation/destruction
- naturally recursive functions can be harder to understand in iterative form
recursion :
+ naturally recursive functions are much more concise when recursively expressed
+ languages which support tail recursion can eliminate some of the extra costs to performance + stack overflow
