Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
2. (3 MARKS) Prove that the complexity of a well-formed-formula equals
the number of its right brackets.
Hint. Analyse formula-constructions, or use induction on formulas.
3. (3 MARKS) Prove that (p) is not a wff.
Hint. One way is to analyse formula-constructions.
4. (1 MARK) Prove that ((?(p → r)) ≡ (r → p)) is a wff.
5. (6 MARKS) Recall that a schema is a tautology iff all its instances are
tautologies.
Which of the following six schemata are tautologies? Show the whole
process that led to your answers, including truth tables or equivalent short
cuts, and words of explanation.
I note that in the six sub-questions below I am not using all the formally
necessary brackets.
Therefore be mindful of connective priorities and associativities!
A → B → (A → ⊥) ∨ B
A ≡ B → (A → ⊥) ∨ B
(A ≡ B) → A ∧ B
A → B → ?B → ?A
(?A) ∧ B ≡ A → B
A ∨ B → A → B
6. (3 MARKS) Prove that if we have > |=taut A, then we also have B |=taut A
for any B.
7. (6 MARKS) By using truth tables, or using related shortcuts, examine
whether or not the following tautological implications are correct.
In order to show that a tautological implication that involves meta-variables
for formulas —i.e., it is a schema— is incorrect you must consider a special
case that is incorrect (since some other special cases might work).
Page 2 G. Tourlakis
Show the whole process that led to each of your answers.
p ∧ ?p |=taut ⊥
p ∨ q ∧ r → r
00 |=taut >
p |=taut p ∨ B
A, A → B |=taut B
A ≡ B |=taut A ∧ B
A ∧ B |=taut A ≡ B
8. (6 MARKS) Write down the most simplified result of the following substitutions,
whenever the requested substitution makes sense. Whenever a
requested substitution does not make sense, explain exactly why it does
not.
Show the whole process that led to each of your answers in each case.
Remember the priorities of the various connectives as well as that of
the meta-expression “[p := . . .]”! The following formulas have not been
written with all the formally required brackets.