2. Propositional logic

Question 1

Technical name of: ¬

Answer 1

Negation

Question 2

Technical name of: ^

Answer 2

Conjunction

Question 3

Technical name of: v

Answer 3

Disjunction

Question 4

Technical name of: ->

Answer 4

Implication

Question 5

Technical name of: <->

Answer 5

Equivalence

Question 6

What does V(p) = 1 mean?

Answer 6

P is true in the situation presented by V

Question 7

What is the equivalence of V(p) = 1?

Answer 7

V |= p

Question 8

Describe valid consequence

Answer 8

ϕ1, . . . , ϕk |= ψ
is valid if each valuation V with V (ϕ1) = . . . = V (ϕk) = 1 also has V (ψ) = 1

Question 9

Describe logical equivalence

Answer 9

If ϕ |= ψ and ψ |= ϕ

Question 10

Describe satisfiability

Answer 10

A set of formulas X (say, ϕ1, . . . , ϕk) is satisfiable if there
is a valuation that makes all formulas in X true

Question 11

Describe consistency

Answer 11

A set of formulas X (say, ϕ1, . . . , ϕk) is satisfiable if the valuations don’t lead to a contradiction.

Question 12

Describe tautology

Answer 12

A formula ψ that gets the value 1 in every valuation is called
a tautology. The notation for tautologies is |= ψ.

Question 12

De Morgan laws

Answer 12

¬(ϕ ∨ ψ) ↔ (¬ϕ ∧ ¬ψ)
¬(ϕ ∧ ψ) ↔ (¬ϕ ∨ ¬ψ)

Question 13

Distribution laws

Answer 13

(ϕ ∧ (ψ ∨ χ)) ↔ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ))
(ϕ ∨ (ψ ∧ χ)) ↔ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ))

Question 14

What are the 3 axioms?

Answer 14

(1) (ϕ → (ψ → ϕ))
(2) ((ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)))
(3) ((¬ϕ → ¬ψ) → (ψ → ϕ))