Test 2

Question 1

Literal

Answer 1

an atom or the negation of an atom

Question 2

Normal Forms

Answer 2

standardised forms of writing a WFF so that people can read them easily

Question 3

Adequate set of connectives

Answer 3

A set (S) of logical connectives is adequate if every WFF in PL is logically equivalent to a WFF constructed using the logical connectives in S (and the atoms)

Question 4

How to show a set of connectives are adequate

Answer 4

show that you can construct ¬ and ∧ or ¬ and ∨

Question 5

Negation Normal Form

Answer 5

only uses literals and the logical connectives ∧, ∨

Question 6

Disjunctive Normal Form

Answer 6

literals on their own
(∧ literals)
(∧ literals) ∨ (∧ literals) ∨ …

Question 7

Conjunctive Normal Form

Answer 7

(∨ literals) ∧ (∨ literals)

Question 8

Clause

Answer 8

(∧ literals)

∨ literals

Question 9

Horn Formula

Answer 9

called a horn formula if each clause has at most 1 positive literal. Fast algorithm to decide satisfiability. Can be converted into “Implicational form”