Results 1 to 3 of 3

Math Help - Logic: formulas, proof

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    5

    Logic: formulas, proof

    Hello!
    I have just started learning logic and have to idea how to solve this, can anyone help with ideas please?

    Prove that a formula that contains only variables and equivalence and negation as operations is identically true if and only if the number each variable and operation of negation appears in the formula is even.

    Thank you in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Interesting problem. An obvious idea is to try proving this by induction on formulas. However, as often happens, one needs a stronger induction statement because in a formula A <-> B, A and B separately don't have to be tautologies or contain even number of occurrences of each variable even if the whole formula does this. So the challenge is to come up with a generalization of the claim that will let induction go through.

    I'll denote truth values by T and F. Let is call a formula A(p) containing a variable p stable with respect to p if for all values of other variables, A(T) and A(F) have the same truth values, i.e., A(T) <-> A(F) is a tautology. Similarly, A(p) is called unstable w.r.t. p if for all values of other variables, A(T) and A(F) have the opposite truth values, i.e., A(T) <-> A(F) is a contradiction. Note that if A is not stable w.r.t. p, it does not necessarily follow that it is unstable w.r.t. p.

    Lemma 1. Let a formula A(p) be built from variables, truth values, equivalences and negations only. Then A is stable w.r.t. p if the number of occurrences of p is even, and A is unstable w.r.t. p if the number of occurrences of p is odd.

    Proved by induction on A.

    Corollary. If a formula as above contains even number of occurrences of every variable, then it is either a tautology or a contradiction.

    Lemma 2. A formula built from T, equivalences and negations only is true iff it contains an even number of negations.

    Proved by induction.

    From this the claim follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    5
    Thank you! I appreciate it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of F-statistic Formulas
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: December 5th 2012, 09:24 AM
  2. Help with logic formulas
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 20th 2011, 10:34 AM
  3. derive formulas in mathematical logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2010, 02:25 AM
  4. Proof: recursive and closed formulas
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 28th 2010, 05:49 PM
  5. Mathematical logic - String formulas and Godel numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 10th 2007, 04:04 PM

Search Tags


/mathhelpforum @mathhelpforum