Chapter 3 - The logic of quantified statements

A predicate

A sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable

Other words for predicate

Propositional functions or open sentences.

If P(x) is a predicate and x has domain D, the truth set of P(x) is

The set of all elements of D that make P(x) true when they are substituted for x.

Quantifiers

Words that refer to quantities such as “some” or “all” and tell for how many elements a given predicate is true.

Universal quantifier

“for every”, “for each”, “for any”, “given any”, or “for all”

A universal statement

A statement of the form “∀x ∈ D, Q(x)”.

When is a universal statement true and false?

Iff Q(x) is true for each individual x in D. It's false iff Q(x) is false for at least one x in D.

Counterexample to the universal statement

A value for x for which Q(x) is false.

Method of exhaustion

Showing the truth of the predicate separately for each individual element of the domain.

Existential quantifier

"there exists", "there is a", "we can find a", "there is at least one", "for some", and "for at least one".

An existential statement

A statement of the form “∃x ∈ D such that Q(x).”

When is an existential statement true and false?

It's defined to be true iff Q(x) is true for at least one x in D. It's false iff Q(x) is false for all x in D.

A prime number

An integer greater than 1 whose only positive integer factors are itself and 1.

We say that the variable x is bound by the quantifier that controls it and that its scope begins when the quantifier introduces it and ends at the end of the quantified statement.

A bound variable

A variable that is associated with a quantifier. The variable’s meaning is controlled by the quantifier, so it does not refer to anything outside the statement.

The scope of a quantifier

The part of the statement where the quantifier controls its variable.

The notation P(x)

> Q(x) means?

The notation P(x) <

> Q(x) means?

~(∀x ∈ D, Q(x))

∃x ∈ D such that ~Q(x)

~(∃x ∈ D, Q(x))

∀x ∈ D such that ~Q(x)

Universal Conditional Statement

∀x, if P(x) then Q(x)

~(∀x, if P(x) then Q(x))

∃x such that P(x) and ~Q(x)

Contrapositive universal conditional statement

∀x ∈ D, if ~Q(x) then ~P(x)

Converse universal conditional statement

∀x ∈ D, if Q(x) then P(x)

Inverse universal conditional statement

∀x ∈ D, if ~P(x) then ~Q(x)

A universal conditional statement is logically equivalent to?

Its contrapositive

"∀x, r(x) is a sufficient condition for s(x)" means?

"∀x, if r(x) then s(x)"

"∀x, r(x) is a necessary condition for s(x)" means?

"∀x, if ~r(x) then ~s(x)" or "∀x, if s(x) then r(x)"

“∀x, r(x) only if s(x)” means?

“∀x, if s(x) then r(x)” or “∀x, if r(x) then s(x)”

The reciprocal of a number

The reciprocal of a real number a is a real number b such that ab

~(∀x in D, ∃y in E such that P(x, y))

∃x in D, such that ∀y in E, ~P(x, y)

~(∃x in D, ∀y in E such that E(x, y))

∀x in D, such that ∃y in E, ~P(x, y)

Prolog

Programming in logic