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 Logic - Many simple questions

  1. Nov 10, 2007 #1
    [SOLVED] Boolean Logic - Multiple simple questions

    My professor, he's a good, witty guy. He wasn't satisfied with other textbooks, so he decided to write his own. Since it's not published yet, we get a free pdf version of it, downloadable.

    Sadly, despite how good of a person he seems to be, he can't write a textbook for anything. It's very difficult to read without a dictionary and wikipedia at my side, and he fails to define many symbols and techniques, as well as providing zero examples or sample problems.

    So, now that we have an assignment, I'm lost, naturally. I'm very capable of doing this assignment on my own, however I have absolutely no clue what they're asking, as he never defined what half of these symbols and words mean.

    As such, I have a handful of small questions.
    In advance, thank-you for any information given; you're helping save my education :)

    1) [itex]A, A \rightarrow B \vdash B[/itex] - SOLVED -
    I know what 'A' is, and I know what [itex]A \rightarrow B[/itex] is. But what does it mean when you have a list of variables to the left of a [itex]\vdash[/itex] symbol? What does [itex]\vdash[/itex] mean, and what does the entire phrase mean?

    2) [tex]\frac{A, A \equiv B}{B}[/tex] - SOLVED -
    Is this division? I think it has something to do with my first question, but again, I wouldn't have a clue. What does this fraction-like formation mean?

    3) [itex]\vdash (A \rightarrow (B \rightarrow C))[/itex] - SOLVED -
    Again, similar to my first question... if there is no list to the left of [itex]\vdash[/itex], what does this mean? It may not matter, but since I don't know the answer to the first question, I haven't a clue.

    4) What's the difference between t, f, T, and [itex]\perp[/itex]? In theory, t and T both mean true, but apparently there's some kind of difference, as I lost marks for this. - SOLVED -

    5) What is the letter [itex]\Gamma[/itex] used for in this subject? It seems to be a set of formulae, or some kind of set, since my professor has been using [itex]\subset[/itex] and [itex]\subseteq[/itex] with it. - SOLVED -

    6) [itex]T \equiv \perp \equiv \perp[/itex] - SOLVED -
    I think this is saying that the statement "True = False" is false, but what does it mean when it has even more than two [itex]\equiv[/itex] signs, such as [itex]\perp \equiv \perp \equiv A \equiv A[/itex]? This likely has to do with hidden brackets, or my lack of understanding of the order of operations.

    7) What is the difference between [itex]\vdash[/itex] and [itex]\models_{taut}[/itex]? - SOLVED -
    Last edited: Nov 11, 2007
  2. jcsd
  3. Nov 11, 2007 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    This looks more like propositional calculus than boolean logic. I'll help where I can.

    Given that A and A implies B are separately true statements, therefore B is a true statement.

    It is tautologically true that A implies (B implies C).
    Except that is not the case. A=T,B=T,C=F. B->C=F, A->(B->C)=F

    It's his nomenclature, so what does he say in his notes and in class? While you are not entitled to a better grade because you think otherwise, you certainly are entitled to an explanation regarding why you lost marks. Don't be argumentative. Just ask for an explanation.

    "That true is tautologically false is tautologically false'
  4. Nov 11, 2007 #3
    If so, what is the difference between [itex]\vdash[/itex] and [itex]\models_{taut}[/itex]?
  5. Nov 11, 2007 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    More or less the same as the difference between [itex]=[/itex] and [itex]\equiv[/itex].

    There is no such thing as one standard nomenclature for propositional calculus and boolean algebra. Most textbooks have a nomenclature section. If yours doesn't, ask your instructor.

    A bit of reference on where these expressions arise would help. A Rosetta Stone would be nice ...
  6. Nov 11, 2007 #5
    Thanks, marked a few more as solved now. :)

    Looking back at 6, in lamens terms, would it be okay to say that the first equation means "It is untrue that 'True = False'."?

    And also in lamens terms, what would the second equation mean?

    Edit: Also, as you can see by my post count, I'm new here - is there any way I can give you homework helper points, or something that helps contribute to your awards? You're really saving my education here :P
    Last edited: Nov 11, 2007
  7. Nov 11, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    Reading back, I think you should read the answer to 5) first, or maybe even read the answers to 5) and 1) simultaneously... anyway I hope it's clear

    [itex]\Gamma \vdash \phi[/itex] means: there is a proof with assumptions [itex]\Gamma[/itex] and conclusion [itex]\phi[/itex]. So if the question is [itex]A, A \rightarrow B \vdash B[/itex], he most likely means: give a proof of B, assuming A and A -> B. Of course it is equivalent to prove [itex][ A \wedge (A \rightarrow B) ] \rightarrow B[/itex] :smile:

    The fraction-like notation is another way of writing it. Instead of [itex]\Gamma \vdash \phi[/itex] we can also write
    This notation seems a bit cumbersome, but (you'll probably learn later) that you can build clear proof trees from it, where each intermediate conclusion is under a bar with the assumptions to reach it above it (and you can even write the inference rule used to derive it next to it). E.g. the solution to 1) would be written
    [tex]\frac{A \qquad A \rightarrow B}{B} \quad \mathrm{\rightarrow E}[/tex]
    where I annotated the inference rule I used to derive B from the assumptions.

    For 3): [itex]\vdash \phi[/itex] is a shorthand for [itex]\emptyset \vdash \phi[/itex], which just means: [itex]\phi[/itex] is provable without assumptions, in other words: [itex]\phi[/itex] is a tautology (e.g. [itex]\vdash A \rightarrow A[/itex] is true).

    For 4): I don't think there is a difference. I usually use the latter two (T and inverse-T or perp-sign). You should ask your prof which convention is used in your class.

    5) As I said before, [itex]\Gamma[/itex] is a set of formula (usually, assumptions). For example, I could formulate 1) as :
    Define [itex]\Gamma := \{ A, A \rightarrow B \}[/itex]. Prove that [itex]\Gamma \vdash B[/itex].

    6) I don't quite see it either. I would say the notation
    [tex]A \equiv B \equiv C[/tex]
    means that A, B and C are (pairwise) equivalent, that is,
    [tex]A \vdash B, B \vdash A, A \vdash C, \text{ etc.}[/tex]
    but I don't quite see the use of this particular example. Of course, [itex]\perp[/itex] is equivalent to [itex]\perp[/itex]; and if T is equivalent to [itex]\perp[/itex] then it is equivalent to [itex]\perp[/itex] as well.

    Ah, I just realized (rather late) that the T in the statement is the "True" symbol. If you read it as I said above, then indeed [itex]\mathsf{T} \equiv \perp[/itex] is not true, even though [itex]\perp \equiv\perp[/itex] is.
    Last edited: Nov 11, 2007
  8. Nov 11, 2007 #7


    User Avatar
    Gold Member

    1. it means that B is deducible from A and A->B.
    2. the line means exactly like in 1, i.e that B is deducible from A and A<->B.
    3. it means usually that A->(B->C) is provable, deducible from the axioms schema you have in the system.
    4. well i dont know what it means in your terminology but perhaps it means that t is to mention if a proposition is satisfiable, i.e that it has a truth function which gives the proposition a truth value T.
    5. gamma in logic usually means a set of proposiitions or sentences (in predicate logic).
    6. my guess here is a wild one, but you look at the truth table of, double material implication then yes the result of T and false gives you false proposition.
  9. Nov 11, 2007 #8


    User Avatar
    Science Advisor

    Please do NOT post the same thing in different places. I have merged the thread from Math-set theory and logic with this thread.
  10. Nov 11, 2007 #9
    Was never my intent to do so.
    See here: https://www.physicsforums.com/showthread.php?t=197347

    I don't have the power to move threads, nor do I to delete my own self-created threads. I thought of this and tried, but found no way to do so.

    All questions solved, thanks :)
    I updated the title of the thread to say [SOLVED], but it isn't showing >.>

    These forums are much like my course - I have the intent to do things right and proper, but I screw up 'cause I haven't a clue what I'm doing :(

    Regardless, thanks to you all :)
    Last edited: Nov 11, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook