1

Now I have been researching this for the last couple of hours trying to understand this, looking at similar questions asked on Stack but I am still very confused.

This question was asked by another user a while back: Show that a set of logical connectives is expresively complete

The question was:

Show that a set of connectives {∧,¬} is expressively complete, given that {∨,∧,¬} is expressively complete.

I do not get the actual principle of what we are doing. Am I right in saying we are given the fact that all propositional formulas can be expressed in terms of {∨,∧,¬} and we need to see if these propositional formulas that are expressed in {∨,∧,¬} can be expressed as {∧,¬}?

I don't really get the steps to how you show this? Is there like a template step by step format you can follow to answer questions like these? Do we have to prove we can derive formulas that contain {∧,¬} only from each formula in this set {V,∧,¬}

Thank you

computerscienceisapain
  • 238
  • 1
    Just note that $(p \vee q ) \Leftrightarrow ; (\thicksim( \thicksim p;\wedge \thicksim q))$. – Emad Aug 18 '21 at 19:58
  • I know that but it doesn't answer any of my questions in OP @Emad – computerscienceisapain Aug 18 '21 at 20:03
  • So the answer is yes. Since you can express every propositional formula by ${\vee, \neg, \wedge}$ you only need to replace every occurrence of $\vee$ by $\wedge$ and $\neg$ using the note I stated. So the ${\neg, \wedge}$ is functionally complete. The procedure for solving questions similar to this is using the completeness of ${\vee, \neg, \wedge}$ and noting that you can't express $C$ without $\neg$. This way you can find all different subsets of functionally complete logical operators. – Emad Aug 18 '21 at 20:14
  • Can you replace every occurrence of ∨ by ∧ and ¬ separately or do you need to do it combined like how you did in the note? Also wdym by C? @Emad – computerscienceisapain Aug 18 '21 at 20:19
  • No. You should do it in a combined way. – Emad Aug 18 '21 at 20:20
  • So how do you Show that the connective ↓ is adequate for propositional logic given that you know that the set {¬, ∨} is complete? @Emad – computerscienceisapain Aug 18 '21 at 20:22
  • Let us continue this discussion in chat. – computerscienceisapain Aug 18 '21 at 20:22
  • $C$ is contradiction. And you will find the answer to your last question in the book logic for mathematicians by Hamilton. – Emad Aug 18 '21 at 20:26

0 Answers0