Propositional Logic Flashcards Preview

CS3050 > Propositional Logic > Flashcards

Flashcards in Propositional Logic Deck (13)
Loading 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 𝑄