Propositional Logic Flashcards
1
Q
[[P]]
A
Semantics of P, given by assignment
2
Q
Valid/Tautology
A
A proposition 𝑃 such that all assignments make [[𝑃]] T
3
Q
Unsatisfiable/Contradiction
A
A proposition 𝑃 such that all assignments make [[𝑃]] F
4
Q
Satisfiable
A
A proposition 𝑃 such that at least one assignment makes [[𝑃]] T
5
Q
Invalid
A
A proposition 𝑃 such that at least one assignment makes [[𝑃]] F
6
Q
Complete Set of Operators
A
Operators in terms of which we can define everything else (construct any truth table)
7
Q
𝑃 ⇔ 𝑄
A
(𝑃 ∧ 𝑄) ∨ (¬𝑃 ∧ ¬𝑄)
8
Q
𝑃 → 𝑄
A
¬𝑃 ∨ 𝑄
9
Q
𝑃 ∨ (𝑄 ∧ 𝑅)
A
(𝑃 ∨ 𝑄) ∧ (𝑃 ∨ 𝑅)
10
Q
𝑃 ∨ (𝑃 ∧ 𝑄)
A
P
11
Q
𝑃 ∧ (𝑃 ∨ 𝑄)
A
P
12
Q
Assumption Rule
A
Γ ⊢ 𝑃
13
Q
Modus Ponens
A
If we can prove 𝑃 → 𝑄 and 𝑃, then we can use that to
prove 𝑄
