Propositional logic
Problem 1
1)Using the truth table method check if “” connective is associative: .
2)Using the truth table method check if “” connective is associative: .
3)Using the truth table method check if “” connective is distributive over “” connective: .
4)Using the truth table method check if “” connective is distributive over “” connective: .
5)Using the truth table method check the properties of absorption: and
.
6)Using the truth table method check the De’Morgan law for :
;
Problem 2.
Using the truth table method decide what kind of formula (consistent, inconsistent, tautology, contingent) is A . If A is consistent, write all the models of A.
1)A=
2)A=
3)A=
4)A=
5)A=
6).
Problem 3. Using the truth table method check if:
1) |=
2) |=
3) |=
4) |=
5) |=
6);
Problem 4.
Using the truth table method prove that the following formulas are tautologies.
1)---semidistributivity of over
2)--- permutation of the premises law.
3)--- reunion of the premises law.
4)--- separation of the premises law.
5)---“cut” law.
6) --- semidistributivity of over
Problem 5. Transform the formula A into its equivalent CNF and DNF. Using one of these forms prove that A is a valid formula in propositional calculus.
1)A=--- permutation of the premises law.
2)A= ---“cut” law.
3)A=--- separation of the premises law.
4)A=--- reunion of the premises law.
5)A=--- axiom A2
6)A=--- semidistributivity of over
Problem 6.
Using the apropriate normal form write all the models of the following formulas:
1)A=.
2)A=
3)A=
4)A=
5)A=
6)A=
Problem 7.
Using the apropriate normal form prove that the following formulas are inconsistent:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
Problem 8
Prove the following properties of the logical equivqlence relation where: R, S FP and
U, V, Z FP.
1.monotonicity: if R |=U and R S then S |=U;
2.cut:if S |=Vi, iI and S{Vi|iI }|= U then S |=U;
3.tranzitivity: if S |=U and {U}|=V then S |=V;
4.conjunction inconclusions (right „and” ):
if S |= U and S |= V then S |= UV;
5.disjunctioninpremises (left „or”):
if S{U} |= Z and S{V} |= Z then S{UV}|=Z;
6.proof by cases:
if S{U} |= V and S{U } |= V then S |= V.
Problem 9.
Using the definition of deduction prove the following:
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. .
Problem 10.
Using the theorem of deduction and its reverse prove that:
1) --- reunion of the premises law.
2) --- separation of the premises law
3)--- permutation of the premises law.
4)--- second axiom of propositional logic
5) --- “cut” law.
6)
Problem 11.
Using the theorem of deduction and its reverse prove that:
1)
2)
3)
4)
5)
6).
Problem 12
Using the theorem of deduction and its reverse prove that:
1)
2)
3)
4)
5)
6);
Problem 13. Using the semantic tableaux method decide what kind of formula is A. If A is consistent, write all its models.
1. A=.
2. A=
3. A=
4. A=.
5. A=
6. .
Problem 14. Prove that the formula A is valid using the semantic tableaux method.
1.A= permutation of the premises
2. A=distributivity of implication over disjunction
3. A= distributivity of implication over disjunction
4. A=
5. A=
6. ;
Problem 15. Using the semantic tableaux method check if:
1. .
2. |=
3.
4.
5. |=
Problem 16. Using the sequent calculus check if the following sequent is true or not.
- .
3.
4. .
5.
6.
Problem 17. Prove the validity of the formula A using the sequent calculus method:
1)A=, distributivity of over
2)A=, reunion of the premises
3)A=
4)A=, distributivity of over .
5)A=, separation of the premises
6)
Problem 18. Using the sequent calculus check if:
1) |=
2) |=
3)
4)
5)
6)
Problem 19.
Using general resolution prove that the following formulas are tautologies:
1)
2)
3)
4)
5)
Problem 20
Using lock resolution check the inconsistency of the following sets of clauses:
1),
2),
3),
4),
5),
Problem 21
Check if the following deductions are valid using linear resolution:
1)
2)
3)
4)
5)