Propositional Variables/Formulas

Question 1

What are the symbols of propositional logic?

Answer 1

Propositional variables
Connectives
Brackets

Question 2

What are the 6 propositional formulas?

Answer 2

1. All propositional variables are formulas.
2. ¬φ where φ is a formula
3. (φ → ψ) where φ and ψ are formulas
4. (φ∧ψ) where φ and ψ are formulas
5. (φ∨ψ) where φ and ψ are formulas
6. (φ↔ψ) where φ and ψ are formulas

Question 3

How do you show a formula is made up of propositional variables?

Answer 3

Breaking the formula down using propositional formulas

Question 4

How do you determine the number of different truth assignments for a formula?

Answer 4

2^(number of propositional variables)

Question 5

What are the following formulas equivalent to?
(φ∧ψ)
(φ∨ψ)
(φ↔ψ)

Answer 5

(φ∧ψ) ≡ ¬(φ→¬ψ)
(φ∨ψ) ≡ (¬φ→ψ)
(φ↔ψ) ≡ ¬((φ→ψ)→¬(ψ→φ))

Question 6

What does it mean for φ to be valid and what is the notation?

Answer 6

For finitely many formulas, for every truth assignment such that e(φ_1),…,e(φ_n) = T we also have e(φ) = T

{φ_1 ,…, φ_n} ⊨ φ

Question 7

What does it mean for two formulas to be logically (truth) equivalent and what is the notation?

Answer 7

e(φ) = e(ψ) for all truth assignments

φ ⊨ =|ψ

Question 8

Let ψ be a sub formula of φ. Suppose ψ ̂ is a formula such that ψ ̂ ⊨ =| ψ, and let φ ̂ be the formula obtained by replacing an occurrence of ψ in φ by ψ ̂. Then?

Answer 8

φ ̂ ⊨ =| φ

Question 9

What formulas are the connectives built upon?

Answer 9

¬,→

Question 10

When makes a set of connectives C adequate?

Answer 10

If every formula is logically equivalent to a formula using only connectives from C.

Question 11

What set is adequate by definition?

Answer 11

{¬,→}

Question 12

How would you show that {¬,*} is adequate?

Answer 12

Show that → can be expressed by {¬,*} since {¬,→} is adequate by definition.

Question 13

What is a logical consequence and what is the notation?

Answer 13

if e(γ) = T for all γ∈Γ, then e(φ)= T where Γ is a possibly empty, possibly infinite, possibly finite set of propositional formulas.

Γ⊨ φ

Question 14

What is the difference between logical consequence and valid?

Answer 14

valid – finitely many formulas,
logical consequence – possibly empty, finite, or infinite

Question 15

Define tautology and give the notation

Answer 15

e(φ) = T for all truth assignments e

⊨ φ

Question 16

tWhat is the relationship between tautologies and truth equivalences?

Answer 16

φ ⊨ =| ψ if and only if ⊨ (φ ↔ ψ).

Question 17

What is a conjunct?

Answer 17

A and B

Question 18

What is a disjunct?

Answer 18

A or B

Question 19

What is a literal?

Answer 19

Either a propositional variable or the negation of a propositional variable.

Question 20

What is DNF?

Answer 20

sets of “ands” grouped together by “ors”
((P_1 ∧P_2 ∧¬P_3)∨(P_1 ∧〖¬P〗_2 ∧P_3)∨(¬P_1 ∧P_2 ∧P_3))

Question 21

What are two rules for DNF constituents in DNF?

Answer 21

All variables must appear in each DNF constituent.

No DNF constituent can be repeated.

Question 22

What are DNF constituents?

Answer 22

the “and” parts of the set

Question 23

Is (P_1∧¬P_1) in DNF?

Answer 23

yes

Question 24

Describe two ways to find the DNF of a formula

Answer 24

Finding DNFs:
1. Truth tables, locate which combinations of variables result in the formula being true.
2. Truth equivalences

Question 25

What is constructive normal form (CNF)?

Answer 25

A set of ors grouped together by ands

Question 26

How do you find CNF using a truth table?

Answer 26

Locate which ones are false, if e(P)=T, then ¬P in the CNF.

Question 27

Define satisfiability

Answer 27

There exists a truth assignment where are the formulas in the set are true

Question 28

Is the empty set satisfiable?

Answer 28

Yes

Question 29

What is the relationship between satisfiability and logical consequences?

Answer 29

1. If Γ is satisfiable and Γ⊨φ, then Γ∪{φ} is satisfiable. 2. Γ ⊭ φ if and only if Γ∪{¬φ} is satisfiable.

Question 30

What is a clause?

Answer 30

a finite (possibly empty) set of literals

Question 31

Define satisfiability for clauses.

Answer 31

For any truth assignment e, a clause is satisfiable if and only if there is some L_i∈{L_1,...,L_n} with e(L_i) = T.

Question 32

What is the clause associated with φ?

Answer 32

If φ = (L_1 ∨ ...∨ L_n) where L_1,...,L_n are literals, then {L_1,...,L_n} is the clause associated to φ.

Question 33

What are two ways you can see if a set is satisfiable?

Answer 33

1. Truth table 2. Davis-Putnam Procedure

Question 34

Define the Davis-Putnam Procedure

Answer 34

1. Remove all clauses including X and ¬X 2. If X does not appear in any clauses, remove all clauses including ¬X. 3. If ¬X does not appear in any clauses, remove all clauses including X. 4. Preform resolution on any variable. End of procedure: 1. ∅ (the empty set of clauses): the original set of clauses was satisfiable {{X}} or {{¬X}} or {{X,¬X}} 2. {∅} (the empty clause): the original set of clauses was unsatisfiable {{¬X},{X}}

Question 35

What is a horn clause?

Answer 35

A clause where at most one of the literals is not negated.

Question 36

What is a horn formula?

Answer 36

A formula of the form ¬(P_1 ∧ ...∧P_n) or ((P_1 ∧ ...∧P_m) → Q)

Question 37

What are the three horn clause/formula associations?

Answer 37

Horn clause: {P} Horn formula: P Horn clause: {¬P_1,...,¬P_n} Horn formula: ¬(P_1∧...∧P_n) Horn clause: {¬P_1,...,¬P_m,Q} Horn formula: ((P_1∧...∧P_m)→Q).

Question 38

What is the procedure to determine if a set of horn formulas is satisfiable?

Answer 38

1. For all variables, set e(P)=T 2. If there are any formulas of the form ¬(P_1∧...∧P_m) with all e(P_i) = T, then unsatisfiable 3. If there are no formulas of the form ((P_1∧...∧P_m)→Q) with all e(P_i) = T but Q undefined, then satisfiable 4. Set all e(Q) = T

Question 39

What is 3-SAT?

Answer 39

Determining if a set where each clause has exactly 3 literals is satisfiable, convert to 3-SAT, then use Davis-Putnam procedure

Question 40

What are the 3-SAT satisfiability equivalences?

Answer 40

3-SAT satisfiability equivalent: If n = 1, let D_l = {{L_1, X_1, X_2}, {L_1, ¬X_1, X_2}, {L_1, X_1, ¬X_2}, {L_1, ¬X_1, ¬X_2} If n = 2, let D_l = {{L_1, L_2, X_1}, {L_1, L_2, ¬X_1}} If n = 3, let D_l = {{L_1^l, L_2^l, L_3^l}}. If n > 3, let D_l = {{L_1, L_2, X_1}, {¬X_1, L_3, X_2},{¬X_2, L_4, X_3} ,..., {¬X_(n_l-3), L_(n_l-1), L_(n_l)}}.

Question 41

What is Tseitin's algorithm used for?

Answer 41

To find a satisfiably equivalent set of clauses

Question 42

Describe Tseitin's algorithm

Answer 42

1. Use truth equivalences to find a formula φ ̃⊨ =| φ so ¬ only appears as part of a literal 2. Find all non-literal sub formulas of φ ̃ 3. For non-literal sub formulas: let φ_i = sub formula i 4. For each non-literal sub formula, let L_(φ_i) = X_i 5. For each φ_i If ψ=(ψ_1∨ψ_2), C_(φ_i ) ={{¬X_i,ψ_1,ψ_2}, {¬ψ_1,X_i},{¬ψ_2,X_i}} If ψ=(ψ_1∧ψ_2), C_(φ_i ) ={{¬X_i,ψ_1},{¬X_i,ψ_2},{¬ψ_1,¬ψ_2,X_i}} 6. Let Γ={{X_n}}∪ C_ψ.

Question 43

What is the relationship between validity and satisfiability for x, y, z therefore w statements?

Answer 43

If a set where ¬w is satisfiable, it is not valid. If a set where ¬w is unsatisfiable, it is valid.

Question 44

What is Modus Ponens (MP)?

Answer 44

For φ and ψ, from φ and (φ → ψ), we conclude ψ.

Question 45

What are the 3 sources for derivation?

Answer 45

Premiss: φ_i∈Γ Axiom MP (Rules)

Question 46

What is soundness?

Answer 46

if Γ ⊢ φ, then Γ ⊨ φ. if φ is derivable from Γ, then φ is a logical consequence of Γ.

Question 47

How do you prove soundness?

Answer 47

o Show that all axioms are tautologies o Show that all rules preserve truth

Question 48

What is the notation for derivation?

Answer 48

Γ ⊢ φ

Question 49

What is completeness?

Answer 49

if Γ ⊨ φ, then Γ ⊢ φ. if φ is a logical consequence of Γ, then φ is derivable from Γ.

Question 50

How can you prove completeness?

Answer 50

Show that for any formula, if Γ⊨ φ, then φ is derivable from the system

Question 51

How can you disprove completeness?

Answer 51

Give a set of formulas and a formula that is a logical consequence (Γ⊨ φ ) but is not derivable from the system

Question 52

What is deduction theorem?

Answer 52

If Γ ∪ {φ} ⊢ ψ, then Γ ⊢ (φ → ψ).

Question 53

Does the converse of Deduction theorem hold?

Answer 53

Yes, if Γ⊢(φ→ψ), then Γ∪{φ}⊢ψ.

Question 54

What is Hypothetical syllogism (HS)?

Answer 54

{(φ → ψ),(ψ → χ)} ⊢ (φ → χ)

Question 55

Define consistent.

Answer 55

There is no formula φ such that both Γ ⊢ φ and Γ ⊢ ¬φ.

Question 56

How can you show a set is inconsistent?

Answer 56

Show that both φ and ¬φ are derivable from Γ.

Question 57

What theorem should you use to show a set is consistent?

Answer 57

If Γ is a satisfiable set of propositional formulas, then Γ is consistent

Question 58

What is the maximal consistent set of formulas?

Answer 58

if Γ is consistent and if for every formula φ, either φ∈Γ or ¬φ∈Γ

Question 59

What is compactness?

Answer 59

Γ is satisfiable if and only if every finite subset of Γ is satisfiable.