1. Propositional Logic and Natural Deduction

Question 1

What are the 5 propositional connectives?

Answer 1

not (¬), and (∧), or (∨), implies (→), if and only if (↔)

Question 2

What is the precedence of propositional connectives? (high to low)

Answer 2

¬,∧,∨,→,↔

Question 3

Define interpretation (propositional logic)

Answer 3

A truth assignment to symbols in the alphabet

Question 4

Define valuation (propositional logic)

Answer 4

A truth assignment to symbols in the alphabet

Question 5

Define satisfaction (propositional logic)

Answer 5

An interpretation satisfies a wff if the wff is true under the interpretation

Question 6

Define satisfiable (propositional logic)

Answer 6

A wff is satisfiable if there exists and interpretation that satisfies it

Question 7

Define unsatisfiable (propositional logic)

Answer 7

A wff is unsatisfiable if there does not exist an interpretation that satisfies it

Question 8

Define valid (propositional logic)

Answer 8

A wff is valid if every interpretation satisfies it

Question 9

Define tautology (propositional logic)

Answer 9

A wff is a tautology if every interpretation satisfies it

Question 10

What does wff stand for?

Answer 10

Well formed formula

Question 11

What is a wff in propostional logic?

Answer 11

Given a (possibly infinite) alphabet of propositional symbols L

• Any symbol in A ∈ L
• If P, Q are wff so are ¬P, P∧Q, P∨Q, P→Q, P↔Q

Question 12

Define entailment

Answer 12

wff p1, p2, …, pn ⊨ Q if for an interpretation which satisfies all of p1, p2, …, pn also satisfies Q

Question 13

Is satisfiability of propositional logic decidable?

Answer 13

Yes

Question 14

Is validity of propositional logic decidable?

Answer 14

Yes

Question 15

Is entailment of propositional logic decidable?

Answer 15

Yes

Question 16

What is a formal deductive system?

Answer 16

A set of valid inference rules that tells us what conclusions we can draw from some premises.