Discover published sets by community

Explore tens of thousands of sets crafted by our community.

Fundamentals of First-Order Logic

Flashcards

0/10

Still learning

Universal Quantification

Universal quantification is denoted by

\forall

and asserts that a predicate holds for all individuals in a domain. For example,

\forall x P(x)

means 'For all x, P(x) is true'.

Predicate

A predicate is a function that returns a truth value. For example, the predicate P(x) might represent 'x is a prime number'.

Logical Conjunction

Logical conjunction is denoted by

\land

and corresponds to the logical 'and'. For example, if P(x) and Q(x) are predicates, then

P(x) \land Q(x)

means 'P(x) and Q(x) are both true'.

Existential Quantification

Existential quantification is denoted by

\exists

and asserts that there exists at least one individual in the domain for which the predicate holds. For example,

\exists x P(x)

means 'There exists an x such that P(x) is true'.

Logical Disjunction

Logical disjunction is denoted by

\lor

and corresponds to the logical 'or'. For instance,

P(x) \lor Q(x)

means 'Either P(x) or Q(x) (or both) is true'.

Logical Implication

Logical implication is denoted by

\rightarrow

and represents 'if...then...'. For example,

P(x) \rightarrow Q(x)

means 'If P(x) is true, then Q(x) is also true'.

Logical Negation

Logical negation is represented by

\neg

and inverts the truth value of a statement. For a predicate P(x),

\neg P(x)

means 'It is not the case that P(x) is true'.

Bound and Free Variables

A bound variable is quantified by a logical quantifier, while a free variable is not. In

\forall x P(x)

, x is bound, but in P(x) without quantification, x is free.

Domain of Discourse

The domain of discourse is the set of all objects under consideration for the logical predicates. For example, if the domain is all humans,

\forall x P(x)

considers every human for property P.

Logical Equivalence

Logical equivalence is denoted by

\leftrightarrow

and indicates that two statements are logically equivalent. The statement

P(x) \leftrightarrow Q(x)

means 'P(x) is true if and only if Q(x) is true'.

Know

Still learning

Click to flip

Know