Search code examples
mathdiscrete-mathematicsprooftruthtable

Understanding Truth Proofs in relation to proof tables

I have been doing discrete structures and learning truth proofs and the sort (ETC. ((A→B)∨B)→C, (¬p→q)⊕¬q, etc, can know how those work and how to arrive at an answer, however recently things similar to

A→B 
B→C     A∨¬B
B       ¬A
____    ____
A→C     ????
???

have appeared and I cannot find any information on that format or how to solve it on google, nor was I given any information about it and how to solve it, as such It is new and I do not know how to approach it. The closest I found to a similar source was google books on theories of computation and automata and algebra textbooks which seemed to reference them as matrices. I tried doing each truth table separate but could not find a pattern to link it.

Sources or examples as for how to deal with this sort of proof are appreciated. I have never come across this layout before, I very well may be something I know, just in a new format. Thanks for any relevant help in advance.

Solution

  • There are two ways to prove things in logic:

    1. by computing the value for all inputs and then verifying it's a tautology
    2. by using a proof system to manipulate the formulae to show it's a tautology

    You are used to approach 1. It is easy to understand and concrete. Approach 2 is more abstract and more difficult. To execute proofs in a proof system, you must first fix the proof system. This means declaring some axioms and rules of logical deduction.

    For instance, a simple system can be found here:

    1. A→(B→A)
    2. (A→(B→C))→((A→B)→(A→C))
    3. (¬A→¬B)→(B→A)
    4. Deduction is by Modus Ponens: A, A → B | B

    In this system, your proof might look like this:

    1. A→B, B→C, B | (A→(B→C))→((A→B)→(A→C))       (2)
2. A→B, B→C, B | (B→C)→(A→(B→C))               (1)
3. A→B, B→C, B | A→(B→C)                       MP on 2. and hypothesis B→C
4. A→B, B→C, B | (A→B)→(A→C)                   MP on 1. and 3.
5. A→B, B→C, B | A→C                           MP on 4. and hypothesis A→B

    At each step, you either introduce a new instance of one of your axioms or you apply your rule of deduction to produce a new line. From then on, you can use the lines so derived to derive new lines, until you derive the intended result.

    Your second one doesn't make a lot of sense since you can't prove something that hasn't been claimed. If you get something like that I suggest you just fill in the blank with something easy to prove, like true, and then state true in the proof and be done with it.