fol (first order logic) Flashcards
fol terms
all objects: constants and variables and names. lowercase. (pia, p, 1, x)
examples of names in fol
pia, p, quinn
no numbers and no uppercase and no variables
what is an atomic sentence?
predicate + right number of names
variables of FOL
x,y,z,u,v,w
what does Ex bound in this sentence: ExCat(X)Dog(x)
only cat
what is it called when there is a free variable in the formula?
open formula. Dog(x)
what is a sentence with no free variable?
closed formula. AxDog(x)
what is a well formed formula (WFF)?
open and closed formulas
null quantification
if there are no variables in the formula that the quantifier binds, then the quantifier can be put wide scope around formula
P&AxQ(x) ==> Ax(P&Q(x))
true or false: the universal quantifier distributes over &
true
Ax(P(x)&Q(x)) ==> AxP(x)&AxQ(x)
true or false: the existential distibutes over &
false
true or false: the existential distributes over the v
true
true or false: the universal distributes over the v
false
all quantifiers are widest scope
prenex normal form (PNF)
what is DeMorgan’s for Quantifiers?
~AxP(x) ==> Ex~P(x)
~ExP(x) ==> Ax~P(x)
true or false: a quantifier can apply to an object with no name
true
what is the abominable form?
Ex around conditional
Ex(P(x)->Q(x))
how do you say “All Ps are Q”?
Ax(P(x)->Q(x))
how do you say “some Ps are Q”?
Ex(P(x)&Q(x))
how do you say “no Ps are Q”?
Ax(P(x)->~Q(x))
how do you say “some Ps are not Q”?
Ex(P(x)&~Q(x))
what is a vacuously true conditonal?
always true when the antecedent is false
- all unicorns are magical: true because there are no unicorns
how do you translate this sentence? Ax(P(x)->Q(X))
~Ex(P(x)&~Q(x))
how do you translate this sentence? ~Ax(P(x)->Q(x))
Ex(P(x)&~Q(x))
what is a tautological equivalence?
equivalence that depends just on the truth-function connectives
what does is mean for something to be “null”?
a quantifier that doesn’t bind any variables
translate the sentence into Aristotelian form: “all dogs go to heaven”
Ax(D(x)->H(x))
translate the sentence into Aristotelian form: “some dogs go to heaven”
Ex(D(x)&H(x))
translate the sentence into Aristotelian form: “no dogs go to heaven”
Ax(D(x)->~H(x))
translate the sentence into Aristotelian form: “some dogs don’t go to heaven”
Ex(D(x)&~H(x))
how do you translate a sentence into truth functional form?
- underline full scopes of quantifiers and atomic sentences
- replace identical underline strings of symbols w the same sentence letters
translate the sentence into TFF: ~~ExP(x)->ExP(x)
~~P->P
how do you place sentences using the delete rows method?
- make truth table
- FOL: delete what is impossible
- Logical: delete what is impossible
what is an FO validity?
necessary truths of FOL
- a=a
- any logical truth that depends on =, A, E
- any equivalence of FOL w biconditional between them
what is a FO falsity?
necessary false in FOL
- if the symbols A, E, or = ensure sentence is always false, then it is an FO falsity, not a taut-falsity
- ~(p=p)
place the sentence in FOL: ~(p=p)
fo falsity
what guarantees a sentence is necessarily true?
truth functional form algorithm. tells what is doing the work in a sentence; the connectives or the quantifiers
place the sentence in FOL: (a<b)->~(b<a)
logical truth
how do you say “there are 2 distinct dogs”?
ExEy(D(x)&D(y)&~(x=y))
what does it mean when “X is stronger than Y”?
X entails Y, but Y doesn’t entail X
which is stronger: ExAy or AyEx?
ExAy is always stronger
how do you say “at least n…”
n existential quantifiers (Ex) and enough distinctive clauses (~(x=y))
how do you say “at most n…”
takes n+1 universal quantifiers (Ax)
AxAyAz((D(x)&D(y)&D(z))->(x=y v x=z v y=z))
how do you say “exactly…” in the long way?
combine “at most” and “At least”
-n Es and n+1 As
how do you say “exactly” in the short way?
n existentials and 1 universal