Predicate Logic Flashcards
What is the name for specific objects (a,b,c)?
Constants
What are variables (xyz)?
Placeholders for arbitrary objects
What can Fx be thought as?
It [x] is F
What do predicates do?
Establish relationships
Give the semantics for the universal indicator in tableaux
ν(∀xA)=1 iff ν(Ax(kd))=1 for all objects d in the domain
Give the semantics for existential indicator in tableaux
ν(∃xA)=1 iff ν(Ax(kd))=1 for some object d in the domain
What is required in an interpretation for predicate logic?
{D, v}
What do we say about objects in the domain?
For each object d∈D, there is a constant kd that is guaranteed to refer to that object, i.e. ν(kd)=d
Give the semantics for atomics
For atomics, ν(Pnt1…tn)=1 iff the sequence ⟨ν(t1),…,ν(tn)⟩ is in ν(Pn)
(thus, ν(t1=t2)=1 iff ⟨ν(t1),ν(t2)⟩ is in ν(=) iff ν(t1) and ν(t2) are the same object)
State the tableaux rules for universal indicator
∀-rule ¬∀-rule
∀xA __ ¬∀xA ✓
_ ↓ _____ ↓
Ax(t) __ ∃x¬A
Apply to any term t free for x that is on the branch (if no eligible terms, you can introduce new constant).Don’t check off.
State the tableaux rules for the existential indicator
∃-rule ____ ¬∃-rule
∃xA ✓ ____ ¬∃xA ✓
_ ↓ _________ ↓
Ax(t) ______ ∀x¬A
Must use a new constant t that does not already occur elsewhere on the branch.
What are the identity rules for tableaux?
=-rule \_\_ / =-rule A x(t) \_\_\_\_ t/ =t ✓ _s =t \_\_\_\_\_\_ x \_\_↓ A x(s)
Don’t check off either node.
Regarding substitution, when is y free for x in A?
If x is not within the scope of a quantifier over y
What is a tactic for substitution if y isn’t free for x?
Pick another variable (eg z)
What does v do in an interpretation?
Takes a name and spits out an object
What is Kd?
A special name for each object in the domain
What is not permitted in predicate logic?
An empty domain
Otherwise vacuous
In Natural deduction, when can we apply the identity rule (t = t)?
Anytime, it is not an assumption sequence
What is important about the order of letters in =E?
Second letter must be subbed by the first, not the other way around
eg
n (1) Ax(t) …
m (2) s=t …
n,m (3) Ax(s) 1,2 =E
Describe the criteria and process for VI
- Prove that the context A is satisfied by an arbitrary object (to derive that Ax(y) is true for some appropriate variable y
- To prove its arbitrary, we cant have y free in any of the assumptions Ax(y) depends on
- Also cant have y show up free in the universal VxA (eg Fy –> Gy)
How does VE work?
Sub in some term
eg
n (1) VxA …
n (2) Ax(t) 1 VE
^If everything is A then t is A
What is the macro thought for EE?
If you can show arbitrarily that y . ‘ . C, the ExFx . ‘ . C
How do you know y is arbitrary?
y is not free in any other assumptions that B/C depends on
What do we need in the counter-model of Modal Predicate logic?
{D, W, R, v}
What don’t you need to specify in countermodels?
=
How might you write a countermodel that has Rab?
D = {d1, d2}
v(a) = d1
v(b) = d2
v(R) = {}How do Pn predicates work?
P1 = (_) P2 = ( _ , _ ) P3 = ( _ , _ , _ ) etc.
What can things have?
Multiple names (eg v(a) = d1, v(b) = d1)
What is the countermodel structure for predicate logic and how does it differ in Modal Predicate?
D = Set of objects v = Constants --> objects in domain v = Predicates --> a set of objects in domain v = Predicates (P2) --> A set of pairs of objects
Modal same but with accessibility relation, worlds and v of these ^ in each of those worlds (where applicable)
