Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2020-06-22 21:28:54

Mknb
Guest

Discrete math

Solving this type of questions any method:

Question) Prove the validity of the sequent
a) -p -> p |- p

b) -p |- p->q


See book logic in computer science by huth 2nd edition pg 78.

#2 2020-06-22 23:00:36

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Discrete math

hi Mknb

I cannot view that book.  It seems to be out of print.

I've done some more research on logic in computer science.  I'm guessing that you are using - to mean NOT (that's not standard) but I cannot find anyone using the symbol | 

In case your computer is displaying this differently I'll describe how it appears to me . 
It is a vertical line a little longer than a letter l.

What is this symbol meant to be?  Commonly used connectives are IMPLIES, NOT, AND, OR.  IF you mean one of these please say which.  In other areas of maths that symbol can be used for SUCH THAT  and for DIVIDES but neither makes sense in the context of your question.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#3 2020-06-23 01:35:17

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Discrete math

hi Mknb

I still could not view that book.  The link fails for me.  I expect you have to be on the course for it to work.

But I found something called BACKUS NAUR form which told me what I wanted to know.  That | is an OR.  So I think I can have a go at these.

First you have to decide the order of precedence of the operators.  NOT should come first, then OR and finally IMPLIES.

So the first question is

NOT p IMPLIES (p OR NOT p)

What I have done is consider the two cases p TRUE and p FALSE.

The top two boxes below show me writing in T or F for p; then on the next line applying the NOT; then the OR; and lastly the IMPLIES.

If p is TRUE the statement is FALSE.

The second question has no brackets so, using precedence it ought to mean

(NOT p or NOT p) IMPLIES q.

That seems a bit silly for a question, so I've assumed it means NOT p OR (NOT p IMPLIES q).  Hope that's ok.

This time there are four cases to consider TT, TF, FT, and FF.  So I've done each and boxed it around so you can follow the logic.

All four cases lead to TRUE, so you can conclude this statement is TRUE.


qMaTSpr.gif

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

Board footer

Powered by FluxBB