1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Boolean proofs

  1. Sep 19, 2009 #1
    1. The problem statement, all variables and given/known data

    Let [itex]|A|[/itex] denote the weight function in this way:


    | ┐|=0


    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 [itex]A[/itex] is non-negative (i.e ⩾ 0)
    2. Relevant equations

    p,q,r,s (variables)

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

    3. 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).

    [tex]|u_1u_2\cdots u_n|=\sum_{i=1}^{n} |u_i|[/tex]

    where [itex]u_1, u_2, \cdots , u_n[/itex] denote one of the symbols (in the 2. Relevant 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 [itex]\land[/itex] 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.



    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

    |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) ?
    Last edited: Sep 19, 2009
  2. jcsd
  3. Sep 22, 2009 #2
    Any help please?
  4. Sep 22, 2009 #3
    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) [itex]|\neg p|=-1,|p \wedge q| = -1[/itex].

    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) [itex]|p \vee q| = |p \rightarrow q| = |p \leftrightarrow q| = -1[/itex]

    and that should be enough for structural induction to work.

  5. Sep 22, 2009 #4
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook