1

Question: For this logical expression without truth table please: $( → ) → $ and $( ∧ ) → $ are not equivalent based on truth table below:

enter image description here

Problem: Answer based on truth table is NO. But how to find out that they are not using logical equivalences please?

Avv
  • 1,159
  • 1
    Because $p\to q$ is true where $p$ is false and $q$ is true, so there are more conditions for $(p\to q)\to r.$ – Thomas Andrews Oct 16 '21 at 01:55
  • @ThomasAndrews. What would you recommend please to do this or something similar in less than a minute? – Avv Oct 16 '21 at 02:13
  • 1
    Going through these 22 identities helps develop a better feel for the behaviour of logical connectives (there is nothing special about this list; it's just the first result that Google returned). Do memorise #18, which helps to more easily compare formulae involving $\to:\quad p\to q :\equiv, \lnot p \lor q.$ – ryang Oct 16 '21 at 04:28

1 Answers1

1

Using basic equivalences you can only demonstrate further equivalences … you can’t demonstrate non-equivalence using equivalences… or at least not using equivalences alone. Something you could do is using equivalences to transform a statement into some kind of ‘canonical’ form, where each statement has exactly one canonical form, where any two statements that ate equivalent have the same canonical form, and where two statements that are not equivalent will have different canonical forms.

We could treat, for example, $(p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land q \land \neg r) \lor (\neg p \land \neg q \land r) \lor (\neg p \land \neg q \land\neg r)$ as a canonical form of $(p \land q) \to r$ … avoiding having to give an exact definition, I think the nature of this statement will give you the idea of what makes this ‘canonical’ … it basically picks out the rows of a systematically constructed truh-table where the statement is true

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Thank you very much. Do you think there is an approach to solve this and similar problems in a minute exactly please? – Avv Oct 16 '21 at 02:15
  • 1
    @Avra No, there is not. Since these kinds of problems can have arbitrary many variables, and since the time it takes to solve the worst case scenario depends on that very number of variables, no matter what speed you work with or whatever systematic method you use, there will always be a problem that will take more time to solve than whatever time you set out. – Bram28 Oct 16 '21 at 12:10