Logic Statement Weights - Proving Sum is -1

[njama]

Homework Statement

Let |A| denote the weight function in this way:

|=>|=|⋁|=|⋀|=|<=>|=+1

| ┐|=0

|p|=|r|=|s|=-1

Now I need to show that one statement to be logic statement the sum of all symbols need to be -1, and the sum of the symbols in every series, starting from A is non-negative (i.e ⩾ 0)

Homework Equations

p,q,r,s (variables)

⋀, ⋁, =>, <=>, ┐ (relations)

The Attempt at a Solution

Let me check what the task is denoting to proof.

p => q

sum: p (-1), => (+1) , q (-1) , -1+1-1=-1 (which is true)

((┐p)=> (q V (┐s)))

sum: ┐(0) p (-1), => (+1), q(-1), V (+1), ┐(0), s(-1) , 0-1+1-1+1+0-1=-1 (again true)

(Sorry for not mentioning, it should actually be in Polish notation, so there is no confusion)

Till' now we sow that the thing really works. Now the harder thing (to prove it).

|u_1u_2\cdots u_n|=\sum_{i=1}^{n} |u_i|

where u_1, u_2, \cdots , u_n denote one of the symbols (in the

Homework Equations

, I call them symbols)

For the first part of the task I need to prove that the sum equals -1.

By definition every logic variable (p,q,r,s) is logic formula. Also by definition if p is logic formula then (┐p), (p \land q), (p V q) and (p <=> q) are also logic formulas.

So by definition every logic formula can contain at least one logic variable (p,q,r,s). If there are two logic variables then it is again logic statement (for ex. p=>q), but there are 2 logic variables (p,q) and one relation (=>).

Other examples.

p=>q=>r

p<=>q<=>r<=>s

We can see that the number of variables (p,q,r,s) is always greater (for 1) of the logic relations (=>,v, <=>)

p (1 variable, 0 relations)

p=>q (2 variables, 1 relation)

p=>q=>r (3 variables, 2 relations)

p=>q=>r=> . . . => s (n variables, n-1 relations)

Now using the weight function

variables:
|n|= n* (-1)=-n

relations without ┐:
|n-1| = (n-1)*(+1)=n-1

┐:

The number of ┐ could be ⩽n

The number of ┐ could be 1,2,3,..., n

|n|=n*0=0, |n-1|=(n-1)*0=0

sum: n-n-1+0= -1

Did I do the proof correct for the first part) ?

 

[njama]

Any help please?

 

[Elucidus]

There are multiple ways to do this. One way deals with the completeness of logic using only negation and conjunction. So you need only show that

(1) |p| = -1, |q| = -1

(2) |\neg p|=-1,|p \wedge q| = -1.

Then by structural induction, the weight of any well-formed logical expression (proposition) must be -1.

Alternately (if you are not willing to accept equivalent expressions having equal weight)

prove in addtion to the 2 above:

(3) |p \vee q| = |p \rightarrow q| = |p \leftrightarrow q| = -1

and that should be enough for structural induction to work.

--Elucidus

 

[njama]

Thanks for the help but unfortunately I am totally inexperienced with structural induction. I need something simple, because this topic covers the my first course (not advanced) of Boolean algebra.