Logic Lecture 1 Flashcards
What is a declarative sentence?
A declarative sentence (or proposition) is a statement that is either true or false.
What are some examples of declarative sentences?
Examples include ‘5 > 3’, ‘grass is green’, and ‘if x > 1, then x^2 ≠ x’.
What is an example of an argument abstraction?
If p and not q, then r. Not r. p. Therefore, q.
What does the symbol ∧ represent in propositional logic?
It represents conjunction, meaning ‘and’.
What does the symbol ∨ represent in propositional logic?
It represents disjunction, meaning ‘or’.
What does the symbol ⊕ represent in propositional logic?
It represents exclusive or (XOR), meaning ‘either…or’.
What does the symbol ¬ represent in propositional logic?
It represents negation, meaning ‘not’.
What does the symbol → represent in propositional logic?
It represents implication, meaning ‘if…then’.
What does the symbol ↔ represent in propositional logic?
It represents bi-implication, meaning ‘if and only if’.
What are the base elements of a propositional formula?
Propositional variables (p, q, r, …), negation (¬), and binary connectives (∧, ∨, ⊕, →, ↔).
What are the rules for constructing a propositional formula?
- Every propositional variable is a formula. 2. If φ is a formula, then ¬φ is a formula. 3. If φ and ψ are formulas, then (φ ∧ ψ), (φ ∨ ψ), (φ ⊕ ψ), (φ → ψ), and (φ ↔ ψ) are also formulas.
What is syntax in logic?
Syntax refers to how a word (or formula) is written.
What is semantics in logic?
Semantics refers to the meaning of a word (or formula).
What is a valuation in propositional logic?
A valuation is an assignment of truth values to propositional variables.
What is a truth table?
A table that shows the truth values of a formula for all possible truth values of its components.
What are the truth values of a negation ¬φ?
If φ is true, ¬φ is false; if φ is false, ¬φ is true.
What are the truth values of a conjunction φ ∧ ψ?
True only if both φ and ψ are true; false otherwise.
What are the truth values of a disjunction φ ∨ ψ?
True if at least one of φ or ψ is true; false otherwise.
What are the truth values of an implication φ → ψ?
False only when φ is true and ψ is false; true otherwise.
What are the truth values of a bi-implication φ ↔ ψ?
True if φ and ψ have the same truth value; false otherwise.
What is a tautology?
A formula that is always true regardless of truth values.
What is a contradiction?
A formula that is always false regardless of truth values.
What is a contingent formula?
A formula that is neither always true nor always false.
What are some important semantic equivalences?
Examples: ¬¬φ ≡ φ, φ ∧ ψ ≡ ψ ∧ φ, φ ∨ ψ ≡ ψ ∨ φ, ¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ (De Morgan’s Law).
What does the principle of explosion state?
From a contradiction, anything follows.
What is the meaning of p → q in terms of disjunction?
p → q is equivalent to ¬p ∨ q.
What is an example of a tautology?
p ∨ ¬p (law of excluded middle).
What is an example of a contradiction?
p ∧ ¬p.
What is an associative property in logic?
(φ ∧ ψ) ∧ χ ≡ φ ∧ (ψ ∧ χ) and (φ ∨ ψ) ∨ χ ≡ φ ∨ (ψ ∨ χ).
Is implication associative?
No, (φ → ψ) → χ ≠ φ → (ψ → χ).
