Results 1 to 6 of 6

Math Help - Proof of distributivity theorem in the equational logic

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    9

    Proof of distributivity theorem in the equational logic

    Hi,

    I've recently begun studying equational logic E, that outlined in Gries and Schneider's Logical Approach to Discrete math, and I'm working away proving each theorem in turn.

    I've stumbled on theorem 3.45 (Distributivity of \vee over \wedge): p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)

    and theorem 3.46 (Distributivity of \wedge over \vee ): p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)

    As usual, they can only be proven with theorems and axioms of a lower number, and truth tables aren't allowed. I keep starting off by going for axiom 3.35 (Golden rule): p \wedge q \equiv p \equiv q \equiv p \vee q, to transform (in the case of 3.45 obviously) (p \vee q) \wedge (p \vee r) as my first step. Does anyone have any hints as to where to start? Am I headed in the right direction? How would anyone else prove these?

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Stephen Shaw View Post
    I've recently begun studying equational logic E, that outlined in Gries and Schneider's Logical Approach to Discrete math, and I'm working away proving each theorem in turn.
    I fear that we may not be able to help you. There may be one of the regulars who may know that particular textbook. The way the question is asked, it is absolutely necessary to have that exact edition of the textbook. I have never even seen a reference to it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    9
    Hmm. I was of the impression that E was quite a well-known logic :-(

    Even if people don't know exact theorem numbers, is there any formulaic manipulation that they would do to show that the LHS equals the RHS? I'd quite like to be able to work formally it start-to-finish by myself, but I'm just trying to take some step in the right direction!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Stephen Shaw View Post
    Hmm. I was of the impression that E was quite a well-known logic.
    So far as I know, it is not. But I am in the USA.
    I will say that I am a bit suspect of a text that does not use truth-tables for these simple properties. They must be developed is a sequence of definitions and axioms. We donít have them.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    Posts
    9
    Well obviously the fundamental axioms have to be proven by truth tables, and it would be a trivial task to prove the above theorems by truth table. But that's not the point of the exercise. The idea is to formulate theorems from other theorems without explicitly evaluating their truth values, to foster skills in formal symbol manipulation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I found this book in Google Books. While propositional logic is completely standard, calling it "equational logic" is uncommon. Their axioms are equally eccentric, in particular in treating equivalence \equiv as associative. In general, their rewriting approach is a little too algebraic to the detriment of presenting logic as the study of the laws of reasoning. So if I didn't know how to prove some theorem in this particular version of propositional calculus, I wouldn't be too upset.

    There is an interesting question why formal logic is taught in discrete mathematics courses at all. I support teaching Boolean logic because, for example, it won't be good if a programmer cannot quickly prove the equivalence of two tests, even though he/she is reasonable smart and understands logical operations in principle. However, it has long been not clear to me how the study of formal proofs, with all those in-house bookworm overly syntactic ways of manipulating strings of characters helps with the development of either mathematical maturity or appreciation of usefulness of logic. Teaching typical Boolean-algebra, rewriting inference rules that are advocated by the book in question may not produce much in this respect. It may not be more effective that teaching any mathematical topic at all. Working through any mathematical subject will implicitly teach students proper laws of reasoning, which is probably the greatest benefit of such courses for future programmers.

    However, I believe that teaching formal proofs may have benefit if it is done right. For this, one has to forget about the relation between inference rules and truth tables for a moment. Each of the connectives (\land, \lor, and \to) has to be considered separately, in terms of what it takes to prove a formula with this connective and how such formula can be used to prove others. Under this view, the laws that allow expressing one connective via another, like De Morgan laws, suddenly become non-obvious, and indeed, they cannot be proved without the law of excluded middle, which is a completely different beast by itself. In fact, the first propositional axiom of the book, ((p\equiv q)\equiv r)\equiv(p\equiv (q\equiv r)), is false under this interpretation. Only then can it be seen that there is a clear connection between proofs and programs, in fact, that proofs are programs. Therefore, teaching formal logic is nothing different from teaching programming. I am wondering if students would be more excited about learning formal proofs if they understood this.

    This approach to logic (not so much to teaching) is not my own position. It is a well-known and often taught subject (see, e.g., this course and especially this text).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving a Theorem (Predicate Logic)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 13th 2011, 04:57 AM
  2. Replies: 13
    Last Post: May 6th 2011, 10:16 AM
  3. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  4. How to prove distributivity of cardinals?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 31st 2010, 05:50 AM
  5. Distributivity of Cardinal Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2009, 06:29 AM

Search Tags


/mathhelpforum @mathhelpforum