Question

Need some help with mathematical logic:
Prove that (A → B) ~ (¬A ∨ ¬B).
My book says that it is always true, however i can not understand why. I tried making tables of truth, but it is not getting anywhere...

Answer 1

My initial table of truth:
A B "A" "B" ("A" ∨ "B") (A → B)
1 T T F F F T
2 T F F T T F
3 F T T F T T
4 F F T T T T

So, (A → B) ~ ("A" ∨ "B"):
1 F
2 F
3 T
4 T

Answer 2

Where did I make a mistake?

Answer 3

I don't understand your problem. Can you take a snapshot?

Answer 4

@Loser66 I had found a way to denote the negation (that's what I had meant with inverse). Now question is exactly as what was stated.

Answer 5

@sleepyjess

Answer 6

I have rewritten the question and my attempt to solve in a fancier manner (with table and such) on MSE: http://math.stackexchange.com/questions/1925326/mathematical-logic-problem-about-proof

Answer 7

Your textbook is wrong

Answer 8

Below is correct :

(A → B) ~ (¬A ∨ B)

Answer 9

@ganeshie8 I think it is the first time I had spotted a mistake in my textbooks, but it's awesome to know that I wasn't wrong (tried doing the same thing with (A → B) ~ (¬A ∨ B) and I got the right result) Thank you very much for spotting it! :)

Answer 10

Nice, looking at truth table may not satisfy you. You should try and get convinced of the result in other ways..

Answer 11

@ganeshie8 what do you mean?

Answer 12

\(A \to B\) is false only when A is true and B is false, yes ?

Answer 13

If it is raining, you will carry umbrella.

A : it is raining
B : you carry umbrella

Answer 14

Notice that the statement says what you do when it rains. (A is true)

It doesn't say anything about your actions when it doesn't rain. (A is false)

Answer 15

That means the statement holds true no matter what you do when it doesn't rain.

Answer 16

That's quite an interesting example! Thank you for providing it! When I first looked at the truth table it looked like I was supposed to memorize it (as always - a sign that I am not understanding something), but after some googling I understood that it is quite hm... logical.
It is really fascinating how mathematical logic is connected so much with every day life (it sounds quite stupid, when put into words, but I mean that it's quite interesting how we can put everything in a few tables and it explains a lot of things that happen every day).
It was very interesting for me to learn that we can apply a few mathematical rules to simplify electrical circuits! :)

Sorry to bother you, @ganeshie8 but could you think of a way to represent "~" with some kind of real life example (like the one with umbrella)?

Answer 17

By "~", do you mean "negation" or a "tautology" ?

Answer 18

I think that I am talking about tautology.

Answer 19

tautology is simply another way to say the same statement

Answer 20

Consider below statements

statement1 : I am your sibling

statement2 : You are my sibling

Answer 21

Would you agree that they are logically equivalent ?

Answer 22

Yes.

Answer 23

We call it a tautology and represent it as :

statement1 \(\iff\) statement2

Answer 24

Proper symbol to use is \(\iff\)

May I know why you're using ~ for tautology ?

Answer 25

Oh! You were right saying that truth tables are not the right way to look into this!
Well, my book tells me that it is either double arrow (that you used) or ~, but I have no idea how to write double arrow, so I am using ~.

Answer 26

Okay, I see... good. So a tautology is when you have two logically equivalent statements. You may think of that sibling example and double implication when you see a tautology

Answer 27

Do you see why below is a tautology ?

(A → B) ~ (¬A ∨ B)

Answer 28

In other words, why the expression to the left of ~ is logically equivalent to the expression on the right ?

Answer 29

Yes, both (A → B) and (¬A ∨ B) produce the same results, so they are logically always equivalent.

Answer 30

Can you see that with out using truth tables ?

Answer 31

familiar with Demorgan laws ?

Answer 32

No, I can't. And I am not familiar with it. Truth to be told, it was the very first problem I had tried to solve using mathematical logic and all those symbols.

Answer 33

Demorgan Law1 :

\(\neg (A \lor B)\) is logically equivalent to \(\neg A \land \neg B\)

Answer 34

When you're free, may be cookup few examples and try to figure out how/why demorgan law works..

Answer 35

Do not depend on truth tables so much, use and/or/not logic instead

Answer 36

Truth tables prove things, but they don't help you learn anything new..

Answer 37

What do you mean by and/or/not logic?

Answer 38

Every statement in logic can be represented using those 3 symbols

Answer 39

Let me show you quick how (A → B) and (¬A ∨ B) are equivalent using simple words

Answer 40

I am very eager to see that :) (I had worked it out using tables again)

Answer 41

We know that A → B is false only when A is true and B is false, yes ?

Answer 42

its raining outside, but you're not carrying umbrella

Answer 43

That is the only way to violate the statement :
If it is raining, you will carry umbrella.

Answer 44

Yes, I understand that.

Answer 45

We know that A → B is false only when A is true and B is false.

That is same as saying A → B is always true except when A is true and B is false.

Answer 46

Next look at "or" logic.
"X or Y" is always true except when X is false and Y is false, yes ?

Answer 47

Yes.

Answer 48

(Sorry for delays before my answers - it's very unusual for me to see everything put into words. I played around with and, or, not logic with programming, but never tried to put everything into words and it stayed as an idea without a clear formulation in my head)

Answer 49

OH! Now I see what you meant. It's quite interesting! I am going to try and solve all the problems using such method without really relying on the tables (although table is a description of and/or/not, so in a way it is still relying on it ;) ). Thanks for showing it to me!

Answer 50

Basically, what you meant is to look at the cases when it's false, yes?

Answer 51

Yes, there is only one false case. Looking at 1 case is easier than looking at 3 cases, right ?

Answer 52

Saying

"last week, it didn't rain only on sunday"

is easier than saying

"last week, it rained only on monday, tuesday,..., saturday"

Answer 53

both convey the same information, but the first statement certainly looks simpler

Answer 54

How would you go about simplifying the logical statements, @ganeshie8? For example this one:
((A1 v A3) ^ A2) v (A1 ^ ¬A2 ^ A3) v (¬A1 ^ ¬A2 ^ A3). Is it possible to simplify this without a need of truth tables?

Answer 55

Yes, that is specially made to simplify with out using truth tables.

Answer 56

First lets look at few things quick

Answer 57

1) what's the truth value of the expression \(A \lor \neg A\) ?
Does it evaluate to true or false ?

Answer 58

example :

I'll be happy if it rains or doesn't rain tomorrow.

\(A\) : it rains
\(\neg A\) : doesn't rain

Would I be happy tomorrow in regards to raining/not raining ?

Answer 59

@ganeshie8, sorry that I hadn't responded - was in school.

it would always be True.

Answer 60

Let's use 1 to mean false and 0 to mean true

Answer 61

With above notation,

\(A \lor \neg A = 1\)

Answer 62

Let me ask you another question. In algebra, what do below expressions refer to ?

1) xy
2) x + y

Answer 63

Well, it is multiplication and addition, isn't it, @ganeshie8 ?

Answer 64

Yes, why are we using a special symbol "+" for addition and not using any symbol for multiplication ?

Answer 65

Because it looks simple and clear if we don't use \(*\) or \(\times \) to mean multiplication

Answer 66

We can do the same in logic. It may look weird in the starting, but after using it 2-3 times, you will get used to it.

Answer 67

Lets use "+" to refer to "or" logic

and "nothing" to refer to "and" logic

Answer 68

For example :

\(A \lor B \) in our new compact notation becomes \(A+B\)
\(A \land B \) in our new compact notation becomes \(AB\)

Answer 69

Oh my! So, the problem gets down to: ((A1 + A3)A2) + (A1¬A2A3) + (¬A1 ¬A2A3), right?

Answer 70

It actually looks a lot less scary with arithmetic notation, hehe.

Answer 71

Looks nice, isn't it ?
One more thing before getting back to simplifying it

Answer 72

Let's use \('\) to refer to the negation \(\neg \)

Answer 73

For example
\(\neg A\) in our compact notation would be \(A'\)

Answer 74

Okay, like in physics.

Answer 75

Btw, this notation is not invented by me. All engineers use this notation..

Answer 76

Engineers like to simplify things, so trust that this new notation is going to help you understand logic faster and better ;)

Answer 77

Well, it already looks easier ;) (A1 + A3)A2 + A1A2`A3 + A1`A2`A3 = (A1 + A3)A2 + A2`A3(A1 + A1`), as I see.

Answer 78

Perfect!

Answer 79

Since x + x` = 1, like we talked earlier we can just "erase" that A1 + A1`?

Answer 80

Yes, replace that by "1"

Answer 81

Don't forget that \(AB\) means \(A \land B\)

Answer 82

(A1 + A3)A2 + A2`A3 = A1A2 + A2A3 + A2`A3 = A1A2 + A3(A2 + A2`), so the same thing and we get A1A2 + A3 and in symbolic notation it would be A1 ^ A2 v A3, it's same as the answer in the book (though, there are brackets around A1 and A2, how did they appear here?).

Answer 83

Seems that it's a lot easier to use the engineering notation :)
Maybe you know some more examples of such simplifications? It seems that my book provides only "prove X" type of problems and I am still not very confident with this simplification thing.

Answer 84

Yes, just so you know, the entire semiconductor industry is based on this simplification. We use computers to simplify these boolean expressions invonvling millions of or/and/not gates. It gets messy to simplify manually once the number of variables in the expression become more than 4..

Answer 85

Let me cook up an interesting expression to simplify..

Answer 86

xz' + xyz' = ?

Answer 87

hm, xz`(1 + y), since + is or, meaning that it is always true? since, we are comparing true and something with or statement. so, we get 1 + y = 1, then xz` is left, so x ^ z`.
Was that right?

Answer 88

Excellent! one more ?

Answer 89

Yes, I would be happy to see one more.

Answer 90

x + x'y = ?

Answer 91

Mmm...
Perhaps we can somehow make x to be x` plus or times something? Since we don't(?) have minus it would make sense, but I can't really figure out what to exchange x for...

Answer 92

Ahh sorry, it's a tricky one. Let me rephrase the q :

Prove
x + x'y = x + y

Answer 93

use any method

Answer 94

You may also argue in simple sentences and convey your understanding. Its considered a valid proof if it follows valid reasoning...

Answer 95

I see that it's not possible to add things to both sides, to prove this.
I also see a weird thing: 1 + x = 1, then I should be able to multiply anything by 1 + x without changing a thing, however:
x + x`y(1 + x) = x + y
x + x`y + y = x + y
Meaning that x`y = 0, which isn't really true? (It's weird to me since I arrived at this conclusion a few times, but it seems to be false to me)

Answer 96

You're wrongly assuming that x'x = 1

Answer 97

Check the red parts, they are not same.

x + \(\color{red}{x`y(1 + x)}\) = x + y
x + \(\color{red}{x`y + y}\) = x + y