Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

PMATH 330 > Propositional Variables/Formulas > Flashcards

Propositional Variables/Formulas Flashcards

1
Q

What are the symbols of propositional logic?

A

Propositional variables
Connectives
Brackets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 6 propositional formulas?

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

Breaking the formula down using propositional formulas

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

2^(number of propositional variables)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

{φ_1 ,…, φ_n} ⊨ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

φ ⊨ =|ψ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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?

A

φ ̂ ⊨ =| φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What formulas are the connectives built upon?

A

¬,→

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

When makes a set of connectives C adequate?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What set is adequate by definition?

A

{¬,→}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a logical consequence and what is the notation?

A

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

Γ⊨ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the difference between logical consequence and valid?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define tautology and give the notation

A

e(φ) = T for all truth assignments e

⊨ φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

tWhat is the relationship between tautologies and truth equivalences?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a conjunct?

A

A and B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a disjunct?

A

A or B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a literal?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is DNF?

A

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))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are two rules for DNF constituents in DNF?

A

All variables must appear in each DNF constituent.

No DNF constituent can be repeated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are DNF constituents?

A

the “and” parts of the set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Is (P_1∧¬P_1) in DNF?

A

yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Describe two ways to find the DNF of a formula

A

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

25
Q

What is constructive normal form (CNF)?

A

A set of ors grouped together by ands

26
Q

How do you find CNF using a truth table?

A

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

27
Q

Define satisfiability

A

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

28
Q

Is the empty set satisfiable?

A

Yes

29
Q

What is the relationship between satisfiability and logical consequences?

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

What is a clause?

A

a finite (possibly empty) set of literals

31
Q

Define satisfiability for clauses.

A

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.

32
Q

What is the clause associated with φ?

A

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

33
Q

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

A
  1. Truth table
  2. Davis-Putnam Procedure
34
Q

Define the Davis-Putnam Procedure

A
  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}}

35
Q

What is a horn clause?

A

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

36
Q

What is a horn formula?

A

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

37
Q

What are the three horn clause/formula associations?

A

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).

38
Q

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

A
  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
39
Q

What is 3-SAT?

A

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

40
Q

What are the 3-SAT satisfiability equivalences?

A

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)}}.

41
Q

What is Tseitin’s algorithm used for?

A

To find a satisfiably equivalent set of clauses

42
Q

Describe Tseitin’s algorithm

A
  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_ψ.
43
Q

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

A

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

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

44
Q

What is Modus Ponens (MP)?

A

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

45
Q

What are the 3 sources for derivation?

A

Premiss: φ_i∈Γ
Axiom
MP (Rules)

46
Q

What is soundness?

A

if Γ ⊢ φ, then Γ ⊨ φ.

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

47
Q

How do you prove soundness?

A

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

48
Q

What is the notation for derivation?

A

Γ ⊢ φ

49
Q

What is completeness?

A

if Γ ⊨ φ, then Γ ⊢ φ.

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

50
Q

How can you prove completeness?

A

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

51
Q

How can you disprove completeness?

A

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

52
Q

What is deduction theorem?

A

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

53
Q

Does the converse of Deduction theorem hold?

A

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

54
Q

What is Hypothetical syllogism (HS)?

A

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

55
Q

Define consistent.

A

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

56
Q

How can you show a set is inconsistent?

A

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

57
Q

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

A

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

58
Q

What is the maximal consistent set of formulas?

A

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

59
Q

What is compactness?

A

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

PMATH 330 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions