7/9 7. Predicates and Quantifiers Free Online FlashCards

What distinguishes a proposition from a predicate?

A proposition is a complete statement with a definite truth value; a predicate is a statement form whose truth depends on variables or objects.

What is the difference between one-place and two-place predicates?

A one-place predicate describes a property of one object; a two-place predicate expresses a relation between two objects, and argument order can change its meaning.

What is the domain of discourse?

The domain of discourse is the collection of objects that variables may represent. Changing the domain can change whether a quantified statement is true.

How do free and bound variables differ?

A free variable is not assigned a value or governed by a quantifier. A bound variable is governed by a quantifier such as $\forall$ or $\exists$.

What does the universal quantifier $\forall$ assert?

The universal quantifier $\forall$ means “for all” or “for every.” Thus, $\forall x\,P(x)$ says that every object in the domain satisfies $P$.

How do you translate “Every F is G”?

“Every F is G” translates as $\forall x\,(F(x)\rightarrow G(x))$. The conditional restricts the claim to objects that are F.

What is enough to disprove $\forall x\,P(x)$?

A universal statement is disproved by one counterexample: an object $a$ for which $\neg P(a)$ is true.

What does $\exists x\,P(x)$ mean?

The existential quantifier $\exists$ means “there exists at least one.” It permits one object, several objects, or every object in the domain to satisfy the predicate.

What is a witness for an existential statement?

A witness is an object in the domain that satisfies the predicate. One witness is enough to establish that $\exists x\,P(x)$ is true.

How do you translate “Some F is G”?

“Some F is G” translates as $\exists x\,(F(x)\land G(x))$. The conjunction requires the same object to be both F and G.

How is “Every student is present” represented?

“Every student is present” is $\forall x\,(S(x)\rightarrow P(x))$. The student condition belongs in the antecedent, not as a universal conjunction.

Why does quantifier order matter?

The formulas $\forall x\,\exists y\,R(x,y)$ and $\exists y\,\forall x\,R(x,y)$ generally differ because the first allows y to depend on x, while the second requires one y for all x.