Logic Lecture 2 Flashcards
What is semantic entailment (⊨)?
A formula ψ is semantically entailed by formulas φ1, …, φn if every valuation that makes φ1, …, φn true also makes ψ true.
What is the symbol used for semantic entailment?
The symbol ⊨ (turnstile) is used.
What is a counterexample in semantic entailment?
A valuation where all premises φ1, …, φn are true, but ψ is false.
What does it mean if φ1, …, φn ⊨ ψ does not hold?
There exists at least one valuation where φ1, …, φn are true but ψ is false.
What does it mean if p → q, ¬q ⊨ ¬p?
It means that whenever p → q and ¬q are true, ¬p must also be true.
What is a key method to determine semantic entailment?
Using truth tables to check if all rows where premises are true also make the conclusion true.
What is the Deduction Theorem?
φ1, …, φn ⊨ ψ is equivalent to φ1, …, φn-1 ⊨ (φn → ψ).
What is the semantic equivalence relation (≡)?
φ ≡ ψ holds if both φ ⊨ ψ and ψ ⊨ φ.
What does the Distributivity Law state?
(φ ∧ ψ) ∨ χ ≡ (φ ∨ χ) ∧ (ψ ∨ χ).
What is reflexivity in semantic entailment?
φ ⊨ φ, meaning every formula semantically entails itself.
What is transitivity in semantic entailment?
If φ ⊨ ψ and ψ ⊨ χ, then φ ⊨ χ.
What does φ ⊨ ψ mean in terms of a truth table?
In all rows where φ is true, ψ must also be true.
How can semantic entailment be expressed as a formula?
As an implication: φ1 ∧ … ∧ φn → ψ.
What is metalogic?
A higher-level reasoning framework analyzing logical structures, rather than specific formulas.
What is an example of a tautology in metalogic?
If φ ∧ ψ is a tautology, then φ and ψ must also be tautologies.
What is an example of a false metalogic statement?
If φ ∨ ψ is a tautology, then φ or ψ must be tautologies (this is false).
What is the significance of the truth table for p → (q → r)?
It shows that p → (q → r), p ⊭ r but p → (q → r), p, q ⊨ r.
What does p ∨ q ⊭ p → q mean?
It means that p ∨ q does not always imply p → q.
What is a key rule in the island of liars and truth speakers?
Each islander either always lies or always tells the truth.
What is the logical formula for ‘islander x is a liar’?
¬tx, where tx means x is a truth speaker.
What is the bi-implication for an islander’s statement?
If an islander x makes an assertion φ, then tx ↔ φ holds.
What happens when an islander says ‘We are both liars’?
It results in a contradiction, meaning one must be a liar and the other a truth speaker.
What is the logical reasoning method for solving liar/truth speaker puzzles?
Assume one possibility, derive consequences, and check for contradictions.
What is a key characteristic of truth tables in logic puzzles?
They are exhaustive but can be laborious and error-prone.
What question helps find the right way at a T-crossing on the liar/truth speaker island?
‘If I asked you whether the right path leads to the harbor, would you say yes?’
What does the liar/truth speaker pointing paradox show?
If two islanders claim the other is lying, they are either both truth speakers or both liars.
What does ‘If I am a truth speaker, then …’ imply?
It does not provide conclusive information since it is a tautology.
What does ta ↔ m and ta ↔ (m → k) ⊨ ta ∧ m ∧ k mean?
It means if a truth speaker says ‘I love Martha’ and ‘If I love Martha, I love Kathy,’ then they love both.
What is the key takeaway from the lecture?
Understanding semantic entailment, metalogic, and logical puzzles helps in logical reasoning and formal proofs.
