Logic Lecture 6 Flashcards
What is predicate logic?
An extension of propositional logic that includes quantifiers and variables to express properties and relations.
What are predicate symbols?
Symbols that represent properties or relations, such as Person() or Soulmate(, _).
What are constants in predicate logic?
Symbols representing specific objects, such as ‘s’ for Socrates.
What are variables in predicate logic?
Symbols that can take on different values from a domain, like x and y.
What are the logical connectives used in predicate logic?
¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (if and only if).
What are the two main quantifiers in predicate logic?
Universal quantifier (∀) and existential quantifier (∃).
What does the universal quantifier (∀) mean?
It states that a property applies to all elements in a domain.
What does the existential quantifier (∃) mean?
It states that at least one element in the domain satisfies a property.
What is an example of an argument in predicate logic?
‘All humans are mortal. Socrates is a human. Therefore, Socrates is mortal.’
What is the formalization of ‘All humans are mortal’ in predicate logic?
∀x (H(x) → M(x)), where H(x) means ‘x is a human’ and M(x) means ‘x is mortal.’
What is an atomic formula in predicate logic?
A formula that consists of a predicate with constants or variables as arguments.
What is an example of an atomic formula?
C(j), meaning ‘Jane is clever.’
What is a binary predicate?
A predicate with two arguments, such as K(a, b) meaning ‘Anton knows Betty.’
What is the priority of quantifiers in logical expressions?
Quantifiers have the same priority as negation (¬) and bind tighter than conjunctions and disjunctions.
What is a bound variable in predicate logic?
A variable that falls within the scope of a quantifier.
What is a free variable in predicate logic?
A variable that is not within the scope of any quantifier.
What does it mean for a formula to be closed?
A formula with no free variables.
What is a model in predicate logic?
A structure that assigns meaning to constants, variables, and predicate symbols.
What does it mean for a model to satisfy a formula?
A model satisfies a formula if the formula is true under the model’s interpretation.
What is an example of a model in predicate logic?
A model where the domain consists of people, and ‘C(x)’ means ‘x is clever.’
What is semantic entailment?
A set of formulas semantically entails another formula if the latter is true in all models where the first set is true.
What is a tautology in predicate logic?
A formula that is true in all possible models.
What is a contradiction in predicate logic?
A formula that is false in all possible models.
What is a contingent formula?
A formula that is true in some models and false in others.
What is an example of a semantic equivalence in predicate logic?
¬∃x P(x) ≡ ∀x ¬P(x), meaning ‘Nobody is perfect’ is the same as ‘Everybody is imperfect.’
What is α-conversion in predicate logic?
The process of renaming bound variables, such as ∃x C(x) ≡ ∃y C(y).
What is the difference between ∃x (φ ∨ ψ) and ∃x φ ∨ ∃x ψ?
They are semantically equivalent, meaning that one of the elements satisfying φ or ψ implies that there exists an element satisfying φ or ψ.
Is ∃x (φ ∧ ψ) ≡ ∃x φ ∧ ∃x ψ a valid equivalence?
No, because the left side requires a single element to satisfy both φ and ψ, whereas the right side allows different elements to satisfy them separately.
What is the difference between ∀x ∃y K(x, y) and ∃y ∀x K(x, y)?
∀x ∃y K(x, y) means ‘everyone knows someone,’ while ∃y ∀x K(x, y) means ‘there is one person whom everyone knows.’
What are some important semantic equivalences in predicate logic?
¬∃x φ ≡ ∀x ¬φ, ¬∀x φ ≡ ∃x ¬φ, ∃x (φ ∨ ψ) ≡ ∃x φ ∨ ∃x ψ, ∀x (φ ∧ ψ) ≡ ∀x φ ∧ ∀x ψ.
