Propositional Variables/Formulas Flashcards
What are the symbols of propositional logic?
Propositional variables
Connectives
Brackets
What are the 6 propositional formulas?
- All propositional variables are formulas.
- ¬φ where φ is a formula
- (φ → ψ) where φ and ψ are formulas
- (φ∧ψ) where φ and ψ are formulas
- (φ∨ψ) where φ and ψ are formulas
- (φ↔ψ) where φ and ψ are formulas
How do you show a formula is made up of propositional variables?
Breaking the formula down using propositional formulas
How do you determine the number of different truth assignments for a formula?
2^(number of propositional variables)
What are the following formulas equivalent to?
(φ∧ψ)
(φ∨ψ)
(φ↔ψ)
(φ∧ψ) ≡ ¬(φ→¬ψ)
(φ∨ψ) ≡ (¬φ→ψ)
(φ↔ψ) ≡ ¬((φ→ψ)→¬(ψ→φ))
What does it mean for φ to be valid and what is the notation?
For finitely many formulas, for every truth assignment such that e(φ_1),…,e(φ_n) = T we also have e(φ) = T
{φ_1 ,…, φ_n} ⊨ φ
What does it mean for two formulas to be logically (truth) equivalent and what is the notation?
e(φ) = e(ψ) for all truth assignments
φ ⊨ =|ψ
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?
φ ̂ ⊨ =| φ
What formulas are the connectives built upon?
¬,→
When makes a set of connectives C adequate?
If every formula is logically equivalent to a formula using only connectives from C.
What set is adequate by definition?
{¬,→}
How would you show that {¬,*} is adequate?
Show that → can be expressed by {¬,*} since {¬,→} is adequate by definition.
What is a logical consequence and what is the notation?
if e(γ) = T for all γ∈Γ, then e(φ)= T where Γ is a possibly empty, possibly infinite, possibly finite set of propositional formulas.
Γ⊨ φ
What is the difference between logical consequence and valid?
valid – finitely many formulas,
logical consequence – possibly empty, finite, or infinite
Define tautology and give the notation
e(φ) = T for all truth assignments e
⊨ φ
tWhat is the relationship between tautologies and truth equivalences?
φ ⊨ =| ψ if and only if ⊨ (φ ↔ ψ).
What is a conjunct?
A and B
What is a disjunct?
A or B
What is a literal?
Either a propositional variable or the negation of a propositional variable.
What is DNF?
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))
What are two rules for DNF constituents in DNF?
All variables must appear in each DNF constituent.
No DNF constituent can be repeated.
What are DNF constituents?
the “and” parts of the set
Is (P_1∧¬P_1) in DNF?
yes
Describe two ways to find the DNF of a formula
Finding DNFs:
1. Truth tables, locate which combinations of variables result in the formula being true.
2. Truth equivalences
What is constructive normal form (CNF)?
A set of ors grouped together by ands
How do you find CNF using a truth table?
Locate which ones are false, if e(P)=T, then ¬P in the CNF.
Define satisfiability
There exists a truth assignment where are the formulas in the set are true
Is the empty set satisfiable?
Yes
What is the relationship between satisfiability and logical consequences?
- If Γ is satisfiable and Γ⊨φ, then Γ∪{φ} is satisfiable.
- Γ ⊭ φ if and only if Γ∪{¬φ} is satisfiable.
What is a clause?
a finite (possibly empty) set of literals
Define satisfiability for clauses.
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.
What is the clause associated with φ?
If φ = (L_1 ∨ …∨ L_n) where L_1,…,L_n are literals, then {L_1,…,L_n} is the clause associated to φ.
What are two ways you can see if a set is satisfiable?
- Truth table
- Davis-Putnam Procedure
Define the Davis-Putnam Procedure
- Remove all clauses including X and ¬X
- If X does not appear in any clauses, remove all clauses including ¬X.
- If ¬X does not appear in any clauses, remove all clauses including X.
- 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}}
What is a horn clause?
A clause where at most one of the literals is not negated.
What is a horn formula?
A formula of the form
¬(P_1 ∧ …∧P_n) or ((P_1 ∧ …∧P_m) → Q)
What are the three horn clause/formula associations?
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).
What is the procedure to determine if a set of horn formulas is satisfiable?
- For all variables, set e(P)=T
- If there are any formulas of the form ¬(P_1∧…∧P_m) with all e(P_i) = T, then unsatisfiable
- If there are no formulas of the form ((P_1∧…∧P_m)→Q) with all e(P_i) = T but Q undefined, then satisfiable
- Set all e(Q) = T
What is 3-SAT?
Determining if a set where each clause has exactly 3 literals is satisfiable, convert to 3-SAT, then use Davis-Putnam procedure
What are the 3-SAT satisfiability equivalences?
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)}}.
What is Tseitin’s algorithm used for?
To find a satisfiably equivalent set of clauses
Describe Tseitin’s algorithm
- Use truth equivalences to find a formula φ ̃⊨ =| φ so ¬ only appears as part of a literal
- Find all non-literal sub formulas of φ ̃
- For non-literal sub formulas: let φ_i = sub formula i
- For each non-literal sub formula, let L_(φ_i) = X_i
- 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}} - Let Γ={{X_n}}∪ C_ψ.
What is the relationship between validity and satisfiability for x, y, z therefore w statements?
If a set where ¬w is satisfiable, it is not valid.
If a set where ¬w is unsatisfiable, it is valid.
What is Modus Ponens (MP)?
For φ and ψ, from φ and (φ → ψ), we conclude ψ.
What are the 3 sources for derivation?
Premiss: φ_i∈Γ
Axiom
MP (Rules)
What is soundness?
if Γ ⊢ φ, then Γ ⊨ φ.
if φ is derivable from Γ, then φ is a logical consequence of Γ.
How do you prove soundness?
o Show that all axioms are tautologies
o Show that all rules preserve truth
What is the notation for derivation?
Γ ⊢ φ
What is completeness?
if Γ ⊨ φ, then Γ ⊢ φ.
if φ is a logical consequence of Γ, then φ is derivable from Γ.
How can you prove completeness?
Show that for any formula, if Γ⊨ φ, then φ is derivable from the system
How can you disprove completeness?
Give a set of formulas and a formula that is a logical consequence (Γ⊨ φ ) but is not derivable from the system
What is deduction theorem?
If Γ ∪ {φ} ⊢ ψ, then Γ ⊢ (φ → ψ).
Does the converse of Deduction theorem hold?
Yes, if Γ⊢(φ→ψ), then Γ∪{φ}⊢ψ.
What is Hypothetical syllogism (HS)?
{(φ → ψ),(ψ → χ)} ⊢ (φ → χ)
Define consistent.
There is no formula φ such that both Γ ⊢ φ and Γ ⊢ ¬φ.
How can you show a set is inconsistent?
Show that both φ and ¬φ are derivable from Γ.
What theorem should you use to show a set is consistent?
If Γ is a satisfiable set of propositional formulas, then Γ is consistent
What is the maximal consistent set of formulas?
if Γ is consistent and if for every formula φ, either φ∈Γ or ¬φ∈Γ
What is compactness?
Γ is satisfiable if and only if every finite subset of Γ is satisfiable.
