Logic for programing FOL

Proposition

A declarative sentence that is either true or false.

Contingency

A statement that is sometimes true and sometimes false depending on the truth assignment.

Logical Equivalence

Two statements that always have the same truth value under every truth assignment.

Entailment (⊨)

A semantic relationship where if the premises are true, the conclusion must be true in all interpretations.

Provability (⊢)

A syntactic relationship where the conclusion can be derived from premises using rules of inference.

Term: ⊥

Contradiction / falsehood.

Term: ⊤

Always true.

Predicate

A property or relation that returns true or false when given an object or objects.

Function Symbol

A symbol that maps objects to other objects.

Constant Symbol

A symbol that refers to a specific object in the domain.

Domain

The set of objects an interpretation ranges over.

Interpretation

A domain plus a meaning for every predicate, function, and constant.

Model

An interpretation that makes a formula true.

∀

Universal quantifier (“for all”).

∃

Existential quantifier (“there exists”).

Scope of a Quantifier

The part of the formula the quantifier applies to

Predicate Symbol

A symbol that expresses a property or relation; its arity tells how many arguments it takes (e.g., unary P(x), binary R(x,y)).

Function Symbol

A symbol that maps objects in the domain to another object (e.g., f(x), f(x,y)); arity indicates how many inputs it takes.

Constant Symbol

A symbol that refers to one specific object in the domain (e.g., a, b, c).

Arity

The number of arguments a predicate or function takes.

Well-Formed Formula (WFF)

A syntactically correct logical expression built using predicates applied to terms, connectives, and quantifiers.

Domain (D)

The set of all objects over which variables range in an interpretation.

Interpretation (I = (D, Φ))

A structure consisting of a domain D and an assignment Φ that gives meaning to all constants, predicates, and functions in the language.

Meaning Function Φ

The part of the interpretation that maps:

constants → elements of the domain
• predicates → sets of tuples
• functions → mappings from domain tuples to domain

Satisfies

An interpretation satisfies a formula if the formula evaluates to true in that interpretation.

Satisfiable

A formula that is true in at least one interpretation.

Unsatisfiable

A formula that is false in every interpretation (no model exists)

Universal Quantifier (∀x)

“For all x”; the statement must hold for every element in the domain.

Existential Quantifier (∃x)

“There exists an x”; the statement holds for at least one element in the domain.

Main Connective

The outermost logical operator of a formula, which determines its overall structure.

Assigning Predicate Meaning

Choosing which domain elements make the predicate true (e.g., Φ(P) = {a, c}).

Assigning Function Meaning

Defining how the function symbol maps domain elements (e.g., f(a)=b).

Making a Formula True

Choosing a domain and meaning so that the formula evaluates to true

You will use the same first-order language for the whole card. Which of these is the best choice for a predicate that means “x is a saucepan”?

A. Sau(x) — unary predicate

Which predicate signature best matches “x gives y to z”?

 Give(x,y,z) — ternary

Which predicate fits “x is made of tin”?

MadeOf(x,y) — binary where y is a material

Which constant would best represent “my saucepan” (a specific saucepan)?

S — a constant symbol

English: “All of my saucepans are made of tin.”
Language: unary predicate Sau(x) = “x is one of my saucepans”; binary MadeOf(x,y) where material Tin is a constant.

∀x (Sau(x) → MadeOf(x, Tin))

“There exists a present that you gave me.”
Predicates: Give(x,y) = “x gave y to me” where you is constant u and me is constant m. Which is correct?

∃y Give(u,y,m)

English: “No saucepan of mine is useful.” Predicates: Sau(x) = my saucepan, Useful(x). Correct translation?

D. Both A and C

English: “You have never given me anything made of tin.” Using Give(giver,item,receiver) with constants u for you and m for me and MadeOf(item, Tin). Which matches?

D. Both A and C

Premises: (1) All Buffalo are reptiles. (2) No Buffalo are reptiles. Conclusion: There are no Buffalo. Which entailment matches this argument? Use Buff(x) and Reptile(x).

A. {∀x (Buff(x) → Reptile(x)), ∀x (Buff(x) → ¬Reptile(x))} ⊨ ∀x ¬Buff(x)

Formula: ∀x (Student(x) → ∃y Teaches(y,x))

Every student is taught by someone.

¬∃x (Cat(x) ∧ Friendly(x))

No cat is friendly.

∃x ∀y Loves(x,y)

There is someone who loves everyone.